* [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
2023-06-06 22:24 [PATCH bpf-next v3 0/4] verify scalar ids mapping in regsafe() Eduard Zingerman
@ 2023-06-06 22:24 ` Eduard Zingerman
2023-06-07 21:40 ` Andrii Nakryiko
2023-06-06 22:24 ` [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids Eduard Zingerman
` (2 subsequent siblings)
3 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-06 22:24 UTC (permalink / raw)
To: bpf, ast; +Cc: andrii, daniel, martin.lau, kernel-team, yhs, Eduard Zingerman
Change mark_chain_precision() to track precision in situations
like below:
r2 = unknown value
...
--- state #0 ---
...
r1 = r2 // r1 and r2 now share the same ID
...
--- state #1 {r1.id = A, r2.id = A} ---
...
if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
...
--- state #2 {r1.id = A, r2.id = A} ---
r3 = r10
r3 += r1 // need to mark both r1 and r2
At the beginning of the processing of each state, ensure that if a
register with a scalar ID is marked as precise, all registers sharing
this ID are also marked as precise.
This property would be used by a follow-up change in regsafe().
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 10 +-
kernel/bpf/verifier.c | 114 ++++++++++++++++++
.../testing/selftests/bpf/verifier/precise.c | 8 +-
3 files changed, 127 insertions(+), 5 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index ee4cc7471ed9..3f9856baa542 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -559,6 +559,11 @@ struct backtrack_state {
u64 stack_masks[MAX_CALL_FRAMES];
};
+struct reg_id_scratch {
+ u32 count;
+ u32 ids[BPF_ID_MAP_SIZE];
+};
+
/* single container for all structs
* one verifier_env per bpf_check() call
*/
@@ -590,7 +595,10 @@ struct bpf_verifier_env {
const struct bpf_line_info *prev_linfo;
struct bpf_verifier_log log;
struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
- struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
+ union {
+ struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
+ struct reg_id_scratch precise_ids_scratch;
+ };
struct {
int *insn_state;
int *insn_stack;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d117deb03806..2aa60b73f1b5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
}
}
+static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id)
+{
+ u32 i;
+
+ for (i = 0; i < s->count; ++i)
+ if (s->ids[i] == id)
+ return true;
+
+ return false;
+}
+
+static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id)
+{
+ if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids)))
+ return -1;
+ s->ids[s->count++] = id;
+ WARN_ONCE(s->count > 64,
+ "reg_id_scratch.count is unreasonably large (%d)", s->count);
+ return 0;
+}
+
+static inline void reg_id_scratch_reset(struct reg_id_scratch *s)
+{
+ s->count = 0;
+}
+
+/* Collect a set of IDs for all registers currently marked as precise in env->bt.
+ * Mark all registers with these IDs as precise.
+ */
+static void mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
+{
+ struct reg_id_scratch *precise_ids = &env->precise_ids_scratch;
+ struct backtrack_state *bt = &env->bt;
+ struct bpf_func_state *func;
+ struct bpf_reg_state *reg;
+ DECLARE_BITMAP(mask, 64);
+ int i, fr;
+
+ reg_id_scratch_reset(precise_ids);
+
+ for (fr = bt->frame; fr >= 0; fr--) {
+ func = st->frame[fr];
+
+ bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr));
+ for_each_set_bit(i, mask, 32) {
+ reg = &func->regs[i];
+ if (!reg->id || reg->type != SCALAR_VALUE)
+ continue;
+ if (reg_id_scratch_push(precise_ids, reg->id))
+ return;
+ }
+
+ bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
+ for_each_set_bit(i, mask, 64) {
+ if (i >= func->allocated_stack / BPF_REG_SIZE)
+ break;
+ if (!is_spilled_scalar_reg(&func->stack[i]))
+ continue;
+ reg = &func->stack[i].spilled_ptr;
+ if (!reg->id || reg->type != SCALAR_VALUE)
+ continue;
+ if (reg_id_scratch_push(precise_ids, reg->id))
+ return;
+ }
+ }
+
+ for (fr = 0; fr <= st->curframe; ++fr) {
+ func = st->frame[fr];
+
+ for (i = BPF_REG_0; i < BPF_REG_10; ++i) {
+ reg = &func->regs[i];
+ if (!reg->id)
+ continue;
+ if (!reg_id_scratch_contains(precise_ids, reg->id))
+ continue;
+ bt_set_frame_reg(bt, fr, i);
+ }
+ for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) {
+ if (!is_spilled_scalar_reg(&func->stack[i]))
+ continue;
+ reg = &func->stack[i].spilled_ptr;
+ if (!reg->id)
+ continue;
+ if (!reg_id_scratch_contains(precise_ids, reg->id))
+ continue;
+ bt_set_frame_slot(bt, fr, i);
+ }
+ }
+}
+
/*
* __mark_chain_precision() backtracks BPF program instruction sequence and
* chain of verifier states making sure that register *regno* (if regno >= 0)
@@ -3910,6 +4000,30 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
bt->frame, last_idx, first_idx, subseq_idx);
}
+ /* If some register with scalar ID is marked as precise,
+ * make sure that all registers sharing this ID are also precise.
+ * This is needed to estimate effect of find_equal_scalars().
+ * Do this at the last instruction of each state,
+ * bpf_reg_state::id fields are valid for these instructions.
+ *
+ * Allows to track precision in situation like below:
+ *
+ * r2 = unknown value
+ * ...
+ * --- state #0 ---
+ * ...
+ * r1 = r2 // r1 and r2 now share the same ID
+ * ...
+ * --- state #1 {r1.id = A, r2.id = A} ---
+ * ...
+ * if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
+ * ...
+ * --- state #2 {r1.id = A, r2.id = A} ---
+ * r3 = r10
+ * r3 += r1 // need to mark both r1 and r2
+ */
+ mark_precise_scalar_ids(env, st);
+
if (last_idx < 0) {
/* we are at the entry into subprog, which
* is expected for global funcs, but only if
diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c
index b8c0aae8e7ec..99272bb890da 100644
--- a/tools/testing/selftests/bpf/verifier/precise.c
+++ b/tools/testing/selftests/bpf/verifier/precise.c
@@ -46,7 +46,7 @@
mark_precise: frame0: regs=r2 stack= before 20\
mark_precise: frame0: parent state regs=r2 stack=:\
mark_precise: frame0: last_idx 19 first_idx 10\
- mark_precise: frame0: regs=r2 stack= before 19\
+ mark_precise: frame0: regs=r2,r9 stack= before 19\
mark_precise: frame0: regs=r9 stack= before 18\
mark_precise: frame0: regs=r8,r9 stack= before 17\
mark_precise: frame0: regs=r0,r9 stack= before 15\
@@ -106,10 +106,10 @@
mark_precise: frame0: regs=r2 stack= before 22\
mark_precise: frame0: parent state regs=r2 stack=:\
mark_precise: frame0: last_idx 20 first_idx 20\
- mark_precise: frame0: regs=r2 stack= before 20\
- mark_precise: frame0: parent state regs=r2 stack=:\
+ mark_precise: frame0: regs=r2,r9 stack= before 20\
+ mark_precise: frame0: parent state regs=r2,r9 stack=:\
mark_precise: frame0: last_idx 19 first_idx 17\
- mark_precise: frame0: regs=r2 stack= before 19\
+ mark_precise: frame0: regs=r2,r9 stack= before 19\
mark_precise: frame0: regs=r9 stack= before 18\
mark_precise: frame0: regs=r8,r9 stack= before 17\
mark_precise: frame0: parent state regs= stack=:",
--
2.40.1
^ permalink raw reply related [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
2023-06-06 22:24 ` [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision() Eduard Zingerman
@ 2023-06-07 21:40 ` Andrii Nakryiko
2023-06-08 12:35 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Andrii Nakryiko @ 2023-06-07 21:40 UTC (permalink / raw)
To: Eduard Zingerman; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Change mark_chain_precision() to track precision in situations
> like below:
>
> r2 = unknown value
> ...
> --- state #0 ---
> ...
> r1 = r2 // r1 and r2 now share the same ID
> ...
> --- state #1 {r1.id = A, r2.id = A} ---
> ...
> if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
> ...
> --- state #2 {r1.id = A, r2.id = A} ---
> r3 = r10
> r3 += r1 // need to mark both r1 and r2
>
> At the beginning of the processing of each state, ensure that if a
> register with a scalar ID is marked as precise, all registers sharing
> this ID are also marked as precise.
>
> This property would be used by a follow-up change in regsafe().
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
> include/linux/bpf_verifier.h | 10 +-
> kernel/bpf/verifier.c | 114 ++++++++++++++++++
> .../testing/selftests/bpf/verifier/precise.c | 8 +-
> 3 files changed, 127 insertions(+), 5 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index ee4cc7471ed9..3f9856baa542 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -559,6 +559,11 @@ struct backtrack_state {
> u64 stack_masks[MAX_CALL_FRAMES];
> };
>
> +struct reg_id_scratch {
> + u32 count;
> + u32 ids[BPF_ID_MAP_SIZE];
> +};
> +
> /* single container for all structs
> * one verifier_env per bpf_check() call
> */
> @@ -590,7 +595,10 @@ struct bpf_verifier_env {
> const struct bpf_line_info *prev_linfo;
> struct bpf_verifier_log log;
> struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
> - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> + union {
> + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> + struct reg_id_scratch precise_ids_scratch;
naming nit: "ids_scratch" or "idset_scratch" to stay in line with
"idmap_scratch"?
> + };
> struct {
> int *insn_state;
> int *insn_stack;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index d117deb03806..2aa60b73f1b5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
> }
> }
>
> +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id)
> +{
> + u32 i;
> +
> + for (i = 0; i < s->count; ++i)
> + if (s->ids[i] == id)
> + return true;
> +
> + return false;
> +}
> +
> +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id)
> +{
> + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids)))
> + return -1;
> + s->ids[s->count++] = id;
this will allow duplicated IDs to be added? Was it done in the name of speed?
> + WARN_ONCE(s->count > 64,
> + "reg_id_scratch.count is unreasonably large (%d)", s->count);
do we need this one? Especially that it's not _ONCE variant? Maybe the
first WARN_ON_ONCE is enough?
> + return 0;
> +}
> +
> +static inline void reg_id_scratch_reset(struct reg_id_scratch *s)
we probably don't need "inline" for all these helpers?
> +{
> + s->count = 0;
> +}
> +
> +/* Collect a set of IDs for all registers currently marked as precise in env->bt.
> + * Mark all registers with these IDs as precise.
> + */
> +static void mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
> +{
> + struct reg_id_scratch *precise_ids = &env->precise_ids_scratch;
> + struct backtrack_state *bt = &env->bt;
> + struct bpf_func_state *func;
> + struct bpf_reg_state *reg;
> + DECLARE_BITMAP(mask, 64);
> + int i, fr;
> +
> + reg_id_scratch_reset(precise_ids);
> +
> + for (fr = bt->frame; fr >= 0; fr--) {
> + func = st->frame[fr];
> +
> + bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr));
> + for_each_set_bit(i, mask, 32) {
> + reg = &func->regs[i];
> + if (!reg->id || reg->type != SCALAR_VALUE)
> + continue;
> + if (reg_id_scratch_push(precise_ids, reg->id))
> + return;
> + }
> +
> + bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
> + for_each_set_bit(i, mask, 64) {
> + if (i >= func->allocated_stack / BPF_REG_SIZE)
> + break;
> + if (!is_spilled_scalar_reg(&func->stack[i]))
> + continue;
> + reg = &func->stack[i].spilled_ptr;
> + if (!reg->id || reg->type != SCALAR_VALUE)
is_spilled_scalar_reg() already ensures reg->type is SCALAR_VALUE
> + continue;
> + if (reg_id_scratch_push(precise_ids, reg->id))
> + return;
if push fails (due to overflow of id set), shouldn't we propagate
error back and fallback to mark_all_precise?
> + }
> + }
> +
> + for (fr = 0; fr <= st->curframe; ++fr) {
> + func = st->frame[fr];
> +
> + for (i = BPF_REG_0; i < BPF_REG_10; ++i) {
> + reg = &func->regs[i];
> + if (!reg->id)
> + continue;
> + if (!reg_id_scratch_contains(precise_ids, reg->id))
> + continue;
> + bt_set_frame_reg(bt, fr, i);
> + }
> + for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) {
> + if (!is_spilled_scalar_reg(&func->stack[i]))
> + continue;
> + reg = &func->stack[i].spilled_ptr;
> + if (!reg->id)
> + continue;
> + if (!reg_id_scratch_contains(precise_ids, reg->id))
> + continue;
> + bt_set_frame_slot(bt, fr, i);
> + }
> + }
> +}
> +
> /*
> * __mark_chain_precision() backtracks BPF program instruction sequence and
> * chain of verifier states making sure that register *regno* (if regno >= 0)
> @@ -3910,6 +4000,30 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
> bt->frame, last_idx, first_idx, subseq_idx);
> }
>
> + /* If some register with scalar ID is marked as precise,
> + * make sure that all registers sharing this ID are also precise.
> + * This is needed to estimate effect of find_equal_scalars().
> + * Do this at the last instruction of each state,
> + * bpf_reg_state::id fields are valid for these instructions.
> + *
> + * Allows to track precision in situation like below:
> + *
> + * r2 = unknown value
> + * ...
> + * --- state #0 ---
> + * ...
> + * r1 = r2 // r1 and r2 now share the same ID
> + * ...
> + * --- state #1 {r1.id = A, r2.id = A} ---
> + * ...
> + * if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
> + * ...
> + * --- state #2 {r1.id = A, r2.id = A} ---
> + * r3 = r10
> + * r3 += r1 // need to mark both r1 and r2
> + */
> + mark_precise_scalar_ids(env, st);
> +
> if (last_idx < 0) {
> /* we are at the entry into subprog, which
> * is expected for global funcs, but only if
> diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c
> index b8c0aae8e7ec..99272bb890da 100644
> --- a/tools/testing/selftests/bpf/verifier/precise.c
> +++ b/tools/testing/selftests/bpf/verifier/precise.c
> @@ -46,7 +46,7 @@
> mark_precise: frame0: regs=r2 stack= before 20\
> mark_precise: frame0: parent state regs=r2 stack=:\
> mark_precise: frame0: last_idx 19 first_idx 10\
> - mark_precise: frame0: regs=r2 stack= before 19\
> + mark_precise: frame0: regs=r2,r9 stack= before 19\
> mark_precise: frame0: regs=r9 stack= before 18\
> mark_precise: frame0: regs=r8,r9 stack= before 17\
> mark_precise: frame0: regs=r0,r9 stack= before 15\
> @@ -106,10 +106,10 @@
> mark_precise: frame0: regs=r2 stack= before 22\
> mark_precise: frame0: parent state regs=r2 stack=:\
> mark_precise: frame0: last_idx 20 first_idx 20\
> - mark_precise: frame0: regs=r2 stack= before 20\
> - mark_precise: frame0: parent state regs=r2 stack=:\
> + mark_precise: frame0: regs=r2,r9 stack= before 20\
> + mark_precise: frame0: parent state regs=r2,r9 stack=:\
> mark_precise: frame0: last_idx 19 first_idx 17\
> - mark_precise: frame0: regs=r2 stack= before 19\
> + mark_precise: frame0: regs=r2,r9 stack= before 19\
> mark_precise: frame0: regs=r9 stack= before 18\
> mark_precise: frame0: regs=r8,r9 stack= before 17\
> mark_precise: frame0: parent state regs= stack=:",
> --
> 2.40.1
>
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
2023-06-07 21:40 ` Andrii Nakryiko
@ 2023-06-08 12:35 ` Eduard Zingerman
2023-06-08 15:43 ` Alexei Starovoitov
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-08 12:35 UTC (permalink / raw)
To: Andrii Nakryiko; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > Change mark_chain_precision() to track precision in situations
> > like below:
> >
> > r2 = unknown value
> > ...
> > --- state #0 ---
> > ...
> > r1 = r2 // r1 and r2 now share the same ID
> > ...
> > --- state #1 {r1.id = A, r2.id = A} ---
> > ...
> > if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
> > ...
> > --- state #2 {r1.id = A, r2.id = A} ---
> > r3 = r10
> > r3 += r1 // need to mark both r1 and r2
> >
> > At the beginning of the processing of each state, ensure that if a
> > register with a scalar ID is marked as precise, all registers sharing
> > this ID are also marked as precise.
> >
> > This property would be used by a follow-up change in regsafe().
> >
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> > include/linux/bpf_verifier.h | 10 +-
> > kernel/bpf/verifier.c | 114 ++++++++++++++++++
> > .../testing/selftests/bpf/verifier/precise.c | 8 +-
> > 3 files changed, 127 insertions(+), 5 deletions(-)
> >
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index ee4cc7471ed9..3f9856baa542 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -559,6 +559,11 @@ struct backtrack_state {
> > u64 stack_masks[MAX_CALL_FRAMES];
> > };
> >
> > +struct reg_id_scratch {
> > + u32 count;
> > + u32 ids[BPF_ID_MAP_SIZE];
> > +};
> > +
> > /* single container for all structs
> > * one verifier_env per bpf_check() call
> > */
> > @@ -590,7 +595,10 @@ struct bpf_verifier_env {
> > const struct bpf_line_info *prev_linfo;
> > struct bpf_verifier_log log;
> > struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
> > - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> > + union {
> > + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> > + struct reg_id_scratch precise_ids_scratch;
>
> naming nit: "ids_scratch" or "idset_scratch" to stay in line with
> "idmap_scratch"?
Makes sense, will change to "idset_scratch".
>
> > + };
> > struct {
> > int *insn_state;
> > int *insn_stack;
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index d117deb03806..2aa60b73f1b5 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
> > }
> > }
> >
> > +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id)
> > +{
> > + u32 i;
> > +
> > + for (i = 0; i < s->count; ++i)
> > + if (s->ids[i] == id)
> > + return true;
> > +
> > + return false;
> > +}
> > +
> > +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id)
> > +{
> > + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids)))
> > + return -1;
> > + s->ids[s->count++] = id;
>
> this will allow duplicated IDs to be added? Was it done in the name of speed?
tbh, it's an artifact from bsearch/sort migration of a series.
While doing test veristat runs I found that maximal value of s->count is 5,
so looks like it would be fine the way it is now and it would be fine
if linear scan is added to avoid duplicate ids. Don't think I have a preference.
>
> > + WARN_ONCE(s->count > 64,
> > + "reg_id_scratch.count is unreasonably large (%d)", s->count);
>
> do we need this one? Especially that it's not _ONCE variant? Maybe the
> first WARN_ON_ONCE is enough?
We make an assumption that linear scans of this array are ok, and it
would be scanned often. I'd like to have some indication if this
assumption is broken. The s->ids array is large (10 regs + 64 spills) * 8 frames.
If you think that this logging is not necessary I'll remove it.
>
> > + return 0;
> > +}
> > +
> > +static inline void reg_id_scratch_reset(struct reg_id_scratch *s)
>
> we probably don't need "inline" for all these helpers?
Ok, will remove "inline".
>
> > +{
> > + s->count = 0;
> > +}
> > +
> > +/* Collect a set of IDs for all registers currently marked as precise in env->bt.
> > + * Mark all registers with these IDs as precise.
> > + */
> > +static void mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
> > +{
> > + struct reg_id_scratch *precise_ids = &env->precise_ids_scratch;
> > + struct backtrack_state *bt = &env->bt;
> > + struct bpf_func_state *func;
> > + struct bpf_reg_state *reg;
> > + DECLARE_BITMAP(mask, 64);
> > + int i, fr;
> > +
> > + reg_id_scratch_reset(precise_ids);
> > +
> > + for (fr = bt->frame; fr >= 0; fr--) {
> > + func = st->frame[fr];
> > +
> > + bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr));
> > + for_each_set_bit(i, mask, 32) {
> > + reg = &func->regs[i];
> > + if (!reg->id || reg->type != SCALAR_VALUE)
> > + continue;
> > + if (reg_id_scratch_push(precise_ids, reg->id))
> > + return;
> > + }
> > +
> > + bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
> > + for_each_set_bit(i, mask, 64) {
> > + if (i >= func->allocated_stack / BPF_REG_SIZE)
> > + break;
> > + if (!is_spilled_scalar_reg(&func->stack[i]))
> > + continue;
> > + reg = &func->stack[i].spilled_ptr;
> > + if (!reg->id || reg->type != SCALAR_VALUE)
>
> is_spilled_scalar_reg() already ensures reg->type is SCALAR_VALUE
Yes, my bad.
>
> > + continue;
> > + if (reg_id_scratch_push(precise_ids, reg->id))
> > + return;
>
> if push fails (due to overflow of id set), shouldn't we propagate
> error back and fallback to mark_all_precise?
In theory this push should never fail, as we pre-allocate enough slots
in the scratch. I'll propagate error to __mark_chain_precision() and
exit from that one with -EFAULT.
>
>
> > + }
> > + }
> > +
> > + for (fr = 0; fr <= st->curframe; ++fr) {
> > + func = st->frame[fr];
> > +
> > + for (i = BPF_REG_0; i < BPF_REG_10; ++i) {
> > + reg = &func->regs[i];
> > + if (!reg->id)
> > + continue;
> > + if (!reg_id_scratch_contains(precise_ids, reg->id))
> > + continue;
> > + bt_set_frame_reg(bt, fr, i);
> > + }
> > + for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) {
> > + if (!is_spilled_scalar_reg(&func->stack[i]))
> > + continue;
> > + reg = &func->stack[i].spilled_ptr;
> > + if (!reg->id)
> > + continue;
> > + if (!reg_id_scratch_contains(precise_ids, reg->id))
> > + continue;
> > + bt_set_frame_slot(bt, fr, i);
> > + }
> > + }
> > +}
> > +
> > /*
> > * __mark_chain_precision() backtracks BPF program instruction sequence and
> > * chain of verifier states making sure that register *regno* (if regno >= 0)
> > @@ -3910,6 +4000,30 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)
> > bt->frame, last_idx, first_idx, subseq_idx);
> > }
> >
> > + /* If some register with scalar ID is marked as precise,
> > + * make sure that all registers sharing this ID are also precise.
> > + * This is needed to estimate effect of find_equal_scalars().
> > + * Do this at the last instruction of each state,
> > + * bpf_reg_state::id fields are valid for these instructions.
> > + *
> > + * Allows to track precision in situation like below:
> > + *
> > + * r2 = unknown value
> > + * ...
> > + * --- state #0 ---
> > + * ...
> > + * r1 = r2 // r1 and r2 now share the same ID
> > + * ...
> > + * --- state #1 {r1.id = A, r2.id = A} ---
> > + * ...
> > + * if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
> > + * ...
> > + * --- state #2 {r1.id = A, r2.id = A} ---
> > + * r3 = r10
> > + * r3 += r1 // need to mark both r1 and r2
> > + */
> > + mark_precise_scalar_ids(env, st);
> > +
> > if (last_idx < 0) {
> > /* we are at the entry into subprog, which
> > * is expected for global funcs, but only if
> > diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c
> > index b8c0aae8e7ec..99272bb890da 100644
> > --- a/tools/testing/selftests/bpf/verifier/precise.c
> > +++ b/tools/testing/selftests/bpf/verifier/precise.c
> > @@ -46,7 +46,7 @@
> > mark_precise: frame0: regs=r2 stack= before 20\
> > mark_precise: frame0: parent state regs=r2 stack=:\
> > mark_precise: frame0: last_idx 19 first_idx 10\
> > - mark_precise: frame0: regs=r2 stack= before 19\
> > + mark_precise: frame0: regs=r2,r9 stack= before 19\
> > mark_precise: frame0: regs=r9 stack= before 18\
> > mark_precise: frame0: regs=r8,r9 stack= before 17\
> > mark_precise: frame0: regs=r0,r9 stack= before 15\
> > @@ -106,10 +106,10 @@
> > mark_precise: frame0: regs=r2 stack= before 22\
> > mark_precise: frame0: parent state regs=r2 stack=:\
> > mark_precise: frame0: last_idx 20 first_idx 20\
> > - mark_precise: frame0: regs=r2 stack= before 20\
> > - mark_precise: frame0: parent state regs=r2 stack=:\
> > + mark_precise: frame0: regs=r2,r9 stack= before 20\
> > + mark_precise: frame0: parent state regs=r2,r9 stack=:\
> > mark_precise: frame0: last_idx 19 first_idx 17\
> > - mark_precise: frame0: regs=r2 stack= before 19\
> > + mark_precise: frame0: regs=r2,r9 stack= before 19\
> > mark_precise: frame0: regs=r9 stack= before 18\
> > mark_precise: frame0: regs=r8,r9 stack= before 17\
> > mark_precise: frame0: parent state regs= stack=:",
> > --
> > 2.40.1
> >
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
2023-06-08 12:35 ` Eduard Zingerman
@ 2023-06-08 15:43 ` Alexei Starovoitov
2023-06-08 17:30 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Alexei Starovoitov @ 2023-06-08 15:43 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Andrii Nakryiko, bpf, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Martin KaFai Lau, Kernel Team, Yonghong Song
On Thu, Jun 8, 2023 at 5:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > Change mark_chain_precision() to track precision in situations
> > > like below:
> > >
> > > r2 = unknown value
> > > ...
> > > --- state #0 ---
> > > ...
> > > r1 = r2 // r1 and r2 now share the same ID
> > > ...
> > > --- state #1 {r1.id = A, r2.id = A} ---
> > > ...
> > > if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
> > > ...
> > > --- state #2 {r1.id = A, r2.id = A} ---
> > > r3 = r10
> > > r3 += r1 // need to mark both r1 and r2
> > >
> > > At the beginning of the processing of each state, ensure that if a
> > > register with a scalar ID is marked as precise, all registers sharing
> > > this ID are also marked as precise.
> > >
> > > This property would be used by a follow-up change in regsafe().
> > >
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > ---
> > > include/linux/bpf_verifier.h | 10 +-
> > > kernel/bpf/verifier.c | 114 ++++++++++++++++++
> > > .../testing/selftests/bpf/verifier/precise.c | 8 +-
> > > 3 files changed, 127 insertions(+), 5 deletions(-)
> > >
> > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > index ee4cc7471ed9..3f9856baa542 100644
> > > --- a/include/linux/bpf_verifier.h
> > > +++ b/include/linux/bpf_verifier.h
> > > @@ -559,6 +559,11 @@ struct backtrack_state {
> > > u64 stack_masks[MAX_CALL_FRAMES];
> > > };
> > >
> > > +struct reg_id_scratch {
> > > + u32 count;
> > > + u32 ids[BPF_ID_MAP_SIZE];
> > > +};
> > > +
> > > /* single container for all structs
> > > * one verifier_env per bpf_check() call
> > > */
> > > @@ -590,7 +595,10 @@ struct bpf_verifier_env {
> > > const struct bpf_line_info *prev_linfo;
> > > struct bpf_verifier_log log;
> > > struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
> > > - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> > > + union {
> > > + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> > > + struct reg_id_scratch precise_ids_scratch;
> >
> > naming nit: "ids_scratch" or "idset_scratch" to stay in line with
> > "idmap_scratch"?
>
> Makes sense, will change to "idset_scratch".
>
> >
> > > + };
> > > struct {
> > > int *insn_state;
> > > int *insn_stack;
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index d117deb03806..2aa60b73f1b5 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
> > > }
> > > }
> > >
> > > +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id)
> > > +{
> > > + u32 i;
> > > +
> > > + for (i = 0; i < s->count; ++i)
> > > + if (s->ids[i] == id)
> > > + return true;
> > > +
> > > + return false;
> > > +}
> > > +
> > > +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id)
> > > +{
> > > + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids)))
> > > + return -1;
> > > + s->ids[s->count++] = id;
> >
> > this will allow duplicated IDs to be added? Was it done in the name of speed?
>
> tbh, it's an artifact from bsearch/sort migration of a series.
> While doing test veristat runs I found that maximal value of s->count is 5,
> so looks like it would be fine the way it is now and it would be fine
> if linear scan is added to avoid duplicate ids. Don't think I have a preference.
Maybe return -EFAULT for count > 64 and print a verifier error message ?
If/when syzbot/human manages to craft such a program we'll know that
this is something to address.
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
2023-06-08 15:43 ` Alexei Starovoitov
@ 2023-06-08 17:30 ` Eduard Zingerman
0 siblings, 0 replies; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-08 17:30 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Andrii Nakryiko, bpf, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Martin KaFai Lau, Kernel Team, Yonghong Song
On Thu, 2023-06-08 at 08:43 -0700, Alexei Starovoitov wrote:
> On Thu, Jun 8, 2023 at 5:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> > > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > Change mark_chain_precision() to track precision in situations
> > > > like below:
> > > >
> > > > r2 = unknown value
> > > > ...
> > > > --- state #0 ---
> > > > ...
> > > > r1 = r2 // r1 and r2 now share the same ID
> > > > ...
> > > > --- state #1 {r1.id = A, r2.id = A} ---
> > > > ...
> > > > if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
> > > > ...
> > > > --- state #2 {r1.id = A, r2.id = A} ---
> > > > r3 = r10
> > > > r3 += r1 // need to mark both r1 and r2
> > > >
> > > > At the beginning of the processing of each state, ensure that if a
> > > > register with a scalar ID is marked as precise, all registers sharing
> > > > this ID are also marked as precise.
> > > >
> > > > This property would be used by a follow-up change in regsafe().
> > > >
> > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > > ---
> > > > include/linux/bpf_verifier.h | 10 +-
> > > > kernel/bpf/verifier.c | 114 ++++++++++++++++++
> > > > .../testing/selftests/bpf/verifier/precise.c | 8 +-
> > > > 3 files changed, 127 insertions(+), 5 deletions(-)
> > > >
> > > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > > index ee4cc7471ed9..3f9856baa542 100644
> > > > --- a/include/linux/bpf_verifier.h
> > > > +++ b/include/linux/bpf_verifier.h
> > > > @@ -559,6 +559,11 @@ struct backtrack_state {
> > > > u64 stack_masks[MAX_CALL_FRAMES];
> > > > };
> > > >
> > > > +struct reg_id_scratch {
> > > > + u32 count;
> > > > + u32 ids[BPF_ID_MAP_SIZE];
> > > > +};
> > > > +
> > > > /* single container for all structs
> > > > * one verifier_env per bpf_check() call
> > > > */
> > > > @@ -590,7 +595,10 @@ struct bpf_verifier_env {
> > > > const struct bpf_line_info *prev_linfo;
> > > > struct bpf_verifier_log log;
> > > > struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
> > > > - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> > > > + union {
> > > > + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> > > > + struct reg_id_scratch precise_ids_scratch;
> > >
> > > naming nit: "ids_scratch" or "idset_scratch" to stay in line with
> > > "idmap_scratch"?
> >
> > Makes sense, will change to "idset_scratch".
> >
> > >
> > > > + };
> > > > struct {
> > > > int *insn_state;
> > > > int *insn_stack;
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index d117deb03806..2aa60b73f1b5 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
> > > > }
> > > > }
> > > >
> > > > +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id)
> > > > +{
> > > > + u32 i;
> > > > +
> > > > + for (i = 0; i < s->count; ++i)
> > > > + if (s->ids[i] == id)
> > > > + return true;
> > > > +
> > > > + return false;
> > > > +}
> > > > +
> > > > +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id)
> > > > +{
> > > > + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids)))
> > > > + return -1;
> > > > + s->ids[s->count++] = id;
> > >
> > > this will allow duplicated IDs to be added? Was it done in the name of speed?
> >
> > tbh, it's an artifact from bsearch/sort migration of a series.
> > While doing test veristat runs I found that maximal value of s->count is 5,
> > so looks like it would be fine the way it is now and it would be fine
> > if linear scan is added to avoid duplicate ids. Don't think I have a preference.
>
> Maybe return -EFAULT for count > 64 and print a verifier error message ?
> If/when syzbot/human manages to craft such a program we'll know that
> this is something to address.
Sounds a bit heavy-handed.
Should the same logic apply to idmap?
I did some silly testing, 1'000'000 searches over u32 array of size (10+64)*8:
- linear search is done in 0.7s
- qsort/bsearch is done in 23s
It looks like my concerns are completely overblown. I'm inclined to
remove the size warning and just check for array overflow.
^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
2023-06-06 22:24 [PATCH bpf-next v3 0/4] verify scalar ids mapping in regsafe() Eduard Zingerman
2023-06-06 22:24 ` [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision() Eduard Zingerman
@ 2023-06-06 22:24 ` Eduard Zingerman
2023-06-07 21:40 ` Andrii Nakryiko
2023-06-06 22:24 ` [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids() Eduard Zingerman
2023-06-06 22:24 ` [PATCH bpf-next v3 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe() Eduard Zingerman
3 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-06 22:24 UTC (permalink / raw)
To: bpf, ast; +Cc: andrii, daniel, martin.lau, kernel-team, yhs, Eduard Zingerman
Check __mark_chain_precision() log to verify that scalars with same
IDs are marked as precise. Use several scenarios to test that
precision marks are propagated through:
- registers of scalar type with the same ID within one state;
- registers of scalar type with the same ID cross several states;
- registers of scalar type with the same ID cross several stack frames;
- stack slot of scalar type with the same ID;
- multiple scalar IDs are tracked independently.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
.../selftests/bpf/prog_tests/verifier.c | 2 +
.../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++
2 files changed, 326 insertions(+)
create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index 531621adef42..070a13833c3f 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -50,6 +50,7 @@
#include "verifier_regalloc.skel.h"
#include "verifier_ringbuf.skel.h"
#include "verifier_runtime_jit.skel.h"
+#include "verifier_scalar_ids.skel.h"
#include "verifier_search_pruning.skel.h"
#include "verifier_sock.skel.h"
#include "verifier_spill_fill.skel.h"
@@ -150,6 +151,7 @@ void test_verifier_ref_tracking(void) { RUN(verifier_ref_tracking); }
void test_verifier_regalloc(void) { RUN(verifier_regalloc); }
void test_verifier_ringbuf(void) { RUN(verifier_ringbuf); }
void test_verifier_runtime_jit(void) { RUN(verifier_runtime_jit); }
+void test_verifier_scalar_ids(void) { RUN(verifier_scalar_ids); }
void test_verifier_search_pruning(void) { RUN(verifier_search_pruning); }
void test_verifier_sock(void) { RUN(verifier_sock); }
void test_verifier_spill_fill(void) { RUN(verifier_spill_fill); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
new file mode 100644
index 000000000000..0f1071847490
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
@@ -0,0 +1,324 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+/* Check that precision marks propagate through scalar IDs.
+ * Registers r{0,1,2} have the same scalar ID at the moment when r0 is
+ * marked to be precise, this mark is immediately propagated to r{1,2}.
+ */
+SEC("socket")
+__success __log_level(2)
+__msg("frame0: regs=r0,r1,r2 stack= before 4: (bf) r3 = r10")
+__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
+__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
+__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
+__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void precision_same_state(void)
+{
+ asm volatile (
+ /* r0 = random number up to 0xff */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ /* tie r0.id == r1.id == r2.id */
+ "r1 = r0;"
+ "r2 = r0;"
+ /* force r0 to be precise, this immediately marks r1 and r2 as
+ * precise as well because of shared IDs
+ */
+ "r3 = r10;"
+ "r3 += r0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+/* Same as precision_same_state, but mark propagates through state /
+ * parent state boundary.
+ */
+SEC("socket")
+__success __log_level(2)
+__msg("frame0: last_idx 6 first_idx 5 subseq_idx -1")
+__msg("frame0: regs=r0,r1,r2 stack= before 5: (bf) r3 = r10")
+__msg("frame0: parent state regs=r0,r1,r2 stack=:")
+__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
+__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
+__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
+__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
+__msg("frame0: parent state regs=r0 stack=:")
+__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void precision_cross_state(void)
+{
+ asm volatile (
+ /* r0 = random number up to 0xff */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ /* tie r0.id == r1.id == r2.id */
+ "r1 = r0;"
+ "r2 = r0;"
+ /* force checkpoint */
+ "goto +0;"
+ /* force r0 to be precise, this immediately marks r1 and r2 as
+ * precise as well because of shared IDs
+ */
+ "r3 = r10;"
+ "r3 += r0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+/* Same as precision_same_state, but break one of the
+ * links, note that r1 is absent from regs=... in __msg below.
+ */
+SEC("socket")
+__success __log_level(2)
+__msg("frame0: regs=r0,r2 stack= before 5: (bf) r3 = r10")
+__msg("frame0: regs=r0,r2 stack= before 4: (b7) r1 = 0")
+__msg("frame0: regs=r0,r2 stack= before 3: (bf) r2 = r0")
+__msg("frame0: regs=r0 stack= before 2: (bf) r1 = r0")
+__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
+__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void precision_same_state_broken_link(void)
+{
+ asm volatile (
+ /* r0 = random number up to 0xff */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ /* tie r0.id == r1.id == r2.id */
+ "r1 = r0;"
+ "r2 = r0;"
+ /* break link for r1, this is the only line that differs
+ * compared to the previous test
+ */
+ "r1 = 0;"
+ /* force r0 to be precise, this immediately marks r1 and r2 as
+ * precise as well because of shared IDs
+ */
+ "r3 = r10;"
+ "r3 += r0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+/* Same as precision_same_state_broken_link, but with state /
+ * parent state boundary.
+ */
+SEC("socket")
+__success __log_level(2)
+__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10")
+__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0")
+__msg("frame0: parent state regs=r0,r2 stack=:")
+__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
+__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
+__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
+__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
+__msg("frame0: parent state regs=r0 stack=:")
+__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void precision_cross_state_broken_link(void)
+{
+ asm volatile (
+ /* r0 = random number up to 0xff */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ /* tie r0.id == r1.id == r2.id */
+ "r1 = r0;"
+ "r2 = r0;"
+ /* force checkpoint, although link between r1 and r{0,2} is
+ * broken by the next statement current precision tracking
+ * algorithm can't react to it and propagates mark for r1 to
+ * the parent state.
+ */
+ "goto +0;"
+ /* break link for r1, this is the only line that differs
+ * compared to the previous test
+ */
+ "r1 = 0;"
+ /* force r0 to be precise, this immediately marks r1 and r2 as
+ * precise as well because of shared IDs
+ */
+ "r3 = r10;"
+ "r3 += r0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+/* Check that precision marks propagate through scalar IDs.
+ * Use the same scalar ID in multiple stack frames, check that
+ * precision information is propagated up the call stack.
+ */
+SEC("socket")
+__success __log_level(2)
+/* bar frame */
+__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10")
+__msg("frame2: regs=r1 stack= before 8: (85) call pc+1")
+/* foo frame */
+__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1")
+__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1")
+__msg("frame1: regs=r1 stack= before 4: (85) call pc+1")
+/* main frame */
+__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0")
+__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
+__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void precision_many_frames(void)
+{
+ asm volatile (
+ /* r0 = random number up to 0xff */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ /* tie r0.id == r1.id == r6.id */
+ "r1 = r0;"
+ "r6 = r0;"
+ "call precision_many_frames__foo;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+static __naked __noinline __attribute__((used))
+void precision_many_frames__foo(void)
+{
+ asm volatile (
+ /* conflate one of the register numbers (r6) with outer frame,
+ * to verify that those are tracked independently
+ */
+ "r6 = r1;"
+ "r7 = r1;"
+ "call precision_many_frames__bar;"
+ "exit"
+ ::: __clobber_all);
+}
+
+static __naked __noinline __attribute__((used))
+void precision_many_frames__bar(void)
+{
+ asm volatile (
+ /* force r1 to be precise, this immediately marks:
+ * - bar frame r1
+ * - foo frame r{1,6,7}
+ * - main frame r{1,6}
+ */
+ "r2 = r10;"
+ "r2 += r1;"
+ "r0 = 0;"
+ "exit;"
+ ::: __clobber_all);
+}
+
+/* Check that scalars with the same IDs are marked precise on stack as
+ * well as in registers.
+ */
+SEC("socket")
+__success __log_level(2)
+/* foo frame */
+__msg("frame1: regs=r1 stack=-8,-16 before 9: (bf) r2 = r10")
+__msg("frame1: regs=r1 stack=-8,-16 before 8: (7b) *(u64 *)(r10 -16) = r1")
+__msg("frame1: regs=r1 stack=-8 before 7: (7b) *(u64 *)(r10 -8) = r1")
+__msg("frame1: regs=r1 stack= before 4: (85) call pc+2")
+/* main frame */
+__msg("frame0: regs=r0,r1 stack=-8 before 3: (7b) *(u64 *)(r10 -8) = r1")
+__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
+__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void precision_stack(void)
+{
+ asm volatile (
+ /* r0 = random number up to 0xff */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ /* tie r0.id == r1.id == fp[-8].id */
+ "r1 = r0;"
+ "*(u64*)(r10 - 8) = r1;"
+ "call precision_stack__foo;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+static __naked __noinline __attribute__((used))
+void precision_stack__foo(void)
+{
+ asm volatile (
+ /* conflate one of the register numbers (r6) with outer frame,
+ * to verify that those are tracked independently
+ */
+ "*(u64*)(r10 - 8) = r1;"
+ "*(u64*)(r10 - 16) = r1;"
+ /* force r1 to be precise, this immediately marks:
+ * - foo frame r1,fp{-8,-16}
+ * - main frame r1,fp{-8}
+ */
+ "r2 = r10;"
+ "r2 += r1;"
+ "exit"
+ ::: __clobber_all);
+}
+
+/* Use two separate scalar IDs to check that these are propagated
+ * independently.
+ */
+SEC("socket")
+__success __log_level(2)
+/* r{6,7} */
+__msg("11: (0f) r3 += r7")
+__msg("frame0: regs=r6,r7 stack= before 10: (bf) r3 = r10")
+/* ... skip some insns ... */
+__msg("frame0: regs=r6,r7 stack= before 3: (bf) r7 = r0")
+__msg("frame0: regs=r0,r6 stack= before 2: (bf) r6 = r0")
+/* r{8,9} */
+__msg("12: (0f) r3 += r9")
+__msg("frame0: regs=r8,r9 stack= before 11: (0f) r3 += r7")
+/* ... skip some insns ... */
+__msg("frame0: regs=r8,r9 stack= before 7: (bf) r9 = r0")
+__msg("frame0: regs=r0,r8 stack= before 6: (bf) r8 = r0")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void precision_two_ids(void)
+{
+ asm volatile (
+ /* r6 = random number up to 0xff
+ * r6.id == r7.id
+ */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ "r6 = r0;"
+ "r7 = r0;"
+ /* same, but for r{8,9} */
+ "call %[bpf_ktime_get_ns];"
+ "r0 &= 0xff;"
+ "r8 = r0;"
+ "r9 = r0;"
+ /* clear r0 id */
+ "r0 = 0;"
+ /* force checkpoint */
+ "goto +0;"
+ "r3 = r10;"
+ /* force r7 to be precise, this also marks r6 */
+ "r3 += r7;"
+ /* force r9 to be precise, this also marks r8 */
+ "r3 += r9;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
--
2.40.1
^ permalink raw reply related [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
2023-06-06 22:24 ` [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids Eduard Zingerman
@ 2023-06-07 21:40 ` Andrii Nakryiko
2023-06-08 16:17 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Andrii Nakryiko @ 2023-06-07 21:40 UTC (permalink / raw)
To: Eduard Zingerman; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Check __mark_chain_precision() log to verify that scalars with same
> IDs are marked as precise. Use several scenarios to test that
> precision marks are propagated through:
> - registers of scalar type with the same ID within one state;
> - registers of scalar type with the same ID cross several states;
> - registers of scalar type with the same ID cross several stack frames;
> - stack slot of scalar type with the same ID;
> - multiple scalar IDs are tracked independently.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
> .../selftests/bpf/prog_tests/verifier.c | 2 +
> .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++
> 2 files changed, 326 insertions(+)
> create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
>
Great set of tests! I asked for yet another one, but this could be
easily a follow up. Looks great.
Acked-by: Andrii Nakryiko <andrii@kernel.org>
[...]
> +
> +/* Same as precision_same_state_broken_link, but with state /
> + * parent state boundary.
> + */
> +SEC("socket")
> +__success __log_level(2)
> +__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10")
> +__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0")
> +__msg("frame0: parent state regs=r0,r2 stack=:")
> +__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
> +__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
> +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
> +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
> +__msg("frame0: parent state regs=r0 stack=:")
> +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
> +__flag(BPF_F_TEST_STATE_FREQ)
> +__naked void precision_cross_state_broken_link(void)
> +{
> + asm volatile (
> + /* r0 = random number up to 0xff */
> + "call %[bpf_ktime_get_ns];"
> + "r0 &= 0xff;"
> + /* tie r0.id == r1.id == r2.id */
> + "r1 = r0;"
> + "r2 = r0;"
> + /* force checkpoint, although link between r1 and r{0,2} is
> + * broken by the next statement current precision tracking
> + * algorithm can't react to it and propagates mark for r1 to
> + * the parent state.
> + */
> + "goto +0;"
> + /* break link for r1, this is the only line that differs
> + * compared to the previous test
> + */
not really the only line, goto +0 is that different line ;)
> + "r1 = 0;"
> + /* force r0 to be precise, this immediately marks r1 and r2 as
> + * precise as well because of shared IDs
> + */
> + "r3 = r10;"
> + "r3 += r0;"
> + "r0 = 0;"
> + "exit;"
> + :
> + : __imm(bpf_ktime_get_ns)
> + : __clobber_all);
> +}
> +
> +/* Check that precision marks propagate through scalar IDs.
> + * Use the same scalar ID in multiple stack frames, check that
> + * precision information is propagated up the call stack.
> + */
> +SEC("socket")
> +__success __log_level(2)
> +/* bar frame */
> +__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10")
> +__msg("frame2: regs=r1 stack= before 8: (85) call pc+1")
> +/* foo frame */
> +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1")
> +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1")
> +__msg("frame1: regs=r1 stack= before 4: (85) call pc+1")
> +/* main frame */
> +__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0")
> +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
> +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
nice test! in this case we discover r6 and r7 during instruction
backtracking. Let's add another variant of this multi-frame test with
a forced checkpoint to make sure that all this works correctly between
child/parent states with multiple active frames?
> +__flag(BPF_F_TEST_STATE_FREQ)
> +__naked void precision_many_frames(void)
> +{
> + asm volatile (
> + /* r0 = random number up to 0xff */
> + "call %[bpf_ktime_get_ns];"
> + "r0 &= 0xff;"
> + /* tie r0.id == r1.id == r6.id */
> + "r1 = r0;"
> + "r6 = r0;"
> + "call precision_many_frames__foo;"
> + "exit;"
> + :
> + : __imm(bpf_ktime_get_ns)
> + : __clobber_all);
> +}
> +
> +static __naked __noinline __attribute__((used))
nit: bpf_misc.h has __used macro defined, we can use that everywhere
> +void precision_many_frames__foo(void)
> +{
> + asm volatile (
> + /* conflate one of the register numbers (r6) with outer frame,
> + * to verify that those are tracked independently
> + */
> + "r6 = r1;"
> + "r7 = r1;"
> + "call precision_many_frames__bar;"
> + "exit"
> + ::: __clobber_all);
> +}
> +
[...]
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
2023-06-07 21:40 ` Andrii Nakryiko
@ 2023-06-08 16:17 ` Eduard Zingerman
2023-06-08 17:33 ` Andrii Nakryiko
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-08 16:17 UTC (permalink / raw)
To: Andrii Nakryiko; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > Check __mark_chain_precision() log to verify that scalars with same
> > IDs are marked as precise. Use several scenarios to test that
> > precision marks are propagated through:
> > - registers of scalar type with the same ID within one state;
> > - registers of scalar type with the same ID cross several states;
> > - registers of scalar type with the same ID cross several stack frames;
> > - stack slot of scalar type with the same ID;
> > - multiple scalar IDs are tracked independently.
> >
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> > .../selftests/bpf/prog_tests/verifier.c | 2 +
> > .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++
> > 2 files changed, 326 insertions(+)
> > create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
> >
>
> Great set of tests! I asked for yet another one, but this could be
> easily a follow up. Looks great.
Thanks.
>
> Acked-by: Andrii Nakryiko <andrii@kernel.org>
>
> [...]
>
> > +
> > +/* Same as precision_same_state_broken_link, but with state /
> > + * parent state boundary.
> > + */
> > +SEC("socket")
> > +__success __log_level(2)
> > +__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10")
> > +__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0")
> > +__msg("frame0: parent state regs=r0,r2 stack=:")
> > +__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
> > +__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
> > +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
> > +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
> > +__msg("frame0: parent state regs=r0 stack=:")
> > +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
> > +__flag(BPF_F_TEST_STATE_FREQ)
> > +__naked void precision_cross_state_broken_link(void)
> > +{
> > + asm volatile (
> > + /* r0 = random number up to 0xff */
> > + "call %[bpf_ktime_get_ns];"
> > + "r0 &= 0xff;"
> > + /* tie r0.id == r1.id == r2.id */
> > + "r1 = r0;"
> > + "r2 = r0;"
> > + /* force checkpoint, although link between r1 and r{0,2} is
> > + * broken by the next statement current precision tracking
> > + * algorithm can't react to it and propagates mark for r1 to
> > + * the parent state.
> > + */
> > + "goto +0;"
> > + /* break link for r1, this is the only line that differs
> > + * compared to the previous test
> > + */
>
> not really the only line, goto +0 is that different line ;)
My bad, the comment should be "... this is the only line that differs
compared to precision_cross_state_broken()".
>
> > + "r1 = 0;"
> > + /* force r0 to be precise, this immediately marks r1 and r2 as
> > + * precise as well because of shared IDs
> > + */
> > + "r3 = r10;"
> > + "r3 += r0;"
> > + "r0 = 0;"
> > + "exit;"
> > + :
> > + : __imm(bpf_ktime_get_ns)
> > + : __clobber_all);
> > +}
> > +
> > +/* Check that precision marks propagate through scalar IDs.
> > + * Use the same scalar ID in multiple stack frames, check that
> > + * precision information is propagated up the call stack.
> > + */
> > +SEC("socket")
> > +__success __log_level(2)
> > +/* bar frame */
> > +__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10")
> > +__msg("frame2: regs=r1 stack= before 8: (85) call pc+1")
> > +/* foo frame */
> > +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1")
> > +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1")
> > +__msg("frame1: regs=r1 stack= before 4: (85) call pc+1")
> > +/* main frame */
> > +__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0")
> > +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
> > +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
>
> nice test! in this case we discover r6 and r7 during instruction
> backtracking. Let's add another variant of this multi-frame test with
> a forced checkpoint to make sure that all this works correctly between
> child/parent states with multiple active frames?
Because of BPF_F_TEST_STATE_FREQ new state is created at each prune
point. Prune points are marked for each conditional target and
sub-program entry. I skipped a lot of log lines for brevity, here is a
bigger portion of the log:
8: (85) call pc+1
caller:
frame1: R6=scalar(id=1,...) R7=scalar(id=1,...) R10=fp0
callee:
frame2: R1=scalar(id=1,...) R10=fp0
10: (bf) r2 = r10 ; frame2: R2_w=fp0 R10=fp0
11: (0f) r2 += r1
frame2: last_idx 11 first_idx 10 subseq_idx -1 <- current state
frame2: regs=r1 stack= before 10: (bf) r2 = r10
frame2: parent state regs=r1 stack=
frame1: parent state regs=r6,r7 stack= <- (I)
frame0: parent state regs=r6 stack=
frame2: last_idx 8 first_idx 8 subseq_idx 10 <- parent state
frame2: regs=r1 stack= before 8: (85) call pc+1
frame1: parent state regs=r1,r6,r7 stack= <- (II)
frame0: parent state regs=r6 stack=
frame1: last_idx 7 first_idx 6 subseq_idx 8 <- parent state
frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1
frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1
frame1: parent state regs=r1 stack=
frame0: parent state regs=r6 stack=
frame1: last_idx 4 first_idx 4 subseq_idx 6 <- parent state
frame1: regs=r1 stack= before 4: (85) call pc+1
frame0: parent state regs=r1,r6 stack=
frame0: last_idx 3 first_idx 1 subseq_idx 4 <- parent state
frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0
frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0
frame0: regs=r0 stack= before 1: (57) r0 &= 255
At (I) frame1.r{6,7} are marked because mark_precise_scalar_ids()
looks for all registers with frame2.r1.id in the current state.
At (II) frame1.r1 is marked because of backtracking of call instruction.
It looks like both baсktracking and cross-state propagation are tested.
Maybe I miss-understand your comment.
>
> > +__flag(BPF_F_TEST_STATE_FREQ)
> > +__naked void precision_many_frames(void)
> > +{
> > + asm volatile (
> > + /* r0 = random number up to 0xff */
> > + "call %[bpf_ktime_get_ns];"
> > + "r0 &= 0xff;"
> > + /* tie r0.id == r1.id == r6.id */
> > + "r1 = r0;"
> > + "r6 = r0;"
> > + "call precision_many_frames__foo;"
> > + "exit;"
> > + :
> > + : __imm(bpf_ktime_get_ns)
> > + : __clobber_all);
> > +}
> > +
> > +static __naked __noinline __attribute__((used))
>
> nit: bpf_misc.h has __used macro defined, we can use that everywhere
>
> > +void precision_many_frames__foo(void)
> > +{
> > + asm volatile (
> > + /* conflate one of the register numbers (r6) with outer frame,
> > + * to verify that those are tracked independently
> > + */
> > + "r6 = r1;"
> > + "r7 = r1;"
> > + "call precision_many_frames__bar;"
> > + "exit"
> > + ::: __clobber_all);
> > +}
> > +
>
> [...]
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
2023-06-08 16:17 ` Eduard Zingerman
@ 2023-06-08 17:33 ` Andrii Nakryiko
2023-06-08 17:35 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Andrii Nakryiko @ 2023-06-08 17:33 UTC (permalink / raw)
To: Eduard Zingerman; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Thu, Jun 8, 2023 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > Check __mark_chain_precision() log to verify that scalars with same
> > > IDs are marked as precise. Use several scenarios to test that
> > > precision marks are propagated through:
> > > - registers of scalar type with the same ID within one state;
> > > - registers of scalar type with the same ID cross several states;
> > > - registers of scalar type with the same ID cross several stack frames;
> > > - stack slot of scalar type with the same ID;
> > > - multiple scalar IDs are tracked independently.
> > >
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > ---
> > > .../selftests/bpf/prog_tests/verifier.c | 2 +
> > > .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++
> > > 2 files changed, 326 insertions(+)
> > > create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
> > >
> >
> > Great set of tests! I asked for yet another one, but this could be
> > easily a follow up. Looks great.
>
> Thanks.
>
> >
> > Acked-by: Andrii Nakryiko <andrii@kernel.org>
> >
> > [...]
> >
> > > +
> > > +/* Same as precision_same_state_broken_link, but with state /
> > > + * parent state boundary.
> > > + */
> > > +SEC("socket")
> > > +__success __log_level(2)
> > > +__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10")
> > > +__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0")
> > > +__msg("frame0: parent state regs=r0,r2 stack=:")
> > > +__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
> > > +__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
> > > +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
> > > +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
> > > +__msg("frame0: parent state regs=r0 stack=:")
> > > +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
> > > +__flag(BPF_F_TEST_STATE_FREQ)
> > > +__naked void precision_cross_state_broken_link(void)
> > > +{
> > > + asm volatile (
> > > + /* r0 = random number up to 0xff */
> > > + "call %[bpf_ktime_get_ns];"
> > > + "r0 &= 0xff;"
> > > + /* tie r0.id == r1.id == r2.id */
> > > + "r1 = r0;"
> > > + "r2 = r0;"
> > > + /* force checkpoint, although link between r1 and r{0,2} is
> > > + * broken by the next statement current precision tracking
> > > + * algorithm can't react to it and propagates mark for r1 to
> > > + * the parent state.
> > > + */
> > > + "goto +0;"
> > > + /* break link for r1, this is the only line that differs
> > > + * compared to the previous test
> > > + */
> >
> > not really the only line, goto +0 is that different line ;)
>
> My bad, the comment should be "... this is the only line that differs
> compared to precision_cross_state_broken()".
>
> >
> > > + "r1 = 0;"
> > > + /* force r0 to be precise, this immediately marks r1 and r2 as
> > > + * precise as well because of shared IDs
> > > + */
> > > + "r3 = r10;"
> > > + "r3 += r0;"
> > > + "r0 = 0;"
> > > + "exit;"
> > > + :
> > > + : __imm(bpf_ktime_get_ns)
> > > + : __clobber_all);
> > > +}
> > > +
> > > +/* Check that precision marks propagate through scalar IDs.
> > > + * Use the same scalar ID in multiple stack frames, check that
> > > + * precision information is propagated up the call stack.
> > > + */
> > > +SEC("socket")
> > > +__success __log_level(2)
> > > +/* bar frame */
> > > +__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10")
> > > +__msg("frame2: regs=r1 stack= before 8: (85) call pc+1")
> > > +/* foo frame */
> > > +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1")
> > > +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1")
> > > +__msg("frame1: regs=r1 stack= before 4: (85) call pc+1")
> > > +/* main frame */
> > > +__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0")
> > > +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
> > > +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
> >
> > nice test! in this case we discover r6 and r7 during instruction
> > backtracking. Let's add another variant of this multi-frame test with
> > a forced checkpoint to make sure that all this works correctly between
> > child/parent states with multiple active frames?
>
> Because of BPF_F_TEST_STATE_FREQ new state is created at each prune
> point. Prune points are marked for each conditional target and
> sub-program entry. I skipped a lot of log lines for brevity, here is a
> bigger portion of the log:
>
> 8: (85) call pc+1
> caller:
> frame1: R6=scalar(id=1,...) R7=scalar(id=1,...) R10=fp0
> callee:
> frame2: R1=scalar(id=1,...) R10=fp0
> 10: (bf) r2 = r10 ; frame2: R2_w=fp0 R10=fp0
> 11: (0f) r2 += r1
> frame2: last_idx 11 first_idx 10 subseq_idx -1 <- current state
> frame2: regs=r1 stack= before 10: (bf) r2 = r10
> frame2: parent state regs=r1 stack=
> frame1: parent state regs=r6,r7 stack= <- (I)
> frame0: parent state regs=r6 stack=
>
> frame2: last_idx 8 first_idx 8 subseq_idx 10 <- parent state
> frame2: regs=r1 stack= before 8: (85) call pc+1
> frame1: parent state regs=r1,r6,r7 stack= <- (II)
> frame0: parent state regs=r6 stack=
>
> frame1: last_idx 7 first_idx 6 subseq_idx 8 <- parent state
> frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1
> frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1
> frame1: parent state regs=r1 stack=
> frame0: parent state regs=r6 stack=
>
> frame1: last_idx 4 first_idx 4 subseq_idx 6 <- parent state
> frame1: regs=r1 stack= before 4: (85) call pc+1
> frame0: parent state regs=r1,r6 stack=
>
> frame0: last_idx 3 first_idx 1 subseq_idx 4 <- parent state
> frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0
> frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0
> frame0: regs=r0 stack= before 1: (57) r0 &= 255
>
> At (I) frame1.r{6,7} are marked because mark_precise_scalar_ids()
> looks for all registers with frame2.r1.id in the current state.
> At (II) frame1.r1 is marked because of backtracking of call instruction.
> It looks like both baсktracking and cross-state propagation are tested.
> Maybe I miss-understand your comment.
>
From the set of __msg() tests it's not obvious that (I) is happening.
So just maybe let's messages like below:
__msg("frame1: parent state regs=r6,r7 stack=")
to make it more explicit?
Either way, it's minor. You are right about checkpoint after each
helper call and subprog call.
> >
> > > +__flag(BPF_F_TEST_STATE_FREQ)
> > > +__naked void precision_many_frames(void)
> > > +{
> > > + asm volatile (
> > > + /* r0 = random number up to 0xff */
> > > + "call %[bpf_ktime_get_ns];"
> > > + "r0 &= 0xff;"
> > > + /* tie r0.id == r1.id == r6.id */
> > > + "r1 = r0;"
> > > + "r6 = r0;"
> > > + "call precision_many_frames__foo;"
> > > + "exit;"
> > > + :
> > > + : __imm(bpf_ktime_get_ns)
> > > + : __clobber_all);
> > > +}
> > > +
> > > +static __naked __noinline __attribute__((used))
> >
> > nit: bpf_misc.h has __used macro defined, we can use that everywhere
> >
> > > +void precision_many_frames__foo(void)
> > > +{
> > > + asm volatile (
> > > + /* conflate one of the register numbers (r6) with outer frame,
> > > + * to verify that those are tracked independently
> > > + */
> > > + "r6 = r1;"
> > > + "r7 = r1;"
> > > + "call precision_many_frames__bar;"
> > > + "exit"
> > > + ::: __clobber_all);
> > > +}
> > > +
> >
> > [...]
>
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
2023-06-08 17:33 ` Andrii Nakryiko
@ 2023-06-08 17:35 ` Eduard Zingerman
0 siblings, 0 replies; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-08 17:35 UTC (permalink / raw)
To: Andrii Nakryiko; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Thu, 2023-06-08 at 10:33 -0700, Andrii Nakryiko wrote:
> On Thu, Jun 8, 2023 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> > > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > Check __mark_chain_precision() log to verify that scalars with same
> > > > IDs are marked as precise. Use several scenarios to test that
> > > > precision marks are propagated through:
> > > > - registers of scalar type with the same ID within one state;
> > > > - registers of scalar type with the same ID cross several states;
> > > > - registers of scalar type with the same ID cross several stack frames;
> > > > - stack slot of scalar type with the same ID;
> > > > - multiple scalar IDs are tracked independently.
> > > >
> > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > > ---
> > > > .../selftests/bpf/prog_tests/verifier.c | 2 +
> > > > .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++
> > > > 2 files changed, 326 insertions(+)
> > > > create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
> > > >
> > >
> > > Great set of tests! I asked for yet another one, but this could be
> > > easily a follow up. Looks great.
> >
> > Thanks.
> >
> > >
> > > Acked-by: Andrii Nakryiko <andrii@kernel.org>
> > >
> > > [...]
> > >
> > > > +
> > > > +/* Same as precision_same_state_broken_link, but with state /
> > > > + * parent state boundary.
> > > > + */
> > > > +SEC("socket")
> > > > +__success __log_level(2)
> > > > +__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10")
> > > > +__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0")
> > > > +__msg("frame0: parent state regs=r0,r2 stack=:")
> > > > +__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0")
> > > > +__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0")
> > > > +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
> > > > +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
> > > > +__msg("frame0: parent state regs=r0 stack=:")
> > > > +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns")
> > > > +__flag(BPF_F_TEST_STATE_FREQ)
> > > > +__naked void precision_cross_state_broken_link(void)
> > > > +{
> > > > + asm volatile (
> > > > + /* r0 = random number up to 0xff */
> > > > + "call %[bpf_ktime_get_ns];"
> > > > + "r0 &= 0xff;"
> > > > + /* tie r0.id == r1.id == r2.id */
> > > > + "r1 = r0;"
> > > > + "r2 = r0;"
> > > > + /* force checkpoint, although link between r1 and r{0,2} is
> > > > + * broken by the next statement current precision tracking
> > > > + * algorithm can't react to it and propagates mark for r1 to
> > > > + * the parent state.
> > > > + */
> > > > + "goto +0;"
> > > > + /* break link for r1, this is the only line that differs
> > > > + * compared to the previous test
> > > > + */
> > >
> > > not really the only line, goto +0 is that different line ;)
> >
> > My bad, the comment should be "... this is the only line that differs
> > compared to precision_cross_state_broken()".
> >
> > >
> > > > + "r1 = 0;"
> > > > + /* force r0 to be precise, this immediately marks r1 and r2 as
> > > > + * precise as well because of shared IDs
> > > > + */
> > > > + "r3 = r10;"
> > > > + "r3 += r0;"
> > > > + "r0 = 0;"
> > > > + "exit;"
> > > > + :
> > > > + : __imm(bpf_ktime_get_ns)
> > > > + : __clobber_all);
> > > > +}
> > > > +
> > > > +/* Check that precision marks propagate through scalar IDs.
> > > > + * Use the same scalar ID in multiple stack frames, check that
> > > > + * precision information is propagated up the call stack.
> > > > + */
> > > > +SEC("socket")
> > > > +__success __log_level(2)
> > > > +/* bar frame */
> > > > +__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10")
> > > > +__msg("frame2: regs=r1 stack= before 8: (85) call pc+1")
> > > > +/* foo frame */
> > > > +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1")
> > > > +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1")
> > > > +__msg("frame1: regs=r1 stack= before 4: (85) call pc+1")
> > > > +/* main frame */
> > > > +__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0")
> > > > +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0")
> > > > +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255")
> > >
> > > nice test! in this case we discover r6 and r7 during instruction
> > > backtracking. Let's add another variant of this multi-frame test with
> > > a forced checkpoint to make sure that all this works correctly between
> > > child/parent states with multiple active frames?
> >
> > Because of BPF_F_TEST_STATE_FREQ new state is created at each prune
> > point. Prune points are marked for each conditional target and
> > sub-program entry. I skipped a lot of log lines for brevity, here is a
> > bigger portion of the log:
> >
> > 8: (85) call pc+1
> > caller:
> > frame1: R6=scalar(id=1,...) R7=scalar(id=1,...) R10=fp0
> > callee:
> > frame2: R1=scalar(id=1,...) R10=fp0
> > 10: (bf) r2 = r10 ; frame2: R2_w=fp0 R10=fp0
> > 11: (0f) r2 += r1
> > frame2: last_idx 11 first_idx 10 subseq_idx -1 <- current state
> > frame2: regs=r1 stack= before 10: (bf) r2 = r10
> > frame2: parent state regs=r1 stack=
> > frame1: parent state regs=r6,r7 stack= <- (I)
> > frame0: parent state regs=r6 stack=
> >
> > frame2: last_idx 8 first_idx 8 subseq_idx 10 <- parent state
> > frame2: regs=r1 stack= before 8: (85) call pc+1
> > frame1: parent state regs=r1,r6,r7 stack= <- (II)
> > frame0: parent state regs=r6 stack=
> >
> > frame1: last_idx 7 first_idx 6 subseq_idx 8 <- parent state
> > frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1
> > frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1
> > frame1: parent state regs=r1 stack=
> > frame0: parent state regs=r6 stack=
> >
> > frame1: last_idx 4 first_idx 4 subseq_idx 6 <- parent state
> > frame1: regs=r1 stack= before 4: (85) call pc+1
> > frame0: parent state regs=r1,r6 stack=
> >
> > frame0: last_idx 3 first_idx 1 subseq_idx 4 <- parent state
> > frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0
> > frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0
> > frame0: regs=r0 stack= before 1: (57) r0 &= 255
> >
> > At (I) frame1.r{6,7} are marked because mark_precise_scalar_ids()
> > looks for all registers with frame2.r1.id in the current state.
> > At (II) frame1.r1 is marked because of backtracking of call instruction.
> > It looks like both baсktracking and cross-state propagation are tested.
> > Maybe I miss-understand your comment.
> >
>
> From the set of __msg() tests it's not obvious that (I) is happening.
> So just maybe let's messages like below:
>
> __msg("frame1: parent state regs=r6,r7 stack=")
>
> to make it more explicit?
Yes good point,
I'll add a few __msg lines and a comment to make this thing clear.
>
> Either way, it's minor. You are right about checkpoint after each
> helper call and subprog call.
>
>
> > >
> > > > +__flag(BPF_F_TEST_STATE_FREQ)
> > > > +__naked void precision_many_frames(void)
> > > > +{
> > > > + asm volatile (
> > > > + /* r0 = random number up to 0xff */
> > > > + "call %[bpf_ktime_get_ns];"
> > > > + "r0 &= 0xff;"
> > > > + /* tie r0.id == r1.id == r6.id */
> > > > + "r1 = r0;"
> > > > + "r6 = r0;"
> > > > + "call precision_many_frames__foo;"
> > > > + "exit;"
> > > > + :
> > > > + : __imm(bpf_ktime_get_ns)
> > > > + : __clobber_all);
> > > > +}
> > > > +
> > > > +static __naked __noinline __attribute__((used))
> > >
> > > nit: bpf_misc.h has __used macro defined, we can use that everywhere
> > >
> > > > +void precision_many_frames__foo(void)
> > > > +{
> > > > + asm volatile (
> > > > + /* conflate one of the register numbers (r6) with outer frame,
> > > > + * to verify that those are tracked independently
> > > > + */
> > > > + "r6 = r1;"
> > > > + "r7 = r1;"
> > > > + "call precision_many_frames__bar;"
> > > > + "exit"
> > > > + ::: __clobber_all);
> > > > +}
> > > > +
> > >
> > > [...]
> >
^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
2023-06-06 22:24 [PATCH bpf-next v3 0/4] verify scalar ids mapping in regsafe() Eduard Zingerman
2023-06-06 22:24 ` [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision() Eduard Zingerman
2023-06-06 22:24 ` [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids Eduard Zingerman
@ 2023-06-06 22:24 ` Eduard Zingerman
2023-06-07 21:40 ` Andrii Nakryiko
2023-06-06 22:24 ` [PATCH bpf-next v3 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe() Eduard Zingerman
3 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-06 22:24 UTC (permalink / raw)
To: bpf, ast; +Cc: andrii, daniel, martin.lau, kernel-team, yhs, Eduard Zingerman
Make sure that the following unsafe example is rejected by verifier:
1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...
--- checkpoint ---
7: r9 += r7
8: *(u64 *)r9 = Y
This example is unsafe because not all execution paths verify r7 range.
Because of the jump at (4) the verifier would arrive at (6) in two states:
I. r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
Currently regsafe() does not call check_ids() for scalar registers,
thus from POV of regsafe() states (I) and (II) are identical. If the
path 1-6 is taken by verifier first, and checkpoint is created at (6)
the path [1-4, 6] would be considered safe.
This commit updates regsafe() to call check_ids() for precise scalar
registers.
To minimize the impact on verification performance, avoid generating
bpf_reg_state::id for constant scalar values when processing BPF_MOV
in check_alu_op(). Scalar IDs are utilized by find_equal_scalars() to
propagate information about value ranges for registers that hold the
same value. However, there is no need to propagate range information
for constants.
Still, there is some performance impact because of this change.
Using veristat to compare number of processed states for selftests
object files listed in tools/testing/selftests/bpf/veristat.cfg and
Cilium object files from [1] gives the following statistics:
$ ./veristat -e file,prog,states -f "states_pct>10" \
-C master-baseline.log current.log
File Program States (DIFF)
----------- ------------------------------ --------------
bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%)
bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%)
bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%)
loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)
Also test case verifier_search_pruning/allocated_stack has to be
updated to avoid conflicts in register ID assignments between cached
and new states.
[1] git@github.com:anakryiko/cilium.git
Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 34 ++++++++++++++++---
.../bpf/progs/verifier_search_pruning.c | 3 +-
2 files changed, 32 insertions(+), 5 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2aa60b73f1b5..175ca22b868e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
if (BPF_SRC(insn->code) == BPF_X) {
struct bpf_reg_state *src_reg = regs + insn->src_reg;
struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
+ bool need_id = (src_reg->type == SCALAR_VALUE && !src_reg->id &&
+ !tnum_is_const(src_reg->var_off));
if (BPF_CLASS(insn->code) == BPF_ALU64) {
/* case: R1 = R2
* copy register state to dest reg
*/
- if (src_reg->type == SCALAR_VALUE && !src_reg->id)
+ if (need_id)
/* Assign src and dst registers the same ID
* that will be used by find_equal_scalars()
* to propagate min/max range.
@@ -12957,7 +12959,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
} else if (src_reg->type == SCALAR_VALUE) {
bool is_src_reg_u32 = src_reg->umax_value <= U32_MAX;
- if (is_src_reg_u32 && !src_reg->id)
+ if (is_src_reg_u32 && need_id)
src_reg->id = ++env->id_gen;
copy_register_state(dst_reg, src_reg);
/* Make sure ID is cleared if src_reg is not in u32 range otherwise
@@ -15289,9 +15291,33 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
return false;
if (!rold->precise)
return true;
- /* new val must satisfy old val knowledge */
+ /* Why check_ids() for scalar registers?
+ *
+ * Consider the following BPF code:
+ * 1: r6 = ... unbound scalar, ID=a ...
+ * 2: r7 = ... unbound scalar, ID=b ...
+ * 3: if (r6 > r7) goto +1
+ * 4: r6 = r7
+ * 5: if (r6 > X) goto ...
+ * 6: ... memory operation using r7 ...
+ *
+ * First verification path is [1-6]:
+ * - at (4) same bpf_reg_state::id (b) would be assigned to r6 and r7;
+ * - at (5) r6 would be marked <= X, find_equal_scalars() would also mark
+ * r7 <= X, because r6 and r7 share same id.
+ * Next verification path is [1-4, 6].
+ *
+ * Instruction (6) would be reached in two states:
+ * I. r6{.id=b}, r7{.id=b} via path 1-6;
+ * II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
+ *
+ * Use check_ids() to distinguish these states.
+ * ---
+ * Also verify that new value satisfies old value range knowledge.
+ */
return range_within(rold, rcur) &&
- tnum_in(rold->var_off, rcur->var_off);
+ tnum_in(rold->var_off, rcur->var_off) &&
+ check_ids(rold->id, rcur->id, idmap);
case PTR_TO_MAP_KEY:
case PTR_TO_MAP_VALUE:
case PTR_TO_MEM:
diff --git a/tools/testing/selftests/bpf/progs/verifier_search_pruning.c b/tools/testing/selftests/bpf/progs/verifier_search_pruning.c
index 5a14498d352f..bb3cd14bb3a1 100644
--- a/tools/testing/selftests/bpf/progs/verifier_search_pruning.c
+++ b/tools/testing/selftests/bpf/progs/verifier_search_pruning.c
@@ -271,7 +271,7 @@ l2_%=: r0 = 0; \
SEC("socket")
__description("allocated_stack")
-__success __msg("processed 15 insns")
+__success __msg("processed 16 insns")
__success_unpriv __msg_unpriv("") __log_level(1) __retval(0)
__naked void allocated_stack(void)
{
@@ -279,6 +279,7 @@ __naked void allocated_stack(void)
r6 = r1; \
call %[bpf_get_prandom_u32]; \
r7 = r0; \
+ call %[bpf_get_prandom_u32]; \
if r0 == 0 goto l0_%=; \
r0 = 0; \
*(u64*)(r10 - 8) = r6; \
--
2.40.1
^ permalink raw reply related [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
2023-06-06 22:24 ` [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids() Eduard Zingerman
@ 2023-06-07 21:40 ` Andrii Nakryiko
2023-06-08 1:26 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Andrii Nakryiko @ 2023-06-07 21:40 UTC (permalink / raw)
To: Eduard Zingerman; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Make sure that the following unsafe example is rejected by verifier:
>
> 1: r9 = ... some pointer with range X ...
> 2: r6 = ... unbound scalar ID=a ...
> 3: r7 = ... unbound scalar ID=b ...
> 4: if (r6 > r7) goto +1
> 5: r6 = r7
> 6: if (r6 > X) goto ...
> --- checkpoint ---
> 7: r9 += r7
> 8: *(u64 *)r9 = Y
>
> This example is unsafe because not all execution paths verify r7 range.
> Because of the jump at (4) the verifier would arrive at (6) in two states:
> I. r6{.id=b}, r7{.id=b} via path 1-6;
> II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
>
> Currently regsafe() does not call check_ids() for scalar registers,
> thus from POV of regsafe() states (I) and (II) are identical. If the
> path 1-6 is taken by verifier first, and checkpoint is created at (6)
> the path [1-4, 6] would be considered safe.
>
> This commit updates regsafe() to call check_ids() for precise scalar
> registers.
>
> To minimize the impact on verification performance, avoid generating
> bpf_reg_state::id for constant scalar values when processing BPF_MOV
> in check_alu_op(). Scalar IDs are utilized by find_equal_scalars() to
> propagate information about value ranges for registers that hold the
> same value. However, there is no need to propagate range information
> for constants.
>
> Still, there is some performance impact because of this change.
> Using veristat to compare number of processed states for selftests
> object files listed in tools/testing/selftests/bpf/veristat.cfg and
> Cilium object files from [1] gives the following statistics:
>
> $ ./veristat -e file,prog,states -f "states_pct>10" \
> -C master-baseline.log current.log
> File Program States (DIFF)
> ----------- ------------------------------ --------------
> bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%)
> bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%)
> bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%)
> loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)
>
> Also test case verifier_search_pruning/allocated_stack has to be
> updated to avoid conflicts in register ID assignments between cached
> and new states.
>
> [1] git@github.com:anakryiko/cilium.git
>
> Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
So I checked it also on our internal BPF object files, and it looks
mostly good. Here are the only regressions:
Program States (A) States (B)
States (DIFF)
---------------------------------------- ---------- ----------
---------------
balancer_ingress 29219 34531
+5312 (+18.18%)
syar_bind6_protect6 3257 3599
+342 (+10.50%)
syar_bind4_protect4 2590 2931
+341 (+13.17%)
on_alloc 415 526
+111 (+26.75%)
on_free 406 517
+111 (+27.34%)
pycallcount 395 506
+111 (+28.10%)
resume_context 405 516
+111 (+27.41%)
on_py_event 395 506
+111 (+28.10%)
on_event 284 394
+110 (+38.73%)
handle_cuda_event 268 378
+110 (+41.04%)
handle_cuda_launch 276 386
+110 (+39.86%)
handle_cuda_malloc_ret 272 382
+110 (+40.44%)
handle_cuda_memcpy 270 380
+110 (+40.74%)
handle_cuda_memcpy_async 270 380
+110 (+40.74%)
handle_pytorch_allocate_ret 271 381
+110 (+40.59%)
handle_pytorch_malloc_ret 272 382
+110 (+40.44%)
on_event 284 394
+110 (+38.73%)
on_event 284 394
+110 (+38.73%)
syar_task_enter_execve 309 329
+20 (+6.47%)
kprobe__security_inode_link 968 986
+18 (+1.86%)
kprobe__security_inode_symlink 838 854
+16 (+1.91%)
tw_twfw_egress 249 251
+2 (+0.80%)
tw_twfw_ingress 250 252
+2 (+0.80%)
tw_twfw_tc_eg 248 250
+2 (+0.81%)
tw_twfw_tc_in 250 252
+2 (+0.80%)
raw_tracepoint__sched_process_exec 136 139
+3 (+2.21%)
kprobe_ret__do_filp_open 869 871
+2 (+0.23%)
read_erlang_stack 572 573
+1 (+0.17%)
They are mostly on small-ish programs. The only mild concern from my
side is balancer_ingress, which is one of Katran BPF programs. It add
+18% of states (which translates to about 70K more instructions
verified, up from 350K). I think we can live with this, but would be
nice to check why it's happening.
I suspect that dropping SCALAR IDs as we discussed (after fixing
register fill/spill ID generation) might completely mitigate that.
Overall, LGTM:
Acked-by: Andrii Nakryiko <andrii@kernel.org>
> kernel/bpf/verifier.c | 34 ++++++++++++++++---
> .../bpf/progs/verifier_search_pruning.c | 3 +-
> 2 files changed, 32 insertions(+), 5 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 2aa60b73f1b5..175ca22b868e 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
> if (BPF_SRC(insn->code) == BPF_X) {
> struct bpf_reg_state *src_reg = regs + insn->src_reg;
> struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
> + bool need_id = (src_reg->type == SCALAR_VALUE && !src_reg->id &&
> + !tnum_is_const(src_reg->var_off));
>
nit: unnecessary outer ()
> if (BPF_CLASS(insn->code) == BPF_ALU64) {
> /* case: R1 = R2
> * copy register state to dest reg
> */
> - if (src_reg->type == SCALAR_VALUE && !src_reg->id)
> + if (need_id)
> /* Assign src and dst registers the same ID
> * that will be used by find_equal_scalars()
> * to propagate min/max range.
[...]
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
2023-06-07 21:40 ` Andrii Nakryiko
@ 2023-06-08 1:26 ` Eduard Zingerman
2023-06-08 17:21 ` Andrii Nakryiko
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-08 1:26 UTC (permalink / raw)
To: Andrii Nakryiko; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > Make sure that the following unsafe example is rejected by verifier:
> >
> > 1: r9 = ... some pointer with range X ...
> > 2: r6 = ... unbound scalar ID=a ...
> > 3: r7 = ... unbound scalar ID=b ...
> > 4: if (r6 > r7) goto +1
> > 5: r6 = r7
> > 6: if (r6 > X) goto ...
> > --- checkpoint ---
> > 7: r9 += r7
> > 8: *(u64 *)r9 = Y
> >
> > This example is unsafe because not all execution paths verify r7 range.
> > Because of the jump at (4) the verifier would arrive at (6) in two states:
> > I. r6{.id=b}, r7{.id=b} via path 1-6;
> > II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
> >
> > Currently regsafe() does not call check_ids() for scalar registers,
> > thus from POV of regsafe() states (I) and (II) are identical. If the
> > path 1-6 is taken by verifier first, and checkpoint is created at (6)
> > the path [1-4, 6] would be considered safe.
> >
> > This commit updates regsafe() to call check_ids() for precise scalar
> > registers.
> >
> > To minimize the impact on verification performance, avoid generating
> > bpf_reg_state::id for constant scalar values when processing BPF_MOV
> > in check_alu_op(). Scalar IDs are utilized by find_equal_scalars() to
> > propagate information about value ranges for registers that hold the
> > same value. However, there is no need to propagate range information
> > for constants.
> >
> > Still, there is some performance impact because of this change.
> > Using veristat to compare number of processed states for selftests
> > object files listed in tools/testing/selftests/bpf/veristat.cfg and
> > Cilium object files from [1] gives the following statistics:
> >
> > $ ./veristat -e file,prog,states -f "states_pct>10" \
> > -C master-baseline.log current.log
> > File Program States (DIFF)
> > ----------- ------------------------------ --------------
> > bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%)
> > bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%)
> > bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%)
> > loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)
> >
> > Also test case verifier_search_pruning/allocated_stack has to be
> > updated to avoid conflicts in register ID assignments between cached
> > and new states.
> >
> > [1] git@github.com:anakryiko/cilium.git
> >
> > Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
>
> So I checked it also on our internal BPF object files, and it looks
> mostly good. Here are the only regressions:
>
> Program States (A) States (B)
> States (DIFF)
> ---------------------------------------- ---------- ----------
> ---------------
> balancer_ingress 29219 34531
> +5312 (+18.18%)
> syar_bind6_protect6 3257 3599
> +342 (+10.50%)
> syar_bind4_protect4 2590 2931
> +341 (+13.17%)
> on_alloc 415 526
> +111 (+26.75%)
> on_free 406 517
> +111 (+27.34%)
> pycallcount 395 506
> +111 (+28.10%)
> resume_context 405 516
> +111 (+27.41%)
> on_py_event 395 506
> +111 (+28.10%)
> on_event 284 394
> +110 (+38.73%)
> handle_cuda_event 268 378
> +110 (+41.04%)
> handle_cuda_launch 276 386
> +110 (+39.86%)
> handle_cuda_malloc_ret 272 382
> +110 (+40.44%)
> handle_cuda_memcpy 270 380
> +110 (+40.74%)
> handle_cuda_memcpy_async 270 380
> +110 (+40.74%)
> handle_pytorch_allocate_ret 271 381
> +110 (+40.59%)
> handle_pytorch_malloc_ret 272 382
> +110 (+40.44%)
> on_event 284 394
> +110 (+38.73%)
> on_event 284 394
> +110 (+38.73%)
> syar_task_enter_execve 309 329
> +20 (+6.47%)
> kprobe__security_inode_link 968 986
> +18 (+1.86%)
> kprobe__security_inode_symlink 838 854
> +16 (+1.91%)
> tw_twfw_egress 249 251
> +2 (+0.80%)
> tw_twfw_ingress 250 252
> +2 (+0.80%)
> tw_twfw_tc_eg 248 250
> +2 (+0.81%)
> tw_twfw_tc_in 250 252
> +2 (+0.80%)
> raw_tracepoint__sched_process_exec 136 139
> +3 (+2.21%)
> kprobe_ret__do_filp_open 869 871
> +2 (+0.23%)
> read_erlang_stack 572 573
> +1 (+0.17%)
>
>
> They are mostly on small-ish programs. The only mild concern from my
> side is balancer_ingress, which is one of Katran BPF programs. It add
> +18% of states (which translates to about 70K more instructions
> verified, up from 350K). I think we can live with this, but would be
> nice to check why it's happening.
Thank you for reviewing this series.
I looked at the logs that you've shared, the difference is indeed
caused by some scalar registers having a unique ID in cached state and
no ID in current state or vice versa. The !rold->id trick that we
discussed for V2 helps :)
What do you think about an alternative way to exclude unique scalars
as in the patch below? (on top of this patch-set):
--- 8< -------------------------
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 235d7eded565..ece9722dff3b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15149,6 +15149,13 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
return false;
}
+static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_verifier_env *env)
+{
+ old_id = old_id ? old_id : env->id_gen++;
+ cur_id = cur_id ? cur_id : env->id_gen++;
+ return check_ids(old_id, cur_id, env->idmap_scratch);
+}
+
static void clean_func_state(struct bpf_verifier_env *env,
struct bpf_func_state *st)
{
@@ -15325,7 +15332,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
*/
return range_within(rold, rcur) &&
tnum_in(rold->var_off, rcur->var_off) &&
- check_ids(rold->id, rcur->id, idmap);
+ check_scalar_ids(rold->id, rcur->id, env);
case PTR_TO_MAP_KEY:
case PTR_TO_MAP_VALUE:
case PTR_TO_MEM:
------------------------- >8 ---
For me this patch removes all veristat differences compared to the
master. If doing it for real, I'd like to reset env->id_gen at exit
from states_equal() to the value it had at entry (to avoid allocating
too many ids).
>
> I suspect that dropping SCALAR IDs as we discussed (after fixing
> register fill/spill ID generation) might completely mitigate that.
>
> Overall, LGTM:
>
> Acked-by: Andrii Nakryiko <andrii@kernel.org>
>
> > kernel/bpf/verifier.c | 34 ++++++++++++++++---
> > .../bpf/progs/verifier_search_pruning.c | 3 +-
> > 2 files changed, 32 insertions(+), 5 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 2aa60b73f1b5..175ca22b868e 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > if (BPF_SRC(insn->code) == BPF_X) {
> > struct bpf_reg_state *src_reg = regs + insn->src_reg;
> > struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
> > + bool need_id = (src_reg->type == SCALAR_VALUE && !src_reg->id &&
> > + !tnum_is_const(src_reg->var_off));
> >
>
> nit: unnecessary outer ()
>
> > if (BPF_CLASS(insn->code) == BPF_ALU64) {
> > /* case: R1 = R2
> > * copy register state to dest reg
> > */
> > - if (src_reg->type == SCALAR_VALUE && !src_reg->id)
> > + if (need_id)
> > /* Assign src and dst registers the same ID
> > * that will be used by find_equal_scalars()
> > * to propagate min/max range.
>
> [...]
^ permalink raw reply related [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
2023-06-08 1:26 ` Eduard Zingerman
@ 2023-06-08 17:21 ` Andrii Nakryiko
2023-06-08 19:05 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Andrii Nakryiko @ 2023-06-08 17:21 UTC (permalink / raw)
To: Eduard Zingerman; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Wed, Jun 7, 2023 at 6:26 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > Make sure that the following unsafe example is rejected by verifier:
> > >
> > > 1: r9 = ... some pointer with range X ...
> > > 2: r6 = ... unbound scalar ID=a ...
> > > 3: r7 = ... unbound scalar ID=b ...
> > > 4: if (r6 > r7) goto +1
> > > 5: r6 = r7
> > > 6: if (r6 > X) goto ...
> > > --- checkpoint ---
> > > 7: r9 += r7
> > > 8: *(u64 *)r9 = Y
> > >
> > > This example is unsafe because not all execution paths verify r7 range.
> > > Because of the jump at (4) the verifier would arrive at (6) in two states:
> > > I. r6{.id=b}, r7{.id=b} via path 1-6;
> > > II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
> > >
> > > Currently regsafe() does not call check_ids() for scalar registers,
> > > thus from POV of regsafe() states (I) and (II) are identical. If the
> > > path 1-6 is taken by verifier first, and checkpoint is created at (6)
> > > the path [1-4, 6] would be considered safe.
> > >
> > > This commit updates regsafe() to call check_ids() for precise scalar
> > > registers.
> > >
> > > To minimize the impact on verification performance, avoid generating
> > > bpf_reg_state::id for constant scalar values when processing BPF_MOV
> > > in check_alu_op(). Scalar IDs are utilized by find_equal_scalars() to
> > > propagate information about value ranges for registers that hold the
> > > same value. However, there is no need to propagate range information
> > > for constants.
> > >
> > > Still, there is some performance impact because of this change.
> > > Using veristat to compare number of processed states for selftests
> > > object files listed in tools/testing/selftests/bpf/veristat.cfg and
> > > Cilium object files from [1] gives the following statistics:
> > >
> > > $ ./veristat -e file,prog,states -f "states_pct>10" \
> > > -C master-baseline.log current.log
> > > File Program States (DIFF)
> > > ----------- ------------------------------ --------------
> > > bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%)
> > > bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%)
> > > bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%)
> > > loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)
> > >
> > > Also test case verifier_search_pruning/allocated_stack has to be
> > > updated to avoid conflicts in register ID assignments between cached
> > > and new states.
> > >
> > > [1] git@github.com:anakryiko/cilium.git
> > >
> > > Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > ---
> >
> > So I checked it also on our internal BPF object files, and it looks
> > mostly good. Here are the only regressions:
> >
> > Program States (A) States (B)
> > States (DIFF)
> > ---------------------------------------- ---------- ----------
> > ---------------
> > balancer_ingress 29219 34531
> > +5312 (+18.18%)
> > syar_bind6_protect6 3257 3599
> > +342 (+10.50%)
> > syar_bind4_protect4 2590 2931
> > +341 (+13.17%)
> > on_alloc 415 526
> > +111 (+26.75%)
> > on_free 406 517
> > +111 (+27.34%)
> > pycallcount 395 506
> > +111 (+28.10%)
> > resume_context 405 516
> > +111 (+27.41%)
> > on_py_event 395 506
> > +111 (+28.10%)
> > on_event 284 394
> > +110 (+38.73%)
> > handle_cuda_event 268 378
> > +110 (+41.04%)
> > handle_cuda_launch 276 386
> > +110 (+39.86%)
> > handle_cuda_malloc_ret 272 382
> > +110 (+40.44%)
> > handle_cuda_memcpy 270 380
> > +110 (+40.74%)
> > handle_cuda_memcpy_async 270 380
> > +110 (+40.74%)
> > handle_pytorch_allocate_ret 271 381
> > +110 (+40.59%)
> > handle_pytorch_malloc_ret 272 382
> > +110 (+40.44%)
> > on_event 284 394
> > +110 (+38.73%)
> > on_event 284 394
> > +110 (+38.73%)
> > syar_task_enter_execve 309 329
> > +20 (+6.47%)
> > kprobe__security_inode_link 968 986
> > +18 (+1.86%)
> > kprobe__security_inode_symlink 838 854
> > +16 (+1.91%)
> > tw_twfw_egress 249 251
> > +2 (+0.80%)
> > tw_twfw_ingress 250 252
> > +2 (+0.80%)
> > tw_twfw_tc_eg 248 250
> > +2 (+0.81%)
> > tw_twfw_tc_in 250 252
> > +2 (+0.80%)
> > raw_tracepoint__sched_process_exec 136 139
> > +3 (+2.21%)
> > kprobe_ret__do_filp_open 869 871
> > +2 (+0.23%)
> > read_erlang_stack 572 573
> > +1 (+0.17%)
> >
> >
> > They are mostly on small-ish programs. The only mild concern from my
> > side is balancer_ingress, which is one of Katran BPF programs. It add
> > +18% of states (which translates to about 70K more instructions
> > verified, up from 350K). I think we can live with this, but would be
> > nice to check why it's happening.
>
> Thank you for reviewing this series.
>
> I looked at the logs that you've shared, the difference is indeed
> caused by some scalar registers having a unique ID in cached state and
> no ID in current state or vice versa. The !rold->id trick that we
> discussed for V2 helps :)
>
> What do you think about an alternative way to exclude unique scalars
> as in the patch below? (on top of this patch-set):
>
> --- 8< -------------------------
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 235d7eded565..ece9722dff3b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -15149,6 +15149,13 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
> return false;
> }
>
> +static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_verifier_env *env)
> +{
> + old_id = old_id ? old_id : env->id_gen++;
> + cur_id = cur_id ? cur_id : env->id_gen++;
> + return check_ids(old_id, cur_id, env->idmap_scratch);
> +}
> +
> static void clean_func_state(struct bpf_verifier_env *env,
> struct bpf_func_state *st)
> {
> @@ -15325,7 +15332,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> */
> return range_within(rold, rcur) &&
> tnum_in(rold->var_off, rcur->var_off) &&
> - check_ids(rold->id, rcur->id, idmap);
> + check_scalar_ids(rold->id, rcur->id, env);
> case PTR_TO_MAP_KEY:
> case PTR_TO_MAP_VALUE:
> case PTR_TO_MEM:
>
> ------------------------- >8 ---
>
> For me this patch removes all veristat differences compared to the
> master. If doing it for real, I'd like to reset env->id_gen at exit
> from states_equal() to the value it had at entry (to avoid allocating
> too many ids).
Hm.. It's clever and pretty minimal, I like it. We are basically
allocating virtual ID for SCALAR that doesn't have id, just to make
sure we get a conflict if the SCALAR with ID cannot be mapped into two
different SCALARs, right?
The only question would be if it's safe to do that for case when
old_reg->id != 0 and cur_reg->id == 0? E.g., if in old (verified)
state we have r6.id = r7.id = 123, and in new state we have r6.id = 0
and r7.id = 0, then your implementation above will say that states are
equivalent. But are they, given there is a link between r6 and r7 that
might be required for correctness. Which we don't have in current
state.
So with this we are getting to my original concerns with your
!rold->id approach, which tries to ignore the necessity of link
between registers.
What if we do this only for old registers? Then, (in old state) r6.id
= 0, r7.id = 0, (in new state) r6.id = r7.id = 123. This will be
rejected because first we'll map 123 to newly allocated X for r6.id,
and then when we try to match r7.id=123 to another allocated ID X+1
we'll get a conflict, right?
>
> >
> > I suspect that dropping SCALAR IDs as we discussed (after fixing
> > register fill/spill ID generation) might completely mitigate that.
> >
> > Overall, LGTM:
> >
> > Acked-by: Andrii Nakryiko <andrii@kernel.org>
> >
> > > kernel/bpf/verifier.c | 34 ++++++++++++++++---
> > > .../bpf/progs/verifier_search_pruning.c | 3 +-
> > > 2 files changed, 32 insertions(+), 5 deletions(-)
> > >
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 2aa60b73f1b5..175ca22b868e 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > > if (BPF_SRC(insn->code) == BPF_X) {
> > > struct bpf_reg_state *src_reg = regs + insn->src_reg;
> > > struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
> > > + bool need_id = (src_reg->type == SCALAR_VALUE && !src_reg->id &&
> > > + !tnum_is_const(src_reg->var_off));
> > >
> >
> > nit: unnecessary outer ()
> >
> > > if (BPF_CLASS(insn->code) == BPF_ALU64) {
> > > /* case: R1 = R2
> > > * copy register state to dest reg
> > > */
> > > - if (src_reg->type == SCALAR_VALUE && !src_reg->id)
> > > + if (need_id)
> > > /* Assign src and dst registers the same ID
> > > * that will be used by find_equal_scalars()
> > > * to propagate min/max range.
> >
> > [...]
>
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
2023-06-08 17:21 ` Andrii Nakryiko
@ 2023-06-08 19:05 ` Eduard Zingerman
2023-06-08 20:58 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-08 19:05 UTC (permalink / raw)
To: Andrii Nakryiko; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Thu, 2023-06-08 at 10:21 -0700, Andrii Nakryiko wrote:
> On Wed, Jun 7, 2023 at 6:26 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote:
> > > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > Make sure that the following unsafe example is rejected by verifier:
> > > >
> > > > 1: r9 = ... some pointer with range X ...
> > > > 2: r6 = ... unbound scalar ID=a ...
> > > > 3: r7 = ... unbound scalar ID=b ...
> > > > 4: if (r6 > r7) goto +1
> > > > 5: r6 = r7
> > > > 6: if (r6 > X) goto ...
> > > > --- checkpoint ---
> > > > 7: r9 += r7
> > > > 8: *(u64 *)r9 = Y
> > > >
> > > > This example is unsafe because not all execution paths verify r7 range.
> > > > Because of the jump at (4) the verifier would arrive at (6) in two states:
> > > > I. r6{.id=b}, r7{.id=b} via path 1-6;
> > > > II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
> > > >
> > > > Currently regsafe() does not call check_ids() for scalar registers,
> > > > thus from POV of regsafe() states (I) and (II) are identical. If the
> > > > path 1-6 is taken by verifier first, and checkpoint is created at (6)
> > > > the path [1-4, 6] would be considered safe.
> > > >
> > > > This commit updates regsafe() to call check_ids() for precise scalar
> > > > registers.
> > > >
> > > > To minimize the impact on verification performance, avoid generating
> > > > bpf_reg_state::id for constant scalar values when processing BPF_MOV
> > > > in check_alu_op(). Scalar IDs are utilized by find_equal_scalars() to
> > > > propagate information about value ranges for registers that hold the
> > > > same value. However, there is no need to propagate range information
> > > > for constants.
> > > >
> > > > Still, there is some performance impact because of this change.
> > > > Using veristat to compare number of processed states for selftests
> > > > object files listed in tools/testing/selftests/bpf/veristat.cfg and
> > > > Cilium object files from [1] gives the following statistics:
> > > >
> > > > $ ./veristat -e file,prog,states -f "states_pct>10" \
> > > > -C master-baseline.log current.log
> > > > File Program States (DIFF)
> > > > ----------- ------------------------------ --------------
> > > > bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%)
> > > > bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%)
> > > > bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%)
> > > > loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)
> > > >
> > > > Also test case verifier_search_pruning/allocated_stack has to be
> > > > updated to avoid conflicts in register ID assignments between cached
> > > > and new states.
> > > >
> > > > [1] git@github.com:anakryiko/cilium.git
> > > >
> > > > Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
> > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > > ---
> > >
> > > So I checked it also on our internal BPF object files, and it looks
> > > mostly good. Here are the only regressions:
> > >
> > > Program States (A) States (B)
> > > States (DIFF)
> > > ---------------------------------------- ---------- ----------
> > > ---------------
> > > balancer_ingress 29219 34531
> > > +5312 (+18.18%)
> > > syar_bind6_protect6 3257 3599
> > > +342 (+10.50%)
> > > syar_bind4_protect4 2590 2931
> > > +341 (+13.17%)
> > > on_alloc 415 526
> > > +111 (+26.75%)
> > > on_free 406 517
> > > +111 (+27.34%)
> > > pycallcount 395 506
> > > +111 (+28.10%)
> > > resume_context 405 516
> > > +111 (+27.41%)
> > > on_py_event 395 506
> > > +111 (+28.10%)
> > > on_event 284 394
> > > +110 (+38.73%)
> > > handle_cuda_event 268 378
> > > +110 (+41.04%)
> > > handle_cuda_launch 276 386
> > > +110 (+39.86%)
> > > handle_cuda_malloc_ret 272 382
> > > +110 (+40.44%)
> > > handle_cuda_memcpy 270 380
> > > +110 (+40.74%)
> > > handle_cuda_memcpy_async 270 380
> > > +110 (+40.74%)
> > > handle_pytorch_allocate_ret 271 381
> > > +110 (+40.59%)
> > > handle_pytorch_malloc_ret 272 382
> > > +110 (+40.44%)
> > > on_event 284 394
> > > +110 (+38.73%)
> > > on_event 284 394
> > > +110 (+38.73%)
> > > syar_task_enter_execve 309 329
> > > +20 (+6.47%)
> > > kprobe__security_inode_link 968 986
> > > +18 (+1.86%)
> > > kprobe__security_inode_symlink 838 854
> > > +16 (+1.91%)
> > > tw_twfw_egress 249 251
> > > +2 (+0.80%)
> > > tw_twfw_ingress 250 252
> > > +2 (+0.80%)
> > > tw_twfw_tc_eg 248 250
> > > +2 (+0.81%)
> > > tw_twfw_tc_in 250 252
> > > +2 (+0.80%)
> > > raw_tracepoint__sched_process_exec 136 139
> > > +3 (+2.21%)
> > > kprobe_ret__do_filp_open 869 871
> > > +2 (+0.23%)
> > > read_erlang_stack 572 573
> > > +1 (+0.17%)
> > >
> > >
> > > They are mostly on small-ish programs. The only mild concern from my
> > > side is balancer_ingress, which is one of Katran BPF programs. It add
> > > +18% of states (which translates to about 70K more instructions
> > > verified, up from 350K). I think we can live with this, but would be
> > > nice to check why it's happening.
> >
> > Thank you for reviewing this series.
> >
> > I looked at the logs that you've shared, the difference is indeed
> > caused by some scalar registers having a unique ID in cached state and
> > no ID in current state or vice versa. The !rold->id trick that we
> > discussed for V2 helps :)
> >
> > What do you think about an alternative way to exclude unique scalars
> > as in the patch below? (on top of this patch-set):
> >
> > --- 8< -------------------------
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 235d7eded565..ece9722dff3b 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -15149,6 +15149,13 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
> > return false;
> > }
> >
> > +static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_verifier_env *env)
> > +{
> > + old_id = old_id ? old_id : env->id_gen++;
> > + cur_id = cur_id ? cur_id : env->id_gen++;
> > + return check_ids(old_id, cur_id, env->idmap_scratch);
> > +}
> > +
> > static void clean_func_state(struct bpf_verifier_env *env,
> > struct bpf_func_state *st)
> > {
> > @@ -15325,7 +15332,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > */
> > return range_within(rold, rcur) &&
> > tnum_in(rold->var_off, rcur->var_off) &&
> > - check_ids(rold->id, rcur->id, idmap);
> > + check_scalar_ids(rold->id, rcur->id, env);
> > case PTR_TO_MAP_KEY:
> > case PTR_TO_MAP_VALUE:
> > case PTR_TO_MEM:
> >
> > ------------------------- >8 ---
> >
> > For me this patch removes all veristat differences compared to the
> > master. If doing it for real, I'd like to reset env->id_gen at exit
> > from states_equal() to the value it had at entry (to avoid allocating
> > too many ids).
>
> Hm.. It's clever and pretty minimal, I like it. We are basically
> allocating virtual ID for SCALAR that doesn't have id, just to make
> sure we get a conflict if the SCALAR with ID cannot be mapped into two
> different SCALARs, right?
>
> The only question would be if it's safe to do that for case when
> old_reg->id != 0 and cur_reg->id == 0? E.g., if in old (verified)
> state we have r6.id = r7.id = 123, and in new state we have r6.id = 0
> and r7.id = 0, then your implementation above will say that states are
> equivalent. But are they, given there is a link between r6 and r7 that
> might be required for correctness. Which we don't have in current
> state.
You mean the other way around, rold.id == 0, rcur.id != 0, right?
(below 0/2 means: original value 0, replaced by new id 2).
(1) old cur
r6.id 0/2 1
r7.id 0/3 1 check_ids returns true
(2) old cur
r6.id 1 0/2
r7.id 1 0/3 check_ids returns false
Also, (1) is no different from (3):
(3) old cur
r6.id 1 3
r7.id 2 3 check_ids returns true
Current check:
if (!rold->precise)
return true;
return range_within(rold, rcur) &&
tnum_in(rold->var_off, rcur->var_off) &&
check_ids(rold->id, rcur->id, idmap);
Will reject (1) and (2), but will accept (3).
New check:
if (!rold->precise)
return true;
return range_within(rold, rcur) &&
tnum_in(rold->var_off, rcur->var_off) &&
check_scalar_ids(rold->id, rcur->id, idmap);
Will reject (2), but will accept (1) and (3).
And modification of check_scalar_ids() to generate IDs only for rold
or only for rcur would not reject (3) either.
(3) would be rejected only if current check is used together with
elimination of unique scalar IDs from old states.
My previous experiments show that eliminating unique IDs from old
states and not eliminating unique IDs from cur states is *very* bad
for performance.
>
> So with this we are getting to my original concerns with your
> !rold->id approach, which tries to ignore the necessity of link
> between registers.
>
> What if we do this only for old registers? Then, (in old state) r6.id
> = 0, r7.id = 0, (in new state) r6.id = r7.id = 123. This will be
> rejected because first we'll map 123 to newly allocated X for r6.id,
> and then when we try to match r7.id=123 to another allocated ID X+1
> we'll get a conflict, right?
>
> >
> > >
> > > I suspect that dropping SCALAR IDs as we discussed (after fixing
> > > register fill/spill ID generation) might completely mitigate that.
> > >
> > > Overall, LGTM:
> > >
> > > Acked-by: Andrii Nakryiko <andrii@kernel.org>
> > >
> > > > kernel/bpf/verifier.c | 34 ++++++++++++++++---
> > > > .../bpf/progs/verifier_search_pruning.c | 3 +-
> > > > 2 files changed, 32 insertions(+), 5 deletions(-)
> > > >
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index 2aa60b73f1b5..175ca22b868e 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > > > if (BPF_SRC(insn->code) == BPF_X) {
> > > > struct bpf_reg_state *src_reg = regs + insn->src_reg;
> > > > struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
> > > > + bool need_id = (src_reg->type == SCALAR_VALUE && !src_reg->id &&
> > > > + !tnum_is_const(src_reg->var_off));
> > > >
> > >
> > > nit: unnecessary outer ()
> > >
> > > > if (BPF_CLASS(insn->code) == BPF_ALU64) {
> > > > /* case: R1 = R2
> > > > * copy register state to dest reg
> > > > */
> > > > - if (src_reg->type == SCALAR_VALUE && !src_reg->id)
> > > > + if (need_id)
> > > > /* Assign src and dst registers the same ID
> > > > * that will be used by find_equal_scalars()
> > > > * to propagate min/max range.
> > >
> > > [...]
> >
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
2023-06-08 19:05 ` Eduard Zingerman
@ 2023-06-08 20:58 ` Eduard Zingerman
2023-06-08 22:37 ` Andrii Nakryiko
0 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-08 20:58 UTC (permalink / raw)
To: Andrii Nakryiko; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Thu, 2023-06-08 at 22:05 +0300, Eduard Zingerman wrote:
[...]
> > Hm.. It's clever and pretty minimal, I like it. We are basically
> > allocating virtual ID for SCALAR that doesn't have id, just to make
> > sure we get a conflict if the SCALAR with ID cannot be mapped into two
> > different SCALARs, right?
> >
> > The only question would be if it's safe to do that for case when
> > old_reg->id != 0 and cur_reg->id == 0? E.g., if in old (verified)
> > state we have r6.id = r7.id = 123, and in new state we have r6.id = 0
> > and r7.id = 0, then your implementation above will say that states are
> > equivalent. But are they, given there is a link between r6 and r7 that
> > might be required for correctness. Which we don't have in current
> > state.
>
> You mean the other way around, rold.id == 0, rcur.id != 0, right?
> (below 0/2 means: original value 0, replaced by new id 2).
>
> (1) old cur
> r6.id 0/2 1
> r7.id 0/3 1 check_ids returns true
>
> (2) old cur
> r6.id 1 0/2
> r7.id 1 0/3 check_ids returns false
>
> Also, (1) is no different from (3):
>
> (3) old cur
> r6.id 1 3
> r7.id 2 3 check_ids returns true
>
> Current check:
>
> if (!rold->precise)
> return true;
> return range_within(rold, rcur) &&
> tnum_in(rold->var_off, rcur->var_off) &&
> check_ids(rold->id, rcur->id, idmap);
>
> Will reject (1) and (2), but will accept (3).
>
> New check:
>
> if (!rold->precise)
> return true;
> return range_within(rold, rcur) &&
> tnum_in(rold->var_off, rcur->var_off) &&
> check_scalar_ids(rold->id, rcur->id, idmap);
>
> Will reject (2), but will accept (1) and (3).
>
> And modification of check_scalar_ids() to generate IDs only for rold
> or only for rcur would not reject (3) either.
>
> (3) would be rejected only if current check is used together with
> elimination of unique scalar IDs from old states.
>
> My previous experiments show that eliminating unique IDs from old
> states and not eliminating unique IDs from cur states is *very* bad
> for performance.
>
> >
> > So with this we are getting to my original concerns with your
> > !rold->id approach, which tries to ignore the necessity of link
> > between registers.
> >
> > What if we do this only for old registers? Then, (in old state) r6.id
> > = 0, r7.id = 0, (in new state) r6.id = r7.id = 123. This will be
> > rejected because first we'll map 123 to newly allocated X for r6.id,
> > and then when we try to match r7.id=123 to another allocated ID X+1
> > we'll get a conflict, right?
[...]
Ok, here is what I think is the final version:
a. for each old or cur ID generate temporary unique ID;
b. for scalars use modified check_ids that forbids mapping same 'cur'
ID to several different 'old' IDs.
(a) allows to reject situations like:
(1) old cur (2) old cur
r6.id 0 1 r6.id 1 0
r7.id 0 1 r7.id 1 0
(b) allows to reject situations like:
(3) old cur
r6.id 1 3
r7.id 2 3
And whether some scalar ID is unique or not does not matter for the
algorithm.
Tests are passing, katran example is fine (350k insns, 29K states),
minor veristat regression:
File Program States (DIFF)
--------- ------------------------------ -------------
bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +3 (+0.80%)
bpf_xdp.o tail_rev_nodeport_lb4 +2 (+0.50%)
--- 8< -----------------------------
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 235d7eded565..5794dc7830db 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15149,6 +15149,31 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
return false;
}
+static bool check_scalar_ids(struct bpf_verifier_env *env, u32 old_id, u32 cur_id,
+ struct bpf_id_pair *idmap)
+{
+ unsigned int i;
+
+ old_id = old_id ? old_id : env->id_gen++;
+ cur_id = cur_id ? cur_id : env->id_gen++;
+
+ for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
+ if (!idmap[i].old) {
+ /* Reached an empty slot; haven't seen this id before */
+ idmap[i].old = old_id;
+ idmap[i].cur = cur_id;
+ return true;
+ }
+ if (idmap[i].old == old_id)
+ return idmap[i].cur == cur_id;
+ if (idmap[i].cur == cur_id)
+ return false;
+ }
+ /* We ran out of idmap slots, which should be impossible */
+ WARN_ON_ONCE(1);
+ return false;
+}
+
static void clean_func_state(struct bpf_verifier_env *env,
struct bpf_func_state *st)
{
@@ -15325,7 +15350,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
*/
return range_within(rold, rcur) &&
tnum_in(rold->var_off, rcur->var_off) &&
- check_ids(rold->id, rcur->id, idmap);
+ check_scalar_ids(env, rold->id, rcur->id, idmap);
case PTR_TO_MAP_KEY:
case PTR_TO_MAP_VALUE:
case PTR_TO_MEM:
----------------------------- >8 ---
^ permalink raw reply related [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
2023-06-08 20:58 ` Eduard Zingerman
@ 2023-06-08 22:37 ` Andrii Nakryiko
2023-06-08 23:40 ` Eduard Zingerman
0 siblings, 1 reply; 21+ messages in thread
From: Andrii Nakryiko @ 2023-06-08 22:37 UTC (permalink / raw)
To: Eduard Zingerman; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Thu, Jun 8, 2023 at 1:58 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2023-06-08 at 22:05 +0300, Eduard Zingerman wrote:
> [...]
> > > Hm.. It's clever and pretty minimal, I like it. We are basically
> > > allocating virtual ID for SCALAR that doesn't have id, just to make
> > > sure we get a conflict if the SCALAR with ID cannot be mapped into two
> > > different SCALARs, right?
> > >
> > > The only question would be if it's safe to do that for case when
> > > old_reg->id != 0 and cur_reg->id == 0? E.g., if in old (verified)
> > > state we have r6.id = r7.id = 123, and in new state we have r6.id = 0
> > > and r7.id = 0, then your implementation above will say that states are
> > > equivalent. But are they, given there is a link between r6 and r7 that
> > > might be required for correctness. Which we don't have in current
> > > state.
> >
> > You mean the other way around, rold.id == 0, rcur.id != 0, right?
> > (below 0/2 means: original value 0, replaced by new id 2).
no, I actually meant what I wrote, but I didn't realize that
check_ids() is kind of broken... Because it shouldn't allow the same
ID from cur state to be mapped to two different IDs in old state,
should it?
> >
> > (1) old cur
> > r6.id 0/2 1
> > r7.id 0/3 1 check_ids returns true
I think this should be rejected.
> >
> > (2) old cur
> > r6.id 1 0/2
> > r7.id 1 0/3 check_ids returns false
And this should be rejected.
> >
> > Also, (1) is no different from (3):
> >
> > (3) old cur
> > r6.id 1 3
> > r7.id 2 3 check_ids returns true
And this definitely should be rejected.
The only situation that might not be rejected would be:
old cur
r6.id 0/1 3
r7.id. 0/2 4
And perhaps this one is ok as well?
old cur
r6.id 3 0/1
r7.id. 4 0/2
And my assumption was that that's what you are trying to do. But
weirdly check_ids() is enforcing only that old ID has to have a unique
mapping, which seems like a bug.
> >
> > Current check:
> >
> > if (!rold->precise)
> > return true;
> > return range_within(rold, rcur) &&
> > tnum_in(rold->var_off, rcur->var_off) &&
> > check_ids(rold->id, rcur->id, idmap);
> >
> > Will reject (1) and (2), but will accept (3).
> >
> > New check:
> >
> > if (!rold->precise)
> > return true;
> > return range_within(rold, rcur) &&
> > tnum_in(rold->var_off, rcur->var_off) &&
> > check_scalar_ids(rold->id, rcur->id, idmap);
> >
> > Will reject (2), but will accept (1) and (3).
> >
> > And modification of check_scalar_ids() to generate IDs only for rold
> > or only for rcur would not reject (3) either.
> >
> > (3) would be rejected only if current check is used together with
> > elimination of unique scalar IDs from old states.
> >
> > My previous experiments show that eliminating unique IDs from old
> > states and not eliminating unique IDs from cur states is *very* bad
> > for performance.
> >
> > >
> > > So with this we are getting to my original concerns with your
> > > !rold->id approach, which tries to ignore the necessity of link
> > > between registers.
> > >
> > > What if we do this only for old registers? Then, (in old state) r6.id
> > > = 0, r7.id = 0, (in new state) r6.id = r7.id = 123. This will be
> > > rejected because first we'll map 123 to newly allocated X for r6.id,
> > > and then when we try to match r7.id=123 to another allocated ID X+1
> > > we'll get a conflict, right?
>
> [...]
>
> Ok, here is what I think is the final version:
> a. for each old or cur ID generate temporary unique ID;
> b. for scalars use modified check_ids that forbids mapping same 'cur'
> ID to several different 'old' IDs.
>
> (a) allows to reject situations like:
>
> (1) old cur (2) old cur
> r6.id 0 1 r6.id 1 0
> r7.id 0 1 r7.id 1 0
>
> (b) allows to reject situations like:
>
> (3) old cur
> r6.id 1 3
> r7.id 2 3
>
> And whether some scalar ID is unique or not does not matter for the
> algorithm.
>
> Tests are passing, katran example is fine (350k insns, 29K states),
> minor veristat regression:
>
> File Program States (DIFF)
> --------- ------------------------------ -------------
> bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +3 (+0.80%)
> bpf_xdp.o tail_rev_nodeport_lb4 +2 (+0.50%)
>
> --- 8< -----------------------------
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 235d7eded565..5794dc7830db 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -15149,6 +15149,31 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
> return false;
> }
>
> +static bool check_scalar_ids(struct bpf_verifier_env *env, u32 old_id, u32 cur_id,
> + struct bpf_id_pair *idmap)
> +{
> + unsigned int i;
> +
> + old_id = old_id ? old_id : env->id_gen++;
> + cur_id = cur_id ? cur_id : env->id_gen++;
> +
> + for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
> + if (!idmap[i].old) {
> + /* Reached an empty slot; haven't seen this id before */
> + idmap[i].old = old_id;
> + idmap[i].cur = cur_id;
> + return true;
> + }
> + if (idmap[i].old == old_id)
> + return idmap[i].cur == cur_id;
> + if (idmap[i].cur == cur_id)
> + return false;
I think this should just be added to existing check_ids(), I think
it's a bug that we don't check this condition today in check_ids().
But I'd say let's land fixes you have right now. And then work on
fixing and optimizing scala ID checks separately. We are doing too
many things at the same time :(
> + }
> + /* We ran out of idmap slots, which should be impossible */
> + WARN_ON_ONCE(1);
> + return false;
> +}
> +
> static void clean_func_state(struct bpf_verifier_env *env,
> struct bpf_func_state *st)
> {
> @@ -15325,7 +15350,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> */
> return range_within(rold, rcur) &&
> tnum_in(rold->var_off, rcur->var_off) &&
> - check_ids(rold->id, rcur->id, idmap);
> + check_scalar_ids(env, rold->id, rcur->id, idmap);
> case PTR_TO_MAP_KEY:
> case PTR_TO_MAP_VALUE:
> case PTR_TO_MEM:
>
> ----------------------------- >8 ---
^ permalink raw reply [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
2023-06-08 22:37 ` Andrii Nakryiko
@ 2023-06-08 23:40 ` Eduard Zingerman
0 siblings, 0 replies; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-08 23:40 UTC (permalink / raw)
To: Andrii Nakryiko; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Thu, 2023-06-08 at 15:37 -0700, Andrii Nakryiko wrote:
> On Thu, Jun 8, 2023 at 1:58 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Thu, 2023-06-08 at 22:05 +0300, Eduard Zingerman wrote:
> > [...]
> > > > Hm.. It's clever and pretty minimal, I like it. We are basically
> > > > allocating virtual ID for SCALAR that doesn't have id, just to make
> > > > sure we get a conflict if the SCALAR with ID cannot be mapped into two
> > > > different SCALARs, right?
> > > >
> > > > The only question would be if it's safe to do that for case when
> > > > old_reg->id != 0 and cur_reg->id == 0? E.g., if in old (verified)
> > > > state we have r6.id = r7.id = 123, and in new state we have r6.id = 0
> > > > and r7.id = 0, then your implementation above will say that states are
> > > > equivalent. But are they, given there is a link between r6 and r7 that
> > > > might be required for correctness. Which we don't have in current
> > > > state.
> > >
> > > You mean the other way around, rold.id == 0, rcur.id != 0, right?
> > > (below 0/2 means: original value 0, replaced by new id 2).
>
> no, I actually meant what I wrote, but I didn't realize that
> check_ids() is kind of broken... Because it shouldn't allow the same
> ID from cur state to be mapped to two different IDs in old state,
> should it?
IDs are used for several things, and it looks like the answer might vary.
For example, I looked at mark_ptr_or_null_regs():
- it is called when conditional of form (ptr == NULL) is checked;
- it marks every register with pointer having same ID as ptr as
null/non-null;
- when register is marked not null ID is removed (not for locks but
ignore it for now).
Assume r6 and r7 are both PTR_MAYBE_NULL and ID assignments look as
follows:
old cur
r6.id 1 3
r7.id 2 3
'old' is safe, which means the following:
- either r6 was not accessed or it was guarded by (r6 == NULL)
- either r7 was not accessed or it was guarded by (r7 == NULL)
In both cases it should be ok, if r6 and r7 are in fact the same
pointer. It would be checked to be not NULL two times but that's fine.
So, I'd say that 'cur' is a special case of 'old' and check_ids() is
correct for it. But this is the same argument I used for scalars and
you were not convinced :)
Need to examine each use case carefully.
> > > (1) old cur
> > > r6.id 0/2 1
> > > r7.id 0/3 1 check_ids returns true
>
> I think this should be rejected.
That's what we agreed upon when decided not to do !rold->id, so yes.
> > > (2) old cur
> > > r6.id 1 0/2
> > > r7.id 1 0/3 check_ids returns false
>
> And this should be rejected.
For sure.
> > > Also, (1) is no different from (3):
> > >
> > > (3) old cur
> > > r6.id 1 3
> > > r7.id 2 3 check_ids returns true
>
> And this definitely should be rejected.
Same as (1).
> The only situation that might not be rejected would be:
>
> old cur
> r6.id 0/1 3
> r7.id. 0/2 4
>
> And perhaps this one is ok as well?
>
> old cur
> r6.id 3 0/1
> r7.id. 4 0/2
I think these two should be accepted.
[...]
> > +static bool check_scalar_ids(struct bpf_verifier_env *env, u32 old_id, u32 cur_id,
> > + struct bpf_id_pair *idmap)
> > +{
> > + unsigned int i;
> > +
> > + old_id = old_id ? old_id : env->id_gen++;
> > + cur_id = cur_id ? cur_id : env->id_gen++;
> > +
> > + for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
> > + if (!idmap[i].old) {
> > + /* Reached an empty slot; haven't seen this id before */
> > + idmap[i].old = old_id;
> > + idmap[i].cur = cur_id;
> > + return true;
> > + }
> > + if (idmap[i].old == old_id)
> > + return idmap[i].cur == cur_id;
> > + if (idmap[i].cur == cur_id)
> > + return false;
>
> I think this should just be added to existing check_ids(), I think
> it's a bug that we don't check this condition today in check_ids().
>
> But I'd say let's land fixes you have right now. And then work on
> fixing and optimizing scala ID checks separately. We are doing too
> many things at the same time :(
Ok, will post V4 with these changes and examine other cases later.
Thanks again for the discussion.
[...]
^ permalink raw reply [flat|nested] 21+ messages in thread
* [PATCH bpf-next v3 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe()
2023-06-06 22:24 [PATCH bpf-next v3 0/4] verify scalar ids mapping in regsafe() Eduard Zingerman
` (2 preceding siblings ...)
2023-06-06 22:24 ` [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids() Eduard Zingerman
@ 2023-06-06 22:24 ` Eduard Zingerman
2023-06-07 21:40 ` Andrii Nakryiko
3 siblings, 1 reply; 21+ messages in thread
From: Eduard Zingerman @ 2023-06-06 22:24 UTC (permalink / raw)
To: bpf, ast; +Cc: andrii, daniel, martin.lau, kernel-team, yhs, Eduard Zingerman
Verify that the following example is rejected by verifier:
r9 = ... some pointer with range X ...
r6 = ... unbound scalar ID=a ...
r7 = ... unbound scalar ID=b ...
if (r6 > r7) goto +1
r7 = r6
if (r7 > X) goto exit
r9 += r6
*(u64 *)r9 = Y
Also add test cases to check that check_alu_op() for BPF_MOV instruction does
not allocate scalar ID if source register is a constant.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
.../selftests/bpf/progs/verifier_scalar_ids.c | 184 ++++++++++++++++++
1 file changed, 184 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
index 0f1071847490..00d80ba525d7 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
@@ -321,4 +321,188 @@ __naked void precision_two_ids(void)
: __clobber_all);
}
+/* Verify that check_ids() is used by regsafe() for scalars.
+ *
+ * r9 = ... some pointer with range X ...
+ * r6 = ... unbound scalar ID=a ...
+ * r7 = ... unbound scalar ID=b ...
+ * if (r6 > r7) goto +1
+ * r6 = r7
+ * if (r6 > X) goto exit
+ * r9 += r7
+ * *(u8 *)r9 = Y
+ *
+ * The memory access is safe only if r7 is bounded,
+ * which is true for one branch and not true for another.
+ */
+SEC("socket")
+__failure __msg("register with unbounded min value")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void check_ids_in_regsafe(void)
+{
+ asm volatile (
+ /* Bump allocated stack */
+ "r1 = 0;"
+ "*(u64*)(r10 - 8) = r1;"
+ /* r9 = pointer to stack */
+ "r9 = r10;"
+ "r9 += -8;"
+ /* r7 = ktime_get_ns() */
+ "call %[bpf_ktime_get_ns];"
+ "r7 = r0;"
+ /* r6 = ktime_get_ns() */
+ "call %[bpf_ktime_get_ns];"
+ "r6 = r0;"
+ /* if r6 > r7 is an unpredictable jump */
+ "if r6 > r7 goto l1_%=;"
+ "r7 = r6;"
+"l1_%=:"
+ /* if r6 > 4 exit(0) */
+ "if r7 > 4 goto l2_%=;"
+ /* Access memory at r9[r7] */
+ "r9 += r6;"
+ "r0 = *(u8*)(r9 + 0);"
+"l2_%=:"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+/* Similar to check_ids_in_regsafe.
+ * The l0 could be reached in two states:
+ *
+ * (1) r6{.id=A}, r7{.id=A}, r8{.id=B}
+ * (2) r6{.id=B}, r7{.id=A}, r8{.id=B}
+ *
+ * Where (2) is not safe, as "r7 > 4" check won't propagate range for it.
+ * This example would be considered safe without changes to
+ * mark_chain_precision() to track scalar values with equal IDs.
+ */
+SEC("socket")
+__failure __msg("register with unbounded min value")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void check_ids_in_regsafe_2(void)
+{
+ asm volatile (
+ /* Bump allocated stack */
+ "r1 = 0;"
+ "*(u64*)(r10 - 8) = r1;"
+ /* r9 = pointer to stack */
+ "r9 = r10;"
+ "r9 += -8;"
+ /* r8 = ktime_get_ns() */
+ "call %[bpf_ktime_get_ns];"
+ "r8 = r0;"
+ /* r7 = ktime_get_ns() */
+ "call %[bpf_ktime_get_ns];"
+ "r7 = r0;"
+ /* r6 = ktime_get_ns() */
+ "call %[bpf_ktime_get_ns];"
+ "r6 = r0;"
+ /* scratch .id from r0 */
+ "r0 = 0;"
+ /* if r6 > r7 is an unpredictable jump */
+ "if r6 > r7 goto l1_%=;"
+ /* tie r6 and r7 .id */
+ "r6 = r7;"
+"l0_%=:"
+ /* if r7 > 4 exit(0) */
+ "if r7 > 4 goto l2_%=;"
+ /* Access memory at r9[r7] */
+ "r9 += r6;"
+ "r0 = *(u8*)(r9 + 0);"
+"l2_%=:"
+ "r0 = 0;"
+ "exit;"
+"l1_%=:"
+ /* tie r6 and r8 .id */
+ "r6 = r8;"
+ "goto l0_%=;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+/* Check that scalar IDs *are not* generated on register to register
+ * assignments if source register is a constant.
+ *
+ * If such IDs *are* generated the 'l1' below would be reached in
+ * two states:
+ *
+ * (1) r1{.id=A}, r2{.id=A}
+ * (2) r1{.id=C}, r2{.id=C}
+ *
+ * Thus forcing 'if r1 == r2' verification twice.
+ */
+SEC("socket")
+__success __log_level(2)
+__msg("11: (1d) if r3 == r4 goto pc+0")
+__msg("frame 0: propagating r3,r4")
+__msg("11: safe")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void no_scalar_id_for_const(void)
+{
+ asm volatile (
+ "call %[bpf_ktime_get_ns];"
+ /* unpredictable jump */
+ "if r0 > 7 goto l0_%=;"
+ /* possibly generate same scalar ids for r3 and r4 */
+ "r1 = 0;"
+ "r1 = r1;"
+ "r3 = r1;"
+ "r4 = r1;"
+ "goto l1_%=;"
+"l0_%=:"
+ /* possibly generate different scalar ids for r3 and r4 */
+ "r1 = 0;"
+ "r2 = 0;"
+ "r3 = r1;"
+ "r4 = r2;"
+"l1_%=:"
+ /* predictable jump, marks r3 and r4 precise */
+ "if r3 == r4 goto +0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
+/* Same as no_scalar_id_for_const() but for 32-bit values */
+SEC("socket")
+__success __log_level(2)
+__msg("11: (1e) if w3 == w4 goto pc+0")
+__msg("frame 0: propagating r3,r4")
+__msg("11: safe")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void no_scalar_id_for_const32(void)
+{
+ asm volatile (
+ "call %[bpf_ktime_get_ns];"
+ /* unpredictable jump */
+ "if r0 > 7 goto l0_%=;"
+ /* possibly generate same scalar ids for r3 and r4 */
+ "w1 = 0;"
+ "w1 = w1;"
+ "w3 = w1;"
+ "w4 = w1;"
+ "goto l1_%=;"
+"l0_%=:"
+ /* possibly generate different scalar ids for r3 and r4 */
+ "w1 = 0;"
+ "w2 = 0;"
+ "w3 = w1;"
+ "w4 = w2;"
+"l1_%=:"
+ /* predictable jump, marks r1 and r2 precise */
+ "if w3 == w4 goto +0;"
+ "r0 = 0;"
+ "exit;"
+ :
+ : __imm(bpf_ktime_get_ns)
+ : __clobber_all);
+}
+
char _license[] SEC("license") = "GPL";
--
2.40.1
^ permalink raw reply related [flat|nested] 21+ messages in thread* Re: [PATCH bpf-next v3 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe()
2023-06-06 22:24 ` [PATCH bpf-next v3 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe() Eduard Zingerman
@ 2023-06-07 21:40 ` Andrii Nakryiko
0 siblings, 0 replies; 21+ messages in thread
From: Andrii Nakryiko @ 2023-06-07 21:40 UTC (permalink / raw)
To: Eduard Zingerman; +Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yhs
On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Verify that the following example is rejected by verifier:
>
> r9 = ... some pointer with range X ...
> r6 = ... unbound scalar ID=a ...
> r7 = ... unbound scalar ID=b ...
> if (r6 > r7) goto +1
> r7 = r6
> if (r7 > X) goto exit
> r9 += r6
> *(u64 *)r9 = Y
>
> Also add test cases to check that check_alu_op() for BPF_MOV instruction does
> not allocate scalar ID if source register is a constant.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
> .../selftests/bpf/progs/verifier_scalar_ids.c | 184 ++++++++++++++++++
> 1 file changed, 184 insertions(+)
>
[...]
> +/* Similar to check_ids_in_regsafe.
> + * The l0 could be reached in two states:
> + *
> + * (1) r6{.id=A}, r7{.id=A}, r8{.id=B}
> + * (2) r6{.id=B}, r7{.id=A}, r8{.id=B}
> + *
> + * Where (2) is not safe, as "r7 > 4" check won't propagate range for it.
> + * This example would be considered safe without changes to
> + * mark_chain_precision() to track scalar values with equal IDs.
> + */
> +SEC("socket")
> +__failure __msg("register with unbounded min value")
> +__flag(BPF_F_TEST_STATE_FREQ)
> +__naked void check_ids_in_regsafe_2(void)
> +{
> + asm volatile (
> + /* Bump allocated stack */
> + "r1 = 0;"
> + "*(u64*)(r10 - 8) = r1;"
> + /* r9 = pointer to stack */
> + "r9 = r10;"
> + "r9 += -8;"
> + /* r8 = ktime_get_ns() */
> + "call %[bpf_ktime_get_ns];"
> + "r8 = r0;"
> + /* r7 = ktime_get_ns() */
> + "call %[bpf_ktime_get_ns];"
> + "r7 = r0;"
> + /* r6 = ktime_get_ns() */
> + "call %[bpf_ktime_get_ns];"
> + "r6 = r0;"
> + /* scratch .id from r0 */
> + "r0 = 0;"
> + /* if r6 > r7 is an unpredictable jump */
> + "if r6 > r7 goto l1_%=;"
> + /* tie r6 and r7 .id */
> + "r6 = r7;"
> +"l0_%=:"
> + /* if r7 > 4 exit(0) */
> + "if r7 > 4 goto l2_%=;"
> + /* Access memory at r9[r7] */
> + "r9 += r6;"
> + "r0 = *(u8*)(r9 + 0);"
> +"l2_%=:"
> + "r0 = 0;"
> + "exit;"
> +"l1_%=:"
complete offtopic, feel free to ignore:
I must say that this "l0_%=" pattern is so ugly that I instead choose
to use local labels and specify forward/backward mark:
goto 1f; /* forward */
1:
...
goto 1b; /* backward */
I can see why _%= is good for the code generation approach (and even
then it probably is not hard to determine this b/f mark during
codegen), but for manual code I'm not convinced it's worth it :)
> + /* tie r6 and r8 .id */
> + "r6 = r8;"
> + "goto l0_%=;"
> + :
> + : __imm(bpf_ktime_get_ns)
> + : __clobber_all);
> +}
> +
> +/* Check that scalar IDs *are not* generated on register to register
> + * assignments if source register is a constant.
> + *
> + * If such IDs *are* generated the 'l1' below would be reached in
> + * two states:
> + *
> + * (1) r1{.id=A}, r2{.id=A}
> + * (2) r1{.id=C}, r2{.id=C}
> + *
> + * Thus forcing 'if r1 == r2' verification twice.
> + */
> +SEC("socket")
> +__success __log_level(2)
> +__msg("11: (1d) if r3 == r4 goto pc+0")
> +__msg("frame 0: propagating r3,r4")
> +__msg("11: safe")
would this detect that `if r1 == r2` happens twice, if it did?
maybe we should check the number of verified states instead? We
control branching and checkpointing, so this should be stable, right?
> +__flag(BPF_F_TEST_STATE_FREQ)
> +__naked void no_scalar_id_for_const(void)
> +{
> + asm volatile (
> + "call %[bpf_ktime_get_ns];"
> + /* unpredictable jump */
> + "if r0 > 7 goto l0_%=;"
> + /* possibly generate same scalar ids for r3 and r4 */
> + "r1 = 0;"
> + "r1 = r1;"
> + "r3 = r1;"
> + "r4 = r1;"
> + "goto l1_%=;"
> +"l0_%=:"
> + /* possibly generate different scalar ids for r3 and r4 */
> + "r1 = 0;"
> + "r2 = 0;"
> + "r3 = r1;"
> + "r4 = r2;"
> +"l1_%=:"
> + /* predictable jump, marks r3 and r4 precise */
> + "if r3 == r4 goto +0;"
> + "r0 = 0;"
> + "exit;"
> + :
> + : __imm(bpf_ktime_get_ns)
> + : __clobber_all);
> +}
> +
[...]
^ permalink raw reply [flat|nested] 21+ messages in thread