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
Times are displayed in time zone: Guadalajara, Mexico City, Monterrey change

15:30 - 17:00: Testing IResearch Papers / Journal-First at Horizons 5
Chair(s): David LoSingapore Management University
15:30 - 15:52
Talk
Identifying failure-causing schemas in the presence of multiple faults
Journal-First
Xintao Niu, Changhai Nie, Yu Lei, Hareton Leung, Xiaoyin WangUniversity of Texas at San Antonio, USA
DOI
15:52 - 16:15
Talk
Singularity: Pattern Fuzzing for Worst Case Complexity
Research Papers
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
16:15 - 16:37
Talk
Bug Synthesis: Challenging Bug-Finding Tools with Deep Faults
Research Papers
Subhajit RoyIIT Kanpur, India, Awanish PandeyIIT Kanpur, India, Brendan Dolan-GavittNew York University, Yu HuNew York University, USA
16:37 - 17:00
Talk
Modify, Enhance, Select: Co-Evolution of Combinatorial Models and Test Plans
Research Papers
Rachel Tzoref-BrillIBM Research, Shahar MaozTel Aviv University