bpf: fix control-flow graph checking in privileged mode
Subsystems (4)
Andrii Nakryiko
maintainerPATCH 1/2 bpf: fix control-flow graph checking in privileged mode
When BPF program is verified in privileged mode, BPF verifier allows bounded loops. This means that from CFG point of view there are definitely some back-edges. Original commit adjusted check_cfg() logic to not detect back-edges in control flow graph if they are resulting from conditional jumps, which the idea that subsequent full BPF verification process will determine whether such loops are bounded or not, and either accept or reject the BPF program. At least that's my reading of the intent.
Unfortunately, the implementation of this idea doesn't work correctly in all possible situations. Conditional jump might not result in immediate back-edge, but just a few unconditional instructions later we can arrive at back-edge. In such situations check_cfg() would reject BPF program even in privileged mode, despite it might be bounded loop. Next patch adds one simple program demonstrating such scenario.
To keep things simple, instead of trying to detect back edges in privileged mode, just assume every back edge is valid and let subsequent BPF verification prove or reject bounded loops.
Note a few test changes. For unknown reason, we have a few tests that are specified to detect a back-edge in a privileged mode, but looking at their code it seems like the right outcome is passing check_cfg() and letting subsequent verification to make a decision about bounded or not bounded looping.
Bounded recursion case is also interesting. The example should pass, as recursion is limited to just a few levels and so we never reach maximum number of nested frames and never exhaust maximum stack depth. But the way that max stack depth logic works today it falsely detects this as exceeding max nested frame count. This patch series doesn't attempt to fix this orthogonal problem, so we just adjust expected verifier failure.
--- kernel/bpf/verifier.c | 23 +++++++------------ .../selftests/bpf/progs/verifier_loops1.c | 9 +++++--- tools/testing/selftests/bpf/verifier/calls.c | 6 ++--- 3 files changed, 17 insertions(+), 21 deletions(-)
kernel/bpf/verifier.c +8 -15
@@ -15403,8 +15403,7 @@ enum {* w - next instruction * e - edge */ -static int push_insn (int t,int w,int e,struct bpf_verifier_env *env, -bool loop_ok) +static int push_insn (int t,int w,int e,struct bpf_verifier_env *env) {int *insn_stack = env->cfg.insn_stack;int *insn_state = env->cfg.insn_state;
@@ -15436,7 +15435,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, insn_stack[env->cfg.cur_stack++] = w;return KEEP_EXPLORING ; }else if ((insn_state[w] &0xF0 ) ==DISCOVERED ) { -if (loop_ok && env->bpf_capable) +if (env->bpf_capable)return DONE_EXPLORING ;verbose_linfo (env, t,"%d: " , t);verbose_linfo (env, w,"%d: " , w);
@@ -15459,7 +15458,7 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,int ret, insn_sz; insn_sz =bpf_is_ldimm64 (&insns[t]) ?2 :1 ; - ret =push_insn (t, t + insn_sz,FALLTHROUGH , env, false); + ret =push_insn (t, t + insn_sz,FALLTHROUGH , env);if (ret)return ret;
@@ -15469,12 +15468,7 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,if (visit_callee) {mark_prune_point (env, t); - ret =push_insn (t, t + insns[t].imm +1 ,BRANCH , env, -/* It's ok to allow recursion from CFG point of -* view. __check_func_call() will do the actual -* check. -*/ -bpf_pseudo_func (insns + t)); + ret =push_insn (t, t + insns[t].imm +1 ,BRANCH , env); }return ret; }
@@ -15496,7 +15490,7 @@ static int visit_insn(int t, struct bpf_verifier_env *env)if (BPF_CLASS (insn->code) !=BPF_JMP &&BPF_CLASS (insn->code) !=BPF_JMP32 ) { insn_sz =bpf_is_ldimm64 (insn) ?2 :1 ; -return push_insn (t, t + insn_sz,FALLTHROUGH , env, false); +return push_insn (t, t + insn_sz,FALLTHROUGH , env); }switch (BPF_OP (insn->code)) {
@@ -15543,8 +15537,7 @@ static int visit_insn(int t, struct bpf_verifier_env *env) off = insn->imm;/* unconditional jump with single edge */ - ret =push_insn (t, t + off +1 ,FALLTHROUGH , env, - true); + ret =push_insn (t, t + off +1 ,FALLTHROUGH , env);if (ret)return ret;
@@ -15557,11 +15550,11 @@ static int visit_insn(int t, struct bpf_verifier_env *env)/* conditional jump with two edges */ mark_prune_point (env, t); - ret =push_insn (t, t +1 ,FALLTHROUGH , env, true); + ret =push_insn (t, t +1 ,FALLTHROUGH , env);if (ret)return ret; -return push_insn (t, t + insn->off +1 ,BRANCH , env, true); +return push_insn (t, t + insn->off +1 ,BRANCH , env); } }
tools/testing/selftests/bpf/progs/verifier_loops1.c +6 -3
@@ -75,9 +75,10 @@ l0_%=: r0 += 1; \ " ::: __clobber_all); } -SEC("tracepoint") +SEC("socket") __description("bounded loop, start in the middle") -__failure __msg("back-edge") +__success +__failure_unpriv __msg_unpriv("back-edge")__naked void loop_start_in_the_middle (void ) { asm volatile (" \
@@ -136,7 +137,9 @@ l0_%=: exit; \ SEC("tracepoint") __description("bounded recursion") -__failure __msg("back-edge") +__failure +/* verifier limitation in detecting max stack depth */ +__msg("the call stack of 8 frames is too deep !")__naked void bounded_recursion (void ) { asm volatile (" \
tools/testing/selftests/bpf/verifier/calls.c +3 -3
@@ -442,7 +442,7 @@ BPF_EXIT_INSN(), }, .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "back-edge from insn 0 to 0", + .errstr = "the call stack of 9 frames is too deep", .result = REJECT, }, {
@@ -799,7 +799,7 @@ BPF_EXIT_INSN(), }, .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "back-edge", + .errstr = "the call stack of 9 frames is too deep", .result = REJECT, }, {
@@ -811,7 +811,7 @@ BPF_EXIT_INSN(), }, .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "back-edge", + .errstr = "the call stack of 9 frames is too deep", .result = REJECT, }, {
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH 2/2 selftests/bpf: add more test cases for check_cfg()
Add a few more simple cases to validate proper privileged vs unprivileged loop detection behavior. conditional_loop2 is the one reported by Hao Sun that triggered this set of fixes.
--- .../selftests/bpf/progs/verifier_cfg.c | 62 +++++++++++++++++++ 1 file changed, 62 insertions(+)
tools/testing/selftests/bpf/progs/verifier_cfg.c +62 -0
@@ -97,4 +97,66 @@ l0_%=: r2 = r0; \ " ::: __clobber_all); } +SEC("socket") +__description("conditional loop (2)") +__success +__failure_unpriv __msg_unpriv("back-edge from insn 10 to 11") +__naked void conditional_loop2 (void ) +{ + asmvolatile (" \ +r9 = 2 ll; \ +r3 = 0x20 ll; \ +r4 = 0x35 ll; \ +r8 = r4; \ +goto l1_%=; \ +l0_%=: r9 -= r3; \ +r9 -= r4; \ +r9 -= r8; \ +l1_%=: r8 += r4; \ +if r8 < 0x64 goto l0_%=; \ +r0 = r9; \ +exit; \ +" ::: __clobber_all); +} + +SEC("socket") +__description("unconditional loop after conditional jump") +__failure __msg("infinite loop detected") +__failure_unpriv __msg_unpriv("back-edge from insn 3 to 2") +__naked void uncond_loop_after_cond_jmp(void) +{ + asmvolatile (" \ +r0 = 0; \ +if r0 > 0 goto l1_%=; \ +l0_%=: r0 = 1; \ +goto l0_%=; \ +l1_%=: exit; \ +" ::: __clobber_all); +} + + +__naked __noinline __used +static unsigned long never_ending_subprog() +{ + asmvolatile (" \ +r0 = r1; \ +goto -1; \ +" ::: __clobber_all); +} + +SEC("socket") +__description("unconditional loop after conditional jump") +/* infinite loop is detected *after* check_cfg() */ +__failure __msg("infinite loop detected") +__naked void uncond_loop_in_subprog_after_cond_jmp(void) +{ + asmvolatile (" \ +r0 = 0; \ +if r0 > 0 goto l1_%=; \ +l0_%=: r0 += 1; \ +call never_ending_subprog; \ +l1_%=: exit; \ +" ::: __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.34.1
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:
Quoted 10 lines · On Thu, 9 Nov 2023 22:14:10 -0800 you wrote:
When BPF program is verified in privileged mode, BPF verifier allows bounded loops. This means that from CFG point of view there are definitely some back-edges. Original commit adjusted
check_cfg()logic to not detect back-edges in control flow graph if they are resulting from conditional jumps, which the idea that subsequent full BPF verification process will determine whether such loops are bounded or not, and either accept or reject the BPF program. At least that's my reading of the intent.[...]
Here is the summary with links:
- [bpf,1/2] bpf: fix control-flow graph checking in privileged mode
https://git.kernel.org/bpf/bpf/c/10e14e9652bf - [bpf,2/2] selftests/bpf: add more test cases for check_cfg() https://git.kernel.org/bpf/bpf/c/e2e57d637aa5
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html