bpf: Bound the number of indirect jump edges in a program

Every gotox instruction gets its own copy of the jump table of the subprog
containing it, and each distinct target in that table is a CFG successor
of the instruction. The number of such edges is therefore the number of
gotox instructions times the number of distinct targets, and neither
factor is bounded by anything except the instruction limit.

What is expensive is a BPF prog whose gotox instructions are themselves
the targets, which makes the edge count quadratic. 1024 such gotox are
already ~1e6 edges and about 4s of CPU to load.

Bound the total across the program at BPF_COMPLEXITY_LIMIT_INSNS, aka
the limit on the number of instructions the verifier processes. Progs
with real switch statements are orders of magnitude below this.

This bounds the edges only. Building the jump table of a gotox costs the
number of entries of all insn array maps regardless of how many distinct
targets they hold, which a later patch addresses separately.

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: STAR Labs SG <info@starlabs.sg>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
Link: https://patch.msgid.link/20260925175244.1136329-3-daniel@iogearbox.net

1 files changed, 1 insertions, 0 deletions

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 646e447cebd8..67363c25526d 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1004,6 +1004,7 @@ struct bpf_verifier_env {
 		int cur_stack;
 		/* current position in the insn_postorder vector */
 		int cur_postorder;
+		u32 gotox_edges;
 	} cfg;
 	struct backtrack_state bt;
 	struct bpf_jmp_history_entry *cur_hist_ent;