Lab 21: The Standard Library (Milestone 13)

Background

You will build src/stdlib/: base, math, string, and table, behind a Capabilities set whose default grants nothing dangerous — and then write the test that enumerates the entire granted surface and compares it against a golden file.

Why This Lab Matters

The library is where a runtime becomes usable and where it becomes an attack surface, and the same commit decides both.
pcall must not catch limit errors. One line, and every CPU control in the threat model depends on it.
table.sort with a hostile comparator is a real CVE class, not a hypothetical.

Prerequisites

Labs 19–20 complete.
The Standard Library read.
Lua 5.4 Reference Manual §6 open. You will consult it constantly, and the differences you find are the deliverable.

Predict First

pcall(function() while true do end end) under a small instruction budget — what happens?
tostring(1/0) and tostring(0/0) — what should Ember print, and is that the same on every platform?
table.sort(t, function(a,b) return true end) — a comparator that is not a strict weak ordering. What can a naive quicksort do?
("x"):rep(1e9) — where is that stopped, and is the check before or after the allocation?
string.format("%d", "abc") — error, or something worse?
math.random is not in SAFE. Which of the two possible reasons applies — determinism or security?

Step 1: The Capability Set

Write Capabilities and install from the concept chapter. Then write the test before the library, so that every function you add is a deliberate addition:

#![allow(unused)]
fn main() {
#[test]
fn default_globals_contain_no_ambient_authority() {
    let e = Engine::new();                     // SAFE by default
    let mut names = e.enumerate_globals();
    names.sort();
    assert_eq!(names, read_golden("tests/golden/safe-globals.txt"));
    // And the specific negative assertions, so the failure NAMES the problem:
    for forbidden in ["io", "os", "load", "loadstring", "dofile", "loadfile",
                      "require", "debug", "package", "collectgarbage_disable"] {
        assert!(!names.contains(&forbidden.to_string()),
                "`{forbidden}` is reachable in the SAFE capability set");
    }
}
}

The golden file is the point. Adding a global changes a checked-in file, which makes the grant appear in a diff instead of in a builder call three modules away.

Step 2: `base`

#![allow(unused)]
fn main() {
// The four that carry decisions. The rest are mechanical.

// 1. pcall — MUST NOT catch limits.
fn pcall(ctx: &mut Ctx, args: &[Value]) -> Result<Vec<Value>> {
    let f = args.first().copied().unwrap_or(Value::Nil);
    match ctx.call(f, &args[1..]) {
        Ok(mut vs) => { let mut out = vec![Value::Boolean(true)]; out.append(&mut vs); Ok(out) }
        // A Limit error UNWINDS PAST pcall. Without this line, a script can
        // defeat every CPU control:  while true do pcall(burn) end
        Err(e) if e.kind == ErrorKind::Limit => Err(e),
        // A Host error also propagates: it is the HOST's bug, not the script's,
        // and swallowing it hides a service defect inside a policy.
        Err(e) if e.kind == ErrorKind::Host => Err(e),
        Err(e) => Ok(vec![Value::Boolean(false), ctx.error_to_value(e)?]),
    }
}

// 2. tostring — honors __tostring, and float formatting must match the language.
// 3. tonumber — accepts an optional base; returns nil on failure, never errors.
// 4. error — error(msg, level); level 1 (default) blames the caller's position.
}

Warning: Step 2's pcall is the single most security-critical function in the library. Write its test first, and make the test's name say why: pcall_does_not_catch_limit_errors_because_that_would_defeat_the_budget.

Float formatting. tostring(1/0) and tostring(0/0) must be chosen, not inherited:

lua -e 'print(1/0, -1/0, 0/0)'     # inf  -inf  and a PLATFORM-DEPENDENT nan spelling

Ember prints inf, -inf, and nan — always, on every platform. Run the Lua command on two machines if you can; the difference is a determinism lesson you can see.

Step 3: `math`

Mechanical, with three notes:

