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

Displayed time zone: Guadalajara, Mexico City, Monterrey change

15:30 - 17:00
Testing IJournal-First / Research Papers at Horizons 5
Chair(s): David Lo Singapore Management University
15:30
22m
Talk
Identifying failure-causing schemas in the presence of multiple faults
Journal-First
Xintao Niu , Changhai Nie , Yu Lei , Hareton Leung , Xiaoyin Wang University of Texas at San Antonio, USA
DOI
15:52
22m
Talk
Singularity: Pattern Fuzzing for Worst Case Complexity
Research Papers
Jiayi Wei University of Texas at Austin, Jia Chen University of Texas at Austin, Yu Feng University of California, Santa Barbara, USA, Kostas Ferles UT Austin, Isil Dillig UT Austin
DOI Pre-print
16:15
22m
Talk
Bug Synthesis: Challenging Bug-Finding Tools with Deep Faults
Research Papers
Subhajit Roy IIT Kanpur, India, Awanish Pandey IIT Kanpur, India, Brendan Dolan-Gavitt New York University, Yu Hu New York University, USA
16:37
22m
Talk
Modify, Enhance, Select: Co-Evolution of Combinatorial Models and Test Plans
Research Papers
Rachel Tzoref-Brill IBM Research, Shahar Maoz Tel Aviv University