WISE: Automated Test Generation for Worst-Case Complexity

Program analysis and automated test generation have primarily been used to find correctness bugs. The authors present complexity testing, a novel automated test generation technique to find performance bugs. Their complexity testing algorithm, which they 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 "Input generator." The generator is subsequently used to efficiently generate worst-case inputs for larger input sizes.