“Program Analysis for Software Testing”

Fall 2017: Mondays, 4:30pm-7:10pm, Room 2026 Art and Design

Instructor: Prof. Jonathan Bell
Email: [email protected]
Twitter: @_jon_bell_
Office: 4422 Engineering Building; (703) 993-6089
Office Hours: Anytime electronically, Mondays 3:30-4:30pm, or by appointment

Contacting:

Please post on Piazza for course-related inquiries.

Pre-Requisites:

Students are required to have previously taken a compilers course (E.g. CS 540) OR a testing class (e.g. SWE 637) OR special permission from the instructor to take this class. This class also assumes working knowledge of programming in Java and C/C++ (although most assignments will use Java). Students must also have working understanding of UNIX shell environments. For CS MS students, this course will count towards the Programming Languages/Software Engineering Requirement.

Objectives:

Learn different methods for analyzing software, with several applications in software engineering, particularly testing. We will study different analysis techniques, learn how they work by studying specific algorithms and tools, and discuss applications of the techniques. Our goal will be to explore the current research issues in this cutting edge area, to learn how to build software analysis tools, and to understand how these techniques can be applied to software development activities.

We will primarily focus on applications for testing software, including automatic test data generation. We will also consider using analysis techniques for other software related activities such as maintenance, reuse, metrics, and optimization. Some of the specific analysis techniques to be studied are parsing, software representation methods (control flow graphs, data flow graphs, program dependency graphs), symbolic evaluation, constraints, program slicing, software coupling, and testability.

While we will consider analyses in various languages (e.g. applying to native x86 binaries, Java and JavaScript), there will be a particular emphasis towards Java analysis. Students will complete a research project involving dynamic analysis of Java applications.

Intended Audience:

This graduate-level course is intended for students in a MS degree program or in a PhD program. This course is intended for students who would like to become more productive software engineers in industry by applying analysis tools.

This is also intended for research-focused students who would like to prepare for research in programming languages, compilers or software engineering, or would like to prepare for research in other areas of computer science (E.g., security or systems) that involve applying software analysis and testing.

Learning Outcomes:

• Understand the abstract properties of different techniques for analyzing and testing software.
• Compute the outcome of these techniques on concrete code examples.
• Evaluate the suitability of different techniques for a given software and/or set of constraints.
• Run analysis and testing tools on actual software and interpret their results to improve the quality of their code.

Term Project:

This seminar-style class will include a term project, worth 50% of your grade. The project will involve a hands-on application of the techniques and tools that we discuss in class, and can be completed either individually or in a group of at most two. Topics for the project will be discussed in the first three weeks of class, and your specific project topic will be finalized on October 2nd. At a high level, project topics will include two tracks:

1. Research track: These projects are intended for students interested in pushing the state-of-the-art in program analysis and software testing tools. These projects will involve creating a prototype tool that implements some new concept. Example research projects might include: extending Phosphor or optimizing or enhancing EvoSuite. If you would like to create a formal writeup of your research project, most of these projects will be suitable for publication in an academic workshop.
2. Industry track: These projects are intended primarily for students who are interested in honing their programming and software engineering skills, by taking a state-of-the-art idea, and transitioning it to the state-of-practice. These projects will involve taking some idea that we talk about in class and implementing it in a popular tool, for instance, improving the flaky test detector built into Maven, optimizing the JaCoCo coverage tool, or hacking on the regression test selection system in Clover. These projects are intended to be of sufficient quality that you can submit a pull request to have your changes included in the open source tool. Think about next time you are on an interview and you are asked if you are familiar with (insert name of tool here), and you can say “Oh yes, and I have contributed code that made its way in to X.“

Required Materials:

There is no required textbook for this class. Weekly readings will involve academic papers, which will be made available online. To complete the homeworks and project successfully, students will need access to a computer capable of running virtualization technology (e.g. VirtualBox).

Grading:

30% Homework
10% Reading writeups
50% Final Project
5% Participation
5% Labs

Reading Writeups

Most classes have readings assigned. You will need to submit a reading writeup for each paper specified. Each writeup should be at most half of one page, and contain:

1. Choose one good thing about the paper (e.g. problem, solution or evaluation) and describe why you find it good
2. Choose one bad thing  about the paper (e.g. problem, solution or evaluation) and describe why you find it good
3. List one question that you’d like to ask about the paper in class
4. Optionally describe how the paper relates to your course project

