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
vbe read in the future?
- Do the variables
ypoint to the same location in the heap?
- Was the loop counter initialized before it is used?
- Could the secret data pointed to by
sleak to some unauthorized party?
- Can method
bar? And which method
barcould 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
- Web Page: “http://karimali.ca/sas/”
- Instructor: Karim Ali (see contact information below)
- 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|
|Caitlin Sadowski, Jeffrey van Gogh, Ciera Jaspan, Emma Söderberg, and Collin Winter. Tricorder: Building a Program Analysis Ecosystem, ICSE'15, pages 598-608.|
|Jens Dietrich, Nicholas Hollingum, and Bernhard Scholz. Giga-Scale Exhaustive Points-To Analysis for Java in Under a Minute, OOPSLA'15.|
|Rohan Padhye and Uday P. Khedker. Interprocedural data flow analysis in Soot using value contexts, SOAP'13, pages 31-36.||Mirko & Johannes|
|19.01.16||Pushdown Systems & Analysis Correctness|
|Thomas W. Reps, Stefan Schwoon, Somesh Jha, and David Melski. Weighted Pushdown Systems and Their Application to Interprocedural Dataflow Analysis, SAS'03, pages 189-213.||Laila|
|Roberto Giacobazzi, Francesco Logozzo, and Francesco Ranzato. Analyzing Program Analyses, POPL'15, pages 261-273.|
|Paolina Centonze, Marco Pistoia, and Omer Tripp. Access-rights Analysis in the Presence of Subjects, ECOOP'15, pages 222-246.||Bharathi|
|Lucas Brutschy, Pietro Ferrara, Omer Tripp, and Marco Pistoia. ShamDroid: Gracefully Degrading Functionality in the Presence of Limited Resource Access, OOPSLA'15.|
|02.02.16||Dynamic Languages II|
|Essen Andreasen and Anders Møller. Determinacy in Static Analysis for jQuery, OOPSLA'14.|
|Brittany Johnson, Yoonki Song, Emerson R. Murphy-Hill, and Robert W. Bowdidge. Why don't software developers use static analysis tools to find bugs?, ICSE'13, pages 672-681.||Sruthi & Mohan|
|Justin Smith, Brittany Johnson, Emerson Murphy-Hill, Bill Chu and Heather Richter Lipford. Questions Developers Ask While Diagnosing Potential Security Vulnerabilities with Static Analysis, FSE'15.||Azmat|
|Jim Witschey, Olga Zielinska, Allaire Welk, Emerson Murphy-Hill, Chris Mayhorn, and Thomas Zimmermann. Quantifying developers' adoption of security tools, FSE'15, pages 260-271.||Bharathi|