Patch "bpf: check bpf_func_state->callback_depth when pruning states" has been added to the 6.6-stable tree

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



This is a note to let you know that I've just added the patch titled

    bpf: check bpf_func_state->callback_depth when pruning states

to the 6.6-stable tree which can be found at:
    http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
     bpf-check-bpf_func_state-callback_depth-when-pruning.patch
and it can be found in the queue-6.6 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree,
please let <stable@xxxxxxxxxxxxxxx> know about it.



commit 7c9d40a5754ad7178a258c251895e21399b5e3b0
Author: Eduard Zingerman <eddyz87@xxxxxxxxx>
Date:   Thu Feb 22 17:41:20 2024 +0200

    bpf: check bpf_func_state->callback_depth when pruning states
    
    [ Upstream commit e9a8e5a587ca55fec6c58e4881742705d45bee54 ]
    
    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] (assume that BPF_F_TEST_STATE_FREQ is set).
    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
    (a)      - (2) {7P,7,42},depth=2
               - (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             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/9b251840-7cb8-4d17-bd23-1fc8071d8eef@xxxxxxxxx/
    
    Fixes: bb124da69c47 ("bpf: keep track of max number of bpf_loop callback iterations")
    Suggested-by: Yonghong Song <yonghong.song@xxxxxxxxx>
    Signed-off-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
    Acked-by: Yonghong Song <yonghong.song@xxxxxxxxx>
    Link: https://lore.kernel.org/r/20240222154121.6991-2-eddyz87@xxxxxxxxx
    Signed-off-by: Alexei Starovoitov <ast@xxxxxxxxxx>
    Signed-off-by: Sasha Levin <sashal@xxxxxxxxxx>

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a7901ed358a0f..396c4c66932f2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -16238,6 +16238,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))




[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Index of Archives]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]

  Powered by Linux