CIS 700: Software Analysis and Testing (Fall 2018)

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:

• automated source code analysis to help discover entire classes of programming errors in a large application before the code is even executed;
• exploiting the power of randomization to uncover insidious security and concurrency bugs in program runs;
• helping a library developer to automatically generate a test suite that exercises the library's API adequately before publishing it;
• enabling an application developer to leverage the collective power of the deployed application's users in order to uncover the bugs that affect the most users; and
• enabling a QA engineer to automatically reduce a complex crashing test case to help isolate the cause of the crash.

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

Schedule

• L1: Introduction to Software Analysis

  Reading material related to this lesson is organized in three categories:

  Part 1: Introductory articles on program analysis concepts.

  1. What is soundness (in static analysis)? by Michael Hicks.
     Relates soundness/completeness in program analysis to precision/recall and discusses "soundiness".
  2. What is static program analysis? [talk] by Matthew Might.
     Explains why program analysis is undecidable and develops a static analysis to play with in Racket.

  Part 2: Surveys of using program analysis tools in industry.

  1. From Start-ups to Scale-ups: Opportunities and Open Problems for Static and Dynamic Program Analysis, 2018.
     Describes experiences developing and deploying program analysis tools at Facebook.
  2. Lessons from Building Static Analysis Tools at Google, 2018.
     Describes experiences developing and deploying program analysis tools at Google.
  3. What Developers Want and Need from Program Analysis: An Empirical Study, 2016.
     One of the best empirical studies about program analysis.
  4. A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs, 2010.
     Describes experiences applying a commercial static analysis tool by Coverity to large C/C++ programs.
  5. Righting Software, 2004.
     Describes two generations of static analysis tools developed by Microsoft Research.

  Part 3: Consequences and causes of famous software failures.

  1. The Worst Computer Bugs in History: The Ariane 5 Disaster
     Describes famous software bugs including the Ariane Rocket Disaster from the lesson.
  2. The Coming Software Apocalypse
     Overview of the state of software reliability problems and solutions to overcome them.


• L2: Introduction to Software Testing
  1. Pex and Moles
     Unit test generation tools in Visual Studio for .NET programs.
  2. Hints on Test Data Selection: Help for the Practicing Programmer
     Original paper that introduced the idea of mutation testing.
  3. A Theory of Predicate-Complete Test Coverage and Generation [slides]
     Introduces a new code coverage metric based on predicates.


• L3: Random Testing

  Reading material related to this lesson is organized in two categories:

  Part 1: Technical articles on random testing.

  1. A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs, ASPLOS 2010
     Describes fuzz testing in Microsoft's Cuzz tool to find concurrency bugs.
  2. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs, ICFP 2000 [video]
     Describes fuzz testing in the QuickCheck tool to test properties of Haskell programs.
  3. Evaluating Fuzz Testing, CCS 2018 [blog post]
     Describes flaws in past evaluations of fuzz testing and gives guidelines going forward.

  Part 2: Case studies involving random testing.

  1. A Report on Random Testing, ICSE 1981
     Original paper that introduced the idea of random testing.
  2. Webpage describing fuzz testing case studies (1988-2008) by Bart Miller of Univ. of Wisconsin.
  3. A blog post by Google's Project Zero team on fuzz testing popular web browsers' DOM engines.
  4. A talk describing work of the OpenBSD team on using the syzkaller fuzzer to fuzz their kernel.


• L4: Automated Test Generation
  1. Korat: Automated Testing Based on Java Predicates, ISSTA 2002
     Paper that introduced Korat.
  2. Feedback-Directed Random Test Generation, ICSE 2007 [Randoop webpage]
     Paper that introduced Randoop.
  3. Korat vs. Grammar-Based Test Generation by Aalok Thakkar
     Note justifying need for Korat-style search over grammar-based test generation.


• L5: Differential Testing
  1. NEZHA: Efficient Domain-Independent Differential Testing, IEEE S & P 2017 [code] [video]
     A general differential testing approach to find bugs in binaries.
  2. Finding and Understanding Bugs in C Compilers, PLDI 2011 [CSmith]
     Adapts differential testing to find bugs in various C compilers.
  3. DeepXplore: Automated Whitebox Testing of Deep Learning Systems, SOSP 2017 [code] [video]
     Adapts differential testing to find bugs in deep neural networks.


• L7: Pointer Analysis
  1. Pointer Analysis, Foundations and Trends in Programming Languages, 2015
     Recent survey of pointer analysis.


• L8: Inter-Procedural Analysis
  1. Undecidability of Context-Sensitive Data-Dependence Analysis, ACM TOPLAS, 2000
     Proof of undecidability of tracking calls/returns and reads/writes simultaneously.


• L10: Type Systems
  1. Type Systems, CRC Handbook, 2004


• L15: Software Model Checking
  1. Software Model Checking, ACM Computing Surveys, 2009
     Recent survey of software model checking.

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.

• Comparing different industrial static analyzers for finding security vulnerabilities [github link] [presentation]
• A fuzzer for the .NET compiler developed as a project for a 2018 Language-Based Security course at Aarhus University. [github link] [blog post]