From: Alexei Starovoitov A fix of the main pass that stands alone. It is also a prerequisite of the patch that refines linked registers at conditional jumps: that patch intersects the range of one register with var_off of another one and asks reg_is_empty() if the intersection is empty. 1: r0 <<= 3 2: r0 += 5 3: if r0 s< -2 goto pc+2 4: if r0 s> 1 goto pc+1 5: r0 += 3 verifier bug: REG INVARIANTS VIOLATION (alu): range bounds violation The low three bits of r0 are 5. No value in [-2, 1] has them: the range and var_off don't overlap, the fall-through branch of insn 4 is dead. The verifier takes it with an empty register, and the addition at insn 5 trips over that. simulate_both_branches_taken() refines the registers as each branch does and drops a branch in which a range is empty. It relies on reg_bounds_sync() to empty the range. __update_reg64_bounds() steps through var_off from umin to umax, which are 0 and U64_MAX for a range that crosses 0. __update_reg32_bounds() uses only the smallest and the largest member of var_off. tnum_step() returns the next member of var_off. reg_is_empty() asks for the first one from the start of the range on and compares it with the end, in 64 and in 32 bits. A range that crosses 0 wraps around at U64_MAX or U32_MAX: tnum_overlaps_cnum() splits it there. The test is sufficient, not exact: 64 and 32 bits are checked each on its own. The live branch gets the operands that simulate_both_branches_taken() refined for it, as when both branches are live: refine_live_branch(). Not after JSET, whose fall-through branch forgets the ranges. So far check_cond_jmp_op() followed the live branch with the operands as they were before the jump: with more branches found dead, valid progs would get looser bounds. Registers with the same scalar id are not refined there. The patch that refines linked registers at conditional jumps does it. Three tests in verifier_bounds.c. Two have the values above shifted left by 32: no member of var_off is in [-2, 1] and the branch is dead, -3 is one in [-3, 1] and the branch is verified. The third one has the jumps above: the fall-through branch is dead, r0 is not negative in the jump branch. Signed-off-by: Alexei Starovoitov --- kernel/bpf/verifier.c | 80 +++++++++++++++++-- .../selftests/bpf/progs/verifier_bounds.c | 58 ++++++++++++++ 2 files changed, 132 insertions(+), 6 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 5bffc1e288f6..9db855bd6e1c 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2325,6 +2325,36 @@ static bool range_bounds_violation(struct bpf_reg_state *reg) return cnum32_is_empty(reg->r32) || cnum64_is_empty(reg->r64); } +/* Do @t and [min, max] overlap: is a member of @t in the range? */ +static bool tnum_overlaps_urange(struct tnum t, u64 min, u64 max) +{ + u64 tnum_next = tnum_step(t, min); + + return (min & ~t.mask) == t.value || (tnum_next > min && tnum_next <= max); +} + +/* The same for the cnum [@base, @base + @size]. It wraps around at @ut_max. */ +static bool tnum_overlaps_cnum(struct tnum t, u64 base, u64 size, u64 ut_max) +{ + u64 end = (base + size) & ut_max; + + if (base <= end) + return tnum_overlaps_urange(t, base, end); + return tnum_overlaps_urange(t, base, ut_max) || tnum_overlaps_urange(t, 0, end); +} + +/* + * A range and var_off don't overlap. reg_bounds_sync() compares var_off with umin and umax: it + * doesn't see that [-2, 1], which crosses 0, has no member with 5 in its low three bits. + */ +static bool reg_is_empty(struct bpf_reg_state *reg) +{ + return range_bounds_violation(reg) || + !tnum_overlaps_cnum(reg->var_off, reg->r64.base, reg->r64.size, U64_MAX) || + !tnum_overlaps_cnum(tnum_subreg(reg->var_off), reg->r32.base, reg->r32.size, + U32_MAX); +} + static int reg_bounds_sanity_check(struct bpf_verifier_env *env, struct bpf_reg_state *reg, const char *ctx) { @@ -18911,24 +18941,24 @@ static int simulate_both_branches_taken(struct bpf_verifier_env *env, u8 opcode, regs_refine_cond_op(&env->false_reg1, &env->false_reg2, bpf_rev_opcode(opcode), is_jmp32); reg_bounds_sync(&env->false_reg1); reg_bounds_sync(&env->false_reg2); + /* Jump (TRUE) branch. If FALSE is dead refine_live_branch() takes these registers. */ + regs_refine_cond_op(&env->true_reg1, &env->true_reg2, opcode, is_jmp32); + reg_bounds_sync(&env->true_reg1); + reg_bounds_sync(&env->true_reg2); /* * If there is a range bounds violation in *any* of the abstract values in either * reg_states in the FALSE branch (i.e. reg1, reg2), the FALSE branch must be dead. Only * TRUE branch will be taken. */ - if (range_bounds_violation(&env->false_reg1) || range_bounds_violation(&env->false_reg2)) + if (reg_is_empty(&env->false_reg1) || reg_is_empty(&env->false_reg2)) return 1; - /* Jump (TRUE) branch */ - regs_refine_cond_op(&env->true_reg1, &env->true_reg2, opcode, is_jmp32); - reg_bounds_sync(&env->true_reg1); - reg_bounds_sync(&env->true_reg2); /* * If there is a range bounds violation in *any* of the abstract values in either * reg_states in the TRUE branch (i.e. true_reg1, true_reg2), the TRUE branch must be dead. * Only FALSE branch will be taken. */ - if (range_bounds_violation(&env->true_reg1) || range_bounds_violation(&env->true_reg2)) + if (reg_is_empty(&env->true_reg1) || reg_is_empty(&env->true_reg2)) return 0; /* Both branches are possible, we can't determine which one will be taken. */ @@ -19683,6 +19713,38 @@ static void mark_loop_exit_decided(struct bpf_verifier_env *env, struct bpf_veri } } +/* + * One branch of the jump @insn is dead, the current state takes the other one. @reg1 and @reg2 are + * the operands as that branch refines them. They hold every value that takes it, whether the other + * branch is dead or not. + */ +static int refine_live_branch(struct bpf_verifier_env *env, struct bpf_insn *insn, + struct bpf_reg_state *reg1, struct bpf_reg_state *reg2) +{ + struct bpf_reg_state *regs = cur_regs(env); + int err; + + /* is_branch_taken() knew the branch before it refined anything */ + if (!memcmp(reg1, ®s[insn->dst_reg], sizeof(*reg1)) && + (BPF_SRC(insn->code) == BPF_K || !memcmp(reg2, ®s[insn->src_reg], sizeof(*reg2)))) + return 0; + /* + * The fall-through branch of JSET forgets the ranges. Or this branch is dead too: the path + * is infeasible. The registers are left as they are. + */ + if (BPF_OP(insn->code) == BPF_JSET || reg_is_empty(reg1) || reg_is_empty(reg2)) + return 0; + err = reg_bounds_sanity_check(env, reg1, "live_reg1"); + err = err ?: reg_bounds_sanity_check(env, reg2, "live_reg2"); + if (err) + return err; + + regs[insn->dst_reg] = *reg1; + if (BPF_SRC(insn->code) == BPF_X) + regs[insn->src_reg] = *reg2; + return 0; +} + static int check_cond_jmp_op(struct bpf_verifier_env *env, struct bpf_insn *insn, int *insn_idx) { @@ -19788,6 +19850,9 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, if (err < 0) return err; } + err = refine_live_branch(env, insn, &env->true_reg1, &env->true_reg2); + if (err) + return err; if (env->log.level & BPF_LOG_LEVEL) print_insn_state(env, this_branch, this_branch->curframe); *insn_idx += insn->off; @@ -19803,6 +19868,9 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, if (err < 0) return err; } + err = refine_live_branch(env, insn, &env->false_reg1, &env->false_reg2); + if (err) + return err; if (env->log.level & BPF_LOG_LEVEL) print_insn_state(env, this_branch, this_branch->curframe); return 0; diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c index f55d58af8004..f4fe85c46c04 100644 --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c @@ -1995,6 +1995,64 @@ __naked void bounds_refinement_multiple_overlaps(void *ctx) : __clobber_all); } +/* + * r0 is x << 32, the low three bits of x are 5. No such x is in [-2, 1], -3 is in [-3, 1]. + * umin and umax are unbounded for a range that crosses 0. + */ +#define RANGE_CROSSES_0(name, smin) \ +__naked void name(void *ctx) \ +{ \ + asm volatile( \ + "call %[bpf_ktime_get_ns];" \ + "r0 <<= 35;" \ + "r1 = 0x500000000 ll;" \ + "r0 += r1;" \ + "r1 = " #smin " ll;" \ + "if r0 s< r1 goto 1f;" \ + "r1 = 0x100000000 ll;" \ + "if r0 s> r1 goto 1f;" \ + "r10 = 0;" \ +"1: exit;" \ + : \ + : __imm(bpf_ktime_get_ns) \ + : __clobber_all); \ +} + +SEC("socket") +__description("dead branch: tnum and a range that crosses 0 don't overlap") +__success +RANGE_CROSSES_0(range_crossing_0_no_tnum_overlap, -0x200000000) + +SEC("socket") +__description("tnum overlaps the negative part of a range that crosses 0") +__failure __msg("frame pointer is read only") +RANGE_CROSSES_0(range_crossing_0_tnum_overlap_below_0, -0x300000000) + +/* + * The low three bits of r0 are 5. No such value is in [-2, 1]: the fall-through branch of the + * second jump is dead. The jump branch refines r0 to [5, S64_MAX - 2]. + */ +SEC("socket") +__description("dead branch: the live branch is refined") +__success +__naked void dead_branch_live_branch_is_refined(void *ctx) +{ + asm volatile( + "call %[bpf_ktime_get_ns];" + "r0 <<= 3;" + "r0 += 5;" + "if r0 s< -2 goto 1f;" + "if r0 s> 1 goto +1;" + "exit;" + "r0 s>>= 63;" + "if r0 == 0 goto 1f;" + "r10 = 0;" +"1: exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + SEC("socket") __success __naked void signed_unsigned_intersection32_case1(void *ctx) -- 2.55.0