关键词:
Program Verification
Separation Logics
Database Management Systems
摘要:
Program verification consists in finding a formal proof that the program satisfies a given specification. This specification can be described as assertions about the input and output a correct program must satisfy. Assertions and programs are traditionally specified in terms of classical first order logic (FOL). FOL reasoners (inference systems) automatically find the correspondent program correctness proof, if any. However, verification of programs with mutable data structures, such as pointers, is currently a major challenge for the FOL assertion based approach. Mutable data structures are often written in terms of syntactically unrelated expressions, whose specification represents a significant defiance for FOL. Separation logics are a family of formal languages with specially-purposed constructors designed to model mutable data structures. In this paper, we formally verify a database management system using separation logics. We focused on the verification of libraries containing programs about heap manipulation. Several detected bugs are described in detail, respective solutions are also provided.