math.type(x) returns "integer", "float", or nil. It is the script-visible half of ADR-005, and without it a script author cannot debug a subtype confusion.
math.tointeger(x) returns nil rather than erroring — the non-erroring counterpart to the conversion rule.
math.random is behind RANDOM, not in SAFE, for determinism. When granted, the host supplies the seed:

#![allow(unused)]
fn main() {
Engine::builder()
    .capabilities(Capabilities::SAFE | Capabilities::RANDOM)
    .random_seed(request_id_hash)      // ← reproducible per request
    .build()
}

That last line is what makes an A/B experiment replayable, and it is the difference between "we support randomness" and "we support randomness responsibly".

Step 4: `string`

The patterns library is the biggest piece and the one with the sharpest edges.

#![allow(unused)]
fn main() {
// Every allocating function checks the budget BEFORE allocating.
fn rep(ctx: &mut Ctx, args: &[Value]) -> Result<Vec<Value>> {
    let s: Vec<u8> = arg(ctx, args, 0, "rep")?;
    let n: i64     = arg(ctx, args, 1, "rep")?;
    let total = s.len().checked_mul(n.max(0) as usize)
        .ok_or_else(|| ctx.limit_error("string.rep result too large"))?;
    ctx.charge_memory(total)?;      // ← BEFORE. Not after.
    // ...
}
}

Lua patterns are not regexes — no alternation, no unbounded backtracking of the regex kind — which is a genuine safety property worth knowing. They are still a CPU vector: %b, %f, and nested * quantifiers can do a lot of work. Charge matching against the instruction budget in proportion to characters examined, which is the only mechanism that generalizes.

string.format is a parser over a script-controlled format string:

Reject unknown specifiers with a clear error naming the specifier.
Bound the output width (%1000000d must not allocate a megabyte).
Never hand the format string to a C-style formatter.
%d on a float with a fractional part is an error, matching the conversion rule.

Step 5: `table`

#![allow(unused)]
fn main() {
// table.sort must survive a comparator that is not a strict weak ordering.
// A naive quicksort with a bad comparator can run its partition pointers past
// the array bounds — a real CVE class (V8, glibc qsort, and others).
fn sort(ctx: &mut Ctx, args: &[Value]) -> Result<Vec<Value>> {
    // Two defenses, and Ember uses both:
    //  1. An algorithm whose index arithmetic cannot escape the slice regardless
    //     of what the comparator says (bounds-checked indices, no pointer walk).
    //  2. A cheap consistency check: if the comparator claims a < b AND b < a,
    //     error with "invalid order function for sorting" — as Lua does.
    // Every comparator call re-enters the VM, so it may allocate, collect,
    // error, and even MUTATE the table being sorted. Snapshot the values into a
    // Vec, sort that, and write back — which also makes the sort deterministic.
}
}

"The comparator may mutate the table being sorted" is the sentence to internalize. Sorting in place while calling back into script code is how the CVEs happened. The snapshot costs an allocation and removes the whole class.

table.concat is the answer to the O(n²) .. loop — compute the total length first, charge it, allocate once.

Step 6: The Full Surface Audit

#![allow(unused)]
fn main() {
#[test]
fn the_full_capability_surface_matches_the_golden_file() {
    let engine = build_production_engine();       // SAFE + whatever the capstone grants
    let mut surface = engine.enumerate_globals();
    for ud in engine.registered_userdata_types() {
        surface.extend(ud.methods().map(|m| format!("{}:{}", ud.name(), m)));
    }
    surface.sort();
    assert_eq!(surface, read_golden("tests/golden/capability-surface.txt"));
}
}

Run it, commit the golden file, and read it once, slowly. That file is your threat model's attack surface, and this is the only time you will see it all in one place.

The Trace

$ ember run -e 'print(pcall(function() error("boom") end))'
false   <argv>:1:38: boom

$ ember run --max-instructions 10000 -e '
local n = 0
while true do
  n = n + 1
  pcall(function() while true do end end)     -- pcall CANNOT swallow the budget
