A program that triggers a bug in a compiler, interpreter, or other language processor often contains code that is irrelevant for the bug. Such irrelevant code often complicates the debugging, because it can conceal the root cause of the bug. Automated test case reduction techniques try to remove as much of this irrelevant code as possible to help the developers in debugging.
This repository contains efficient implementations of the most important (language-agnostic, syntactical) test case reduction techniques from the scientific literature and is also meant to serve as a basis for the development of future techniques. It accompanies the research paper "P. Kreutzer, T. Kunze, M. Philippsen: Test Case Reduction: A Framework, Benchmark, and Comparative Study" published at ICSME'21, but is also meant to be used for practical purposes.
The input format of a test case is specified by means of a Parsing Expression Grammar (PEG). The respective parser is constructed "on the fly" during runtime (i.e., there is no need to translate the grammar beforehand). This reduces dependencies and should simplify the use of RedPEG in practice.
The RedPEG framework contains implementations of the following test case reduction techniques published in the scientific literature:
- Zeller, A., Hildebrandt, R.: Simplifying and Isolating Failure-Inducing Input. In: IEEE Transactions on Software Engineering. 28(2) (Feb. 2002) 183–200.
- Misherghi, G., Su, Z.: HDD: Hierarchical Delta Debugging. In: ICSE’06: International Conference on Software Engineering (Shanghai, China, May 2006), 142–151.
- Hodován, R., Kiss, A., Gyimóthy, T.: Coarse Hierarchical Delta Debugging. In: ICSME’17: International Conference on Software Maintenance and Evolution (Shanghai, China, Sep. 2017), 194–203.
- Herfert, S., Patra, J., Pradel, M.: Automatically Reducing Tree-Structured Test Inputs. In: ASE’17: International Conference on Automated Software Engineering (Urbana-Champaign, IL, Oct. 2017), 861–871.
- Sun, C., Li, Y., Zhang, Q., Gu, T., Su, Z.: Perses: Syntax-Guided Program Reduction. In: ICSE’18: International Conference on Software Engineering (Gothenburg, Sweden, May 2018), 361–371.
- Gharachorlu, G., Sumner, N.: Avoiding the Familiar to Speed Up Test Case Reduction. In: QRS’18: International Conference on Software Quality, Reliability and Security (Lisbon, Portugal, Jul. 2018), 426–437.
- Kiss, Á., Hodován, R., Gyimóthy, T.: HDDr: A Recursive Variant of the Hierarchical Delta Debugging Algorithm. In: A-TEST’18: Automating Test Case Design, Selection, and Evaluation (Lake Buena Vista, FL, Nov. 2018), 16–22.
- Gharachorlu, G., Sumner, N.: Pardis: Priority Aware Test Case Reduction. In: FASE’19: Fundamental Approaches to Software Engineering (Prague, Czech Republic, Apr. 2019), 409–426.
If you want to cite RedPEG, please cite our ICSME'21 research paper:
- Kreutzer, P., Kunze, T., Philippsen, M.: Test Case Reduction: A Framework, Benchmark, and Comparative Study. In: ICSME'21: International Conference on Software Maintenance and Evolution (Virtual, Luxembourg, Sep. 2021), 58–69.
We use our own parser implementation to convert an input program to its syntax tree (this allowed us to design the syntax trees in a way that supports all examined reducers). Since this parser implementation might also be valuable in other contexts, we moved all code related to parsing to its own library called j-PEG, which RedPEG includes as a Git submodule. Use one of the following ways to correctly set up this submodule:
- When cloning the RedPEG repository, add the command line option
--recurse-submodules. - If you already cloned the RedPEG repository without the aforementioned command line option,
simply type
git submodule update --initto set up the submodule.
When the submodule is correctly set up, simply type ./gradlew build in the root directory of the
RedPEG repository to build the RedPEG framework. After a successful build, there should be a
file build/libs/RedPEG.jar. The instructions below assume that this file exists.
Note:
- You need a working JDK installation to build and run RedPEG (tested with OpenJDK 8 and 11).
- Building RedPEG requires an internet connection to resolve external dependencies.
Once RedPEG has been built successfully (see above), you can run the following example to check if everything works correctly.
Assume that the C program in example/program.c provokes a bug in a C compiler, which is triggered
when a single statement uses the two literal numbers 13 and 3 (a really contrived example).
Further assume that the bug is only triggered if the input program is statically valid (i.e., if it
passes all analyses in the front end of the compiler). (Note: this program has been generated with
the StarSmith compiler fuzzer.)
The test script example/test.sh simulates this "bug" and tells RedPEG whether a reduction
candidate still triggers the bug. It first calls gcc to check if the given reduction candidate is
compilable, i.e., if it is still statically valid (note: this requires a (more or less arbitrary)
version of gcc in the search path). If the candidate is not compilable, the test script returns
with the exit code 0 to signal that the bug is not triggered. If, however, the candidate is
compilable, the test script uses grep to check if there is still a statement that uses the
literals 13 and 3. If there is such a statement, the test script returns with exit code 1 to
signal that the bug has been triggered.
To check that the original program in example/program.c really triggers the "bug", you can run the
following command and check that it returns with exit code 1:
./example/test.sh ./example/program.c
echo $?
To reduce the example program to a smaller one that still triggers the "bug", run the following:
./run.sh \
--grammar grammars/c.txt \
--in example/program.c \
--test example/test.sh \
--reduce 'Perses*' \
--outDir example/reduced \
--cache
This example reduction should only take few seconds, after which the final reduction result can be
found in example/reduced/program.reduced.c:
main(void) {13 |3;
}
In short, the following command line options are used in this example:
--grammar: Path to a PEG that describes the input format of the program that should be reduced. This option is required.--in: Path to the program that should be reduced. This option is required.--test: Path to the test function that checks whether a reduction candidate still triggers the bug. This option is required.--reduce: The reducer that should be used.Perses*is the fixpoint variant of the highly effective Perses reducer by Sun et al. This option is required.--outDir: The directory to which the reduction result (and all temporary reduction candidates) should be written to.--cache: Enables test outcome caching to avoid unnecessary evaluations of the test script. Caching usually accelerates the reduction, but might require a lot of memory.
The following sections give more details on how to use RedPEG and what command line options it offers.
The input format of a test case is specified by means of a Parsing Expression Grammar (PEG). For example, consider the following grammar:
calculation: statement* EOF ;
statement: ( VAR_NAME ASSIGN )? expression SEMICOLON ;
expression: add_expression ;
add_expression: mul_expression ( ( ADD | SUB ) mul_expression )* ;
mul_expression: factor ( ( MUL | DIV ) factor )* ;
factor
: NUM
| VAR_NAME
| LPAREN expression RPAREN
;
ASSIGN: ':=';
SEMICOLON: ';';
ADD: '+';
SUB: '-';
MUL: '*';
DIV: '/';
LPAREN: '(';
RPAREN: ')';
@skip
SPACE: ( ' ' | '\n' | '\r' | '\t' )+ ;
NUM: '0' | ( [1-9][0-9]* ) ;
VAR_NAME: [a-zA-Z] [a-zA-Z0-9]* ;
This grammar matches programs of the following form:
foo := (13 + 3) * 12;
11 + foo;
The names of lexer rules consist of upper case letters (e.g., ASSIGN or SPACE).
The right hand side of a lexer rule consists of a single regular expression (please refer to the example above for the exact notation).
If a lexer rule is annotated with @skip (e.g., the SPACE rule from above), its matches are
discarded (i.e., its matches do not appear as tokens in the token stream).
The implicitly defined EOF rule matches the end of the input.
The names of parser rules consist of lower case letters (e.g., calculation or statement). The
first parser rule becomes the parser's start rule.
The right hand side of a parser rule uses a notation similar to that of EBNF:
*means zero or more repetitions+means one or more repetitions?means zero or one occurrences
Use the choice operator | to specify alternatives. Note: In contrast to "traditional"
context-free grammars in EBNF, the choice operator of PEGs is ordered. Thus, if the first
alternative matches, the second one is ignored. For example, a rule foo: A | A B; only ever
matches A tokens (but you can swap the alternatives so that the parser first tries to match A B).
Since the input PEG is converted to a recursive top-down parser, left recursive rules may lead to an infinite recursion. We provide experimental support for directly left recursive rules, but this has not been fully tested yet. Indirectly left recursive rules are currently not supported.
It is possible to annotate the rules for terminals and non-terminals in a PEG with one or more annotations, and these annotations might optionally carry an (integer or string) argument:
@some_annotation
foo: ... ;
@int_annotation(13)
@string_annotation("value")
bar: ... ;
Nodes in the syntax tree (see below) that belong to such an annotated definition carry these annotations (and their optional values) for further processing.
An input grammar induces a bipartite graph that we call "grammar graph". Its nodes either represent alternatives (so-called alternative nodes) or sequences (so-called sequence nodes). Each alternative node has outgoing edges to all its alternative sequences; each sequence node has outgoing edges to all alternatives that the sequence consists of.
To show a graphical representation of a grammar graph, use the following:
./run.sh --in path/to/test_case --grammar path/to/grammar --printGG | dot -Tx11
This requires the dot tool from the Graphviz package.
Note: The grammar graph is independent from a concrete input test case. However, the command line interface currently requires the specification of an input test case (this may be fixed in a later version).
Most reduction algorithms work on the syntax tree of the input test case (which is induced by the input grammar). To control the shape of the syntax tree, the following command line options are supported:
--omitQuantifiers: By default, quantifiers in the grammar rules (i.e.,*,+, and?) lead to quantifier nodes in the syntax tree. For example, if a*-ed sub-rule is matched, a*-node is added to the syntax tree. Its children areITEMnodes, one for each repetition. Most of the provided reduction algorithms use these quantifier nodes to detect list structures in the syntax tree. By specifying the--omitQuantifiersoption, quantifier andITEMnodes are omitted.--noCompactify: For certain grammars and inputs, the respective syntax trees may contain long "chains" of nodes (i.e., nodes that only have a single child node). By default, these chains are "squeezed". This reduces the number of nodes in the syntax tree and, in general, improves the efficiency of the reduction algorithms. Specifying--noCompactifydisables this behavior (this is not recommended for typical use cases!).
To show a graphical representation of the input test case's syntax tree, use the following:
./run.sh --in path/to/test_case --grammar path/to/grammar --toDot | dot -Tx11
This requires the dot tool from the Graphviz package.
Use the --treeStats command line option to print statistics for the input test case's syntax tree.
Some of the reduction algorithms (e.g., HDD) delete nodes from the syntax tree and replace them with
minimal textual replacements. By default, these replacements are automatically computed from the
input grammar. Use the --printReplacements option to print these replacements.
In certain cases, it might be favorable to specify the replacements for some grammar rules manually.
For example, the automatically computed minimal replacement for the expression rule from our
example grammar may be the string a (a variable name). If there is no variable named a in the
input test case, this replacement may lead to many semantically invalid reduction candidates and
hence hamper the reduction. Instead, replacing expressions with 0s may lead to more efficient
and effective reductions. To manually specify this replacement, create a file with the following
content:
expression: "0";
Use the --replacements option and provide the path to this file as argument to override the
automatically computed replacement for the expression rule. Note that the new replacement for
expression is also used for the automatic computation of minimal replacements for all other rules
that make use of the expression rule. For example, using 0 as replacement for the expression
rule, the minimal replacement for the statement rule becomes 0; (instead of a;).
To actually reduce the input test case, at least provide the --reduce and --test options:
./run.sh --in path/to/test_case --grammar path/to/grammar --reduce ALGORITHM --test TEST_FUNCTION
The --reduce option specifies which reduction algorithm should be used. The most important
reducers that RedPEG offers are: HDD, CoarseHDD, HDDr, GTR, Perses, and Pardis (see
above for references to their respective publications). The source file
src/main/java/i2/act/reduction/ReducerFactory.java contains a list of all provided algorithms and
their respective names.
Note that most reducers (including the ones listed above) also offer a fixpoint mode, in which the
reduction algorithm is executed multiple times until the result no longer changes. Append a * to
the name of a reducer to run it in fixpoint mode.
You can also specify a "reduction pipeline", i.e., a list of reducers that should be applied one
after another. For this purpose, simply separate the reducer names with a | character. For
example, to run CoarseHDD* followed by HDD, pass --reduce 'CoarseHDD*|HDD' to the run.sh
script. If all reducers should be repeatedly run until a fixpoint is reached, simply append a |*
to the list of reducer names (e.g., --reduce 'CoarseHDD*|HDD|*').
The --test option takes as argument a command line that should be executed to check if a reduction
candidate triggers a bug. For this purpose, the path to a file containing the current reduction
candidate is appended as additional command line option to the specified command line. In most
cases, the command line simply consists of the path to a shell script that implements the test
function. The test function should return 1 if the reduction candidate triggers the bug (and 0
otherwise).
In one way or another, most reducers remove tokens from the input program and join the remaining
tokens to a new program. In some cases, naively joining the tokens may lead to syntactically invalid
reduction candidates which are often rejected by the test function (e.g., two neighboring
identifiers may be incorrectly merged to a single one). Our serialization mechanism therefore tries
to find out if neighboring tokens have to be separated. By default, this mechanism uses a single
space character as separator (this is a valid token separator in most programming languages); the
command line option --join can be used to specify a different separator string.
If the --tryFormat command line option is given, our serialization mechanism tries to improve the
formatting of the reduced programs by introducing additional line breaks. Note that this feature is
experimental and may even lead to syntactically invalid reduction candidates in some cases.
By default, the reduction result is written to the same directory as the input program, i.e., if the
input file name is path/to/input.txt, the result is written to path/to/input.reduced.txt. Note
that "on-the-fly" minimization is supported, i.e., as soon as a reduction step is successful, the
reduced test case is available in the output file (but may be overridden in a later step). This
allows you to cancel the reduction at any time, i.e., you do not have to wait until the reduction is
finished.
Use the --out option to manually specify the file name of the output file.
Alternatively, use the --outDir option to specify the directory that the result should be written
to. The file name inside the directory matches that of the input file, but the string reduced is
prepended before its file extension.
By default, only a single reduction candidate is kept on disk (the last successful reduction
candidate). Use --keepSuccessful to keep all successful reduction candidates, --keepUnsuccessful
to keep all unsuccessful reduction candidates, and --keepAll to keep all reduction candidates.
By providing the --statsCSV option and a file name as argument, a CSV file containing statistics
about the reduction is written to disk.
By providing the --statsJSON option and a file name as argument, a JSON file containing statistics
about the reduction is written to disk.
Add the --countTokens option to include the number of tokens of each reduction candidate in the
statistics. Note that counting the tokens takes some time (depending on the size of the reduction
candidate, this may range from few milliseconds to multiple seconds). To not distort the time
measurements, we do not include the time for counting the tokens in the measurements.
Most of the provided reduction algorithms handle list structures specially and apply a list
reduction algorithm to such structures. By default, these algorithms use their respective original
list reduction algorithm for this purpose, but you can manually specify the list reduction algorithm
with the --listReduction option. The two most important list reduction algorithms that RedPEG
offers are DDMin and OPDD (see above for references to their respective publications), but
RedPEG also offers some variants of them. See the file
src/main/java/i2/act/reduction/lists/ListReductionFactory.java for all possible list reduction
algorithms and their names.
You can specify limits to abort the reduction prematurely:
--sizeLimit: Abort the reduction once the size of the reduced input (in bytes) is smaller than the provided value.--checkLimit: Abort the reduction after the provided number of checks.--timeLimit: Abort the reduction after the provided time (in ms).
You can also specify more than one limit.
In some cases, reduction algorithms generate the exact same reduction candidates multiple times. By
default, the test function is executed once per candidate, but you can specify the --cache option
to cache the result of a call of the test function. Note that this may require a lot of memory in
certain cases.
By default, each successful reduction step is logged to stderr. To increase or decrease the level of
output, specify the --verbosity command line option.
In certain cases, it may be useful to first strip some tokens from the input program before starting
the actual reduction, e.g., to remove unnecessary comments. For this purpose, the framework includes
a helper script strip.sh that is invoked as follows:
./strip.sh --in path/to/input --grammar path/to/grammar --out path/to/output --strip TOKENS
Here, TOKENS is a comma separated list of token names (as defined in the input grammar). All
tokens that match one of the specified ones are removed from the input.
The helper script also accepts the command line options --join and --tryFormat (see above).
The RedPEG framework can easily be extended with new reduction algorithms. To do so, simply add a
new class for the reducer and let it implement the interface i2.act.reduction.Reducer. Afterwards,
register the new reducer under the desired name(s) in i2.act.reduction.ReducerFactory. You can
then choose the new reducer with the --reduce command line option (see above).
As explained above, most reducers use a list reduction algorithm under the hood to reduce list
structures in the syntax tree and RedPEG allows the combination of any reducer with any list
reduction algorithm. To extend RedPEG with a new list reduction algorithm, simply implement the
interface i2.act.reduction.lists.ListReduction and register the new list reduction algorithm under
the desired name in i2.act.reduction.lists.ListReductionFactory. The new list reduction algorithm
can then be chosen with the --listReduction command line option (see above).
RedPEG is licensed under the terms of the MIT license (see LICENSE.mit).
RedPEG makes use of the following open-source projects:
- Gradle (licensed under the terms of Apache License 2.0)