On Thu, May 04, 2023 at 03:00:06PM -0700, Andrii Nakryiko wrote:
> On Thu, May 4, 2023 at 9:37 AM Alexei Starovoitov
> <alexei.starovoitov@xxxxxxxxx> wrote:
> >
> > On Tue, Apr 25, 2023 at 04:49:08PM -0700, Andrii Nakryiko wrote:
> > > When precision backtracking bails out due to some unsupported sequence
> > > of instructions (e.g., stack access through register other than r10), we
> > > need to mark all SCALAR registers as precise to be safe. Currently,
> > > though, we mark SCALARs precise only starting from the state we detected
> > > unsupported condition, which could be one of the parent states of the
> > > actual current state. This will leave some registers potentially not
> > > marked as precise, even though they should. So make sure we start
> > > marking scalars as precise from current state (env->cur_state).
> > >
> > > Further, we don't currently detect a situation when we end up with some
> > > stack slots marked as needing precision, but we ran out of available
> > > states to find the instructions that populate those stack slots. This is
> > > akin the `i >= func->allocated_stack / BPF_REG_SIZE` check and should be
> > > handled similarly by falling back to marking all SCALARs precise. Add
> > > this check when we run out of states.
> > >
> > > Signed-off-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
> > > ---
> > > kernel/bpf/verifier.c | 16 +++++++++++++---
> > > tools/testing/selftests/bpf/verifier/precise.c | 9 +++++----
> > > 2 files changed, 18 insertions(+), 7 deletions(-)
> > >
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 66d64ac10fb1..35f34c977819 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -3781,7 +3781,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int frame, int r
> > > err = backtrack_insn(env, i, bt);
> > > }
> > > if (err == -ENOTSUPP) {
> > > - mark_all_scalars_precise(env, st);
> > > + mark_all_scalars_precise(env, env->cur_state);
> > > bt_reset(bt);
> > > return 0;
> > > } else if (err) {
> > > @@ -3843,7 +3843,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int frame, int r
> > > * fp-8 and it's "unallocated" stack space.
> > > * In such case fallback to conservative.
> > > */
> > > - mark_all_scalars_precise(env, st);
> > > + mark_all_scalars_precise(env, env->cur_state);
> > > bt_reset(bt);
> > > return 0;
> > > }
> > > @@ -3872,11 +3872,21 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int frame, int r
> > > }
> > >
> > > if (bt_bitcnt(bt) == 0)
> > > - break;
> > > + return 0;
> > >
> > > last_idx = st->last_insn_idx;
> > > first_idx = st->first_insn_idx;
> > > }
> > > +
> > > + /* if we still have requested precise regs or slots, we missed
> > > + * something (e.g., stack access through non-r10 register), so
> > > + * fallback to marking all precise
> > > + */
> > > + if (bt_bitcnt(bt) != 0) {
> > > + mark_all_scalars_precise(env, env->cur_state);
> > > + bt_reset(bt);
> > > + }
> >
> > We get here only after:
> > st = st->parent;
> > if (!st)
> > break;
> >
> > which is the case when we reach the very beginning of the program (parent == NULL) and
> > there are still regs or stack with marks.
> > That's a situation when backtracking encountered something we didn't foresee. Some new
> > condition. Currently we don't have selftest that trigger this.
> > So as a defensive mechanism it makes sense to do mark_all_scalars_precise(env, env->cur_state);
> > Probably needs verbose("verifier backtracking bug") as well.
>
> I hesitated to add a bug message because of a known case where this
> could happen: stack access through non-r10 register. So it's not a
> bug, it's similar to -ENOTSUPP cases above, kind of expected, if rare.
fair enough. I'm ok to skip verbose().
> >
> > But for the other two cases mark_all_scalars_precise(env, st); is safe.
> > What's the reason to mark everything precise from the very beginning of backtracking (last seen state == current state).
> > Since unsupported condition was in the middle it's safe to mark from that condition till start of prog.
>
> So I don't have a constructed example and it's more of a hunch. But
> let's use the same stack slot precision when some instructions use
> non-r10 registers. We can't always reliably and immediately detect
> this situation, so the point at which we realize that something is off
> could be in parent state, but that same slot might be used in children
> state and if we don't mark everything precise from the current state,
> then we are running a risk of leaving some of the slots as imprecise.
>
> Before patch #8 similar situation could be also with r0 returned from
> static subprog. Something like this:
>
>
> P2: call subprog
> <<- checkpoint ->>
> P1: r1 = r0;
> <<- checkpoint ->>
> CUR: r2 = <map value pointer>
> r2 += r1 <--- need to mark r0 precise and propagate all the way
> to P2 and beyond
>
>
> Precision propagation will be triggered in CUR state. Will go through
> P1, come back to P2 and (before patch #8 changes) will realize this is
> unsupported case. Currently we'll mark R0 precise only in P2 and its
> parents (could be also r6-r9 registers situation).
Correct. I'm with you so far...
> But really we
> should make sure that P1 also has r1 marked as precise.
and here I'm a bit lost.
Precision marking will do r1->precise=true while walking P1 in that state.
The change:
mark_all_scalars_precise(env, env->cur_state);
will mark both r0 and r1 in P1, but that's unnecessary.
> So as a general rule, I think the only safe default is to mark
> everything precise from current state.
>
> Is the above convincing or should I revert back to old behavior?
I'm not seeing the issue yet.
