Advanced Program Analysis Using Declarative Languages

Analyzing programs automatically is an activity in the heart of Computer Science research. Program analysis is fundamentally very hard, as most involved analyses are either undecidable (i.e., mathematically impossible) or intractable (i.e., requiring an astronomically long time to complete). As a result, analyses have high complexity due to their need to achieve efficiency. We propose to implement advanced program analysis algorithms using purely declarative specifications. Such declarative specifications are much easier and more succinct than typical implementations of program analyses, since they concentrate on what the analysis needs to compute and not on how it does so. In our past work we have shown that declarative specifications of points-to analyses not only are easy to define, but also admit aggressive optimization. As a result of our optimization methodology, our work has demonstrated very large (often more than 10x) performance improvements compared to traditional imperative or semi-declarative implementations of points-to analyses. In the proposed work, we plan to employ similar declarative specifications for higher-level analyses than mere points-to analysis and to languages with different features and characteristics. Specifically, we intend to declaratively specify program analyses that are necessary for security (e.g., information leakage analyses), for error detection (e.g., race or deadlock detection in multi-threaded programs), and for optimization (e.g., cast check removal). We also plan to explore languages such as JavaScript (which has strong functional features) in addition to more standard languages like Java. With this work the applicant will transfer his expertise in program analysis to the host institution. Additionally, the proposed work will reintegrate in Europe an applicant with substantial academic experience at multiple US institutions, directly enhancing European scientific excellence.