CIS 573: Software Engineering (Fall 2019)

[F.A.Q.] [Administrivia] [Syllabus] [Labs] [Schedule]



Time: Mondays and Wednesdays, 1:30-3:00 pm
Location: Berger Auditorium, Skirkanich Hall
Instructor: Mayur Naik
Office: Levine 610
Office hours: Wed 3-4 (or by appointment)
Elizabeth Dinella
Office: Levine 575
Office hours: Fri 12-2

Pardis Pashakhanloo
Office: Levine 575
Office hours: Tue 2-4
Acknowledgments: Kihong Heo - primary author of labs
Anthony Canino - lab enhancements


Course Description: This course covers the theory and practice of software analysis -- a body of algorithms and techniques to reason about program behavior with applications to effectively test, debug, and secure large, complex codebases. The course surveys a wide range of applications of software analysis including proving the absence of common programming errors, discovering and preventing security vulnerabilities, systematically testing intricate data structures and libraries, and localizing root causes in complex software failures.

Topics Covered: Intermediate program representations, program specifications, runtime instrumentation, randomized testing, dataflow analysis, constraint generation and constraint solvers, type inference, automated debugging, symbolic execution, assertion verification, automated theorem proving.

Course Outline: In each week, we will cover a different software analysis technique in class. In the following week, you will do a lab in which you will implement the technique in the LLVM compiler framework in C++, and evaluate it on sample C programs. There are 12 such labs (Lab 1 thru Lab 12), plus a prereq Lab 0 in which you will setup the Course VM and familiarize yourself with LLVM.

Grading Rubric: The grading rubric is as follows:

Lab 0 (prereq)2%
Labs 1-1270%
Final Exam25%
Class Participation3%

The prereq Lab 0 is worth 2% and Labs 1-12 are worth 7% each. In the end, we will drop your lowest two of Labs 1-12, so the labs are collectively worth 2 + 7*10 = 72%.

Collaboration Policy: All labs must be done individually. Discussion of conceptual and implementation aspects is allowed, but you must not copy solutions. Also, please DO NOT post any solutions on the Internet.

Course Material: All relevant materials will be made available online. The course textbook is:

It is important to familiarize yourself with C++ programming early on since all the labs require it. The following tutorial and references are highly recommended:

Additionally, you should be familiar with systems programming. The following online book is highly recommended:

Course VM: All programming labs will be implemented in a VM. See the document titled "Course VM and Lab Instructions" linked from Canvas.

Labs (Homeworks)

Instructions for all labs are available from the Assignments section on Canvas. Some of the labs build upon others. Labs with such dependencies are grouped together. There are three such groups:

Group 1: Dynamic Analysis, Testing, and DebuggingLabs 2, 3, 4, 9, 10
Group 2: Static AnalysisLabs 1, 5, 6
Group 3: Constraint-Solving and ApplicationsLabs 7, 8, 11, 12

There will be a leaderboard competition at the end of the last lab in each group. The leaderboard will target these topics: 1) fuzz testing, 2) bug-finding via static analysis, and 3) assertion verification.

Each lab is due by midnight on the date indicated below. The due dates are tentative and might change slightly due to unanticipated reasons.

Lab # Title Due Date
Lab 0Introduction to LLVMSep 02 (Mon)
Lab 1Simple Static AnalysisSep 10 (Tue)
Lab 2Simple Dynamic AnalysisSep 17 (Tue)
Lab 3Mutational FuzzingSep 24 (Tue)
Lab 4Feedback-Directed FuzzingOct 01 (Tue)
Lab 5Dataflow AnalysisOct 09 (Wed)
Lab 6Pointer AnalysisOct 18 (Fri)
Lab 7Constraint-Based AnalysisOct 28 (Mon)
Lab 8Type InferenceNov 06 (Wed)
Lab 9Statistical DebuggingNov 13 (Wed)
Lab 10Delta DebuggingNov 22 (Fri)
Lab 11Dynamic Symbolic ExecutionDec 01 (Sun)
Lab 12Assertion CheckingDec 11 (Wed)

Lecture Schedule

Date Lesson Slides/Video Reading
Aug 28 (Wed) L1: Introduction to Software Analysis [pdf] [pptx] [video]
Sep 02 (Mon) No lecture - Labor Day
Sep 04 (Wed) L1 contd.
Sep 09 (Mon) L2: Introduction to Software Testing [pdf] [pptx] [video]
Sep 11 (Wed) L2 contd.
Sep 16 (Wed) L3: Random Testing [pdf] [pptx] [video]
Sep 18 (Wed) No lecture (instructor away)
Sep 23 (Mon) L4: Automated Test Generation [pdf] [pptx] [video]
Sep 25 (Wed) L4 contd.
Sep 30 (Mon) L5: Dataflow Analysis [pdf] [pptx] [video]
Oct 02 (Wed) L5 contd.
Oct 07 (Mon) L6: Pointer Analysis [pdf] [pptx] [video]
  • Pointer Analysis, FTPL 2015.
    Modern and comprehensive treatise of pointer analysis abstractions and techniques.
Oct 09 (Wed) TA recitation (instructor away)
Oct 14 (Mon) L7: Constraint-Based Analysis [pdf] [pptx] [video]
Oct 16 (Wed) L7 contd.
Oct 21 (Mon) Guest Lecture: Abstract Interpretation [pdf]
  • The ASTREE Analyzer, ESOP 2005.
    Describes the ASTREE static analyzer and how it is used to verify safety-critical embedded software.
Oct 23 (Wed) Guest Lecture contd.
Oct 28 (Mon) L8: Type Systems [pdf] [pptx] [video]
Oct 30 (Wed) L8 contd.
Nov 04 (Mon) L9: Statistical Debugging [pdf] [pptx] [video]
Nov 06 (Wed) L9 contd.
Nov 11 (Mon) L10: Delta Debugging [pdf] [pptx] [video]
Nov 13 (Wed) L10 contd.
Nov 18 (Mon) L11: Dynamic Symbolic Execution [pdf] [pptx] [video]
Nov 20 (Wed) L11 contd.
Nov 25 (Mon) No lecture - Thanksgiving Break
Nov 27 (Wed) No leture - Thanksgiving Break
Dec 02 (Mon) L12: Assertion Checking via Constraint Solving [CHC demo]
Dec 04 (Wed) L13: Software Model Checking [pdf] [pptx]
Dec 09 (Mon)

Last updated: 2 Sept, 2019