19 - Recursion: stack overflow and billion-laughs

Objectives: Understand why unbounded recursion causes a fatal stack overflow that recover() cannot catch, and how this repo defends against it with an absolute depth ceiling. Learn how a TrueType composite glyph can amplify a tiny input into billions of operations (billion-laughs), and how a shared budget counter stops the explosion before it starts. Estimated time: 20 minutes.

---

What this actually means (plain English)

No jargon — here's what the ideas in this lesson actually mean, and why they matter.

• Recursion = "to open a Russian nesting doll, first open the one inside it." Every function call to parseElement opens another doll; the parser cannot return until every child is fully resolved.
• The call stack = "a stack of cafeteria trays with a fixed ceiling." Each function call adds a tray; once the stack touches the ceiling, the whole structure crashes — and no one can catch it on the way down.
• A stack overflow is fatal = "the fire alarm that cuts the power." Unlike a normal panic, a goroutine stack overflow is handled by the Go runtime before recover() ever runs, so the process is already dead — the only defence is the depth ceiling in parseElement.
• Billion-laughs = "a chain letter that tells every reader to send copies to ten friends." A composite glyph references K children, each referencing K more; 8 levels in, a few-KB file triggers K^8 rasterizer invocations.
• A depth ceiling = "a bouncer counting floors — turn around at floor 8." maxNestingDepth in tinyxml2-go and the depth > 8 check in glyphContours stop linear chains before they overflow the stack.
• A budget counter (glyphBudget) = "a shared taxi meter for the whole trip." The depth ceiling alone allows a legal-depth tree with K=1000 children per level; glyphBudget.components is decremented by every recursive call across the entire expansion tree, so the meter runs out long before K^8 work is done.

Why it matters: both attacks are triggered by a single call to your parser with a crafted input file. They require no authentication, no network, no memory corruption — just a malformed file dropped on your API endpoint.

See it — exponential fan-out. Each composite glyph references K children, each of which references K more. Depth d alone is legal, but the work is K^d. A plain depth ceiling does not help once the depth is within bounds — only a shared budget counter (glyphBudget), decremented across the whole expansion, stops it.

---

Part 1 — XML and the fatal stack overflow

How the recursive parser works

tinyxml2-go/tinyxml2.go builds an XML DOM by calling parseElement once per node.

In plain terms: a function is a named, reusable chunk of code that does one job — like parseElement, whose job is to read one XML tag and everything inside it; "calling" it just means running it. "Building an XML DOM" means constructing, in the computer's memory, a tree-shaped map of the document's tags and their nesting. Recursion means a function calling itself to handle a smaller version of the same problem.

When it reads a child start-tag, it recurses — parseElement calls parseElement again to read the tag nested just inside the current one:

// from tinyxml2-go/tinyxml2.go
func parseElement(dec *xml.Decoder, se xml.StartElement, depth int) (*Node, error) {
    if depth > maxNestingDepth {
        return nil, fmt.Errorf("XML nesting exceeds maximum depth %d", maxNestingDepth)
    }
    // ...
    case xml.StartElement:
        child, err := parseElement(dec, v, depth+1)
        // ...
}

In plain terms: this code says "before doing anything else, check whether we've nested deeper than maxNestingDepth; if so, stop and report an error. Otherwise, when a child tag starts, call parseElement again — on that child — one level deeper." Each such nested call waits for its child call to finish before it can finish itself, which is exactly what "recursion" means in practice.

Each call to parseElement lives on the goroutine stack until its matching EndElement is read.

In plain terms: a goroutine is a lightweight, independently-running worker inside a Go program — one of possibly many running at once. The stack is a region of memory that tracks every function call in progress for that worker, like a pile of index cards (one per call, added on top when a call starts, removed when it finishes); "lives on the stack" means the call's information sits on that pile until it's done. A few KB is a few kilobytes — a kilobyte being about a thousand bytes, a byte being a basic unit of digital storage — and growing the stack "dynamically" means its size expands automatically as needed.

With deeply nested XML (<a><b><c>...), this grows linearly with nesting depth. Go starts goroutines with a small stack (a few KB) and grows it dynamically — but growth has a ceiling, and past that the runtime terminates the program with no opportunity to recover.

The absolute ceiling

The constant maxNestingDepth is the safety valve:

