Systems programming languages like C and C++ give programmers low-level control over resource management at the expense of safety, whereas most other
| Previous PDF | Next PDF |
[PDF] RustBelt: securing the foundations of the rust programming language
Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer 2018 RustBelt: Securing the Foun- dations of the Rust Programming Language Proc
[PDF] Utilizing Rust Programming Language for EFI - CEUR-WSorg
5 Conclusion and Future Work As discussed, Rust offers high level language se- mantics, advanced standard library with modern skill set including most of the features and functional ele- ments of widely-used programming languages More- over, Rust can be used as both a scripting language or a functional language
[PDF] Securing the Foundations of the Rust Programming Language
Systems programming languages like C and C++ give programmers low-level control over resource management at the expense of safety, whereas most other
[PDF] Understanding and Evolving the Rust Programming Language
Rust is the only language to provide • Low-level control à la C/C • Strong safety guarantees • Modern, functional paradigms • Industrial development and
[PDF] 15 The Rust programming language - Lund University Publications
This paper presents a case study of evaluating a programming language tran- sition from C to Rust through the creation and usage of a Programming Language
A Comparison of Performance & Implementation Complexity - DiVA
At the time of writing Java and C++ are the most widely used languages for systems programming As a language for systems programming Rust has the
[PDF] Future Programming Paradigms in the Automotive Industry - VDA
single programming language able to directly and adequately cover all the needs of Python, Rust, Java and Go appear to be simple and practical languages
[PDF] Patina: A Formalization of the Rust Programming Language - Dada
The Rust Programming Language [1] makes strong claims about ensuring memory safety without garbage collection We would like to prove that those claims are
[PDF] the gap inc stock
[PDF] the global city new york london
[PDF] the global city new york london tokyo pdf
[PDF] the global city new york london tokyo saskia sassen
[PDF] the global city new york london tokyo saskia sassen pdf
[PDF] the global city saskia sassen pdf
[PDF] the global city: introducing a concept
[PDF] the globalization of chinese food
[PDF] the great recession
[PDF] the great recession and charitable giving
[PDF] the great recession of 2007 09 was triggered by a
[PDF] the great recession of 2008 stock market
[PDF] the great recession of 2008 2009: causes
[PDF] the gutenberg bible was first published in
66
RustBelt: Securing the Foundations of the Rust
Programming Language
RALF JUNG,MPI-SWS, Germany
JACQUES-HENRI JOURDAN,MPI-SWS, Germany
ROBBERT KREBBERS,Delft University of Technology, The NetherlandsDEREK DREYER,MPI-SWS, Germany
Rust is a new systems programming language that promises to overcome the seemingly fundamental tradeo?
between high-level safety guarantees and low-level control over resource management. Unfortunately, none
of Rust"s safety claims have been formally proven, and there is good reason to question whether they actually
hold. Speci?cally, Rust employs a strong, ownership-based type system, but then extends the expressive power
of this core type system through libraries that internally use unsafe features. In this paper, we give the ?rst
formal (and machine-checked) safety proof for a language representing a realistic subset of Rust. Our proof is
extensible in the sense that, for each new Rust library that uses unsafe features, we can say what veri?cation
condition it must satisfy in order for it to be deemed a safe extension to the language. We have carried out
this veri?cation for some of the most important libraries that are used throughout the Rust ecosystem.
CCS Concepts: Theory of computation→ Programming logic; Separation logic; Operational semantics;
Additional Key Words and Phrases: Rust, separation logic, type systems, logical relations, concurrency
ACM Reference Format:
Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer. 2018. RustBelt: Securing the Foun-
dations of the Rust Programming Language.Proc. ACM Program. Lang.2, POPL, Article 66 (January 2018),34pages.https://doi.org/10.1145/3158154
1 INTRODUCTION
Systems programming languages like C and C++ give programmers low-level control over resource managementattheexpenseofsafety, whereasmostothermodern languagesgiveprogrammers safe, high-level abstractions at the expense of control. It has long been a "holy grail" of programming languages research to overcome this seemingly fundamental tradeo? and design a language that o?ers programmers both high-level safetyandlow-level control. Rust [Matsakis and Klock II 2014;Rust team 2017], developed at Mozilla Research, comes closer to achieving this holy grail than any other industrially supported programming language to date. On the one hand, like C++, Rust supports zero-cost abstractions for many common systems programming idioms and avoids dependence on a garbage collector [Stroustrup 2012;Turon2015a]. On the other hand, like most modern high-level languages, Rust is type-safe and memory-
safe. Furthermore, Rust"s type system goes beyond that of the vast majority of safe languages in that it statically rules out data races (which are a form of unde?ned behavior for concurrent programs in many languages like C++ or Rust), as well as common programming pitfalls likeAuthors" addresses: Ralf Jung, MPI-SWS?, jung@mpi-sws.org; Jacques-Henri Jourdan, MPI-SWS?, jjourdan@mpi-sws.org;
Robbert Krebbers, Delft University of Technology, mail@robbertkrebbers.nl; Derek Dreyer, MPI-SWS?, dreyer@mpi-sws.org.
?Saarland Informatics Campus.Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for pro?t or commercial advantage and that copies bear this notice and
the full citation on the ?rst page. Copyrights for third-party components of this work must be honored. For all other uses,
contact the owner/author(s).© 2018 Copyright held by the owner/author(s).
2475-1421/2018/1-ART66
https://doi.org/10.1145/3158154Proceedings of the ACM on Programming Languages, Vol. 2, No. POPL, Article 66. Publication date: January 2018.This work is licensed under a Creative Commons Attribution 4.0 International License.
66:2 Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer
iterator invalidation [Gregor and Schupp 2003]. In other words, compared to mainstream "safe" languages, Rust o?ers both lower-level controlandstronger safety guarantees. At least, that is the hope.Unfortunately, none of Rust"s safety claims have been formally proven, and there is good reason to question whether they actually hold. In this paper, we make a major step toward rectifying this situation by giving the ?rst formal (and machine-checked) safety proof for a language representing a realistic subset of Rust. Before explaining our contributions in more detail, and in particular what we mean here by "realistic", let us begin by exploring what makes Rust"s type system so unusual, and its safety so challenging to verify.1.1 Rust"s "Extensible" Approach to Safe Systems Programming
At the heart ofthe Rust type system is an ideathat has emerged in recent yearsas a unifying concept connecting both academic and mainstream language design:ownership. In its simplest form, the idea of ownership is that, although multiple aliases to a resource may exist simultaneously, performing certain actions on the resource (such as reading and writing a memory location) should require a "right" or "capability" that is uniquely "owned" by one alias at any point during the execution of the program. Although the right is uniquely owned, it can be "transferred" from one alias to another-e.g., upon calling a function or spawning a thread, or via synchronization mechanisms like locks. In more complex variations, ownership can besharedbetween aliases, but only in a controlled manner (e.g., shared ownership only permits read access [Boyland 2003]). In this way, ownership allows one to carefully administer the safe usage of potentially aliased resources. Ownership pervades both academic and mainstream language design for safe(r) systems pro- gramming. On the academic side, many proposals have been put forth for usingtypesto enforce various ownership disciplines, including "ownership type" systems [Clarke et al.1998]; region- or typestate-based systems for "safe C" programming in languages like Cyclone [Jim et al.2002] and
Alms [Tov and Pucella 2011], and Mezzo [Balabonski et al.2016]. Unfortunately, although these languages provide strong safety guarantees, none of them have made it out of academic research into mainstream use. On the mainstream side, "modern C++" (i.e., C++ since the 2011 standard [ISO Working Group 21 2011]) provides several features-e.g., smart pointers, move semantics, and RAII (Resource Acquisition Is Initialization)-that are essentially mechanisms for controlling ownership. However, while these features encourage safer programming idioms, the type system of C++ is tooweak to enforce its ownership disciplines statically, so it is still easy to write programs with unsafe
or unde?ned behavior using these features. and the reason perhaps that academic e?orts have not taken o? in practice-is that no language can account for the safety of every advanced form of low-level programming that one ?nds in the wild, because there is no practical way to do so while retaining automatic type checking. As a result, previous designs employ type systems that are either too restrictive (i.e., preventing programmers from writing certain kinds of low-level code they want to write) or too expressive (i.e., encoding such a rich logic in the type structure that programmers must do proofs to appease the type checker). Rust addresses this challenge by taking a hybrid,extensibleapproach to ownership. The basic ownership discipline enforced by Rust"s type system is a simple one: If ownership of an object (of type T) is shared between multiple aliases ("shared references" of type&T), then none of them can be used to directly mutate it. This discipline, which is similar in spirit to (if di?erent in detail from) that of several prior academic approaches, is enforceable automatically and eliminates a wide range of common low-level programming errors, such as "use after free", data races, and iterator invalidation. However, it is also too restrictive to account for many low-levelProceedings of the ACM on Programming Languages, Vol. 2, No. POPL, Article 66. Publication date: January 2018.
RustBelt: Securing the Foundations of the Rust Programming Language 66:3 data structures and synchronization mechanisms, which fundamentally depend on the ability to mutate aliased state (e.g., to implement mutual exclusion or communication between threads). Consequently, to overcome this restriction, the implementations of Rust"s standard libraries make widespread use ofunsafeoperations, such as "raw pointer" manipulations for which aliasing is not tracked. The developers of these libraries claim that their uses ofunsafecode have been properly "encapsulated", meaning that if programmers make use of the APIs exported by these libraries but otherwise avoid the use ofunsafeoperations themselves, then their programs should never exhibit any unsafe/unde?ned behaviors. In e?ect, these libraries extend the expressive power of Rust"s type system by loosening its ownership discipline on aliased mutable state in a modular, controlled fashion: Even though a shared reference of type&Tmay not be used todirectlymutate the contents of the reference, it may nonetheless be used toindirectlymutate them by passing it to one of the observably "safe" (but internallyunsafe) methods exported by the object"s API. However, there is cause for concern about whether Rust"s extensible approach is actually sound. Over the past few years, several soundness bugs have been found in Rust, both in the type system itself [Ben-Yehuda 2015a,b;Turon 2015b] and in libraries that useunsafecode [Ben-Yehuda 2015c; Biocca 2017;Jung 2017]. Some of these-such as the Leakpocalypse bug [Ben-Yehuda 2015c]-are quite subtle in that they involve aninteractionof multiple libraries, each of which is (or seems to be) perfectly safe on its own. To make matters worse, the problem cannot easily be contained by blessing a ?xed set of standard libraries as primitive and just verifying the soundness of those; for although it is considered a badge of honor for Rust programmers to avoid the use of unsafe code entirely, many nevertheless ?nd it necessary to employ a sprinkling ofunsafecode in their developments. Of course, it is not unusual for safe languages to provide unsafe escape hatches (e.g., Haskell"s unsafePerformIO, OCaml"sObj.magic) to work around limitations of their type systems. Butunsafecode plays such a fundamental role in Rust"s extensible ownership disciplinethat it cannot simply be swept aside if one wishes to give a realistic formal account of the language.
The question remains: How can we verify that Rust"s extensible approach makes any sense? The standard technique for proving safety properties for high-level programming languages-namely, "progress and preservation" introduced byWright and Felleisen[1994]-does not apply to languages in which one can mix safe and unsafe code. (Progress and preservation is aclosed-worldmethod, which assumes the use of a closed set of typing rules. This assumption is fundamentally violated by Rust"s extensible, open-world approach.) So, to account for safe-unsafe interaction, we need a way to specify formally what we are obliged toproveif we want to establish that a library employing unsafecode constitutes a sound extension of the Rust type system. Luckily, decades of research in semantics and veri?cation have provided us with just the right tools for the job.1.2 RustBelt: An Extensible, Semantic Approach to Proving Soundness of Rust
In this paper, we give the ?rst formal (and machine-checked) account of Rust"s extensible approach to safe systems programming and how to prove it sound. For obvious reasons of scale, we do not consider the full Rust language, for which no formal description exists anyway. Instead, after beginning (in§2) with an example-driven tour of the
most central and distinctive features of the Rust type system, we proceed (in§3) to describe
λRust, a continuation-passing style language (of our own design) that formalizes the static and lifetimes, andlifetime inclusion-which are fundamental to Rust"s ownership discipline-in a manner inspired by Rust"s Mid-level Intermediate Representation (MIR). For simplicity,λRustomits someorthogonal features of Rust such as traits (which are akin to Haskell type classes); it also avoids the
model featuring only non-atomic and sequentially consistent atomic operations. Nevertheless,λRust
Proceedings of the ACM on Programming Languages, Vol. 2, No. POPL, Article 66. Publication date: January 2018.