[PATCH bpf v2 4/7] bpf: Reject fall-through across subprogram boundaries

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

check_subprogs() verifies that each subprogram ends in an exit or an
unconditional jump, preventing control flow from falling through into
the next subprogram. However, this check runs before CO-RE relocations
are applied.

When a relocation cannot be resolved, bpf_core_patch_insn() poisons its
target by replacing it with an invalid BPF_CALL. A relocation targeting
the terminal instruction of a non-final subprogram can therefore create
a fall-through edge into the next subprogram after the invariant was
checked.

The per-subprogram DFS in bpf_compute_postorder() then visits the next
subprogram twice and writes past its prog->len-sized postorder array.
Stack liveness analysis relies on the same containment and can access its
per-subprogram arrays out of bounds as well.

Reject fall-through edges whose endpoints belong to different
subprograms in push_insn(). This reestablishes the invariant on the final
instruction stream at the common CFG edge insertion point. Cross-subprog
pseudo-call edges remain valid because they are represented as branch
edges.

Fixes: efcda22aa541 ("bpf: compute instructions postorder per subprogram")
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/cfg.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 842c7d1eabcc..e3c904328ede 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -102,6 +102,7 @@ enum {
  */
 static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
 {
+	struct bpf_subprog_info *subprog;
 	int *insn_stack = env->cfg.insn_stack;
 	int *insn_state = env->cfg.insn_state;
 
@@ -121,6 +122,26 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
 		return -EINVAL;
 	}
 
+	/*
+	 * check_subprogs() prevents control flow from falling through a
+	 * subprogram boundary, but runs before CO-RE relocations can rewrite an
+	 * instruction. Reestablish the invariant on the final instruction stream
+	 * before constructing the CFG used by later per-subprogram passes.
+	 */
+	if (e == FALLTHROUGH) {
+		subprog = bpf_find_containing_subprog(env, t);
+		if (w < subprog->start || w >= (subprog + 1)->start) {
+			verbose_linfo(env, t, "%d: ", t);
+			verbose(env, "fall-through out of subprog from insn %d to %d\n", t, w);
+			bpf_diag_program_structure(
+				env, t, "fall-through leaves subprogram",
+				"Keep fall-through control flow inside the current subprogram.",
+				"Instruction %d falls through to instruction %d outside its subprogram.",
+				t, w);
+			return -EINVAL;
+		}
+	}
+
 	if (e == BRANCH) {
 		/* mark branch target for state pruning */
 		mark_prune_point(env, w);
-- 
2.53.0