Dagstuhl Seminar 13162
Pointer Analysis
( Apr 14 – Apr 19, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/13162
Organizers
- Ondrej Lhotak (University of Waterloo, CA)
- Yannis Smaragdakis (University of Athens, GR)
- Manu Sridharan (IBM TJ Watson Research Center - Yorktown Heights, US)
Contact
- Annette Beyer (for administrative matters)
External Homepage
Schedule
Pointer analysis is one of the most fundamental static program analyses. It consists of computing an abstraction of which heap objects a program variable or expression can refer to. Due to its importance, a large body of work exists on pointer analysis, and many researchers continue to study and develop new variants. Pointer analyses can vary along many axes, such as desired precision, handling of particular language features, and implementation data structures and optimizations. Given the subtle implications of these design choices, and the importance of low-level details often excluded from conference-length papers, it can be difficult even for pointer analysis experts to understand the relationship between different analysis variants. For a non-expert aiming to use pointer analysis in a higher-level client (for verification, optimization, refactoring, etc.), choosing the right analysis variant can be truly daunting.
This seminar brings together researchers working on pointer analysis for various programming languages with researchers working on key analysis clients. The main goals are (1) to deepen understanding of the relationships between existing pointer analysis techniques, and (2) to gain a better understanding of what pointer analysis improvements are required by clients, thereby setting an exciting agenda for the area going forward.
Pointer analysis is a mature area with a wealth of results, at a temptingly close distance from wide practical applicability, but not there yet. The breakout application of precise analysis algorithms has seemed to be around the corner for the past decade. This seminar can be truly catalytic in the most crucial next steps. By bringing together the community, we hope to consolidate the intense progress in the area in all the right ways, by complementing expertise, by cultivating connections to clients of pointer analysis, and by sharing experience on deployment of analysis algorithms in practice.
The Dagstuhl seminar on Pointer Analysis brought together experts in pointer analysis and researchers building demanding clients of pointer analysis, with the goal of disseminating recent results and identifying important future directions. The seminar was a great success, with high-quality talks, plenty of interesting discussions, and illuminating breakout sessions.
Research context
Pointer analysis is one of the most fundamental static program analyses, on which virtually all others are built. It consists of computing an abstraction of which heap objects a program variable or expression can refer to. Due to its importance, a large body of work exists on pointer analysis, and many researchers continue to study and develop new variants. Pointer analyses can vary along many axes, such as desired precision, handling of particular language features, and implementation data structures and optimizations. Given the subtle implications of these design choices, and the importance of low-level details often excluded from conference-length papers, it can be difficult even for pointer analysis experts to understand the relationship between different analysis variants. For a non-expert aiming to use pointer analysis in a higher-level client (for verification, optimization, refactoring, etc.), choosing the right analysis variant can be truly daunting.
Pointer analysis is a mature area with a wealth of research results, at a temptingly close distance from wide practical applicability, but not there yet. The breakout application of precise analysis algorithms has seemed to be around the corner for the past decade. Although research ideas are implemented and even deployed in limited settings, several caveats always remain. These include assumptions about client analyses (i.e., the pointer analysis algorithm is valid only under assumptions of how the information will be used), assumptions about the analyzed program (e.g., that some language features are absent or that their presence does not affect the analysis outcome), assumptions about modularity (e.g., that the code to be analyzed constitutes the whole program), etc. The right engineering packaging of pointer analysis algorithms as well as a convenient characterization of their domain of applicability are still elusive.
In this light, the seminar aimed to emphasize the relationship of pointer analysis algorithms with client analyses, as well as practical deployment issues. The seminar brought together researchers working on pointer analysis for various programming languages with researchers working on key analysis clients. Our main goals were (1) to deepen understanding of the relationships between existing pointer analysis techniques, and (2) to gain a better understanding of what pointer analysis improvements are required by clients, thereby setting an exciting agenda for the area going forward.
Seminar Format
Our seminar employed a somewhat unusual format for participant talks, intended to encourage a deeper discussion of each participant's work. Each participant was alloted a 40-minute slot to present their work, consisting of 20 minutes of presentation and 20 minutes of discussion. The presentation and discussion times in each slot were enforced using a chess clock: when a question arose during a talk, the clock was "flipped" to discussion time, and after the discussion, it was flipped back to speaker time. (The times were not very strictly enforced; in some cases, the audience would "donate" time to the speaker to complete his/her presentation.) This format had two key benefits:
- It enabled discussion to freely occur during the talk, removing the worry that the speaker would have no time left to complete his/her presentation.
- It encouraged the audience to ask more questions, in order to "use up" the alloted audience time.
Overall, the format was very successful in encouraging good discussion, and most participants enjoyed it.
In addition to talks, we held four 90-minute breakout sessions. The session topics were proposed by participants before and during the seminar and voted on by participants. The sessions were scheduled two at a time, and participants could choose which session to attend. The discussions held in these sessions were quite illuminating, and are summarized in Section 4 of this report. Finally, the last half-day of the seminar was spent on additional discussion of the breakout session topics, and on an initial effort to collectively improve the Wikipedia article on pointer analysis.(http://en.wikipedia.org/wiki/Pointer_analysis).
Seminar Results
Recent advancements in pointer analysis have come from several different directions:
- Formulations (CFL, Datalog)---highly-complex analyses have been specified in terms of consise specifications, by utilizing declarative notations.
- Greater precision---interesting analyses that maintain finer-grained abstractions while maintaining scalability have been invented.
- Optimizations---data structures such as BDDs have been used to make complex analyses feasible.
- Demand-driven, refinement---the analysis problem has been specialized effectively when pointer information only needs to be computed for select program sites.
- Partial programs---analyses have been formulated to work without fully analyzing all libraries, or even all application code.
Such advances were discussed in detail during many participant talks in the seminar, and in the breakout sessions.
Recent work in pointer analysis has been driven by new clients for the analysis and by new programming languages. Along with ongoing use of pointer analysis in traditional optimizing compilers, recent years have seen many other clients emerge that require effective pointer analysis, e.g., in the areas of program verification and bug finding, refactoring, and security. These clients were well-represented by seminar attendees, who gave many interesting talks on novel uses of pointer analysis (particularly in the security domain). The rich exchanges between researchers building novel clients and those with pointer analysis expertise were one of the most valuable aspects of the seminar. Additionally, one breakout session covered the difficulties in designing an effective general pointer-analysis API that is suitable for a wide variety of clients.
Mainstream programming has been transitioning to increasingly heap-intensive languages: from C-like languages to object-oriented languages like Java and C#, and more recently to scripting languages like JavaScript and Ruby. As languages become more heap-intensive, the need for effective pointer analysis is greater, motivating continuing work in this area. The seminar talks covered a wide and diverse set of languages, each with its own considerations. A few talks covered pointer analysis for higher-level languages such as JavaScript and MATLAB. Such languages are becoming increasingly popular, and they are very heap-intensive compared to C-like languages, motivating the need for better pointer analysis. A couple of talks presented techniques for control-flow analysis of functional languages like Scheme. While the pointer analysis and control-flow analysis communities often use similar techniques, the relationships between the techniques is often obscured by differing terminology and presentation styles. The presentations on control-flow analysis and the corresponding discussions were helpful in bridging this gap.
The seminar included a good deal of discussion on practical issues with pointer analysis, including evaluation methodologies and issues arising in real-world deployments. A key theme that arose from these discussions was the need for pointer analysis to be at least partially unsound to be useful in practice, and how this need for unsoundness has not been explained properly in the literature. Analyses that made soundness compromises for practicality were deemed "soundy," a tongue-in-cheek term that caught on quickly among participants. Recently, some seminar participants presented a well-received PLDI Fun and Interesting Topics (FIT) talk on the notion of "soundiness," and several participants have agreed to collectively co-author a publishable document on the topic.
Conclusions
Overall, the Pointer Analysis Dagstuhl seminar was a great success. The seminar brought together 27 researchers from both academia and industry (including Google, IBM, Microsoft, NEC), with a good mix of junior and senior researchers. There were many interesting talks, with deep discussion facilitated by the chess clock time maintenance. The seminar facilitated interaction between pointer analysis experts and researchers building novel clients (a key goal for the seminar from the beginning), and also between researchers working on analyses for a variety of languages. Breakout sessions enabled further discussion of certain particularly interesting topics. In particular, there were invaluable discussions of many practical issues that often get short shrift in conference papers. These discussions sparked the notion of "soundiness," which may have broader impact via a future publication.
Creative Commons BY 3.0 Unported license
Ondrej Lhotak, Yannis Smaragdakis, and Manu Sridharan
- José Nelson Amaral (University of Alberta - Edmonton, CA) [dblp]
- Gogul Balakrishnan (NEC Laboratories America, Inc. - Princeton, US) [dblp]
- Eric Bodden (TU Darmstadt, DE) [dblp]
- Bor-Yuh Evan Chang (University of Colorado - Boulder, US) [dblp]
- Isil Dillig (College of William and Mary - Williamsburg, US) [dblp]
- Thomas Dillig (College of William and Mary - Williamsburg, US) [dblp]
- Julian Dolby (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Samuel Z. Guyer (Tufts University - Medford, US) [dblp]
- Christian Hammer (Universität des Saarlandes, DE) [dblp]
- Laurie J. Hendren (McGill University - Montreal, CA) [dblp]
- Uday Khedker (Indian Institute of Technology - Mumbai, IN) [dblp]
- Ondrej Lhotak (University of Waterloo, CA) [dblp]
- Ben Livshits (Microsoft Corporation - Redmond, US) [dblp]
- Welf Löwe (Linnaeus University - Växjö, SE) [dblp]
- Mark Marron (Microsoft Corporation - Redmond, US) [dblp]
- Matthew Might (University of Utah - Salt Lake City, US) [dblp]
- Ana Milanova (Rensselaer Polytechnic Institute - Troy, US) [dblp]
- Anders Møller (Aarhus University, DK) [dblp]
- Mayur Naik (Georgia Institute of Technology - Atlanta, US) [dblp]
- Hakjoo Oh (Seoul National University, KR) [dblp]
- Erhard Plödereder (Universität Stuttgart, DE) [dblp]
- Xavier Rival (ENS - Paris, FR) [dblp]
- Yannis Smaragdakis (University of Athens, GR) [dblp]
- Gregor Snelting (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Manu Sridharan (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Bjarne Steensgaard (Microsoft Corporation - Redmond, US) [dblp]
- Dimitris Vardoulakis (Google Inc. - Mountain View, US) [dblp]
Classification
- programming languages / compiler
- software engineering
- verification / logic
Keywords
- Pointer analysis
- points-to analysis
- Static analysis
- Optimization
- Verification
- Bug finding
- Development tools
