A Set-Covering Approach to Customized Coverage InstrumentationA Set-Covering Approach to Customized Coverage InstrumentationThis research was conducted by Carla Michini, Peter Ohmann, Jeff Linderoth, and Ben Liblit. The paper appeared as a featured article in the January–February 2024 issue of the INFORMS Journal on Computing (IJOC).
Program coverage customization selectively adds instrumentation to a compiled computer program so that a limited amount of directly observed data can be used to infer other program coverage information after a run. A good instrumentation plan can reduce run-time overheads while still giving software developers the information they need. Unfortunately, optimal coverage planning is NP-hard, limiting either the quality of heuristic plans or the sizes of programs that can be instrumented optimally. We exploit the monotonicity property of feasible instrumentations to formulate this problem as an intraprocedural set covering problem. Our formulation has an exponential number of constraints, and we design a polynomial-time separation algorithm to incrementally add the necessary subset of these inequalities. Our approach reduces expected run-time probing costs compared with existing methods, offers a guarantee of the optimality of the instrumentation, and has compilation-time overhead suitable for wide practical use.
The full paper is available as a single PDF document. A suggested BibTeX citation record is also available.