Optimizing Customized Program CoverageOptimizing Customized Program CoverageThis research was conducted by Peter Ohmann, David Bingham Brown, Naveen Neelakandan, Jeff Linderoth, and Ben Liblit. The paper will apear in the 31st IEEE / ACM International Conference on Automated Software Engineering (ASE 2016).
Program coverage is used across many stages of software development. While common during testing, program coverage has also found use outside the test lab, in production software. However, production software has stricter requirements on run-time overheads, and may limit possible program instrumentation. Thus, optimizing the placement of probes to gather program coverage is important.
We introduce and study the problem of customized program coverage optimization. We generalize previous work that optimizes for complete coverage instrumentation with a system that adapts optimization to customizable program coverage requirements. Specifically, our system allows a user to specify desired coverage locations and to limit legal instrumentation locations. We prove that the problem of determining optimal coverage probes is NP-hard, and we present a solution based on mixed integer linear programming. Due to the computational complexity of the problem, we also provide two practical approximation approaches. We evaluate the effectiveness of our approximations across a diverse set of benchmarks, and show that our techniques can substantially reduce instrumentation while allowing the user immense freedom in defining coverage requirements. When naïve instrumentation is dense or expensive, our optimizations succeed in lowering execution time overheads.
The full paper is available as a single PDF document. A suggested BibTeX citation record is also available.
Code implementing ideas from this paper is available as open source for others to use and/or build upon. Feedback, bug reports, and enhancements are welcome!