On Thu, May 4, 2023 at 3:32 PM Alexei Starovoitov
<alexei.starovoitov@xxxxxxxxx> wrote:
>
> 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.
you are right, second example is not relevant because we'll be
properly propagating register precision along the way. So I think
stack access is the only one that might be problematic.
I assume you are worried about regressing due to marking more stuff
precise, right? My thinking (besides the subtle correctness issues
with stack access through non-r10 registers) was that all the other
patterns should be now handled properly, so we shouldn't be even
seeing mark_all_precise() use in practice.
But I'm fine reverting those two existing mark_all_precise() calls, if
you insist.
