PADECL · Advanced Program Analysis Using Declarative Languages
FP7 — People (Marie Curie Actions)
- Duration
- 2010-12-01 → 2014-11-30
- EU contribution
- €100,000
- Participants
- 1
- Scheme
- MC-IRG
Lines connect the coordinator with its partners.
Results in brief
Advanced Program Analysis Using Declarative Languages
The project consists of expressing high-level program analysis algorithms (escape analysis, information flow, exception flow, cast safety) entirely in a declarative form, using the Datalog programming language. The declarative approach is a key element of the work. The New Oxford Dictionary of English defines “declarative” in the Computing context as “denoting high-level programming languages which can be used to solve problems without requiring the programmer to specify an exact procedure to be followed”. In other words, a program or language is declarative when it specifies what needs to be computed but not how. Our analysis implementations achieve higher degrees of precision, completeness, and performance than past work. The work consists of specific client analyses (escape analysis, exception analysis, optimization analyses) implemented as part of the Doop framework, as well as refinements of the main functionality of the Java program analysis framework. The end result of the proposed work is an efficient, precise, rich, and modular program analysis framework. This can be a substantial step towards automatic program understanding, which can have great impact in computer science and beyond. Thus, the work is not only a scientific advance but can also lead to faster, more reliable software and increased programmer productivity, with significant benefit for multiple sectors of the economy. Furthermore, the project aids the reintegration of a successful European researcher, thus contributing to European excellence and competitiveness. The work performed since the beginning of the project has been described in numerous top-quality publications (CC'13, PLDI'13, PLDI'14, OOPSLA'13x2) and two M.Sc. theses by University of Athens students, George Balatsouras and George Kastrinis. The M.Sc. theses' contents directly address the goals of the project. The first is titled "Declarative Whole Program Escape Analysis for Java" while the second is titled "The Role of Exceptions in Static Program Analysis for Java". The work has resulted in corresponding additions to the functionality of the Doop framework and has resulted in much more scalable support for exceptions, as well as declarative support for escape analysis (yielding more precision than past approaches). A web page for the resulting program analysis framework (which encompasses but is not specific to the current project) is: http://doop.program-analysis.org/ The beneficiary/Researcher has been professionally re-integrated in the host country, currently holding a permanent position (Associate Professor) at the host institution.
Data: CORDIS, © European Union
Project objective
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.
Original text from CORDIS.
Participants
- ETHNIKO KAI KAPODISTRIAKO PANEPISTIMIO ATHINON · ATHINACoordinatorGreece
Links
Data: CORDIS, © European Union