Verifying embedded software functionality: fault localization, metrics and directed testing

Abhik Roychoudhury

August 26, 2012

Abhik Roychoudhury

So, we are stuck between the frying pan and the fire!

We cannot employ brute force methods such as exhaustive testing of all inputs, because these methods do not scale up for real-world programs. We also cannot hope to cover all program paths by lightweight methods such as random testing; successive experimental studies have shown that random testing leads to poor coverage of program paths.

Nor can we expect to cover all paths (or even a large fraction of them) simply by covering some other code artifact such as statement coverage. How do we proceed?

One answer to this problem seems to be systematic path exploration via directed testing. In this approach, we start testing our program P with a random input i. Suppose executing the program with input i goes along program path π . During the execution of program P with input i, we collect the condition under which path π is executed. This is the path condition of π and captures the set of inputs (one of which is, of course, i) whose executions go along path π. We then slightly modify the path condition π to produce another path conditionπ’, which is solved to produce another test input.

This process goes on, every time modifying the current path condition, thereby getting a new path and then finding a test input that exercises this new path. This is essentially a method of systematic exploration of program paths by finding suitable inputs to exercise the paths. The hope is that, by exploring more program paths, we have a better chance of encountering errors in the program.

We now illustrate this method with an example. Consider the program fragment in Figure 5.9, reproduced here as Figure 5.13 for convenience. The inputs to this program fragment are Climb (boolean variable) and Up (integer variable). Suppose we start with a random input Climb == 0 and Up == 457. This produces the following path:

1. if (Climb)

3. else

4. separation = Up + 100;
5. if (separation > 150)

6. upward = 1;

9. if (upward > 0)

10. ...
11. printf("Upward");

The path condition (i.e., the conditions on the input on which the foregoing path is executed) is

Climb == 0^Up=100 > 150^upward > 0

The preceding is a conjunction of three primitive constraints. To systematically explore other paths, we can negate the last primitive constraint to get

Climb == 0^Up =100 > 150^ upward ≥ 0

This path turns out to be infeasible—no program input exercising this path. So, we negate the next primitive constraint and get

Climb = = 0^Up +100 ≥150

Solving this constraint we can get a sample input Climb = = 0, Up = = 0, allowing us to explore a new path given as follows.

1. if (Climb)

3. else
4. separation = Up + 100;
5. if (separation > 150)

7. else
8. upward = 1;
9. if (upward > 0)

12. else
13. ...
14. printf("Downward");

Continuing further in this fashion, we can explore the different paths in the program and get concrete inputs that exercise these program paths. This method is called directed testing, because we modify the path constraint of the current path being explored to explore a new path.

Thus, the method is directed toward exploring more paths in the program. It will achieve significantly more coverage than random testing, where several randomly generated inputs may exercise the same program path.

One can employ such a directed testing approach for exposing more program behaviors in a systematic way, thereby hoping to encounter corner cases leading to exceptions/crashes during the testing phase.

Before concluding our discussion on directed testing, we should mention that several subtle issues in a directed testing algorithm have not been discussed here. In our example, the first path we obtained in the preceding had a path constraint

Climb == 0^Up -100 > 150^upward > 0

Here Climb and Up are input variables. However, upward is a program variable whose value is related to the value of the input variable Up. In fact, the (boolean) value of upward is directly correlated to the condition Up + 100 > 150. Directed testing methods/tools will usually try to detect such correlations. As a result, they can avoid exploring infeasible paths, such as the path with constraint

Climb == 0^Up >100 > 150^upward ≥ 0

in our example. Other issues in directed testing methods include search strategies for exploring paths. The method we outlined here via an example essentially employs depth-first search to explore paths.

New paths are obtained from the current path being explored by backtracking (where we negate the condition corresponding to the last branch encountered). Other search strategies such as breadth-first or best-first have also been explored in various tools.

To read Part 1, go to “Why functional testing is needed?”
To read Part 2, go to “Dynamic slicing”
Next in Part 4: Formal verification and testing

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

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.