Crashing an in-flight entertainment system

Algorithms are definitive. Programs are frequently inaccurate.

An interesting case of breaking a system comes from Hugh Thompson, who managed to crash a inflight entertainment (IFE) system on a flight from Las Vegas to Orlando in 2005. Most modern aircraft have entertainment systems built into the head rest of the chair in front through which passengers can watch TV shows, movies and play games. The system in question had a game of Tetris which had the option of modifying the number of blocks shown in advance before they start falling. Hugh pressed to + control to a maximum value of 4. Now thinking outside the box, he wondered if there were any other means by which to change the value. A small phone console in the arm rest proved to contain a numeric keypad which controlled the TV monitor. Trying various combinations of numbers: 10, 8 he had no luck. Then trying the value 5, the number of blocks changed. 5 is considered a boundary value, just beyond the maximum allowed for the field, 4. This is a classic off-by-one error often encountered when performing operations on structures such as arrays, or using loops. Now, hitting the + button on the screen, the value actually incremented to 6.

Likely the code was of the form:

keypressed(k);
if (k == "+" && (0 < nblocks && nblocks != 4))
    nblocks = nblocks + 1;

This would allow the number of blocks to be incremented if its value was 0 to 3. Once its value was 4, it would no longer increment. Because nblocks had been changed to 5, the expression holds true, so its value would be incremented. Hugh continued to increment the value until it was 127. 127 is the upper bound of a signed char, so that when the + key is pressed again, in all likelihood the value of nblocks will change to -128. Pausing for a moment to consider this, Hugh proceeded to press the + key once more, the display flashes -128 for an instant and then the screen goes black. Actually every screen in the plane, and the entire entertainment system crashed. A simple logic error.

Crashing in-flight entertainment systems has always been relatively easy – partially because they aren’t built very well.   Generally when one node crashes, the entire system is taken down. This may be due to a lack of testing in a real-time environment. This is however slowly changing as IFE systems become more in vogue. Boeing recently tested the IFE system in their 787 Dreamliner by having 250 employees play with the system on a 7-hour flight. The ultimate in real-world testing! Some airlines such as Hawaiian Airlines are debuting the use of iPads for their inflight entertainment – circumventing the need for proprietary IFE systems all together.

Why image processing can be perplexing.

Image processing sounds like a lot of fun. Until of course, you actually start processing images.

The problem with image processing is that depending on the problem, it can be extremely easy, or extremely challenging. The simplest of image processing processes involves cleaning up images by way of noise suppression, or image sharpening. These algorithms are subjective, in that their parameters can be tweaked in order to obtain the best result, at least to the eye of the beholder. Algorithms such as image thresholding can be used extract text from a scanned document by partitioning the image into black and white segments.

Increased complexity comes with algorithms that need to extract information from the image. The more complex the image, the harder the task. Grayscale images are useful when the image contains minimal or simple objects, otherwise colour provides increased information leverage. Consider the following example.

During WW2,  Allied planes released millions of bombs over Europe during aerial bombing raids. Some of these bombs exploded, leaving craters, others did not.  The monochrome image of Fig.1 shows a vertical photographic-reconnaissance aerial, taken from 10,000 feet, showing the southern entrance of the Saumur railway tunnel following the attack on it by 22 Avro Lancasters of No. 617 Squadron RAF on the night of 8/9 June 1944. The rationale is to derive an algorithm which can automatically scan the historic aerial image,  identify the bomb craters, then overlay these positions on a present day aerial image via image fusion. Sounds simple right? Actually the fusion/registration part is quite simple.

To the human eye, identifying the bomb craters in the historic image is a relatively simple task.

However deriving an algorithm to achieve the same is more challenging. Thresholding the image will partially work, but the result has to be processed further to actually extract the partial contours of the craters. Some sort of edge extraction might also work, but there will be a lot of spurious edges in the image, which will again have to be post-processed. Hough transform for circles? Requires good pre-processing. Template matching? May only work for craters with similar characteristics. Morphological analysis? Maybe, but that may be somewhat of a trial and error process. Why is it so difficult? Because the craters do not exist as a dark circle – typically half the crater is in shadow (which makes for a well defined contour), the other half in light (less well defined). Every algorithm will find some of the craters, but not all of them. Here’s an example.

Even more challenging? Identifying the bombs that impacted but didn’t explode, and in reality these are the ones that matter most. These appear as faint dark spots surrounded by a halo representing the imprint left from impact. The problem is they are so small that they can easily be mistaken for other landscape artifacts, e.g. trees. These are almost impossible to extract automatically.

And then once you have an algorithm, it needs to work on other images. However the caveat is that other images may not have the same appearance. The image below shows the majority of bomb craters as dark circular objects. It may actually be easier to derive an algorithm to find these, but then it wouldn’t work on the previous image. The processed image next to it shows a good portion of the bomb craters extracted using a local thresholding algorithm.

 

That’s why it may be easier to do it the way companies like Zetica do. Research the target area, use software to calculate the depth of bombs, scan the scene using a magnetometer, locate, dig, defuse and dispose of the munitions. Oh, and you can actually download the “UXB Depth Calculator” as an Android app.

