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

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.

The concerns of scalable bug detection and program debugging require innovation from multiple different fronts. As such, this course will cover papers from Software Engineering, Programming Languages, Security, and Systems venues.

Course-level learning goals

• 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.

This is a seminar-style class, which is primarily driven by in-class discussion of a research paper. Each student is expected to submit a response to the paper being discussed in the class 18 hours ahead of the class in which it is discussed. Each student will also serve as discussion lead for 1 paper; the discussion lead will read through other students' responses and prepare questions to start the discussion.

In addition to readings, there will be a programming assignment, 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. The project deliverables include an initial proposal, an in-class presentation of the work, and a final report summarizing what has been achieved.

Grading (Tentative)

• Paper Responses: 20%
• In-class Participation: 10%
• Discussion Lead: 5%
• Assignment: 12.5%
• Project Proposal: 10%
• Project Check-in: 2.5%
• Project Presentation: 10%
• Project Writeup: 30%

Note: this schedule is still subject to change.

You will receive zero on any written submission (paper response, proposal, final write-up) that is found to have plagiarised materials. This includes even a single plagiarized sentence. This includes plagiarism from other students, as well as from other research papers. Refer to this page for more details on the definition of plagiarism, and tips on how to avoid it.

Read each paper to the best of your ability before drafting your paper response. There are two goals to the paper responses:

• Convey your understanding of the paper's core innovations
• Convey your opinion of the paper, in order to spark in-class discussion

• A short paragraph summarizing the paper. What is the problem being tackled? How was it adressed by prior work? What are the innovation(s) proposed in this paper? How are those innovations evaluated?
• Your opinion of the paper, which can be structured in a paragraph or bullet points. Some questions to guide you as you read and write your response:
  • What remains unclear after reading the paper? Are there any clarification questions whose answers would substantially change your opinion of the paper?
  • How does the paper's evaluation match with the proposed problem statement?
  • Do you forsee any barriers to the applicability of the technique proposed in the paper? If so, how could these barriers be overcome?
  • Which technical innovations are most compelling to you?
  • Which problems remain unsolved after this paper?

Paper responses must be submitted to the course Piazza 18 hours before the class on which they are do. Thus, for Monday readings, your paper response should be submitted before 2:30pm on Sunday. For Wednesday readings, they should be submitted before 2:30pm on Tuesday.

Your paper responses will be submitted as follow-up discussions to each paper's post on the course Piazza. You should not read other students' response before writing your own. After posting your response, you may engage with other students' reponses, e.g. answering a clarification question someone else had.

In the assignment, you will design and evaluate a coverage-guided fuzzer for Python. Refer to the assignment webpage for detailed instructions.

The course project constitutes the majority of the course grade. The project is open-ended; the purpose of the project is to give you the opportunity to conduct research in the field of program analysis, debugging, or automated testing. You may pursue the project alone, though I recommend you do it in groups of 2-4; this will give you the opportunity to conduct a project with broader impact.

The scope of acceptable project topics is broad. You are encouraged to find a project with intersects with your own research interests or topic of specialization. But, your project should touch topics in debugging, program analysis, and testing. You may consider a project where you: develop a new tool for testing/analyzing programs in a particular domain, tweak an existing algorithm, conduct an extensive re-evaluation of an existing tool, reimplement an algorithm in a new domain, or create a benchmark suite. If you are not sure if a project is in scope, feel free to set up a meeting with me prior to submitting the project proposal.

Project Ideas Here are some sample project ideas, of varying complexity (some may be better pursued in groups). You need not restrict yourself to these ideas.

• Implement a choice-based backend to JQF in order to make RLCheck Guidance runnable on any arbitrary generator.
• Propose and evaluate a new state/reward framework for RLCheck.
• Run PerfFuzz on a broader benchmark set (i.e. programs not in its evaluation) and evaluate whether the inputs it finds truly represent performance problems.
• Collect a benchmark set of software patches. Evaluate the performance of AFLGo, Hawkeye, or other directed testing tools (e.g. KATCH, SHADOW) on your new benchmark set.
• Develop an algorithm to dynamically infer type signatures from Python calls in order to improve Automated Unit Test Generation that relies on type signatures.
• Study and discuss the links between novelty search and coverage-guided fuzzing. Construct toy benchmarks on which you can evaluate whether conclusions about novelty search also apply to coverage-guided fuzzing.

