Place Capability Graphs: A General-Purpose Model of Rust’s Ownership and Borrowing Guarantees

Zachary Grannan, Aurea Bílá, Jonáš Fiala, Jasper Geer, Markus de Medeiros, Peter Müller, Alexander J. Summers · 2025

Read Place Capability Graphs: A General-Purpose Model of Rust’s Ownership and Borrowing Guarantees by Zachary Grannan, Aurea Bílá, Jonáš Fiala, Jasper Geer, Markus de Medeiros, Peter Müller, Alexander J. Summers (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-2503-21691.txt.

Introduction

Zachary Grannan, Aurea Bílá, and their co-authors present a 2025 model of the ownership rules in the Rust programming language. Rust's type system gives strong promises about who may use or change data, which makes it a good target for tools that check programs for errors. Past models either covered a toy version of the language or handled real code with sharp limits.

Their model, called Place Capability Graphs, can be built straight from the Rust compiler's own data. It handles loans of data, mixed types that hold them, function signatures, and loops. The model covered more than 97 percent of functions in the most used public Rust packages. The team also built trial versions of two existing analysis tools on top of it.

Catalog record

CREATORZachary Grannan, Aurea Bílá, Jonáš Fiala, Jasper Geer, Markus de Medeiros, Peter Müller, Alexander J. Summers
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE154 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-21691

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Place Capability Graphs: A General-Purpose Model of Rust’s Ownership and Borrowing Guarantees Zachary Grannan, Aurea Bílá, Jonáš Fiala, Jasper Geer, Markus de Medeiros, Peter Müller, Alexander J. Summers Abstract . Rust’s novel type system has proved an attractive target for verification and program analysis tools, due to the rich guarantees it provides for controlling aliasing and mutability. However, fully understanding, extracting and exploiting these guarantees is subtle and challenging: existing models for Rust’s type checking either support a smaller idealised language disconnected from real-world Rust code, or come with severe limitations in terms of precise modelling of Rust borrows, composite types storing them, function signatures and loops. In this paper, we present Place Capability Graphs : a novel model of Rust’s type-checking results, which lifts these limitations, and which can be directly calculated from the Rust compiler’s own programmatic representations and analyses. We demonstrate that our model supports over 97% of Rust functions in the most popular public crates, and show its suitability as a general-purpose basis for verification and program analysis tools by developing promising new prototype versions of the existing Flowistry and Prusti tools. DOI: 10.1145/3763122 Journal: PACMPL Volume: 9 OOPSLA2 344 10 CCS: Theory of computation Program analysis CCS: Theory of computation Type structures † † cc-license: by 1. Introduction Rust is a popular programming language, combining competitive performance with a rich and expressive type system that eliminates many common programming errors and unintended side-effects. Rust’s type system applies a notion of ownership to all allocated memory, by default preventing access through any variable other than its owner, and defining its deallocation time (when its owner goes out of scope). Aliasing is restricted by a notion of borrowed references which may temporarily access memory that they alias but do not own. As the name suggests, the ability to access borrowed memory is taken temporarily, and then restored to its lender. Rust allows multiple aliases to the same memory to be usable at once only if none can mutate its content. The restrictive aliasing discipline of Rust’s type system makes the language attractive as a static analysis and verification target, given the challenges of reasoning about aliasing in general (the infamous frame problem ). A wealth of formal techniques have grown up for Rust, including formalisations ( Jung et al., 2018a ; Weiss et al., 2019 ; Matsushita et al., 2022 ; Ho and Protzenko, 2022 ) , (deductive) verification tools targeting specification-annotated Rust code ( Astrauskas et al., 2019 ; Denis et al., 2022 ; Lattuada et al., 2023 ; Lehmann et al., 2022 ) , and static analyses ( VanHattum et al., 2022 ; Crichton et al., 2022 ; Bae et al., 2021 ) . These projects leverage the rich guarantees provided by Rust’s type checking in the ways they internally model program memory, track aliasing and value information, and interpret user-provided specifications of desired program properties. This paper does not define Rust’s type-checking algorithms , but rather defines a detailed model which substantially elaborates their results in a way which reifies Rust’s rich guarantees, and is exploitable for diverse program analysis and verification techniques and tools. Comprehensively modelling Rust’s type checking is technically challenging for a variety of reasons. The properties implied at different program points are flow-sensitive ; for example, whether a variable currently owns memory is not visible from its declared type or its initialisation, as Rust allows move assignments to transfer ownership between places (Rust’s terminology for expressions denoting locations). Similarly, whether a place has been borrowed-from, and for how long, are flow-sensitive properties. Rust’s type checking includes borrow checking , which determines whether consistent choices can be made for the extents of each borrow; the points at which borrows end are invisible in source code, but important for code understanding and analysis: this is when side-effects previously performed via the borrowed references become observable via the borrowed-from places. Capturing Rust’s notions of borrowing for general types and programs yields several sources of complexity: (1) instances of composite types (such as structs) may store borrows. These types are declared with nested lifetimes , which indicates to Rust’s type checker the possibly unbounded number of borrows stored within them; notions of borrowing are generalised to the sets of borrows stored in these types. (2) Rust allows for reborrowing : transitively creating chains of borrows to parts of memory previously borrowed. These borrows can be created and expired differently in different paths through the program, so precisely tracking their effects requires path-sensitive information. (3) Programs with loops can create (re)borrows unboundedly many times. To capture Rust’s type checking in such cases, loops must be summarised in a way which matches the compiler’s rules. (4) A model of Rust’s borrowing must respect the modularity of Rust function calls, including the subtle ways in which Rust allows programmers to abstract over constraints between (nested) lifetimes in function signatures. We explain the full details of these (and other) challenges in Sec. 2 . Table 1 . Most-closely-related work, compared on the criteria motivating our model and paper. Our Key Criteria (cf. page 1 ) Other Borrowing Challenges (cf. page 1) Selected (1) Function- (2) Path- (3) Connect (4) Most (5) Use for Struct Loop Function Defines Existing Modular Sensitive from + to Real-world Diverse Lifetime Reborrow Reborrow Borrow Work Model Info. Rust repr. Rust Code Analyses Params Summary Summary Checking Oxide ( Weiss et al., 2019 ) ✓ 1 ✓ ✓ ✓ Aeneas ( Ho et al., 2024 ) ✓ 1 ✓ 2 ✓ ✓ RustBelt ( Jung et al., 2018a ) ✓ ✓ ✓ ✓ ✓ Stacked / Tree Borrows ( Jung et al., 2020 ; Villani et al., 2025 ) ✓ ✓ ✓ PCGs ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 1 compilation from Rust only; results for custom program representations only. 2 partial heuristic support: see ( Ho et al., 2024 ) for details. In this paper, we present a novel model of the results of Rust’s type checking, designed to address all of these technical challenges and to enable downstream tools to exploit the properties implied by Rust’s design. Our model does not define Rust type checking itself, but captures in detail the results of successfully type checking a Rust program as defined by the standard Rust compiler. It seamlessly combines solutions to two technical objectives: (1) where computable, all information a downstream analysis might require is precise , and (2) where abstractions are necessary in general either for computability or modularity reasons (for loops, function calls and types containing sets of borrows), these abstractions are consistent with those employed by the compiler. While many existing works define a variety of formal models for different aspects of Rust’s design (we discuss these in detail in Sec. 5 ), these do not handle the full set of challenges defined above. We provide a high-level overview of how some related work compares in terms of the objectives of our own work in Table 1 . We note that many existing works have objectives we do not address, such as defining operational semantics for Rust, or defining how type checking itself can/should be done. Overall, we have designed our novel model to satisfy the following

Read the complete text