CITATION.bib

@inproceedings{10.1145/3453483.3454091,
author = {Kalhauge, Christian Gram and Palsberg, Jens},
title = {Logical Bytecode Reduction},
year = {2021},
isbn = {9781450383912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3453483.3454091},
doi = {10.1145/3453483.3454091},
abstract = {Reducing a failure-inducing input to a smaller one is challenging for input with internal
dependencies because most sub-inputs are invalid. Kalhauge and Palsberg made progress
on this problem by mapping the task to a reduction problem for dependency graphs that
avoids invalid inputs entirely. Their tool J-Reduce efficiently reduces Java bytecode
to 24 percent of its original size, which made it the most effective tool until now.
However, the output from their tool is often too large to be helpful in a bug report.
In this paper, we show that more fine-grained modeling of dependencies leads to much
more reduction. Specifically, we use propositional logic for specifying dependencies
and we show how this works for Java bytecode. Once we have a propositional formula
that specifies all valid sub-inputs, we run an algorithm that finds a small, valid,
failure-inducing input. Our algorithm interleaves runs of the buggy program and calls
to a procedure that finds a minimal satisfying assignment. Our experiments show that
we can reduce Java bytecode to 4.6 percent of its original size, which is 5.3 times
better than the 24.3 percent achieved by J-Reduce. The much smaller output is more
suitable for bug reports.},
booktitle = {Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation},
pages = {1003–1016},
numpages = {14},
keywords = {type-safe code transformation, input reduction},
location = {Virtual, Canada},
series = {PLDI 2021}
}