Computing That Serves

Say No to Stack Overflow


Thursday, March 4, 2004 - 10:00am


John Regehr, University of Utah

Most of the CPUs sold in recent years are small embedded processors; they are largely invisible but perform useful and important functions inside automobiles, electronic devices, and factories.  Since these processors are hard to reach, every effort should be taken to ensure software correctness before deployment.  This talk will address the problem of preventing stack overflow: an embedded system bug where the execution stack overwrites and corrupts memory being used for other purposes. Stack overflow is particularly difficult to catch during testing because the stack depth depends not only on the path taken through the software, but also on the timing of the arrivals of external events.

We use abstract interpretation, a form of static analysis, to estimate the behavior of an embedded program, to form a graph of potential preemption relations due to interrupts, and finally compute a bound on overall stack memory usage.  By taking interrupt preemption relations into account we improve stack bounds by about 30%, averaged over a number of embedded programs.  The second contribution of this work is a novel framework for automatically reducing stack memory requirements.  We show that goal-directed global function inlining can be used to reduce the stack memory requirements of component-based embedded software, on average, to 40% of the requirement of a system compiled without inlining, and to 68% of the requirement of a system compiled with aggressive inlining that is not directed towards reducing stack usage.


John Regehr's main research interests are in embedded systems, operating systems, and real-time systems.  He is an assistant professor in the School of Computing at the University of Utah, having received his Ph.D. from the University of Virginia in 2001.  In his spare time he hikes and reads.