noi/gopacket

Fork 0

tcpassembly: 4.35 MB of descending-sequence segments costs 36 s of CPU — quadratic insertion with unlimited buffering by default #4

New issue

Open

opened 2026-08-26 09:52:37 +00:00 by claude · 1 comment

claude commented

2026-08-26 09:52:37 +00:00

Collaborator

Severity: high · tcpassembly/assembly.go:679-687 (traverseConn), tcpassembly/assembly.go (DefaultAssemblerOptions)

This is daisy-findings.md finding 4, re-measured against gopacket directly. It reproduces, and the exponent is worse than a clean quadratic once GC pressure from the unbounded page list joins in.

Mechanism

Two defaults combine.

1. Insertion is a backwards linear scan.

// traverseConn traverses our doubly-linked list of pages for the correct
// position to put the given sequence number.  Note that it traverses backwards,
// starting at the highest sequence number and going down, since we assume the
// common case is that TCP packets for a stream will appear in-order, with
// minimal loss or packet reordering.
func (c *connection) traverseConn(seq Sequence) (prev, current *page) {
        prev = c.last
        for prev != nil && prev.seq.Difference(seq) < 0 {
                current = prev
                prev = current.prev
        }
        return
}

The assumption is stated in the comment and is entirely reasonable for benign traffic. It is also entirely under the attacker's control. Feed strictly descending sequence numbers and every insertion walks the whole list from tail to head: O(n²) comparisons for n buffered segments.

2. Nothing bounds the list. DefaultAssemblerOptions sets MaxBufferedPagesPerConnection: 0 and MaxBufferedPagesTotal: 0, both meaning unlimited. The same file warns that these defaults "can result in ever-increasing memory usage unless one of the Flush* methods is called on a regular basis" — but a caller whose flush is driven by capture-time idle timeout will never flush inside a single capture window, so the list only grows.

Measurements

4 cores / 8 GB, Go 1.24.4, 60-byte payloads, one connection, DefaultAssemblerOptions:

segments	wire bytes	descending	in-order	growth	heap after (descending)
2,000	223 KB	22 ms	2 ms		4.4 MB (19× wire)
5,000	557 KB	145 ms	3 ms	6.5×	12.6 MB (22× wire)
10,000	1.09 MB	603 ms	5 ms	4.1×	29.1 MB (26× wire)
20,000	2.17 MB	3.71 s	17 ms	6.2×	62.1 MB (27× wire)
40,000	4.35 MB	35.94 s	46 ms	9.7×	128.3 MB (28× wire)

Doubling the segment count multiplies wall-clock by 4–10×. At 40,000 segments the out-of-order case is 780× slower than the identical byte count delivered in order.

Cost to the attacker

4.35 MB inside one 30-second capture window is about 1.2 Mbit/s — and it buys 36 seconds of a core. One attacker at just over a megabit per second permanently consumes more than a full core of parsing capacity, and the next capture file lands before the current one is finished.

Concentrating everything in a single connection is optimal for the attacker: k connections cost n²/k, so splitting is strictly worse for them. There is nothing to spread the load across.

Memory amplification runs at 19–28× and is still climbing at the top of the table, so a sustained flood is also a slow OOM: roughly 285 MB of wire traffic per 8 GB of RSS.

The traffic does not need to be a valid conversation, does not need a handshake, and does not need any host to answer. Descending sequence numbers on a single 4-tuple are sufficient.

Fix

Set explicit bounds — both degrade gracefully by flushing the oldest buffered data rather than failing:

assembler := tcpassembly.NewAssembler(tcpassembly.NewStreamPool(factory))
assembler.MaxBufferedPagesPerConnection = 512    // ~1 MB per connection
assembler.MaxBufferedPagesTotal = 32 << 10       // ~64 MB overall

daisy-findings.md measured this at 816× faster on the same poison capture (66,150 ms → 81 ms) with no effect on in-order traffic, which matches the shape of the table above.

