Course Summary

4 CP, 2 SWS, Thursdays on 9:50-11:30 in room 3.1.01 at CASED

The topic of this lecture is the automated (static) code analysis of large software systems, particularly with respect to security properties. We will be treating important scientific problems in the area (partially solved, partially open), and will discuss different conceptual frameworks that can be used to design and implement automated code analyses. We will be paying particular attention to flow- and context sensitive analyses, as well as pointer analyses.

This integrated lecture combines presentations with practical exercises that participants can solve at home in small groups and which are discussed after each lecture. Participants can obtain a bonus by completing these exercises. Goal of the exercises is to learn hands-on what it means to design and implement security code analyses for Android and Java using a Java-based program analysis framework. Students will learn how to design precise and efficient security analyses.

Click here for a detailed outline!


The good old monotone framework:

  • Intra-procedural dataflow analyses*
  • Off-the-shelve call-graph and pointer analyses
  • Inter-procedural dataflow analyses

Call-strings approach vs. functional approach:

  • IFDS and IDE
  • More expressive frameworks

Dealing with pointers and aliasing:

  • Problem of context reification
  • Integration of demand-driven pointer analyses

Scalability through summaries:

  • Summarizing analysis information for frameworks and libraries
  • Modeling pointers through alloc sites vs. access paths

Current and “eternal” limitations:

  • Practical limitations to current client analyses
  • Reflection, dynamic loading, eval

Further Reading (list still incomplete)

  • Thomas Reps, Susan Horwitz, and Mooly Sagiv. 1995. Precise interprocedural dataflow analysis via graph reachability. POPL ’95
  • Shmuel Sagiv, Thomas W. Reps, and Susan Horwitz. 1995. Precise Interprocedural Dataflow Analysis with Applications to Constant Propagation. TAPSOFT ’95
  • Akash Lal, Thomas Reps, and Gogul Balakrishnan. 2005. Extended weighted pushdown systems. CAV 2005
  • Nomair A. Naeem, Ondrej Lhoták, and Jonathan Rodriguez. 2010. Practical extensions to the IFDS algorithm. CC 2010
  • Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhoták. 2011. Pick your contexts well: understanding object-sensitivity. POPL 2011
  • Eric Bodden. 2012. Inter-procedural data-flow analysis with IFDS/IDE and Soot. SOAP 2012
  • Rohan Padhye, Uday P. Khedker. Interprocedural Data Flow Analysis in Soot using Value Contexts. SOAP 2013

Preliminary schedule and course materials (will be expanded on the fly)

Date Topic Links Material
17. Okt. 2013 Overview/Introduction
24. Okt. 2013 Intra-procedural dataflow analyses
31. Okt. 2013
7. Nov. 2013 – no lecture, due to CCS
14. Nov. 2013
21. Nov. 2013
28. Nov. 2013
5. Dez. 2013
12. Dez. 2013
19. Dez. 2013
16. Jan. 2014
23. Jan. 2014
30. Jan. 2014
6. Feb. 2014
13. Feb. 2014