Automated Software Analysis Group

Automatic Program Checking

  • type: lecture
  • semester: SS 2011
  • place:

    Geb. 50.34, Room 236

  • time:

    Monday, Thursday 14:00 - 15:30

  • start: 11.04.2011
  • lecturer:

    Mana Taghdiri, Aboubakr Achraf El Ghazi

  • sws: 3
  • ects: 5

The goal of this course is to introduce students to some modern approaches that can simplify the software development process. We will describe a number of program checking techniques, explain their pros and cons, and discuss what else needs to be done in order to make them fully applicable to real-life software systems.

In this lecture, we will cover some state-of-the-art techniques that check and detect correctness properties of programs. We will particularly focus on lightweight techniques that work at a push-of-a-button: those that are fully automatic and expect very little input from users. Because these techniques do not depend on much user-provided guidance and can be run without any user interactions, they can be easily incorporated into a wide range of software development processes.

In this lecture, we will cover techniques for:

  • Generating test cases exhaustively,
  • Generating test cases randomly,
  • Generating test cases by symbolic execution,
  • Generating test cases by concolic execution.

Readings

  • Alloy:
    • Alloy website: http://alloy.mit.edu/community
    • Software abstractions: logic, language, and analysis, D. Jackson, MIT Press, Cambridge, MA, March 2006. (amazon)
    • A micromodularity mechanism, D. Jackson, I. Shlyakhter, M. Sridharan, 2001. (pdf)
  • Alloy Engine:
    • Automating first-order relational logic, D. Jackson, 2000. (pdf)
    • Kodkod: a relational model finder, E. Torlak, D. Jackson, 2007. (pdf)
    • Kodkod for Alloy users, E. Torlak, G. Dennis, 2006. (pdf)
  • Test case generation:
    • TestEra Generating Structurally Complex Tests from Declarative Constraints, S. Khurshid, MIT PhD Thesis, 2003. (pdf)
    • Korat Automatic Testing of Software with Structurally Complex Inputs, D. Marinov, MIT PhD Thesis, 2004. (pdf)
    • AsmLT Towards a Tool Environment for Model-Based Testing with AsmL, B. Barnett, W. Grieskamp, L. Nachmanson, W. Schulte, N. Tillmann, M. Veanes, 2003. (pdf)
    • JCrasher An Automatic Robustness Tester for Java, C. Csallner, Y. Smaragdakis, 2000. (pdf)
    • Randoop Directed Random Testing, C. Pacheco, MIT PhD Thesis, 2009. (pdf)
    • Rostra A Framework for Detecting Redundant Object-Oriented Unit Tests, T. Xie, D. Marinov, D. Notkin, 2004. (pdf)
    • Symstra A Framework for Generating Object-Oriented Unit Tests using Symbolic Execution, T. Xie, D. Marinov, W. Schulte, D. Notkin, 2005. (pdf)
    • Cute  Scalable Automated Methods for Dynamic Program Analysis, K. Sen, UIUC PhD Thesis , 2006. (pdf)
  • Static bug finding:
    • Jalloy Finding Bugs in Software with a Constraint Solver, M. Vaziri, MIT PhD Thesis, 2004. (pdf)