This article is part of a series of notes that Mahé Tardy and I wrote to prepare a presentation introducing the BPF verifier state pruning for Linux Plumbers 2025 in Tokyo. You can also find the slides and the video recording of the presentation.
State pruning is what helps the BPF verifier in Linux scale to larger programs. It mitigates the path explosion problem by pruning paths that are equivalent to already-verified paths. State pruning evolved alongside the verifier for the past decade. As we illustrated in our talk, it started as a simple …
This article is part of a series of notes that Mahé Tardy and I wrote to prepare a presentation introducing the BPF verifier state pruning for Linux Plumbers 2025 in Tokyo. You can also find the slides and the video recording of the presentation.
State pruning is what helps the BPF verifier in Linux scale to larger programs. It mitigates the path explosion problem by pruning paths that are equivalent to already-verified paths. State pruning evolved alongside the verifier for the past decade. As we illustrated in our talk, it started as a simple optimization and grew into a more complex and efficient component of the verifier.
This timeline tracks the main changes state pruning went through. Each commit is prefixed with a symbol to indicate the overall impact the change had on the complexity (the “cost” of verification). For example, ↓ means the commit decreased complexity and therefore helped the verifier scale. Commits suffixed with a * have been backported to at least one LTS kernel.
As we publish more articles with Mahé, I’ll include more link to Read more on important changes.
v3.18, 2014
v4.7, 2016
- 070161 Add a pruning point after call instructions, in addition to existing pruning points on conditional jump target and after
BPF_JA. Read more
v4.11, 2017
- f0318d Track offseted map value pointers while on the stack.
v4.12, 2017
v4.14, 2017
- dc503a Track register liveness.
v4.16, 2017
- 2f18f6 Fix liveness propagation in case of register with a pointer filled from the stack.
- 3bf159 Detect dead
BPF_JNEbranches. - f4d7e4 Verification of subprogs (BPF-to-BPF function calls).
- cc2b14 Recognize zero-initialized stack slots.
v4.20, 2018
- 4f7b3e* Extend dead-branch detection to all types of numeric conditions.
v5.0, 2018
- e434b8* Track scalars through 32-bit assignments.
- 19e2db Don’t assume a larger stack means verifier states aren’t equivalent.
v5.2, 2019
- 9f4686 Least-recently used mechanism to limit number of saved states at pruning points.
v5.3, 2019
- f7cf25* Track constant scalar registers as they are spilled to the stack.
- 258972 Support bounded loops, introduce heuristic to decide when to save the verifier state on a pruning point.
- b5dc01 Introduce precise tracking of scalar values.
- a3ce68 Fix precision propagation in case of pruned paths.
- 675417 Fix precise tracking in case of subprogs.
v5.5, 2019
- cc52d9 Require precise tracking of map lookup key for tail calls.
v5.6, 2020
- 51c39b Support function-by-function verification.
v5.10, 2020
- 757488 Allocate an ID for scalars to propagate infered ranges to identical scalars.
- 5689d4 Track 64-bit bounded scalar registers as they are spilled to the stack.
v5.15, 2021
v5.16, 2021
- 354e8f* Track all bounded scalar registers as they are spilled to the stack.
v6.2, 2022
- a3b666* Fix precision propagation in case of ALU operations.
- be2ef8* Do not completely disable precise tracking whenever subprogs are used.
- f63181* Improve accuracy of precision propagation.
- bffdea* Decouple jump history from pruning points.
- 7a830b* Improve accuracy of precision propagation by actively forgetting precise marks.
v6.3, 2022–2023
- 4633a0 Fix register comparison in state pruning to take into account ID remapping between paths.
- 6715df* Relax slack slot equivalence when running with
CAP_PERFMON.
v6.4, 2023
- 4b5ce5 Introduce force pruning points for
iter_nextkfuncs. - 13fbce Improve
BPF_JEQandBPF_JNEdead-branch detection.
v6.5, 2023
- 407958 Introduce
struct backtrack_stateto track the precise marking through backtracking. - fde2a3 Support precise tracking for subprogs, including callback functions.
- 904e6d Share precise mark between all scalars with the same ID.
v6.7, 2023
- 2793a8* For
iter_nextloops, require exact state match in state pruning and introduce widening of registers. - 42d31d Improve
BPF_JEQandBPF_JNEdead-branch detection by using signed ranges. - ab5cfa* Add a pruning point on calls to synchronous callback functions, fix callback function verification to verify all iterations. Read more
- cafe2c* Extend use of register widening to synchronous callback functions.
v6.8, 2023
- 0acd03* Require precise tracking of R0 on callback function return.
- eabe51 Require precise tracking of R0 when checking return code is within expected range.
- 41f6f6 Precise tracking on spill to the stack even if using non-R10 register.
- 18a433 Don’t trigger precise tracking whenever writing zero register to aligned stack slots.
v6.9, 2024
- 9a4c57 Don’t trigger precise tracking whenever writing zero immediate to aligned stack slots, a pattern common for
mcpu=v4. - 6efbde Improve state pruning when comparing unbounded spilled register to misc. stack slots.
v6.12, 2024
- 4bf79f Improving precise tracking at conditional jumps in case of linked registers.
v6.15, 2025
- 14c855 Data-flow analysis for register liveness, before the actual program analysis.
v6.17, 2025
- 96c6aa Compute Strongly Connected Components (SCCs) of control-flow graph.
- c9e319 Use SCC to improve read and precise marks propagation in case of loops.
v6.18, 2025