April 13 – 18 , 2008, Dagstuhl Seminar 08161
Scalable Program Analysis
For support, please contact
As the volume of existing software in the industry grows at a rapid pace, the problems of understanding, maintaining, and developing software assume great significance. A strong support for analysis of programs is essential for a practical and meaningful solution to such problems. Static analysis tools can make a huge impact on how software is engineered but in an industrial context research must be properly balanced with a focus on deployment of analysis tools.
Our goal was to bring together researchers from academia and industry to discuss the strengths and weaknesses of state-of-the-art program analysis technology for industrial-sized software. To achieve that goal the seminar gathered~38 participants from 9 companies and 23 academic/research institutions.
The seminar started with two sessions on technological research challenges in industry and continued with more theoretical sessions, covering scalable shape and pointer analysis, concurrent program analysis, source-level and scalable instruction-level analysis, scalable path conditions, state-of-the-art techniques in abstract interpretation for scalability, and type systems. Overall we had 28 talks, with a good diversity in topics, showing the many research directions and applications of program analysis, also covering program synthesis with sketching, using machine learning for scalable analysis, analysis for architecture reconstruction, and data-flow analysis for multi-core architectures.
A high number of participants, about 50%, had also implemented their analysis technique in a tool. Some participants had already expressed some interest in tool sessions before the seminar, but there were also concerns mentioned that tool sessions can be a real show-stopper if too lengthy. To encourage lively discussions, the tool sessions were preceded by discussion groups starting on Tuesday. Each group consisted of 4--7 people, of which at least two people had already indicated their interest in presenting a tool. Each group was asked to define a set of challenging questions to be asked about a program analysis tool. On the the next day, Wednesday, we selected in a one hour discussion session in a democratic process a subset of the proposed questions to be answered by every tool presenter on Wednesday/Friday.
The idea was that each presentation of a tool would start by answering those selected 7 questions, providing some basis for comparing the tools, and to create a common frame for each tool presentation. The presentations were kept to a minimum in time, about 15 mins, and the presenters were asked to focus on the most impressive analysis feature of the tool.
This format with preceding working groups worked out well, as it further increased the interest in the tool sessions. We eventually scheduled~15 tool & infrastructure presentations on Thursday and Friday.
The Dagstuhl seminar on ``Scalable Program Analysis'' was a tremendous success with many fruitful discussions and new questions being raised. Several connections between industry and academia were formed and showed all signs that they will find their continuation after the seminar. The seminar also showed that program analysis and the question about scalability is cross-cutting many different communities. This was also reflected by the diversity of the techniques presented in talks and the tools as well. The cooperation of industry and academia, as being encouraged by many funding programs these days, will further help both sides, to focus on new methods for addressing, characterizing, and comparing scalability.
- Data Structures / Algorithms / Complexity
- Security / Cryptography
- Optimization / Scheduling
- Programming Languages / Compiler
- Semantics / Specification / Formal Methods
- Verification / Logic
- Static analysis
- Pointer analysis
- Data flow analysis
- Error detection