News for hackers. Stuff that matters.
Re:Bootstrapping from Hex to Bison to GCC by markjenkinswpg on Monday May 03, 2021 @07:03PM (#27032036)
Nice work Fossy and co.

I believe this is this is the dependency chain your live-bootstrap works through: https://github.com/oriansj/talk-notes/raw/master/live-bootst...

Re:Bootstrapping from Hex to Bison to GCC by userbinator on Monday May 03, 2021 @08:01PM (#27032482)
See also Bellard's TCCBOOT, which is based on the far simpler TCC instead of GCC: https://bellard.org/tcc/tccboot.html
Re:Bootstrapping from Hex to Bison to GCC by donio on Tuesday May 04, 2021 @02:59AM (#27034738)
That's a different kind of bootstrapping though. The OP is about building up to a toolchain from almost nothing using only source code and only relying on some tiny binaries that could be hand-assembled or verified. And it also uses a version of TinyCC along the way before it arrives to gcc.
Re:Bootstrapping from Hex to Bison to GCC by fosslinux on Tuesday May 04, 2021 @07:08AM (#27036241)
I do plan to integrate this, or something very similar, into live-bootstrap. This is essentially the type of thing we would do to compile the Linux kernel within the bootstrap, which has not been done yet. However tccboot/derivative needs to be compiled from source within live-bootstrap which is not simple.
Re:Bootstrapping from Hex to Bison to GCC by markjenkinswpg on Monday May 03, 2021 @09:24PM (#27033067)
One nice thing about the work showcased here is that it bootstraps TCC on its journey to GCC. At some point we could see attempts to bootstrap tccboot as a kind of "escape pod" from other systems, and after booting tccboot, have the bootstrapping work documented here continue from TCC onward.
Re:Bootstrapping from Hex to Bison to GCC by XorNot on Monday May 03, 2021 @08:29PM (#27032696)
This is cool as heck. Outside of architectural attacks, this seems like a practical response to Reflections on Trusting Trust (http://users.ece.cmu.edu/~ganger/712.fall02/papers/p761-thom...).

While we can definitely discuss whether it's practical for anyone to actually audit all that source code (no it is not), proving a 356 bytes codestream isn't malicious seems like a good foundation to argue about.

Re:Bootstrapping from Hex to Bison to GCC by recuter on Monday May 03, 2021 @10:06PM (#27033319)
suspicious squints

Perhaps this bit is key as you could cross reference the two:

> Furthermore, having an alternative bootstrap automation tool allows people to have greater trust in the bootstrap procedure.

Interesting thought exercise.

Edit: Avoid this subject unless you want to be nerd sniped and spiral into paranoia.

Re:Bootstrapping from Hex to Bison to GCC by siraben on Monday May 03, 2021 @08:48PM (#27032822)
See also blynn-compiler[0], made by the same contributors, that bootstrap a Haskell compiler from C (which in term is bootstrapped from hex).

[0] https://github.com/oriansj/blynn-compiler

Re:Bootstrapping from Hex to Bison to GCC by Aissen on Tuesday May 04, 2021 @03:47AM (#27034956)
See this doc for how the full process works: https://github.com/fosslinux/live-bootstrap/blob/master/part...

In particular, this the very first step: https://github.com/oriansj/stage0-posix/blob/master/x86/hex0... (or its hand-edited binary version ?)

Edit: this how it's "assembled":

    sed 's/[;#].*$//g' $input_file | xxd -r -p > $output_file
See: https://github.com/oriansj/bootstrap-seeds/blob/master/READM...
Re:Bootstrapping from Hex to Bison to GCC by fjfaase on Tuesday May 04, 2021 @05:19AM (#27035515)
I wonder if Brainfuck could be used for https://github.com/oriansj/stage0-posix ? It would not surprise me if there is no other language for which there are so many interpreters written in so many different programming languages. It is even possible to write a Brainfuck interpreter in Brainfuck, which can be verified. And there is also a Brainfuck interpreter written in x86-64: https://github.com/316k/brainfuck-x86-64 . It is a little larger than hex0_x86.hex0 , but not too much to make it hard to verify.
Re:Bootstrapping from Hex to Bison to GCC by kragen on Tuesday May 04, 2021 @10:46AM (#27038154)
Bootfuckbrainstrapping (?) is definitely an interesting idea; I explored it in some depth in https://dercuano.github.io/notes/uvc-archiving.html#addtoc_2 and https://dercuano.github.io/notes/self-compiler-bootstrapping..., and I concluded that although BF is inspiring, it would be easy to do better. Also, although the interpreter you point at compiles to 11331 bytes on my machine (5992 stripped, 5912 after objcopy -S -R .note.gnu.build-id bf bf.small) Brian Raiter wrote a 199-byte BF interpreter for i386 Linux last millennium: http://www.muppetlabs.com/~breadbox/software/tiny/bf.asm.txt
Re:Bootstrapping from Hex to Bison to GCC by fjfaase on Tuesday May 11, 2021 @08:51AM (#27117451)
I have written a BrainFuck generator for writing a BrainFuck program which could replace the hex0 seeds. See https://www.iwriteiam.nl/BFgen.html
Re:Bootstrapping from Hex to Bison to GCC by kragen on Thursday May 13, 2021 @02:16PM (#27145378)
This is pretty cool!

The dataflow is not totally clear to me—am I understanding correctly that the parser generator is implemented by a recursive-descent parser implemented in 1400 lines of JS, which then compiles the example grammar in "grammar" into the top-down Forthish code in "grammar_error", which is then used to compile the Algolish code in "input" into the Lispish code in "output", which is then compiled into the BF in "result"?

While this is an inspiring and aesthetically delightful achievement, it's not clear that it helps with the hex0 seeds, because executing the 1400-line recursive-descent parser requires the seed to grow by the size of one JavaScript execution engine; all the existing ones are about four orders of magnitude larger than the live-bootstrap seed. Lacking that, a malicious JS execution engine could inject malicious code into the BF output, in the Karger–Thompson-attack scenario.

I suspect that the initial grammar compilation could be achieved by a cut-down compiler-compiler along the lines of what I'm working on in http://canonical.org/~kragen/sw/dev3/meta5ix.m5, although Meta5ix itself is not currently bootstrappable from a human-written seed.

Re:Bootstrapping from Hex to Bison to GCC by fjfaase on Tuesday May 18, 2021 @04:04PM (#27200294)
Thanks!

It is not so much a parser generator as in interpreting parser. It is based on https://fransfaase.github.io/ParserWorkshop/Online_inter_par... which I developed earlier this year.

My idea was not to use the input as the base of the seed, but the generated BrainFuck program. The idea is that there are a multitude of BrainFuck interpreters/compilers in a multitude of programming languages that one could use verify that they are not malicious.

Also, I think it is easier to verify that a BrainFuck program is not malicious than a program in machine code. The x86 instruction set is rather large, I understand, with all its extensions. I understand that only a very restricted subset of instructions is used in the seed, but one still needs to verify this requiring to understand the x86 instruction documentation. Verifying the BrainFuck program is not easy, but it does not require the access to some external document. Besides the definition of the language, only an ASCII table, which would also be needed for x86 seed, BTW.

Re:Bootstrapping from Hex to Bison to GCC by NieDzejkob on Tuesday May 04, 2021 @09:11AM (#27037188)
Except that brainfuck was actively designed to make programming difficult, and as you can only increment and decrement, the performance is abysmal.
Re:Bootstrapping from Hex to Bison to GCC by fjfaase on Wednesday May 05, 2021 @04:40AM (#27047575)
The performance argument is not a real issue if it is only used as a replacement for sed/xxd combination. And yes, it was designed to make programming difficult, but one could argue that it is easier to verify manually than machine code, because machine code requires you to know the whole x86 instruction set, which I understand, is rather large, taking into account all the extensions. I suspect that these exentions are not used in the stage0 code, but we still have to verify that they are not used.
Re:Bootstrapping from Hex to Bison to GCC by kragen on Tuesday May 04, 2021 @10:47AM (#27038173)
You can make more efficient BF interpreters and compilers that recognize common patterns and optimize them.
Re:Bootstrapping from Hex to Bison to GCC by choeger on Tuesday May 04, 2021 @02:27AM (#27034609)
So, how about the kernel, eh? ;)
Re:Bootstrapping from Hex to Bison to GCC by fosslinux on Tuesday May 04, 2021 @07:05AM (#27036214)
The kernel is still an unsolved problem, unfortunately. We need an appropriate, small seed kernel to be able to successfully run everything up until we can recompile linux (which also has proved difficult and is not why it is in the repo yet) :(