On Mon, Jun 12, 2023 at 9:08 AM Eduard Zingerman <eddyz87@xxxxxxxxx> 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.
>
> Changes in this commit:
> - Function check_scalar_ids() is added, it differs from check_ids() in
> the following aspects:
> - treats ID zero as a unique scalar ID;
> - disallows mapping same 'cur_id' to multiple 'old_id'.
> - check_scalar_ids() needs to generate temporary unique IDs, field
> 'tmp_id_gen' is added to bpf_verifier_env::idmap_scratch to
> facilitate this.
> - Function scalar_regs_exact() is added, it differs from regs_exact()
> in the following aspects:
> - uses check_scalar_ids() for ID comparison;
> - does not check reg_obj_id as this field is not used for scalar
> values.
> - regsafe() is updated to:
> - use check_scalar_ids() for precise scalar registers.
> - use scalar_regs_exact() for scalar registers, but only for
> explore_alu_limits branch. This simplifies control flow for scalar
> case, and has no measurable performance impact.
> - check_alu_op() is updated avoid generating bpf_reg_state::id for
> constant scalar values when processing BPF_MOV. ID is needed to
> propagate range information for identical values, but there is
> nothing to propagate for constants.
>
> Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
> Acked-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
> Signed-off-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
> ---
> include/linux/bpf_verifier.h | 17 ++++--
> kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++-------
> 2 files changed, 97 insertions(+), 28 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 73a98f6240fd..042b76fe8e29 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -313,11 +313,6 @@ struct bpf_idx_pair {
> u32 idx;
> };
>
> -struct bpf_id_pair {
> - u32 old;
> - u32 cur;
> -};
> -
> #define MAX_CALL_FRAMES 8
> /* Maximum number of register states that can exist at once */
> #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)
> @@ -559,6 +554,16 @@ struct backtrack_state {
> u64 stack_masks[MAX_CALL_FRAMES];
> };
>
> +struct bpf_id_pair {
> + u32 old;
> + u32 cur;
> +};
> +
> +struct bpf_idmap {
> + u32 tmp_id_gen;
> + struct bpf_id_pair map[BPF_ID_MAP_SIZE];
> +};
> +
> struct bpf_idset {
> u32 count;
> u32 ids[BPF_ID_MAP_SIZE];
> @@ -596,7 +601,7 @@ struct bpf_verifier_env {
> struct bpf_verifier_log log;
> struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
> union {
> - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> + struct bpf_idmap idmap_scratch;
> struct bpf_idset idset_scratch;
> };
> struct {
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 9b5f2433194f..b15ebfed207a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -12942,12 +12942,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.
> @@ -12966,7 +12968,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
> @@ -15122,8 +15124,9 @@ static bool range_within(struct bpf_reg_state *old,
> * So we look through our idmap to see if this old id has been seen before. If
> * so, we require the new id to match; otherwise, we add the id pair to the map.
> */
> -static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
> +static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
> {
> + struct bpf_id_pair *map = idmap->map;
> unsigned int i;
>
> /* either both IDs should be set or both should be zero */
> @@ -15134,14 +15137,44 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
> return true;
>
> for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
> - if (!idmap[i].old) {
> + if (!map[i].old) {
> /* Reached an empty slot; haven't seen this id before */
> - idmap[i].old = old_id;
> - idmap[i].cur = cur_id;
> + map[i].old = old_id;
> + map[i].cur = cur_id;
> return true;
> }
> - if (idmap[i].old == old_id)
> - return idmap[i].cur == cur_id;
> + if (map[i].old == old_id)
> + return map[i].cur == cur_id;
> + }
> + /* We ran out of idmap slots, which should be impossible */
> + WARN_ON_ONCE(1);
> + return false;
> +}
> +
> +/* Similar to check_ids(), but:
> + * - disallow mapping of different 'old_id' values to same 'cur_id' value;
> + * - for zero 'old_id' or 'cur_id' allocate a unique temporary ID
> + * to allow pairs like '0 vs unique ID', 'unique ID vs 0'.
> + */
> +static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
> +{
> + struct bpf_id_pair *map = idmap->map;
> + unsigned int i;
> +
> + old_id = old_id ? old_id : ++idmap->tmp_id_gen;
> + cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen;
> +
> + for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
> + if (!map[i].old) {
> + /* Reached an empty slot; haven't seen this id before */
> + map[i].old = old_id;
> + map[i].cur = cur_id;
> + return true;
> + }
> + if (map[i].old == old_id)
> + return map[i].cur == cur_id;
> + if (map[i].cur == cur_id)
> + return false;
We were discussing w/ Alexei (offline) making these changes as
backportable and minimal as possible, so I looked again how to
minimize all the extra code added.
I still insist that the current logic in check_ids() is invalid to
allow the same cur_id to map to two different old_ids, especially for
non-SCALAR, actually. E.g., a situation where we have a register that
is auto-invalidated. E.g., bpf_iter element (each gets an ID), or it
could be id'ed dynptr_ringbuf.
Think about the following situation:
In the old state, we could have r1.id = 1; r2.id = 2; Two registers
keep two separate pointers to ringbuf.
In the new state, we have r1.id = r2.id = 3; That is, two registers
keep the *same* pointer to ringbuf elem.
Now imagine that a BPF program has bpf_ringbuf_submit(r1) and
invalidates this register. With the old state it will invalidate r1
and will keep r2 valid. So it's safe for the BPF program to keep
working with r2 as valid ringbuf (and eventually submit it as well).
Now this is entirely unsafe for the new state. Once
bpf_ringbuf_submit(r1) happens, r2 shouldn't be accessed anymore. But
yet it will be declared safe with current check_ids() logic.
Ergo, check_ids() should make sure we do not have multi-mapping for
any of the IDs. Even if in some corner case that might be ok.
I actually tested this change with veristat, there are no regressions
at all. I think it's both safe from a perf standpoint, and necessary
and safe from a correctness standpoint.
So all in all (I did inline scalar_regs_exact in a separate patch, up
to you), I have these changes on top and they all are good from
veristat perspective:
Author: Andrii Nakryiko <andrii@xxxxxxxxxx>
Date: Mon Jun 12 12:53:25 2023 -0700
bpf: inline scalar_regs_exact
Signed-off-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9d5fefd970a3..c5606613136d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15262,14 +15262,6 @@ static bool regs_exact(const struct
bpf_reg_state *rold,
check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
}
-static bool scalar_regs_exact(const struct bpf_reg_state *rold,
- const struct bpf_reg_state *rcur,
- struct bpf_idmap *idmap)
-{
- return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
- check_scalar_ids(rold->id, rcur->id, idmap);
-}
-
/* Returns true if (rold safe implies rcur safe) */
static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
struct bpf_reg_state *rcur, struct bpf_idmap *idmap)
@@ -15309,8 +15301,13 @@ static bool regsafe(struct bpf_verifier_env
*env, struct bpf_reg_state *rold,
switch (base_type(rold->type)) {
case SCALAR_VALUE:
- if (env->explore_alu_limits)
- return scalar_regs_exact(rold, rcur, idmap);
+ if (env->explore_alu_limits) {
+ /* explore_alu_limits disables tnum_in() and
range_within()
+ * logic and requires everything to be strict
+ */
+ return memcmp(rold, rcur, offsetof(struct
bpf_reg_state, id)) == 0 &&
+ check_scalar_ids(rold->id, rcur->id, idmap);
+ }
if (!rold->precise)
return true;
/* Why check_ids() for scalar registers?
commit 57297c01fe747e423cd3c924ef492c0688d8057a
Author: Andrii Nakryiko <andrii@xxxxxxxxxx>
Date: Mon Jun 12 11:46:46 2023 -0700
bpf: make check_ids disallow multi-mapping of IDs universally
Signed-off-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3da77713d1ca..9d5fefd970a3 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15137,6 +15137,8 @@ static bool check_ids(u32 old_id, u32 cur_id,
struct bpf_idmap *idmap)
}
if (map[i].old == old_id)
return map[i].cur == cur_id;
+ if (map[i].cur == cur_id)
+ return false;
}
/* We ran out of idmap slots, which should be impossible */
WARN_ON_ONCE(1);
@@ -15144,33 +15146,15 @@ static bool check_ids(u32 old_id, u32
cur_id, struct bpf_idmap *idmap)
}
/* Similar to check_ids(), but:
- * - disallow mapping of different 'old_id' values to same 'cur_id' value;
* - for zero 'old_id' or 'cur_id' allocate a unique temporary ID
* to allow pairs like '0 vs unique ID', 'unique ID vs 0'.
*/
static bool check_scalar_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
{
- struct bpf_id_pair *map = idmap->map;
- unsigned int i;
-
old_id = old_id ? old_id : ++idmap->tmp_id_gen;
cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen;
- for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
- if (!map[i].old) {
- /* Reached an empty slot; haven't seen this id before */
- map[i].old = old_id;
- map[i].cur = cur_id;
- return true;
- }
- if (map[i].old == old_id)
- return map[i].cur == cur_id;
- if (map[i].cur == cur_id)
- return false;
- }
- /* We ran out of idmap slots, which should be impossible */
- WARN_ON_ONCE(1);
- return false;
+ return check_ids(old_id, cur_id, idmap);
}
static void clean_func_state(struct bpf_verifier_env *env,
> }
> /* We ran out of idmap slots, which should be impossible */
> WARN_ON_ONCE(1);
> @@ -15246,16 +15279,24 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
>
> static bool regs_exact(const struct bpf_reg_state *rold,
> const struct bpf_reg_state *rcur,
> - struct bpf_id_pair *idmap)
> + struct bpf_idmap *idmap)
> {
> return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
> check_ids(rold->id, rcur->id, idmap) &&
> check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
> }
>
[...]
