WebAssembly binary format

Deep dive

How it works

In: bytes of a module · Out: types, exports, function bodies, or an error · State: none (a cursor) · Cost: O(bytes), one pass

1. Check the 4 magic bytes 00 61 73 6D and version 01 00 00 00.
2. Loop: read id (1 byte) and size (u32 LEB128); the payload is the next size bytes, so skipping needs no decoding.
3. Id 0 is a custom section (name, debug info such as DWARF): any position, never invalidates the module.
4. Other ids (type 1, import 2, function 3, table 4, memory 5, global 6, export 7, start 8, element 9, code 10, data 11) come in increasing order, at most once. Data count (12) goes before code, tag (13) before global.
5. The function section lists a type index per function; the code section holds the bodies (locals, then instructions). Signatures precede bodies.
6. Validate each body in one pass: pop operand types, push result types; at end the stack must equal the result types.
7. Branches name an enclosing block by depth: no free jump target (structured control flow).

Why untrusted code is safe: no jump to an arbitrary address, no operand of the wrong type; a load or store outside the linear memory traps (spec overview). The host is reachable only via imports. The spec's validation algorithm is a single pass over the opcodes that fits into a decoder (appendix).

Streaming: V8's baseline compiler Liftoff decodes, validates and emits machine code in one pass per function, so with the streaming API it compiles while the module downloads (V8 blog). Bodies are independent, so threads can take them in parallel.

Code

Parser, LEB128, section-order check and one-pass validator for a hand-assembled 41-byte add module, with asserts for the export, LEB128 edges, swapped sections and a one-operand i32.add.

#[derive(Clone, Copy, PartialEq, Debug)]
enum Ty { I32, I64, F32, F64 }
type Sig = (Vec<Ty>, Vec<Ty>);
type R<T> = Result<T, String>;
struct Rd<'a> { b: &'a [u8], p: usize }
impl<'a> Rd<'a> {
    fn bytes(&mut self, n: usize) -> R<&'a [u8]> {
        self.p += n;
        self.b.get(self.p - n..self.p).ok_or("eof".into())
    }
    fn byte(&mut self) -> R<u8> { Ok(self.bytes(1)?[0]) }
    fn u32(&mut self) -> R<u32> { // unsigned LEB128, at most 5 bytes
        let mut v = 0u32;
        for shift in (0..35).step_by(7) {
            let b = self.byte()?;
            if shift == 28 && b > 0x0F { break; } // 5th byte: only 4 bits fit
            v |= ((b & 0x7F) as u32) << shift;
            if b & 0x80 == 0 { return Ok(v); }
        }
        Err("bad u32".into())
    }
    fn ty(&mut self) -> R<Ty> {
        match self.byte()? {
            0x7F => Ok(Ty::I32), 0x7E => Ok(Ty::I64), 0x7D => Ok(Ty::F32), 0x7C => Ok(Ty::F64),
            t => Err(format!("bad valtype {t:#x}")),
        }
    }
    fn vec<T>(&mut self, f: fn(&mut Self) -> R<T>) -> R<Vec<T>> { (0..self.u32()?).map(|_| f(self)).collect() }
}
fn put_u32(out: &mut Vec<u8>, mut v: u32) {
    while v >= 0x80 { out.push((v & 0x7F) as u8 | 0x80); v >>= 7; }
    out.push(v as u8);
}

