Details About Instrumentation Schemes

Schemes In General

The application packager has several instrumentation strategies to choose from. They vary in terms of how extensively they monitor program behavior as well as what kinds of bugs they will tend to detect. However, all instrumentation schemes have the same general form:

  1. Select some sort of potentially interesting program behavior by matching certain patterns against the program source code.

  2. Sweep across the source code, finding all instances of that pattern. Each of these becomes one instrumentation site.

  3. Partition the possible behaviors at each site to a collection of mutually exclusive tests, or predicates, that completely summarize possibly interesting observations at that site.

  4. Inject instrumentation code to count how often each predicate is observed while the program runs. Thus, each predicate at each instrumentation site gets one predicate summary counter.

  5. When the program exits, either successfully or by crashing, upload a feedback report to our report collection server here at Bug Isolation Headquarters.

Another property that all schemes share is that they are fairly simpleminded about what constitutes interesting behavior. Most of what any scheme records is just standard, dull, correct execution. Read more about statistical debugging to see how we find the few bug-inducing anomalies among all this data.

Currently Deployed Schemes

What defines an instrumentation scheme, then, is the patterns we look for and the counted predicates we use to summarize program behavior. Each application we currently have posted uses one of the following schemes:


Each if statement is interesting. At each conditional, count how many times the condition is true versus false. (Or if you prefer, how many times we branch left versus right.) This includes implicit branches in things like loops and certain C operators (&&, ||, ?:) but not the multi-way branches of switch statements. Each conditional induces two predicate counters.

function returns

The values returned by function and system calls are interesting. At each function call site, count how many times that call returns a negative number, zero, or a positive number. Each scalar-returning function call site induces three predicate counters.

scalar pairs

The values assigned to scalar variables are interesting. Whenever we see an assignment to a simple named variable (x = ) of pointer or integer type, grab the new value. Compare that new value to each and every other variable of the same type that is also in scope at that assignment. Count how often the new value of x is less than, equal to, or greater than the other variable. Throw 0 into the mix as well, so we’re also counting how often negative, zero, and positive values appear. Each assignment induces three predicate counters per other same-typed variable that’s also in scope.

Ongoing Development

While the above schemes capture many interesting program behaviors (and misbehaviors), they are certainly not exhaustive. We are considering or implementing many additional schemes to monitor things like assertion failures, average data values, extremal data values, values relative to source literals, code coverage, pointer zone (heap/stack) trends, and more. Learning which schemes work well in what contexts is one of the key questions we seek to answer in this ongoing research project.