CIS 700: Software Analysis and Testing (Fall 2018)

[Administrivia] [Syllabus] [Schedule] [Reading] [Project]


Time: Mondays and Wednesdays, 1:30-3:00 pm
Location: LRSM 112B
Instructor: Mayur Naik
Office: Levine 610
Office hours: 2-3 pm Tuesdays (or by appointment)
Xujie Si
Office: Levine 613
Office hours: 3-4 pm Thursdays (or by appointment)

All announcements will be made on Piazza.


Course Overview: Aspects of software development besides programming, such as diagnosing bugs, testing, and debugging, comprise over 50% of development costs. Modern technology has come a long way in aiding programmers with these aspects of development, and at the heart of this technology lies software analysis: a body of work that concerns discovering facts about a given program. Many diverse software analysis approaches exist, each with their own strengths and weaknesses. In this course, you will learn the principles underlying these approaches and gain hands-on experience applying them to automate testing software and finding bugs in complex, real-world programs. Some common examples include:

The course will involve three major concurrent activities:

Course Objectives: Upon successfully completing the course, you will be able to:

Evaluation: Evaluation will be based on four components: homeworks, student presentations, and the project.

Collaboration Policy: Discussing homework solutions is allowed but each individual's submission should be their own.

Prerequisites: The course has two prerequisites:

Course Material: All relevant materials will be made available online. The course textbook is Static Program Analysis by Moeller and Schwartzbach.


Date Lesson Slides/Video Book Chapter(s) Student Presentation Homework Due
Introduction to software analysis/testing. Presents landscape of different techniques, basic concepts, and capabilities/limitations.
Aug 29 (Wed) L1: Introduction to Software Analysis [pdf] [pptx] [video] Ch1, Ch2
Sep 03 (Mon) No lecture - Labor Day Holiday
Sep 05 (Wed) L1 contd. P1 (based on L1) [pdf] [pptx]
Sep 10 (Mon) L2: Introduction to Software Testing [pdf] [pptx] [video] HW1 (Lab: L1 - Racket)
Presents techniques for automated testing in dominant application domains and languages.
Sep 12 (Wed) L3: Random Testing [pdf] [pptx] [video]
Sep 17 (Mon) L4: Automated Test Generation [pdf] [pptx] [video] P2 (based on L3) [pdf] [pptx] [code] HW2 (Lab: L3 - AFL)
Sep 19 (Wed) L4 contd.
Sep 24 (Mon) L5: Differential Testing [pdf] [pptx] HW3 (Lab: L4 - Korat)
Sep 26 (Wed) L5 contd.
Presents building blocks of dataflow analysis. Covers abstractions and algorithms for analyzing structured language constructs.
Oct 01 (Mon) L6: Dataflow Analysis [pdf] [pptx] [video] Ch4, Ch5, Ch6 P3 (based on L5) [pdf] [pptx] HW4 (Lab: L4: Randoop)
Oct 03 (Wed) L6 contd.
Oct 08 (Mon) L7: Pointer Analysis [pdf] [pptx] [video] Ch9 P4 (based on L6) [pdf] [pptx] Project Proposals Due
Oct 10 (Wed) L7 contd.
Oct 15 (Mon) L8: Inter-Procedural Analysis [pdf] Ch7 P5 (based on L7) [pdf] [pptx] [demo files] [demo website]
Oct 17 (Wed) Guest Lecture by Mukund Raghothaman [pdf] [pptx]
Oct 22 (Mon) L8 contd. P6 (based on L8) [pdf] HW5 (Lab: L5 - LLVM)
Oct 24 (Wed) L8 contd.
Presents theoretical foundations of static analysis via topics of constraint-based analysis, type systems, and abstract interpretation.
Oct 26 (Fri) Project Milestone 1
Oct 29 (Mon) L9: Constraint-Based Analysis [pdf] [pptx] [video] Ch8
Oct 31 (Wed) L9 contd. P7 (based on L9) [pdf] [pptx]
Nov 05 (Mon) L10: Type Systems [pdf] [pptx] [video] Ch3
Nov 07 (Wed) L11: Abstract Interpretation [pdf part 1] [pdf part 2] Ch10 HW6 (Lab: L9 - Datalog)
Presents techniques to automate debugging. Covers algorithms for test-input minimization and fault localization.
Nov 09 (Fri) Project Milestone 2
Nov 12 (Mon) L12: Delta Debugging [pdf] [pptx] [video] P8 (based on L10) [demo files] [demo website]
Nov 14 (Wed) L12 contd. P9 (based on L10)
Presents path-sensitive analysis and its incarnation in dynamic symbolic execution and software model checking.
Nov 19 (Mon) L12 contd.
Nov 21 (Wed) No lecture - Thanksgiving Holiday
Nov 26 (Mon) L13: Statistical Debugging [pdf] [pptx] [video] HW7 (Lab: L12 - Delta)
Nov 28 (Wed) L14: Dynamic Symbolic Execution [pdf] [pptx] [video] P10 (based on L12) HW8 (Lab: L13 - CBI)
Nov 30 (Fri) Project Milestone 3
Dec 03 (Mon) L14 contd. P11 (based on L14) HW9 (Lab: L14 - KLEE)
Dec 05 (Wed) Project presentations
Dec 10 (Mon) Project presentations



Project Overview: A hands-on project will span the duration of the course. Students will form teams of upto two and pick a topic in consultation with the instructor. There will be three milestones to provide feedback on each team's progress. Each team will develop their implementation on github and maintain a technical report to be submitted at each milestone. The project will conclude with an in-class presentation by each team at the end of the semester.

Each project must encompass a problem statement, a formal/conceptual formulation of your proposed solution, a realistic implementation, and an experimental evaluation. The project will be evaluated based on creativity, correctness, comprehensiveness, and clarity.

Project Milestones: All project-related deliverables must be submitted through Canvas by midnight on the below dates.

Oct 08Propose project topicProject topic description
Oct 15Finalize project topic
Oct 26Project milestone 1Implementation and report
Nov 09Project milestone 2
Nov 30Project milestone 3
Dec 3, 5, 10In-class project presentationsPresentation slides

Sample Projects: