Topics in Programming Languages: Automated Testing, Bug Detection, and Program Analysis

Topics in Programming Languages: Automated Testing, Bug Detection, and Program Analysis

CPSC 539L, Winter Term 1 2022, Instructor: Caroline Lemieux (clemieux@cs.ubc.ca)

Mon/Wed 10:30AM-12:00PM, DMP 101, UBC course page


(05/27) This webpage is under construction; syllabus and grading scheme are subject to change.

Course description

Software bugs remain pervasive in modern software systems. As software becomes increasingly intertwined in all aspects of our lives, the consequences of these bugs become increasingly severe. For instance, since the mid 2010s, several important security vulnerabilities have emerged from basic correctness bugs in software (e.g. Heartbleed, Cloudbleed, Shellshock ). Though not all bugs cause important security vulnerabilities, their overall cost remains high: one estimate puts the cost of dealing with software failures and defects in the United States alone in 2018 at nearly USD$1,540,000,000---the worldwide impact of these defects is even more severe.

While human-written tests are a prevailing method for assuring the quality of software in practice, they are still subject to human error, and allowing bugs to slip through the cracks that the human tester did not consider. This class will explore topics in the field of automated testing, which aims, at a high-level, to reduce the developer burden in discovering bugs and writing test cases. Recent advances in this field leverage static and dynamic information from the program under test in order to effectively explore the space of behaviors of the program under test, enabling the quick discovery of potentially severe security bugs.

Course-level learning goals

The course will provide an opportunity for participants to:
  • Become familiar with key techniques used in automated testing tools (including concolic execution, coverage-guided fuzz testing, search-based algorithms);
  • Critically evaluate research papers in the field of program testing and analysis;
  • Program automated testing tools in Python;
  • Design and conduct experimental evaluation of a program testing or analysis tool.

Format

This is a seminar-style class, which is primarily driven by in-class discussion of papers (1-2 per class). Each student is expected to submit an evaluation of the paper(s) being discussed in the class ahead of the class in which it is discussed. Each student will also serve as discussion lead for 1-2 papers, depending on class enrolment; the discussion lead will read through other student's responses and prepare questions to start the discussion.

In addition to readings, there will be one or two programming assignments, which will give you the opportunity to implement and evaluate some of the test generation algorithms we will explore in papers.

The bulk of your course mark will come from an open-ended course project. The project can be conducted as part of a team. I will provide suggestions for a few potential projects early in the semester, or you can propose a project close to your interests that intersects with topics in debugging, program analysis, and testing. The project deliverables include an initial proposal, an in-class presentation of the work, and a final report summarizing what has been achieved.

The scope of acceptable projects is broad; developing a new tool for testing in a particular domain, tweaking an existing algorithm, an extensive re-evaluation of an existing tool, or reimplementation of an algorithm in a new domain. The projects should involve an empirical experimental component. Feel free to set up a meeting with me prior to the inital proposal stage.

Schedule (Tentative)

Note: this section will be populated with an exact list of papers closer to the start of the semester.

Time permitting, we will cover the following topics:

  • Symbolic/Concolic Execution
  • Coverage-Guided Greybox Fuzzing
  • Property-Based Testing (a.k.a. Generator Based Fuzzing)
  • Test Suite Generation Techniques
  • Delta Debugging
  • Concurrency Testing
  • Input Structure Inference
  • Scalability of the above techniques

This course is loosely based off of Koushik Sen's 2016 offering of CS 294-15.