Batch Alias Analysis Many programanalysis based tools require precise pointstoalias information only for some program variables. To meet this requirement efficiently, there have been many works on demanddriven analyses that perform only the work necessary to compute the pointsto or alias information on the requested variables (queries). However, these demanddriven analyses can be very expensive when applied on large systems where the number of queries can be significant. Such a blowup in analysis time is unacceptable in cases where scalability with realtime constraints is crucial; for example, when program analysis tools are plugged into an IDE (Integrated Development Environment). In this paper, we propose schemes to improve the scalability of demanddriven analyses without compromising on precision. Our work is based on novel ideas for eliminating irrelevant and redundant dataflow paths for the given queries. We introduce the idea of batch analysis, which can answer multiple given queries in batch mode. Batch analysis suits the environments with strict time constraints, where the queries come in batch. We present a batch alias analysis framework that can be used to speed up given demanddriven alias analysis. To show the effectiveness of this framework, we use two demanddriven alias analyses (1) the existing best performing demanddriven alias analysis tool for racedetection clients and (2) an optimized version thereof that avoids irrelevant computation. Our evaluations on a simulated datarace client, and on a recent programunderstanding tool, show that batch analysis leads to significant performance gains, along with minor gains in precision.

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.