Daniel Borkmann wrote: > Juan reported that after doing some changes to buzzer [0] and implementing > a new fuzzing strategy guided by coverage, they noticed the following in > one of the probes: > > [...] > 13: (79) r6 = *(u64 *)(r0 +0) ; R0=map_value(ks=4,vs=8) R6_w=scalar() > 14: (b7) r0 = 0 ; R0_w=0 > 15: (b4) w0 = -1 ; R0_w=0xffffffff > 16: (74) w0 >>= 1 ; R0_w=0x7fffffff > 17: (5c) w6 &= w0 ; R0_w=0x7fffffff R6_w=scalar(smin=smin32=0,smax=umax=umax32=0x7fffffff,var_off=(0x0; 0x7fffffff)) > 18: (44) w6 |= 2 ; R6_w=scalar(smin=umin=smin32=umin32=2,smax=umax=umax32=0x7fffffff,var_off=(0x2; 0x7ffffffd)) > 19: (56) if w6 != 0x7ffffffd goto pc+1 > REG INVARIANTS VIOLATION (true_reg2): range bounds violation u64=[0x7fffffff, 0x7ffffffd] s64=[0x7fffffff, 0x7ffffffd] u32=[0x7fffffff, 0x7ffffffd] s32=[0x7fffffff, 0x7ffffffd] var_off=(0x7fffffff, 0x0) > REG INVARIANTS VIOLATION (false_reg1): range bounds violation u64=[0x7fffffff, 0x7ffffffd] s64=[0x7fffffff, 0x7ffffffd] u32=[0x7fffffff, 0x7ffffffd] s32=[0x7fffffff, 0x7ffffffd] var_off=(0x7fffffff, 0x0) > REG INVARIANTS VIOLATION (false_reg2): const tnum out of sync with range bounds u64=[0x0, 0xffffffffffffffff] s64=[0x8000000000000000, 0x7fffffffffffffff] u32=[0x0, 0xffffffff] s32=[0x80000000, 0x7fffffff] var_off=(0x7fffffff, 0x0) > 19: R6_w=0x7fffffff > 20: (95) exit > > from 19 to 21: R0=0x7fffffff R6=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=0x7ffffffe,var_off=(0x2; 0x7ffffffd)) R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm > 21: R0=0x7fffffff R6=scalar(smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=0x7ffffffe,var_off=(0x2; 0x7ffffffd)) R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm > 21: (14) w6 -= 2147483632 ; R6_w=scalar(smin=umin=umin32=2,smax=umax=0xffffffff,smin32=0x80000012,smax32=14,var_off=(0x2; 0xfffffffd)) > 22: (76) if w6 s>= 0xe goto pc+1 ; R6_w=scalar(smin=umin=umin32=2,smax=umax=0xffffffff,smin32=0x80000012,smax32=13,var_off=(0x2; 0xfffffffd)) > 23: (95) exit > > from 22 to 24: R0=0x7fffffff R6_w=14 R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm > 24: R0=0x7fffffff R6_w=14 R7=map_ptr(ks=4,vs=8) R9=ctx() R10=fp0 fp-24=map_ptr(ks=4,vs=8) fp-40=mmmmmmmm > 24: (14) w6 -= 14 ; R6_w=0 > [...] > > What can be seen here is a register invariant violation on line 19. After > the binary-or in line 18, the verifier knows that bit 2 is set but knows > nothing about the rest of the content which was loaded from a map value, > meaning, range is [2,0x7fffffff] with var_off=(0x2; 0x7ffffffd). When in > line 19 the verifier analyzes the branch, it splits the register states > in reg_set_min_max() into the registers of the true branch (true_reg1, > true_reg2) and the registers of the false branch (false_reg1, false_reg2). > > Since the test is w6 != 0x7ffffffd, the src_reg is a known constant. > Internally, the verifier creates a "fake" register initialized as scalar > to the value of 0x7ffffffd, and then passes it onto reg_set_min_max(). Now, > for line 19, it is mathematically impossible to take the false branch of > this program, yet the verifier analyzes it. It is impossible because the > second bit of r6 will be set due to the prior or operation and the > constant in the condition has that bit unset (hex(fd) == binary(1111 1101). > > When the verifier first analyzes the false / fall-through branch, it will > compute an intersection between the var_off of r6 and of the constant. This > is because the verifier creates a "fake" register initialized to the value > of the constant. The intersection result later refines both registers in > regs_refine_cond_op(): > > [...] > t = tnum_intersect(tnum_subreg(reg1->var_off), tnum_subreg(reg2->var_off)); > reg1->var_off = tnum_with_subreg(reg1->var_off, t); > reg2->var_off = tnum_with_subreg(reg2->var_off, t); > [...] > > Since the verifier is analyzing the false branch of the conditional jump, > reg1 is equal to false_reg1 and reg2 is equal to false_reg2, i.e. the reg2 > is the "fake" register that was meant to hold a constant value. The resulting > var_off of the intersection says that both registers now hold a known value > of var_off=(0x7fffffff, 0x0) or in other words: this operation manages to > make the verifier think that the "constant" value that was passed in the > jump operation now holds a different value. > > Normally this would not be an issue since it should not influence the true > branch, however, false_reg2 and true_reg2 are pointers to the same "fake" > register. Meaning, the false branch can influence the results of the true > branch. In line 24, the verifier assumes R6_w=0, but the actual runtime > value in this case is 1. The fix is simply not passing in the same "fake" > register location as inputs to reg_set_min_max(), but instead making a > copy. With this, the verifier successfully rejects invalid accesses from > the test program. > > [0] https://github.com/google/buzzer > > Fixes: 67420501e868 ("bpf: generalize reg_set_min_max() to handle non-const register comparisons") > Reported-by: Juan José López Jaimez <jjlopezjaimez@xxxxxxxxxx> > Signed-off-by: Daniel Borkmann <daniel@xxxxxxxxxxxxx> > --- Reviewed-by: John Fastabend <john.fastabend@xxxxxxxxx>
