263-2910-00L  Automated Techniques for Software Reliability

SemesterAutumn Semester 2012
LecturersM. Vechev
Periodicityyearly course
Language of instructionEnglish

AbstractThis course introduces both theoretical and applied aspects of automatic program analysis. We will cover both:

i) Core principles underlying automated analysis.

ii) Applications of these techniques to solve challenging practical problems (e.g. in security, reliability, synthesis).
ObjectiveThe course has 3 main objectives:

- Understand the foundational principles behind automated program analysis techniques.

- Understand how to use these principles to build a practical working analyzer. This will be helped by a hands-on programming project.

- Gain familiarity with the state-of-the-art in the research area.
ContentThe last 10 years have seen an explosion in techniques for automated program analysis. These techniques have enabled a vast range of interesting applications: from ensuring correctness of complex algorithms to finding security violations in mobile applications and even to code synthesis.

This course will cover the core principles behind these automated techniques including static and dynamic program analysis, symbolic execution, predicate abstraction, pointer analysis as well as practical analysis frameworks such as Soot.

To gain a deeper understanding of how to apply these techniques in practice, the course will involve a small hands-on programming project where based on the principles introduced in class, the students will build a program analyzer for a modern programming language.

Topics Include (we will cover only some of these):

program semantics: small-step, big-step, concurrency, usage examples
dynamic analysis: typestate, race detection
abstract interpretation: domains, soundness, precision, fixed points, applications
predicate abstraction: classic (Graf-Saidi), boolean programs (SLAM for C code)
pointer analysis: flow-insensitive
symbolic execution: SMT solvers, concolic, tools (CUTE/DART/KLEE)
program synthesis: synthesis of concurrent programs, combining with abstractions
inter-procedural analysis: two approaches: Pnueli, Reps.
program analysis frameworks: Wala, Soot, LLVM
Lecture notesDistributed in class.
LiteratureDistributed in class.
Prerequisites / NoticeThis course is aimed at graduate students, but advanced bachelor students can sign up with lecturer's permission.