CS 6340 Software Analysis Lab 6 Delta
¡ð ¡ð ¡ð ¡ð ¡ð
program fails. A folder called
– skeleton file for you to implement your algorithm in – Program to run and test your program
– first buggy encoder program
– second buggy encoder program
– an input text file on which each buggy encoder
containing the following:
: the correct minimal test input
DeltaDebug.java
DeltaDebugTest.java
SecretCoder
MessageCoder
long_failing_text.txt
Lab 6: Delta
Fall Semester 2022
Due: 21 November, 8:00 a.m. Eastern Time Corresponding Lecture: Lesson 10 (Delta Debugging)
In this lab, you will implement the Delta Debugging algorithm using Java 1.8 (already installed on class VM) to find 1-minimal failing test cases for buggy text encoder programs using both line and character granularity.
1. Delta Debugging webpage: http://www.st.cs.uni-sb.de/dd/
Dr. Zeller, the author of the Delta Debugging technique, and several other people have published implementations of the Delta Debugging algorithm. While we encourage you to research and read more about the algorithm, looking at someone else¡¯s implementation, will almost certainly cause your implementation to be similar to theirs. Therefore, make sure that you do not view or reference any implementations or code of the algorithm.
1. Download delta.zip from Canvas and decompress it. It will produce the directory delta where you should find:
expected_output
[prg]_min_failing_text_line.txt
that should be produced by your Delta Debugging program on SecretCoder (¡°sc¡±) or MessageCoder (¡°mc¡±) for part 1 (line granularity)
¡ö sc_min_failing_text_char.txt: the correct minimal test input that should be produced by your Delta Debugging program on SecretCoder for part 2.
Copyright ý 2022 Georgia Institute of Technology. All Rights Reserved.
2. Each time you change the DeltaDebug.java and DeltaDebugTest.java files, you need to compile the program with:
javac *.java
3. After compiling the files, you may execute the DeltaDebugTest program as follows:
java DeltaDebugTest
Part 1: Line Granularity
Program Description
SecretCoder and MessageCoder implement a Caesar (or shift) cipher with a right shift of 98 places. Instead of the regular alphabet, these programs are intended to encode the 128 characters in the ASCII character set (value 0 to 127). When the programs run successfully, they will print out a message that indicates the program executed successfully.
The programs can be executed directly in the command line, followed by a single input that is the path to the input file, as shown below:
./SecretCoder
Note: In the VM, you may need to change the access mode of the executables in order to run them:
chmod +x
Problem Summary
The bug in SecretCoder occurs when long_failing_text.txt contains a non-ASCII character. The program is using the UTF-8 character set to determine the number of characters in the file and creates a char array to store the encoded values for printing. It does not take into account that non-ASCII characters in the UTF-8 character set could be included into the file and these will take up more than one byte. When a non-ASCII character is read into the file as two or more bytes, the char array runs out of room and throws a java.lang.ArrayIndexOutOfBoundsException.
is able to handle all characters, but the bug in the encoding program
occurs when long_failing_text.txt contains a specific pattern: a four-letter pattern of alternating caps starting with a capital letter (e.g. ¡°JaVa¡±, or ¡°HaHa¡±). When this pattern is detected, the following exception occurs: java.lang.IllegalArgumentException
Your task is to implement the delta debugging algorithm presented in the lecture to obtain the minimal test case on which SecretCoder fails for
MessageCoder
MessageCoder
Copyright ý 2022 Georgia Institute of Technology. All Rights Reserved.
and the minimal test case on which fails for . In your
implementation, do not hardcode the program names and error messages. Your program should be able to run for a program of any name and any error message.
To accomplish this task, we have provided a framework and you will need to implement the deltaDebug method in . For part one of the lab, we will use line granularity. We have provided a program that you can use to run DeltaDebug to test your changes.
Note that DeltaDebugTest will call the deltaDebug method in DeltaDebug.java, which requires 5 parameters:
¡ñ char_granularity – If false, implement line granularity only
¡ñ program – this is the path to the program being tested
¡ñ failing_file – this is the path to the file with the large failing test case
¡ñ error_msg – this is the error message that will be used to determine if the program is
failing for the same reason as the original file or not
¡ñ final_minimized_file – this is the name of the final file that your program should print
with the minimized input.
Similarly, the grading script will call the deltaDebug method directly in DeltaDebug.java. Therefore, it is very important that you do not make any changes to the type or method signature of deltaDebug in DeltaDebug.java.
Ensure you are using the failing_file and final_minimized_file parameters for your file names in DeltaDebug.java instead of hardcoding files because the grader will be using additional files besides the ones provided in this lab.
We have provided an outline for some helper methods in DeltaDebug.java that you may find useful (there are comments in the code to explain what these do). You can modify these methods or add new helper methods in in any way you see fit as long as your algorithm is invoked by calling with the original parameters. As a warning, since there are test cases looking for exact text matches, it is in your best interest to keep changes to the writeToFile() method minimal since the method appends a new line at the end of the file by design; the grader will be expecting this new line.
java.lang.ArrayIndexOutOfBoundsException
MessageCoder
java.lang.IllegalArgumentException
DeltaDebug.java
DeltaDebugTest
deltaDebug(Boolean char_granularity, String program,
String failing_file, String error_msg,
String final_minimized_file)
DeltaDebug.java
deltaDebug
Copyright ý 2022 Georgia Institute of Technology. All Rights Reserved.
Github
If the deltaDebug is written correctly, executing the test program will create a 1-minimal test case text file (named by your variable). The contents should be identical to the provided expected when running the algorithm with line-granularity.
You may verify the files are identical (including whitespace & new lines) using the diff command (replace ¡®prg¡¯ with ¡®mc¡¯ or ¡®sc¡¯ depending on which files you are comparing): diff my_min_failing_text_line.txt [prg]_min_failing_text_line.txt
For grading, we will also be testing your algorithm on hidden input files. For this section, we are looking for an exact text match since the test cases will have at most 1 line with a failing character or pattern. The hidden test cases will be similar in format to the provided one, but will have a different file name, different number of lines, different failing character or pattern, different position for failing character or pattern, or other changes appropriate for a text file. You can assume that there will be a single failing character or pattern in the file. We encourage you to come up with different inputs to test how your algorithm handles different cases.
Your algorithm should run in less than 3 minutes on the course VM.
If you add print statements for debugging, make sure to remove these before submission.
Part 2: Character Granularity
Now you will extend your algorithm to perform minimization at the character granularity level when the flag is set. Make sure to minimize the file by lines as much as possible, and then switch to character granularity when line granularity has reached its minimum.
If the deltaDebug is written correctly, executing the test program will create a 1-minimal test case text file (named by your final_minimized_file variable). The 1-minimal failing test case for should be identical to the provided
, and you can verify with diff. Due to the nature of the failure in , we are expecting an exact text match.
The 1-minimal failing test case for MessageCoder will vary depending on the partition strategy implemented in your method, so there will not be an exact text matching for this portion. The grading criteria for these test cases is as follows:
¡ñ The final minimized text must be a subsequence of your output from the line-granularity of MessageCoder, or else no credit. This means if your line-granularity was
SecretCoder
final_minimized_file
[prg]_min_failing_text_line.txt
sc_min_failing_text_char.txt
SecretCoder
Copyright ý 2022 Georgia Institute of Technology. All Rights Reserved.
Code Help
¡°abcdefgh¡±, your char-granularity can be ¡°acg¡±, but it cannot be ¡°gah¡±. The characters must be found in the same order as it appears in the original string. The algorithm for delta handles this implicitly, so if your output is not a proper subsequence, something is wrong with your algorithm.
¡ñ The char-granularity output must also fail when passed into the buggy encoder program, or else no credit. If you run the program with your char-granularity output, you should still get the failure. This means that at minimum, there should be some upper-lower-upper-lower pattern in your output.
¡ñ The output is 1-minimal, which means that you cannot refine your granularity any further. Removal of any single character will result in a non-failing input.
If your output meets all three criteria, full credit for that test case will be awarded. Partial credit will be awarded if and only if you meet the first 2 criteria but not the last criteria.
The same grading notes and 3 minute timeout limit apply as in part 1.
Items to Submit
Submit the following file into Gradescope.
¡ñ DeltaDebug.java
Make sure the spelling of the filenames and the extensions are exactly as indicated above. Misspellings in filenames may result in a deduction to your grade. Also double-check that you are not accidentally submitting DeltaDebugTest.java.
MessageCoder
java.lang.IllegalArgumentException
Copyright ý 2022 Georgia Institute of Technology. All Rights Reserved.
¡ñ 8% of grade: For
¡ñ 12% of grade: For
¡ñ 30% of grade: Other test cases
¡ñ 8% of grade: For
¡ñ 12% of grade: For
SecretCoder
, correctly minimizes correctly minimizes
, correctly minimizes
, correctly minimizes to some reduced failing text.
DeltaDebug.java
long_failing_text.txt
sc_min_failing_test_case_line.txt
MessageCoder
DeltaDebug.java
long_failing_text.txt
mc_min_failing_test_case_line.txt
SecretCoder
DeltaDebug.java
long_failing_text.txt
sc_min_failing_test_case_char.txt
MessageCoder
DeltaDebug.java
long_failing_text.txt
¡ñ 30% of grade: Other test cases How Do We Use It?
Delta Debugging is an expanded binary search. There are multiple implementations available for most common programming languages. Researchers have even extended the technique into test case minimization. Even without implementing the technique in code, it can be used to help quickly diagnose problems with failing inputs in cases where the error messages available do not provide sufficient information for isolating issues. For example, it is possible to debug a program that reads in multiple records and does not give status on how many succeeded when it fails by using a Delta Debugging-influenced technique to isolate a failing record.
Note: Every semester, we have students asking if they can implement binary search. The point of this lab is to learn how to implement Delta Debugging, which is not binary search. However, we will not penalize you for using binary search for the line granularity portion of this lab, but you will not be able to use binary search for char granularity. Ultimately, it is up to you whether you want to implement only one algorithm that will work for both parts as long as you build sufficient flexibility into it, or two separate algorithms.
Note that binary search only works for line granularity because we promise that the failure condition will be contained within a single line. If we allowed the failure across multiple lines as we allow for a multiple character failure, you would need to use the Delta Debugging algorithm to get correct results.
Copyright ý 2022 Georgia Institute of Technology. All Rights Reserved.
CS Help, Email: tutorcs@163.com