Abstract

Analysing and comprehending C programs that use strings is hard: Using standard library functions for manipulating strings is not enforced and programs often use complex loops for the same purpose. We introduce the notion of memoryless loops that capture some of these string loops and present a counterexample-guided inductive synthesis approach to summarise memoryless string loops using C standard library functions, which has applications to testing, optimization and refactoring.

We prove our summarization is correct for arbitrary input strings and evaluate it on a database of loops we gathered from a set of 13 open-source programs. Our approach can summarize over two thirds of memoryless loops in less than 5 minutes of computation time per loop. We then show that these summaries can be used to both enhance symbolic execution testing, where we observed significant speedups when employing a string constraint solver and refactor code, where we had several patches accepted in the codebases of popular applications such as patch and wget.

Joint work with Oren Ish-Shalom, Shachar Itzhaky, Noam Rinetzky and Cristian Cadar.