Re: [BUG] verifier escape with iteration helpers (bpf_loop, ...)

[Eduard Zingerman <eddyz87@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2256 bytes --]

On Tue, 2023-10-03 at 22:50 -0700, Alexei Starovoitov wrote:
> On Tue, Oct 3, 2023 at 7:57 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> > 
> > ok. discard that idea.
> 
> Attached is a 3rd version of the same idea I argued earlier.
> Let normal DFS go as normal,
> do states_equal() on V which has 1 looping branch remain
> and all other explored.
> To achieve that when iter_next() is seen do parent->looping_states += 2;
> 
> then when processing any children do parent->looping_states++;
> in the correct parent.
> Since there could be many intermediate states have to walk back
> parentage chain to increment correct parent.
> When the state reaches bpf_exit or safety, walk back
> the parentage chain and do looping_states--.
> The state is ok to use in states_equal() if looping_states==1.

But what if each next iteration spawns more than two looping states?
E.g. for the following example:

  0. // full test attached as a patch
  1. while (next(i)) {
  2.   if (random())
  3.     continue;
  4.   if (random())
  5.     continue;
  6.   if (random())
  7.     continue;
  8.   r0 += 0;
  9. }

For me it bails out with the following message:

    run_subtest:FAIL:unexpected_load_failure unexpected error: -28
    ....
    The sequence of 8193 jumps is too complex.
    processed 49161 insns (limit 1000000) max_states_per_insn 4 total_states 2735 peak_states 2735 mark_read 2

(I bumped insn complexity limit back to 1,000,000).

> With this patch all existing iter tests still pass,
> and all Ed's special tests pass or fail as needed.
> Ex: loop_state_deps1 is rejected with misaligned stack,
> loop1 loads with success, num_iter_bug fails with bad pointer.

Are you sure that correct version of the patch was shared?
I get the following log for loop_state_deps1:

    run_subtest:FAIL:unexpected_load_success unexpected success: 0
    from 21 to 22: safe
    ...
    update_br2 80c0 branches=0/0
    processed 75 insns (limit 1000000) max_states_per_insn 2 total_states 29 peak_states 29 mark_read 9
    =============
    #104/26  iters/loop_state_deps1:FAIL

The test case is marked as safe.
iter_precision_fixed_point{1,2} and num_iter_bug work as expected.

[-- Attachment #2: hydra1.patch --]
[-- Type: text/x-patch, Size: 1646 bytes --]

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 019c8dde5fa2..cf9041fac272 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -16821,7 +16821,7 @@ static int do_check(struct bpf_verifier_env *env)
 		insn = &insns[env->insn_idx];
 		class = BPF_CLASS(insn->code);
 
-		if (++env->insn_processed > 1000) {//BPF_COMPLEXITY_LIMIT_INSNS) {
+		if (++env->insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) {
 			verbose(env,
 				"BPF program is too large. Processed %d insn\n",
 				env->insn_processed);
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 9add71d79a3a..f08288c0b74a 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -991,4 +991,42 @@ int num_iter_bug(const void *ctx) {
      return 0;
 }
 
+SEC("?raw_tp")
+__success
+__naked int hydra1(void)
+{
+	asm volatile (
+		"r1 = r10;"
+		"r1 += -8;"
+		"r2 = 0;"
+		"r3 = 10;"
+		"call %[bpf_iter_num_new];"
+	"loop_%=:"
+		"r1 = r10;"
+		"r1 += -8;"
+		"call %[bpf_iter_num_next];"
+		"if r0 == 0 goto loop_end_%=;"
+		"call %[bpf_get_prandom_u32];"
+		"if r0 != 42 goto loop_%=;"
+		"call %[bpf_get_prandom_u32];"
+		"if r0 != 42 goto loop_%=;"
+		"call %[bpf_get_prandom_u32];"
+		"if r0 != 42 goto loop_%=;"
+		"r0 += 0;"
+		"goto loop_%=;"
+	"loop_end_%=:"
+		"r1 = r10;"
+		"r1 += -8;"
+		"call %[bpf_iter_num_destroy];"
+		"r0 = 0;"
+		"exit;"
+		:
+		: __imm(bpf_get_prandom_u32),
+		  __imm(bpf_iter_num_new),
+		  __imm(bpf_iter_num_next),
+		  __imm(bpf_iter_num_destroy)
+		: __clobber_all
+	);
+}
+
 char _license[] SEC("license") = "GPL";