We describe a new blackbox complexity testing technique for determining the worst-case asymptotic complexity of a given application. The key idea is to
look for an \emph{input pattern} —rather than a concrete input— that maximizes the asymptotic resource usage of the target program. Because input patterns can be described concisely as programs in a restricted language, our method transforms the complexity testing problem to \emph{optimal program synthesis}. In particular, we express these input patterns using a new model of computation called \emph{Recurrent Computation Graph (RCG)} and solve the optimal synthesis problem by developing a genetic programming algorithm that operates on RCGs. We have implemented the proposed ideas in a tool called {\sc Singularity}\xspace and evaluate it on a diverse set of benchmarks. Our evaluation shows that {\sc Singularity}\xspace can effectively discover the worst-case complexity of various algorithms and that it is more scalable compared to existing state-of-the-art techniques.
Furthermore, our experiments also corroborate that {\sc Singularity}\xspace can discover \emph{previously unknown} performance bugs and availability vulnerabilities in real-world applications such as Google Guava and JGraphT.