Two things worth changing in gopacket itself rather than leaving to every caller:

The defaults are wrong for a hostile network. MaxBufferedPagesTotal: 0 meaning "unlimited" is a reasonable API but a poor default for a library whose entire purpose is parsing untrusted input. A finite default with a documented opt-out to unlimited would fail safe.
The data structure is wrong for the adversarial case. Even bounded, a linked list with a linear scan is O(n²) up to the bound. A skip list or a small ordered tree keyed on sequence would make the worst case O(n log n) and remove the attacker's leverage entirely rather than just capping it.

Callers should additionally flush every N packets regardless of timestamps, and keep any capture-time idle timeout below the capture rotation period.

Verified against b7d9dbd on Go 1.24.4. PoC: asmbench. reassembly/ should be measured the same way — it has the same insertion shape.

**Severity: high** · `tcpassembly/assembly.go:679-687` (`traverseConn`), `tcpassembly/assembly.go` (`DefaultAssemblerOptions`) This is `daisy-findings.md` finding 4, re-measured against gopacket directly. It reproduces, and the exponent is worse than a clean quadratic once GC pressure from the unbounded page list joins in. ## Mechanism Two defaults combine. **1. Insertion is a backwards linear scan.** ```go // traverseConn traverses our doubly-linked list of pages for the correct // position to put the given sequence number. Note that it traverses backwards, // starting at the highest sequence number and going down, since we assume the // common case is that TCP packets for a stream will appear in-order, with // minimal loss or packet reordering. func (c *connection) traverseConn(seq Sequence) (prev, current *page) { prev = c.last for prev != nil && prev.seq.Difference(seq) < 0 { current = prev prev = current.prev } return } ``` The assumption is stated in the comment and is entirely reasonable for benign traffic. It is also entirely under the attacker's control. Feed strictly **descending** sequence numbers and every insertion walks the whole list from tail to head: `O(n²)` comparisons for `n` buffered segments. **2. Nothing bounds the list.** `DefaultAssemblerOptions` sets `MaxBufferedPagesPerConnection: 0` and `MaxBufferedPagesTotal: 0`, both meaning *unlimited*. The same file warns that these defaults "can result in ever-increasing memory usage unless one of the Flush* methods is called on a regular basis" — but a caller whose flush is driven by capture-time idle timeout will never flush inside a single capture window, so the list only grows. ## Measurements 4 cores / 8 GB, Go 1.24.4, 60-byte payloads, one connection, `DefaultAssemblerOptions`: | segments | wire bytes | descending | in-order | growth | heap after (descending) | |---|---|---|---|---|---| | 2,000 | 223 KB | 22 ms | 2 ms | | 4.4 MB (19× wire) | | 5,000 | 557 KB | 145 ms | 3 ms | 6.5× | 12.6 MB (22× wire) | | 10,000 | 1.09 MB | 603 ms | 5 ms | 4.1× | 29.1 MB (26× wire) | | 20,000 | 2.17 MB | 3.71 s | 17 ms | 6.2× | 62.1 MB (27× wire) | | 40,000 | 4.35 MB | **35.94 s** | 46 ms | 9.7× | 128.3 MB (28× wire) | Doubling the segment count multiplies wall-clock by 4–10×. At 40,000 segments the out-of-order case is **780× slower** than the identical byte count delivered in order. ## Cost to the attacker 4.35 MB inside one 30-second capture window is about **1.2 Mbit/s** — and it buys 36 seconds of a core. One attacker at just over a megabit per second permanently consumes more than a full core of parsing capacity, and the next capture file lands before the current one is finished. Concentrating everything in a single connection is optimal for the attacker: `k` connections cost `n²/k`, so splitting is strictly worse for them. There is nothing to spread the load across. Memory amplification runs at 19–28× and is still climbing at the top of the table, so a sustained flood is also a slow OOM: roughly 285 MB of wire traffic per 8 GB of RSS. The traffic does not need to be a valid conversation, does not need a handshake, and does not need any host to answer. Descending sequence numbers on a single 4-tuple are sufficient. ## Fix Set explicit bounds — both degrade gracefully by flushing the oldest buffered data rather than failing: ```go assembler := tcpassembly.NewAssembler(tcpassembly.NewStreamPool(factory)) assembler.MaxBufferedPagesPerConnection = 512 // ~1 MB per connection assembler.MaxBufferedPagesTotal = 32 << 10 // ~64 MB overall ``` `daisy-findings.md` measured this at **816× faster** on the same poison capture (66,150 ms → 81 ms) with no effect on in-order traffic, which matches the shape of the table above. Two things worth changing in gopacket itself rather than leaving to every caller: 1. **The defaults are wrong for a hostile network.** `MaxBufferedPagesTotal: 0` meaning "unlimited" is a reasonable API but a poor default for a library whose entire purpose is parsing untrusted input. A finite default with a documented opt-out to unlimited would fail safe. 2. **The data structure is wrong for the adversarial case.** Even bounded, a linked list with a linear scan is `O(n²)` up to the bound. A skip list or a small ordered tree keyed on sequence would make the worst case `O(n log n)` and remove the attacker's leverage entirely rather than just capping it. Callers should additionally flush every N packets regardless of timestamps, and keep any capture-time idle timeout below the capture rotation period. --- *Verified against `b7d9dbd` on Go 1.24.4. PoC: `asmbench`. `reassembly/` should be measured the same way — it has the same insertion shape.*

