Course Description

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 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.

General Information

  • 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: “https://karimali.ca/sas/”
  • Instructor: Karim Ali (see contact information below)
  • Office Hours: by appointment
  • Teaching Assistant: Johannes Späth

Course Format

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.

Evaluation Criteria

Presentations: 40%
Paper Summaries: 30%
Participation: 20%
Presentation Peer-Reviews: 10%

Schedule

Date Paper Presenter(s)
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.
03.11.15 Guest Lecture: "JavaScript and Mobile Static Analysis with WALA at IBM" Julian Dolby
10.11.15 Analysis Frameworks
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
17.11.15 Tabulation/IFDS/IDE
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.
24.11.15 Android I
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
Koushik Sen, Swaroop Kalasapur, Tasneem G. Brutch, and Simon Gibbs. Jalangi: a selective record-replay and dynamic analysis framework for JavaScript, FSE'13, pages 488-498.
Vaseline Raychev, Martin Vechev, and Andreas Krause. Predicting Program Properties from "Big Code", POPL'15, pages 111-124. Sruthi & Mohan
12.01.16 Analysis Infrastructure
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.
26.01.16 Android III
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
Magnus Madsen, Frank Tip, and Ondřej Lhoták. Static Analysis of Event-Driven Node.js JavaScript Applications, OOPSLA'15. Azmat
Essen Andreasen and Anders Møller. Determinacy in Static Analysis for jQuery, OOPSLA'14.
Shiyi Wei and Barbara Ryder. Adaptive Context-sensitive Analysis for JavaScript, ECOOP'15.
09.02.16 Usability
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