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

Commit Message

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

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;
    }

Prior to this commit verifier built the following checkpoint tree for
this example:

 .------------------------------------- Checkpoint / State name
 |    .-------------------------------- Code point number
 |    |   .---------------------------- Stack state {ctx.a,ctx.b,ctx.c}
 |    |   |        .------------------- Callback depth in frame #0
 v    v   v        v
   - (0) {7P,7P,7},depth=0
     - (3) {7P,7P,7},depth=1
       - (0) {7P,7P,42},depth=1
         - (3) {7P,7,42},depth=2
           - (0) {7P,7,42},depth=2      loop terminates because of depth limit
             - (4) {7P,7,42},depth=0    predicted false, ctx.a marked precise
             - (6) exit
         - (2) {7P,7,42},depth=2
(a)        - (0) {7P,42,42},depth=2     loop terminates because of depth limit
             - (4) {7P,42,42},depth=0   predicted false, ctx.a marked precise
             - (6) exit
(b)      - (1) {7P,7P,42},depth=2
           - (0) {42P,7P,42},depth=2    loop terminates because of depth limit
             - (4) {42P,7P,42},depth=0  predicted false, ctx.{a,b} marked precise
             - (6) exit
     - (2) {7P,7,7},depth=1
       - (0) {7P,42,7},depth=1          considered safe, pruned using checkpoint (a)
(c)  - (1) {7P,7P,7},depth=1            considered safe, pruned using checkpoint (b)

Here checkpoint (b) has callback_depth of 2, meaning that it would
never reach state {42,42,7}.
While checkpoint (c) has callback_depth of 1, and thus
could yet explore the state {42,42,7} if not pruned prematurely.
This commit makes forbids such premature pruning,
allowing verifier to explore states sub-tree starting at (c):

(c)  - (1) {7,7,7P},depth=1
       - (0) {42P,7,7P},depth=1
         ...
         - (2) {42,7,7},depth=2
           - (0) {42,42,7},depth=2      loop terminates because of depth limit
             - (4) {42,42,7},depth=0    predicted true, ctx.{a,b,c} marked precise
               - (5) division by zero

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

Suggested-by: Yonghong Song <[e-mail]>
Signed-off-by: Eduard Zingerman <[e-mail]>
---
 kernel/bpf/verifier.c | 3 +++
 1 file changed, 3 insertions(+)

Comments

Andrii Nakryiko Feb. 16, 2024, 6:16 p.m. UTC | #1

On Fri, Feb 16, 2024 at 7:03 AM Eduard Zingerman <[e-mail]> 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;
>     }
>
> Prior to this commit verifier built the following checkpoint tree for
> this example:
>
>  .------------------------------------- Checkpoint / State name
>  |    .-------------------------------- Code point number
>  |    |   .---------------------------- Stack state {ctx.a,ctx.b,ctx.c}
>  |    |   |        .------------------- Callback depth in frame #0
>  v    v   v        v
>    - (0) {7P,7P,7},depth=0
>      - (3) {7P,7P,7},depth=1
>        - (0) {7P,7P,42},depth=1
>          - (3) {7P,7,42},depth=2
>            - (0) {7P,7,42},depth=2      loop terminates because of depth limit
>              - (4) {7P,7,42},depth=0    predicted false, ctx.a marked precise
>              - (6) exit
>          - (2) {7P,7,42},depth=2
> (a)        - (0) {7P,42,42},depth=2     loop terminates because of depth limit
>              - (4) {7P,42,42},depth=0   predicted false, ctx.a marked precise
>              - (6) exit
> (b)      - (1) {7P,7P,42},depth=2
>            - (0) {42P,7P,42},depth=2    loop terminates because of depth limit
>              - (4) {42P,7P,42},depth=0  predicted false, ctx.{a,b} marked precise
>              - (6) exit
>      - (2) {7P,7,7},depth=1
>        - (0) {7P,42,7},depth=1          considered safe, pruned using checkpoint (a)
> (c)  - (1) {7P,7P,7},depth=1            considered safe, pruned using checkpoint (b)
>
> Here checkpoint (b) has callback_depth of 2, meaning that it would
> never reach state {42,42,7}.
> While checkpoint (c) has callback_depth of 1, and thus
> could yet explore the state {42,42,7} if not pruned prematurely.
> This commit makes forbids such premature pruning,
> allowing verifier to explore states sub-tree starting at (c):
>
> (c)  - (1) {7,7,7P},depth=1
>        - (0) {42P,7,7P},depth=1
>          ...
>          - (2) {42,7,7},depth=2
>            - (0) {42,42,7},depth=2      loop terminates because of depth limit
>              - (4) {42,42,7},depth=0    predicted true, ctx.{a,b,c} marked precise
>                - (5) division by zero
>
> [0] https://lore.kernel.org/bpf/[e-mail]/
>
> Suggested-by: Yonghong Song <[e-mail]>
> Signed-off-by: Eduard Zingerman <[e-mail]>
> ---
>  kernel/bpf/verifier.c | 3 +++
>  1 file changed, 3 insertions(+)
>

Missing Fixes: tag? Also, shouldn't this go into bpf tree instead of bpf-next?

Otherwise everything looks good.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 011d54a1dc53..c1fa1de590dc 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -16705,6 +16705,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))
> --
> 2.43.0
>

Eduard Zingerman Feb. 17, 2024, 6:19 p.m. UTC | #2

On Fri, 2024-02-16 at 10:16 -0800, Andrii Nakryiko wrote:
[...]

> Missing Fixes: tag?

Right, sorry aboutt that

> Also, shouldn't this go into bpf tree instead of bpf-next?

Will re-send v3 with fixes tag to 'bpf'

Eduard Zingerman Feb. 19, 2024, 12:48 p.m. UTC | #3

On Sat, 2024-02-17 at 20:19 +0200, Eduard Zingerman wrote:
[...]

> > Also, shouldn't this go into bpf tree instead of bpf-next?
> 
> Will re-send v3 with fixes tag to 'bpf'

Sending via 'bpf' tree would require dropping patch #1.
The test_tcp_custom_syncookie is not yet in 'bpf'.
Note that patch #2 breaks syncookie test w/o patch #1.
Should I split this in two parts?
- patch #1   - send via bpf-next
- patch #2,3 - send via bpf

Yonghong Song Feb. 20, 2024, 12:30 a.m. UTC | #4

On 2/19/24 4:48 AM, Eduard Zingerman wrote:
> On Sat, 2024-02-17 at 20:19 +0200, Eduard Zingerman wrote:
> [...]
>
>>> Also, shouldn't this go into bpf tree instead of bpf-next?
>> Will re-send v3 with fixes tag to 'bpf'
> Sending via 'bpf' tree would require dropping patch #1.
> The test_tcp_custom_syncookie is not yet in 'bpf'.
> Note that patch #2 breaks syncookie test w/o patch #1.
> Should I split this in two parts?
> - patch #1   - send via bpf-next
> - patch #2,3 - send via bpf

Sounds good to me. Patch 1 will likely to be merged in bpf-next
before patch 2/3 merged in bpf tree and circulared back to bpf-next.
Please add related commit message in Patch 1 to explain actual
fix will go to bpf tree and will be back to bpf-next later.

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 011d54a1dc53..c1fa1de590dc 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -16705,6 +16705,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))