WISE: Automated test generation for worst-case complexity

Program analysis and automated test generation have primarily been used to find correctness bugs. We present complexity testing, a novel automated test generation technique to find performance bugs. Our complexity testing algorithm, which we call WISE (worst-case inputs from symbolic execution), operates on a program accepting inputs of arbitrary size. For each input size, WISE attempts to construct an input which exhibits the worst-case computational complexity of the program. WISE uses exhaustive test generation for small input sizes and generalizes the result of executing the program on those inputs into an ldquoinput generator.rdquo The generator is subsequently used to efficiently generate worst-case inputs for larger input sizes. We have performed experiments to demonstrate the utility of our approach on a set of standard data structures and algorithms. Our results show that WISE can effectively generate worst-case inputs for several of these benchmarks.