Metraipolis › archive › dc_143fc5d47efe
Verified Implementation of the Next-gen Borrow Checking Algorithm for Rust via Abstract Interpretation — arXiv:2611.06319
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06319
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:32:31.028Z
- SHA-256 of the archived text
74824121fa6fcac3e3f7423a55ab92a3ffa01669e13640faee3b5f7312ce4d42- Stable URL of this page
https://metraipolis.com/documento/dc_143fc5d47efe
How to cite
Verified Implementation of the Next-gen Borrow Checking Algorithm for Rust via Abstract Interpretation — arXiv:2611.06319 — arXiv (en), https://arxiv.org/abs/2611.06319 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_143fc5d47efe (Metraipolis archive dc_143fc5d47efe, sha256 74824121fa6fcac3e3f7423a55ab92a3ffa01669e13640faee3b5f7312ce4d42)
BibTeX
@misc{dc143fc5d47efe,
title = {Verified Implementation of the Next-gen Borrow Checking Algorithm for Rust via Abstract Interpretation — arXiv:2611.06319},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06319},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_143fc5d47efe; sha256 74824121fa6fcac3e3f7423a55ab92a3ffa01669e13640faee3b5f7312ce4d42},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06319. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Borrow checking is a central mechanism for Rust to ensure temporal memory safety. Its correctness is based on the intuition that the Aliasing XOR Mutability discipline guarantees that programs without borrow errors inherently could not access invalid references (i.e., pointers). However, existing work on formalizing borrow checking treats it either as a component of type systems or as symbolic execution describing resource transfer. None provides a direct explanation of the correctness of borrow checking algorithms such as Non-Lexical Lifetimes (NLL) or Polonius in the official Rust compiler that function more like static pointer analysis. We take a first step toward solving this problem by formalizing Polonius, the next-generation borrow- checking algorithm for the Rust compiler, on a core subset of Rust. We prove its correctness by showing that any program accepted by Polonius does not access invalid references at runtime. The key observation is that, when borrow checking is performed lazily, Polonius could be treated as a forward abstract interpretation on abstract domains recording pointer aliasing (borrowing) relations. By providing a concrete semantics that formally describes the Aliasing XOR Mutability discipline, we prove the soundness of this abstract interpretation, from which we derive memory safety of checked programs. This formulation of Polonius is implemented and formally verified in the abstract interpretation framework of CompCert. The correctness proofs are generated by an agentic AI under human guidance using paper proofs as proof outline. To the best of our knowledge, this is the first comprehensive formalization and verification of a borrow checking algorithm as manifested in the Rust compiler. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.PL, nuovi lavori del giorno). Categorie arXiv: Programming Languages (cs.PL). Pagina del lavoro: https://arxiv.org/abs/2611.06319 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-05T18:22:04.037Z dalla pagina https://arxiv.org/list/cs.PL/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).