Deriving an algorithm for this task may work better if the historic images were colour, to provide additional information. It may also be possible to look at similar applications, such as crater identification in lunar or Mars images – although these often make use of elevation data, and both the moon and Mars have somewhat barren landscapes. Any image analysis that involves partitioning or segmenting the image can be fraught with anguish. There is just no easy way to have a machine perform the same task as the human visual system.

Origami and algorithms

Think of origami and most people think of insects, birds, and animals made by folding paper. Yet the art of paper folding finds numerous applications, especially in fields such as mathematics and engineering. How can folding paper save your life? The methods of origami are synonymous with modern algorithms. For example the origami algorithms used to fold bugs are the same as the ones used to fold air bags [1]. Designing airbags requires a great deal of experimentation and computer simulation. All simulations start with the airbag folded up into a small packet, and whilst flattening a real airbag is not difficult, simulating the flattening process is. The process of finding creases to flatten an airbag is no different than finding the creases that turn a flat sheet of paper into a flat shape.

In 1995, Japanese scientists used origami concepts to pack and deploy a solar power array in the research vessel called Space Flight Unit (SFU). On Earth, the solar array was folded into a compact parallelogram, and then in space, it was expanded into a solar sail. The method of folding the solar panels is called “Miura-ori”, in honor of Koryo Miura, a professor in Tokyo University, who developed the fold.

Refs:
[1] Lang, R.J., Origami Design Secrets: Mathematical Methods for an Ancient Art, AK Peters, 2003.
[2] Cipra, B.A., “In the fold: Origami meets mathematics”, SIAM News, 34:4, 2001.

What is spaghetti code?

There are few programmers who haven’t heard of spaghetti code. But few truly understand it. There are often first year students who ask why they shouldn’t use goto statements in their code. It’s hard for them to understand partially because they have little context. Spaghetti code is intrinsically linked with the use of goto statements. When Fortran first appeared, the goto statement was one of the languages core control structures. It provided jumps from one part of the program to another part – often in an extremely unstructured manner. Languages that followed like Pascal, C, Ada, all had goto statements.

So adding one goto statement to a program may not seem like a big deal. But it is, and students don’t truly understand this. Until of course they have re-engineered a “small” vintage Fortran program. Then they get a true feeling for how messy unstructured programs are – pure spaghetti. Consider the amount of “jumps” in the following small legacy Fortran program from 1966.

A full description of spaghetti code with examples, can be found here.

iPhone 5s fingerprint reader hacked!

Shortly after the iPhone 5s began shipping, Europe’s largest association of hackers, known as the “Chaos Computer Club”  found a way of fooling the fingerprint reader and gaining access to an iPhone, bypassing Apple’s so-called biometric security shield. Here’s a link to their page describing the process, but it is incredibly simple.

1. Enrol your finger on an iPhone.
2. Photograph the finger with 2400dpi resolution.
3. Enhance, invert, and laser print on a transparency sheet (1200dpi).
4. Put white wood glue on the pattern created by the toner on the transparency.
5. Let it set until the latex fingerprint can be lifted from the transparency.

A more accurate fingerprint can be made using a photo-sensitive PCB material after step 3 (also described on their blog). What’s the moral of the story? Using fingerprint recognition for security doesn’t work too well. But the concept of spoofing isn’t so new. In 2002, Japanese cryptographer and mathematician Tsutomu Matsumoto showed how fake fingerprints could be made using the same material used to make Gummi bears. His experiments fooled fingerprint readers more than 67% of the time. A brief synopsis of fingerprint spoofing can be found here. Gelatin, plasticine, PVC glue… they all seem to work.

Don’t rely on fingerprint recognition to protect anything (that includes door locks with fingerprint access). Think fingerprint scanners that sense a pulse, or moisture in skin are any better? Think again, they too can be spoofed. Eye retinas might be better, or better still DNA. Let’ s see Apple stuff a DNA scanner onto the iPhone 6.

Software and redundancy

The term redundancy in an engineering sense implies duplicating critical components of a system with the intention of increasing its reliability. In some safety-critical systems such as fly-by-wire aircraft, parts of the system may be triplicated, such that an error in one component may then be out-voted by the other two. A good example is the SACEM system which controls train movements on the RER A (regional express metro) in Paris. The automated system optimizes the real-time running of each train. The ground based computers used in the system are duplicated and fitted with an automatic switch-over system in case of failure (the active computer is changed every day).

Hardware redundancy is not difficult because most times failures are statistically independent. The failure of a hard-drive on one machine will probably not preempt the failure of a hard-drive on another. A common mode failure occurs when one event causes multiple systems to fail. Software redundancy is more difficult because unlike physical structures, software has the same point of origin. Using the same algorithm, written using the same compiler, yet distributed on different machines does not imply redundancy. Ariane 5 contained both a primary and backup IRS, both with the same software, resulting in exactly the same behavior – they shut themselves down exactly as they were suppose to do. If the same software is used, then the same input will cause the same sequence of statements to be executed, resulting in the same outcome. To properly facilitate software redundancy, one must design software which does the same work, but is algorithmically different.