end'
error: instruction budget exhausted
$ echo $?
1

That second command is the security test made visible. If pcall caught ErrorKind::Limit, the outer while true would run forever, resetting nothing, and the budget would never terminate anything.

Now the capability surface:

$ ember run -e 'return type(io), type(os), type(load), type(require), type(debug)'
nil     nil     nil     nil     nil

$ ember run -e 'return type(print), type(math.floor), type(string.rep), type(table.concat)'
function        function        function        function

$ ember run -e 'return math.type(1), math.type(1.0), math.type("1")'
integer float   nil

$ ember run --max-memory 1048576 -e 'return ("x"):rep(1000000000)'
error: string.rep result too large
$ echo $?
1

And the sort hazard:

$ ember run -e 'local t = {3,1,2} table.sort(t, function(a,b) return true end) return #t'
error: invalid order function for sorting

Not a crash, not silent corruption, not an out-of-bounds read. Three possible outcomes, and only one of them is acceptable.

Expected Output

$ cargo test --test stdlib
test pcall_does_not_catch_limit_errors_because_that_would_defeat_the_budget ... ok
test default_globals_contain_no_ambient_authority ... ok
test the_full_capability_surface_matches_the_golden_file ... ok
test sort_survives_an_inconsistent_comparator ... ok
test sort_survives_a_comparator_that_mutates_the_table ... ok
test allocating_functions_check_the_budget_before_allocating ... ok
test format_rejects_unknown_specifiers_and_bounds_width ... ok

$ cargo test --features lua-compat --test lua_compat     # the library, against real Lua

Debugging Steps

A budget-exhausted script keeps running

pcall is catching ErrorKind::Limit. This is the bug the whole lab is arranged around.

`("x"):rep(1e9)` OOMs instead of erroring

The budget check is after the allocation, or checked_mul is missing and the size wrapped.

`table.sort` panics with an index out of bounds

A comparator that is not a strict weak ordering. Snapshot, bounds-check, and add the consistency check.

`table.sort` produces different results between runs

The comparator is reading a table that another part of the script mutates, or your sort is not stable and the corpus depends on it. Decide whether Ember's sort is stable and document it — Lua's is not, and that is a divergence either way.

`tostring(0/0)` differs between machines

You are formatting through the platform's printf. Choose a spelling and produce it yourself.

The golden-globals test fails after adding a function

Working as intended. Read the diff, decide whether the grant is wanted, and update the file deliberately.

`string.format("%s", huge_table)` produces megabytes of output

%s calls tostring, which may call __tostring, which may return anything. Bound the result.

Experiment

CLAIM. Lua patterns are not vulnerable to catastrophic backtracking the way regexes are — but they are still a CPU vector, and the instruction budget is what bounds them.

METHOD. Time string.match on a 100 KB subject with: (a) a simple literal; (b) (a*)*b (the classic regex bomb, which Lua patterns cannot express — check!); (c) %b() on deeply nested parentheses; (d) .-x (the lazy quantifier) with no match.

PREDICTION. Which of these is quadratic? Does the instruction budget stop the worst one, and after how many instructions?

RESULT. Record it in docs/learning/13-sandboxing.md, and add the worst case to tests/golden/limits/ so it stays bounded.

Test

