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:
Select some sort of potentially interesting program behavior by matching certain patterns against the program source code.
Sweep across the source code, finding all instances of that pattern. Each of these becomes one instrumentation site.
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.
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.
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.
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
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 (if&&,
||, ?:) but not the multi-way branches
of
statements. Each conditional
induces two predicate counters.switch
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.
The values assigned to scalar variables are interesting.
Whenever we see an assignment to a simple named variable
(
) 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 = …x is less than, equal to, or greater than the other
variable. Throw
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.0
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.