// from tinyxml2-go/tinyxml2.go
const maxNestingDepth = 10000

In plain terms: this line defines a fixed number, named maxNestingDepth, permanently set to 10000 — the most levels of nesting the parser will ever allow before refusing to go further.

It lives right above parseElement and is checked as the very first thing on every recursive call. The comment in the source is explicit (in plain terms: a "comment" is a note written into the source code — the human-readable text a programmer types to explain what the code does; the computer ignores it entirely when running the program):

Going far past it would overflow the goroutine stack — a fatal error recover() cannot catch — so the parser returns an error instead.

(In plain terms: "returns an error" means the function stops and hands back, to whoever called it, a special value that signals "something went wrong" instead of a normal result — the caller is then responsible for noticing and handling it.)

10 000 is far higher than any real XML document needs; it is well below the point where Go would crash.

Why recover() cannot save you

// This does NOT work for a stack overflow:
func safeParseElement(...) (n *Node, err error) {
    defer func() {
        if r := recover(); r != nil {
            err = fmt.Errorf("caught: %v", r)
        }
    }()
    return parseElement(...)
}

In plain terms: this code tries a safety net — "run parseElement, and if it panics (crashes with a special kind of error), catch that panic and turn it into an ordinary error instead of letting the program die." The point of the example is that this safety net does not actually work for the specific kind of crash a stack overflow causes, which the prose right after explains.

