Modal Verification Patterns for Systems
Ismail Kuru, Colin S. Gordon · 2025
Read Modal Verification Patterns for Systems by Ismail Kuru, Colin S. Gordon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01719.txt.
Introduction
Systems software is hard to verify because its parts share resources in shifting patterns, yet those patterns repeat across programs. Ismail Kuru and Colin Gordon argue in 2025 that modal logic, the logic of what holds in which context, should be the default tool for the job. A notion they call resource context guides how new modalities get designed.
They reread earlier verified systems and show each fits the pattern they describe. The fit, they argue, is no accident: the systems succeeded because their modalities matched the resource structure. The position paper then sketches how the pattern could attack fresh verification problems. It offers designers a reusable shape for proofs about low level code.
Catalog record
| CREATOR | Ismail Kuru, Colin S. Gordon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01719
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Modal Verification Patterns for Systems Ismail Kuru, Colin S. Gordon Abstract Although they differ in the functionality they offer, low-level systems exhibit certain patterns of design and utilization of computing resources. In this paper we examine how modalities have emerged as a common structure in formal verification of low-level software, and explain how many recent examples naturally share common structure in the relationship between the modalities and software features they are used to reason about. We explain how the concept of a resource context (a class of system resources to reason about) naturally corresponds to families of modal operators indexed by system data, and how this naturally leads to using modal assertions to describe resource elements (data in the relevant context). We also describe extensions of this idea to ongoing work in formal verification of filesystems code. 1 Introduction Although they differ in the functionality they offer, low-level systems exhibit certain patterns of design and utilization of computing resources. Systems software, in general, interfaces with an underlying computing substrate such that any software system at any higher level in the software stack can (at least indirectly) utilize the resources of the machine. The last layer of software before the hardware is naturally critical to the correctness of an overall system, as essentially all software built on top of it assumes its correctness. And because hardware is complex and highly diverse, the implementation of those lowest layers of the software stack is typically intricate and naturally error-prone, despite how critical its correctness is. Typically systems software has, as a primary focus, the task of abstracting from hardware details to simplify the construction of higher layers of the stack. Low-level systems software exhibits certain patterns in their designs, especially when interacting with computing resources. Exploiting certain patterns while designing software has been an important field of study. This survey examines these common patterns in systems software, and their relationships to modalities. We believe that certain properties of modalities enable us to understand and address the verification challenges of these systems by tailoring specification and proof to the same patterns used to design the systems. Contributions We argue that modal abstractions can be used to identify and abstract system verification challenges. We justify our perspective by discussing prior systems that have successfully used modalities for system verification, arguing that they fit into the verification design pattern we articulate, and explaining how this approach might apply to other systems’ verification challenges. • Identifying System Verification Challenges : We start with identifying common patterns in system verification: virtualization, sharing, and translation . • Introducing Modal Resource Contexts : Then we discuss the concept of resource which has already been an essential concept in the design of systems. Inspired by the concept of resource in the systems, we define what a resource and its context are in the modal abstractions. • Introducing Nominals for System Resources : Existing logics for systems software must frequently identify individual resources within a given context — nominalization (in the sense of hybrid logic) enables identifying a resource in its context. For example, a filesystem transaction is a context of resources for in-memory updated disk blocks which have not yet been saved to disk. The transaction identifier is used to associate a transaction with a disk-block to be persisted so that, in case of a crash while persisting updated disk-blocks, the filesystem can rollback the already persisted disk-blocks of the transaction, and reach to the previous consistent disk state. We discuss other examples to contextualize the existing systems surveyed. • Taxonomy of Current Modal Approaches in System Verification : Based on these concepts defined, we summarize contemporary verification efforts using modal abstractions. We choose them from different domains, for example, reasoning about weak memory models and storage persistence [ 5 , 6 , 7 , 47 , 13 , 14 , 9 , 33 , 48 ] because we would like to justify that our definitions are not domain dependent. 2 Background on Modal Logics for Programs, and Low-Level Systems Software This section briefly recalls related concepts from modal logic of particular relevance to our taxonomy, which should be familiar but benefit from fixing notation (Section 2.1 ), and enough general background on the systems software concepts organized by our taxonomy for the connections to modalities to be clear (Section 2.2 ). 2.1 Hybrid Logic, Dynamic Logic, and Nominals in Program Logics Dynamic Logics as Program Logics We believe that for the kinds of informal reasoning and the sorts of data structures discussed in the previous section, ideas from modal logic are a promising approach to formalization and verification. Broadly speaking modal logics incorporate modal operators , which take as arguments a proposition expected to be true in another time [ 39 ] , place [ 19 , 18 , 1 , 17 , 35 ] , circumstance or point-of-view [ 25 , 23 ] , and result in a proposition true in the current time, place, or circumstance at which the truth of the use of the modal operator is being evaluated. Classic examples include modal necessity \square P describing that P is necessarily true, \mathsf{G}~P meaning P is true globally (i.e., forever from this time onwards in temporal logics), or K_{i}(P) describing that a particular participant i knows that P is true. The latter is an example of multimodal logic, where there is an family of modalities (modal operators) parameterized by some dimension of interest (there, participants). Dynamic logic [ 40 ] , a (multi)modal logic of weakest preconditions [ 12 ] which works with modalities of the form [p](P) , which states that in the current program state , if program p is run then afterwards P will hold (modulo non-termination). This same idea is used to encode Hoare triples in the Iris program logic [ 28 ] , using the same encoding as in Pratt’s original presentation, where a Hoare triple \{P\}C\{Q\} is encoded as P\rightarrow[C](Q) . Iris is now one of the most successful foundational program logics, and its rich support for extending the base logic with additional modalities [ 31 ] means that modal logics, and in particular dynamic logic, now play an outsized role in program verification — many challenging proofs of program correctness use a substructural dynamic logic containing many additional modalities which interact with the weakest precondition modality. Hybrid Logic Hybrid logics [ 2 , 18 , 17 , 1 , 4 ] are a class of modal logics that add two primary new concepts to a logic. Nominals \l\in\textsf{Loc} uniquely identify points in a model (e.g., a particular state), so there is exactly one point in the model where a nominal Loc is true. Satisfaction operators are modal operators indexed by nominals, which enable claims about the truth of another proposition at some arbitrary point in the model identified by a nominal. Traditionally @_{l}\varphi asserts that \varphi is true in the state identified by l . Conceptually, given our context, we might like l to indicate truth in a particular data structure l . However, most prior work on hybrid logics works in classical logics rather than a substructural setting like separation logic. Newer work surveyed here adapts this idea to