Re: [PATCH bpf-next 2/3] bpf: check bpf_func_state->callback_depth when pruning states

[Yonghong Song <yonghong.song@linux.dev>]

On 2/12/24 6:38 AM, Eduard Zingerman wrote:
> When comparing current and cached states verifier should consider
> bpf_func_state->callback_depth. Current state cannot be pruned against
> cached state, when current states has more iterations left compared to
> cached state. Current state has more iterations left when it's
> callback_depth is smaller.
>
> Below is an example illustrating this bug, minimized from mailing list
> discussion [0].
> The example is not a safe program: if loop_cb point (1) is followed by
> loop_cb point (2), then division by zero is possible at point (4).
>
>      struct ctx {
>      	__u64 a;
>      	__u64 b;
>      	__u64 c;
>      };
>
>      static void loop_cb(int i, struct ctx *ctx)
>      {
>      	/* assume that generated code is "fallthrough-first":
>      	 * if ... == 1 goto
>      	 * if ... == 2 goto
>      	 * <default>
>      	 */
>      	switch (bpf_get_prandom_u32()) {
>      	case 1:  /* 1 */ ctx->a = 42; return 0; break;
>      	case 2:  /* 2 */ ctx->b = 42; return 0; break;
>      	default: /* 3 */ ctx->c = 42; return 0; break;
>      	}
>      }
>
>      SEC("tc")
>      __failure
>      __flag(BPF_F_TEST_STATE_FREQ)
>      int test(struct __sk_buff *skb)
>      {
>      	struct ctx ctx = { 7, 7, 7 };
>
>      	bpf_loop(2, loop_cb, &ctx, 0);              /* 0 */
>      	/* assume generated checks are in-order: .a first */
>      	if (ctx.a == 42 && ctx.b == 42 && ctx.c == 7)
>      		asm volatile("r0 /= 0;":::"r0");    /* 4 */
>      	return 0;
>      }
>
The change LGTM. But the below description seems not very clear to me.

> Prior to this commit verifier built the following checkpoint tree for
> this example (notation: `(code point #) {<ctx->a>,<ctx->b>,<ctx->c>}`):
>
> - (0) {7P,7,7}

Why we have '7P' here?

>    - (3) {7P,7,7}

So here when (3) is hit, we have callback_depth  = 1, right?

>      - (0) {7P,7,42} (checkpoint #1):

So for below (3)/(2)/(1) we have callback_depth = 2, right?

>        - (3) {7P,7,42}
>          - (0) {7P,7,42}   -> to end
>        - (2) {7P,7,42}
>          - (0) {7P,42,42}  -> to end
>        - (1) {7P,7,42} (checkpoint #2)
>          - (0) {42P,7P,42} -> to end
>    - (2) {7P,7,7}

So now we back to callback_depth = 1.

>      - (0) {7P,42,7} safe (checkpoint #1)
>    - (1) {7,7,7} safe (checkpoint #2)
>
> Here checkpoint #2 has callback_depth of 1, meaning that it would
> never reach state {42,42,7}.

It would be good to specify which 'checkpoint #2' has callback_depth of 1.

> While the last branch of the tree has callback_depth of 0, and thus
> could yet explore the state {42,42,7} if not pruned prematurely.

which 'last branch'?

> This commit makes disallows such premature pruning.

It would be good if the commit message mentions what will change
for the above digram if this commit is applied, so people can understand
why this commit helps.

>
> [0] https://lore.kernel.org/bpf/9b251840-7cb8-4d17-bd23-1fc8071d8eef@linux.dev/
>
> Suggested-by: Yonghong Song <yonghong.song@linux.dev>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>   kernel/bpf/verifier.c | 3 +++
>   1 file changed, 3 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ddaf09db1175..df99fcdbaa05 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -16715,6 +16715,9 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
>   {
>   	int i;
>   
> +	if (old->callback_depth > cur->callback_depth)
> +		return false;
> +
>   	for (i = 0; i < MAX_BPF_REG; i++)
>   		if (!regsafe(env, &old->regs[i], &cur->regs[i],
>   			     &env->idmap_scratch, exact))