Automated Debugging (2): how failures come to be

1. Facts on Debugging

* Software bugs are costing ~60 bln US$/yr
* Improvements could reduce cost by 30%
* Validation (including debugging) can easily take up to 50-75% of the development time
* When debugging, some people are three times as efficient than others

2. How to Debug

Locate error => Design error repair => Repair error => Re-test program

3. The Traffic Principle

* Track the problem
* Reproduce
* Automate
* Find Origins
* Focus
* Isolate
* Correct

4. From Defect to Failure


1) The programmer creates a defect – an error in the code.
2) When executed, the defect creates an infection – an error in the state.
3) The infection propagates.
4) The infection causes a failure.


This infection chain must be traced back – and broken.

* trace back is for locating the defect
* broken is for eliminating the failure




5. The Curse of Testing

* Not every defect causes a failure!
* Testing can only show the presence of errors – not their absence.(Dijkstra 1972)

Curse means "a prayer or invocation for harm or injury to come upon one "

6. Debugging

* Every failure can be traced back to some infection, and every infection is caused by some defect.
* Debugging means to relate a given failure to the defect – and to remove the defect.


Search in Time and Space

Defect is traced back, and located.



Then the next figure:













7. Sample Program and Shell Sort

Find Origin:
* The 0 printed is the value of a[0]. Where does it come from?
* Basic idea: Track or deduce value origins
* Separates relevant from irrelevant values
* We can trace back a[0] to shell_sort

Search in Time

* In shell_sort, the state must have become infected.
* Basic idea: Observe a transition from sane to infected.

Observing a Run
* Dynamic running, from the timeline point of view

Specific Observation
* isolate the potential crime scene
* narrow the searching space and time

Fixing the Program

Finding Causes
* difference between sane state and infected state

Search in Space
* compare infected state and sane state
* locate / isolate the infected (faulting) variable(s)

Search in Time
* search in the direction of the timeline
* when the error first demonstrate itself?

8. Debugging tools

Automated Debugging Service
Closed now. Other relevant tools are available (eclipse plugin, command line tool).

A variety of other tools and techniques is available to automate debugging:

* Program Slicing
* Observing & Watching State
* Asserting Invariants
* Detecting Anomalies
* Isolating Cause-Effect Chains