Full Text: Download PDF
Stack overflows can have catastrophic consequences in embedded software controlling safety- or security-critical systems. Static stack analysis tools provide the best choice to ensure reliable execution.
Every high-integrity system and, in general, any system that requires reliability must provide evidence demonstrating the impossibility of stack overflow. Static verification is mandatory for high-integrity systems because it is the only way to ensure that worst-case scenarios are found. Safety-critical standards such as DO-178B require worst-case memory utilization to be known, and stack memory is no exception.
Approaches to analysis
The major weakness of dynamic testing-based approaches is they cannot guarantee that the worst-case execution path has been covered during the testing campaign, which is why this method is not valid for high-integrity systems.
When fully applied, static stack analysis techniques provide worst-case results that can be safely used for dimension stacks, ensuring reliable stack memory usage and thus guaranteeing safe execution. Unaffected by the limitations of dynamic testing, this technique rapidly provides precise results without much effort early in the development process.
It is worth noting that static stack analysis or any verification technique is no substitute for clean and precise programming. While static analysis is certainly useful, it will not magically turn carelessly written code into good code. Stack analysis needs to know the stack requirements for each subprogram as well as all feasible control flow during execution. Hence, several constructs typically excluded for high-integrity systems threaten this analysis, including:
- Cycles in the control flow graph:In the presence of control flow cycles involving stack consumption, the worst-case boundary is a function of the maximum number of cycle iterations.
- Indirect or dispatching subprogram calls:Statically determining the target subprogram when dereferencing an access to the subprogram requires data flow analysis, which is not always possible. In Ada, these occurrences can be forbidden using the restriction No_Access_Subprograms. Dispatching calls in object-oriented programming are another instance of indirect calls. In Ada, dispatching calls can be eliminated using the restriction No_Dispatch, which prohibits class-wide constructs. However, runtime dispatching calls are problematic when runtime dispatching is inherent to the language, as in Java.
- Dynamic stack allocations:The presence of dynamically sized local objects, such as those whose size depends on an input argument, introduces variable, nonstatically bound amounts of stack usage on the paths where they appear.
One approach to static stack analysis is parsing the object or assembly code to extract the code that performs stack allocations and calls to subprograms. This technique can provide accurate information; however, it requires a comprehensive and complex machine code parser and is very sensitive to compiler changes and optimization options.
Leveraging the compiler
A more advantageous approach is leveraging the compiler itself, which is well positioned to know everything about stack allocations and subprogram calls for the code it processes. Three steps are needed to analyze stack usage:
1.Generating the basic stack consumption and call graph information
2.Computing the complete call tree using control flow analysis, decorated with local stack requirements
3.Analyzing worst-case stacks for any entry point in the application (see Figure 1)
The compiler knows the generated code and where it comes from, which is valuable when developers want to point directly to some user-level construct that jeopardizes static analysis. It is also important to note that a compiler has visibility in semantic information that can help tackle some of the previously identified challenging constructs.
Consider an Ada Integer subtype with range 1..5, for example. If a variable of this subtype is used to size a local array, the range may be used to compute a bound on the array size and corresponding stack allocation. Furthermore, using subprogram profiles and actual references to subprograms, the compiler can provide a limited yet in-depth list of subprograms possibly reached by an indirect call.
Detecting problematic constructs
AdaCoreís GNATstack is a static stack analysis tool that uses a specialized extension to the GNU compiler collection back end to produce the required call graph and stack usage information. It constructs the full call graph annotated with local stack requirements and then performs a depth-first traversal of the tree to extract the worst-case analysis in terms of stack usage (see Figure 2).
This static stack analysis tool also can detect and report the problematic constructs mentioned previously (cycles, indirect calls, dynamic frames, and missing stack information), providing an infrastructure that allows users to specify the required information, such as potential targets for indirect calls, stack requirements for externals calls, and user-defined bounds for unbounded frames. Avoiding these program constructs is often part of already established coding guidelines in environments where preventing stack overflows is a real concern. GNATstack ensures that these harmful situations do not go unnoticed.
Relying on the compiler back end to obtain stack information works smoothly at any optimization level for any target machine and allows mixing different programming languages (Ada, C, C++, and so on).
Stack overflow prevention
During the development phase, static stack analysis provides early feedback that helps tackle undesired constructs and hot spots with respect to stack usage. In the validation phase, any possible execution path is analyzed, thus guaranteeing that the computed worst-case stack can never overflow. This characteristic makes static analysis the only viable approach for high-integrity systems and for any system that requires reliability. The generated information can be used as evidence for certifying high-integrity and high-reliability applications.
JosÈ F. Ruiz is a senior software engineer at AdaCore, based at the companyís European headquarters in Paris, where he specializes in real-time, embedded, and certifiable systems in Ada. He has 15-plus years of software development experience and has authored/coauthored more than 20 technical papers. JosÈ holds a PhD from the Technical University of Madrid for his work in the field of real-time and multimedia systems.
AdaCore
+33 1 49 70 67 16
ruiz@adacore.com
www.adacore.com
