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.
>
> 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). But really we
should make sure that P1 also has r1 marked as precise.
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?
