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.
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.
