News for hackers. Stuff that matters.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by patio11 on Monday September 06, 2010 @02:20PM (#1667117)
This was covered in our C classes in college, and it is probably more interesting for programmers here if you understand what the bug actually was.

The "software error" Wiki alludes to is that the Patriot missile kept track of its internal clock with floating point numbers. When the machine had been booted in the recent past, such as every time in testing, the floating point number spent most of its precision to the right of the decimal point. This let it able to do the designed behavior, which was calculate very small delta(time) to be able to do velocity/position calculations and get fairly close to fast moving objects then go boom.

The problem is that floating point numbers have a limited amount of precision available to them, and if you are using a few billion milliseconds (2 weeks), almost all of your precision is lost to the left of the decimal point (and, given that this is precision-intensive work, you didn't need to wait that long to see anomalies).

Lower precision meant that taking delta(time) got increasingly less precise as time went on. Which meant that velocity/position calculations got progressively more screwed up. Which meant the missile did not go boom in the general vicinity of incoming missiles. Which killed Americans and allies.

Thus the moral of the lecture: a) your computer is a powerful, tricksy beast which has many ways to trap you in even straightforward code and b) you should treat software quality like some 19 year old's life depends on it, because it might.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by davidw on Monday September 06, 2010 @04:08PM (#1667320)
> you should treat software quality like some 19 year old's life depends on it, because it might.

You should treat it like that if someone's life does depend on it and you have the resources to develop accordingly.

If you're developing something like, say, bingo software, you're probably better off devoting time to improving the product or marketing it, rather than working on it being 100% bug free.

It's all a tradeoff - time spent on eliminating every last little bug is time not spent on adding features or making it faster or marketing it or whatever.