Deliverables

Proposal. Your project proposal should roughly follow this structure, adapting to the nature of your project (new tool vs. replication vs. benchmark creation):

• Background. What is the problem domain you are investigating? Why is the problem important?
• Intended approach. What, precisely, are you aiming to build or investigate in the project? What precise problem will you be solving?
• Evaluation plan. If you are planning on running an experiment, how many benchmarks will you evaluate on? How long will you run your tool(s)?
• Timeline. Determine a timeline you will follow to achieve your implementation and experimental goals, as well as to deliver the writeup + presentation.

Check-in. The check-in is nearly a month in to the project. It should outline the progress achieved so far. If the timeline's goals have not been reached so far, provide an updated timeline. If, in starting the project, a different research direction has emerged as the more interesting one to follow, the check-in provides a mechanism to update the proposal.

Presentation

Length. For 1-person groups, the presentation should be 12 minutes + 3 minutes for questions. For 2-person groups, the presentation should be 16 minutes + 4 minutes for questions. For 3 or 4-person groups, the presentation should be 25 minutes + 5 minutes for questions.

Contents. The final presentation should convey:

• Background + Motivation Why is this project important?
• Key details of accomplished approach. If you built a tool/algorithm: what are the key contributions of the tool/algorithm you built? If you are conducting an empirical investigation/case study: what methodology did you adopt?
• Evaluation Results + Conlcusion. How did you evaluate your approach? What were the results? What are the high-level takeaways of these results?

Grading. You will be graded on (1) communication effectiveness of the presentation; (2) the ability to answer questions, and (3) for groups, the fair division of the presentation amongst group members.

Writeup.

Length. Your final report should be in ACM format. Use the "sigconf" option, i.e. "\usepackage[sigconf]{acmart}" at the top of your LaTeX source. The report should not exceed 10 pages in this format; however, you may have appendices for additional figures/data. As a rough guideline, aim for at least: 5 pages total; 0.75 pages background/intro; 0.5 pages related work. The exact number of pages and length of each section will depend on the nature of your projects. For instance, projects that are improving an existing tool may spend more time talking about the details of the existing tool and the implementation details of an improvement, than on less-closely-related work.

Contents. Your final writeup should cover the following topics.

• Background. What is the problem domain you are investigating? Why is the problem important?
• Related work. How does your approach compare and contrast with related approaches? Focus only on the details necessary to contextualize your approach in the literature.
• Approach. What, precisely, did you build or investigate in the project?
• Evaluation. What research questions will your evaluation answer? How does your experiment design help answer these questions? What are the results of the experiment, and how do those results inform the research questions?
• Discussion. Discuss any observations on the experiment which do not fit in the main evaluation, any goals that were not achieved, potential room for improvement.
• Division of tasks. If you are working in a group, how did you divide work on the project? Include who wrote different sections of the writeup.

Grading. The final report will be graded on several points, including (not necessarily equally weighted):

• the background provided is sufficient to understand the contribution
• the related work is critically analyzed in order to contextualize the contribution
• the overall project approach (as proposed and updated in the check-in) has been accomplished
• the experimental methodology is sound, the analysis of the experiments has defined takeaways
• the overall clarity of presentation

You will serve as discussion lead for one paper in the class. As a discussion lead, you do not need to submit a response to the paper being read on Piazza. However, you should read the paper in detail, as you will be the "goto" person for clarification questions during discussion. Read through other students' responses, and identify common themes and interesting questions.

• A 5-10 minute summary of the key technical contributions of the paper. You may make a slide deck or use the whiteboard. Caroline will by default project the paper for reference during discussion.
• Identify 3 common themes, future work suggestions, or points of contention from your reading and the other students' responses. Be prepared to briefly explain these to jump-start discussion.
• Identify any clarification questions from your own reading of the paper and other students' reponses.