This isn't unique to kernels. The standard heap-allocated vector type in Rust (on which the standard string type is based) is full of unsafe blocks: https://doc.rust-lang.org/src/alloc/vec.rs.html The problem of implementing a heap-allocated vector, with some elements uninitialized but available for use and with the ability to reallocate the entire vector and copy the members, is not a problem that lends itself well to the borrow checker's view of the world, so raw pointers are a fine way to solve it. Use of vectors themselves, their iterators, references to items in the vectors, etc. does match the borrow checker's view of the world, so the average Rust program running in userspace doesn't have to care that the standard library itself isn't implemented in safe Rust.
So copious usage of the "unsafe" keyword in a codebase can be a sign that the code as a whole is more safe: instead of having large portions of the code be unsafe (or instead of having the code pretend it's containing unsafety when it's not), only the parts that need raw memory access use it, and they maintain invariants used by the rest of the code.
It is certainly possible to do better - there are no machine-checked proofs that unsafe code does what it claims and upholds the invariants it claims to uphold. There could be, and I'm really interested to see what people do with languages that lend themselves better to proofs (usually dependently-typed, Turing-incomplete-but-very-powerful languages). But right now the state of the art is that such languages are a pain to use and writing proofs is even more of a pain. I think that's where the compromise is right now. The borrow checker is, arguably, a system for proving things about your code; it just only knows how to prove specific things. (Way more than C's type system proves, but way less than you'd prove in a perfect world.)
https://i.imgur.com/oqtEDoV.png
From miri, page 27 in their slide deck. The miri project has changed a lot since the slides were written — and it is now close to being merged into rustc.
Once you can say that, you can prove it. The proof techniques are well known. The first step is to be able to talk about it within the language. A predicate like
initialized(A,i,j)
meaning that array A is initialized from elements i to j inclusive is all that's needed.
Then, when you write assert(initialized(A,i,j));
A[j+1] = 0;
assert(initialized(A,i,j+1);
you've expressed how much of the array is now initialized. Then automatic theorem proving takes over and proves that if the first assert is true, so is the second.This eliminates the need for "unsafe" in many places. A fancier type system is not needed.
It only takes one wrong piece of unsafe code to enable a buffer overflow attack.
The "Weak" problem is mostly a back-pointer problem. If you had some way to talk about a back pointer locked in an invariant relationship with a forward pointer, that would deal with back pointers for trees and such. I sketched out a solution for this on YC earlier this year.[1] This doesn't deal with true circular lists, but those are relatively rare; people tend to use arrays for that today.
It's good to hear this criticized from someone who does program proving. I used to do that, a long time ago. What I usually get from the Rust crowd is macho assertion that they don't need checking of their unsafe code. History and the CERT archives indicate they do.
You mentioned Vec right after that. Which is interesting, because Vec deals with uninitialized memory just fine. https://doc.rust-lang.org/std/vec/struct.Vec.html#method.res... allocates more space, but doesn't allow you to read it unless you explicitly add elements.
> It only takes one wrong piece of unsafe code to enable a buffer overflow attack.
Isn't that the case for every language? Here, you can limit the unsafe bit to the underlying datastructure if any unsafe actions are required. Maybe Vec uses some unsafe bits, maybe not - but the usage of it is all safe code.
https://docs.microsoft.com/en-us/dotnet/csharp/language-refe...
Among other things, you need to opt in to unsafe with the `/unsafe` compiler flag. I'm pretty much 100% certain that the `unsafe` keyword applied to scopes does not mean "treat the contained scope as if it were safe, but permit the use of unsafe operators" which is how it works in Rust.
Edit: to put some more words here, I think what you may be saying is "the unsafe fragment of C# behaves like Rust", which sounds sane to me: `unsafe` decorates regions and the compiler will complain at you if you use unsafe things outside such scopes. When I said "C#" I meant the larger language in which programs are either "safe" (verifiable) or not, and for which `unsafe { .. }` forces you into the unsafe fragment.
Rust doesn't have safe and unsafe language fragments; there is one language which follows rules similar to (as you say) unsafe C#, but which advertises itself as safe. In that language, `unsafe` moves you back in to "safe" code (or we could agree that it was never safe in the same sense that languages like C# are).
If it were otherwise, no C# program would compile without "unsafe", because large parts of the standard library core (stuff in System) is unsafe. The only reason why "unsafe" is useful is precisely because it lets you isolate unsafe operations in a way that lets safe code invoke into them (assuming that you uphold your safety guarantees).
The /unsafe switch is a different thing - it needs to be turned out for the C# compiler to allow "unsafe" anywhere in its input, and is basically a project-level declaration that "this has some unsafe code somewhere in it".
There are deployment scenarios, like IIS, where admins can disable the execution/loading of Assemblies with unsafe code.
Nor does "unsafe" breaks verification by itself - it's only the specific features that you might use inside (like pointer arithmetic) that would do so, and even then not all of them. For example, C# requires "unsafe" for any use of sizeof() that is not known at compile-time, and for which it needs to emit the sizeof IL opcode. So e.g. sizeof(int) is okay, but sizeof(IntPtr) is unsafe; also, sizeof all structs are considered unsafe. However, the IL opcode for sizeof is not unverifiable, and so such an assembly would pass verification, despite requiring "unsafe" in C#.
Buffer overflows in C are caused by accessing uninitialized memory, regardless of why the program does it (how big is it vs null pointer derefs vs various other ways).
Rust does solve that problem at the language level. There's no such thing as an uninitialized pointer, which is the only right solution I'd argue. If you do access out-of-bounds in a safe block, you panic, not cause a vulnerability. How is the problem not solved by this, combined with iterators?
What you're talking about, tracking uninitialized/initialized at runtime, can totally be done in rust too, e.g. with a [Option<T>] or such... but then you'll obviously pay the runtime price of doing such checking.
The more common case though is someone wishes to have a mutable vector which has a capacity and an accessible subset of data, which Vec implements.
What you're claiming can be proven easily is not so trivial to prove for the common case; it may be `j+n` where `n` may derive from user input.
It would be cool if blocks of rust now could be "theorem-proved-unsafe", but I think realistically it's a huge amount of work for a small win.
Writing and proving theorems about code is typically much more time-consuming than exhaustively testing or informally verifying a block of code via review, and when the unsafe code is small and simple enough, the results we get are already "good enough".
> It only takes one wrong piece of unsafe code to enable a buffer overflow attack.
Yup, though for many programs you can entirely avoid unsafe code (outside of the well-reviewed and well-tested stdlib), and you can pay special attention to unsafe code in review and testing.
That's a damn sight better than other low level non-gc'd languages like C++/C where the default is unsafe and all code is suspect.
What exactly makes it "poorly chosen"?
But it disagrees with all past use of the name “vector” in mathematics and numerical computing, which is reasonably consistent and well defined and dates from the mid-19th century.
A Rust (C++, etc) Vec<T> of length n where T implements addition and multiplication in a way that satisfies field laws is the "reasonable" representation of a n length "mathematical" vector over the field T. It just generalizes that storage type to situations where T is not a field.
It doesn't support addition of two vectors and multiplication by a element of T using the normal mathematical syntax, but that's a fairly reasonable choice given how we regularly use vectors as a sequence of independent numbers and the different priorities for math syntax and programming language syntax.
On the other hand, a mathematical vector is not a resizable thing: a vector in R² is of a fundamentally different type from a vector in R³.
A type named "vector" should be more like Vec<T, n> for some type T and some integer n. Failing that, the reasonable representation of an n-length mathematical vector, in C++/whatever, is an array.
The idea of appending an element to make a new vector is however extremely common, particularly in induction like proofs.
Vec<T, n> is in a sense already what we have, it's just that we are not capable of storing the n in the type information^0 so we store it at runtime.
^0 For a number of reasons. n can change with mutation while types can't. We don't necessarily know n ahead of time when building a vector (which happens in math too) but we have to know types at compile time. And we just don't have a great way of storing numbers in types in Rust anyways.
Also more importantly in mathematics vectors aren’t really growable. When you change the number of elements you change the dimension (and thus the “type” for that vector). It is then ill-defined to add two vectors of different dimensions.
The advantage is that you should be able to write application code without unsafe blocks; they should be in a library. And the library has a contract: if unsafe behavior does leak outside the library, it is clearly the fault of the library, and can't be blamed on the (safe) caller.
It is better to know that only a specific subset of the codebase could be responsible for memory unsafety even if that behavior may leak. If nothing else, it helps focus reviewing and testing effort.
On some level, yes, it's the best we can do. Unless you want to add hardware semantics into your language. Unless you do, writing two bytes to 0xB8000 is going to be an arbitrary memory access. At least, that's my take.
The two places of unsafe are barely just the minimum.
When interacting with UEFI you have to include a bunch more unsafe clauses since you'll be FFI'ing to PE-calling convention C code to wrap the UEFI methods. You'll have to allocate memory without being able to malloc which means passing a raw memory block, allocate in C, to rust and tell the frame allocator to use that.
Setting up a syscall is unsafe, you have to use a naked function with internal unsafeness and the entire construct is unsafe because a syscall can easily crash the system if it doesn't return properly.
You will have to dereference null pointers because on kernel level a null pointer is a valid address (my UEFI places a memory region at 0x00 for about 30 pages which is a great starting region) unless you waste a buffer region. But Rust and LLVM don't allow that safely at all.
The very nature of a kernel is unsafe. It has to do very unsafe things in an unsafe way to enable software running in Ring 3 to make safe assumptions about it's environment as long as it gets scheduled.
Of course, Rust is somewhat better than C since it's type system allows one to express things without the entire construct blowing up every 2 minutes unless you're developing a kernel for years.
Yes, this is only one subsystem. Obviously, as you say, there are more than that in a realer kernel. But even larger ones have still shown that the vast majority of their stuff works in safe code.
> Setting up a syscall is unsafe
Fun detail, this isn't unsafe anymore on x86! You don't need naked functions; you can
extern "x86-interrupt" fn some_handler()
and LLVM knows how to properly do the codegen! This is kinda emblematic of what I mean: you can do more with safe code than you'd think.On x86, not x86-64, which has the syscall instruction, replacing interrupts for syscalls (technically x86 had sysenter)
The syscall instruction requires writing the address of the syscall function into the LSTAR MSR. Additionally, the syscall entry is purely naked, only the EIP and Segments are preserved and in a way that requires the caller to handle it.
Sysret is also particularly nasty in being unsafe in various ways, including being buggy on all Intel CPUs.
Atleast it's faster than interrupts and you don't technically need the -mno-redzone for it if it's not part of your interrupt handling code.
However, those two calls to unsafe rely on an invariant maintained by the rest of the code that is not marked unsafe. Effectively, the entire module has to be treated as unsafe code by the programmer.
The question is, how much code is in this state, vs being purely safe? My experience and that of others shows that it's generally a smaller amount than many people not experienced with Rust assume.
Basically, I find the "there's always unsafe code somewhere at the bottom and therefore it's the same as 100% unsafe" to be overly reductive.
I totally agree; it's not the same. However, I think there is disagreement about whether saying only "there's always unsafe code somewhere at the bottom" is better or worse than saying "it's 100% unsafe".
I tend to write some sketchy unsafe code, and the only thing I can say with a straight face is "please don't use this if you care about safety", i.e. treat it as if "it's 100% unsafe". I'm slightly weirded out that Rust has a keyword that amounts to "I understand UB really well; tell others to trust me on it transitively".
I'll be less weirded out when the UB story gets shaken out more, or if cargo gets an "audit-unsafe" option that shows you all unsafe blocks you transitively depend on (does that exist yet?). Still like Rust, but letting randoms write unsafe code is scary.
Are you saying that Rust doesn't have a better memory safety story than C++? In practice, that hasn't been our experience.
I don't use C++ anymore, but I am not clear on how Rust has better memory safety guarantees than C++. I do like its story more, for sure, and I could see how they might turn in to guarantees (but I could also believe that someone could identify a similarly safe fragment of modern C++, and don't want to start that).
Edit: will rust-lang.org take a PR changing "guaranteed memory safety" to "memory safety story"? ;)
I hope not. The value proposition of Rust is that if you stick to writing code without unsafe, then you have a guarantee that you will not fall victim to memory unsafety unless there is a bug in the language or in some unsafe block in a dependency you're using.
Personally, I find your quibbling in this thread pretty strange. Rust very clearly provides more memory safety guarantees than C++. For starters, you could not take the guarantee I just stated above and apply it to C++ because there is no such thing as "C++ without unsafe blocks."
I have used other memory safe languages, and I find their guarantees qualitatively different from Rust. I would say of them "you will not fall victim to memory unsafety unless there is a bug in the language or in the standard library" with no mention of other dependencies. The standard library is then fairly thoroughly audited.
By comparison, you have e.g. the `memmap` crate, which I like and use, written by serious people known to you, where `unsafe` is used in construction of the memory map. It is then on the user to ensure that there are no concurrent writes to the backing file for the lifetime of the map, at the risk of (as I understand it) UB. Would you describe such a program as "safe"? Or at least, can you understand why I might not? If a concurrent modification happens, is the bug to be found in the `unsafe { MmapMut::map_mut(&file)? }` block, or perhaps farther away where you safely open and modify the file before dropping the map?
I'm sorry if this comes off as quibbling; I do actually care about getting these things right, as I want to rely on them and do more interesting things (e.g. de-abomonate mapped memory).
What I should have written is: "you will not fall victim to memory unsafety unless there is a bug in the language or in the standard library, or you explicitly opt out of safety". Using `unsafe` in C# is opting out of its safety guarantees (and requires the `/unsafe` flag); I'm pretty sure none of the C# team would say "guaranteed memory safety" of unsafe C#. I expect the same is true of Java, and have no clue about Python.
To the extent that we are talking about unsafe C#, I think you are right; it's mostly the same as Rust. But, no one would claim that unsafe C# has "guaranteed memory safety" where the guarantee is "as long as your code and all the code you bring in don't have memory safety bugs". At least, I hope not.
My original point was just meant to be that there is the risk of harm when you try and quantify a language as "more safe" because there are fewer regions where unsafe operations are permitted. People might read "guaranteed memory safety" and misunderstand what it means, as evidenced by me not actually knowing what it means.
"Rust is not perfect, so it's basically the same as C"
The fact that "american fuzzy lop" and "syzkaller" have gone through the kernel and found dozens of use-after-free's (see https://github.com/google/syzkaller/blob/4bd70f/docs/linux/f...), shows that even incredibly carefully programmed C messes up in totally rote ways.
The basic cleanup code which is able to be exploited here would not be in an unsafe block if this were rust. In fact, because rust abstracts memory management out better, most of the cleanup code wouldn't exist at all.
Rust also allows better abstractions. For example, Rc<T> in rust is much easier to use without screwing up than the manually handled reference counters littered throughout the kernel. It seems obvious to me that numerous deadlocks in the kernel could be avoided by not hand-rolling refcounting everywhere.
You're right that there's still the potential with rust for some code to compromise the safety of the entire kernel.
But with rust that's a subset of code, not practically every single line of the whole thing.
It seems to me like memory corruption/use-after-free/etc only being able to happen in a small fraction of code is better than it being able to happen anywhere.
Rc requires memory allocation. When you boot a kernel you don't have that. Until you set it up, you can't use anything that requires a heap, only stack values.
The best solution I found is to use C code to allocate raw memory and then go through the elaborate process of setting up kernel address space, after which you setup a frame allocator, after which you can setup interrupts and finally use pagefaults to normally use kernel heap.
But wait there is more! During a pagefault interrupt you can't use the kernel heap in a writeful manner that is not inplace. Since a page fault during a page fault is a double fault and thusly your only option is to crash the kernel. You can only read from the kernel heap, modify in place in the heap and write to pagetables.
Same goes for some other interrupts. Which btw, violate a lot of ways Rust code likes to work. An interrupt is like a coroutine but you don't have a nice runtime that abstracts it for you, instead the IRQ just smashes into the active execution and let's hope you haven't held any locks to important kernel stuff at that moment because you will have to crack that lock open.
Sure, the kernel has reusable things like its embedded linked list etc, but they're not type-safe, and they can't represent ownership.
With rust's type-system, a generic rc-like thing could be created which is suitable for the world of the kernel, even if it's not the stdlib Rc.
Without any memory management, things get hard fast, especially considering you still need to parse the memory layout to find out which parts of memory are even usable.
That's heap vs. heap. It comes after the very brief stage you're mentioning.
I tend to think that the driver and network level, which is where most problems in the real world tend to lie, is similar to userland in how often unsafe code gets used and the impact of unsafe code on the correctness of the kernel. In fact, the fact that you can write some drivers in userland on certain OS's--and they can crash without bringing down the whole OS--is strong evidence of this.
You can write some device drivers in userspace. But you can't handle page faults in userspace. Those need to be handled by the kernel and will be 100% unsafe because any mistake will lead to a certain and quick double or triple fault.
Kernel Level Programming is very very different to normal user-level programming. There is no malloc. There is no segmentation. Nothing prevents you from dereferencing a null pointer. In fact, in kernel-land a null pointer is valid memory. You don't have any of the forgiving properties of Ring3 assembly code in kernel-land.
Once you have VMM and Paging setup, preventing a null pointer deref is not hard (simply unpage 0x0)
You don't have to go all that way to be better than C or C++. Rust can give you a submodule A whose correctness doesn't impact the safety of any uses of submodule B.
That's true, but the property I described can still help you track down the root cause and limit the number of places that interact with it.
A memory safe language for the kernel doesn't seem possible using "traditional" safety tools. I'd expect a "safer" language would look a lot like formal verification. If you can make a safer language that doesn't look a lot like formal verification, you can probably automate a lot of formal verification.
There are still some big advantages to rust. By explicitly marking unsafe code, you've made it a lot easier to figure out what needs to be focused on. I imagine you can even formally verify just the unsafe parts of your ecosystem.
Also, rusts tooling just seems more pleasant.
It was a systems programming language based on Algol and already had the notion of unsafe code for low level code.
Those modules had to be marked as UNSAFE and could only be executed if allowed to do so by the sysadmin.
Similar exemples could be provided about PL/S, PL/8, Mesa, Modula-2, Modula-3 and many others.
One big contribution that Rust brings into the table is to educate a whole generation that belives the myth that C was the very first systems programming language, that there are actually safer alternatives.
Safety vs. authorization are completely orthogonal. The former is an objective property of a program, to be established or refuted with formal proof. The latter depends on the subjective whims of one specific human being, in this case, the sysadmin. And, in my experience, the typical sysadmin is not a good enough semanticist to determine whether a program is safe or not.
Formal proofs can also contain logic errors.
Any kind of safety improvement is better than what C offers.
And my point is that this is useless in the absence of someone or something capable of reliably determining whether the code is safe to run.
> Formal proofs can also contain logic errors.
So you have competent people write them.
As for competent programmer, we all know how many corporations search who they hire.
I'm no expert, but from a layperson's perspective, the rust usage in these areas depends on a lot of "unsafe" blocks, fighting the borrow checker, etc.
Does that ratchet it down from "great" for this space to something like "ok" or "usable"?
Or is this just the best we can do in terms of a memory safe language for kernel and/or bare metal embedded?