A step-by-step guide to using static analysis to debug embedded software

David Kalinsky, Kalinsky Associates

July 05, 2014

David Kalinsky, Kalinsky AssociatesJuly 05, 2014

Very often, the bugs and defects identified by static analysis tools are not localized to a single line of code, or even to a single function of code. Many of the more subtle code defects found by static analysis tools are “inter-procedural” in nature. In other words a bug ‘scenario’ may develop in a number of steps, where some of those steps may be in one code function, while some additional steps may be in another code function, and yet further steps – or an ultimate crash or failure – may be in yet another function.

In order to deal with the complexity of some of the defects that are uncovered, static analysis tool GUIs will present each separate defect in its own separate window. Several lines of code may be involved in that defect, and they will be highlighted and explanations given. When there are a number of defects within a few lines of code of each other within a single function, each defect will have its own dedicated window.

And if it is an inter-procedural defect, each function involved in that defect will be shown in its own separate GUI window.

Case study of static analysis. Static analysis involves four main steps:

  • Identifying the source code involved in the application, and constructing its call graph.
  • Examining the functions in the call graph, in bottom-up fashion, searching for properties of functions that may contribute to defects.
  • Constructing the control flow graph of each function.
  • Searching for code defects in the code paths of each function.

What follows is a simple case study of the workings of these four steps. We begin with some defective code, involving a function ‘test’ and its sub- function ‘access_or_deref’:



As shown below, in the first step of the static analysis, the call graph (or ‘functional calling tree’) is built:



In the second step, the functions in the call graph are examined one-by-one going from the leaf nodes to the top of the call graph, searching for properties of each function that might contribute to defects.

For example, if we are worried about null pointer de-references in our code base, at this time we would examine all the functions in our call graph, searching for places in the code where variables are being viewed as pointers and those pointers are being de- referenced. [We’re not yet searching for bugs. At this point, we’re just looking for code functions where memory addresses are being pointed at with the intent of writing there.] In the function ‘access_or_deref’, this search would yield the following results:
  1. Variable ‘buf’ is de-referenced when variable pos != 0.
  2. Variable ‘ptr’ is de-referenced when variable pos == 0. This information about the properties of the function is stored for later use.
Next, in the third step of the static analysis, the control flow graph of each function is built. [Sometimes referred to as a ‘flow chart’.] Here below is the control flow graph of function ‘test’:




The control flow graph of function ‘test’ has only 1 path, from ‘START’ to 'END'.

In the fourth and final step of the static analysis, the search for code defects takes place, going through the paths of each function. We will see this done for function ‘test’ as we search for null pointer de-reference defects in its code. A NULL_POINTER_DEREF defect-searching tool will update a state table (shown below) listing the variables in this code, as it walks down the path of function ‘test’ . The states relevant to this defect-searching tool are ‘Unknown’, ‘NULL’, and ‘Not_NULL’.



At the first line of code in function ‘test’ , variable ‘buf’ first appears. Its state is recorded as ‘Unknown’ since the function ‘malloc’ which provides it with a value, might give it a Not_NULL pointer to an allocated memory buffer, or it might give it a NULL value if it’s run out of memory to allocate. At the second line of code in function ‘test’ , variable ‘ptr’ appears. The code at this line shows that the state of variable ‘ptr’ is ‘NULL’. After those two lines of code, there are no more state changes for those variables in function ‘test’ .

The NULL_POINTER_DEREF defect-searching tool will then continue to the next line of code in function ‘test’ . There it will see that sub-function ‘access_or_deref’ is called for the first time. It will then fetch the properties of the sub-function that were stored in analysis step two. Since the first parameter passed to the sub-function is pos=1 for this call, the stored properties information tells the tool that variable ‘buf’ is de-referenced within the sub-function at this call. But the tool’s state table tells it that variable ‘buf’ is in ‘Unknown’ state – perhaps NULL or perhaps Non-NULL. Because of the lack of certainly about the NULLness of variable ‘buf’, the tool will not report a defect in this instance.

Similarly, at the next line of code in function ‘test’ , sub-function ‘access_or_deref’ is called again, but pos=4 for this call. The NULL_POINTER_DEREF defect-searching tool will again not report a defect here for the same reasons.

At the following (and last) line of code in function ‘test’ , sub-function ‘access_or_deref’ is called once more, but pos=0 this time. Stored properties information from analysis step 2 tells the tool that variable ‘ptr’ is de-referenced within the sub-function for this call. And the tool’s state table tells it that variable ‘ptr’ is definitely in the ‘NULL’ state – with no doubt about it! This time the NULL_POINTER_DEREF defect-searching tool will report a defect loud and clear.

Please note that although the NULL_POINTER_DEREF defect-searching tool identified the bug during its analysis of function ‘test’ , the actual crash will happen during the execution of sub-function ‘access_or_deref’ .

Conclusions
A new generation of static source code analysis tools has very recently become available for the analysis of software code bases for bugs and other defects. These tools work without actually running the programs that are built from the software that’s under analysis. Faults can be found early in the development process, so as to improve software quality as well as save developers time. Such tools can cover the execution paths through a very large code base in a fully automated way, and identify complex defects including bugs involving interactions among multiple procedures.

Acknowledgement: Many of the examples and illustrations in this paper are courtesy of Coverity, Inc.

References
[1] Boehm, B., Software Engineering Economics, 1981, ISBN: 0138221227

[2] DO-178B, "Software Considerations in Airborne Systems and Equipment Certification", RCTA, December 1992.

[3] Engler, D. and Musuvathi, M., Static Analysis vs. Software Model Checking for Bug Finding

[4] Engler, D. and Ashcraft, K., RacerX: Effective, Static Detection of Race Conditions and Deadlocks

< Previous
Page 2 of 2
Next >

Loading comments...

Most Commented