Sophisticated Program Analysis, Declaratively

Static program analysis is a fundamental computing challenge. We have recently demonstrated significant advantages from expressing analyses for Java declaratively, in the Datalog language. This means that the algorithm is in a form that resembles a pure logical specification, rather than a step-by-step definition of the execution. The declarative specification does not merely cover the main logic of the algorithm, but its entire implementation, including the handling of complex semantic features (such as native methods, reflection, threads) of the Java language. Surprisingly, the declarative specification can be made to execute up to an order of magnitude faster than the dominant pre-existing implementations of the same algorithms. Armed with this past experience, the SPADE project aims to develop a next-generation approach to the design and declarative implementation of static program analyses. This will include a) a substantially more flexible notion of context-sensitive analysis, which allows context to vary according to introspective observations; b) a flow-sensitive analysis framework that can be used as the basis for dataflow analysis; c) an approach to producing parallel implementations of analyses by exploiting the parallelism inherent in the declarative specification; d) an exploration of adapting analysis logic to multiple languages and paradigms, including C (using the LLVM infrastructure), functional languages (e.g., Scheme), and dynamic languages (notably, Javascript); e) client analyses algorithms (e.g., may-happen-in-parallel, bug finding analyses such as race and atomicity-violation detectors, etc.) expressed modularly over the underlying substrate of points-to analysis. The work will have applications to multiple languages and a variety of analyses. Concretely, our precise and scalable analysis algorithms will enhance optimizing compilers, program analyzers for error detection, and program understanding tools.