Automatic Linear Resource Bound Analysis for Rust via Prophecy Potentials
Qihao Lian, Di Wang · 2025
Read Automatic Linear Resource Bound Analysis for Rust via Prophecy Potentials by Qihao Lian, Di Wang (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-2502-19810.txt.
Introduction
Qihao Lian and Di Wang present a static tool that bounds the resource use of Rust programs. Their paper is from two thousand twenty-five. Rust is a systems language prized for memory safety with speed. Yet a safe program can still be slow, and its cost in time or memory is hard to call in advance.
Their tool, RaRust, is a type system that infers straight-line bounds on cost. It leans on Rust's borrow rules, the feature that makes its safety work. New prophecy potentials let it track shared and sole borrows in parts. A test build infers bounds for programs with loans, heaps, loops, and self-calls.
Catalog record
| CREATOR | Qihao Lian, Di Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 137 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-19810
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Automatic Linear Resource Bound Analysis for Rust via Prophecy Potentials Qihao Lian, Di Wang Abstract . Rust has become a popular system programming language that strikes a balance between memory safety and performance. Rust’s type system ensures the safety of low-level memory controls; however, a well-typed Rust program is not guaranteed to enjoy high performance. This article studies static analysis for resource consumption of Rust programs, aiming at understanding the performance of Rust programs. Although there have been tons of studies on static resource analysis, exploiting Rust’s memory safety—especially the borrow mechanisms and their properties—to aid resource-bound analysis, remains unexplored. This article presents RaRust , a type-based linear resource-bound analysis for well-typed Rust programs. RaRust follows the methodology of automatic amortized resource analysis (AARA) to build a resource-aware type system. To support Rust’s borrow mechanisms, including shared and mutable borrows, RaRust introduces shared and novel prophecy potentials to reason about borrows compositionally. To prove the soundness of RaRust , this article proposes Resource-Aware Borrow Calculus (RABC) as a variant of recently proposed Low-Level Borrow Calculus (LLBC). The experimental evaluation of a prototype implementation of RaRust demonstrates that RaRust is capable of inferring symbolic linear resource bounds for Rust programs featuring shared and mutable borrows, reborrows, heap-allocated data structures, loops, and recursion. DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 10 ISBN: 978-1-4503-XXXX-X/18/06 1. Introduction Rust ( Matsakis and Klock, 2014 ) has become a popular programming language that aims to bridge the gap between fine-grained memory control and high-level memory safety, especially in the context of system programming. Rust introduces a complex type system that features linear types and borrow mechanisms, enabling system engineers to write high-performance memory-manipulating code without needing garbage collection or compromising memory safety. The popularity of Rust indicates that system engineers still care about resource consumption —such as time, memory, and energy usage—of their programs, in order to achieve high or predictable performance. However, using Rust does not directly mean achieving high performance; in fact, there exists a book ( Nethercote, 2020 ) that collects techniques to improve the performance of Rust programs, including general and Rust-specific techniques. Additionally, predicting the performance of a Rust program is often difficult to do manually. Therefore, understanding the resource consumption—as a general topic in software engineering—continues to be a crucial issue in Rust programming. In this paper, we study how to automatically and statically reason about the resource consumption of Rust programs via a type system. In particular, we want to understand how the reasoning process could benefit from Rust’s advanced type system. Recent years have seen many studies on (i) static analysis for resource consumption, and (ii) static analysis of Rust programs. We highlight some mostly-related type-based approaches below; other related work will be discussed in section 9 . Automatic amortized resource analysis (AARA)—initially proposed by Hofmann and Jost (2003) —has been a state-of-the-art framework for statically inferring symbolic resource bounds of various kinds of programs ( Hoffmann and Jost, 2022 ) . The inferred bounds are symbolic in the sense that they are interpreted as functions of a program’s input and output. Despite the fact that most AARA approaches are focused on analyzing pure functional programs, there are multiple exceptions related to memory control: Atkey (2010) studied the integration of AARA and separation logic, Carbonneaux et al. (2015) developed C4B, which can analyze C programs with arrays, and Lichtman and Hoffmann (2017) proposed a method to analyze arrays and references in ML programs. However, it is unclear whether any of those approaches can leverage Rust’s type system—especially the borrow mechanisms—during the analysis. On the other hand, some recent studies build advanced type systems upon Rust’s type system. Flux ( Lehmann et al., 2023 ) is a liquid-style refinement type system for Rust, which aims to automatically verify the functional correctness of safe Rust programs. Flux allows programmers to annotate types (including reference types) with decidable logical predicates and then exploits Rust’s borrow mechanisms to separate functional verification from low-level memory reasoning. RefinedRust ( Gäher et al., 2024 ) is another refinement type system for Rust, which aims to carry out foundational reasoning and produce Coq proofs for the functional correctness of both safe and unsafe Rust programs in a semi-automated way. However, those approaches are focused on functional correctness rather than resource consumption of Rust programs. In this paper, we propose RaRust , a new AARA approach that leverages Rust’s borrow mechanisms and a prototype implementation that automatically infers linear resource bounds for safe Rust programs. Rust’s type system enforces ownership principles around references: one can borrow a reference with ownership and later return it back, and the type system checks the soundness of such borrows via a notion of lifetimes . Meanwhile, AARA enforces principles of amortized analysis ( Tarjan, 1985 ) around data structures: type annotations specify potential functions , such that a value can own some potentials to pay for resource consumption and one can transfer potentials among values, and the type system checks the soundness of the potential-based reasoning. Intuitively, our approach integrates the ownership principles of memory locations and potentials. Below we sketch three main technical challenges to obtaining such an integration and our solutions. Firstly, Rust’s type system is rather complex already, and its borrow mechanisms are being updated actively, so we desire the resource analysis to be as orthogonal to Rust’s own borrow checking as possible. Rust now features shared borrows, mutable borrows, reborrows, and non-lexical lifetimes that allow complex uses of borrows. Modifying Rust’s type checker (especially the borrow checker) would be arduous and thus unacceptable. To tackle this challenge, we propose a lightweight design that performs resource analysis on well-borrowed and well-typed Rust programs. RaRust relies on Rust’s borrow checker to ensure the analyzed program to be well-borrowed and then exploits Rust’s borrow mechanism to associate data structures and references with potentials. We adapt the recently proposed Low-Level Borrow Calculus (LLBC) ( Ho and Protzenko, 2022 ) , which is based on Rust’s MIR, formulate a resource-aware version called Resource-Aware Borrow Calculus (RABC), and devise an AARA type system on RABC. Secondly, Rust’s borrow mechanisms, especially mutable borrows, pose a non-trivial problem for AARA in tracking potentials along borrowing. For example, one can mutably borrow a value v from a location \ell with p(v) units of potentials, update the original value to v^{\prime} , consume or store some potentials, and end the borrow to return v^{\prime} back to the location \ell with p^{\prime}(v^{\prime}) units of potentials. Note that the pre- and post-potential functions p and p^{\prime} can be different; however, in a typical AARA type system, types are invariant , i.e., once a location \ell has a resource-annotated type that specifies a potential function, the type would not change. To tackle this challenge, we propose prophecy potentials , which are inspired from prophecy variables ( Jung et al., 2019 ) and RefinedRust’s borrow names ( Gäher et al., 2024 ) . Intuitively, prophecy variables provide a compositional reasoning mechanism for future states, as they stand for the value, returned to a location after a mutable borrow ends. When a mutable borrow of a location \ell with the potential function p starts, RaRust generates a prophecy potential function q