Verifying embedded software functionality: Why it’s necessary

Abhik Roychoudhury

August 5, 2012

Abhik Roychoudhury

As another example, consider the following program fragment, written in C style:

1.   a = 1;
2.   b = a;
3.   c = b;
4.   if (c){
          v = 10;}
5.   else { v = 20;}
6.   println("%d", v);

Suppose the bug is in line 1, where variable a is set to a wrong value. Let us see how this bug will be manifested. The wrong value of variable a will be propagated to variable b—thereby “infecting” variable b. This wrong value will then be passed from variable b to variable c. Based on the wrong value passed to variable c, a branch or a decision will be made in line 4 and, in this case, the decision for the branch evaluation is wrong as a result.

Because of the wrong branch evaluation, the variable v is set wrong, and this wrong value is printed in line 6—the manifestation of the “bug” in line 1! So, as we can see, the bug in a program is usually quite different from its manifestation during program execution.

Now, what should a debugging method do? Of course, while testing the software, that is, running it against selected test cases, the programmer can see only the manifestation of the bug and not the bug itself! The task of a debugging method is to start from the manifestation the bug, and trace back to the bug itself.

So, in the preceding C program fragment, the observable error will be an unexpected value of variable v being printed. From here, the debugging method has to reason that (i) variable v was set in lines 4 or 5, (ii) the setting of variable v depends on a branch that is evaluated based on the value of c, (iii) the value of c depends on the value of b, and (iv) the value of b depends on the value of a.

Thus, the reasoning here uncovers a chain of dependencies starting from the observable error (line 6), in order to locate the error cause (in line 1). We now discuss the dynamic slicing method, which traverses an execution trace to uncover the program dependency chains of an observable error. The lines of program captured in these program dependency chains are highlighted in a bug report, which is also called the “slice.” The programmer can then inspect the bug report to locate the probable error causes.

Manual versus Automated
To understand the power of the dynamic slicing methodology, it is important to compare it to conventional software debugging tools (Figure 5-2 below) such as the gdb for C, jdb for Java, or VBwatch for Visual Basic.

All of these tools essentially track the program execution for a given input. The programmer can set “breakpoints,” guiding the tool to freeze the program execution at specific control locations, and then observe values of specific variables at these locations. However, note that the entire debugging process is still manual.

Figure 5-2. Software engineering without a model: possible validation mechanisms
The programmer has to instruct the debugging tool about where to stop (i.e., where to set the breakpoint), and then manually observe selected variables at these breakpoints. The tool is only keeping track of the program execution, but not analyzing the program execution in any way!

Thus, existing debugging tools do not employ any analysis of the execution trace—they only record or profile the execution trace and display the trace information. The real issue at hand is not the visualization of the trace information—many of the existing debuggers have detailed graphical user interfaces (GUIs) for this purpose.

Click on image to enlarge.

Figure 5-3. Snapshot of a conventional debugger (gdb for C)
Figure 5-3 above shows a snapshot of a conventional debugger -actually the well-known gdb debugger for C. It collects and lets the user visualize relevant information about the program execution—the figure shows the user inquiring about the value of a program variable h at a specific control location of the program.

What is missing is an analysis of the execution trace to explain a possibly unexpected value of the variable h—this has to be done manually by the user. As we shall see in Part 2, the dynamic slicing method provides such an analysis.

Next in Part 2: The importance of dynamic code slicing.

Abhik Roychoudhury is associate professor at the National Univdrsity of Singapore. He received his Ph.D. in computer science from the State University of New York at Stony Brook. His research interests are system modeling and validation with a specific focus on embedded software and systems.

Used with permission from Morgan Kaufmann, a division of Elsevier. Copyright 2009, from "Embedded Systems and Software Validation," by Abhik Roychoudbury. For more information about this title and other similar books, visit www.elsevierdirect.com