Stack Overflow Could Explain Toyota Vehicles' Unintended Acceleration

New submitter robertchin writes "Michael Barr recently testified in the Bookout v. Toyota Motor Corp lawsuit that the likely cause of unintentional acceleration in the Toyota Camry may have been caused by a stack overflow. Due to recursion overwriting critical data past the end of the stack and into the real time operating system memory area, the throttle was left in an open state and the process that controlled the throttle was terminated. How can users protect themselves from sometimes life endangering software bugs?"

Comments

Re:Never use any software.

[Anonymous Coward]

Not using recursion in constrained embedded systems is a good start. It's been best practice since I started working with them 15 years ago.

coding standards

[lkcl]

... you know... i worked for pi technology in milton, cambridge, in 1993. they're a good company. they write automotive control systems, engine control management software, vehicle monitoring software and diagnosis systems and so on. one of the things i learned was that coding standards for mission-critical systems such as engine control have to be very very specific and very very strict. the core rules were simple:

1) absolutely no recursion. it could lead to stack overflows.
2) absolutely no local variables. it could lead to stack overflows.
3) absolutely no use of of malloc or free. it could lead to stack overflows.

now you're telling me that there are actually car manufacturers that cannot be bothered to follow even the simplest and most obvious of safety rules for development of mission-critical software, on which peoples' lives depend? that's so basic that to not adhere to those blindingly-obvious rules sounds very much like criminal negligence.

Re:coding standards

[Beryllium Sphere(tm)]

> I wouldn't want to drive a car which was designed on a budget restriction.

That criterion will eliminate a lot of confusing choice from your purchasing decisions.

Re:coding standards

[TopSpin]

This should be rule number one for this type of application.

Perhaps it should be rule number one, but actually it's Rule 16.2 of MISRA-C:2004 (Motor Industry Software Reliability Association, Guidelines for the use of the C language in critical systems):

Functions shall not call themselves, either directly or indirectly.

The rule actually appeared first in MISRA-C:1998. Each rule is accompanied by a detailed rationale that I will not reproduce verbatim here as the standard is not open; one must pay for the privilege. The rationale for 16.2 is that recursion may cause stack overflows. I only cite the rule itself because it appears in public testimony and also on the (first) page linked by this story ...... which you obviously did not read.

Because MISRA also disallows constructs such as function call indirection, self modifying code, etc. a compiler is entirely capable of detecting recursion and reporting the violation as an error. MISRA compliant compilers do exactly that.

Yes Virginia, the largest auto manufacturer on Earth ignores the very thing that was designed to prevent simple, common, easily predictable failures such as stack overflow despite the fact that the cost of compliance is much, much smaller than a rounding error for an outfit like Toyota.

Also, despite the fact that Industry dutifully identified this specific problem in a published standard at least 16 years ago, compliance is apparently not yet a requirement by government regulators. I suspect they're too busy investigating child seat manufacturers or Telsa batteries or whatever other politically high profile crisis that giant, engineer-free gaggle of NTSB lawyers fill their bankers hours with.

Re:coding standards

[ld a,b]

Sorry. I work in automotive embedded systems(although not personally in safety-critical parts we use the same parts and rules) and I can tell you rules like yours were behind this.

We are following all these rules and so we are safe. We can save a penny per 1000 units sold using a crappy MMU-less CPU.

First of all, following the stupid rules requires you to use baroque lint imitations which will go off on every line of idiomatic C. You need a paper trail to justify every line of code. Seems about right, people's lives are in danger, right?

Now consider that the controller system is hundreds of thousand of LOCs(for us it's more like millions). Most of that is crap boilerplate code required by the standards. This means if you follow that methodology strictly, you need hundreds of people going through mindnumbing lists of "You are not using this argument/This code assigning an argument to itself does nothing". Given that most software developers are inept and overworked, I can give you a certificate that there will be bugs.

It took me two weeks with the code to find a checksum function used all over the place that had been "fixed" to detect offset data after some earlier corruption bug was not detected.

Every 256 bytes "checksummed", a bit from the input would be left unaccounted(And it was actually used for data several times larger than that). I know for a fact that had to go through at least three source and design reviews and at least one more design review with some fat managers higher up.

Now tell me you feel safe.

Note to PHBs: Googleing up a fucking working CRC and getting a CS PhD to make a formal proof that it will work as intended would have cost far less.

Also, you see, the crappy CPU vendor stack measuring tools - that rules say we must use to guarantee safety - don't account for function pointers(they do show scary icons for recursive functions). They say foo(384) bar(uhhm... maybe 0?) I know to look for that when I add calls to function pointers, but I guess most people don't.

Now you add another rule. LOZRA 4092: You can't use function pointers at all.

Make my life more miserable, give the remaining work I will be unable to do to Dave, the monstera plant, or someone with the same programming aptitude.

I will give the crappy CPU/Compiler/RTOS vendors that should be sued free advice:

0- Add an MPU

1- Add canaries to every function call with any local variable at all(here it's not hackers it's programmers following LOZRA 396: cast the shit off everything so the compiler can't tell)

2- Add stack overflow canaries on every task switch. (add an MPU and align to page in the stack growing direction)

3- Add canaries to any memory pool allocation. (add MPU dead pages - You don't need RAM, just fucking address space of which you are using like 2%)

4- If any of the above traps, jump to a customer defined function(stored in ROM than can only be physically modified by outside hardware) that puts all vital hardware in a safe state, adds a record to the black box and reset the whole thing from scratch.

5- Forget about tasks and threads and move on to processes running on separate address spaces. If information must flow from a to b it better go through accepted channels. 6- Did I tell you to add a fucking MPU!?

Stack overflow vs. buffer overflow (difference)

[Trax3001BBS]

For anyone else that's curious; at first I thought it was double speak, so not to sound as bad.

Stack overflow refers specifically to the case when the execution stack grows beyond the memory that is reserved for it. For example, if you call a function which recursively calls itself without termination, you will cause a stack overflow as each function call creates a new stack frame and the stack will eventually consume more memory than is reserved for it.

Buffer overflow refers to any case in which a program writes beyond the end of the memory allocated for any buffer (including on the heap, not just on the stack). For example, if you write past the end of an array allocated from the heap, you've caused a buffer overflow.

http://stackoverflow.com/quest...

NO

[confused one]

First rule of real time: No recursion.

Re:Go Amish?

[dcw3]

The aerospace industry deploys bugs very frequently. Don't pretend like you don't. Yes, for some applications, we test the hell out of it, but bug free, hardly.

Re:This is a case of manual override

[jcdr]

Actually the brakes alone are enough to stop the car even in case of a full throttle bug.

Re:Motorcycles!

[Walter White]

Does it have an automatic transmission, and if not does it have clutch by wire?

Automatic transmissions are common (perhaps universal) on scooters and have been used on motorcycles in the past. The newest BMWs have ability to shift without pulling the clutch lever or reducing the throttle. From http://www.motorcycledaily.com... "The BMW Gear Shift Assistant Pro, available as a factory option, represents a world first for production motorcycle manufacture. It enables upshifts and downshifts to be made without operation of the clutch or throttle valve in the proper load and rpm speed ranges while riding."

Re: Live in a cave

[TWX]

In what car?! All modern mainstream vehicles still use a master cylinder in tandem with a booster and ABS. Even if you lose all engine power, should still be able to apply the brakes. Although it will require more force to push the pedal down, it should still be doable to bring the car to a complete safe stop.

The brakes are never adequate to overcome the power of open throttle. NEVER. One is expected to stop pressing the throttle when applying the brakes, that's why one is taught to use one foot for both functions, so that one does not push both pedals at the same time.

Braking subjects lots of parts to massive thermal changes. Those changes significantly reduce the effectiveness of the brakes after only a small amount of use. That's why race cars and other performance vehicles that are expected to have *ahem* spirited driving have much more expensive brake components, that fade less.

Lastly, look at burnout competitions. In those, someone spins their tires for as long as possible, generating smoke and noise, usually either the longest-burning or the crowd favorite wins. Unless a car has been modified to allow only the non-drive wheels to apply brakes, then the same brakes holding the car still (from a standing stop position mind you, not starting out in-motion) are easily overcame by the drivetrain. Yes, the drive wheels spinning in a burnout competition have their brakes applied and it doesn't do a thing to stop the wheels. Sometimes even the non-drive-wheel brakes are overcome in a burnout competition, and the car crashes into something.

My daily driver is a '95 Impala SS. 260hp, 330lbft torque. Tires are 255mm wide, about 10 inches, and are "W" rated, meaning that they're high-performance for grip and are capable of handling extremely high-speed rotation. On smooth, dry pavement or asphalt it's very hard to do a burnout, the car simply overcomes the brakes and takes off, and that's with probably 75% of the braking force on the front, non-drive wheels. A modern FWD car puts all of its torque into the wheels that would normally do the lion's share of the braking, so once they're overcome, the rear wheels aren't going to do squat to stop the car.

This error is VERY dangerous. The ignition key should ALWAYS overcome the throttle. The brakes should ALWAYS overcome the throttle. The gear shifter should ALWAYS overcome the throttle. Hell, even the four-way hazards should trip the computer into resetting the throttle algorithm.

Re:Never use any software.

[viperidaenz]

Because its very easy to overflow the stack? Embedded systems tend to have a limited stack space too.

Re:turn off the car?

[Anonymous Coward]

I tried to, but didn't find a single source to support your claim. Would you be kind enough to point it out?

Re: ieee floats

[JesseMcDonald]

Division by zero results in positive or negative infinity, depending upon the sign of the numerator.

False. Division by zero is simply undefined. Sometimes you can determine the limit of some function as it approaches a discontinuity due to division by zero, but the limit will depend on the function (not just the numerator) and possibly on which side you approach the discontinuity from. For example, the function x/x has a discontinuity at x=0, but the limit isn't infinity, it's 1. The function 1/x approaches positive infinity as x goes to zero from the right, and negative infinity as x goes to zero from the left; since these are not equal, the limit does not exist at x=0. On the other hand, the limit of 1/(x*x) at x=0 is in fact positive infinity, because the function approaches positive infinity from both sides.

If X divided by zero were actually defined to be "equal to" positive infinity for all X > 0, then you could turn that equation around and say that 0 * infinity = X. Since 1/0 = infinity, 0 * infinity = 1. And 2/0 = infinity, so 0 * infinity = 2. Ergo 1 = 2. (Or not...)

The problem is that infinity isn't a number you can calculate with; it's more of a trend, or a way to express the absence of a finite boundary. An expression is never "equal to" infinity, though it may approach infinity as some other condition changes.