A Formal Verification Library Design for Behavioral Refinement of CompCert Clight

Abstract

As computer systems become increasingly ubiquitous in our daily lives, ensuring the safety and reliability of system software has become a major concern across various fields of computer science. Among the various methodologies for ensuring software correctness, formal verification using interactive theorem provers is recognized as the method providing the strongest assurance of formal guarantees with a minimal trusted computing base. While many verification frameworks in interactive theorem provers adopt separation logic, there is another paradigm that has not been as extensively studied in this context: behavioral refinement, despite its effectiveness being demonstrated in several large-scale software verification projects. In this work, we develop a concrete theory of behavioral refinement for verifying C programs against abstract specifications. For the formal C semantics, we employ the Clight language provided by the CompCert verified compiler project. We use interaction trees (ITrees) as the representation framework for abstract specifications. We have implemented our approach as a C-program verification library, C2IRef, in the Coq theorem prover, and demonstrated its effectiveness by verifying several practical C programs.

Keywords

• Interactive theorem provers
• programming languages
• software verification