Submit your reading writeup by emailing it to me.

Homework policy

Students must work individually on all homework assignments. We encourage you to have high-level discussions with other students in the class about the assignments, however, we require that when you turn in an assignment, it is only your work. That is, copying any part of another student’s assignment is strictly prohibited. You are free to reuse small snippets of example code found on the Internet (e.g. via StackOverflow) provided that it is attributed. If you are concerned that by reusing and attributing that copied code it may appear that you didn’t complete the assignment yourself, then please raise a discussion with the instructor.

10% will be deducted for late HW assignments and late HW assignments will only be accepted for 24 hours after the due date. HW assignments submitted more than 24 hours late will receive a zero. If you’re worried about being busy around the time of a HW submission, please plan ahead and get started early. Homework that does not compile or run will receive at most 50% credit.

For fairness to all, there are no exceptions to the above rules.

In Class Activities:

Most lectures will feature interactive activities that support the material being presented. You are strongly encouraged to bring your laptop to class so that you can participate. Your 5% participation grade is based on attendance and participation in in-class activities.

Schedule (subject to change):

Date	Topic	Reading (read before class)	Additional references
8/28	1. Introduction to program analysis; course overview; Lab: Java bytecode instrumentation HW1 out, due 9/5	Bring your laptop so you can complete the lab in class.	Slides (PDF, Keynote), ASM API, ASM Manual, JVM Spec
9/4	(No class) labor day
9/5	HW1 due. (No class) last day to drop class with no financial penalty
9/11	2. Dynamic dataflow analysis and taint tracking Lab: Phosphor HW2 out, due 9/18 Submit a writeup for Phosphor, DyTAN	Phosphor, DyTAN	Slides (PDF, Keynote), Phosphor GitHub
9/18	3. Model Checking & Dynamic Symbolic Execution HW2 due; HW3 out, due 9/25 Discuss project ideas Submit a writeup for EXE	JPF, EXE	No slides (wrote on whiteboard)
9/25	4. Flaky Tests Preliminary Project Proposal due 10/2	Deflaker, Does Refactoring of Test Smells Induce Fixing Flaky Tests?
10/2	5. Change Impact Analysis and Fault Repair Discuss preliminary project proposals. Project Proposal Due 10/10	Chianti, Tarrantula, FaultTracer (suggested in that order)
10/10 (Note: TUESDAY)	6. More Symbolic Execution Discuss project proposals. Final project proposal is due.	KLEE, SAGE
10/16	7. More Test Generation	RANDOOP, EvoSuite
10/23	OOPSLA (no class)
10/30	8. Mid-Project Presentations
11/6	9. More Fault Localization & Defects4J	Mutant effectiveness,  Evaluating and improving fault localization
11/13	10. Test Dependencies	VMVM, DTDetector
11/20	11. Test Coverage and Selection	Empirical Study of Test Suite Reduction , Ekstazi
11/27	12.  Performance Testing & Analysis	Kraken, Canopy
12/4	13. Debugging	Delta Debugging, Rx
12/11	(No class during study period)
12/18	Project presentations (during exam time, normal room)

Here’s a list of great papers that we haven’t gotten to fit on the schedule:

Hybrid Race Detection, RV-Predict, Rx, CROCHET

Honor Code:

GMU is an Honor Code university; please see the Office for Academic Integrity for a full description of the code and the honor committee process, and the Computer Science Department’s Honor Code Policies regarding programming assignments. The principle of academic integrity is taken very seriously and violations are treated gravely. What does academic integrity mean in this course? Essentially this: when you are responsible for a task, you will perform that task. When you rely on someone else’s work in an aspect of the performance of that task, you will give full credit in the proper, accepted form. Another aspect of academic integrity is the free play of ideas. Vigorous discussion and debate are encouraged in this course, with the firm expectation that all aspects of the class will be conducted with civility and respect for differing ideas, perspectives, and traditions. When in doubt (of any kind) please ask for guidance and clarification.

Accommodations for Disabilities:

If you have a documented learning disability or other condition that may affect academic performance you should: 1) make sure this documentation is on file with Office for Disability Services (SUB I, Rm. 4205; 993-2474; http://ods.gmu.edu) to determine the accommodations you need; and 2) talk with me to discuss your accommodation needs.

Privacy:

Students must use their MasonLIVE email account to receive important University information, including messages related to this class. See http://masonlive.gmu.edu for more information.