Efficient Tracing of Cold Code via Bias-Free Sampling

Baris Kasikci, Thomas Ball, George Candea, John Erickson, Madanlal Musuvathi

TL;DR

This paper introduces "Bias-Free Sampling" (BfS), a novel technique for efficiently tracing infrequently executed ("cold") code in programs. By leveraging hardware breakpoints, BfS samples cold code without over-sampling hot code, significantly reducing overhead and enabling more effective debugging and analysis of rare bugs.

What Problem Does This Paper Address?

Debugging and understanding complex software often requires analyzing "cold code" – parts of a program that are rarely executed. These sections are crucial because bugs frequently hide there, yet they are elusive during normal execution. Traditional methods either incur prohibitive overhead by tracing everything or use sampling techniques that can miss cold code due to low sampling rates, requiring many program runs to catch a rare event. This leaves developers without efficient tools to pinpoint issues in these critical, yet hard-to-reach, code segments.

Methods

The core innovation is Bias-Free Sampling (BfS), which uses hardware breakpoints to achieve its goals. Instead of relying on temporal sampling (taking samples at fixed intervals), BfS dynamically places breakpoints on instructions. The key ideas are:

  • Sampling Cold Code Without Bias: BfS ensures that the first few executions of any instruction are always sampled. This guarantees that even very rare instructions will be captured at least once.
  • Avoiding Over-Sampling Hot Code: While ensuring cold code is sampled, BfS is designed not to over-sample frequently executed ("hot") code. This is achieved by intelligently managing breakpoints and their refresh rates.
  • Leveraging Hardware Breakpoints: The technique directly utilizes CPU hardware breakpoints, which are efficient and can be set/cleared without significant synchronization overhead across threads.
  • Lightweight Code Breakpoints (LCB): The authors developed an implementation called LCB, which handles breakpoints efficiently for both kernel and user-mode code, and for both native and managed (e.g., .NET) applications. This includes sophisticated mechanisms to bypass regular debuggers and handle shared modules.
  • Multi-Shot Breakpoints: For scenarios requiring continuous sampling of an instruction after its initial capture, LCB implements "multi-shot" breakpoints, which allow an instruction to be re-sampled without removing the breakpoint.

Datasets

The paper evaluates BfS and its implementation (LCC for code coverage) on a variety of datasets:

  • Z3: An automated theorem prover, used for detailed case studies.
  • SPEC CPU2006 Integer Benchmarks: A standard suite of integer computation benchmarks.
  • CLR Performance Benchmarks: Three managed code applications (RayTracer, BizTalk, ClientSimulator) used internally at Microsoft.
  • Windows 8 Native Binaries: A large-scale evaluation on a subset of system tests from Windows 8, including kernel-mode drivers.

No new benchmarks were introduced; the focus was on evaluating the existing technique on established workloads.

Key Insights and Ideas

  • Breakpoints are the Key: The paper convincingly argues that hardware breakpoints, often overlooked for large-scale dynamic analysis due to perceived overhead, are actually a highly efficient mechanism when managed correctly.
  • The "Elephant in the Haystack" Problem: The analogy of searching for rare bugs (needles) in a large program (haystack) is central. BfS directly addresses the challenge of finding these needles without being overwhelmed by the haystack.
  • Overhead Independence: A major breakthrough is achieving sampling overhead that is largely independent of program execution frequency, instead being primarily a function of program size. This is a significant departure from traditional sampling.
  • Unified Approach for Native and Managed Code: The ability to apply BfS effectively to both native and managed code, including kernel drivers, demonstrates its broad applicability.
  • Code Coverage as a "Lean" BfS Instance: The paper shows that a simple configuration of BfS (setting breakpoints on every basic block and logging only the first hit) is an efficient way to implement code coverage (LCC), achieving low overhead.

Key Results

  • Low Overhead: The LCC implementation (a form of BfS for code coverage) incurred performance overheads of 1-6% across a wide range of native and managed applications. This is significantly lower than alternative static instrumentation tools like bbcover, which showed overheads up to 176%.
  • Comprehensive Coverage: LCC was applied to 679 programs, including Windows system binaries, and demonstrated robustness. In a large-scale test on Windows 8 binaries, LCC achieved better coverage than bbcover, partly because bbcover's higher overhead caused some tests to time out.
  • Efficient Cold Code Tracing: The paper demonstrates how BfS can be extended for periodic logging of cold code, with overheads ranging from 1.4% to 2.18% for periodic logging every half second on Z3, and significantly lower for less frequent refreshes.

Limitations and Future Work

  • Managed Code JIT Challenges: While addressed, disabling JIT optimizations for managed code to ensure breakpoint accuracy is a workaround. The authors mention future work on recovering correspondence without disabling JIT.
  • Breakpoint Placement on Writable Pages: LCB avoids setting breakpoints on writable code pages to prevent conflicts with self-generated code.
  • Debugger Interaction: While LCB hides its breakpoints from debuggers, the interaction could be further refined.
  • Future Work: The authors suggest exploring more sophisticated sampling distributions based on application needs, and further optimizing the managed code support. The potential for using BfS for other dynamic analysis tasks like bug isolation and performance profiling is also highlighted.

Summary updated

BibTeX
@inproceedings{kasikci2014efficient,
  author = {Baris Kasikci and Thomas Ball and George Candea and John Erickson and Madanlal Musuvathi},
  title = {{Efficient Tracing of Cold Code via Bias-Free Sampling}},
  booktitle = {USENIX ATC},
  year = {2014},
}
Figure