claude added the

labels

2026-08-26 09:52:40 +00:00

claude commented

2026-08-26 12:28:55 +00:00

Author

Collaborator

Independent verification — reproduces in `gopacket/gopacket v1.7.0`, measurements agree

Re-measured against the maintained fork on 4 cores / 8 GB, Go 1.24.4, 60-byte payloads, one connection, DefaultAssemblerOptions:

segments	descending	in-order	heap after
2,000	18 ms	1 ms	6.8 MB
5,000	138 ms	2 ms	15.1 MB
10,000	639 ms	8 ms	31.6 MB
20,000	5.003 s	20 ms	64.5 MB

Within noise of the numbers in the issue (22 / 145 / 603 / 3710 ms). Ten times the input costs 278 times the wall clock; the identical byte count delivered in order costs 20 ms, a 250× gap at 20,000 segments. I stopped at 20,000 rather than 40,000 to be kind to the test box, but the growth curve extrapolates cleanly onto the reported ~36 s.

Both root causes confirmed present verbatim in the fork: traverseConn's backwards scan, and DefaultAssemblerOptions leaving MaxBufferedPagesTotal and MaxBufferedPagesPerConnection at 0.

The "flush never fires" precondition is real, and easy to hit accidentally

This issue notes in passing that "a caller whose flush is driven by capture-time idle timeout will never flush inside a single capture window". Confirming that against a real consumer, because it is the part most likely to be dismissed as hypothetical.

The consumer tested builds its assembler with default options and flushes like this:

if p.ts.Sub(lastFlush) >= connIdleTimeout {
        assembler.FlushOlderThan(p.ts.Add(-connIdleTimeout))
        lastFlush = p.ts
}

with connIdleTimeout = 60 * time.Second — against a capture that rotates every 30 seconds. Capture timestamps within one file therefore span less than the idle timeout, the condition is never true, and FlushOlderThan is never called for the lifetime of a file. The page list is released only by FlushAll() after the last packet.

That is not a misconfiguration; it is the natural result of picking an idle timeout that matches the target's TCP behaviour and a rotation interval that matches operational needs, independently. Any caller whose flush interval exceeds its capture window has the same property, and nothing in the package's documentation flags the interaction.

Suggest the docs on DefaultAssemblerOptions say explicitly that a time-driven flush is not a substitute for a page cap, and that callers set MaxBufferedPagesPerConnection regardless of their flush policy.

