Tue 6 Nov 2018 15:52 - 16:15 at Horizons 5 - Testing I Chair(s): David Lo

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.

Tue 6 Nov

15:30 - 17:00: Research Papers - Testing I at Horizons 5
Chair(s): David LoSingapore Management University
fse-2018-Journal-First15:30 - 15:52
Xintao Niu, Changhai Nie, Yu Lei, Hareton Leung, Xiaoyin WangUniversity of Texas at San Antonio, USA
fse-2018-research-papers15:52 - 16:15
Jiayi WeiUniversity of Texas at Austin, Jia ChenUniversity of Texas at Austin, Yu FengUniversity of California, Santa Barbara, USA, Kostas FerlesUT Austin, Isil DilligUT Austin
DOI Pre-print
fse-2018-research-papers16:15 - 16:37
Subhajit RoyIIT Kanpur, India, Awanish PandeyIIT Kanpur, India, Brendan Dolan-GavittNew York University, Yu HuNew York University, USA
fse-2018-research-papers16:37 - 17:00
Rachel Tzoref-BrillIBM Research, Shahar MaozTel Aviv University