Delta debugging is a technique for minimizing input files – typically failing test cases, to find a smaller input with the same behavior.
The high-level goal of this exercise is to learn about automated debugging and how to use the delta debugging approach to systematically minimize (“isolate”) failure-inducing inputs.
Your company uses a sorting program named mysort.pl. The
program works most of the time, but a user ran into a problem with it.
In the spirit of following best practices, they provided instructions
with a concrete test case that shows the problem: a file named
failing.txt.
You have been assigned to fix this bug. The source code is unintelligible (it’s written in Perl, after all), so you decide to minimize the test input in hopes of easing the debugging task or giving hints about the underlying defect.
A delta-debugging implementation is provided in the repository. Your
goal in this exercise is to apply delta debugging to the input
failing.txt.
Use a Unix environment (e.g., attu.cs.washington.edu, macOS, or WSL) or git bash for Windows.
Clone the following Git repository: https://bitbucket.org/rjust/delta-debugging (Clone the repository into a directory whose absolute path does not contain any white spaces.)
Read the entire assignment and ask any clarifying questions that you might have.
In the top-level directory (delta-debugging),
run:
perl mysort.pl passing.txt
perl mysort.pl failing.txt (does not terminate; use
ctrl-c to interrupt)
Use delta debugging to minimize failing.txt. Here
are the steps to do so:
mysort.pl.dd-wrapper.sh (in the top level of the
repository) to call your interestingness test script, by replacing the
text “<your test oracle script>” or
“your_interestingness_test_script” by your script’s file
name.dd-wrapper.sh.Hints:
You can write your interestingness test script in any way and any programming language.
The interestingness test script will be run with an input filename as a command-line argument.
What constitutes interestingness for your invocation of delta debugging?
How will your interestingness test script handle the fact that
mysort.pl may not terminate?
The interestingness test script you write must work when run in
any directory. That is, don’t use relative paths (for example, when
calling mysort.pl from within your script). Your
interestingness test script will be run in a a subdirectory like
tmp0/arena/
Documentation of the delta debugging implementation appears in
file delta/doc/using_delta.txt.
This documentation includes an example interestingness test script,
which you can also find in file
delta/test/delta0/hello.test.
If you can’t get your interestingness test script to work within 15 minutes, ask the staff for help and move on.
The minimized test input is stored in file min.txt.
Verify that mysort.pl does not terminate. Using
min.txt, debug and fix the issue in mysort.pl.
(See Questions 1-3 below.)
Hints about Perl:
Here is some basic Perl syntax:
A variable is referenced using a dollar sign $. So,
$x means a use of the variable x.
A field is referenced using ->{fieldname}. So,
$x->{foo} + 1 is like x.foo + 1 in many
other languages.
We know it is frustrating to debug a program in a programming language you don’t know well. (This will happen often in your career!) Don’t panic. You do not need substantial knowledge of Perl in order to fix the defect.
Manually create two test input files that trigger the problem in
the original mysort.pl and that have the following
properties (see Question 4 below) :
both test inputs have four lines;
test input 1 represents the best case scenario – that is, requires the fewest delta-debugging steps.
test input 2 represents the worst case scenario – that is, requires the most delta-debugging steps.
Delta debugging implementations differ in the order in which they evaluate subsets and complements of the input. Validate your test inputs for the provided delta-debugging implementation.
What is the root cause of the bug in
mysort.pl?
Give a one sentence explanation to characterize
all test inputs (input files, or equivalently input
lists) on which mysort.pl fails because of the root cause
in Question 1.
Provide a fix to the bug as a unified
diff (use git diff).
Provide your two four-line test inputs and:
briefly explain why these test inputs are the best and worst case, respectively;
for each test input, list all inputs (subsets and complements) evaluated by the provided delta-debugging implementation (in order of evaluation);
for each test input and corresponding list of evaluated inputs, identify the steps that correspond to “increase granularity”, “reduce to subset”, and “reduce to complement”.
Carefully look at the documentation at
delta/doc/using_delta.txt, and make sure you understand the
example under /delta/test/delta0. Your understanding is
crucial for building your test for this activity.
You do not need to follow the README.md file under
directory delta/; the files are already unzipped and ready
to use. However, note that actual file names are inconsistent with what
has been mentioned in the documentation. in.c should be
hello.c, and testit should be
hello.test.
If you do not want to add delta command to your
path, use ./delta/bin/delta instead, as what
‘dd-wrapper.sh’ does.
You may construct your interestingness test script in any
language, but a bash script is enough for this activity and is arguably
the simplest one. The structure would be similar to the one for the
example provided at delta/test/delta0/hello.test. The
course staff has provided some other information about bash scripting that
you might find helpful for this exercise.
If you encounter issues with permission when executing
./dd-wrapper.sh or running command, for example error
message like
[0,500] 000.csh: /path/to/test_mysort.py: Permission denied,
try to give your test file permission
chmod +x /path/to/your.test.
A plain-text file with your answers to the four questions above. Please list all group members.
The interestingness test script you wrote.
One team member should upload the deliverables to Canvas, via the Canvas submission site for this course.