CIS 700: Software Analysis and Testing (Fall 2017)

[Recent News] [Logistics] [Syllabus] [Schedule] [Homeworks] [Project]

Recent News

Logistics

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

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.

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

Evaluation: Evaluation will be based on three components: homeworks, two in-class exams, and a project. Exams will be based only on material covered in the lectures and will be open lecture slides/notes.

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

Prerequisites: The course has two prerequisites:

Course Material: There is no required textbook; all relevant materials will be made available online.

Schedule

Note: This is a tentative list subject to revision!

Date Topic Notes
Introduction to software analysis and software testing. Presents landscape of different techniques, introduces basic concepts, and discusses capabilities and limitations.
Sep 06 Introduction to Software Analysis [PPTX] [PDF] [video]
Sep 11 Introduction to Software Testing [PPTX] [PDF] [video]
Presents techniques for automated testing in important application domains (mobile and multi-threaded applications) and languages (object-oriented and functional).
Sep 13 Random Testing [PPTX] [PDF] [video]
Sep 18 & Sep 29 Automated Test Generation [PPTX] [PDF] [video]
Sep 27 Property-Based Testing
(Guest lecture by John Hughes)
[PDF]
Presents building blocks of dataflow analysis. Covers abstractions and algorithms for analyzing structured language constructs, primitive data, and objects.
Sep 25 & Oct 02 Dataflow Analysis [PPTX] [PDF] [video]
Oct 04 & Oct 11 Pointer Analysis [PPTX] [PDF] [video]
Nov 01 Type-State Analysis [PPTX] [PDF]
Presents theoretical foundations of static analysis. Introduces topics of constraint-based analysis, type-based analysis, and abstract interpretation.
Oct 18 & Oct 30 Constraint-Based Analysis [PPTX] [PDF] [video]
Oct 23 Abstract Interpretation (Part 1) [PDF]
Oct 25 Abstract Interpretation (Part 2) [PDF]
Nov 06 Type Systems [PPTX] [PDF] [video]
Presents techniques to automate debugging. Covers algorithms for statistical debugging, fault localization, and performance debugging.
Nov 08 Statistical Debugging [PPTX] [PDF] [video]
Nov 13 Delta Debugging [PPTX] [PDF] [video]
Presents path-sensitive analysis and its incarnation in dynamic symbolic execution and software model checking.
Nov 15 Dynamic Symbolic Execution [PPTX] [PDF] [video]
Nov 20 Software Model Checking [PPTX] [PDF]
Presents advanced topics in dataflow analysis with an emphasis on scaling to very large programs.
Nov 27 Inter-Procedural Analysis [PPTX] [PDF]
Nov 29 Sensitivity & Sparsity in Dataflow Analysis [PPTX] [PDF]

Homeworks

Homeworks will be of four kinds: (1) reading technical papers and writing reviews; (2) solving practice questions for exams (3) applying software analyis/testing tools and reporting your findings; and (4) implementing software analysis/testing algorithms.

Homeworks will be published on Canvas and solutions should be submitted through Canvas.

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 13Propose project topicProject topic description
Oct 19Finalize project topic
Nov 03Project milestone 1Implementation and report
Nov 15Project milestone 2
Nov 29Project milestone 3
Dec 4, 6In-class project presentationsPresentation slides

Relevant Materials