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

Perform systematic program debugging (Part 2)

Posted: 29 Jul 2013     Print Version  Bookmark and Share

Keywords:debugging  infection  programmer  recompiling  debuggers 

To find out how shell_sort() was actually invoked, we need a means of observing the state during execution. Here we will use the simplest of all observation techniques: We insert output statements in the code that log specific variables and their values when executed.

For instance, we could insert the following code in line 10 to have the values of the parameters a[ ] and size logged on the standard error channel whenever shell_sort() is invoked.

fprintf(stderr, "At shell_sort");
for (i = 0; i < size; i++)
  fprintf(stderr, "a[%d] = %d\n", i, a[i]);
fprintf(stderr, "size = %d\n", size);

Focus on the most likely origins: After inserting the code and restarting sample with the arguments 11 and 14, you will find that at shell_sort() the values of the parameters are as follows.

a[0] = 11
a[1] = 14
a[2] = 0
size = 3

We see that shell_sort() is invoked with three elements—that is, the array a[ ] to be sorted is [11, 14, 0]. This state is infected—that is, a[ ] should contain only two elements. As discussed previously, an infected state is likely to cause failures, and this particular state may well be the cause of our failure.

Our hypothesis is that shell_sort() properly sorts the three elements of a[ ] in place to [0, 11, 14]. Later on, though, only the first two elements of a[ ] will be printed, resulting in the failure output.

Isolate the origin of the infection: According to our earlier reasoning, the infection must have occurred before the invocation of shell_sort(). Obviously, the parameter size is wrong. We can trace back its origin to the point at which shell_sort() is invoked: In line 36,we find the invocation shell_sort(a, argc); and find that the size parameter gets its value from the argc variable. However, argc is not the number of elements in a[ ].

It is the number of arguments to the sample program, including the name sample itself (argc is always one more than the number of elements in a). Thus, the following is our speculation about what is happening in our program:
1. The array a[ ] is allocated and initialized with the correct number of elements (2).
2. shell_sort() is invoked such that the size parameter is 3 instead of 2 (the state is infected).
3. size being 3 causes shell_sort() to access a[ ] beyond the allocated space (namely, at a[2]).
4. The uninitialized memory at a[2] happens to be 0.
5. During the sort, a[2] is eventually swapped with a[0], thus setting a[0] to zero (the infection has spread to a[0]).
6. Thus, the zero value of a[0] is printed, causing the failure.

You may wonder why sample actually worked when being invoked with the arguments 9 7 8. The defect was the same, and it caused the same infection. However, as a[3] in this case turned out to be larger than 9 it did not get swapped with another array element. At the return of shell_sort() the infection was gone, and thus the defect never showed up as a failure.

Correct the defect: So far, we are still speculating about the failure cause. To deliver the final proof, we have to correct the defect. If the failure no longer occurs, we know that the defect caused the failure. In addition to prohibiting the failure in question we want to prohibit as many failures as possible. In our case, we achieve this by replacing line 36, shell_sort(a, argc); with the correct invocation shell_sort(a, argc—1);

Repeating the test with the fixed program, as follows, shows that the original failure no longer occurs.

$ ./sample 11 14
Output: 11 14
$ _

This resolves the sample problem.

Automated debugging techniques
Essentially, we have solved the sample problem manually—that is, without using any specific tools. In principle, all debugging problems can be solved manually—by deduction from the source code and observation of what is going on in a program. (Purists might even argue that deduction alone suffices to prove a program correct, removing the need to fix defects.)

In practice, though, it is unwise to rely on manual debugging alone, as the computer can relieve you of most boring and tedious tasks. In particular, the sample program discussed earlier can be debugged almost automatically. Figure 3 depicts the automated debugging techniques available.

Figure 3: Some automated debugging techniques: (a) program slice, (b) observing state, (c) watching state, (d) asserting an invariant, (e) anomalies, and (f) cause–effect chain.

Simplified input with delta debugging: This is a technique that automatically narrows down the difference between a passing and a failing run. Applied to program input, delta debugging returns a simplified input wherein each part contributes to the failure. Applied to the failing sample run, delta debugging determines that each of the arguments 11 and 14 is relevant. The failure no longer occurs if sample is being called with one argument only.

 First Page Previous Page 1 • 2 • 3 Next Page Last Page

Comment on "Perform systematic program debugging..."
*  You can enter [0] more charecters.
*Verify code:


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


Go to top             Connect on Facebook      Follow us on Twitter      Follow us on Orkut

Back to Top