| Message ID | 20221128163442.280187-2-eddyz87@gmail.com (mailing list archive) |
|---|---|
| State | RFC |
| Delegated to: | BPF |
| Headers | show |
| Series | bpf: verify scalar ids mapping in regsafe() using check_ids() | expand |
On Mon, Nov 28, 2022 at 8:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > Prior to this commit the following unsafe example passed verification: > > 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 ... ; <-- suppose checkpoint state is created here > 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 makes the following changes: > - a call to check_ids() is added in regsafe() for scalar registers case; > - a function mark_equal_scalars_as_read() is added to ensure that > registers with identical IDs are preserved in the checkpoint states > in case when find_equal_scalars() updates register range for several > registers sharing the same ID. > Fixes tag missing? These are tricky changes with subtle details. Let's split check_ids() change and all the liveness manipulations into separate patches? They are conceptually completely independent, right? > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > --- > kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++- > 1 file changed, 85 insertions(+), 2 deletions(-) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 6599d25dae38..8a5b7192514a 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) > /* case: R1 = R2 > * copy register state to dest reg > */ > - if (src_reg->type == SCALAR_VALUE && !src_reg->id) > + if (src_reg->type == SCALAR_VALUE && !src_reg->id && > + !tnum_is_const(src_reg->var_off)) > /* Assign src and dst registers the same ID > * that will be used by find_equal_scalars() > * to propagate min/max range. > + * Skip constants to avoid allocation of useless ID. > */ > src_reg->id = ++env->id_gen; > *dst_reg = *src_reg; > @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, > return true; > } > > +/* Scalar ID generation in check_alu_op() and logic of > + * find_equal_scalars() make the following pattern possible: > + * > + * 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 ... ; <-- suppose checkpoint state is created here > + * 7: r9 += r7 > + * 8: *(u64 *)r9 = Y > + * > + * Because of the jump at (4) the verifier would arrive at (6) in two states: > + * I. r6{.id=b}, r7{.id=b} > + * II. r6{.id=a}, r7{.id=b} > + * > + * Relevant facts: > + * - regsafe() matches ID mappings for scalars using check_ids(), this makes > + * states (I) and (II) non-equal; > + * - clean_func_state() removes registers not marked as REG_LIVE_READ from > + * checkpoint states; > + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents); > + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning > + * that parent pointers are copied as well. not too familiar with liveness handling, but is this correct and expected? Should this be fixed instead of REG_LIVE_READ manipulations? > + * > + * Thus, for execution path 1-6: > + * - both r6->parent and r7->parent point to the same register in the parent state (r7); > + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark; I'm trying to understand this. Clearly both r6 and r7 are read. r6 for if (r6 > X) check, r7 for r9 manipulations. Why do we end up not marking one of them as read using a normal logic? I have this bad feeling I'm missing something very important here or we have some bug somewhere else. So please help me understand which one it is. This special liveness manipulation seems wrong. My concern is that if I have some code like r6 = r7; r9 += r6; and I never use r7 anymore after that, then we should be able to forget r7 and treat it as NOT_INIT. But you are saying it's unsafe right now and that doesn't make much sense to me. > + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT). > + * > + * Consequently, when execution path 1-4, 6 reaches (6) in state (II) > + * regsafe() won't be able to see a mismatch in ID mappings. > + * > + * To avoid this issue mark_equal_scalars_as_read() conservatively > + * marks all registers with matching ID as REG_LIVE_READ, thus > + * preserving r6 and r7 in the checkpoint state for the example above. > + */ > +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id) > +{ > + struct bpf_verifier_state *st; > + struct bpf_func_state *state; > + struct bpf_reg_state *reg; > + bool move_up; > + int i = 0; > + > + for (st = vstate, move_up = true; st && move_up; st = st->parent) { > + move_up = false; > + bpf_for_each_reg_in_vstate(st, state, reg, ({ > + if (reg->type == SCALAR_VALUE && reg->id == id && > + !(reg->live & REG_LIVE_READ)) { > + reg->live |= REG_LIVE_READ; > + move_up = true; > + } > + ++i; > + })); > + } > +} > + > static void find_equal_scalars(struct bpf_verifier_state *vstate, > struct bpf_reg_state *known_reg) > { > struct bpf_func_state *state; > struct bpf_reg_state *reg; > + int count = 0; > > bpf_for_each_reg_in_vstate(vstate, state, reg, ({ > - if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) { > *reg = *known_reg; > + ++count; > + } > })); > + > + /* Count equal to 1 means that find_equal_scalars have not > + * found any registers with the same ID (except self), thus > + * the range knowledge have not been transferred and there is > + * no need to preserve registers with the same ID in a parent > + * state. > + */ > + if (count > 1) > + mark_equal_scalars_as_read(vstate->parent, known_reg->id); > } > > static int check_cond_jmp_op(struct bpf_verifier_env *env, > @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > */ > return equal && rold->frameno == rcur->frameno; > > + /* even if two registers are identical the id mapping might diverge > + * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2} > + */ > + if (equal && rold->type == SCALAR_VALUE && rold->id) > + return check_ids(rold->id, rcur->id, idmap); nit: let's teach check_ids() to handle the id == 0 case properly instead of guarding everything with `if (rold->id)`? but also I think this applies not just to SCALARs, right? the memcmp() check above has to be augmented with check_ids() for id and ref_obj_id > + > if (equal) > return true; > > @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > if (env->explore_alu_limits) > return false; > if (rcur->type == SCALAR_VALUE) { > + /* id relations must be preserved, see comment in > + * mark_equal_scalars_as_read() for SCALAR_VALUE example. > + */ > + if (rold->id && !check_ids(rold->id, rcur->id, idmap)) > + return false; > if (!rold->precise) > return true; > /* new val must satisfy old val knowledge */ > -- > 2.34.1 >
On Wed, 2022-11-30 at 16:26 -0800, Andrii Nakryiko wrote: > On Mon, Nov 28, 2022 at 8:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > Prior to this commit the following unsafe example passed verification: > > > > 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 ... ; <-- suppose checkpoint state is created here > > 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 makes the following changes: > > - a call to check_ids() is added in regsafe() for scalar registers case; > > - a function mark_equal_scalars_as_read() is added to ensure that > > registers with identical IDs are preserved in the checkpoint states > > in case when find_equal_scalars() updates register range for several > > registers sharing the same ID. > > > > Fixes tag missing? > > These are tricky changes with subtle details. Let's split check_ids() > change and all the liveness manipulations into separate patches? They > are conceptually completely independent, right? > > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > > --- > > kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++- > > 1 file changed, 85 insertions(+), 2 deletions(-) > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > index 6599d25dae38..8a5b7192514a 100644 > > --- a/kernel/bpf/verifier.c > > +++ b/kernel/bpf/verifier.c > > @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) > > /* case: R1 = R2 > > * copy register state to dest reg > > */ > > - if (src_reg->type == SCALAR_VALUE && !src_reg->id) > > + if (src_reg->type == SCALAR_VALUE && !src_reg->id && > > + !tnum_is_const(src_reg->var_off)) > > /* Assign src and dst registers the same ID > > * that will be used by find_equal_scalars() > > * to propagate min/max range. > > + * Skip constants to avoid allocation of useless ID. > > */ > > src_reg->id = ++env->id_gen; > > *dst_reg = *src_reg; > > @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, > > return true; > > } > > > > +/* Scalar ID generation in check_alu_op() and logic of > > + * find_equal_scalars() make the following pattern possible: > > + * > > + * 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 ... ; <-- suppose checkpoint state is created here > > + * 7: r9 += r7 > > + * 8: *(u64 *)r9 = Y > > + * > > + * Because of the jump at (4) the verifier would arrive at (6) in two states: > > + * I. r6{.id=b}, r7{.id=b} > > + * II. r6{.id=a}, r7{.id=b} > > + * > > + * Relevant facts: > > + * - regsafe() matches ID mappings for scalars using check_ids(), this makes > > + * states (I) and (II) non-equal; > > + * - clean_func_state() removes registers not marked as REG_LIVE_READ from > > + * checkpoint states; > > + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents); > > + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning > > + * that parent pointers are copied as well. > > not too familiar with liveness handling, but is this correct and > expected? Should this be fixed instead of REG_LIVE_READ manipulations? Well, that's what I wanted to ask, actually :) Here is how current logic works: - is_state_visited() has the following two loops in the end: for (j = 0; j <= cur->curframe; j++) { for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++) cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i]; for (i = 0; i < BPF_REG_FP; i++) cur->frame[j]->regs[i].live = REG_LIVE_NONE; } /* all stack frames are accessible from callee, clear them all */ for (j = 0; j <= cur->curframe; j++) { struct bpf_func_state *frame = cur->frame[j]; struct bpf_func_state *newframe = new->frame[j]; for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) { frame->stack[i].spilled_ptr.live = REG_LIVE_NONE; frame->stack[i].spilled_ptr.parent = &newframe->stack[i].spilled_ptr; } } These connect the bpf_reg_state members of the new state with corresponding (index-wise) members of the parent state. - find_equal_scalars() looks as follows: static void find_equal_scalars(struct bpf_verifier_state *vstate, struct bpf_reg_state *known_reg) { struct bpf_func_state *state; struct bpf_reg_state *reg; bpf_for_each_reg_in_vstate(vstate, state, reg, ({ if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) *reg = *known_reg; // <--- full copy, incl. parent pointer })); } - mark_reg_read() updates the ->live field of the *parent* register when called only if ->live field of the *current* register is not marked as written. - in case if register is overwritten it's ->live field is marked as written, e.g. see check_stack_read_fixed_off(). Suppose we have an example: ---- checkpoint ---- r1 = r0 ; now r1.parent == &checkpoint->regs[0] r2 = r1 ; now r2.parent == &checkpoint->regs[0] if (r1 == 0) goto +42 ... Given the above logic only &checkpoint->regs[0] would receive read marks. Although I'm not the original author but this behavior seem to make sense. > > > + * > > + * Thus, for execution path 1-6: > > + * - both r6->parent and r7->parent point to the same register in the parent state (r7); > > + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark; > > I'm trying to understand this. Clearly both r6 and r7 are read. r6 for > if (r6 > X) check, r7 for r9 manipulations. Why do we end up not > marking one of them as read using a normal logic? When (r6 > X) is processed find_equal_scalars() updates parent pointers for all registers with the same ID as r6, in this case only for r7. So, after find_equal_scalars() is done both current state r6 and r7 ->parent point to the r6 of the latest checkpoint state. > > I have this bad feeling I'm missing something very important here or > we have some bug somewhere else. So please help me understand which > one it is. This special liveness manipulation seems wrong. > > My concern is that if I have some code like > > r6 = r7; > r9 += r6; > > and I never use r7 anymore after that, then we should be able to > forget r7 and treat it as NOT_INIT. But you are saying it's unsafe > right now and that doesn't make much sense to me. It is unsafe because of the "spooky action at a distance" produced by a combination of: - allocation of scalar IDs for moves, see check_alu_op() case for 64-bit move; - find_equal_scalars() that propagates range, this one is only executed for conditional jumps. > > > > + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT). > > + * > > + * Consequently, when execution path 1-4, 6 reaches (6) in state (II) > > + * regsafe() won't be able to see a mismatch in ID mappings. > > + * > > + * To avoid this issue mark_equal_scalars_as_read() conservatively > > + * marks all registers with matching ID as REG_LIVE_READ, thus > > + * preserving r6 and r7 in the checkpoint state for the example above. > > + */ > > +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id) > > +{ > > + struct bpf_verifier_state *st; > > + struct bpf_func_state *state; > > + struct bpf_reg_state *reg; > > + bool move_up; > > + int i = 0; > > + > > + for (st = vstate, move_up = true; st && move_up; st = st->parent) { > > + move_up = false; > > + bpf_for_each_reg_in_vstate(st, state, reg, ({ > > + if (reg->type == SCALAR_VALUE && reg->id == id && > > + !(reg->live & REG_LIVE_READ)) { > > + reg->live |= REG_LIVE_READ; > > + move_up = true; > > + } > > + ++i; > > + })); > > + } > > +} > > + > > static void find_equal_scalars(struct bpf_verifier_state *vstate, > > struct bpf_reg_state *known_reg) > > { > > struct bpf_func_state *state; > > struct bpf_reg_state *reg; > > + int count = 0; > > > > bpf_for_each_reg_in_vstate(vstate, state, reg, ({ > > - if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > > + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) { > > *reg = *known_reg; > > + ++count; > > + } > > })); > > + > > + /* Count equal to 1 means that find_equal_scalars have not > > + * found any registers with the same ID (except self), thus > > + * the range knowledge have not been transferred and there is > > + * no need to preserve registers with the same ID in a parent > > + * state. > > + */ > > + if (count > 1) > > + mark_equal_scalars_as_read(vstate->parent, known_reg->id); > > } > > > > static int check_cond_jmp_op(struct bpf_verifier_env *env, > > @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > > */ > > return equal && rold->frameno == rcur->frameno; > > > > + /* even if two registers are identical the id mapping might diverge > > + * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2} > > + */ > > + if (equal && rold->type == SCALAR_VALUE && rold->id) > > + return check_ids(rold->id, rcur->id, idmap); > > nit: let's teach check_ids() to handle the id == 0 case properly > instead of guarding everything with `if (rold->id)`? > > but also I think this applies not just to SCALARs, right? the memcmp() > check above has to be augmented with check_ids() for id and ref_obj_id Yes, it is the same issue as described in [1] as you pointed out. I'll updated it for other branches, but I want the main issue to be sorted out first. [1] https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/ > > > + > > if (equal) > > return true; > > > > @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > > if (env->explore_alu_limits) > > return false; > > if (rcur->type == SCALAR_VALUE) { > > + /* id relations must be preserved, see comment in > > + * mark_equal_scalars_as_read() for SCALAR_VALUE example. > > + */ > > + if (rold->id && !check_ids(rold->id, rcur->id, idmap)) > > + return false; > > if (!rold->precise) > > return true; > > /* new val must satisfy old val knowledge */ > > -- > > 2.34.1 > >
On Thu, 2022-12-01 at 03:14 +0200, Eduard Zingerman wrote: > On Wed, 2022-11-30 at 16:26 -0800, Andrii Nakryiko wrote: > > On Mon, Nov 28, 2022 at 8:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > Prior to this commit the following unsafe example passed verification: > > > > > > 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 ... ; <-- suppose checkpoint state is created here > > > 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 makes the following changes: > > > - a call to check_ids() is added in regsafe() for scalar registers case; > > > - a function mark_equal_scalars_as_read() is added to ensure that > > > registers with identical IDs are preserved in the checkpoint states > > > in case when find_equal_scalars() updates register range for several > > > registers sharing the same ID. > > > > > > > Fixes tag missing? > > > > These are tricky changes with subtle details. Let's split check_ids() > > change and all the liveness manipulations into separate patches? They > > are conceptually completely independent, right? > > > > > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > > > --- > > > kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++- > > > 1 file changed, 85 insertions(+), 2 deletions(-) > > > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > > index 6599d25dae38..8a5b7192514a 100644 > > > --- a/kernel/bpf/verifier.c > > > +++ b/kernel/bpf/verifier.c > > > @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) > > > /* case: R1 = R2 > > > * copy register state to dest reg > > > */ > > > - if (src_reg->type == SCALAR_VALUE && !src_reg->id) > > > + if (src_reg->type == SCALAR_VALUE && !src_reg->id && > > > + !tnum_is_const(src_reg->var_off)) > > > /* Assign src and dst registers the same ID > > > * that will be used by find_equal_scalars() > > > * to propagate min/max range. > > > + * Skip constants to avoid allocation of useless ID. > > > */ > > > src_reg->id = ++env->id_gen; > > > *dst_reg = *src_reg; > > > @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, > > > return true; > > > } > > > > > > +/* Scalar ID generation in check_alu_op() and logic of > > > + * find_equal_scalars() make the following pattern possible: > > > + * > > > + * 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 ... ; <-- suppose checkpoint state is created here > > > + * 7: r9 += r7 > > > + * 8: *(u64 *)r9 = Y > > > + * > > > + * Because of the jump at (4) the verifier would arrive at (6) in two states: > > > + * I. r6{.id=b}, r7{.id=b} > > > + * II. r6{.id=a}, r7{.id=b} > > > + * > > > + * Relevant facts: > > > + * - regsafe() matches ID mappings for scalars using check_ids(), this makes > > > + * states (I) and (II) non-equal; > > > + * - clean_func_state() removes registers not marked as REG_LIVE_READ from > > > + * checkpoint states; > > > + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents); > > > + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning > > > + * that parent pointers are copied as well. > > > > not too familiar with liveness handling, but is this correct and > > expected? Should this be fixed instead of REG_LIVE_READ manipulations? TLDR: - looks like it is safe to avoid bpf_reg_state->parent update when registers are copied, but it has some performance impact. If this impact is acceptable I'd like to move this way are remove mark_equal_scalars_as_read(). - unrelated question: does anything has to be done to __mark_chain_precision to make it know about shared scalar IDs? E.g. in the following case: ... --- checkpoint 1 --- r6 would be marked as precise here r6 = r7 ... --- checkpoint 2 --- r6 won't be marked as precise here ... if r6 < 10 --- checkpoint 3 --- fp[r7] = 42 The additional precision marks could be inferred if additional info is added the jump stack. ----- Long version about bpf_reg_state->parent. All functions that copy register states: - save_register_state() Register is copied to stack spill location. - check_kfunc_mem_size_reg() Makes a tmp register copy, harmless. - sanitize_ptr_alu() Register copy is visible in the speculative branch. - check_alu_op() Register is copied when reg to reg MOV is processed. - find_equal_scalars() Register is copied to the registers with the same ID. Original commit introducing bpf_reg_state->parent: - 679c782de14bd48c19dd74cd1af20a2bc05dd936 2018-08-30 bpf/verifier: per-register parent pointers Updates mark_reg_read() and removes mark_stack_slot_read(). Previous version accessed parent state registers directly using regno w/o any additional manipulations. In this commit: - save_register_state() - does not exist yet, its function is performed by check_stack_write(), has a direct register state copy as in save_register_state(); - check_kfunc_mem_size_reg() - does not exist yet; - sanitize_ptr_alu() - does not exist yet; - check_alu_op() - has a direct register state copy unchanged for reg to reg MOV. Commit introducing find_equal_scalars(): - 75748837b7e56919679e02163f45d5818c644d03 2020-10-09 bpf: Propagate scalar ranges through register assignments. Has a direct register copy *reg = *known_reg. It looks like that for places where registers are copied ->parent change is an unintentional side effect. Removal of this side effect might in theory lead to some additional register read marks, e.g. in this case: r6 = r7 if (r6 > X) goto +42 r5 = r7 ; this would lead to a read mark on r7 not ; present previously. This should not hinder correctness. However, there is some negative performance impact: $ ./veristat -e file,prog,states -f 'states_pct!=0' -C master-baseline.log current.log File Program States (A) States (B) States (DIFF) ------------------------ -------------------------------- ---------- ---------- -------------- bpf_host.o cil_to_netdev 358 455 +97 (+27.09%) bpf_host.o tail_handle_nat_fwd_ipv4 1746 1891 +145 (+8.30%) bpf_host.o tail_handle_nat_fwd_ipv6 709 717 +8 (+1.13%) bpf_host.o tail_nodeport_ipv4_dsr 31 42 +11 (+35.48%) bpf_host.o tail_nodeport_nat_egress_ipv4 2269 2274 +5 (+0.22%) bpf_host.o tail_nodeport_nat_ingress_ipv4 276 316 +40 (+14.49%) bpf_host.o tail_nodeport_nat_ingress_ipv6 243 254 +11 (+4.53%) bpf_lxc.o tail_handle_nat_fwd_ipv4 1746 1891 +145 (+8.30%) bpf_lxc.o tail_handle_nat_fwd_ipv6 709 717 +8 (+1.13%) bpf_lxc.o tail_ipv4_ct_egress 248 251 +3 (+1.21%) bpf_lxc.o tail_ipv4_ct_ingress 248 251 +3 (+1.21%) bpf_lxc.o tail_ipv4_ct_ingress_policy_only 248 251 +3 (+1.21%) bpf_lxc.o tail_nodeport_ipv4_dsr 31 42 +11 (+35.48%) bpf_lxc.o tail_nodeport_nat_ingress_ipv4 276 316 +40 (+14.49%) bpf_lxc.o tail_nodeport_nat_ingress_ipv6 243 254 +11 (+4.53%) bpf_overlay.o tail_handle_nat_fwd_ipv4 1082 1109 +27 (+2.50%) bpf_overlay.o tail_nodeport_ipv4_dsr 31 42 +11 (+35.48%) bpf_overlay.o tail_nodeport_nat_egress_ipv4 2238 2243 +5 (+0.22%) bpf_overlay.o tail_nodeport_nat_ingress_ipv4 276 316 +40 (+14.49%) bpf_overlay.o tail_nodeport_nat_ingress_ipv6 243 254 +11 (+4.53%) bpf_sock.o cil_sock4_connect 47 64 +17 (+36.17%) bpf_sock.o cil_sock4_sendmsg 45 62 +17 (+37.78%) bpf_xdp.o tail_handle_nat_fwd_ipv4 1461 1912 +451 (+30.87%) bpf_xdp.o tail_lb_ipv4 4643 4738 +95 (+2.05%) bpf_xdp.o tail_nodeport_nat_egress_ipv4 1066 1069 +3 (+0.28%) bpf_xdp.o tail_rev_nodeport_lb4 404 411 +7 (+1.73%) bpf_xdp.o tail_rev_nodeport_lb6 1076 1083 +7 (+0.65%) pyperf600_bpf_loop.bpf.o on_event 285 287 +2 (+0.70%) xdp_synproxy_kern.bpf.o syncookie_tc 22513 22564 +51 (+0.23%) xdp_synproxy_kern.bpf.o syncookie_xdp 22207 24206 +1999 (+9.00%) ------------------------ -------------------------------- ---------- ---------- -------------- > > Well, that's what I wanted to ask, actually :) > Here is how current logic works: > - is_state_visited() has the following two loops in the end: > > for (j = 0; j <= cur->curframe; j++) { > for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++) > cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i]; > for (i = 0; i < BPF_REG_FP; i++) > cur->frame[j]->regs[i].live = REG_LIVE_NONE; > } > > /* all stack frames are accessible from callee, clear them all */ > for (j = 0; j <= cur->curframe; j++) { > struct bpf_func_state *frame = cur->frame[j]; > struct bpf_func_state *newframe = new->frame[j]; > > for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) { > frame->stack[i].spilled_ptr.live = REG_LIVE_NONE; > frame->stack[i].spilled_ptr.parent = > &newframe->stack[i].spilled_ptr; > } > } > > These connect the bpf_reg_state members of the new state with > corresponding (index-wise) members of the parent state. > - find_equal_scalars() looks as follows: > static void find_equal_scalars(struct bpf_verifier_state *vstate, > struct bpf_reg_state *known_reg) > { > struct bpf_func_state *state; > struct bpf_reg_state *reg; > > bpf_for_each_reg_in_vstate(vstate, state, reg, ({ > if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > *reg = *known_reg; // <--- full copy, incl. parent pointer > })); > } > - mark_reg_read() updates the ->live field of the *parent* register > when called only if ->live field of the *current* register is not > marked as written. > - in case if register is overwritten it's ->live field is marked as > written, e.g. see check_stack_read_fixed_off(). > > Suppose we have an example: > > ---- checkpoint ---- > r1 = r0 ; now r1.parent == &checkpoint->regs[0] > r2 = r1 ; now r2.parent == &checkpoint->regs[0] > if (r1 == 0) goto +42 > ... > > Given the above logic only &checkpoint->regs[0] would receive read > marks. Although I'm not the original author but this behavior seem to > make sense. > > > > > > + * > > > + * Thus, for execution path 1-6: > > > + * - both r6->parent and r7->parent point to the same register in the parent state (r7); > > > + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark; > > > > I'm trying to understand this. Clearly both r6 and r7 are read. r6 for > > if (r6 > X) check, r7 for r9 manipulations. Why do we end up not > > marking one of them as read using a normal logic? > > When (r6 > X) is processed find_equal_scalars() updates parent > pointers for all registers with the same ID as r6, in this case only > for r7. So, after find_equal_scalars() is done both current state r6 > and r7 ->parent point to the r6 of the latest checkpoint state. > > > > > I have this bad feeling I'm missing something very important here or > > we have some bug somewhere else. So please help me understand which > > one it is. This special liveness manipulation seems wrong. > > > > My concern is that if I have some code like > > > > r6 = r7; > > r9 += r6; > > > > and I never use r7 anymore after that, then we should be able to > > forget r7 and treat it as NOT_INIT. But you are saying it's unsafe > > right now and that doesn't make much sense to me. > > It is unsafe because of the "spooky action at a distance" produced by > a combination of: > - allocation of scalar IDs for moves, see check_alu_op() case for > 64-bit move; > - find_equal_scalars() that propagates range, this one is only > executed for conditional jumps. > > > > > > > > + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT). > > > + * > > > + * Consequently, when execution path 1-4, 6 reaches (6) in state (II) > > > + * regsafe() won't be able to see a mismatch in ID mappings. > > > + * > > > + * To avoid this issue mark_equal_scalars_as_read() conservatively > > > + * marks all registers with matching ID as REG_LIVE_READ, thus > > > + * preserving r6 and r7 in the checkpoint state for the example above. > > > + */ > > > +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id) > > > +{ > > > + struct bpf_verifier_state *st; > > > + struct bpf_func_state *state; > > > + struct bpf_reg_state *reg; > > > + bool move_up; > > > + int i = 0; > > > + > > > + for (st = vstate, move_up = true; st && move_up; st = st->parent) { > > > + move_up = false; > > > + bpf_for_each_reg_in_vstate(st, state, reg, ({ > > > + if (reg->type == SCALAR_VALUE && reg->id == id && > > > + !(reg->live & REG_LIVE_READ)) { > > > + reg->live |= REG_LIVE_READ; > > > + move_up = true; > > > + } > > > + ++i; > > > + })); > > > + } > > > +} > > > + > > > static void find_equal_scalars(struct bpf_verifier_state *vstate, > > > struct bpf_reg_state *known_reg) > > > { > > > struct bpf_func_state *state; > > > struct bpf_reg_state *reg; > > > + int count = 0; > > > > > > bpf_for_each_reg_in_vstate(vstate, state, reg, ({ > > > - if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > > > + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) { > > > *reg = *known_reg; > > > + ++count; > > > + } > > > })); > > > + > > > + /* Count equal to 1 means that find_equal_scalars have not > > > + * found any registers with the same ID (except self), thus > > > + * the range knowledge have not been transferred and there is > > > + * no need to preserve registers with the same ID in a parent > > > + * state. > > > + */ > > > + if (count > 1) > > > + mark_equal_scalars_as_read(vstate->parent, known_reg->id); > > > } > > > > > > static int check_cond_jmp_op(struct bpf_verifier_env *env, > > > @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > > > */ > > > return equal && rold->frameno == rcur->frameno; > > > > > > + /* even if two registers are identical the id mapping might diverge > > > + * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2} > > > + */ > > > + if (equal && rold->type == SCALAR_VALUE && rold->id) > > > + return check_ids(rold->id, rcur->id, idmap); > > > > nit: let's teach check_ids() to handle the id == 0 case properly > > instead of guarding everything with `if (rold->id)`? > > > > but also I think this applies not just to SCALARs, right? the memcmp() > > check above has to be augmented with check_ids() for id and ref_obj_id > > Yes, it is the same issue as described in [1] as you pointed out. > I'll updated it for other branches, but I want the main issue to > be sorted out first. > > [1] https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/ > > > > > > + > > > if (equal) > > > return true; > > > > > > @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > > > if (env->explore_alu_limits) > > > return false; > > > if (rcur->type == SCALAR_VALUE) { > > > + /* id relations must be preserved, see comment in > > > + * mark_equal_scalars_as_read() for SCALAR_VALUE example. > > > + */ > > > + if (rold->id && !check_ids(rold->id, rcur->id, idmap)) > > > + return false; > > > if (!rold->precise) > > > return true; > > > /* new val must satisfy old val knowledge */ > > > -- > > > 2.34.1 > > > >
On Thu, 2022-12-01 at 20:33 +0200, Eduard Zingerman wrote: > On Thu, 2022-12-01 at 03:14 +0200, Eduard Zingerman wrote: > > On Wed, 2022-11-30 at 16:26 -0800, Andrii Nakryiko wrote: > > > On Mon, Nov 28, 2022 at 8:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > > > Prior to this commit the following unsafe example passed verification: > > > > > > > > 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 ... ; <-- suppose checkpoint state is created here > > > > 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 makes the following changes: > > > > - a call to check_ids() is added in regsafe() for scalar registers case; > > > > - a function mark_equal_scalars_as_read() is added to ensure that > > > > registers with identical IDs are preserved in the checkpoint states > > > > in case when find_equal_scalars() updates register range for several > > > > registers sharing the same ID. > > > > > > > > > > Fixes tag missing? > > > > > > These are tricky changes with subtle details. Let's split check_ids() > > > change and all the liveness manipulations into separate patches? They > > > are conceptually completely independent, right? > > > > > > > > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > > > > --- > > > > kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++- > > > > 1 file changed, 85 insertions(+), 2 deletions(-) > > > > > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > > > index 6599d25dae38..8a5b7192514a 100644 > > > > --- a/kernel/bpf/verifier.c > > > > +++ b/kernel/bpf/verifier.c > > > > @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) > > > > /* case: R1 = R2 > > > > * copy register state to dest reg > > > > */ > > > > - if (src_reg->type == SCALAR_VALUE && !src_reg->id) > > > > + if (src_reg->type == SCALAR_VALUE && !src_reg->id && > > > > + !tnum_is_const(src_reg->var_off)) > > > > /* Assign src and dst registers the same ID > > > > * that will be used by find_equal_scalars() > > > > * to propagate min/max range. > > > > + * Skip constants to avoid allocation of useless ID. > > > > */ > > > > src_reg->id = ++env->id_gen; > > > > *dst_reg = *src_reg; > > > > @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, > > > > return true; > > > > } > > > > > > > > +/* Scalar ID generation in check_alu_op() and logic of > > > > + * find_equal_scalars() make the following pattern possible: > > > > + * > > > > + * 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 ... ; <-- suppose checkpoint state is created here > > > > + * 7: r9 += r7 > > > > + * 8: *(u64 *)r9 = Y > > > > + * > > > > + * Because of the jump at (4) the verifier would arrive at (6) in two states: > > > > + * I. r6{.id=b}, r7{.id=b} > > > > + * II. r6{.id=a}, r7{.id=b} > > > > + * > > > > + * Relevant facts: > > > > + * - regsafe() matches ID mappings for scalars using check_ids(), this makes > > > > + * states (I) and (II) non-equal; > > > > + * - clean_func_state() removes registers not marked as REG_LIVE_READ from > > > > + * checkpoint states; > > > > + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents); > > > > + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning > > > > + * that parent pointers are copied as well. > > > > > > not too familiar with liveness handling, but is this correct and > > > expected? Should this be fixed instead of REG_LIVE_READ manipulations? > > > TLDR: > > - looks like it is safe to avoid bpf_reg_state->parent update when > registers are copied, but it has some performance impact. If this > impact is acceptable I'd like to move this way are remove > mark_equal_scalars_as_read(). > > - unrelated question: does anything has to be done to > __mark_chain_precision to make it know about shared scalar IDs? > E.g. in the following case: > ... > --- checkpoint 1 --- r6 would be marked as precise here > r6 = r7 > ... > --- checkpoint 2 --- r6 won't be marked as precise here > ... > if r6 < 10 > --- checkpoint 3 --- > fp[r7] = 42 > > The additional precision marks could be inferred if additional info > is added the jump stack. > > ----- > Long version about bpf_reg_state->parent. > > All functions that copy register states: > - save_register_state() > Register is copied to stack spill location. > > - check_kfunc_mem_size_reg() > Makes a tmp register copy, harmless. > > - sanitize_ptr_alu() > Register copy is visible in the speculative branch. > > - check_alu_op() > Register is copied when reg to reg MOV is processed. > > - find_equal_scalars() > Register is copied to the registers with the same ID. > > Original commit introducing bpf_reg_state->parent: > - 679c782de14bd48c19dd74cd1af20a2bc05dd936 2018-08-30 > bpf/verifier: per-register parent pointers > > Updates mark_reg_read() and removes mark_stack_slot_read(). > Previous version accessed parent state registers directly using > regno w/o any additional manipulations. > > In this commit: > - save_register_state() - does not exist yet, its function is > performed by check_stack_write(), has a direct register state copy > as in save_register_state(); > - check_kfunc_mem_size_reg() - does not exist yet; > - sanitize_ptr_alu() - does not exist yet; > - check_alu_op() - has a direct register state copy unchanged for > reg to reg MOV. > > Commit introducing find_equal_scalars(): > - 75748837b7e56919679e02163f45d5818c644d03 2020-10-09 > bpf: Propagate scalar ranges through register assignments. > > Has a direct register copy *reg = *known_reg. > > It looks like that for places where registers are copied ->parent > change is an unintentional side effect. Removal of this side effect > might in theory lead to some additional register read marks, e.g. in > this case: > > r6 = r7 > if (r6 > X) goto +42 > r5 = r7 ; this would lead to a read mark on r7 not > ; present previously. > Upon detailed examination of the differences in tests behaviour with and without preserving register parentage chains I came up with the following test case: { "write tracking and register parent chain bug", .insns = { /* r6 = ktime_get_ns() */ BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns), BPF_MOV64_REG(BPF_REG_6, BPF_REG_0), /* r0 = ktime_get_ns() */ BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns), /* if r0 > r6 goto +1 */ BPF_JMP_REG(BPF_JGT, BPF_REG_0, BPF_REG_6, 1), /* *(u64 *)(r10 - 8) = 0xdeadbeef */ BPF_ST_MEM(BPF_DW, BPF_REG_FP, -8, 0xdeadbeef), /* r1 = 42 */ BPF_MOV64_IMM(BPF_REG_1, 42), /* *(u8 *)(r10 - 8) = r1 */ BPF_STX_MEM(BPF_B, BPF_REG_FP, BPF_REG_1, -8), /* r2 = *(u64 *)(r10 - 8) */ BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_FP, -8), /* exit(0) */ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, .flags = BPF_F_TEST_STATE_FREQ, .errstr = "invalid read from stack off -8+1 size 8", .result = REJECT, }, This test case is currently marked as safe, which is not true, because the write of 0xdeadbeef to fp[-8] might be omitted. The bug is caused by tossing around the register parent pointers. So there is no real choice here, this behaviour has to be changed. I'll submit a separate patch shortly. > This should not hinder correctness. > However, there is some negative performance impact: > > $ ./veristat -e file,prog,states -f 'states_pct!=0' -C master-baseline.log current.log > File Program States (A) States (B) States (DIFF) > ------------------------ -------------------------------- ---------- ---------- -------------- > bpf_host.o cil_to_netdev 358 455 +97 (+27.09%) > bpf_host.o tail_handle_nat_fwd_ipv4 1746 1891 +145 (+8.30%) > bpf_host.o tail_handle_nat_fwd_ipv6 709 717 +8 (+1.13%) > bpf_host.o tail_nodeport_ipv4_dsr 31 42 +11 (+35.48%) > bpf_host.o tail_nodeport_nat_egress_ipv4 2269 2274 +5 (+0.22%) > bpf_host.o tail_nodeport_nat_ingress_ipv4 276 316 +40 (+14.49%) > bpf_host.o tail_nodeport_nat_ingress_ipv6 243 254 +11 (+4.53%) > bpf_lxc.o tail_handle_nat_fwd_ipv4 1746 1891 +145 (+8.30%) > bpf_lxc.o tail_handle_nat_fwd_ipv6 709 717 +8 (+1.13%) > bpf_lxc.o tail_ipv4_ct_egress 248 251 +3 (+1.21%) > bpf_lxc.o tail_ipv4_ct_ingress 248 251 +3 (+1.21%) > bpf_lxc.o tail_ipv4_ct_ingress_policy_only 248 251 +3 (+1.21%) > bpf_lxc.o tail_nodeport_ipv4_dsr 31 42 +11 (+35.48%) > bpf_lxc.o tail_nodeport_nat_ingress_ipv4 276 316 +40 (+14.49%) > bpf_lxc.o tail_nodeport_nat_ingress_ipv6 243 254 +11 (+4.53%) > bpf_overlay.o tail_handle_nat_fwd_ipv4 1082 1109 +27 (+2.50%) > bpf_overlay.o tail_nodeport_ipv4_dsr 31 42 +11 (+35.48%) > bpf_overlay.o tail_nodeport_nat_egress_ipv4 2238 2243 +5 (+0.22%) > bpf_overlay.o tail_nodeport_nat_ingress_ipv4 276 316 +40 (+14.49%) > bpf_overlay.o tail_nodeport_nat_ingress_ipv6 243 254 +11 (+4.53%) > bpf_sock.o cil_sock4_connect 47 64 +17 (+36.17%) > bpf_sock.o cil_sock4_sendmsg 45 62 +17 (+37.78%) > bpf_xdp.o tail_handle_nat_fwd_ipv4 1461 1912 +451 (+30.87%) > bpf_xdp.o tail_lb_ipv4 4643 4738 +95 (+2.05%) > bpf_xdp.o tail_nodeport_nat_egress_ipv4 1066 1069 +3 (+0.28%) > bpf_xdp.o tail_rev_nodeport_lb4 404 411 +7 (+1.73%) > bpf_xdp.o tail_rev_nodeport_lb6 1076 1083 +7 (+0.65%) > pyperf600_bpf_loop.bpf.o on_event 285 287 +2 (+0.70%) > xdp_synproxy_kern.bpf.o syncookie_tc 22513 22564 +51 (+0.23%) > xdp_synproxy_kern.bpf.o syncookie_xdp 22207 24206 +1999 (+9.00%) > ------------------------ -------------------------------- ---------- ---------- -------------- > > > > > Well, that's what I wanted to ask, actually :) > > Here is how current logic works: > > - is_state_visited() has the following two loops in the end: > > > > for (j = 0; j <= cur->curframe; j++) { > > for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++) > > cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i]; > > for (i = 0; i < BPF_REG_FP; i++) > > cur->frame[j]->regs[i].live = REG_LIVE_NONE; > > } > > > > /* all stack frames are accessible from callee, clear them all */ > > for (j = 0; j <= cur->curframe; j++) { > > struct bpf_func_state *frame = cur->frame[j]; > > struct bpf_func_state *newframe = new->frame[j]; > > > > for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) { > > frame->stack[i].spilled_ptr.live = REG_LIVE_NONE; > > frame->stack[i].spilled_ptr.parent = > > &newframe->stack[i].spilled_ptr; > > } > > } > > > > These connect the bpf_reg_state members of the new state with > > corresponding (index-wise) members of the parent state. > > - find_equal_scalars() looks as follows: > > static void find_equal_scalars(struct bpf_verifier_state *vstate, > > struct bpf_reg_state *known_reg) > > { > > struct bpf_func_state *state; > > struct bpf_reg_state *reg; > > > > bpf_for_each_reg_in_vstate(vstate, state, reg, ({ > > if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > > *reg = *known_reg; // <--- full copy, incl. parent pointer > > })); > > } > > - mark_reg_read() updates the ->live field of the *parent* register > > when called only if ->live field of the *current* register is not > > marked as written. > > - in case if register is overwritten it's ->live field is marked as > > written, e.g. see check_stack_read_fixed_off(). > > > > Suppose we have an example: > > > > ---- checkpoint ---- > > r1 = r0 ; now r1.parent == &checkpoint->regs[0] > > r2 = r1 ; now r2.parent == &checkpoint->regs[0] > > if (r1 == 0) goto +42 > > ... > > > > Given the above logic only &checkpoint->regs[0] would receive read > > marks. Although I'm not the original author but this behavior seem to > > make sense. > > > > > > > > > + * > > > > + * Thus, for execution path 1-6: > > > > + * - both r6->parent and r7->parent point to the same register in the parent state (r7); > > > > + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark; > > > > > > I'm trying to understand this. Clearly both r6 and r7 are read. r6 for > > > if (r6 > X) check, r7 for r9 manipulations. Why do we end up not > > > marking one of them as read using a normal logic? > > > > When (r6 > X) is processed find_equal_scalars() updates parent > > pointers for all registers with the same ID as r6, in this case only > > for r7. So, after find_equal_scalars() is done both current state r6 > > and r7 ->parent point to the r6 of the latest checkpoint state. > > > > > > > > I have this bad feeling I'm missing something very important here or > > > we have some bug somewhere else. So please help me understand which > > > one it is. This special liveness manipulation seems wrong. > > > > > > My concern is that if I have some code like > > > > > > r6 = r7; > > > r9 += r6; > > > > > > and I never use r7 anymore after that, then we should be able to > > > forget r7 and treat it as NOT_INIT. But you are saying it's unsafe > > > right now and that doesn't make much sense to me. > > > > It is unsafe because of the "spooky action at a distance" produced by > > a combination of: > > - allocation of scalar IDs for moves, see check_alu_op() case for > > 64-bit move; > > - find_equal_scalars() that propagates range, this one is only > > executed for conditional jumps. > > > > > > > > > > > > + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT). > > > > + * > > > > + * Consequently, when execution path 1-4, 6 reaches (6) in state (II) > > > > + * regsafe() won't be able to see a mismatch in ID mappings. > > > > + * > > > > + * To avoid this issue mark_equal_scalars_as_read() conservatively > > > > + * marks all registers with matching ID as REG_LIVE_READ, thus > > > > + * preserving r6 and r7 in the checkpoint state for the example above. > > > > + */ > > > > +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id) > > > > +{ > > > > + struct bpf_verifier_state *st; > > > > + struct bpf_func_state *state; > > > > + struct bpf_reg_state *reg; > > > > + bool move_up; > > > > + int i = 0; > > > > + > > > > + for (st = vstate, move_up = true; st && move_up; st = st->parent) { > > > > + move_up = false; > > > > + bpf_for_each_reg_in_vstate(st, state, reg, ({ > > > > + if (reg->type == SCALAR_VALUE && reg->id == id && > > > > + !(reg->live & REG_LIVE_READ)) { > > > > + reg->live |= REG_LIVE_READ; > > > > + move_up = true; > > > > + } > > > > + ++i; > > > > + })); > > > > + } > > > > +} > > > > + > > > > static void find_equal_scalars(struct bpf_verifier_state *vstate, > > > > struct bpf_reg_state *known_reg) > > > > { > > > > struct bpf_func_state *state; > > > > struct bpf_reg_state *reg; > > > > + int count = 0; > > > > > > > > bpf_for_each_reg_in_vstate(vstate, state, reg, ({ > > > > - if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > > > > + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) { > > > > *reg = *known_reg; > > > > + ++count; > > > > + } > > > > })); > > > > + > > > > + /* Count equal to 1 means that find_equal_scalars have not > > > > + * found any registers with the same ID (except self), thus > > > > + * the range knowledge have not been transferred and there is > > > > + * no need to preserve registers with the same ID in a parent > > > > + * state. > > > > + */ > > > > + if (count > 1) > > > > + mark_equal_scalars_as_read(vstate->parent, known_reg->id); > > > > } > > > > > > > > static int check_cond_jmp_op(struct bpf_verifier_env *env, > > > > @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > > > > */ > > > > return equal && rold->frameno == rcur->frameno; > > > > > > > > + /* even if two registers are identical the id mapping might diverge > > > > + * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2} > > > > + */ > > > > + if (equal && rold->type == SCALAR_VALUE && rold->id) > > > > + return check_ids(rold->id, rcur->id, idmap); > > > > > > nit: let's teach check_ids() to handle the id == 0 case properly > > > instead of guarding everything with `if (rold->id)`? > > > > > > but also I think this applies not just to SCALARs, right? the memcmp() > > > check above has to be augmented with check_ids() for id and ref_obj_id > > > > Yes, it is the same issue as described in [1] as you pointed out. > > I'll updated it for other branches, but I want the main issue to > > be sorted out first. > > > > [1] https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/ > > > > > > > > > + > > > > if (equal) > > > > return true; > > > > > > > > @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, > > > > if (env->explore_alu_limits) > > > > return false; > > > > if (rcur->type == SCALAR_VALUE) { > > > > + /* id relations must be preserved, see comment in > > > > + * mark_equal_scalars_as_read() for SCALAR_VALUE example. > > > > + */ > > > > + if (rold->id && !check_ids(rold->id, rcur->id, idmap)) > > > > + return false; > > > > if (!rold->precise) > > > > return true; > > > > /* new val must satisfy old val knowledge */ > > > > -- > > > > 2.34.1 > > > > > > >
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 6599d25dae38..8a5b7192514a 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) /* case: R1 = R2 * copy register state to dest reg */ - if (src_reg->type == SCALAR_VALUE && !src_reg->id) + if (src_reg->type == SCALAR_VALUE && !src_reg->id && + !tnum_is_const(src_reg->var_off)) /* Assign src and dst registers the same ID * that will be used by find_equal_scalars() * to propagate min/max range. + * Skip constants to avoid allocation of useless ID. */ src_reg->id = ++env->id_gen; *dst_reg = *src_reg; @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, return true; } +/* Scalar ID generation in check_alu_op() and logic of + * find_equal_scalars() make the following pattern possible: + * + * 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 ... ; <-- suppose checkpoint state is created here + * 7: r9 += r7 + * 8: *(u64 *)r9 = Y + * + * Because of the jump at (4) the verifier would arrive at (6) in two states: + * I. r6{.id=b}, r7{.id=b} + * II. r6{.id=a}, r7{.id=b} + * + * Relevant facts: + * - regsafe() matches ID mappings for scalars using check_ids(), this makes + * states (I) and (II) non-equal; + * - clean_func_state() removes registers not marked as REG_LIVE_READ from + * checkpoint states; + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents); + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning + * that parent pointers are copied as well. + * + * Thus, for execution path 1-6: + * - both r6->parent and r7->parent point to the same register in the parent state (r7); + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark; + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT). + * + * Consequently, when execution path 1-4, 6 reaches (6) in state (II) + * regsafe() won't be able to see a mismatch in ID mappings. + * + * To avoid this issue mark_equal_scalars_as_read() conservatively + * marks all registers with matching ID as REG_LIVE_READ, thus + * preserving r6 and r7 in the checkpoint state for the example above. + */ +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id) +{ + struct bpf_verifier_state *st; + struct bpf_func_state *state; + struct bpf_reg_state *reg; + bool move_up; + int i = 0; + + for (st = vstate, move_up = true; st && move_up; st = st->parent) { + move_up = false; + bpf_for_each_reg_in_vstate(st, state, reg, ({ + if (reg->type == SCALAR_VALUE && reg->id == id && + !(reg->live & REG_LIVE_READ)) { + reg->live |= REG_LIVE_READ; + move_up = true; + } + ++i; + })); + } +} + static void find_equal_scalars(struct bpf_verifier_state *vstate, struct bpf_reg_state *known_reg) { struct bpf_func_state *state; struct bpf_reg_state *reg; + int count = 0; bpf_for_each_reg_in_vstate(vstate, state, reg, ({ - if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) { *reg = *known_reg; + ++count; + } })); + + /* Count equal to 1 means that find_equal_scalars have not + * found any registers with the same ID (except self), thus + * the range knowledge have not been transferred and there is + * no need to preserve registers with the same ID in a parent + * state. + */ + if (count > 1) + mark_equal_scalars_as_read(vstate->parent, known_reg->id); } static int check_cond_jmp_op(struct bpf_verifier_env *env, @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, */ return equal && rold->frameno == rcur->frameno; + /* even if two registers are identical the id mapping might diverge + * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2} + */ + if (equal && rold->type == SCALAR_VALUE && rold->id) + return check_ids(rold->id, rcur->id, idmap); + if (equal) return true; @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, if (env->explore_alu_limits) return false; if (rcur->type == SCALAR_VALUE) { + /* id relations must be preserved, see comment in + * mark_equal_scalars_as_read() for SCALAR_VALUE example. + */ + if (rold->id && !check_ids(rold->id, rcur->id, idmap)) + return false; if (!rold->precise) return true; /* new val must satisfy old val knowledge */
Prior to this commit the following unsafe example passed verification: 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 ... ; <-- suppose checkpoint state is created here 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 makes the following changes: - a call to check_ids() is added in regsafe() for scalar registers case; - a function mark_equal_scalars_as_read() is added to ensure that registers with identical IDs are preserved in the checkpoint states in case when find_equal_scalars() updates register range for several registers sharing the same ID. Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> --- kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 85 insertions(+), 2 deletions(-)