[PATCH bpf 4/6] bpf: Reject indirect jumps that leave their subprogram

[Daniel Borkmann <daniel@iogearbox.net>]

The jump table of a subprog is collected in compute_subprog_jts() from the
insn_array maps of the program, and a map is attributed to the subprog that
contains its first entry. check_indirect_jump() instead resolves the targets
from the map the gotox register actually points to, bounded only by the
index range of that register, and never relates them back to the subprog
of the gotox.

The two disagree, so bpf_insn_successors() reports a subset of the edges the
BPF program can take and a gotox can enter a subprog the CFG never walked.
The x86 epilogue there pops the callee saved registers of its own subprog and
leaves the ones pushed by the current prologue unrestored, handing rbx, r13,
r14 and r15 to the kernel with the values the BPF program left in them.

Close both ends in check_indirect_jump(): confine the resolved targets to the
subprog of the gotox, and require each of them to be present in the jump table
the CFG walked, that is, in the successor set bpf_insn_successors() reported
for this instruction. The latter is the invariant that actually has to hold,
the former is kept because it names the problem the BPF program has.

Fixes: 493d9e0d6083 ("bpf, x86: add support for indirect jumps")
Reported-by: James Burton <jamesburton@meta.com>
Reported-by: Nuoqi Gui <gnq25@mails.tsinghua.edu.cn>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 include/linux/bpf_verifier.h                  |  1 +
 kernel/bpf/cfg.c                              | 35 +++++-----
 kernel/bpf/verifier.c                         | 65 +++++++++++++++++++
 .../selftests/bpf/progs/verifier_gotox.c      |  2 +-
 4 files changed, 85 insertions(+), 18 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 301a47d2b272..baf2e17d7019 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -826,6 +826,7 @@ struct bpf_subprog_info {
 	bool keep_fastcall_stack: 1;
 	bool changes_pkt_data: 1;
 	bool might_sleep: 1;
+	bool jt_spans_subprogs: 1;
 	u8 arg_cnt:4;
 
 	enum priv_stack_mode priv_stack_mode;
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 8aee94689229..879587af8d08 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -315,6 +315,11 @@ static int compute_subprog_jts(struct bpf_verifier_env *env)
 			kvfree(jt_cur);
 			continue;
 		}
+		if (jt_cur->items[jt_cur->cnt - 1] >= (subprog + 1)->start) {
+			subprog->jt_spans_subprogs = true;
+			kvfree(jt_cur);
+			continue;
+		}
 
 		old_cnt = subprog->jt ? subprog->jt->cnt : 0;
 		jt = bpf_iarray_realloc(subprog->jt, old_cnt + jt_cur->cnt);
@@ -346,6 +351,7 @@ static void free_subprog_jts(struct bpf_verifier_env *env)
 	for (i = 0; i < ARRAY_SIZE(env->subprog_info); i++) {
 		kvfree(env->subprog_info[i].jt);
 		env->subprog_info[i].jt = NULL;
+		env->subprog_info[i].jt_spans_subprogs = false;
 	}
 	env->cfg.subprog_jts_ready = false;
 }
