Automatically refining partial specifications for heap-manipulating programs

• Published in: Science of computer programming 2014-03, Vol.82, p.56-76
• Main Authors: Qin, Shengchao, He, Guanhua, Luo, Chenguang, Chin, Wei-Ngan, Yang, Hongli
• Format: Article
• Language: English
• Subjects: Constraint abstraction; Numerical analysis; Partial specification refinement; Semi-automatic software verification; Separation logic; Static program analysis
• ISSN: 0167-6423; 1872-7964
• DOI: 10.1016/j.scico.2013.03.004

Automatically verifying heap-manipulating programs is a challenging task, especially when dealing with complex data structures with strong invariants, such as sorted lists and AVL/red–black trees. The verification process can greatly benefit from human assistance through specification annotations, but this process requires intellectual effort from users and is error-prone. In this paper, we propose a new approach to program verification that allows users to provide only partial specification to methods. Our approach will then refine the given annotation into a more complete specification by discovering missing constraints. The discovered constraints may involve both numerical and multi-set properties that could be later confirmed or revised by users. We further augment our approach by requiring partial specification to be given only for primary methods. Specifications for loops and auxiliary methods can then be systematically discovered by our augmented mechanism, with the help of information propagated from the primary methods. Our work is aimed at verifying beyond shape properties, with the eventual goal of analysing full functional properties for pointer-based data structures. Initial experiments have confirmed that we can automatically refine partial specifications with non-trivial constraints, thus making it easier for users to handle specifications with richer properties. •We propose a specification refinement algorithm for heap-manipulating programs.•Our analysis refines user-given shape specifications into complete specifications.•Users can define their own predicates to control program properties to be verified.•We reduce user annotations by requiring no information on loops/auxiliary methods.•We have implemented our analysis and obtained non-trivial experimental results.