Subformula Caching for Model Counting and Quantitative Program Analysis Quantitative program analysis is an emerging area with applications to software reliability, quantitative information flow, sidechannel detection and attack synthesis. Most quantitative program analysis techniques rely on model counting constraint solvers, which are typically the bottleneck for scalability. Although the effectiveness of formula caching in expediting expensive modelcounting queries has been demonstrated in prior work, our key insight is that many subformulas are shared across nonidentical constraints generated during program analyses. This has not been utilized by prior formula caching approaches. In this paper we present a subformula caching framework and integrate it into a model counting constraint solver. We experimentally evaluate its effectiveness under three quantitative program analysis scenarios: 1) model counting constraints generated by symbolic execution, 2) reliability analysis using probabilistic symbolic execution, 3) adaptive attack synthesis for sidechannels. Our experimental results demonstrate that our subformula caching approach significantly improves the performance of quantitative program analysis.

Benchmarking Symbolic Execution Using Constraint Problems  Initial Results. Symbolic execution is a powerful technique for bug finding and program testing. It is successful in finding bugs in realworld code. The core reasoning techniques use constraint solving, path exploration, and search, which are also the same techniques used in solving combinatorial problems, e.g., finitedomain constraint satisfaction problems (CSPs). We propose CSP instances as more challenging benchmarks to evaluate the effectiveness of the core techniques in symbolic execution. We transform CSP benchmarks into C programs suitable for testing the reasoning capabilities of symbolic execution tools. From a single CSP P, we transform P depending on transformation choice into different C programs. Preliminary testing with the KLEE, TracerX, and LLBMC tools show substantial runtime differences from transformation and solver choice. Our C benchmarks are effective in showing the limitations of existing symbolic execution tools. The motivation for this work is we believe that benchmarks of this form can spur the development and engineering of improved core reasoning in symbolic execution engines.