@@ -354,9 +360,8 @@ static struct bpf_iarray *
 create_jt(int t, struct bpf_verifier_env *env)
 {
 	struct bpf_subprog_info *subprog;
-	int subprog_start, subprog_end;
 	struct bpf_iarray *jt;
-	int i, err;
+	int subprog_start, err;
 
 	if (!env->cfg.subprog_jts_ready) {
 		err = compute_subprog_jts(env);
@@ -366,7 +371,17 @@ create_jt(int t, struct bpf_verifier_env *env)
 
 	subprog = bpf_find_containing_subprog(env, t);
 	subprog_start = subprog->start;
-	subprog_end = (subprog + 1)->start;
+
+	if (subprog->jt_spans_subprogs) {
+		verbose(env, "jump table of subprog starting at %u spans multiple subprogs\n",
+			subprog_start);
+		bpf_diag_program_structure(
+			env, subprog_start, "jump table spans subprograms",
+			"Keep every entry of a jump table inside one subprogram.",
+			"A jump table found for the subprogram that starts at instruction %u reaches past its end at instruction %u.",
+			subprog_start, (subprog + 1)->start);
+		return ERR_PTR(-EINVAL);
+	}
 
 	if (!subprog->jt) {
 		verbose(env, "no jump tables found for subprog starting at %u\n", subprog_start);
@@ -383,20 +398,6 @@ create_jt(int t, struct bpf_verifier_env *env)
 		return ERR_PTR(-ENOMEM);
 	memcpy(jt->items, subprog->jt->items, subprog->jt->cnt << 2);
 
-	for (i = 0; i < jt->cnt; i++) {
-		if (jt->items[i] < subprog_start || jt->items[i] >= subprog_end) {
-			verbose(env, "jump table for insn %d points outside of the subprog [%u,%u]\n",
-					t, subprog_start, subprog_end);
-			bpf_diag_program_structure(
-				env, t, "jump table target out of range",
-				"Keep every jump-table target inside the same subprogram.",
-				"The jump table for instruction %d points outside subprogram range [%u,%u).",
-				t, subprog_start, subprog_end);
-			kvfree(jt);
-			return ERR_PTR(-EINVAL);
-		}
-	}
-
 	return jt;
 }
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 72a3f5998dd2..45234e2fbee6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18165,11 +18165,56 @@ static int indirect_jump_min_max_index(struct bpf_verifier_env *env,
 	return 0;
 }
 
+/* 'jt' is sorted and free of duplicates, see sort_insn_array_uniq() */
+static bool jt_contains(const struct bpf_iarray *jt, u32 target)
+{
+	int l = 0, r = jt->cnt - 1, m;
+
+	while (l <= r) {
+		m = l + (r - l) / 2;
+		if (jt->items[m] == target)
+			return true;
+		if (jt->items[m] < target)
+			l = m + 1;
+		else
+			r = m - 1;
+	}
+	return false;
+}
+
+static int reject_gotox_out_of_subprog(struct bpf_verifier_env *env, u32 target,
+				       u32 subprog_start, u32 subprog_end)
+{
+	verbose(env, "indirect jump from insn %d to %u leaves the subprog [%u,%u)\n",
+		     env->insn_idx, target, subprog_start, subprog_end);
+	bpf_diag_program_structure(
+		env, env->insn_idx, "indirect jump leaves subprogram",
+		"Keep every reachable jump-table target inside the subprogram of the indirect jump.",
+		"Instruction %d can jump indirectly to instruction %u, which is outside its own subprogram [%u,%u).",
+		env->insn_idx, target, subprog_start, subprog_end);
+	return -EINVAL;
+}
+
+static int reject_gotox_without_cfg_edge(struct bpf_verifier_env *env, u32 target)
+{
+	verbose(env, "indirect jump from insn %d to %u is not in the jump table of the subprog\n",
+		     env->insn_idx, target);
+	bpf_diag_program_structure(
+		env, env->insn_idx, "indirect jump target without CFG edge",
+		"Resolve indirect jumps through a jump table whose entries all fall inside the subprogram of the jump.",
+		"Instruction %d can jump indirectly to instruction %u, which is not part of the jump table of its subprogram.",
+		env->insn_idx, target);
+	return -EINVAL;
+}
+
 /* gotox *dst_reg */
 static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *insn)
 {
 	struct bpf_verifier_state *other_branch;
+	struct bpf_subprog_info *subprog;
+	u32 subprog_start, subprog_end;
 	struct bpf_reg_state *dst_reg;
+	struct bpf_iarray *jt;
 	struct bpf_map *map;
 	u32 min_index, max_index;
 	int err = 0;
@@ -18212,6 +18257,26 @@ static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *in
 		return -EINVAL;
 	}
 
+	subprog = bpf_find_containing_subprog(env, env->insn_idx);
+	if (verifier_bug_if(!subprog, env, "no subprog contains insn %d", env->insn_idx))
+		return -EFAULT;
+	subprog_start = subprog->start;
+	subprog_end = (subprog + 1)->start;
+
+	jt = env->insn_aux_data[env->insn_idx].jt;
+	if (verifier_bug_if(!jt, env, "no jump table for insn %d", env->insn_idx))
+		return -EFAULT;
+
+	for (i = 0; i < n; i++) {
+		u32 target = env->gotox_tmp_buf->items[i];
+
+		if (target < subprog_start || target >= subprog_end)
+			return reject_gotox_out_of_subprog(env, target, subprog_start,
+							   subprog_end);
+		if (!jt_contains(jt, target))
+			return reject_gotox_without_cfg_edge(env, target);
+	}
+
 	for (i = 0; i < n - 1; i++) {
 		mark_indirect_target(env, env->gotox_tmp_buf->items[i]);
 		other_branch = push_stack(env, env->gotox_tmp_buf->items[i],
diff --git a/tools/testing/selftests/bpf/progs/verifier_gotox.c b/tools/testing/selftests/bpf/progs/verifier_gotox.c
index 5b18c9a27717..3567b29e2378 100644
--- a/tools/testing/selftests/bpf/progs/verifier_gotox.c
+++ b/tools/testing/selftests/bpf/progs/verifier_gotox.c
@@ -318,7 +318,7 @@ __used static int test_subprog(void)
 }
 
 SEC("socket")
-__failure __msg("jump table for insn 4 points outside of the subprog [0,10]")
+__failure __msg("jump table of subprog starting at 0 spans multiple subprogs")
 __naked void jump_table_outside_subprog(void)
 {
 	asm volatile ("						\
-- 
2.43.0