CIS 700: Software Analysis and Testing (Fall 2018)

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

Administrivia

Time: Mondays and Wednesdays, 1:30-3:00 pm
Location: LRSM 112B
Instructor: Mayur Naik
Email: mhnaik@cis.upenn.edu
Office: Levine 610
Office hours: 2-3 pm Tuesdays (or by appointment)
Teaching
Assistant:
Xujie Si
Email: xsi@cis.upenn.edu
Office: Levine 613
Office hours: 3-4 pm Thursdays (or by appointment)

All announcements will be made on Piazza.

Syllabus

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.

Schedule

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 Ch7 P5 (based on L7)
Oct 17 (Wed) Guest Lecture by Mukund Raghothaman [pdf] [pptx]
Oct 22 (Mon) L9: Constraint-Based Analysis [pdf] [pptx] [video] Ch8 P6 (based on L8) HW5 (Lab: L5 - LLVM)
Oct 24 (Wed) L9 contd.
Oct 26 (Fri) Project Milestone 1
Presents theoretical foundations of static analysis via topics of constraint-based analysis, type systems, and abstract interpretation.
Oct 29 (Mon) L10: Type Systems [pdf] [pptx] [video] Ch3 P7 (based on L9)
Oct 31 (Wed) L11: Abstract Interpretation [pdf part 1] [pdf part 2]
Nov 05 (Mon) L11 contd. P8 (based on L10) HW6 (Lab: L9 - Datalog)
Presents techniques to automate debugging. Covers algorithms for test-input minimization and fault localization.
Nov 07 (Wed) L12: Delta Debugging [pdf] [pptx] [video]
Nov 09 (Fri) Project Milestone 2
Nov 12 (Mon) L13: Statistical Debugging [pdf] [pptx] [video] P9 (based on L12) HW7 (Lab: L12 - Delta)
Presents path-sensitive analysis and its incarnation in dynamic symbolic execution and software model checking.
Nov 14 (Wed) L14: Dynamic Symbolic Execution [pdf] [pptx] [video]
Nov 19 (Mon) L14 contd. P10 (based on L13) HW8 (Lab: L13 - CBI)
Nov 21 (Wed) No lecture - Thanksgiving Holiday
Nov 26 (Mon) L15: Software Model Checking P11 (based on L14) HW9 (Lab: L14 - KLEE)
Nov 28 (Wed) L15 contd.
Nov 30 (Fri) Project Milestone 3
Dec 03 (Mon) Project presentations P12 (based on L15)
Dec 05 (Wed) Project presentations
Dec 10 (Mon) Project presentations

Reading

Project

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.

WhenWhatDeliverable
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: