13 ms·
Are we shooting ourselves in the foot with stack overflows?
- jtokoph 13y agoMy first thought was: How could stackoverflow.com be responsible for car crashes?
- munimkazia 13y agoI am ashamed to admit that it took me a full minute to realize that they are not talking about the website.
- Theodores 13y agoI suggest we sing one tune to the song of another and re-purpose this thread to be about stackoverflow.com, as if nobody read the article!
- nyrina 13y agoI was thinking the exact same thing, and only saw the "s" at the end of Stack Overflow"S" when I came back to Hacker News
- slaxman 13y agoI was thinking the same thing until I read past the first 2 paragraphs.
- Helianthus 13y agoWhat's amusing is that the correct title of the piece (no plural on 'overflow') is more ambiguous. I wonder which way the HN title mods will rule.
- gkoberger 13y agoCompletely unrelated to yesterday's "I No Longer Need StackOverflow" https://news.ycombinator.com/item?id=7251169 https://news.ycombinator.com/item?id=7251169 I was all excited to defend StackOverflow.com.
- deleted 13y ago[deleted]
- wirrbel 13y agoFirst I was annoyed at yet another upvote fishing blog post on stack overflow. Then I read it, while I was annoyed at getting caught by the catchy headline that I conciously despised. Then I saw that it was not at all about some forum on the web and now I cannot stop smiling.
- deleted 13y ago[deleted]
- robryk 13y agoWould it be considerably expensive to check in runtime that SP is in an expected range every time it gets moved? This'd work with multiple stacks, too.
- simias 13y agoWell assuming you run in virtual mode you could always leave the page/segment directly below the stack unmapped, this way if the stack overflows it'll trigger an exception by accessing invalid addresses.
- prutschman 13y agoThere is an enormous class of embedded devices not running on chips capable of address virtualization.
- ctz 13y agoYou don't need virtual memory, just memory protection. Many microprocessors and microcontrollers offer just an MPU, without the full fat of address translation machinery needed for an MMU.
- sitkack 13y agohttp://www.freertos.org/FreeRTOS-MPU-memory-protection-unit.html http://www.freertos.org/FreeRTOS-MPU-memory-protection-unit....
- robryk 13y agoUnless you move the stack pointer by more than a page (the stack in Linux grows automatically: IIRC any access to at most 64k below the stack pointer is considered to be an attempt to grow the stack, because the compiler may very well reorder a change in SP in a function's prelude and an access to the newly-allocated stack frame). Edit: I'm sorry, I was somewhat wrong. Accessing stack below SP is considered a bug, but x86 enter instruction can make it seem like such an access has taken place if it faults: http://lxr.free-electrons.com/source/arch/x86/mm/fault.c?v=3.2#L1136 http://lxr.free-electrons.com/source/arch/x86/mm/fault.c?v=3...
- deleted 13y ago[deleted]
- skrebbel 13y agoCould you at least try to read an article before you comment? Like, at least the first 5 words?
- kens 13y agoIf I'm reading the testimony correctly, there is actually no evidence that a stack overflow caused unintended acceleration. The idea is that Toyota used 94% of the stack, and they had recursive functions. If (big if) the recursive functions used enough stack to cause an overflow, memory corruption could happen. If (big if) that memory corruption happened in exactly the right way, it could corrupt variables controlling acceleration. And then, maybe, unintended acceleration could occur. But that's a far cry from the stack overflow actually causing any cases of unintended acceleration.
- reddiric 13y agoI didn't read the linked article but I did look through the slides, which were very interesting and talked about - the abhorrent state of the engine control module code, - the RToS's design, - the critical data structures right above the stack, - that those critical data structures weren't mirrored to detect corruption as is standard and as they did for other data, - that single bit changes in that critical data structure right above a stack can cause the death of tasks in the RToS whose failsafe capabilities were located in those same tasks, and whose death was tested and confirmed to cause unintended acceleration consistent with accounts and descriptions of the event - that the failsafe monitoring CPU was not designed to detect this failure, and in fact Toyota outsourced its design and didn't even have the source code to it...
- pnathan 13y agoEffectively this is the total point of the transcript - that the system was fatally flawed in software design. Any number of bad things could have happened to cause catastrophic faults. Unintended accleration was demonstrated to be a result that could happen on a fault occurance.
- kllrnohj 13y ago> Unintended accleration was demonstrated to be a result that could happen on a fault occurance. Where was that demonstrated? It was hypothesized that it may be a result, but I'm not seeing anything other than speculation.
- xerophtye 13y agoSo what's the catch? We have been developing memory architectures, and embedded systems, and OS's for decades now. So if the solution is as simple as this post says, why hasn't it ever been implemented before? I am hoping there are experts here that can shed some light on this
- zurn 13y agoA mix of technological and cultural path dependence, cowboy attitude to performance/optimization, and inability to quantify risks. (Somewhat interrelated, eg cowboy attitude -> C, path dependency in C usage -> hard to reason about programs -> hard to quantify risks)
- pjmlp 13y agoI liked your "cowboy attitude -> C". Everyone is a C expert, except when they happen to be a tiny cog in a big coding machine. "I know where all my pointers are memory allocations are!". Sure, but does everyone on your 20+ people team from the intern up to the senior guys know? Then things like this are bound to happen.
- sfk 13y agoC is used in such applications precisely because it is one of the few languages that allow you to reason about things like stack usage. Try that in Python, Ruby (or ML for that matter).
- diydsp 13y agoThis. I've done consulting in embedded for years and years. The discipline of modern desktop/web development has not reached the embedded world, except in a few high-margin areas (such as military and transportation). There are 1,001 reasons for this, ranging from people who didn't learn source control, open source and unit-testing doing much of the coding (iow people from other disciplines besides software engineering and people who don't keep their skillset current), to the fact that cross-compiling is much harder/slower to debug than workstation debugging to the fact that resources are more limited in embedded, so code is more terse, with fewer convenient debugging functions. Other problems are with management- they see embedded code as a "write it and forget about it" schedule item, not a continuous improvement one. Much of this is due to the fact that embedded code is not as portable as workstation code. All of these shortcomings sufficed when the number of time pressure of embedded projects was much smaller 5-10 years ago. Now that embedded has exploded in ubiquity, its requirements are increasing and it's getting less time to be perfected in most markets. So yeah, I guess it's safe to say the embedded world is in a bit of crisis at the moment.
- pjmlp 13y agoAnother example of C's impact into our daily life.
- jmnicolas 13y agoAlthough I use managed languages, I wouldn't want my code audited by the NASA. When 180+ IQ brains analyze your work they're bound to find "horrible defects" that no "competent" programmer would ever make.
- tinco 13y agoI just refactored some code yesterday, I feel pretty confident, I'd love to know what they think :P Though my app is just some silly ruby code, not a realtime human life critical C embedded software.
- robinson-wall 13y agoUniversal law: look at your code again in a year and you'll wonder what the hell you were thinking.
- greatsuccess 13y ago2 weeks
- reeses 13y agoAwesome, let's walk through every library, system, and machine call exercised by your ruby code. What happens if you gc while hitting a chunk of ram that was just hit with a corruption causing cosmic ray while your OS paged out your app because your intrusion detection/prevention service went defcon two on a leap millisecond that was announced since your last OS patch and your locale was set to C? Please support your answer with tracing analysis over a set of one billion Monte Carlo simulations and present an accurate and up-to-date IDEF6 model of the application system.
- noelwelsh 13y agoIt's sad that recursion is considered dangerous. Tail calls have been known about for a very long time, and the duality between stack and heap for just about as long.
- Peaker 13y agoEven if you allow tail recursions, you still may want to disallow general recursions.
- reeses 13y agoTail calls are only helpful if optimized into jumps instead of function calls.
- pnathan 13y agoAnd this only happens if your compiler will recognize it. Not all compilers are smart enough. And embedded compilers often don't have the love that mainstream compilers get. In the absence of specific & concrete evidence that your compiler does this optimization and that you have and will tested this (including checking the emitted assembly code), it is correct to assume that TCO does not happen and to perfom stack depth analyses based upon that.
- pessimizer 13y agoIf you also built the computer, wouldn't you already have that specific and concrete evidence?
- pnathan 13y agoBeg pardon? I don't know what you mean. Most embedded companies purchase a chip... sometimes the compilers come from the same company that made the chip, sometimes not. Regardless, it's the engineer's responsibity to not assume about such a critical part of the design.
- hvidgaard 13y ago
- bjourne 13y agoEven if you work in a gc language with a vm and all memory errors are checked, here is the major, MAAJOR, wisdom you should take with you: The crucial aspect in the failure scenario described by Michael is that the stack overflow did not cause an immediate system failure. In fact, an immediate system failure followed by a reset would have saved lives, because Michael explains that even at 60 Mph, a complete CPU reset would have occurred within just 11 feet of vehicle’s travel. We have seen this scenario played out a million times. Some system designers believe it is acceptable to keep the system running after (unexpected) errors occur. "Brush it under the rug, keeping going and hope for the best." Never ever do that. Fail fast, fail early. If something unexpected happens the system must immediately stop.
- aninhumer 13y agoWhen you're talking about a control system "Fail fast, fail early" isn't necessarily an option. In this particular example, while it's arguable that temporary loss of control might be better than the actual outcome, it's still a pretty unacceptable thing to happen. At the point where you are trading off one failure state for another, you need to think very carefully about which one is truly worse, and sometimes "Fail fast, fail early" is a much much worse choice than the alternative.
- twic 13y agoWhen you're talking about a control system, you need to be able to safely recover from a hard crash anyway, because one could happen at any time for purely hardware reasons. Thus, forcing a hard reset in case of inconsistency should be safe.
- bjourne 13y agoExperience (which always should trump theories about how things should work) proves that you are wrong. What would have happened in this case if fail fast was used and the hardware had immediately resetted upon the first byte being written outside the stack area? Likely the bug would have been caught and fixed during testing because debugging a randomly resetting cpu is comparatively easy. It's a hundred times better than people being killed because small unexpected errors are allowed to accumulate.
- laichzeit0 13y agoI'm always skeptical about non-trival recursive calls and generally pass a "depth" variable in as the first param, increasing it each time I do another call, with some sane cut-off point where it just returns.
- nctalaviya 13y agomay be
- tragomaskhalos 13y agoI had an "unintended acceleration case" in my old Austin Morris 1300; the cable connecting the pedal to the throttle snapped, jamming it at a fixed (fairly high revs) level, requiring me to control the speed using the brake. The solution was to pop open the bonnet and swap in a replacement cable, which probably cost a couple of quid. This recollection combined with the Toyota story merely convinces me that automobile automation has got completely out of control.
- userbinator 13y agoI think this issue is more to do with complexity than anything else; my car has an ECU, it's based on an 8-bit CPU from the 70s, never had any problems with it.
- sitkack 13y agoSo does mine, and it is fuel injected. A cable controls a plate that controls the amount of air that gets into the engine. The only way for that design to fail WFO is for the return spring that keeps the plate closed to snap. At that point one would press in the clutch and turn off the ignition. This kind of user corrective action is not possible on modern cars which I consider a huge engineering flaw.
- aaronem 13y agoI'm not tremendously knowledgeable about automobiles, but in a car with an automatic transaxle, shouldn't dropping it in neutral and switching off the ignition do essentially likewise? I ask because that's how I practice responding to uncommanded acceleration, which I've done on occasion since I first heard of the failure mode. I've done this a few times a year in each of several cars, and as far as I can tell it's had no ill effect, but if "as far as I can tell" isn't far enough then I'd like to know it.
- sitkack 13y agoI know of no specific danger in shifting an AT into neutral. You need to be EXTREMELY careful when switching off the ignition that you don't lock the steering column. It would be better to * switch to neutral * safely exit the road and stop * turn off engine I am glad you have practiced it. My concern is over the code running tiptronic transmissions, they are computer controlled manual transmissions where you no longer have an effective physical connection.
- pwg 13y agoExample 7 on page 18 of "UNIQUE ETHICAL PROBLEMS IN INFORMATION TECHNOLOGY" by Walter Maner seems quite appropriate here: Quote: "A program is, as a mechanism, totally different from all the familiar analogue devices we grew up with. Like all digitally encoded information, it has, unavoidably, the uncomfortable property that the smallest possible perturbations -- i.e., changes of a single bit -- can have the most drastic consequences." http://faculty.usfsp.edu/gkearns/articles_fraud/computer_ethics.pdf http://faculty.usfsp.edu/gkearns/articles_fraud/computer_eth...
- raverbashing 13y agoThe least specialized in SW a company is, the worse the software is. What we are accustomed to in discussing in HN for example does not exist in these worlds. Continuous integration? Unit test? Even complexity analysis. And very very old code that's patched over and over and shipped "when it works" It's usually people who have had an academic contact with programming languages and embedded development and don't know anything about code quality. But you can bet their bosses incentive CMMI and other BS like that. (Yes, complete and utter BS) Not to mention ClearCase which seems to be a constant, the worse the company the more they love this completety useless piece of crap
- RogerL 13y agodoes not exist I've worked in that world for a long time, and I assure you we did continuous integration, unit tests, and complexity analysis." Way back in the early 90's, long before it made it into the general population, so to speak. I agree that there are terrible groups out there, but in general there is a far greater emphasis on safety, quality, and correctness than in the non-mission critical world.
- danielweber 13y agoYeah, the software methodology at car companies makes a lot of the seat-of-the-pants just-ship-it stuff that HNers are used to look like kindergarten. The car companies know how to do this. Maybe they messed up in this case (I'm skeptical of the article), but it's not because they don't know software.
- pnathan 13y agoYes and no. The transcript is very enlightening. It was extremely clear that on this particular project, the software development process was a total trainwreck. No one who was familiar with the SW dev literature had technical leadership and authority over the codebase. As a matter of fact, the transcript is so shocking it could be used as a manual of antipatterns for SW development both in embedded and out of embedded. A friend and I (we used to both work at an embedded systems company) spent an evening going over the transcript and mocking the errors. :-) By and large, the errors were of the design form. E.g., too much work on the critical threads. Not separating brake and acceleration threads. Four thousand globals. I think the cyclomatic complexity was something like > 1000 for the control path function. Etc. One of the remarks is actually that Toyota had taken some lessons learned from the time the codebase was developed and had been working on improving since then. So that's good.
- rcfox 13y agoTalking about how to catch stack overflows and protect your data against them isn't useless, but it misses the point. There are rules/guidelines, like MISRA[0] (which the testimony mentions 54 times!) for the automotive industry that prohibit recursion, and tools that will check for conformance. Toyota should not have been using recursion in the first place, and it seems they were too cheap to invest analysis tools like Coverity. [0] http://en.wikipedia.org/wiki/MISRA_C http://en.wikipedia.org/wiki/MISRA_C
- bad_user 13y agoTo me banning recursion in order to prevent stack overflows is like banning arrays to prevent buffer overflows. It misses the problem, doesn't it?
- rcfox 13y agoSort of, but not really... If you statically allocate an array, the compiler will ensure that you get the amount of space that you asked for, or raise a compile-time error. If you dynamically allocate an array (which you probably shouldn't be doing in this case anyway) then you'll either get a pointer to an array, or NULL. Either way, you'll know when it's safe to use the array. With a little bit of discipline, it's not difficult to avoid buffer overflows. Recursive functions don't have a guarantee of safely running. Yes, there are ways to show that certain kinds of recursion will always terminate, and it might even work when you're calling the function at the top frame, but what happens if it's called further down the stack? What happens if the data structure guiding the recursion changes and now it takes a deeper stack than before?
- bad_user 13y agoMost recursions can be written as tail-recursions. If the compiler can optimize tail-recursions, in which case it will behave like a loop and throw warnings when a recursion is not a tail-recursion, then the point is moot. With algebraic data-types and pattern matching, often used for indicating the stage of a recursion which includes the exit condition, the compiler can even warn you that you missed a branch. In fact I find it easier to come up with complex loops expressed as tail-recursions, because in time and with practice, it gets easier to reason about all the possible branches and invariants. The real problem is that we need a higher-level systems programming language. > Recursive functions don't have a guarantee of safely running. Neither do loops for that matter. A loop doesn't have any guarantee that it will ever terminate. Most stack overflows that happen are due to recursions with bad or missing exit conditions, but you can have the same problem with plain loops too. > With a little bit of discipline, it's not difficult to avoid buffer overflows. Buffer overflows is amongst the biggest, most expensive problems in this industry and the primary reason for all the invulnerabilities you're seeing in the wild.
- cognivore 13y agoStack overflows hate the elderly: http://www.forbes.com/2010/03/26/toyota-acceleration-elderly-opinions-contributors-michael-fumento.html http://www.forbes.com/2010/03/26/toyota-acceleration-elderly... (forbes.com)
- aaron695 13y agoYes, I thought the whole issue was myth. Which does lead into, why are we trying to learn about stack overflows and critical system issues about imaginary subjects. And even if it's not myth, as above there's no proof that a stackover flow was the supposed issue.
- erichocean 13y agoIsn't recursion—even if it's indirect—disallowed completely when doing embedded C programming for safety-critical devices? UPDATE: Yup, #70 on the MISRA C rules: http://home.sogang.ac.kr/sites/gsinfotech/study/study021/Lists/b7/Attachments/91/Chap%207.%20MISRA-C%20rules.pdf http://home.sogang.ac.kr/sites/gsinfotech/study/study021/Lis...
- pasbesoin 13y agoI haven't waded into all this, and it's been years -- and years -- since my education touched upon systems that physically separate operating instructions from data memory. But... sooner or later, it seems, we are going to go (back) there. Instructions will become truly privileged, physically-controlled access. Data may go screwy -- or be screwed with -- but this will not directly affect the operating instructions. Inconvenient? As development becomes more mature, instructions will become more debugged and "proven in the field". Stability and safety will outweigh ease and frequency of updates. My 30+ year old microwave chugs along just fine. It doesn't have a turntable nor 1000 W, but I know exactly what it will do, how long to run it for various tasks, and how to rotate the food halfway through to provide even heating. My 34 year old, pilot-light ignited furnace worked like a champ, aside from yet another blower motor going bad. I listened to the service tech when he strongly suggested replacing it before facing a more severe, "winter crisis" problem. The new, micro-processor based model is better in theory (multi-stage speeds, and longer run times for more even heating). In practice, it's been a misery. The first, from-the-factory blower motor was defective. When that was replaced, the unit started making loud air-flow noises periodically. Seeing the blower assembly removed, its constructed of sheet metal. The old furnace, by contrast, had a substantial metal construction that was not going to hum and vibrate if not positioned absolutely perfectly and with brand new, optimized duct work. Past a point, reliability starts to -- far -- outweigh some other optimizations. This is going to become true in our field, as well.
- Fasebook 13y agotl;dr: make the stack bigger! (then is it really a stack overflow?, oh by the way, this won't work in most systems due to virtualized stacks on top of the physical memory making concepts such as order of memory meaningless... but nevermind that) The obvious solution to stack overflows is to make the stack bigger. The obvious problem with this solution is that it just kicks the can down the road.
- Gracana 13y agoAre there any downsides to having the memory set up the "safe" way that they describe? It seems like a win-win situation. [edit] I guess I was thrown off by the shoot-yourself-in-the-foot scenario, where the stack grows toward fixed data structures. If the heap and stack grow towards each other, you have quite a bit of flexibility (though with some danger of collision). If you have the stack grow towards fixed data structures, its size is fixed and it can cause a dangerous overflow. The only disadvantage of the safe example is less flexibility, but for a critical embedded system, that is fine.
- ragecore 13y agoI think cars should just come with slots where we could put in our phones and bam!, powerful computing that you could carry along.
- greatsuccess 13y agoBefore you wonder about stack overflows, as yourself why the occupants never applied the brakes.