Bootstrappable builds: how and why

Ready to give LWN a try? With a subscription to LWN, you can stay current with what is happening in the Linux and free-software community and take advantage of subscriber-only site features. We are pleased to offer you a free trial subscription, no credit card required, so that you can see for yourself. Please, join us! This year's edition of the Free and Open Source Software Yearly conference, better known as "FOSSY", moved north to the beautiful (and enormous) campus of the University of British Columbia (UBC) in Vancouver, Canada from its home for the three previous editions: Portland, Oregon, in the US. There were many different types of talks at FOSSY, from deeply technical kernel-track topics, through talks on legal and community issues, to the "FOSS in Daily Life" talks. In the "Toolchains and Other Development Tools" track, Timothy Sample gave a presentation about bootstrappable builds, which is somewhat less well-known than its cousin, reproducible builds, though LWN did look at the topic just over two years ago. In short, a bootstrappable build is one that starts with a tiny program that can build another slightly larger program, which can build yet another, and so on, until the entirety of a modern Linux user space is built from a small seed. Ultimately, it results in code with a completely understood origin—unlike a typical Linux user space today. He began by asking attendees whether they had heard of bootstrappable builds and whether they were generally familiar with the idea; he seemed impressed that the majority knew the term and that roughly half of the audience knew more than that. He said that he embarked on the path toward bootstrappable builds almost ten years ago when he started using GNU Guix (which he pronounced "geeks"—surprising me). At that time, if you were using Guix, you were contributing to it, he said with a chuckle. Guix is a "functional package manager" that is similar to (and inspired by) Nix. For both Guix and Nix, all of the software in the system is represented in a "derivation graph", which describes how to build each of its programs. There are various inputs required in order to be able to build a particular program, which are specified in the graph. The way to build each of the inputs (and, of course, the inputs to the inputs and so on) is also represented in the graph. "There's hundreds and hundreds of nodes in modern software, which is terrifyingly complex." He gave the example of a Python program. It, obviously, requires Python in order to run, but Python is a C program, so a C compiler is needed. That C compiler is written in some language, so a compiler for that language will be needed. And so on. Guix collects all of that into the graph, which is an object that can be looked at and explored. "So you start wondering who compiles my compiler's compiler compiler and where does it stop?" For a system like Debian, it stops at a C compiler binary that someone has uploaded to the repositories. For Guix, the original stopping point was a 250MB statically linked blob of GNU user-space programs. The answer to where all of that code came from is not entirely clear, of course, which was unsatisfying to Guix developers. That blob could be built reproducibly, which is good, Sample said, but does not solve the entire problem. Bootstrappable The basic idea behind bootstrappable builds is to create a system that can be built without relying on pre-built artifacts. "Can we go from zero to the modern day without having to just assume the existence of these already-built-for-us artifacts?" The classic recipe for yogurt requires some yogurt to start the process, which is like how we normally build a C compiler today—we start with an existing C compiler binary. You might think about making sourdough bread with your grandmother's starter brought over from the old country; "we're basically making C compilers with Dennis Ritchie's starter carried over from Bell Labs". It is not just C, of course, as it is true for most languages. It is something of a point of pride for languages to "self host" by writing the compiler and other tools in the language itself. It is natural for the language developers to do that, because obviously their language is the best, but it leaves something of a chicken-and-egg problem behind. Bootstrappable builds is an effort to move beyond that and to build these tools "from scratch". Reproducible builds allow people to "have more confidence that the binary you are using, which is actually executing on the computer, corresponds to the source code". A user can receive a binary that purports to come from a set of source code files, but how can they be sure that it does? With a reproducible build, they can create the binary themselves and check to ensure that it is bit-for-bit the same as what they were given. Bootstrappable builds do exactly the same thing, but they handle a different failure mode. If a reproducible build fails to verify, that's because the person who built the binary is lying or mistaken about where it came from. Bootstrappable builds can prevent the kinds of problems that Ken Thompson described in his famous Turing Award lecture: Reflections on Trusting Trust. An example that Thompson gave in that lecture asked where in a C compiler you can find the definition of "\n", Sample said. Looking in the source code of the compiler will not show a definition, it will simply provide the circular definition that "\n" is "\n"; the conversion of "\n" to ASCII ten is embodied in the C compiler binary itself. Thompson continued his lecture by noting that something rather more dangerous, such as a backdoor for the login program, could also be hidden in the compiler in the same way. It is not just C compilers, or even just compilers, that can have this sort of flaw; any self-hosting program can potentially fall prey to it. Programs of this sort can remove details from the source code and have them persist in binary form. As he was preparing for the talk, a colleague pointed him at a recent paper ("Trusting-Trust Attack against an Entire Linux Distribution through Binary Manipulation") that showed an actual attack of this sort. The researchers inserted a backdoor into the strip program on NixOS, which is run on nearly every binary that is built on the system. "They were able to backdoor basically every single program on the system in a way that's completely invisible from source-code analysis." That is the kind of attack that bootstrappable builds is meant to thwart. While the security angle is the largest benefit of bootstrappable builds, Sample said that there are software-freedom aspects too. Being able to read the source code is useful, but knowing that the source code corresponds to the running program is important as well. There is also a sense of pride that many programmers have in making their code clear and understandable. Ensuring that the code can be inspected and that all of its details exist in some available body of source code is part of that. The best way to handle bootstrapping is proactively, he said. Before a compiler is self-hosted, it is normally written in some other language; preserving that code and maintaining it alongside the self-hosted version provides a means to ensure that nothing is hidden in the binary. That is what the GNU Guile project does; it is a version of Scheme that is used by Guix and various other projects. Guile still has a C implementation of the language available to use for bootstrapping the compiler. GNU Make has a makefile, of course, but it also has a shell script in case no make is available. "We recognize that we're a fundamental build tool and that there should be another on-ramp here." For tools that only support a self-hosted build, there are some techniques that he and others in the bootstrappable-builds community use to circumvent that lack. The first is an "archaeological dig", which uses the history of the project to find a non-self-hosted version; that version is built using the tools from that era. "Then you move through history, version after version [...] until you get to the modern tool." Sometimes some of the version steps can be skipped, but overall it is a slow process. "In some ways, it just sort of kicks the can down the road; technically, you do have all of the source code", but asking someone to look at, say, 12 different versions of a tool is rather daunting; it would be nice for there to just be one version to verify. An audience member asked if this was like using the OCaml version of the Rust compiler to bootstrap to current Rust; Sample said that it was, except that the OCaml Rust compiler is no longer available. Another attendee noted that the Plan 9 C compiler that was used to build the Go programming language is still available, as is the earlier Plan 9 C compiler that built that C compiler. Those kinds of build chains are normal for Guix, Sample said. For Rust, it currently starts with the C++-based mrustc to build Rust version 1.54 or 1.56; modern Rust is 1.97 and nearly every version in between must be built, which is quite slow. When rebuilding a Guix system, Sample said, "it's very depressing when you hit this chain of Rust compiles"; an attendee said it took them three days to build that on their Arm laptop. The end result of those chains is not all that nice because of the number of steps that need to be verified. An alternative is to "purpose-build a new tool for bringing something up", which is exactly what mrustc is. The result is nicer, with a single code base to inspect, but "it takes forever" to develop a bespoke tool of that sort. He has done some of that and the result is unsatisfying at some level because the tool simply exists to enable another tool to be bootstrapped. Beyond that, the tool will require maintenance to keep up with the target tool, but it is not particularly exciting work that might attract other developers.