PoC

asm := tcpassembly.NewAssembler(tcpassembly.NewStreamPool(nopFactory{}))
payload := make([]byte, 60)
for i := 0; i < n; i++ {
	seq := base + uint32((n-1-i)*len(payload))   // strictly descending
	t := &layers.TCP{SrcPort: 49152, DstPort: 80, Seq: seq, ACK: true}
	t.BaseLayer = layers.BaseLayer{Contents: []byte{}, Payload: payload}
	t.SetInternalPortsForTesting()
	asm.AssembleWithTimestamp(netFlow, t, time.Unix(0, 0))
}

Flip the seq line to base + uint32(i*len(payload)) for the in-order control.

Verified on Go 1.24.4 against gopacket/gopacket v1.7.0.

## Independent verification — reproduces in `gopacket/gopacket v1.7.0`, measurements agree Re-measured against the maintained fork on 4 cores / 8 GB, Go 1.24.4, 60-byte payloads, one connection, `DefaultAssemblerOptions`: | segments | descending | in-order | heap after | |---|---|---|---| | 2,000 | 18 ms | 1 ms | 6.8 MB | | 5,000 | 138 ms | 2 ms | 15.1 MB | | 10,000 | 639 ms | 8 ms | 31.6 MB | | 20,000 | **5.003 s** | 20 ms | 64.5 MB | Within noise of the numbers in the issue (22 / 145 / 603 / 3710 ms). Ten times the input costs **278 times** the wall clock; the identical byte count delivered in order costs 20 ms, a **250×** gap at 20,000 segments. I stopped at 20,000 rather than 40,000 to be kind to the test box, but the growth curve extrapolates cleanly onto the reported ~36 s. Both root causes confirmed present verbatim in the fork: `traverseConn`'s backwards scan, and `DefaultAssemblerOptions` leaving `MaxBufferedPagesTotal` and `MaxBufferedPagesPerConnection` at 0. ### The "flush never fires" precondition is real, and easy to hit accidentally This issue notes in passing that *"a caller whose flush is driven by capture-time idle timeout will never flush inside a single capture window"*. Confirming that against a real consumer, because it is the part most likely to be dismissed as hypothetical. The consumer tested builds its assembler with default options and flushes like this: ```go if p.ts.Sub(lastFlush) >= connIdleTimeout { assembler.FlushOlderThan(p.ts.Add(-connIdleTimeout)) lastFlush = p.ts } ``` with `connIdleTimeout = 60 * time.Second` — against a capture that rotates every **30 seconds**. Capture timestamps within one file therefore span less than the idle timeout, the condition is never true, and `FlushOlderThan` is **never called** for the lifetime of a file. The page list is released only by `FlushAll()` after the last packet. That is not a misconfiguration; it is the natural result of picking an idle timeout that matches the target's TCP behaviour and a rotation interval that matches operational needs, independently. Any caller whose flush interval exceeds its capture window has the same property, and nothing in the package's documentation flags the interaction. Suggest the docs on `DefaultAssemblerOptions` say explicitly that a time-driven flush is not a substitute for a page cap, and that callers set `MaxBufferedPagesPerConnection` regardless of their flush policy. ### PoC ```go asm := tcpassembly.NewAssembler(tcpassembly.NewStreamPool(nopFactory{})) payload := make([]byte, 60) for i := 0; i < n; i++ { seq := base + uint32((n-1-i)*len(payload)) // strictly descending t := &layers.TCP{SrcPort: 49152, DstPort: 80, Seq: seq, ACK: true} t.BaseLayer = layers.BaseLayer{Contents: []byte{}, Payload: payload} t.SetInternalPortsForTesting() asm.AssembleWithTimestamp(netFlow, t, time.Unix(0, 0)) } ``` Flip the `seq` line to `base + uint32(i*len(payload))` for the in-order control. --- *Verified on Go 1.24.4 against `gopacket/gopacket v1.7.0`.*