CSE 6329: Special Topics in Advanced Software Engineering: Fall 2008

Basic Information

Time: Monday and Wednesday 4:00-5:20 pm
Location: GS 109 (in the Geoscience building)

Instructor: Christoph Csallner
Email: csallner@uta.edu
Office hours: Monday and Wednesday 5:30-6:30 pm (in NH 306)

Slides

cse6329-2008-08-25-intro.pdf

Topic: Program Analysis

This course is a hands-on introduction to program analysis. We experiment with cutting-edge program analysis tools and work through the techniques they are built on. This should give us a good grasp of the fundamental properties of static program analysis, dynamic program analysis, and their combinations. The course targets both Master and Ph.D. students.

Motivation

Software is everywhere	Bad program behavior could be fatal

(Warsaw, Poland. Picture by rintakumpu)	(Not an actual crash. Picture by louder)

Bad program behavior during production use can endanger the safety of users and become very expensive. To protect the user from bad program behavior, we would like to reason about programs and predict their behavior. Luckily, many techniques exist for reasoning about programs. The subset of automated techniques is commonly referred to as program analysis.

Program analysis is used in many real-world applications. Examples include compilers and virtual machines (e.g.: gcc, HotSpot JVM, .Net), integrated development environments (Eclipse, Visual Studio), automatic bug finding and verification (FindBugs, Static Driver Verifier, Spec#), program understanding and re-engineering (Agitar), embedded system development (AbsInt), etc.

Prerequisites

Fluency in an object-oriented programming language. Good examples include Java, C#, C++, OCaml, and Eiffel.

Overview

Following is a tentative overview.

Static analysis

Control flow and dataflow. Example: FindBugs

Dynamic analysis

Automatic testing. Example: JCrasher
Dynamic invariant detection. Example: Daikon

Formal specification

Design by contract. Example: JML

Static analysis, advanced

Symbolic execution. Example: Spec#

Combining static and dynamic analyses

Analysis pipelines. Example: DSD-Crasher
Dynamic symbolic execution. Example: Pex

Mailing list

We use our mailing list as the main channel for asking and answering questions about homework assignments, etc: CSE6329-CSALLNER.

Textbook

Mauro Pezzè and Michal Young. Testing and Analysis: Process, Principles, and Techniques. John Wiley & Sons. April 2007.

We use selected papers from the literature for advanced material not covered by the textbook.

Optional references

Kenneth H. Rosen. Discrete Mathematics and its Applications. McGraw-Hill. (This textbook explains the basic concepts of set, relation, function, graph, tree, etc.)

Michael Sipser. Introduction to the Theory of Computation. Course Technology. (This textbook provides a very readable introduction to automata, decidability, and complexity theory.)

Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley. (This is the classic compiler book. It gives a thorough introduction to basic program analysis concepts, including basic blocks, control flow graphs, and dataflow analyses.)

Evaluation

Following is the tentative plan.

50% midterm and final exam
25% homework, including hands-on tool evaluation and some easy coding
10% class participation
15% presentation of a research paper from the reading list

Resources

Java

Subjects for experimentation

The Software-artifact Infrastructure Repository (SIR) contains different versions of several real-world programs with seeded bugs.