From: Alexei Starovoitov A valid program can be rejected. No unsafe program is accepted, because the path-sensitive run accepts nothing. After a pass with an error, the run looks for one path to the error. It skips trips of a loop. It gets the number of trips from the step of the iv and the bound, as if the bound stays: i = 0; n = 60; do { end = flag ? 60 : --n; } while (++i < end); buf[n - 30]; If flag is 0, the loop ends at i = 30, n = 30. At i = 5, n = 55 the run counts 50 more trips and skips to i = 54, n = 6. No path has this state, but the access to buf fails with it. The error counts as real, so the budget of the next passes is cut. If the program needs more than that budget, it is rejected. Keep the bound in exit_threshold, which this run does not use, and compare it with the bound of the saved trip. If it moved, mark the skip as a guess. A guess does not cut the budget. If the bound is a range, the jump moves one end of it. Keep the other end. Fixes: a46de5d64e18 ("bpf: Reproduce an error on one path, with no joins") Signed-off-by: Alexei Starovoitov --- include/linux/bpf_verifier.h | 6 +++++- kernel/bpf/equation_join.c | 12 +++++++++--- kernel/bpf/verifier.c | 7 +++++-- 3 files changed, 19 insertions(+), 6 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 7f9594436e..88b3a5226c 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -456,7 +456,11 @@ struct loop_stack_entry { /* an xreg: how many times the program came back to the header */ struct scalar trip_index; bool trip_widened; /* it was moved to a threshold, or it does not grow */ - u64 exit_threshold; /* by the jumps that the state passed and that leave the loop */ + /* + * The trip index at which a jump that the state passed leaves the loop. + * Path-sensitive run: the bound that the jump on the iv saw. + */ + u64 exit_threshold; /* Path-sensitive run: the jump that tests the iv, the value it saw, the trips left */ u32 iv_jump_idx; u64 iv_prev, trips_left; diff --git a/kernel/bpf/equation_join.c b/kernel/bpf/equation_join.c index a01f0fdc74..e601e3dda7 100644 --- a/kernel/bpf/equation_join.c +++ b/kernel/bpf/equation_join.c @@ -756,11 +756,17 @@ static void note_trips_left(struct bpf_verifier_env *env, struct loop_stack_entr far_end = value + (step < 0 ? 0 : jmp32 ? x->r32.size : x->r64.size); if (e->iv_jump_idx) e->trips_left = step ? compute_trip_count(step, &far_end, op, jmp32, *bound) : 0; - if (e->iv_jump_idx && step && is_body_jump && !e->trips_left) - e->trips_left = compute_trip_count(step, &far_end, bpf_rev_opcode(op), - jmp32, *bound); + if (e->iv_jump_idx && step && is_body_jump && !e->trips_left) { + op = bpf_rev_opcode(op); + e->trips_left = compute_trip_count(step, &far_end, op, jmp32, *bound); + } e->iv_jump_idx = env->insn_idx; e->iv_prev = value; + /* the jump moves the other end of the bound */ + op = bpf_signed_opcode(op); + e->exit_threshold = jmp32 ? bound->r32.base : bound->r64.base; + if (op != BPF_JSGT && op != BPF_JSGE && (op != BPF_JNE || step > 0)) + e->exit_threshold += jmp32 ? bound->r32.size : bound->r64.size; } static void move_bounds(struct bpf_verifier_env *env, struct scalar *s, bool is_ptr, u64 off) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 1e24c51a49..0b8063dbb3 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -21046,12 +21046,14 @@ static int check_held_in_leftover(struct bpf_verifier_env *env, * for (i = 0; i < 100000; i++) { if (rnd() && n < 8) n++; } * Two trips show a step also for 'sum += i', and more than 2^32 trips also for a ring index. * If the steps are not constant, the skip or "infinite" is a guess. + * If the bound moved, the skip is a guess. * Returns 1 if it skipped these trips. */ static int fast_forward_trips(struct bpf_verifier_env *env, struct loop_stack_entry *entry) { struct bpf_verifier_state *cur = env->cur_state, *old = &entry->header_state->st; - u32 period = entry->trip - bpf_top_loop(old->frame[old->curframe])->trip; + const struct loop_stack_entry *saved = bpf_top_loop(old->frame[old->curframe]); + u32 period = entry->trip - saved->trip; bool infinite = entry->trips_left > BPF_MAX_TRIPS, guess; DECLARE_BITMAP(iv_xregs, MAX_BPF_XREG) = {}; int err; @@ -21064,7 +21066,8 @@ static int fast_forward_trips(struct bpf_verifier_env *env, struct loop_stack_en err = bpf_jumps_see_same(env, old, cur, entry->iv_jump_idx, infinite ? NULL : iv_xregs); if (err <= 0) return err; - guess = !bpf_steps_are_constant(env, entry, iv_xregs, infinite); + guess = (!infinite && saved->exit_threshold != entry->exit_threshold) || + !bpf_steps_are_constant(env, entry, iv_xregs, infinite); if (infinite) { entry->loop->infinite = true; entry->loop->infinite_is_guess = guess || env->run_has_guess; -- 2.55.0