#![allow(unused)]
fn main() {
#[test]
fn pcall_does_not_catch_limit_errors_because_that_would_defeat_the_budget() {
    let e = run_with_budget("while true do pcall(function() while true do end end) end", 100_000);
    assert_eq!(e.unwrap_err().kind, ErrorKind::Limit);
}

#[test]
fn pcall_catches_ordinary_runtime_errors() {
    assert_eq!(run("local ok, err = pcall(function() error('boom') end)
                    return tostring(ok) .. ':' .. tostring(err):match('boom')"), "false:boom");
}

#[test]
fn pcall_does_not_catch_host_errors() {
    // A host bug is the SERVICE's bug and must reach the service, not be
    // swallowed by a policy.
    let mut e = Engine::new();
    e.register_function("bad", |ctx, _| Err(ctx.error("host failure"))).unwrap();
    assert_eq!(e.execute("pcall(bad)").unwrap_err().kind, ErrorKind::Host);
}

#[test]
fn sort_survives_an_inconsistent_comparator() {
    let e = run("local t={5,3,1,4,2} table.sort(t, function(a,b) return true end) return 1");
    assert!(e.is_err(), "an inconsistent comparator must error, not corrupt");
    assert!(e.unwrap_err().message.contains("order function"));
}

#[test]
fn sort_survives_a_comparator_that_mutates_the_table() {
    // The snapshot design makes this well-defined instead of undefined.
    assert!(run("local t={3,1,2}
                 table.sort(t, function(a,b) t[1]=nil return a<b end)
                 return #t").is_ok());
}

#[test]
fn allocating_functions_check_the_budget_before_allocating() {
    for src in ["return ('x'):rep(1000000000)",
                "local t={} for i=1,100 do t[i]=('y'):rep(100000) end return table.concat(t)",
                "return string.format('%1000000000d', 1)"] {
        let e = run_with_memory_limit(src, 1 << 20).unwrap_err();
        assert_eq!(e.kind, ErrorKind::Limit, "{src}");
    }
}

#[test]
fn nan_and_infinity_print_the_same_on_every_platform() {
    assert_eq!(run("return tostring(1/0) .. ',' .. tostring(-1/0) .. ',' .. tostring(0/0)"),
               "inf,-inf,nan");
}

#[test]
fn math_type_exposes_the_numeric_subtype() {
    assert_eq!(run("return math.type(1)..','..math.type(1.0)..','..tostring(math.type('1'))"),
               "integer,float,nil");
}
}

Challenge Extensions

The utf8 library. char, codepoint, len, offset, charpattern. Lua's answer to Unicode-as-a-library, and it makes the byte-string decision comfortable rather than merely defensible.
os.time and os.date under CLOCK, with an injectable clock so tests are deterministic. Then note how much easier testing became, and generalize the lesson.
A stable table.sort. Lua's is not stable. Decide whether Ember's should be, implement it, and measure the cost. Then write the divergence entry either way.
Pattern-matching instruction charging. Charge string.find/gsub proportionally to characters examined rather than one unit per call. Re-run the experiment above.
A Capabilities::LOGGING set wrapping print plus structured fields, routed to tracing. The capstone wants this.

Deliverables

Capabilities with CORE/MATH/STRING/TABLE/PRINT/CLOCK/RANDOM and SAFE as the default.
base, math, string, table implemented; every function documented against the Lua manual section it corresponds to.
pcall does not catch Limit or Host errors, with the named test.
math.random behind RANDOM with a host-supplied seed; math.type present.
Every allocating function checks the memory budget before allocating; checked_mul on every size computation.
string.format rejects unknown specifiers and bounds output width.
table.sort snapshots, bounds-checks, and detects an inconsistent comparator.
tostring for inf/-inf/nan is platform-independent.
tests/golden/safe-globals.txt and tests/golden/capability-surface.txt committed and reviewed.
Every Lua library function not implemented is listed in appendix/lua-differences.md with its reason.
The pattern-matching CPU experiment recorded, with the worst case added to the corpus.

Validation / Self-check

Why must pcall not catch Limit errors? Give the two-line script that exploits it otherwise.
Why does pcall also propagate Host errors? Who is being protected?
Why is math.random excluded from SAFE, and how does that reason differ from os.execute's?
Name three functions that must check the budget before allocating, and the arithmetic hazard in each.
What can a naive table.sort do with an inconsistent comparator? Give the two defenses.
Why does table.sort snapshot the values? What script behavior makes that necessary?
Why does Ember print nan rather than the platform's spelling?
What is the capability surface, and why is the golden file more valuable than the assertions beside it?
Which Lua library defeats every sandbox built on global deletion, and why?

Next: Lab 22 — Modules.

Open-Source Engineer & Contributor