swMATH ID: 40808
Software Authors: Lundberg, Didrik; Guanciale, Roberto; Lindner, Andreas; Dam, Mads
Description: Hoare-style logic for unstructured programs. Enabling Hoare-style reasoning for low-level code is attractive since it opens the way to regain structure and modularity in a domain where structure is essentially absent. The field, however, has not yet arrived at a fully satisfactory solution, in the sense of avoiding restrictions on control flow (important for compiler optimization), controlling access to intermediate program points (important for modularity), and supporting total correctness. Proposals in the literature support some of these properties, but a solution that meets them all is yet to be found. We introduce the novel Hoare-style program logic (mathcal{L}_A), which interprets postconditions relative to program points when these are first encountered. The logic can support both partial and total correctness, derive contracts for arbitrary control flow, and allows one to freely choose decomposition strategy during verification while avoiding step-indexed approximations and global invariants. The logic can be instantiated for a variety of concrete instruction set architectures and intermediate languages. The rules of (mathcal{L}_A) have been verified in the interactive theorem prover HOL4 and integrated with the toolbox HolBA for semi-automated program verification, making it applicable to the ARMv6 and ARMv8 instruction sets.
Homepage: https://link.springer.com/chapter/10.1007%2F978-3-030-58768-0_11
Keywords: program logics; formal verification; theorem proving; binary analysis; Hoare logic
Related Software: CIRC; CPAchecker; SeaHorn; GNATprove; RGITL; Leon; Isabelle/HOL; Dafny; TrABin; Cloc; BoogiePL; ARMor; seL4; CakeML; HOL
Cited in: 2 Publications

Cited in 0 Serials

Citations by Year