On Mon, Mar 4, 2024 at 8:52 PM Alexei Starovoitov
<alexei.starovoitov@xxxxxxxxx> wrote:
>
> From: Alexei Starovoitov <ast@xxxxxxxxxx>
>
> When open code iterators, bpf_loop or may_goto is used the following two states
> are equivalent and safe to prune the search:
>
> cur state: fp-8_w=scalar(id=3,smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
> old state: fp-8_rw=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
>
> In other words "exact" state match should ignore liveness and precision marks,
> since open coded iterator logic didn't complete their propagation,
> but range_within logic that applies to scalars, ptr_to_mem, map_value, pkt_ptr
> is safe to rely on.
>
> Avoid doing such comparison when regular infinite loop detection logic is used,
> otherwise bounded loop logic will declare such "infinite loop" as false
> positive. Such example is in progs/verifier_loops1.c not_an_inifinite_loop().
>
> Signed-off-by: Alexei Starovoitov <ast@xxxxxxxxxx>
> ---
You haven't updated stacksafe() to work with enums (the code still
assumes bool), please adjust.
pw-bot: cr
Also, I wonder if we actually need three cases. We need EXACT only for
infinite loop detection, right? I wonder if that infinite loop
detection is actually that useful in practice, I rarely encounter it
(if at all), and it constantly causes issues.
What if we just dropped infinite loop detection logic altogether and
have NOT_EXACT vs RANGE_WITHIN logic only?
> kernel/bpf/verifier.c | 39 ++++++++++++++++++++++-----------------
> 1 file changed, 22 insertions(+), 17 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 226bb65f9c2c..74b55d5571c7 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -16254,8 +16254,8 @@ static int check_btf_info(struct bpf_verifier_env *env,
> }
>
> /* check %cur's range satisfies %old's */
> -static bool range_within(struct bpf_reg_state *old,
> - struct bpf_reg_state *cur)
> +static bool range_within(const struct bpf_reg_state *old,
> + const struct bpf_reg_state *cur)
> {
> return old->umin_value <= cur->umin_value &&
> old->umax_value >= cur->umax_value &&
> @@ -16419,21 +16419,26 @@ static bool regs_exact(const struct bpf_reg_state *rold,
> check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
> }
>
> +enum exact_level {
> + NOT_EXACT,
> + EXACT,
> + RANGE_WITHIN
> +};
> +
> /* Returns true if (rold safe implies rcur safe) */
> static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> - struct bpf_reg_state *rcur, struct bpf_idmap *idmap, bool exact)
> + struct bpf_reg_state *rcur, struct bpf_idmap *idmap,
> + enum exact_level exact)
> {
> - if (exact)
> + if (exact == EXACT)
> return regs_exact(rold, rcur, idmap);
>
> - if (!(rold->live & REG_LIVE_READ))
> + if (!(rold->live & REG_LIVE_READ) && exact != RANGE_WITHIN)
imo, `exact == NOT_EXACT` is easier to follow (we excluded EXACT above)
> /* explored state didn't use this */
> return true;
> - if (rold->type == NOT_INIT)
> + if (rold->type == NOT_INIT && exact != RANGE_WITHIN)
ditto
> /* explored state can't have used this */
> return true;
> - if (rcur->type == NOT_INIT)
> - return false;
do we need to remove this? in which case will it do the wrong thing?
>
> /* Enforce that register types have to match exactly, including their
> * modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general
> @@ -16468,7 +16473,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
> check_scalar_ids(rold->id, rcur->id, idmap);
> }
> - if (!rold->precise)
> + if (!rold->precise && exact != RANGE_WITHIN)
same, I think explicit `exact == NOT_EXACT` is easier to follow
> return true;
> /* Why check_ids() for scalar registers?
> *
> @@ -16579,7 +16584,7 @@ static struct bpf_reg_state *scalar_reg_for_stack(struct bpf_verifier_env *env,
> }
>
> static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
> - struct bpf_func_state *cur, struct bpf_idmap *idmap, bool exact)
> + struct bpf_func_state *cur, struct bpf_idmap *idmap, enum exact_level exact)
> {
> int i, spi;
>
> @@ -16743,7 +16748,7 @@ static bool refsafe(struct bpf_func_state *old, struct bpf_func_state *cur,
> * the current state will reach 'bpf_exit' instruction safely
> */
> static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old,
> - struct bpf_func_state *cur, bool exact)
> + struct bpf_func_state *cur, enum exact_level exact)
> {
> int i;
>
> @@ -16770,7 +16775,7 @@ static void reset_idmap_scratch(struct bpf_verifier_env *env)
> static bool states_equal(struct bpf_verifier_env *env,
> struct bpf_verifier_state *old,
> struct bpf_verifier_state *cur,
> - bool exact)
> + enum exact_level exact)
> {
> int i;
>
> @@ -17144,7 +17149,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
> * => unsafe memory access at 11 would not be caught.
> */
> if (is_iter_next_insn(env, insn_idx)) {
> - if (states_equal(env, &sl->state, cur, true)) {
> + if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
> struct bpf_func_state *cur_frame;
> struct bpf_reg_state *iter_state, *iter_reg;
> int spi;
> @@ -17168,20 +17173,20 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
> goto skip_inf_loop_check;
> }
> if (is_may_goto_insn(env, insn_idx)) {
> - if (states_equal(env, &sl->state, cur, true)) {
> + if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
> update_loop_entry(cur, &sl->state);
> goto hit;
> }
> goto skip_inf_loop_check;
> }
> if (calls_callback(env, insn_idx)) {
> - if (states_equal(env, &sl->state, cur, true))
> + if (states_equal(env, &sl->state, cur, RANGE_WITHIN))
> goto hit;
> goto skip_inf_loop_check;
> }
> /* attempt to detect infinite loop to avoid unnecessary doomed work */
> if (states_maybe_looping(&sl->state, cur) &&
> - states_equal(env, &sl->state, cur, true) &&
> + states_equal(env, &sl->state, cur, EXACT) &&
> !iter_active_depths_differ(&sl->state, cur) &&
> sl->state.may_goto_cnt == cur->may_goto_cnt &&
> sl->state.callback_unroll_depth == cur->callback_unroll_depth) {
> @@ -17239,7 +17244,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
> */
> loop_entry = get_loop_entry(&sl->state);
> force_exact = loop_entry && loop_entry->branches > 0;
> - if (states_equal(env, &sl->state, cur, force_exact)) {
> + if (states_equal(env, &sl->state, cur, force_exact ? RANGE_WITHIN : NOT_EXACT)) {
> if (force_exact)
> update_loop_entry(cur, loop_entry);
> hit:
> --
> 2.43.0
>
