An Abstract, Approximation-Based Approach to Embedded Code Pointers and Partial-Correctness
Zhaozhong Ni · 2008
Abstract. To support higher-order type-like features such as embedded code pointers, in logic-based verification, one approach is to build assertion logic that combines logic and types. But it is not totally satisfactory in various aspects. Another approach is to use approximation in logic to simulate the behavior of types and typing invariants, yet polluting program specifications and proofs with complex approximation details. Additionally, existing approximation-based work have only supported embedded code pointers without partial-correctness guarantee. We propose a new abstract, approximation-based approach to support embedded code pointers in logic-based verification. Our specification language and inference rules are independent of approximation, thus allowing programs to be certified abstractly. Approximation is only used to establish soundness and partial-correctness. We can easily support dynamic code generation. The central idea should be applicable to other higher-order features. Our work is presented on and mechanized in, but not limited to, assembly languages and Coq proof-assistant. 1