I'm kind of surprised that the authors went with compare-and-exchange for their ref count, rather than get-and-increment. Even if the counter does overflow, it's usually detectable, and reversible. This is true even in the face of concurrent updates. The benefit is that there is only one atomic operation in the fast path.
The MPX part was a good excuse to look around at the status of MPX support. It seems GCC is the major compiler to support it, but it's under threat of depreciation because the bootsrap build with MPX has been broken for so long. Also the lack of AMD buy-in (patents?) seems like a big hinderance compared to more compatible compiler-based approaches for C memory safety, like SoftBound, CCured, etc.
I don't understand your point. If you haven't got all the source code (e.g. random drivers), you're unlikely to have any say in the language that the binary code blobs were written in either.
I was referring to your original comment: 'they only work properly if 100% of the source code is available.'
This project is adding protection to the linux kernel. Now, this bounds checking could be added to a kernel build with 100% of the source code available, in which case all is good. Or, it could be added to a kernel build where some of the drivers are available only in a 'binary blob' form. In which case, rewriting the kernel in Ada (or whatever) would not help you with the binary blobs, since they are out of your control. So, as I understand it, your point of 'only working properly if 100% of the source code is available' would seem to be just as true for a code rewrite as it is for the paper's approach to the problem.
"- separated kernel and process address space (both can use the whole
address space). Such an implementation, to be efficient, requires a
dedicated support from the underlaining architecture. It is the case of
the primary and secondary context register used in conjunction with the
ASI identifiers on the UltraSPARC (sun4u/sun4v) architecture.
The only limitation to kernel (and processes) virtual space on systems
implementing an userland/kerneland separated address space is given by the
architecture (UltraSPARC I and II can reference only 44bit of the whole
64bit addressable space. This VA-hole is placed among 0x0000080000000000
and 0xFFFFF7FFFFFFFFFF).
This memory model makes explotation indeed harder, because we can't
directly dereference the userspace. The previously cited NULL pointer
dereferences are pretty much un-exploitable.
Moreover, we can't rely on "valid" userland addresses as a place to store
our shellcode (or any other kernel emulation data), neither we can "return
to userspace"."
This already exists on x86_64 Linux in the form of SMEP and SMAP.
> With SMEP enabled, it’s no longer possible to map exploit payloads in userland, as the CPU will trigger a fault if it attempts to execute those user pages in kernel mode
So Rust it is then, eh? Could work through the kernel module by module to rewrite it in rust, but it'd be a multi-year process (like Firefox's rewrite has been).
You mean rewriting unsafe C code to Rust by annotating it with `unsafe` keyword? :-) Try to write in Rust something which would touch bare metal hardware. It would be PITA, it would be full of unsafe keywords and assembler code so it would possibly result in similar amount of bugs in the end, just in different parts.
This is empirically not true if you look at the usage of unsafe in pure Rust kernels. Yes, there is assembly needed, and some unsafe Rust code, but it's very possible to wrap up unsafe operations in safe APIs.
For example, the kernel repository for Redox (a written-in-Rust OS project) appears to have 242 usages of the unsafe keyword (including comments bc lazy), out of 18205 lines of Rust source.
You can wrap most unsafe operations to be safe with proper checks, I've done it myself and it's much less than you would expect since a lot of the memory accesses can be made safe trivially.
Just to turn this discussion towards the practical aspect: does anyone know if a concrete effort has been made to sound out Torvalds and the other senior kernel devs about accepting Rust into the kernel?
I would imagine that initially as PoC one can start by implementing a simple module... obviously a small portion of the Rust stdlib and runtime needs to be ported and of course rustc needs to be integrated into the kernel toolchain...
Perhaps someone has done it privately (i.e., without attempting to submit patches back to source)?
I don't think you actually solve any of the really hard kernel problems with your choice of programming language.
The big problems tend to be about hardware support
(all those drivers, all the odd details about different platforms,
all the subtleties in memory management and resource accounting)
I think what he is saying is that rewriting c->(e.g.) rust doesn't improve make progress on any of the design problems in the linux kernel.
In [2] (2013) he expands on that, essentially explaining how well C maps to machine instructions, and how that helps optimise the kernel.
Personally I think Rust maps very well to machine code, and although it doesn't solve design problems, I do think it saves a lot of time debugging the security flaws and bugs that can result from memory bugs.
I tend to agree with his point that you may perhaps not solve design and driver problems just changing language, but can anyone dispute that a memory-safe language can at least help eliminate routine programming pitfalls like off-by-one, null deferences, double-free and so on? And these are the types of innocuous and inadvertent errors that are exploited by black-hats, sometimes with costly consequences.
I don't see a strong argument against a memory-safe language, although granted it won't solve architectural and hardware issues. Perhaps the effort to support, say Rust, in the kernel is just not worth the trade-off at this point? Perhaps no one has taken on the mantle for doing so? But I can't see how one can categorically argue against it...
> Just to turn this discussion towards the practical aspect: does anyone know if a concrete effort has been made to sound out Torvalds and the other senior kernel devs about accepting Rust into the kernel?
This is not how things work. You don't arrive at changes like this by out-talking Linus. Talk is cheap and Linus is opinionated.
You need to demonstrate that what you want to do is worthwile, i.e. is not only feasible but also provides a payoff that carries the weight of what you're proposing.
You also need to be fiercely committed to your idea and to making it happen inside mainline Linux.
In other words, show me the code (and maintain it out-of-tree for some time, tracking upstream changes and gathering support from other developers).
Don’t think it’ll ever happen. More likely something like redox will get to the point that it’s production-ready and people will just stop using Linux.
I don’t think it’s far off, at least for vms, tbh.
Yeah that may be a really good upside to VMs, that they enable new OSs to have a more level playing field with the established OSs. Letting the VM layer handle all the messy details of real hardware.
..and of course Rust needs to be ported and have its .. "runtime" fixed for all platforms linux runs on. Otherwise this will be a decent way to kill off a bunch of platforms.
Was going to point this out too... Having the Rust compiler support all platforms GCC is able to target is going to be a massive task - nevermind maintaining them.
That's one of the main advantages of C - it runs on pretty much everything.
Not necessarily, Google's approach has been to forbid kernel access (ChromeOS), to make a big pain to use native code only for specific use cases (Android) or to develop a new microkernel in a mix of C++/Rust/Go/Dart (Fuchsia).
Seriously? What is it worth people thinking that Rust is the only choice for such things? Memory safety is nothing new. Languages like D, Nim, and Swift all allow for the possibility of both memory safety and low-level access.
Memory safety without GC and with zero-cost abstractions is the combination rust enables. Nim and swift (and Go) strictly require a GC and D without GC doesn't work without heavy lifting.
What's wrong with garbage collectors? Depending on the type, you can get performance characteristics better than or similar to destructor-based management.
Even current operating systems use forms of garbage collection (such as refcounting) to track resources.
The problems with a GC (in the context of embedding it in a larger codebase written in a another language) is that the calling conventions are more complicated and the existence of a GC (especially mark-and-sweep GCs) means that the embedding is not "seamless". Even with a C FFI interface it's still harder than (for example) using Rust or C in such a project.
And if both languages have GC, then you're in even more trouble.
For what language runtime are the calling conventions an issue? Even the most calling-convention dependent GC I can think of (GHC Haskell's) can handle standard C ABIs and .NET is a good example of making this whole process relatively seamless. If you can export a C FFI with pinned pointers in both directions, I don't see how it's any harder than Rust or C.
The multiple GCs in a process issue is usually due to the collector not playing nice with signal/exception handler installation when using safepoints, which is purely an issue of lazy implementations. There's even ways to collect cross-heap cycles when working this multiple GCs (Xamarin on Android does this fairly well).
Only in GC languages that don't offer good language features for value types, which usually isn't the case with the ones targeted for low level systems development.
Modula-3 either uses one of those techniques, or is not memory safe. (Looks like primarily the first one- manual deallocation is unsafe and it relies on GC for the rest?)
Cyclone and ATS do not have Rust's combination of ownership and borrowing.
Ada's model for safe allocations is far more limited than Rust's, however. Particularly in ways that would require more unsafe code when writing a kernel.
I don't see why, given that Unchecked_Deallocation calls should only exist inside data structure implementations, never called directly from safe code.
Which should just use controlled types, pools or standard containers.
Right, but you don't have to rewrite it at once. There are certain areas of the kernel that have historically had more issues, are at higher risk of attack, etc. Those will make up far less code than 20 million lines, and you can start there.
It does say that the 20 million lines statistic isn't sufficient to dismiss the idea. That's not saying much, but I think it's a valid response to someone pointing out that the Linux kernel is 20 million lines.
you're comparing apples and rutabagas. code line count is a hilariously inaccurate way to measure the complexity required for a portable OS kernel vs a userspace application.
> code line count is a hilariously inaccurate way to measure the complexity required for a portable OS kernel vs a userspace application
I never said that. My whole premise is that you can't say anything like this by just saying code count on two very different projects. Maybe you didn't read my comments properly.
What's the relation with Rust?
I don't see it mentioned in the post, it affects Firefox before version 57, but not 57 (not that there wasn't any Rust code in Firefox before 57) and it seems to be a bug in DOMParser, which as far as I know is not written in Rust.
Rust is not safe. ATS, Pony, C#, Java, lisp come to my mind. But maybe even D, Nim, swift, crystal. Singularity/Midori or the LispM were good candidates.
And it cannot be a monolithic kernel of course.
If someone was going to deploy a version of the Linux kernel with SoftBound (which is among other things what this paper suggests), they would have done so by now. It hasn't happened, because (a) contrary to what that paper suggests, performance really is a concern; (b) the entire ecosystem of C is what makes it so popular, not the language itself. Replacing the runtime is a huge amount of work.
It's possible to program in C in a way that is memory safe and verify it programmatically (even with memory allocations and recursion). It's even do static verification of the absence of runtime errors, arithmetic overflows, inconsistent locking, etc. Best tools are commercial unfortunately.
A static checker for C code can do the similar checks that the borrow checker in Rust does. Essentially it enforces a variation of linear type system. Note that many things for Rust are on ideas from Cyclone [1], that was a research project to provide minimal extensions to C type system to ensure memory safety.
I read the Cyclone papers when I designed the original Rust borrow checker, and we spoke to Dan Grossman.
Cyclone only works because it uses garbage collection for the heap. There is a uniqueness extension, but it is limited compared to what Rust can do. (See Grossman's "Existential Types for Imperative Languages" presentation for details.) The uniqueness extension was not designed to (and is not flexible enough to) supplant the garbage collector in most real-world projects.
This theoretical static checker for C code would not be compatible with virtually any existing C code in the wild, and so it would be effectively a new language.
That's not really relevant when talking about the linux kernel, though, is it ? There's tons and tons of open-source code that could just run clang-analyze today and eliminate swathes of memory bugs.
Static checker can work in principle on binary code. Alternatively, one can annotate API the library provides for the static checker. This is especially feasible with C where API types and usage is typically rather simple. Clearly, this implies trusting API to be implemented correctly or at least using the static checker to prove that memory-safety bugs are originated in the library, not in the application code.
By proving that memory references don't live longer than the allocated memory.
The use of dynamic allocation must be carefully restricted and programmer may need to provide provide assertions or modify the code to pass verification.
There is two ways tho think static verification:
1. Language level verification. All valid programs are verified to be correct in respect of safety guarantees the language gives.
2. Verification of safety features that can't be proved in general. In most cases it's possible to write program in a way that it can be verified to be correct, but finding a way to write provably correct program may need some work.
Easy just like any compiler for a memory safe language.
There might exist logical bugs, but the language semantics allow for a higher thrust of code quality, assuming the binaries haven't been tampered with.
Every line of C code is unsafe, specially if the binary was compiled with -O3.
Regarding Rust, the only issue is lack of support for binary libraries in Cargo, one needs to call rustc directly.
Linux doesn't do any of this, and doing so is tantamount to running a borrow checker on the code, which requires more information than is present in vanilla C.
I wonder what makes C so different from Ada where static verifies are used successfully. Is it because typical C code uses way too many pointers making full static verification much harder?
Language semantics, most of C errors that lead to memory corruption are simply forbidden in Ada.
There is no way to corrupt memory in Ada unless you explicitly import one of the Unchecked packages and ask the compiler permission to do naughty stuff.
Note the article you're citing is going from Ada (already strong safety checks, but you can still write bugs, just not a whole class of them) to Spark2014, so formal proof of absence of runtime errors (first) and automated verification of functional properties. Even nicer, in a stdlib, so not a toy example and something to build on... You're showing (thanks !) how to go (with some effort, but not so much) from 'so much safer than C already' to 'no bug let's move on and maybe remove all the runtime checks to get C-like performance or better'. I'd say it looks pretty cool.
However C gets the usual set of logical errors, common to any safe programming language, memory corruption caused by lack of checks on memory access and implicit type conversions, and 200+ cases of UB when taking advantage of full compiler optimizations.
Reducing the amount of possible errors per line of code is already a plus, even if doesn't remove all of them.
It's probably easier to use a language that has those guarantees already than trying to bolt them onto C. Those tools and coding standards are useful if you're constrained to using C for whatever reason, e.g. if you're on an embedded platform that only has a vendor compiler. For general purpose hardware you have a lot fewer headaches if you start with a language that was designed for safety.
And I think the compiler/interpreter can optimize the code much better when the creators know that such constructs are available in the language itself
I'm kind of surprised that the authors went with compare-and-exchange for their ref count, rather than get-and-increment. Even if the counter does overflow, it's usually detectable, and reversible. This is true even in the face of concurrent updates. The benefit is that there is only one atomic operation in the fast path.