ebpf

32 bytes verified, 40 didn't: parsing HTTP inside the eBPF verifier's budget --- title: "32 bytes verified, 40 didn't: parsing HTTP inside the eBPF verifier's budget" published: true description: "A classic eBPF loop verified over 32 bytes and failed at 40. bpf_loop() and open-coded iterators parsed all 256 bytes in a few hundred verifier instructions." tags: ebpf, linux, go, observability series: Building a zero-instrumentation eBPF agent --- My eBPF agent traces HTTPS traffic without touching the application: uprobes on OpenSSL's SSL_write/SSL_read and on Go's crypto/tls copy the plaintext out of the process before encryption, and the agent turns it into OpenTelemetry spans. The kernel side copies a bounded prefix of each payload — 256 bytes — into a ring buffer, and all the HTTP parsing happens in userspace. The obvious question is why. Parsing in the kernel would mean shipping less data and filtering earlier. "The verifier won't allow it" is the usual answer, but I wanted a number, not folklore. So I wrote the in-kernel parser five different ways and recorded exactly what the verifier said about each. The answer turned out to be more interesting than "no". Repo: sAchin-680/eBPF-observability-agent The setup Every attempt is a real uprobe program that reads up to 256 bytes of the buffer passed to SSL_write and tries to find Host: headers. None is ever attached — they exist to be loaded, and the interesting ones are the loads that fail. Each program is loaded on its own with cilium/ebpf, because loading them together would stop at the first rejection and hide the rest. The test records the outcome, the time, and — new for this post — the verifier's own count of instructions it processed. I originally ran this on kernel 6.8. For this post I re-ran everything on 6.18. Every accept/reject outcome was identical. !Terminal recording on kernel 6.18: the classic per-header parse is accepted at 32 bytes and rejected from 40 bytes up, while the bpf_loop and bpf_for versions are accepted at 256 bytes, then both pass every correctness check Attempt 1: scan until the data says stop The natural way to find the end of a header block: while (data[i] != '\0') { if (data[i] == '\n') lines++; i++; } Rejected: invalid read from stack R3 off=0 size=1 What's interesting is how it fails. Since kernel 5.3 the verifier accepts bounded loops by simulating every iteration. It did exactly that here: it followed i all the way to the end of the 256-byte buffer and refused the read that walks off it. It isn't objecting to the loop. It found the overrun. Attempt 2: bound it by the caller's length for (int i = 0; i < num; i++) { ... } Rejected the same way. The verifier's register state shows why: R6_r=Pscalar(smin=umin=250, smax=umax=0x7fffffff, ...) invalid read from stack R2 off=0 size=1 umax=0x7fffffff. The length comes from userspace, so the verifier knows nothing about it and has to assume two billion. A bound the verifier can't see is no bound at all. Attempt 3: bound it by the buffer for (int i = 0; i < BUF; i++) { if (data[i] == '\n') lines++; } Accepted. 22 instructions, and the verifier processed 6,389 instructions to prove it safe — walking all 256 iterations. But it only counts line breaks. Real parsing needs per-line work. Attempt 4: actually parse — and hit the wall The smallest thing that resembles parsing headers: at each \r\n, check whether the line that just ended starts with Host:, then remember where the next line begins. for (int i = 0; i + 1 < size; i++) { if (data[i] != '\r' || data[i + 1] != '\n') continue; if (line_start + 5 < size && data[line_start] == 'H' && data[line_start + 1] == 'o' && data[line_start + 2] == 's' && data[line_start + 3] == 't' && data[line_start + 4] == ':') matches++; line_start = i + 2; } I compiled the identical code at different buffer sizes. Every version is 76 instructions — the compiler doesn't unroll it. The difference is entirely in how much work the verifier does: | Buffer | Outcome | Instructions processed by the verifier | | ---: | :--- | ---: | | 32 bytes | accepted | 158,806 | | 40 bytes | rejected, E2BIG | over 1,000,000 | | 48 bytes | rejected, E2BIG | over 1,000,000 | | 56 bytes | rejected, E2BIG | over 1,000,000 | | 64 bytes | rejected, E2BIG | over 1,000,000 | | 256 bytes | rejected, E2BIG | over 1,000,000 | E2BIG ("argument list too long") is what the verifier returns when it exhausts its budget of one million processed instructions. 32 bytes uses 16% of the budget. 40 bytes exceeds it. A 25% bigger buffer costs more than six times the verification work. A Host header alone is often longer than 32 bytes, so this isn't a tuning problem — this shape of parser simply can't cover a real request. Why it explodes The verifier walks every iteration and every branch. Normally it keeps the cost down by pruning: when it reaches an instruction in a state equivalent to one it has already proven safe, it stops exploring. line_start defeats that. It's used as a memory offset, so the verifier must track its exact value — and every path through the data sets it differently, depending on where the \r\n pairs fell. States that differ only in line_start can't be merged, so the number of live paths multiplies with each byte. Counting line breaks in attempt 3 has no such variable, which is why it stays cheap over 256 bytes. !Diagram: in the classic loop the verifier explores a tree of paths where each line break sets line_start to a different value, so paths multiply; with bpf_loop the callback is verified once for any index, costing 149 instructions for 256 bytes An aside: asking for the log changed the answer On the 6.8 machine, requesting the verifier's log for the 64-byte program changed the reported error from E2BIG to EINVAL, and verification went from 0.3 s to 5.7 s. Worse: the loader retries with a progressively bigger log buffer while the log is truncated, and no buffer was ever big enough. The test process reached 5.3 GB resident on a 5.9 GB machine and was OOM-killed. Verification itself took 280 ms. Only the log was unbounded. The experiment now loads the size sweep with logging disabled and asks only for the verifier's statistics, which are a few lines long. Attempt 5: the two features built for exactly this My original conclusion was "in-kernel parsing is ruled out." That conclusion was only about the classic loop. Newer kernels have two features designed for loops the verifier can't afford to walk: - bpf_loop() (kernel 5.17): a helper that calls a callback N times. The verifier checks the callback once, with the index known only to be in [0, N). - Open-coded iterators (bpf_for, kernel 6.4): an ordinary-looking loop that the verifier checks by converging on a stable state, rather than by walking every iteration. Here's the same parse with bpf_loop(), over the full 256 bytes: static long parse_step(__u64 index, void *arg) { struct parse_ctx *c = arg; __u64 i = index; __u64 ls; if (i >= BUF - 1) return 1; if (c->data[i] != '\r' || c->data[i + 1] != '\n') return 0; ls = c->line_start; if (ls < BUF - 5 && c->data[ls] == 'H' && c->data[ls + 1] == 'o' && c->data[ls + 2] == 's' && c->data[ls + 3] == 't' && c->data[ls + 4] == ':') c->matches++; c->line_start = i + 2; return 0; } /* in the uprobe: */ bpf_loop(BUF - 1, parse_step, &c, 0); First, the verifier and the compiler disagreed My first versions of both were rejected instantly. Not because of the budget — because of how I'd written the bounds checks: invalid unbounded variable-offset read from stack R5 invalid variable-offset read from stack R2 var_off=(0x0; 0x1ff) off=-256 size=1 Two classic mistakes: 1. if (i + 1 >= BUF) let the compiler test a copy of the index, so the register actually used as the offset was never bounded in the verifier's eyes. Testing i >= BUF - 1 directly bounds the register that's used. 2. if (line_start + 5 < BUF) looks like it proves line_start < 251. In 32-bit arithmetic it doesn't: the addition could wrap, so the verifier learns nothing about line_start from it. line_start < BUF - 5 says the same thing in a form it can use. The agent's production capture code already follows the same rule — it masks the copy length with n &= (MAX_DATA - 1) rather than relying on an earlier if, because the mask states the bound in a form the verifier accepts on every path. Bounds have to be written for the verifier, not just for the reader. Then: 256 bytes, a few hundred instructions | Version | Buffer | Outcome | Instructions processed | | :--- | ---: | :--- | ---: | | classic bounded loop | 32 bytes | accepted | 158,806 | | classic bounded loop | 40 bytes | rejected | over 1,000,000 | | bpf_loop() | 256 bytes | accepted | 149 | | bpf_for iterator | 256 bytes | accepted | 351 | !Log-scale bar chart of verifier instructions processed: classic loop 32 bytes 158,806 accepted; classic loop 40 and 256 bytes over the 1,000,000 budget; bpf_loop 256 bytes 149; bpf_for 256 bytes 351 Eight times the buffer of the largest classic loop that verifies, for 0.1–0.2% of the verification work. Loading isn't the same as being right, so I also checked they compute the correct answer. Uprobe programs can't be test-run directly, so the identical parse is wrapped in a BPF_PROG_TYPE_SYSCALL program and run on real requests with BPF_PROG_TEST_RUN: run_bpf_loop one Host header len= 50 matches=1 want=1 ok run_bpf_loop no Host header len= 51 matches=0 want=0 ok run_bpf_loop two Host headers len= 42 matches=2 want=2 ok run_bpf_loop Host past byte 200 len=224 matches=1 want=1 ok run_bpf_for one Host header len= 50 matches=1 want=1 ok run_bpf_for no Host header len= 51 matches=0 want=0 ok run_bpf_for two Host headers len= 42 matches=2 want=2 ok run_bpf_for Host past byte 200 len=224 matches=1 want=1 ok That last case — a Host header past byte 200 — is one the classic loop couldn't even be verified over. So why does the agent still parse in userspace? The verifier is no longer the deciding reason on a modern kernel. These are: The kernel floor. The agent ships as one CO-RE binary, verified by checksum on kernels 5.15 and 6.8. bpf_loop() needs 5.17 and iterators need 6.4. Ubuntu 22.04 runs 5.15. Using either would mean dropping supported kernels or maintaining two kernel-side parsers. Where the work runs. A uprobe handler runs synchronously in the traced application's own thread, before SSL_write continues. Copying 256 bytes and returning keeps the cost on the application's request path as small as possible. Parsing in userspace moves that work onto the agent's own threads. What the kernel can see. A header block can be split across several SSL_write calls, and the kernel program sees one call at a time. Userspace sees the whole stream and can correlate requests with responses. What I can test. The userspace parser is ordinary Go with ordinary unit tests. The kernel parser needs root, a specific kernel, and a test harness just to run. The cost of this design is explicit: the captured prefix is 256 bytes, so headers beyond it are truncated — and truncation is reported on every event rather than hidden. If the agent ever drops 5.15, an in-kernel pre-filter with bpf_loop() — say, only capture requests to certain hosts — becomes a reasonable option rather than an impossible one. That's a different conclusion from the one I started with. What the evidence does and doesn't establish | Evidence | Establishes | Does not establish | | --- | --- | --- | | Classic loop: 32 bytes accepted, 40+ rejected | This parser shape exceeds the 1M-instruction budget above 32 bytes, on 6.8 and 6.18 | That every classic-loop parser hits the same wall at the same size | | bpf_loop / bpf_for accepted at 256 bytes | These two loop forms verify cheaply for this parse on 6.18 | Behavior on kernels I haven't tested between 5.17/6.4 and 6.18 | | Test-run results | The parse returns the right count for these inputs | That it handles every valid HTTP/1.1 request | | Verifier statistics | How much work the verifier did for these programs on this kernel | Run-time cost of the programs once attached | What I'd take from this 1. Measure the constraint before designing around it. "The verifier won't allow it" was true for one loop shape on one kind of kernel, and false for another. 2. Watch the verifier's instruction count, not just pass/fail. 158,806 of 1,000,000 at 32 bytes was the warning that 40 bytes would fail. 3. Write bounds for the verifier. Check the register you index with, avoid sums that can wrap, and mask when you can. 4. Re-test old conclusions when the platform moves. I'd written "in-kernel parsing is ruled out" into the project's docs. On a 6.x kernel, that's no longer true. Reproduce it sudo go test ./test/verifier/ -v The classic-loop experiment is in test/verifier/headers.bpf.c, and the write-up with the raw verifier output is in docs/verifier/. The bpf_loop/bpf_for versions, the statistics test and the test-run checks are in test/verifier/extra.bpf.c. {% github sAchin-680/eBPF-observability-agent %} Next in this series: why benchmarking the agent against an idle machine made it look faster than running no agent at all — and the control arm that fixed it. --- I'm Sachin, an SRE / platform engineer working on observability, eBPF and Kubernetes — currently open to new roles. LinkedIn · GitHub