recover() catches panics (in plain terms: a "panic" in Go is a sudden, controlled crash — the program stops what it's doing and starts unwinding, unless something catches it) — explicit panic(...) calls or nil-pointer dereferences (in plain terms: an attempt to use a value that was supposed to point to something in memory but points to nothing at all). A stack overflow is handled by the Go runtime itself, before recover ever runs. The program is already dead when it would fire.

recover() and stack overflows

defer/recover is not a substitute for a depth ceiling. If you remove maxNestingDepth, no amount of recover calls will save a process handed a 10 001-deep XML file.

The config-aware variant

ParseWithConfig uses parseElementLimited, which enforces both the user-visible MaxNestingDepth from the config AND the hard maxNestingDepth ceiling. (In plain terms: a "config" — short for configuration — is a bundle of settings passed into a function to control how it behaves, here bundled into a struct, which is just a named grouping of related values, similar to a form with several labeled fields, or "fields," each holding one piece of data.)

// from tinyxml2-go/tinyxml2.go
func parseElementLimited(
    dec *xml.Decoder,
    se xml.StartElement,
    config *Config,
    depth int,
    nodeCount *int,
) (*Node, error) {
    // Hard absolute ceiling — applies even to UnlimitedConfig.
    if depth > maxNestingDepth {
        return nil, fmt.Errorf("XML nesting exceeds maximum depth %d", maxNestingDepth)
    }
    // Soft user-configurable ceiling.
    if config.MaxNestingDepth > 0 && depth > config.MaxNestingDepth {
        return nil, ErrNestingTooDeep
    }
    // ...
}

In plain terms: this function checks two limits in order — first the fixed, non-negotiable ceiling (maxNestingDepth) that applies no matter what; then a second, adjustable ceiling that the caller supplied through config. If either is crossed, the function stops and hands back an error instead of continuing.

The two-layer design matters: the soft limit gives callers control; the hard limit is the last-resort guarantee even when UnlimitedConfig is passed.

Iterative search avoids the same problem in traversal

Searching a deep tree with recursion has the same risk. FindDeep and FindAllDeep use an explicit stack (a Go slice) instead of the call stack. (In plain terms: "traversal" just means visiting every node of the tree one by one, in some order, to look for something. A "slice" in Go is a resizable list of values sitting in memory — here it's being used to build the parser's own to-do list of "nodes I still need to check," standing in for the automatic stack the computer would otherwise use for recursive calls.)

// from tinyxml2-go/tinyxml2.go
func (n *Node) FindDeep(name string) *Node {
    stack := []*Node{n}
    for len(stack) > 0 {
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if cur.Name == name {
            return cur
        }
        for i := len(cur.Children) - 1; i >= 0; i-- {
            stack = append(stack, cur.Children[i])
        }
    }
    return nil
}

In plain terms: instead of having the function call itself for each child (which would use up the goroutine's built-in stack), this code keeps its own list — stack — of nodes still waiting to be checked. It repeatedly takes the last node off that list, checks whether it's the one being searched for, and if not, adds all of that node's children to the list to check later. This achieves the same "visit every node" result as recursion, but without nesting function calls.

A heap-allocated slice can grow as large as available memory; the goroutine call stack cannot. (In plain terms: the "heap" is the large, flexible pool of memory a program can request from at any time — as opposed to the stack, which is small and reserved automatically for function calls in progress. "Heap-allocated" means this list lives in that large flexible pool, so it can keep growing far past what the stack could ever hold.) Converting recursion to an explicit stack is the standard pattern when depth is unbounded.

Try it

From the repo root, run the tinyxml2 tests including the nesting limit. (In plain terms: a "test" here is a small, automated check written by a programmer that runs a piece of code and confirms it behaves as expected — running this command tells the computer "go find the tests whose names match Nesting or DepthCeiling and run them.")

cd tinyxml2-go && go test -v -run 'Nesting|DepthCeiling' ./...

Expected outcome: the test generates XML nested deeper than MaxNestingDepth and expects ErrNestingTooDeep. It also generates XML deeper than maxNestingDepth and expects the hard-ceiling error. Both should pass (PASS). The process should not crash.

---

Part 2 — TrueType composite glyphs and billion-laughs

What a composite glyph is

A TrueType font stores outlines in a table called glyf. Most glyphs (letters, numbers) are simple — they store contour points directly. But some glyphs are composite: instead of points, they store a list of (child glyph ID, transform) pairs. The rasterizer resolves each reference, applies the transform, and stitches the results together. (In plain terms: a "glyph" is the visual shape of one character in a font — the drawing of the letter "A", for instance. "Contour points" are the individual coordinates that trace the outline of that shape, like dots connected to form the letter's edge. A "rasterizer" is the piece of code that turns those outline instructions into an actual grid of pixels/dots you can see on screen. "Resolves each reference" means: for each child glyph ID that's mentioned, the rasterizer goes and looks up what that child glyph actually is.)

This is legitimate and useful: many fonts store accented characters as a base letter plus a floating accent mark, reusing the same outline twice.

The amplification

A malicious font can use this indirection as a multiplier. Suppose each composite glyph references K children, and each child is itself composite, for 8 levels:

Level 0 (top glyph): 1 invocation
Level 1:             K invocations
Level 2:             K² invocations
...
Level 8:             K⁸ invocations

In plain terms: an "invocation" is just one instance of running (calling) the glyph-resolving code. This diagram shows how the count of required runs multiplies at each level of nesting — 1 at the top, then K, then K times K, and so on — because every child glyph at one level can itself demand K more at the next level.

With K=10, that is 100 000 000 invocations triggered by requesting a single character. The font file stays tiny because each glyph definition is short; the work explodes only during rasterization. This is exactly the billion-laughs shape: tiny storage, exponential work.

How the rasterizer enters this path

In stb-truetype-go/sfnt.go, rasterizeGlyph calls glyphContours for the top-level glyph. If numContours < 0, the glyph is composite and compositeContours is called, which calls glyphContours recursively for each component:

// from stb-truetype-go/sfnt.go
func (f *Font) glyphContours(gid uint16, depth int, b *glyphBudget) ([][]glyphPoint, error) {
    if depth > 8 {
        return nil, errors.New("truetype: composite glyph nesting too deep")
    }
    if b.components--; b.components < 0 {
        return nil, errors.New("truetype: composite glyph component budget exceeded")
    }
    // ...
    if numContours < 0 {
        return f.compositeContours(g, depth, b)
    }
    // simple glyph path
    contours, err := parseSimpleGlyph(g, int(numContours))
    // ...
    for _, c := range contours {
        b.points -= len(c)
    }
    if b.points < 0 {
        return nil, errors.New("truetype: composite glyph point budget exceeded")
    }
    return contours, nil
}

In plain terms: every time this function runs, it first checks it hasn't nested more than 8 levels deep, then spends one unit from the shared budget (b.components) and refuses to continue if the budget has run out. If the glyph turns out to be composite, it recurses into compositeContours (which in turn calls glyphContours again for each child); otherwise it reads the glyph's own points directly, spends budget from b.points for each one, and hands back the finished list of contours to whoever called it. b here is a pointer — in plain terms, not a copy of the budget but a shared reference to the one true budget object, so every nested call is spending down the same pool, not separate pools.

The glyphBudget type

The depth check alone stops linear depth (e.g. a chain 100 levels deep) but does not stop exponential fan-out (a tree that is only 8 levels deep but has K=1000 children at each level). The glyphBudget struct is the solution (in plain terms: recall from earlier that a "struct" is just a named grouping of related values — here, two running counters bundled together):

// from stb-truetype-go/sfnt.go
type glyphBudget struct {
    components int // remaining glyph invocations (call-tree nodes)
    points     int // remaining total contour points
}

const (
    maxGlyphComponents = 4096    // total component invocations per top-level glyph
    maxGlyphPoints     = 1 << 20 // total contour points per top-level glyph (≈ 1 M)
)

In plain terms: the first block defines the shape of a "budget" — one number tracking how many glyph invocations are still allowed, and another tracking how many contour points are still allowed. The second block sets the starting amounts: 4096 invocations and about a million (1 << 20, meaning 2 multiplied by itself 20 times) points, per request for one top-level glyph.

The comment on glyphBudget is the clearest statement of the threat:

The depth cap alone does not stop a malicious composite with high fan-out (K children per level, 8 levels ≈ K^8 invocations from a tiny file — a billion-laughs amplification), so a shared counter caps total components visited and total points produced.

components counts every glyphContours call across the whole expansion tree. points counts every contour point produced. Both counters are shared across the entire recursion via a pointer, so the budget is global to the top-level glyph request.

The budget is initialized once per rasterize call

// from stb-truetype-go/sfnt.go
func rasterizeGlyph(f *Font, r rune, size float64) (*image.Gray, GlyphMetrics, error) {
    // ...
    budget := glyphBudget{components: maxGlyphComponents, points: maxGlyphPoints}
    contours, err := f.glyphContours(gid, 0, &budget)
    // ...
}

In plain terms: each time a glyph needs to be rasterized (drawn), a brand-new budget is created, filled to its starting amounts, and then a reference to that one budget (&budget, a pointer to it) is handed down into glyphContours. Because it's a shared reference rather than a fresh copy, every recursive call along the way — no matter how deep — subtracts from that same single budget.

One pointer, threaded through the entire call tree, ensures every recursive invocation decrements the same counters.

Two guards are better than one

Depth cap: blocks chains and guarantees the call stack cannot overflow. Budget counter: blocks exponential fan-out even within the legal depth limit. Neither alone is sufficient — use both.

Try it

Run the stb-truetype tests with the race detector. (In plain terms: a "race detector" is a tool that watches a running program for a "data race" — a bug where two goroutines, the independently-running workers mentioned earlier, read and write the same piece of memory at the same time without coordination, which can corrupt data unpredictably.)

cd stb-truetype-go && go test -race -v ./...

Expected outcome: all tests pass; no data race reported. The budget counters live on the stack of rasterizeGlyph and are never shared across goroutines, so the race detector stays quiet.

---

How the two attacks compare

	XML deep nesting	TrueType billion-laughs
Shape	linear depth	exponential fan-out
Crash mechanism	fatal stack overflow	CPU/memory exhaustion
recover() helps?	no	n/a (not a crash)
Primary guard	depth ceiling	budget counter
Secondary guard	node count limit	depth ceiling
Where in this repo	tinyxml2-go/tinyxml2.go	stb-truetype-go/sfnt.go

---

Key takeaways

• A fatal goroutine stack overflow cannot be caught with recover(). The only defence is an explicit depth ceiling checked before each recursive call.
• maxNestingDepth = 10000 in tinyxml2-go acts as an absolute hard ceiling even for the "unlimited" parse path, keeping the process alive.
• Iterative traversal (FindDeep, FindAllDeep) uses a heap-allocated slice as an explicit stack, sidestepping goroutine stack limits entirely for search.
• The billion-laughs attack exploits composite indirection: a small file produces exponential work. A depth ceiling stops linear chains; only a shared budget counter (components + points) stops exponential fan-out.
• glyphBudget in stb-truetype-go/sfnt.go is threaded as a pointer through the entire composite-glyph call tree so all recursive invocations decrement the same global counters — making the budget truly shared and impossible to circumvent by splitting work across branches.