[bpf-next,v2,3/3] selftests/bpf: test case for callback_depth states pruning logic

Commit Message

Eduard Zingerman Feb. 16, 2024, 3:03 p.m. UTC

The test case was minimized from mailing list discussion [0].
It is equivalent to the following C program:

    struct iter_limit_bug_ctx { __u64 a; __u64 b; __u64 c; };

    static __naked void iter_limit_bug_cb(void)
    {
    	switch (bpf_get_prandom_u32()) {
    	case 1:  ctx->a = 42; break;
    	case 2:  ctx->b = 42; break;
    	default: ctx->c = 42; break;
    	}
    }

    int iter_limit_bug(struct __sk_buff *skb)
    {
    	struct iter_limit_bug_ctx ctx = { 7, 7, 7 };

    	bpf_loop(2, iter_limit_bug_cb, &ctx, 0);
    	if (ctx.a == 42 && ctx.b == 42 && ctx.c == 7)
    	  asm volatile("r1 /= 0;":::"r1");
    	return 0;
    }

The main idea is that each loop iteration changes one of the state
variables in a non-deterministic manner. Hence it is premature to
prune the states that have two iterations left comparing them to
states with one iteration left.
E.g. {{7,7,7}, callback_depth=0} can reach state {42,42,7},
while {{7,7,7}, callback_depth=1} can't.

[0] https://lore.kernel.org/bpf/[e-mail]/

Signed-off-by: Eduard Zingerman <[e-mail]>
---
 .../bpf/progs/verifier_iterating_callbacks.c  | 70 +++++++++++++++++++
 1 file changed, 70 insertions(+)

Comments

Yonghong Song Feb. 20, 2024, 12:32 a.m. UTC | #1

On 2/16/24 7:03 AM, Eduard Zingerman wrote:
> The test case was minimized from mailing list discussion [0].
> It is equivalent to the following C program:
>
>      struct iter_limit_bug_ctx { __u64 a; __u64 b; __u64 c; };
>
>      static __naked void iter_limit_bug_cb(void)
>      {
>      	switch (bpf_get_prandom_u32()) {
>      	case 1:  ctx->a = 42; break;
>      	case 2:  ctx->b = 42; break;
>      	default: ctx->c = 42; break;
>      	}
>      }
>
>      int iter_limit_bug(struct __sk_buff *skb)
>      {
>      	struct iter_limit_bug_ctx ctx = { 7, 7, 7 };
>
>      	bpf_loop(2, iter_limit_bug_cb, &ctx, 0);
>      	if (ctx.a == 42 && ctx.b == 42 && ctx.c == 7)
>      	  asm volatile("r1 /= 0;":::"r1");
>      	return 0;
>      }
>
> The main idea is that each loop iteration changes one of the state
> variables in a non-deterministic manner. Hence it is premature to
> prune the states that have two iterations left comparing them to
> states with one iteration left.
> E.g. {{7,7,7}, callback_depth=0} can reach state {42,42,7},
> while {{7,7,7}, callback_depth=1} can't.
>
> [0] https://lore.kernel.org/bpf/[e-mail]/
>
> Signed-off-by: Eduard Zingerman <[e-mail]>

Acked-by: Yonghong Song <[e-mail]>

Patch

diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index 5905e036e0ea..a955a6358206 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -239,4 +239,74 @@  int bpf_loop_iter_limit_nested(void *unused)
 	return 1000 * a + b + c;
 }
 
+struct iter_limit_bug_ctx {
+	__u64 a;
+	__u64 b;
+	__u64 c;
+};
+
+static __naked void iter_limit_bug_cb(void)
+{
+	/* This is the same as C code below, but written
+	 * in assembly to control which branches are fall-through.
+	 *
+	 *   switch (bpf_get_prandom_u32()) {
+	 *   case 1:  ctx->a = 42; break;
+	 *   case 2:  ctx->b = 42; break;
+	 *   default: ctx->c = 42; break;
+	 *   }
+	 */
+	asm volatile (
+	"r9 = r2;"
+	"call %[bpf_get_prandom_u32];"
+	"r1 = r0;"
+	"r2 = 42;"
+	"r0 = 0;"
+	"if r1 == 0x1 goto 1f;"
+	"if r1 == 0x2 goto 2f;"
+	"*(u64 *)(r9 + 16) = r2;"
+	"exit;"
+	"1: *(u64 *)(r9 + 0) = r2;"
+	"exit;"
+	"2: *(u64 *)(r9 + 8) = r2;"
+	"exit;"
+	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all
+	);
+}
+
+SEC("tc")
+__failure
+__flag(BPF_F_TEST_STATE_FREQ)
+int iter_limit_bug(struct __sk_buff *skb)
+{
+	struct iter_limit_bug_ctx ctx = { 7, 7, 7 };
+
+	bpf_loop(2, iter_limit_bug_cb, &ctx, 0);
+
+	/* This is the same as C code below,
+	 * written in assembly to guarantee checks order.
+	 *
+	 *   if (ctx.a == 42 && ctx.b == 42 && ctx.c == 7)
+	 *     asm volatile("r1 /= 0;":::"r1");
+	 */
+	asm volatile (
+	"r1 = *(u64 *)%[ctx_a];"
+	"if r1 != 42 goto 1f;"
+	"r1 = *(u64 *)%[ctx_b];"
+	"if r1 != 42 goto 1f;"
+	"r1 = *(u64 *)%[ctx_c];"
+	"if r1 != 7 goto 1f;"
+	"r1 /= 0;"
+	"1:"
+	:
+	: [ctx_a]"m"(ctx.a),
+	  [ctx_b]"m"(ctx.b),
+	  [ctx_c]"m"(ctx.c)
+	: "r1"
+	);
+	return 0;
+}
+
 char _license[] SEC("license") = "GPL";