One can ask many interesting questions about a given program such as:
- Does this program terminate?
- Can the pointer p be null?
- Will the value of the variable v be read in the future?
- Do the variables x and y point to the same location in the heap?
- Was the loop counter i initialized before it is used?
- Could the secret data pointed to by s leak to some unauthorized party?
- Can method foo call method bar? And which method bar could be called?
The answer to all those interesting questions about a program is undecidable as stated by Rice’s Theorem. However, people usually use static program analysis to get approximate answers to those questions, which works well in many cases. For example, many bug finding tools (e.g., FindBugs) use various static analysis techniques to detect, and possibly fix, bugs in a given program. Additionally, security analysis tools (e.g., AppScan, FlowDroid) also use static analysis to detect security vulnerabilities and data leakages. In this course, we will read research papers that explain the basics of static analysis as well as the state-of-the-art.
- TUCaN ID: 20-00-0942
- Course Type: Seminar (4CP)
- Language: English
- Kickoff: Tuesday 13.10.15 — 9:50 to 11:30 — Fraunhofer SIT, Raum München
- Class Meetings: Tuesdays — 9:50 to 11:30 — Fraunhofer SIT, Raum München
- Instructor: Dr. Karim Ali (contact)
- Office Hours: by appointment
- Teaching Assistant: Johannes Späth
This is a seminar-based course where we will announce a list of papers selected for the course before the first week of lectures. Each paper will have a specific date/time to be presented at (see tentative schedule below). Students can then select their paper preferences by the end of the first week of lectures. For each meeting, you’re expected to:
- If you are assigned a paper on that day:
- you should deliver a 20 minute presentation to introduce that paper
- you will also lead a 10 minute discussion and answer questions from the audience
- For everybody else:
- you have to read and submit a review of ONE paper from the list of papers that we will discuss that day (review is 1 page max)
- Everybody should:
- submit reviews for ALL the presentations delivered by your colleagues on that day, except, obviously, your own presentations
- participate in the paper discussion
Once the presenters receive their anonymous presentation reviews, they have the chance to submit a short paragraph describing the quality of the reviews they got. The purpose of those activities is to give you a chance to practice a lot of the tasks a researcher encounter: delivering conference presentations, paper reviews, getting feedback about presentation, etc.
|13.10.15||Organizational Meeting + Assignment 0||Karim Ali|
|20.10.15||Points-to Analysis & Call Graphs|
|Ondřej Lhoták and Laurie Hendren. Scaling Java Points-to Analysis Using Spark, CC 2003, pages 153-169.|
|Frank Tip, Jens Palsberg. Scalable Propagation-Based Call Graph Construction Algorithms, OOPSLA’00, pages 281-293.|
|Karim Ali, Marianna Rapoport, Ondřej Lhoták, Julian Dolby, and Frank Tip. Constructing Call Graphs of Scala Programs, ECOOP’14, pages 54-79.||Karim|
|27.10.15||Control-Flow, Object-Sensitivity, and Refinement-Based Analyses|
|O. Shivers. Control flow analysis in scheme, PLDI’88, pages 167-174.||Thomas|
|Ana Milanova, Atanas Rountev, and Barbara G. Ryder. Parameterized object sensitivity for points-to and side-effect analyses for Java, ISSTA’02, pages 1-11.|
|Manu Sridharan and Rastislav Bodík. Refinement-based context-sensitive points-to analysis for Java, PLDI’06, pages 387-400.|
|Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses, OOPSLA’09, pages 243-262.||Sruthi & Mohan|
|Raja Vallée-Rai, Etienne Gagnon, Laurie J. Hendren, Patrick Lam, Patrice Pominville, and Vijay Sundaresan. Optimizing Java Bytecode Using the Soot Framework: Is It Feasible?, CC’00, pages 18-34.||Mirko & Johannes|
|Thomas W. Reps, Susan Horwitz, and Shmuel Sagiv. Precise Interprocedural Dataflow Analysis via Graph Reachability, POPL’95, pages 49-61.|
|Shmuel Sagiv, Thomas W. Reps, and Susan Horwitz. Precise interprocedural dataflow analysis with applications to constant propagation, Theoretical Computer Science, 167(1-2):131-170, 1996.||Laila|
|Nomair A. Naeem, Ondřej Lhoták, and Jonathan Rodriguez. Practical Extensions to the IFDS Algorithm, CC’10, pages 124-144.|
|Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. FlowDroid: Precise Context, Flow, Field, Object-sensitive and Lifecycle-aware Taint Analysis for Android Apps, PLDI’14, page 29.||Mirko & Johannes|
|Damien Octeau, Daniel Luchaup, Matthew Dering, Somesh Jha, and Patrick McDaniel. Composite Constant Propagation: Application to Android Inter-Component Communication Analysis, ICSE’15, pages 77-88.||Laila|
|Shengqian Yang, Dacong Yan, Haowei Wu, Yan Wang, and Atanas Rountev. Static Control-Flow Analysis of User-Driven Callbacks in Android Applications, ICSE’15, pages 89-99.||Thomas|
|01.12.15||Typestate Analysis & Call Graphs|
|Nomair A. Naeem and Ondřej Lhoták. Typestate-like Analysis of Multiple Interacting Objects, OOPSLA’08, pages 347-366.||Thomas|
|Xin Zhang, Ravi Mangal, Mayur Naik, and Hongseok Yang. Hybrid Top-down and Bottom-up Interprocedural Analysis, PLDI’14, page 28.|
|Karim Ali and Ondřej Lhoták. Averroes: Whole-Program Analysis Without the Whole Program, ECOOP’13, pages 378-400.||Bharathi|
|08.12.15||Dynamic Languages I|
|David Hauzar and Jan Kofroň. Framework for Static Analysis of PHP Applications, ECOOP’15, pages 689-711.||Azmat|
|Vaseline Raychev, Martin Vechev, and Andreas Krause. Predicting Program Properties from “Big Code”, POPL’15, pages 111-124.||Sruthi & Mohan|