#[derive(Default, Debug)]
struct Module<'a> { types: Vec<Sig>, funcs: Vec<u32>, exports: Vec<(String, u8, u32)>, code: Vec<&'a [u8]> }
fn parse(bin: &[u8]) -> R<Module<'_>> {
    let mut r = Rd { b: bin, p: 0 };
    if r.bytes(4)? != b"\0asm" { return Err("bad magic".into()); }
    if r.bytes(4)? != [1, 0, 0, 0] { return Err("bad version".into()); }
    let (mut m, mut last) = (Module::default(), 0);
    while r.p < bin.len() {
        let id = r.byte()?;
        let n = r.u32()? as usize;
        let mut s = Rd { b: r.bytes(n)?, p: 0 }; // sized: skippable
        if id == 0 { continue; } // custom: anywhere, ignored
        if id > 11 || id <= last { return Err(format!("section {id} out of order")); }
        last = id;
        match id {
            1 => m.types = s.vec(|s| match s.byte()? {
                0x60 => Ok((s.vec(Rd::ty)?, s.vec(Rd::ty)?)),
                _ => Err("not a func type".into()),
            })?,
            3 => m.funcs = s.vec(Rd::u32)?,
            7 => m.exports = s.vec(|s| {
                let n = s.u32()? as usize;
                let name = String::from_utf8(s.bytes(n)?.to_vec()).map_err(|e| e.to_string())?;
                Ok((name, s.byte()?, s.u32()?))
            })?,
            10 => m.code = s.vec(|s| { let n = s.u32()? as usize; s.bytes(n) })?,
            _ => {} // import, table, ... skipped by size
        }
    }
    if m.funcs.len() != m.code.len() { return Err("function/code count mismatch".into()); }
    for (f, body) in m.funcs.iter().zip(&m.code) {
        validate(m.types.get(*f as usize).ok_or("bad type index")?, body)?;
    }
    Ok(m)
}
// One pass over one body, operand type stack, no control flow in this sketch.
fn validate((params, results): &Sig, body: &[u8]) -> R<()> {
    let mut r = Rd { b: body, p: 0 };
    let mut locals = params.clone();
    for (n, t) in r.vec(|r| Ok((r.u32()?, r.ty()?)))? {
        locals.extend((0..n.min(50_000)).map(|_| t)); // cap locals
    }
    let mut st = Vec::new();
    loop {
        match r.byte()? {
            0x20 => st.push(*locals.get(r.u32()? as usize).ok_or("bad local")?), // local.get
            0x6A => { // i32.add : [i32 i32] -> [i32]
                for _ in 0..2 {
                    if st.pop().ok_or("stack underflow")? != Ty::I32 { return Err("type mismatch".into()); }
                }
                st.push(Ty::I32);
            }
            0x0B => { // end: the stack must be exactly the results
                if st != *results { return Err(format!("end: {st:?} != {results:?}")); }
                return if r.p == body.len() { Ok(()) } else { Err("bytes after end".into()) };
            }
            op => return Err(format!("opcode {op:#x} not in this sketch")),
        }
    }
}
const ADD: &[u8] = &[
    0x00, 0x61, 0x73, 0x6D, 0x01, 0x00, 0x00, 0x00,       // preamble
    0x01, 0x07, 0x01, 0x60, 0x02, 0x7F, 0x7F, 0x01, 0x7F, // type: (i32 i32)->i32
    0x03, 0x02, 0x01, 0x00,                               // function: type 0
    0x07, 0x07, 0x01, 0x03, b'a', b'd', b'd', 0x00, 0x00, // export add = func 0
    0x0A, 0x09, 0x01, 0x07, 0x00,                         // code: 1 body, 7 bytes
    0x20, 0x00, 0x20, 0x01, 0x6A, 0x0B,                   // get 0, get 1, add, end
];
fn main() {
    let m = parse(ADD).unwrap();
    assert_eq!(m.exports, [("add".to_string(), 0, 0)]);
    assert_eq!(m.types[m.funcs[0] as usize], (vec![Ty::I32; 2], vec![Ty::I32]));
    for v in [0, 127, 128, 624485, u32::MAX] {
        let mut o = Vec::new();
        put_u32(&mut o, v);
        assert_eq!(Rd { b: &o, p: 0 }.u32(), Ok(v));
    }
    assert!(Rd { b: &[0xFF, 0xFF, 0xFF, 0xFF, 0x1F], p: 0 }.u32().is_err()); // > u32::MAX
    let custom = [&ADD[..17], &[0, 5, 4, b'n', b'a', b'm', b'e'], &ADD[17..]].concat();
    assert!(parse(&custom).is_ok()); // custom section: skipped
    let swapped = [&ADD[..8], &ADD[17..21], &ADD[8..17], &ADD[21..]].concat();
    assert!(parse(&swapped).unwrap_err().contains("out of order"));
    let bad = [&ADD[..30], &[0x0A, 0x07, 0x01, 0x05, 0x00, 0x20, 0x00, 0x6A, 0x0B][..]].concat();
    assert_eq!(parse(&bad).unwrap_err(), "stack underflow");
    println!("all asserts passed");
}

The sketch handles three opcodes; real validators add a control stack beside the operand stack.

Complexity and constants

• Parse and validate: O(n) in bytes; cost drivers are bytes read and one push or pop per operand, all sequential.
• u32 LEB128 takes 1 byte for 0-127, 2 for 128, 3 for 624485 (E5 8E 26), 5 for u32::MAX (checked in the code above).

Efficiency

• Cost: one pass over the bytes, no syscalls; decoding is bandwidth-bound, compiling is code-generation-bound.
• Levers:
  • Compile while downloading — Liftoff plus streaming hides compile time behind the network (V8 blog) — large modules.
  • Skip by size — bodies stay undecoded until needed — lazy or parallel compilation.
  • Baseline first, optimize hot code later — the post names 39.5 MB and 36.8 MB apps taking over 30 s to start on many machines before Liftoff (V8 blog) — big apps.
  • Validate while decoding — no second pass (spec appendix) — always.
• Naive → standard → state of the art: decode, validate, compile as three passes over the whole file · latency adds up; validate while decoding, per function · one pass; stream into parallel per-function baseline compile, optimize hot code later · overlaps the download (V8 blog).

Implementation notes

• Check each length against the remaining bytes before allocating; a hostile vec count is a memory bomb. Cap locals and nesting depth.
• Reject over-long LEB128: at most ceil(N/7) bytes for uN (spec).
• Sections are sub-slices of the input: zero-copy.
• Fuel and timeouts are not in the format: see instruction metering. JIT output belongs in W^X memory.

Pitfalls

• Ids 12 and 13 are out of numeric order; the sketch rejects them.
• Function count (section 3) must equal body count (section 10); a size field must match its payload exactly.
• Imports and exports are the whole interface; wrappers are FFI binding generation.

Variants and alternatives

In production

• Web browsers: V8 compiles with Liftoff first, then optimizes hot functions (V8 blog); see JIT compilation.
• Edge functions: Fastly Compute runs customer code compiled to Wasm (docs); Cloudflare Workers runs Wasm (docs).
• Proxy plugins: Envoy has a Wasm HTTP filter (docs); proxy-wasm defines the plugin ABI (spec).
• Blockchain: CosmWasm smart contracts for the Cosmos SDK compile to Wasm (repo).
• Embedded and IoT: WAMR, a small-footprint runtime (repo).
• Standalone runtimes: WebAssembly runtime.

Implementations

Sources

• WebAssembly Core Specification: binary format, LEB128 integers, validation algorithm.
• Clemens Backes, Liftoff: a new baseline compiler for WebAssembly in V8, 2018. post
• Haas et al., Bringing the Web up to Speed with WebAssembly, PLDI 2017. paper