Gradual Verification of Recursive Heap Data Structures
Sun 15 Nov 2020 20:20 - 21:00 at SPLASH-VII - Posters Session 1 Mirror
Current static verification techniques do not provide good support for incrementality, making it difficult for developers to focus their limited effort on specifying and verifying the properties and components that are most important. Dynamic verification approaches support incrementality, but cannot provide static guarantees. To bridge this gap, prior work proposed gradual verification, which supports incrementality by allowing every assertion to be complete, partial, or omitted, and provides sound verification that smoothly scales from dynamic to static checking. The prior approach to gradual verification, however, was limited to toy programs without recursive data structures. This paper extends gradual verification to realistic programs that manipulate recursive, mutable data structures on the heap. We solve key technical challenges, semantically connecting iso- and equi-recursive interpretations of abstract predicates as well as gradual verification of heap ownership. Our work thus lays the foundation for future tools that work on realistic programs and support verification within an engineering process in which cost-benefit trade-offs can be made.