FrontPage


Welcome to CS294-32: Dynamic Program Analysis, Testing, and Debugging: Spring 2009

 

General Information

Course Description

Today's software systems suffer from poor reliability and security due to their overwhelming complexity. The problem is even worse for concurrent software systems. A 2002 NIST report estimates that software errors cost the U.S. economy $59.5 billion annually. Traditional software testing and debugging, which usually accounts for more than half the cost of software development, often fail to find many critical bugs in software. Therefore, in the recent years there has been an increasing interest on automated systematic techniques for improving software reliability. A number of recent techniques and tools have combined ideas from program analysis, automated theorem proving, constraint solving, and formal methods and have shown great promises in making software reliable and secure. In this graduate seminar, we will study this new trend with a special focus on program analysis.

We will study:

  1. Automated test generation using sophisticated program analysis and constraint solving techniques. 
  2. Software model checking and various theoretical results that form the foundation of software model checking.
  3. Concurrent program analysis.
  4. Abstract interpretation and points-to analysis.
  5. Scalable static termination detection.
  6. Compositional model checking.

Goals of this course:

  1. To help students start research in the area of program analysis of sequential and concurrent systems.
  2. To help students to apply the techniques learned in this course in their ongoing research in other areas such as parallel computing, operating systems, computer networks, security, and database systems.

Lecture Format and Student Workload

The course readings will include a selected list of papers. Students will read papers ahead of time, review papers, participate in discussions, and do a research project in small teams or individually.  There will be around 16 guest lectures from the leading researchers in the area of programming languages and software engineering.  The guest lecturers include Thomas BallByron Cook, Dimitra Giannakopoulou, Ranjit Jhala, Madan Musuvathi, Mayur NaikCorina Pasareanu, and Mooly Sagiv

Schedule

Lecture Schedule

Grading Details

  1. Project (1-2 student team): (40%) A project must involve new research: it may involve designing a new algorithm, improving an existing technique, or performing a large case study. The idea behind each project should be evaluated by experiments on publicly used programs. The evaluation metrics should be performance improvement, scalability, or discovering previously unknown bugs. 
  2. Paper review and class participation: (30%) We will discuss one paper per meeting. A student will submit a short written review (at most 500 words) of each paper. Reviews will be made available to all students.
  3. Homework (30%).

Reference Books

This course has no required textbook. Research papers and slides will be posted online as needed.