Efficient tracing of cold code via bias-free sampling
Baris Kasikci, Thomas J. Ball, George Candea, John Erickson, Madanlal Musuvathi · 2014
Bugs often lurk in code that is infrequently executed (i.e., cold code), so testing and debugging requires tracing such code. Alas, the location of cold code is generally not known a priori and, by definition, cold code is elu-sive during execution. Thus, programs either incur un-necessary runtime overhead to “catch ” cold code, or they must employ sampling, in which case many executions are required to sample the cold code even once. We introduce a technique called bias-free sampling (BfS), in which the machine instructions of a dynamic execution are sampled independently of their execution frequency by using breakpoints. The BfS overhead is therefore independent of a program’s runtime behavior and is fully predictable: it is merely a function of pro-gram size. BfS operates directly on binaries. We present the theory and implementation of BfS for both managed and unmanaged code, as well as both ker-nel and user mode. We ran BfS on a total of 679 pro-grams (all Windows system binaries, Z3, SPECint suite, and on several C # benchmarks), and BfS incurred per-formance overheads of just 1–6%. 1