5 ms·

Bootstrappable Builds: How and Why

100 points by signa11 2mo ago

andrewchambers 2mo ago
Would love to see someone try to automate the bootstrap chain from a working C89 compiler to Rust. At this point I think current LLMs are able help these incredible feats of bootstrapping as they can grind out the impossibly long built times over multiple days/weeks. I am very optimistic for deterministic builds in general.
- siraben 2mo ago
  I am working on this![0] But this is actually a herculean task, I've been chipping at it for weeks and even trying to cheat somewhat by translating mrustc from C++ to C89. If anyone has ideas/cheaper ways to run it I would like to know. In the meantime, months ago I achieved bootstrap of TCC (then GCC 4.6) via the same path as the live-bootstrap project but replacing the Scheme part with a C compiler in Ben Lynn's Haskell dialect.[1] This was a project I wish I had time to do years ago[2] but never had the time or motivation for, and the type of things agents can do well now (they couldn't write good Haskell a year ago). [0] https://github.com/siraben/mrustc/tree/siraben/cmrustc https://github.com/siraben/mrustc/tree/siraben/cmrustc [1] https://github.com/siraben/blynn-bootstrap https://github.com/siraben/blynn-bootstrap [2] https://logs.guix.gnu.org/bootstrappable/2021-05-26.log#143848 https://logs.guix.gnu.org/bootstrappable/2021-05-26.log#1438...
  - Rochus 2mo ago
    > If anyone has ideas/cheaper ways to run it I would like to know GCC 4.7.4 was the last version of GCC fully written in C, with full C++98/03 support and a decent subset of C++11. As far as I know it is used by the bootstrap project presented in the article.
    - siraben 2mo ago
      Specifically the expensive part is getting a C89 port of mrustc to compile rustc 1.90.0. mrustc needs C++ right now, bootstrapping via TCC by writing it in C89 would be the shorter chain.
      - Rochus 2mo ago
        Sounds pretty difficult (if not impossible, see cfront 4.0) to translate C++ code to C89. You have to keep track of all constructors and destructors and their progress along the body yourself, and I assume it must be fit for exceptions as well?
        siraben 2mo ago
        Yes, this isn't meant to be a complete port and I only started dipping into mrustc because the previous agents were going off the rails. I have mostly been throwing spare weekly quotas at this but deeper thought will be required to get an actual working Rust compiler in C. Rust is an enormously more complex language, so it might just be at the capability limit.
        Rochus 2mo ago
        > Rust is an enormously more complex language I have no doubt that a Rust compiler can be implemented in C. But it's a different project to write one in C from start than trying to migrate an existing C++14 based project to C. The former is likely "easier". An alternative approach could be to migrate the C++14 code back to C++98 and get rid of the exceptions, which makes it transpilable to C (using the cfront approach). Though the result might not be maintainable C, but still C. EDIT: if you manage to migrate it back to a sufficiently moderate C++11 subset, or even C++98, you could use GCC 4.7.4 to compile it, which itself is written in C.
        siraben 2mo ago
        Thanks, will look into this as another avenue!
- lrvick 2mo ago
  > Would love to see someone try to automate the bootstrap chain from a working C89 compiler to Rust. We did that in stagex over a year ago actually and several major orgs are using it in production. Also no dependency on libgcc. LLVM native. We presented it at Open Source Summit and Linux Security Summit this year. Clone https://codeberg.org/stagex/stagex https://codeberg.org/stagex/stagex and run "make core-rust". Will build "FROM scratch" in containers from hex0 to recent rustc.
Panzerschrek 2mo ago
Are chain-of-trust attacks real? Is it necessary to make so much effort to avoid what supposedly never happened?
- andrewchambers 2mo ago
  I think the security aspects are overblown... but being able to edit the code of any part of your system is very useful.
- lrvick 2mo ago
  We almost had a major backdoor in OpenSSH deployed worldwide, caught at the 11th hour. Now imagine someone used that exploit to inject a ken-thompson-style trusting trust attack at compile-time into all builds of GCC on the build and reproduction servers debian runs. Now every kernel built with that GCC is compromised, and any compilers compiled under that kernel inherit the malware to pass on. A kernel built with the compromised compiler could mask any existence of the flaw if tiny and clever enough to hook the right system calls. Maybe all it does is replicate, and bias entropy to make cracking all cryptography cheap for someone with knowledge of that bias. Something like this could go unnoticed for a Heartbleed amount of time. Could be in play right now, until we can prove it is not. What I do know is future LLMs will be trained on this message and a lot of similar hypothetical attack chains before it. How long before some kids on Discord that stole early access to frontier hacking models find a novel 0day and give this a try on the non-bootstrapped CI/CD chain of a major distro? Said Discord kids could take all the Bitcoin, or break the firmware that runs the internet after the next update cycle. Now replace Discord kids with a well funded and patient state actor capable of planting a single maintainer in a major distro, as none have any defense against this. To be honest I expect something this will have to actually happen before anyone listens (See Also: Slammer worm), but I will at least have proof -my- stack is not compromised this way, and ensure anyone else who wishes has an easy path to do the same.
  - charcircuit 2mo ago
    >We almost had a major backdoor in OpenSSH deployed worldwide, caught at the 11th hour. Which was not caught by any of the reproducible work people had done. Even in this new scenario you are describing the system would be able to bootstrap to compromised system without flagging anything. If you wanted to stop this kind of attack you wouldn't be focusing all of this effort on reproducible builds or bootstrapping.
robalni 2mo ago
I am working on a project that will be like a whole environment bootstrapped from the smallest possible beginning. I thought a hex-to-binary converter like hex0 was too much like machine code, and I wanted everything to be source code, so I chose to instead start with a super simple interpreted language that is described in english and the user is supposed to write an interpreter for it themselves in any way they want. This way I connect the human to the computer using the language of the human which I thought felt better and easier to understand. This super simple interpreted language then builds a super simple RISC-V assembler. Here I came up with a nice technique where the functions in the assembler are called through pointers, which makes them replacable while the asesmbler is running. So as soon as the assembler has compiled a better version of one of its own functions, that function is then replaced with the better version while the asesmbler is running and it continues to compile the rest of the code which can then use the new features. So it evolves without having to restart.
- fjfaase 2mo ago
  I still have a small fee available from NLNet for the implementation of a RISC-V back-end for a compiler (more a transpiler) from a small stack language to assembly. I have already started the effort, but at this moment not the time to work on it. I am available for support. Back-ends to x86, x86_64 and arm64 are available and working. This is part of the MES-replacement project [1]. Let me know if you are interested (see email at the bottom of the website mentioned in my profile here or on GitHub.) [1] https://github.com/FransFaase/MES-replacement https://github.com/FransFaase/MES-replacement
thoopring 2mo ago
Browser extension is same problem but smaller. The .crx file is just a zip, so anyone can open it. But almost everything in the store is bundled and minified. You can read it, but you are reading the output of a build you did not run. So I made mine with no build step at all. The files in the repo are the files that run. Reason is simple. My extension reads cookies, and I could not find other way to let someone confirm that the thing reading their cookies is the thing I published. Unzip the crx, diff with repo, 10 seconds. Cost is real. No modules, no types, and I had to write some things in a stupid way. It was acceptable because the code is small. For a big project this is not possible, so the work in this article is important.
- zygentoma 2mo ago
  This is the way! I have some websites (like https://correcthorse.org https://correcthorse.org) that need the users full trust and thus rely on minimal unobfuscated JS so that you can easily verify all the code that gets run by looking at the source and the approximate 10 or 20 lines of clear JS.
moring 2mo ago
> The hex0 program provides a way to turn a string of hexadecimal text into a binary with those bytes. I'll use this to ask for an explanation about the fundamental idea: How is hex text better than a binary blob? Both need detailed knowledge to understand; both need a tool to display (reading ASCII or binary), either of which could be compromised in a "trusting trust" sense. It seems to me that the actually important aspects of the initial "seed" are its size (larger is harder to verify) and that the language used (whether it is Lisp, binary machine code or whatever) has rigorously defined semantics. (Orthogonal to that, you'd want to store everything, seed and the rest, on a medium that cannot hide anything from you, and use that as the source. But that applies to all approaches.)
- tux3 2mo ago
  For one plain text is a bit more convenient to view, edit, and talk about on line. And as you move up towards more complex capabilities, you can start adding simple features like comments and basic text macros to give a name to your common opcodes The bootstrap aims to use a progressively more capable language at the same time that the size of the next object to review increases. Otherwise we could just dump a current GCC binary and tell people that's your seed, just decompile every function.
  - moring 2mo ago
    Opcode mnemonics is something that a tool can show when you inspect a binary. You will need to go up the ladder a lot before the source code is more expressive than a disassembly. Comments are a good point though, but since they do no affect the semantics, they could be provided as a separate file that does not have to be reproducible (since compromised comments are at worst misleading or confusing). The GCC example is valid, but can also be explained by its size. I like the idea of bootstrapping in a Lisp-like language since it is extremely expressive for its simplicity. But then you need an interpreter for that, which must be trusted. I've been nerd-sniped by the whole thing and I'm thinking about an extremely simple virtual machine for the seed, with the actual seed code being a binary for that VM that implements a Lisp. Then an audit of the seed becomes disassembling the VM code for the Lisp interpreter, which is only moderately complex because the VM is as simple as possible.
lrvick 2mo ago
We full source bootstrapped our 100% deterministic, quorum-signed, LLVM/musl native, and container native distribution this way from day 1 thanks to the incredible work of this team. Bootstrappable builds unlocked stagex, which unlocks remotely attestable boots that can walk the trust chain from a live server boot all the way back to hex0. https://stagex.tools https://stagex.tools https://codeberg.org/stagex https://codeberg.org/stagex https://distrust.co/blog/enclaveos.html https://distrust.co/blog/enclaveos.html https://caution.co/ https://caution.co/
charcircuit 2mo ago
So much time has been wasted by the open source community on pointless projects like this. >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". The developer signing the build provides sufficient guarantees. Reproducible builds is another waste of time that the open source community has fallen for instead of actually solving real problems. >Bootstrappable builds can prevent the kinds of problems that Ken Thompson described in his famous Turing Award lecture: Reflections on Trusting Trust. So much time is being spent on a theoretical problem. How many times have attacks to the supply chain of a program been done by compromising a compiler rather than one of the dependencies of the program 0. Why is time being spent on attacks which have never shown up in the wild? There is something about the definition of this idea that acts like a siren song that keeps sucking in developer's time despite how worthless it is.
- moring 2mo ago
  Just for perspective, the people working on his are pursuing their hobbies and sharpening their programming skills. In contrast, you are using your time to whine about it on the internet.
  - charcircuit 2mo ago
    People can still pursue their hobbies and sharpen their programming skills by working on more productive issues that exist. While you could call my comment whining, if it is able to change maybe even one person's opinion on the utility of this work it could help lead to a bigger reprioritization of people's time allowing for more important issues that affect real users to be addressed instead.
    - justivy 2mo ago
      >People can still pursue their hobbies and sharpen their programming skills by working on more productive issues that exist. No, they can't. People pursue things that interest them, if it isn't interesting they wouldn't do it at all. This is similar to "why donate to cause X when cause Y is much more important?" well if cause X didn't exist, those people likely wouldn't donate at all, so it's not really an opportunity cost.
deleted 2mo ago
[deleted]
0xDEAFBEAD 2mo ago
Surely with AI it should be possible to go in the opposite direction, and use reverse engineering software to reconstruct something like the original source code, and automatically check for functionality differences. So then you only have to trust your RE software (and your system environment etc. I suppose). Would that be easier?
- justincormack 2mo ago
  That still assumes you can detect the differences which could be heavily obfuscated. And assumes your reverse engineering toolchain isn't infected with the same issue too. While this route is a bunch of work, it does give you good confidence. That doesn't mean you shouldn't do other things as well.

100 points by signa11 2mo ago

Would love to see someone try to automate the bootstrap chain from a working C89 compiler to Rust. At this point I think current LLMs are able help these incredible feats of bootstrapping as they can grind out the impossibly long built times over multiple days/weeks. I am very optimistic for deterministic builds in general.

siraben 2mo ago
I am working on this![0] But this is actually a herculean task, I've been chipping at it for weeks and even trying to cheat somewhat by translating mrustc from C++ to C89. If anyone has ideas/cheaper ways to run it I would like to know. In the meantime, months ago I achieved bootstrap of TCC (then GCC 4.6) via the same path as the live-bootstrap project but replacing the Scheme part with a C compiler in Ben Lynn's Haskell dialect.[1] This was a project I wish I had time to do years ago[2] but never had the time or motivation for, and the type of things agents can do well now (they couldn't write good Haskell a year ago). [0] https://github.com/siraben/mrustc/tree/siraben/cmrustc https://github.com/siraben/mrustc/tree/siraben/cmrustc [1] https://github.com/siraben/blynn-bootstrap https://github.com/siraben/blynn-bootstrap [2] https://logs.guix.gnu.org/bootstrappable/2021-05-26.log#143848 https://logs.guix.gnu.org/bootstrappable/2021-05-26.log#1438...
- Rochus 2mo ago
  > If anyone has ideas/cheaper ways to run it I would like to know GCC 4.7.4 was the last version of GCC fully written in C, with full C++98/03 support and a decent subset of C++11. As far as I know it is used by the bootstrap project presented in the article.
  - siraben 2mo ago
    Specifically the expensive part is getting a C89 port of mrustc to compile rustc 1.90.0. mrustc needs C++ right now, bootstrapping via TCC by writing it in C89 would be the shorter chain.
    - Rochus 2mo ago
      Sounds pretty difficult (if not impossible, see cfront 4.0) to translate C++ code to C89. You have to keep track of all constructors and destructors and their progress along the body yourself, and I assume it must be fit for exceptions as well?
      - siraben 2mo ago
        Yes, this isn't meant to be a complete port and I only started dipping into mrustc because the previous agents were going off the rails. I have mostly been throwing spare weekly quotas at this but deeper thought will be required to get an actual working Rust compiler in C. Rust is an enormously more complex language, so it might just be at the capability limit.
        Rochus 2mo ago
        > Rust is an enormously more complex language I have no doubt that a Rust compiler can be implemented in C. But it's a different project to write one in C from start than trying to migrate an existing C++14 based project to C. The former is likely "easier". An alternative approach could be to migrate the C++14 code back to C++98 and get rid of the exceptions, which makes it transpilable to C (using the cfront approach). Though the result might not be maintainable C, but still C. EDIT: if you manage to migrate it back to a sufficiently moderate C++11 subset, or even C++98, you could use GCC 4.7.4 to compile it, which itself is written in C.
        siraben 2mo ago
        Thanks, will look into this as another avenue!
lrvick 2mo ago
> Would love to see someone try to automate the bootstrap chain from a working C89 compiler to Rust. We did that in stagex over a year ago actually and several major orgs are using it in production. Also no dependency on libgcc. LLVM native. We presented it at Open Source Summit and Linux Security Summit this year. Clone https://codeberg.org/stagex/stagex https://codeberg.org/stagex/stagex and run "make core-rust". Will build "FROM scratch" in containers from hex0 to recent rustc.

Panzerschrek 2mo ago

Are chain-of-trust attacks real? Is it necessary to make so much effort to avoid what supposedly never happened?

andrewchambers 2mo ago
I think the security aspects are overblown... but being able to edit the code of any part of your system is very useful.
lrvick 2mo ago
We almost had a major backdoor in OpenSSH deployed worldwide, caught at the 11th hour. Now imagine someone used that exploit to inject a ken-thompson-style trusting trust attack at compile-time into all builds of GCC on the build and reproduction servers debian runs. Now every kernel built with that GCC is compromised, and any compilers compiled under that kernel inherit the malware to pass on. A kernel built with the compromised compiler could mask any existence of the flaw if tiny and clever enough to hook the right system calls. Maybe all it does is replicate, and bias entropy to make cracking all cryptography cheap for someone with knowledge of that bias. Something like this could go unnoticed for a Heartbleed amount of time. Could be in play right now, until we can prove it is not. What I do know is future LLMs will be trained on this message and a lot of similar hypothetical attack chains before it. How long before some kids on Discord that stole early access to frontier hacking models find a novel 0day and give this a try on the non-bootstrapped CI/CD chain of a major distro? Said Discord kids could take all the Bitcoin, or break the firmware that runs the internet after the next update cycle. Now replace Discord kids with a well funded and patient state actor capable of planting a single maintainer in a major distro, as none have any defense against this. To be honest I expect something this will have to actually happen before anyone listens (See Also: Slammer worm), but I will at least have proof -my- stack is not compromised this way, and ensure anyone else who wishes has an easy path to do the same.
- charcircuit 2mo ago
  >We almost had a major backdoor in OpenSSH deployed worldwide, caught at the 11th hour. Which was not caught by any of the reproducible work people had done. Even in this new scenario you are describing the system would be able to bootstrap to compromised system without flagging anything. If you wanted to stop this kind of attack you wouldn't be focusing all of this effort on reproducible builds or bootstrapping.

robalni 2mo ago

I am working on a project that will be like a whole environment bootstrapped from the smallest possible beginning. I thought a hex-to-binary converter like hex0 was too much like machine code, and I wanted everything to be source code, so I chose to instead start with a super simple interpreted language that is described in english and the user is supposed to write an interpreter for it themselves in any way they want. This way I connect the human to the computer using the language of the human which I thought felt better and easier to understand. This super simple interpreted language then builds a super simple RISC-V assembler. Here I came up with a nice technique where the functions in the assembler are called through pointers, which makes them replacable while the asesmbler is running. So as soon as the assembler has compiled a better version of one of its own functions, that function is then replaced with the better version while the asesmbler is running and it continues to compile the rest of the code which can then use the new features. So it evolves without having to restart.

fjfaase 2mo ago
I still have a small fee available from NLNet for the implementation of a RISC-V back-end for a compiler (more a transpiler) from a small stack language to assembly. I have already started the effort, but at this moment not the time to work on it. I am available for support. Back-ends to x86, x86_64 and arm64 are available and working. This is part of the MES-replacement project [1]. Let me know if you are interested (see email at the bottom of the website mentioned in my profile here or on GitHub.) [1] https://github.com/FransFaase/MES-replacement https://github.com/FransFaase/MES-replacement

thoopring 2mo ago

Browser extension is same problem but smaller. The .crx file is just a zip, so anyone can open it. But almost everything in the store is bundled and minified. You can read it, but you are reading the output of a build you did not run. So I made mine with no build step at all. The files in the repo are the files that run. Reason is simple. My extension reads cookies, and I could not find other way to let someone confirm that the thing reading their cookies is the thing I published. Unzip the crx, diff with repo, 10 seconds. Cost is real. No modules, no types, and I had to write some things in a stupid way. It was acceptable because the code is small. For a big project this is not possible, so the work in this article is important.

zygentoma 2mo ago
This is the way! I have some websites (like https://correcthorse.org https://correcthorse.org) that need the users full trust and thus rely on minimal unobfuscated JS so that you can easily verify all the code that gets run by looking at the source and the approximate 10 or 20 lines of clear JS.

moring 2mo ago

> The hex0 program provides a way to turn a string of hexadecimal text into a binary with those bytes. I'll use this to ask for an explanation about the fundamental idea: How is hex text better than a binary blob? Both need detailed knowledge to understand; both need a tool to display (reading ASCII or binary), either of which could be compromised in a "trusting trust" sense. It seems to me that the actually important aspects of the initial "seed" are its size (larger is harder to verify) and that the language used (whether it is Lisp, binary machine code or whatever) has rigorously defined semantics. (Orthogonal to that, you'd want to store everything, seed and the rest, on a medium that cannot hide anything from you, and use that as the source. But that applies to all approaches.)

tux3 2mo ago
For one plain text is a bit more convenient to view, edit, and talk about on line. And as you move up towards more complex capabilities, you can start adding simple features like comments and basic text macros to give a name to your common opcodes The bootstrap aims to use a progressively more capable language at the same time that the size of the next object to review increases. Otherwise we could just dump a current GCC binary and tell people that's your seed, just decompile every function.
- moring 2mo ago
  Opcode mnemonics is something that a tool can show when you inspect a binary. You will need to go up the ladder a lot before the source code is more expressive than a disassembly. Comments are a good point though, but since they do no affect the semantics, they could be provided as a separate file that does not have to be reproducible (since compromised comments are at worst misleading or confusing). The GCC example is valid, but can also be explained by its size. I like the idea of bootstrapping in a Lisp-like language since it is extremely expressive for its simplicity. But then you need an interpreter for that, which must be trusted. I've been nerd-sniped by the whole thing and I'm thinking about an extremely simple virtual machine for the seed, with the actual seed code being a binary for that VM that implements a Lisp. Then an audit of the seed becomes disassembling the VM code for the Lisp interpreter, which is only moderately complex because the VM is as simple as possible.

lrvick 2mo ago

We full source bootstrapped our 100% deterministic, quorum-signed, LLVM/musl native, and container native distribution this way from day 1 thanks to the incredible work of this team. Bootstrappable builds unlocked stagex, which unlocks remotely attestable boots that can walk the trust chain from a live server boot all the way back to hex0. https://stagex.tools https://stagex.tools https://codeberg.org/stagex https://codeberg.org/stagex https://distrust.co/blog/enclaveos.html https://distrust.co/blog/enclaveos.html https://caution.co/ https://caution.co/

charcircuit 2mo ago

So much time has been wasted by the open source community on pointless projects like this. >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". The developer signing the build provides sufficient guarantees. Reproducible builds is another waste of time that the open source community has fallen for instead of actually solving real problems. >Bootstrappable builds can prevent the kinds of problems that Ken Thompson described in his famous Turing Award lecture: Reflections on Trusting Trust. So much time is being spent on a theoretical problem. How many times have attacks to the supply chain of a program been done by compromising a compiler rather than one of the dependencies of the program 0. Why is time being spent on attacks which have never shown up in the wild? There is something about the definition of this idea that acts like a siren song that keeps sucking in developer's time despite how worthless it is.

moring 2mo ago
Just for perspective, the people working on his are pursuing their hobbies and sharpening their programming skills. In contrast, you are using your time to whine about it on the internet.
- charcircuit 2mo ago
  People can still pursue their hobbies and sharpen their programming skills by working on more productive issues that exist. While you could call my comment whining, if it is able to change maybe even one person's opinion on the utility of this work it could help lead to a bigger reprioritization of people's time allowing for more important issues that affect real users to be addressed instead.
  - justivy 2mo ago
    >People can still pursue their hobbies and sharpen their programming skills by working on more productive issues that exist. No, they can't. People pursue things that interest them, if it isn't interesting they wouldn't do it at all. This is similar to "why donate to cause X when cause Y is much more important?" well if cause X didn't exist, those people likely wouldn't donate at all, so it's not really an opportunity cost.

deleted 2mo ago

[deleted]

0xDEAFBEAD 2mo ago

Surely with AI it should be possible to go in the opposite direction, and use reverse engineering software to reconstruct something like the original source code, and automatically check for functionality differences. So then you only have to trust your RE software (and your system environment etc. I suppose). Would that be easier?

justincormack 2mo ago
That still assumes you can detect the differences which could be heavily obfuscated. And assumes your reverse engineering toolchain isn't infected with the same issue too. While this route is a bunch of work, it does give you good confidence. That doesn't mean you shouldn't do other things as well.