Re: [PATCH bpf 1/3] bpf: Fix incorrect delta propagation between linked registers

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2024-10-16 at 15:49 +0200, Daniel Borkmann wrote:
> Nathaniel reported a bug in the linked scalar delta tracking, which can lead
> to accepting a program with OOB access. The specific code is related to the
> sync_linked_regs() function and the BPF_ADD_CONST flag, which signifies a
> constant offset between two scalar registers tracked by the same register id.
> 
> The verifier attempts to track "similar" scalars in order to propagate bounds
> information learned about one scalar to others. For instance, if r1 and r2
> are known to contain the same value, then upon encountering 'if (r1 != 0x1234)
> goto xyz', not only does it know that r1 is equal to 0x1234 on the path where
> that conditional jump is not taken, it also knows that r2 is.
> 
> Additionally, with env->bpf_capable set, the verifier will track scalars
> which should be a constant delta apart (if r1 is known to be one greater than
> r2, then if r1 is known to be equal to 0x1234, r2 must be equal to 0x1233.)
> The code path for the latter in adjust_reg_min_max_vals() is reached when
> processing both 32 and 64-bit addition operations. While adjust_reg_min_max_vals()
> knows whether dst_reg was produced by a 32 or a 64-bit addition (based on the
> alu32 bool), the only information saved in dst_reg is the id of the source
> register (reg->id, or'ed by BPF_ADD_CONST) and the value of the constant
> offset (reg->off).
> 
> Later, the function sync_linked_regs() will attempt to use this information
> to propagate bounds information from one register (known_reg) to others,
> meaning, for all R in linked_regs, it copies known_reg range (and possibly
> adjusting delta) into R for the case of R->id == known_reg->id.
> 
> For the delta adjustment, meaning, matching reg->id with BPF_ADD_CONST, the
> verifier adjusts the register as reg = known_reg; reg += delta where delta
> is computed as (s32)reg->off - (s32)known_reg->off and placed as a scalar
> into a fake_reg to then simulate the addition of reg += fake_reg. This is
> only correct, however, if the value in reg was created by a 64-bit addition.
> When reg contains the result of a 32-bit addition operation, its upper 32
> bits will always be zero. sync_linked_regs() on the other hand, may cause
> the verifier to believe that the addition between fake_reg and reg overflows
> into those upper bits. For example, if reg was generated by adding the
> constant 1 to known_reg using a 32-bit alu operation, then reg->off is 1
> and known_reg->off is 0. If known_reg is known to be the constant 0xFFFFFFFF,
> sync_linked_regs() will tell the verifier that reg is equal to the constant
> 0x100000000. This is incorrect as the actual value of reg will be 0, as the
> 32-bit addition will wrap around.
> 
> Example:
> 
>   0: (b7) r0 = 0;             R0_w=0
>   1: (18) r1 = 0x80000001;    R1_w=0x80000001
>   3: (37) r1 /= 1;            R1_w=scalar()
>   4: (bf) r2 = r1;            R1_w=scalar(id=1) R2_w=scalar(id=1)
>   5: (bf) r4 = r1;            R1_w=scalar(id=1) R4_w=scalar(id=1)
>   6: (04) w2 += 2147483647;   R2_w=scalar(id=1+2147483647,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
>   7: (04) w4 += 0 ;           R4_w=scalar(id=1+0,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
>   8: (15) if r2 == 0x0 goto pc+1
>  10: R0=0 R1=0xffffffff80000001 R2=0x7fffffff R4=0xffffffff80000001 R10=fp0
> 
> What can be seen here is that r1 is copied to r2 and r4, such that {r1,r2,r4}.id
> are all the same which later lets sync_linked_regs() to be invoked. Then, in
> a next step constants are added with alu32 to r2 and r4, setting their ->off,
> as well as id |= BPF_ADD_CONST. Next, the conditional will bind r2 and
> propagate ranges to its linked registers. The verifier now believes the upper
> 32 bits of r4 are r4=0xffffffff80000001, while actually r4=r1=0x80000001.
> 
> One approach for a simple fix suitable also for stable is to limit the constant
> delta tracking to only 64-bit alu addition. If necessary at some later point,
> BPF_ADD_CONST could be split into BPF_ADD_CONST64 and BPF_ADD_CONST32 to avoid
> mixing the two under the tradeoff to further complicate sync_linked_regs().
> However, none of the added tests from dedf56d775c0 ("selftests/bpf: Add tests
> for add_const") make this necessary at this point, meaning, BPF CI also passes
> with just limiting tracking to 64-bit alu addition.
> 
> Fixes: 98d7ca374ba4 ("bpf: Track delta between "linked" registers.")
> Reported-by: Nathaniel Theis <nathaniel.theis@nccgroup.com>
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---

Thank you for the fix, missed this on the code review :(

Reviewed-by: Eduard Zingerman <eddyz87@gmail.com>

[...]