Static analysis of lists by combining shape and numerical abstractions

• We propose a light-weight shape abstraction for lists based on bit vectors.
• We use numerical abstractions to infer relations among sizes of list segments.
• We combine shape and numerical abstractions to analyze programs with lists.
• We extend our approach to fit for analyzing circular lists.
• Experiments show that our approach find intricate length properties for lists.

We present an approach in the framework of abstract interpretation to analyze list-manipulating programs by combining shape and numerical abstractions. The analysis automatically divides a list into non-overlapping list segments according to the reachability property of pointer variables to list nodes. The list nodes in each segment are abstracted by a bit-vector wherein each bit corresponds to a pointer variable and indicates whether the nodes can be reached by that pointer variable. Moreover, for each bit-vector, we introduce an auxiliary integer variable, namely a counter variable, to record the number of nodes in the segment abstracted by that bit-vector. On this basis, we leverage the power of numerical abstractions to discover numerical relations among counter variables, so as to infer relational length properties among list segments. Furthermore, we show how our approach works for circular lists. Our approach stands out in its ability to find intricate properties that involve both shape and numerical information, which are important for checking program properties such as memory safety. A prototype is implemented and preliminary experimental results are encouraging.