一句话：提出模式模糊测试，用程序合成搜索输入模式以揭示程序最坏渐近复杂度。
论文提出一种黑盒复杂度测试技术，用于确定程序的最坏情况渐近复杂度。其核心思想不是寻找具体输入，而是寻找能最大化渐近资源使用的输入模式；由于输入模式可用受限语言简洁描述，作者将复杂度测试转化为最优程序合成问题，并定义循环计算图（Recurrent Computation Graph, RCG）作为计算模型，进而设计作用于 RCG 的遗传编程算法。工具 Singularity 在多种基准上评估，能有效发现各类算法的最坏复杂度，且比现有先进技术更具可扩展性，还在 Google Guava、JGraphT 等真实应用中发现了未知性能缺陷与可用性漏洞。
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 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 optimal program synthesis. In particular, we express these input patterns using a new model of computation called 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 Singularityand evaluate it on a diverse set of benchmarks. Our evaluation shows that Singularitycan 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 Singularitycan discover previously unknown performance bugs and availability vulnerabilities in real-world applications such as Google Guava and JGraphT.