Name
Abstract | ||
|---|---|---|
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 multiset properties that could be later confirmed or revised by users. We further augment our approach by requiring only partial specification to be given 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21437-0_28 | FM |
Keywords | Field | DocType |
complete specification,primary method,augmented mechanism,specification annotation,verification process,pointer-based data structure,automatically refining,program verification,complex data structure,new approach,partial specification | Data structure,Pointer (computer programming),Separation logic,Programming language,Complex data structures,Annotation,Multiset,Computer science,Invariant (mathematics),Symbolic execution | Conference |
Citations | PageRank | References |
7 | 0.55 | 36 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shengchao Qin | 1 | 711 | 62.81 |
| Chenguang Luo | 2 | 56 | 5.63 |
| Wei-Ngan Chin | 3 | 868 | 63.37 |
| Guanhua He | 4 | 68 | 7.50 |