Edit somewhat less clear-cut cases might be bits of software that you release publicly, and subsequently get used for life-critical systems. However, in that case, the onus is on those adapting the code for use in that environment to provide the testing/review/etc... rather than blaming the upstream developer.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by extension on Monday September 06, 2010 @04:29PM (#1667350)
That approach works if you know exactly what applications your code will ever be used for. If you are writing a library or a compiler or anything that will potentially be reused by unknown 3rd parties, then you can't be sure just how critically it will be put to use. There is no certification to distinguish software that lives can depend on.

That doesn't mean it's your fault if someone uses your free XML parser in an amusement park ride and your bug makes it fly off the rails. But I still wouldn't feel very good about it and would like to do everything I can to avoid it.

Also, when it comes time for you to write life or death code, it would be good if you already knew how to meet the required quality standard.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by Dove on Monday September 06, 2010 @04:44PM (#1667387)
There is no certification to distinguish software that lives can depend on.

Actually, there is. Google up "safety-critical software". And maybe "trusted software".

I work in military avionics; every dang line of code in the product, including any libraries we use, is vetted to death. If I were to try to just download a library off the internet and include it in the flight control software, I (A) wouldn't get away with it (B) would probably lose my job and (C) would confuse the hell out of my coworkers who all know I know better than that.

So don't worry someone will include your hastily-developed XML parser in safety-critical software without your knowledge. They won't unless you're willing to prove you've certified it to the level they require. And I promise you, that's not an exercise you'll forget having gone through. ;)

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by ssp on Monday September 06, 2010 @05:37PM (#1667463)
But then, how on earth did they manage to get this software certified if it did something as DailyWTF-worthy as using floating point for a clock?
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by Dove on Monday September 06, 2010 @06:22PM (#1667527)
Yeah. You should see some of the other stuff that makes it into production code.

I said there was a process. I didn't say the result was good software. ;)

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by gnaffle on Tuesday September 07, 2010 @09:30AM (#1668810)
According to http://www.cs.unc.edu/~dm/UNC/COMP205/LECTURES/ERROR/lec23/n..., the system stored the time in integers, but it was converted to floating point when doing the conversions. This conversion contained a small error that accumulated over time.

Keep in mind that things that seem very WTF to you, might seem more plausible when given more details about the subject.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by tetha on Tuesday September 07, 2010 @04:51AM (#1668420)
Well I have to give them that this is kind of a curious bug. I mean, you have to wait over 4 days until it triggers. Probably, this just worked whenever it was booted and tested, and booted and certified, because probably the certification did not involve ignoring the thing for four full days.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by phaedrus on Tuesday September 07, 2010 @07:39AM (#1668613)
According to a book I read about game testing it's common for commercial games to be run through a test of simply leaving the game on for hours or days to see if there are bugs that only show up in this way.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by regularfry on Tuesday September 07, 2010 @02:24PM (#1669639)
In part because the user manual included instructions to regularly reboot before precision became a problem. The users did not, because they didn't want to risk being in the middle of a reboot when a target went overhead.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by fshaun on Monday September 06, 2010 @08:33PM (#1667694)
Collection of bits are put to truly horrible uses in the name of efficiency.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by extension on Monday September 06, 2010 @05:50PM (#1667486)
My mistake, but this kind of methodology seems to be specific to a few industries like aviation and space, while being conspicuously absent from e.g. medicine. Ideally, the software industry would have its own life-critical standard that was applied across all domains, not that I'm suggesting such a standard is necessarily feasible right now.

Until we have such a universal standard, it is entirely possible for a bug in your free library to indirectly kill someone, in the course of everyday best practices.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by slavak on Tuesday September 07, 2010 @04:29AM (#1668402)
I have an incredibly hard time believing the medical industry does not have stringent standards in place for safety-critical software. Do you have anything to demonstrate this, and what country are we talking about here? (To remind me not to ever see a doctor there... :) )
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by extension on Wednesday September 08, 2010 @04:19AM (#1671352)
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by farmerbuzz on Wednesday September 08, 2010 @11:31AM (#1672138)
In the US, medical devices are regulated by the FDA. When it comes to using 3rd party software, the company manufacturing the device has the responsibility to ensure any 3rd party components function correctly. Its unrealistic to impose regulations on every piece of software that is written "just in case". It is far more practical to put the responsibility on the company doing the integration and selling the device.

Here is the guidance from the FDA on off-the-shelf software: http://www.fda.gov/MedicalDevices/DeviceRegulationandGuidanc...

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by davidw on Monday September 06, 2010 @04:35PM (#1667371)
You seem to have written this after my edit, which addresses that point. I'd feel bad too, but I'd feel bad if I had to hire a team of coders to review every line of my open source projects and document any change:

> "At the on-board shuttle group, about one-third of the process of writing software happens before anyone writes a line of code. NASA and the Lockheed Martin group agree in the most minute detail about everything the new code is supposed to do -- and they commit that understanding to paper, with the kind of specificity and precision usually found in blueprints. Nothing in the specs is changed without agreement and understanding from both sides. And no coder changes a single line of code without specs carefully outlining the change. Take the upgrade of the software to permit the shuttle to navigate with Global Positioning Satellites, a change that involves just 1.5% of the program, or 6,366 lines of code. The specs for that one change run 2,500 pages, a volume thicker than a phone book. The specs for the current program fill 30 volumes and run 40,000 pages."

From: http://www.fastcompany.com/node/28121/print

If there's no certification for ready-made life critical components, then that means the burden of reviewing, checking and verifying everything in the system is on whoever wants to use it in a life-critical environment.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by kiujygtyujik on Monday September 06, 2010 @04:55PM (#1667411)
This did meet the requirements for what it would be used for.

Intended to be based in Germany in the 60s facing the Russians it wouldn't be powered up for 600 hours, because in 60 hours you would have been overrun.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by ImperatorLunae on Monday September 06, 2010 @05:42PM (#1667471)
There's an old Tom Lehrer song, "So Long, Mom," about just that: http://www.youtube.com/watch?v=pklr0UD9eSo
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by kiujygtyujik on Monday September 06, 2010 @06:40PM (#1667558)
The British vulcan bombers of the same era had the range to reach Moscow - but not the range to return to the UK.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by gaius on Tuesday September 07, 2010 @03:11AM (#1668317)
I don't think that's true - Vulcans hold the record for the longest bombing mission even today (during the Falklands war). The secret is air-to-air refuelling...
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by fgf on Tuesday September 07, 2010 @05:14AM (#1668439)
might be hard to do that somewhere over poland if ww3 just started
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by gaius on Tuesday September 07, 2010 @05:36AM (#1668464)
USAF wargames discovered against F22s the most effective strategy to use would be tanker denial. Tho' with 4th generation fighters you would still need to outnumber them 6:1 (!)
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by kiujygtyujik on Tuesday September 07, 2010 @09:51AM (#1668865)
The astronomer Freeman Dyson was part of the operational analysis team in WWII that worked out it made most sense to only search for and attack refuelling and resupply U-Boats (milkcows)

The Vulcan flight gear famously included hiking boots so the crews could walk to Turkey after completing their mission

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by stretchwithme on Monday September 06, 2010 @08:14PM (#1667665)
ultimately, it is the responsibility of the integrator to test their systems, including the software. And they have the source code for everything. Its like Apple X 100.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by patio11 on Monday September 06, 2010 @11:51PM (#1667978)
Didn't see this last night. FWIW I agree with you, but that was not my recollection of the lecture as presented.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by jacquesm on Monday September 06, 2010 @05:05PM (#1667424)
There's an in-joke amongst embedded systems programmers, which is that if you need floating point you don't fully grok the problem (yet).

Floats are subtle, they can have exactly the kind of nasty little side effects that you overlook during testing and that bite you in a terrible way once you hit production.

Fixed point is the way to go to implement stuff like this, floating point is asking for trouble. Of course floating point is more convenient, but most people that use it don't really understand what's going on under the hood, and most of the time they don't need to.

But bank balances, clock values, GPS coordinates and other values of some importance are best represented in fixed point format. You'll have to do a bit more work when manipulating them but that pays off in reliability.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by jpr on Wednesday September 08, 2010 @02:46AM (#1671235)
Is there really any place where floating point is the right solution or default? I mean, all general purpose languages generally use floating point, but for general purposes, floating point isn't what you want. Or maybe it is, but it certainly isn't what I want.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by pvg on Monday September 06, 2010 @07:18PM (#1667602)
the Patriot missile kept track of its internal clock with floating point numbers

It didn't, really, and the bug itself is more convoluted than the loss of precision you are describing.

See the references:

http://www.mc.edu/campus/users/travis/syllabi/381/patriot.ht... and http://www.fas.org/spp/starwars/gao/im92026.htm

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by extension on Monday September 06, 2010 @04:08PM (#1667322)
A potentially more specific moral in this case is "beware of floating point numbers". Don't use them unless you really, really understand how they work, or if you are using them in a very conventional way, like with 3D graphics.

Inexperienced programmers often regard FP as magical numbers that do everything. It doesn't help that programming languages like JavaScript essentially treat them as such.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by gaius on Monday September 06, 2010 @04:33PM (#1667362)
See, there've been guided missiles since the 1950s. There'll be 60-something old geezers at Raytheon who have done missiles their whole careers, 30-40 years, and they would have been apprenticed to the previous generation of old geezers who had merely done missiles most of their careers. These guys should know this stuff by now.

Fatal errors are almost never a single thing going wrong unpredictably - they're a chain of events leading to an inexorable conclusion. Root cause - where were these guys?

It is possible to get this right: http://en.wikipedia.org/wiki/Sea_Dart_missile#Gulf_War_.2819...

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by azernik on Tuesday September 07, 2010 @12:41AM (#1668073)
The problem is, they never had to deal with software engineering; my mom, who served in the Israeli Navy in the late 70s, told me horror stories about the ship-to-ship guided missiles they dealt with. They were essentially analog electronics - addition done by adding voltages, for example - with error creeping in at every component. The way I remember her telling it, something like 30% to 60% of the things were down at any given time because some analog multiplier or adder had an error that was just a little bit too large. No one in the field was even thinking about software bugs at that point.

The reliable (and programmable) digital electronics were originally developed for ICBMs in the 60s, and only after quite a bit of miniaturization were they available for smaller guided missiles, meaning that there wasn't quite as much institutional experience of software engineering among guided missile designers as you'd think.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by varjag on Tuesday September 07, 2010 @08:23AM (#1668686)
Well, here SCUD (a technology obsoleted by 1960s) certainly worked, while the head-to-toes digital Patriot didn't.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by Symmetry on Tuesday September 07, 2010 @09:21AM (#1668788)
The SCUD was doing a much easier job, though. And the amount the patriot missed by is actually pretty close to the accuracy of a SCUD at hitting its target.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by varjag on Tuesday September 07, 2010 @01:07PM (#1669406)
The SCUD was developed in mid-1950s using technology pioneered in 1940s. Back then, the only feasible electronics were based on vacuum tubes. Noir films were hip, chrome fins on the cars were just in, ball joints in suspensions were about to appear, and it was socially acceptable to call black man a negro.

I think it did amazing job in the 90s against the arguably most technically advanced and innovative military, even more so considering it was pushed past its original specs.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by regularfry on Tuesday September 07, 2010 @02:44PM (#1669699)
They did get it right; the specs for the Patriot system allowed for rebooting every couple of days specifically to avoid this problem.

To my eyes, this is a classic training issue. Either the men on the ground were never told to reboot, or they were never told the consequences of failing to do so. Whether that failure was on the manufacturer's part for making crap manuals, or on the Army's part for screwing up the training, I don't know.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by extension on Monday September 06, 2010 @06:30PM (#1667534)
Well, nevermind. According to this, they were using 24bit fixed point, not floating:

http://www.ima.umn.edu/~arnold/disasters/patriot.html

Maybe a better moral is "avoid absolute clocks or counters, if at all possible".

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by sundarurfriend on Tuesday September 07, 2010 @08:15AM (#1668673)
This may be a naive question but: why did the error get accumulated over time? The original system clock was correct, and if they read from it every time and converted, the error would have remained at 0.000000095. Could someone explain how exactly this happened?
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by regularfry on Tuesday September 07, 2010 @02:37PM (#1669676)
The figure of 0.000000095 refers to the inaccuracy in the multiplier to get from the clock conter value to a value of time in seconds, not the inaccuracy in the clock itself. As the clock counter increases, the difference between the true time and the clock counter times the multiplier increases linearly.

Edited for clarity.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by jacquesm on Monday September 06, 2010 @05:08PM (#1667429)
In 3D graphics you need to do a lot of work beforehand on range checking your input data to make sure you don't end up with runtime overflows, which usually exhibit in visually very disturbing ways, such as planes that suddenly become transparent, pixels that flip from black to white or vv and so on.

It's very easy to destroy the illusion of a three dimensional graphic on a screen, these are very effective ways of doing so.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by bl4k on Monday September 06, 2010 @03:24PM (#1667234)
I thought that the experience of developing the GPS network (where all the sattelites and ground stations must be time co-ordinated to within 10+ decimal places in seconds) would have helped them with this missile system.

A GPS satellite travels much faster than a missile, and is accurate to within meters, so the tolerances are much higher (and the system was designed prior to patriot).

There is a definite 'not invented here' syndrome amongst defense contractors - I doubt they share any information, research or solutions amongst one other, which means the US tax payer foots the bill each time one of these contractors must independently develop and implement a system that has likely already been built in another part of defense.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by rdtsc on Monday September 06, 2010 @04:15PM (#1667332)
> There is a definite 'not invented here' syndrome amongst defense contractors

Yes. Especially because of contractors. A defense contractor is not going to its competitors in order to reveal and exchange know-how. That know-how is a trade secret that gives them competitive advantage. Except that in this case, lack of sharing results in making the same mistake multiple times, which results in loss of human life.

Interestingly lately I have observed that the government is trying to tighten up its defense spending belt and there is a tendency to develop more in-house rather than contract out. In order to gain public support the Congress keeps voting to increase the salary of service personnel. That leaves less money to spend on contracting out. So perhaps we'll see more sharing in the future at least between DoD's own projects.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by gaius on Monday September 06, 2010 @04:34PM (#1667367)
The DoD should have stuck to its guns (hah) and continued to mandate Ada.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by weaksauce on Monday September 06, 2010 @04:06PM (#1667315)
I would wager that some of the NIH syndrome is due to top secret requirements and blackops development that makes things tough to get at source code for other systems.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by Retric on Tuesday September 07, 2010 @10:45AM (#1668982)
It's much simpler to track and predict the position of objects orbiting the earth than moving though the atmosphere. Wind, temperature gradients, particulate matter, mist, etc add a lot of uncertainty to the predictions.

PS: As you increase accuracy more things become important factors. Large Ship guns actually started to track things like temperature at different altitudes to increase accuracy.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by regularfry on Tuesday September 07, 2010 @02:54PM (#1669730)
Also, a GPS satellite is actively designed to be found. A ballistic missile? Not so much.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by some1else on Monday September 06, 2010 @03:32PM (#1667253)
Oh, Interesting. I always figured GPS satellites were geo-stationary, but in fact (as you pointed out), they travel at 7000 mp/h :-0
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by pmjordan on Monday September 06, 2010 @04:04PM (#1667311)
Geostationary orbits would tie the satellites to being directly above the equator, which (a) would prevent the system from working beyond a certain latitude and (b) would cause an extremely bad distribution of "visible" satellites and angles between signals, precision would suffer.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by kiujygtyujik on Monday September 06, 2010 @04:57PM (#1667413)
Not to mention the transmitter power you would need if they were 25,000miles away in GSO rather than 90mi away in LEO
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by chrisbolt on Monday September 06, 2010 @05:43PM (#1667474)
GPS satellites are actually in MEO, at 12,500 miles away.

http://en.wikipedia.org/wiki/Medium_Earth_orbit

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by tetha on Tuesday September 07, 2010 @04:54AM (#1668421)
Note that while you sit on your chair, you are travelling pretty fast. Relativity for the win!
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by dagw on Monday September 06, 2010 @04:13PM (#1667330)
Moral c) The floating point numbers you use when programming computers are fundamentally very different from the numbers you'll see in math class. Any assumption that computer numbers and math numbers behave the same will eventually lead to bugs.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by some1else on Monday September 06, 2010 @03:42PM (#1667268)
It's truly remarkable how nobody cared to attend to the bug report about the drift, given that they are in the business of making missile pilot software, and it turned out they can issue a patch in one day. My teachers didn't have such a terrifying example at hand (they emphasize it with financial calculations), yet I still remember the issue and consider it when necessary. Poor QA :-S
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by joegaudet on Monday September 06, 2010 @04:37PM (#1667375)
I thought the issue was due to the binary representation of numbers like 0.1, 0.01, 0.001 being in fact non terminating fractions ala: 1/3 thus the longer the system ran the more small amounts of round off error it accumulated but adding two incomplete fractions.

I seem to remember this being the case in my numeric methods course, but maybe that was a different systme.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by slavak on Tuesday September 07, 2010 @04:24AM (#1668396)
This baffles me. Did the software engineers creating this not take a course on numerical analysis in college? Or were those, as so often are, electrical engineers that had been hired to do software work? The amount of misunderstanding in the industry about what it takes to create mission-critical software is incredible.
Re:Patriot missile software failure, 28 soldiers died. Fix: ... by assemble on Tuesday September 07, 2010 @09:08AM (#1668770)
Trust me, most of us EEs know -plenty- about floating point problems. We also have to take entire classes about how our work could kill somebody.

Bugs are bugs, errors and oversights happen. You have to deal with it, document what happened, and be vigilant to make sure it never happens again.

Re:Patriot missile software failure, 28 soldiers died. Fix: ... by ars on Monday September 06, 2010 @03:00PM (#1667196)
Do you know how they fixed it? I can think of a few ways, but I'm curious which they used.