From bootstrapping
Revision as of 15:37, 7 July 2022 by (talk) (Initial content, moved from main page)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Karger-Thompson Attack[edit]

Anything related to the karger thompson attack: proof of concept demos, mitigations, theory.

  • multics the original paper explaining the attack (before thompson!)
  • SCM Security by Wheeler (Secure distribution & compilation of source fundamentals; Karger advised mastering it)
  • rotten by rntz (thompson attack demo)
  • rust infection by manishearth (thompson attack demo in the rust compiler)
  • tcc ACSAC by daved wheeler
  • CompCert by Leroy et al (Mathematically-verified, C compiler whose specs and proofs checked with tiny, verified checker)
  • CakeML by Myreen et al (Mathematically-verified, SML compiler whose specs and proofs checked with different, tiny, verified checker)
  • VLISP by Oliva and Wand (Article has links to VLISP which mathematically verified PreScheme and Scheme48)
  • KCC by Rosu et al (Executable, formal semantics for C in rewrite logic; could do that w/ simpler engine)
  • TALC by Cornell (Typed, assembly language to verify safety w/out compiler; checker can be simple; C subset + verified compiler to TALC)
  • CoqASM by Microsoft Research (Bootstrap in verifiably-safe assembly in prover checked by tiny, verified checker)

Ubiquitous Implementations[edit]

These are tools written in ubiquitous languages, therefore they can be used in a wide variety of contexts.

  • shasm by Hohensee (x86 assembler written in BASH)
  • AWKLisp by Bacon (LISP written in Awk; includes Perl version from Perl Avenger)
  • Gherkin by Dipert (LISP written in Bash)
  • BASH Infinity by Brzoska (BASH framework/routines that might help write compilers in it)
  • mal "make a lisp" implementing a very basic lisp interpreter in hundreds of languages
  • [1] A new bootstrapping project that is built up to a self host language above assembly from a minimal DOS platform.

Small C Compilers[edit]

  • c4 by rswier (incredibly short c compiler)
  • cc500 by edmund grimley-evans (tiny c compiler)
  • CUCU by Zaitsev (Small, C compiler designed for easy understanding)
  • SmallerC by Frunze (Small, single-pass, C compiler for several ISA's)
  • picoc interpreter.
  • C Interpreter by Dr Dobbs (Describes building a C interpreter with source)
  • [2] Small C for I386 (IA-32)
  • Selfie, a tiny self-compiling compiler for a subset of C, a tiny self-executing MIPS emulator, and a tiny self-hosting MIPS hypervisor, all in a single 7kLoC file. HN discussion. Paper.
  • Tiny C expression compiler Written in Forth based on tinyc.c by marc feeley.
  • [3] [4] C compilers by Rui Ueyama blog
  • [5] 10 hour self hosting c compiler

Grammars, Parsing, and Term Rewriting[edit]

  • Grammar Executing Machine by McKeeman and He (Incrementally extend languages from simple to complex grammars in interpreter(s))
  • peg by kragen (parsing)
  • PEG-based simple compiler by Ian Piumarta
  • META II by Bayfront Tech (Original meta-compiler w/ live code and detailed tutorial; OMeta was successor)
  • META II implementation by Lugon (Looks like a small implementation of META II; also bootstrapped in META II)
  • OMeta# Intro by Moser (OMeta intro that nicely illustrates the meta approach/advantages)

Virtual Machines, Instruction Sets[edit]

  • P-code by Wirth (High-level language & libraries target ultra-simple, portable interpreter)
  • sweet16 by Steve Wozniak
  • Tiny BASIC by Allison (Small BASIC whose original VM took 120, virtual opcodes to implement using 3KB RAM)
  • Klip by Cutting (Compiler & runtime for simple language for students; done in C#; runtime is very readable)
  • Uxn by Linvega (Portable VM with 32 mnemonics implemented in 100 lines of C89; self-hosted assembler)

CPU's for Bootstrapping: The Simple, The Verified, and The Necessarily Complex[edit]

  • NAND2Tetris by Nisan and Schocken (Guide that teaches hardware step-by-step in fun way with simple CPU emerging)
  • J1 by by Bowman (16-bit Forth CPU in 200 lines of Verilog that does 100MIPS on FPGA's)
  • H2 by Howe (Modified, VHDL version of J1 with detailed description and Howe's code MIT-licensed)
  • RISC-0 by Wirth (Simple, RISC CPU & SOC designed for Oberon language with detailed docs and source online)
  • JOP by Shoeberl et al (Embedded Java processor that takes up 1830 slices on FPGA)
  • Scheme Machine by Burger (Scheme interpreter implemented as CPU using formal methods)
  • ZPU by Zylin AS (Tiny, 32-bit CPU for deep embedded apps in 440 LUT's)
  • J2 by Landley et al (Clone of cost-efficient, SuperH-2 CPU in open-source)
  • VAMP by Beyer et al (Formally-verified, DLX-style processor in 18,000 slices on Xilinx)
  • Leon3 by Gaisler (Industry-grade, 32-bit SPARC w/ auto-configuration of core and GPL license)
  • Rocket by Univ of CA (1.4GHz RISC-V CPU and generator for customization)
  • OpenPITON by Princeton (25-core, shared-memory, SPARC CPU open-sourced and very scalable)

Minimal Operating Systems[edit]

  • KolibriOS - lightweight assembly OS.
  • MikeOS - same.
  • Sortix - modern reimplementation of POSIX in C. (Note: No perl port and GCC does not build natively on it. (yet.))
  • ASMLINUX - linux kernel, but the userspace is implemented entirely in assembly.
  • LFS - Guide on building Linux and the GNU userspace.
  • buildroot
  • NetBSD - Cross-build a complete NetBSD ISO from a foreign OS. There's also a guide in the official NetBSD docs.
  • lh-bootstrap - alternative linux distro, using musl instead of glibc.
  • xv6 - UNIX teaching OS MIT
  • OS/161 - UNIX teaching OS Harvard
  • - Toybox, alternative to Busybox by Robert Landley, see also Aboriginal Linux and mkroot by the same author, which are all geared toward a minimal boostrappable system
  • - Another take at a bootstrappable Linux system
  • Project Oberon - Operating system and programming language Oberon (from the creator of Pascal - Niklaus Wirth)
  • TinyGo Operating system in programming language Go
  • TamaGo - Another operating system in programming language Go
  • seL4 Microkernel - OS kernel in less than 10.000 lines of source code and less than 150 KB binary
  • Ultibo - Unikernel for Raspberry Pi written in FreePascal