|Time:||Mondays and Wednesdays, 1:30-3 pm|
|Location:||Moor Building 212|
Office: Levine 610
Office hours: 2-3 Tuesdays (or by appointment)
Office: Levine 613
Office hours: 3-4 Thursdays (or by appointment)
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.
|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)
|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 & Nov 13||Statistical Debugging||[PPTX] [PDF] [video]|
|Nov 20||Delta Debugging||[PPTX] [PDF] [video]|
|Presents path-sensitive analysis and its incarnation in dynamic symbolic execution and software model checking.|
|Nov 27||Dynamic Symbolic Execution||[PPTX] [PDF] [video]|
|Nov 29||Software Model Checking||[PPTX] [PDF]|
|Presents advanced topics in dataflow analysis with an emphasis on scaling to very large programs.|
|TBD||Inter-Procedural Analysis||[PPTX] [PDF]|
|TBD||Sensitivity & Sparsity in Dataflow Analysis||[PPTX] [PDF]|
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 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 13||Propose project topic||Project topic description|
|Oct 19||Finalize project topic|
|Nov 03||Project milestone 1||Implementation and report|
|Nov 15||Project milestone 2|
|Nov 29||Project milestone 3|
|Dec 4, 6||In-class project presentations||Presentation slides|