Global Sources
EE Times-Asia
Stay in touch with EE Times Asia
EE Times-Asia > Embedded

Finding defects in safety-critical code

Posted: 31 Mar 2009 ?? ?Print Version ?Bookmark and Share

Keywords:code safety critical? static analysis? testing rigorous?

Benefits of advanced static analysis
Testing has traditionally been the most effective way to find defects in code. The best test cases feed in as many combinations of inputs and conditions as possible such that all parts of the code are exercised thoroughly. Statement coverage tools can help you develop a test suite that makes sure that every line of code is executed at least once.

But as all programmers know, just because a statement executes correctly once does not mean it will always do soit may trigger an error only under a very unusual set of circumstances. There are tools that will measure condition coverage and even path coverage, and these are all helpful for exercising these corner cases, but achieving full coverage for non-trivial programs is extraordinarily time-consuming and expensive.

This is where advanced static analysis shines. The tools examine paths and consider conditions and program states in the abstract. By doing so, they can achieve much higher coverage of your code than is usually feasible with testing. Best of all, they do all this without requiring you to write any test cases.

This is the most significant way in which static analysis reduces the cost of testing. The cheapest bug is the one you find earliest. Because static analysis is a compile-time process, it can find bugs before you even finish writing the program. This is usually less expensive than if you have to find them by writing a test case or debugging a crash. This article also describes how these tools work, and then shows how they can also reduce the cost of creating test cases.

How advanced static analysis works
All static analysis tools operate in roughly the same way. First, they create a model of the subject program by parsing its source code. The model includes a set of intermediate representations (IRs) of the program, some of which are very similar to what a compiler might create. Once the IR is ready, an analysis phase is started. A diagram showing the architecture is in Figure 1.

Figure 1: Shown is the architecture of a static analysis tool. (Click to view full image)

The intermediate representations include the program's symbol tables, its abstract syntax tree, its control-flow graph and its call graph.

The analysis phase is of course the most interesting, as that is where defects are detected. Different kinds of defects can be detected by looking at different aspects of the IR. For example, a rule that prohibits calls to the famously insecure gets() function can be checked by inspecting the symbol table. A rule that disallows the use of goto statements is easily checked by searching the abstract syntax tree.

The more sophisticated tools operate by performing an abstract execution of the program. As this execution progresses, the tools track variable values and how they relate to each other. If anomalies are detected, warnings are issued. This can be thought of as a "pretend" or abstract execution of your program. Instead of variables containing actual concrete values, they contain abstract symbols. Input values are given symbolic names, too. The analysis then pretends to execute the program using these symbols by following paths through the code and using these symbols instead of concrete values. As this execution proceeds, the analysis may learn facts about the variables and how they relate to each other. For example, because of the conditions on the path leading to a statement, the analysis may determine that if variable x is greater than ten, pointer p may be NULL. As this execution continues, the analysis looks for anomalies. For example, if p is dereferenced at that statement, the analysis will report that a null pointer dereference may occur. A good tool will explain the reasoning it used to arrive at that conclusion, which is useful for helping you determine whether the report is a true or false positive.

This is the essential difference between testing and static analysis: testing uses real inputs and concrete values, whereas static analysis uses symbolic inputs and abstract values. The appeal of the latter is that, because each abstract value represents a wide range of possible concrete values, static analysis can take into account many possible program states simultaneously and so achieve much greater coverage than testing.

Static analysis identifies places where violations of the fundamental rules of the language or libraries might lead to an error. The following illustrate some of the most important classes. The first class is the most serious: bugs that either cause the program to terminate abnormally or result in highly unpredictable behavior. These include buffer overrun and underrun, null pointer dereference, division by zero and use of uninitialized variables. Memory allocation errors result from the misuse of allocators such as malloc() or new. These can be very tricky to debug because the consequent symptom may only show up long after the event that caused the error. Example errors include double free, use after free and memory leak. Concurrency bugs may be caused by misuse of the threads library. Double locks or unlocks, race conditions and futile attempts to lock are among the kinds of concurrency checks that are available.

?First Page?Previous Page 1???2???3???4?Next Page?Last Page

Article Comments - Finding defects in safety-critical c...
*? You can enter [0] more charecters.
*Verify code:


Visit Asia Webinars to learn about the latest in technology and get practical design tips.

Back to Top