Binary Reduction of Depdendency Graphs

Delta debugging is a technique for reducing a failure-inducing input to a small input that reveals the cause of the failure. This has been successful for a wide variety of inputs including C programs, XML data, and thread schedules. However, for input that has many internal dependencies, delta debugging scales poorly. Such input includes C#, Java, and Java bytecode and they have presented a major challenge for input reduction until now. In this paper, we show that the core challenge is a reduction problem for dependency graphs, and we present a general strategy for reducing such graphs. We combine this with a novel algorithm for reduction called Binary Reduction in a tool called J-Reduce for Java bytecode. Our experiments show that our tool is 12x faster and achieves more reduction than delta debugging on average. This enabled us to create and submit short bug reports for three Java bytecode decompilers.


During the research on this paper we developed the Java reduction tool J-Reduce. To install the tool, either download the artifact or follow the instructions in the github repository. The tool is in active development so the newest tool with most features is in the github repository.


The artifact are mostly targeting reduction given a tool that exhibit a bug, but the tool can also be used as a debloater or slicer. To do this first we have to describe how to run the tests.

In this example, we assume that you are running your tests using JUnit, but the procedure is the same for all test-runners:

First, separate the tests from the application that you want to reduce. We imagine that you put the application in a fat jar named app.jar and the test libraries in a ':'-separated list of absolute class paths named TESTPATH. Finally, a list of test-classes that should be executed should be placed in a newline separated file called test.classes.txt.

Now, you should be able to run J-Reduce and get a debloated jar in output.jar.

jreduce --cp "$TESTPATH" --core @test.classes.txt \ 
    -o output.jar app.jar -- \
    java -cp "$TESTPATH:{}" \
      org.junit.runner.JUnitCore $(cat test.classes.txt)

Everything after the -- is the predicate and it will be run with every reduction to check that the tests parses. {} indicates where the app.jar will be added to the class path. Setting the --core and --cp are not strictly necessary, but it enables J-Reduce to precompute a closure from the test-classes which significantly speeds up debloating.