Skip to content
Topos Uranos
English

Debugging

Summary

A program that gives a wrong result is not fixed by changing lines at random, but by investigating. This lesson presents debugging as an experimental method: reproduce the failure, formulate a hypothesis about its cause, design an experiment that confirms or rules it out, and narrow down the location of the defect; bisection finds it in a number of steps that grows like the logarithm of the size of the program. It develops the instrument (compiling with -g and without optimization, the configuration of Visual Studio Code on the three systems and a real GDB session that shows what the editor does underneath), simple and conditional breakpoints, the steps, the call stack and the inspection of the state, with a central example: the median that fails only with an even number of values. It closes with the strategies that are worth more than the tool (reducing the case, looking for the last correct point, checking invariants with assert, reading the sanitizer report) and with three cases: an off-by-one error, a recursion that does not terminate and an invalidated reference.

Learning objectives

  1. Configure compilation with debugging information (-g, without optimization) and launch the debugger from Visual Studio Code on one's own system.
  2. Use simple and conditional breakpoints, step-by-step execution (step into, step over, step out) and the inspection of variables, of expressions and of the call stack.
  3. Apply a systematic strategy (reproduce, reduce, bisect, formulate and test hypotheses) to locate a given defect, documenting each hypothesis.
  4. Combine the debugger with the sanitizers and with tests to locate a memory error from its report.

Debugging is investigating

The defect and the failure

The failure is what is observed: a wrong result, a program that does not terminate, a sanitizer report. The defect (or bug) is the cause: a line, a condition or a design decision that does not match the specification. The failure is visible; the defect has to be found, and it may be far from it. It follows that fixing where the failure is visible, for example by subtracting 2 from the result because “it always comes out 2 too high”, fixes the symptom and leaves the cause, which will come back with other data.

If this is so, debugging is an investigation into the cause, and its method is that of the experimental sciences:

  1. Observe and reproduce. Describe the failure precisely (with what input, what was expected, what was obtained) and make it happen whenever one wishes. A defect that cannot be reproduced cannot be investigated, nor can one check that it was fixed.
  2. Formulate a hypothesis. A statement about the cause that could turn out to be false: “the sort does not sort”, “the index of the second central value is one too high”.
  3. Design an experiment. Choose a point in the program and predict what state should be seen there if the hypothesis is true and what state if it is false.
  4. Conclude and narrow down. Rule out the hypothesis or confirm it; in both cases, the suspect interval shrinks. This is repeated until the interval is a single line.

Now, the method demands discipline: change only one thing at a time, write down each hypothesis with its result, and do not touch the code as long as one does not know what one is looking for. Changing lines at random until the output looks right can hide the failure without removing the defect.

ExampleThe median with an even number of values

The median of a list of values is the central value of the sorted list if the count is odd, and the average of the two central ones if it is even. The lesson Testing showed that tests discover when a function fails, but not where its defect is. The following function passes the test with five values and not with four.

C++ program
#include <algorithm>#include <cstddef>#include <print>#include <vector>​// Median of a list of values.// Precondition: values is not empty.// Postcondition: returns the central value of the sorted list, or the average of the two central ones.double median(std::vector<double> values){    std::ranges::sort(values);    const std::size_t n{values.size()};    const std::size_t middle{n / 2};    if (n % 2 == 1) {        return values[middle];    }    return (values[middle] + values[middle + 1]) / 2.0;}​int main(){    const std::vector<double> odd{7.0, 1.0, 5.0, 3.0, 9.0};    const std::vector<double> even{7.0, 1.0, 5.0, 3.0};    std::println("Median of {}: {}", odd, median(odd));    std::println("Median of {}: {}", even, median(even));}
Output
Median of [7, 1, 5, 3, 9]: 5Median of [7, 1, 5, 3]: 6

The observation is precise: with {7,1,5,3}\{7, 1, 5, 3\}, sorted as {1,3,5,7}\{1, 3, 5, 7\}, the expected result was (3+5)/2=4(3 + 5)/2 = 4 and the result obtained was 6; with five values, the result is correct. There are at least three hypotheses: (H1) the sort does not sort; (H2) the indices of the two central values are wrong; (H3) the sum or the division is miswritten. Each one predicts something different at line 17, before it is executed: if H1 is true, values is not sorted; if H2 is, values[middle] and values[middle + 1] are not 3 and 5; if H3 is, the two values are 3 and 5 and even so the computation gives 6. That the odd case works makes H1 unlikely, but “unlikely” is not “ruled out”; the experiment, with the debugger, is to stop the program at line 17 and look.

Bisection

When there is no clear hypothesis, there remains a method that does not fail: bisection. One assumes that the state of the program is correct at the beginning and wrong at the end, and that at each intermediate point it can be decided whether it is correct (by comparing it with a value computed by hand, or by checking an invariant). The state is examined in the middle of the suspect interval: if it is correct, the defect is in the second half; if not, in the first. It is the binary search of the lesson Searching and sorting, applied to the lines of a program (or to the iterations of a loop, or to the versions of a file).

The figure follows the bisection of sixteen lines with the defect in line 11; each mark is an experiment on the state after that line: correct (✓) or wrong (✗).

Proof

  1. At the start, all sixteen lines are suspect: the state is known to be correct before line 1 and wrong after line 16.

  2. After line 8, the state is correct: lines 1 to 8 are cleared.

  3. After line 12, the state is already incorrect: the defect is between line 9 and line 12.

  4. After line 10, correct: lines 11 and 12 remain.

  5. After line 11, incorrect: the last correct point and the first incorrect one are neighbors, and the defect is in line 11.

The count is that of binary search: each experiment halves the interval, so kk experiments suffice for 2k2^k lines. For a program of a thousand lines, ten suffice, because 210=10242^{10} = 1024. Hence the advantage of the method: its cost grows like the logarithm of the size, and it does not require understanding the whole program, only knowing how to decide, at one point, whether the state is what it should be. Now, that decision is the hard part: specifications and invariants are the criterion by which each intermediate state is judged.