Shape and Content Incorporating Domain Knowledge into Shape Analysis

Abstract. The verification community has studied dynamic data struc-tures primarily in a bottom-up way by analyzing pointers and the shapes induced by them. Recent work in fields such as separation logic has made significant progress in extracting shapes from program source code. Many real world programs however manipulate complex data whose struc-ture and content is most naturally described by formalisms from ob-ject oriented programming and databases. In this paper, we attempt to bridge the conceptual gap between these two communities. Our approach is based on description logic, a widely used knowledge representation paradigm which gives a logical underpinning for diverse modeling frame-works such as UML and ER. We show how description logic can be used on top of an existing shape analysis to add content descriptions to the shapes. Technically, we assume that we have separation logic shape in-variants obtained from a shape analysis tool, and requirements on the program data in terms of description logic. Thus, we obtain a modular description logic based verification methodology which is able to exploit shape information.