Redundant traversal of loops in the context of other loops has been recently
identified as a source of performance bugs in many Java libraries. This has resulted in
the design of static and dynamic analysis techniques to detect similar performance bugs
automatically. However, while the effectiveness of dynamic analyses is dependent on the
analyzed input tests, static analyses are less effective in automatically validating the
presence of these problems, validating the fixes and avoiding regressions in future versions.
This necessitates the design of an approach to automatically generate tests for exposing
redundant traversal of loops.
In this paper, we design a novel, scalable and automatic approach that addresses this goal.
Our approach takes a library and an initial set of coverage-driven randomly generated tests
as input and generates tests which enable detection of redundant traversal of loops. Our
approach is broadly composed of three phases - analysis of the execution of random tests to
generate method summaries, identification of methods with potential nested loops along with
the appropriate context to expose the problem, and test generation to invoke the identified
methods with the appropriate parameters. The generated tests can be analyzed by existing
dynamic tools to detect possible performance issues.
We have implemented our approach on top of the soot bytecode analysis framework and validated
it on many open-source Java libraries. Our experiments reveal the effectiveness of our
approach in generating 224 tests that reveal 46 bugs across seven libraries, including 34
previously unknown bugs. The tests generated using our approach significantly outperform the
randomly generated tests in their ability to expose the inefficiencies, demonstrating the
usefulness of our design.
The VM image and usage instructions are available here
Directed Test Generation to Detect Loop Inefficiencies. pdf
Monika Dhok firstname.lastname@example.org