A Set-Covering Approach to Customized Coverage Instrumentation
提出将程序覆盖定制问题转化为集合覆盖问题，利用单调性设计多项式时间分离算法，在降低运行时开销的同时保证最优性，适用于实际编译场景。
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. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the National Science Foundation [Grants CCF-1318489, CCF-1420866, and CCF-1423237] and the Air Force Research Laboratory [Grant FA8750-14-2-0270]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0349 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0349 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .