bpf: verify scalar ids mapping in regsafe()
Subsystems (4)
Eduard Zingerman
maintainercover bpf: verify scalar ids mapping in regsafe()
Update regsafe() to use check_ids() for scalar values. Otherwise the following unsafe pattern is accepted 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
See patch #1 for detailed description.
The change has limited impact on verification performance. Here is veristat log comparing this patch with current master on a set of selftest binaries listed in tools/testing/selftests/bpf/veristat.cfg and cilium BPF binaries (see [1]):
$ ./veristat -e file,prog,states -f 'insns_pct>1' -C master-baseline.log current.log File Program States (A) States (B) States (DIFF) ------------------------ ------------------------------ ---------- ---------- --------------- bpf_xdp.o tail_handle_nat_fwd_ipv6 648 660 +12 (+1.85%) bpf_xdp.o tail_nodeport_nat_ingress_ipv4 375 455 +80 (+21.33%) bpf_xdp.o tail_rev_nodeport_lb4 398 472 +74 (+18.59%) pyperf600_nounroll.bpf.o on_event 34169 39465 +5296 (+15.50%) test_verif_scale1.bpf.o balancer_ingress 8636 8942 +306 (+3.54%) test_verif_scale2.bpf.o balancer_ingress 3048 3149 +101 (+3.31%) test_verif_scale3.bpf.o balancer_ingress 8636 8942 +306 (+3.54%)
This was previously posted as an RFC [2].
Changelog:
- RFC -> V1:
- Function verifier.c:mark_equal_scalars_as_read() is dropped, as it was an incorrect fix for problem solved by commit [3].
- check_ids() is called only for precise scalar values.
- Test case updated to use inline assembly.
[1] [email protected]:anakryiko/cilium.git
[2] https://lore.kernel.org/bpf/[email protected]/
[3] commit 71f656a50176 ("bpf: Fix to preserve reg parent/live fields when copying range info")
Eduard Zingerman (2):
bpf: verify scalar ids mapping in regsafe() using check_ids() selftests/bpf: verify that check_ids() is used for scalars in
regsafe()
kernel/bpf/verifier.c | 31 +++++++++- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 59 +++++++++++++++++++ 3 files changed, 91 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
Signature · 1 line
2.40.1
Eduard Zingerman
maintainerPATCH 1/2 bpf: verify scalar ids mapping in regsafe() using check_ids()
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 scalar registers.
The change in check_alu_op() to avoid assigning scalar id to constants is performance optimization. W/o it the regsafe() change becomes costly for some programs, e.g. for tools/testing/selftests/bpf/progs/pyperf600.c the difference is:
File Program States (A) States (B) States (DIFF) --------------- -------- ---------- ---------- ---------------- pyperf600.bpf.o on_event 22200 37060 +14860 (+66.94%)
Where A -- this patch,
B -- this patch but w/o check_alu_op() changes.
--- kernel/bpf/verifier.c | 31 ++++++++++++++++++++++++++++++- 1 file changed, 30 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +30 -1
@@ -12806,10 +12806,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;copy_register_state (dst_reg, src_reg);
@@ -15151,6 +15153,33 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : +/* Why check_ids() for precise 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 would start from (5), because of the jump at (3). +* The only state difference between first and second visits of (5) is +* bpf_reg_state::id assignments for r6 and r7: (b, b) vs (a, b). +* Thus, use check_ids() to distinguish these states. +* +* The `rold->precise` check is a performance optimization. If `rold->id` +* was ever used to access memory / predict jump, the `rold` or any +* register used in `rold = r?` / `r? = rold` operations would be marked +* as precise, otherwise it's ID is not really interesting. +*/ +if (rold->precise && rold->id && !check_ids (rold->id, rcur->id, idmap)) +return false;if (regs_exact (rold, rcur, idmap))return true;if (env->explore_alu_limits)
Signature · 1 line
2.40.1
Re: [PATCH bpf-next v1 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 48 lines · 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 = YThis 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 callcheck_ids()for scalar registers, thus from POV ofregsafe()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 callcheck_ids()for scalar registers.The change in
check_alu_op()to avoid assigning scalar id to constants is performance optimization. W/o it theregsafe()change becomes costly for some programs, e.g. fortools/testing/selftests/bpf/progs/pyperf600.cthe difference is:File Program States (A) States (B) States (DIFF) --------------- -------- ---------- ---------- ---------------- pyperf600.bpf.o on_event 22200 37060 +14860 (+66.94%)Where A -- this patch,
B -- this patch but w/ocheck_alu_op()changes.Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Signed-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 31 ++++++++++++++++++++++++++++++- 1 file changed, 30 insertions(+), 1 deletion(-)kernel/bpf/verifier.c +0
-0@@ -12806,10 +12806,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)/* case: R1 = R2
kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 12815
Quoted 10 lines
kernel/bpf/verifier.c +3
-1* 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. */
The above is for ALU64.
We also have ALU32 version:
} 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)
src_reg->id = ++env->id_gen;
copy_register_state(dst_reg, src_reg);
...Do you think we should do the same thing if src_reg is a constant, not to change src_reg->id?
If this is added, could you have a test case for 32-bit subregister as well?
Quoted 22 lines
kernel/bpf/verifier.c +16
-0src_reg->id = ++env->id_gen;copy_register_state (dst_reg, src_reg);@@ -15151,6 +15153,33 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : +/* Why check_ids() for precise 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 would start from (5), because of the jump at (3).
kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 15181
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* The only state difference between first and second visits of (5) is +* bpf_reg_state::id assignments for r6 and r7: (b, b) vs (a, b). +* Thus, use check_ids() to distinguish these states. +* +* The `rold->precise` check is a performance optimization. If `rold->id` +* was ever used to access memory / predict jump, the `rold` or any +* register used in `rold = r?` / `r? = rold` operations would be marked +* as precise, otherwise it's ID is not really interesting. +*/ +if (rold->precise && rold->id && !check_ids (rold->id, rcur->id, idmap))
Do we need rold->id checking in the above? check_ids should have rold->id = 0 properly. Or this is just an optimization?
regs_exact() has check_ids as well. Not sure whether it makes sense to create a function regs_exact_scalar() just for scalar and include the above code. Otherwise, it is strange we do check_ids in different places.
Quoted 4 lines
kernel/bpf/verifier.c +1
-0+return false;if (regs_exact (rold, rcur, idmap))return true;if (env->explore_alu_limits)
Eduard Zingerman
maintainerRe: [PATCH bpf-next v1 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 72 lines · Yonghong Song
Quoted 48 lines · 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 = YThis 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 callcheck_ids()for scalar registers, thus from POV ofregsafe()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 callcheck_ids()for scalar registers.The change in
check_alu_op()to avoid assigning scalar id to constants is performance optimization. W/o it theregsafe()change becomes costly for some programs, e.g. fortools/testing/selftests/bpf/progs/pyperf600.cthe difference is:File Program States (A) States (B) States (DIFF) --------------- -------- ---------- ---------- ---------------- pyperf600.bpf.o on_event 22200 37060 +14860 (+66.94%)Where A -- this patch,
B -- this patch but w/ocheck_alu_op()changes.Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Signed-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 31 ++++++++++++++++++++++++++++++- 1 file changed, 30 insertions(+), 1 deletion(-)kernel/bpf/verifier.c +0
-0@@ -12806,10 +12806,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)/* case: R1 = R2 kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 12815
Quoted 10 lines
kernel/bpf/verifier.c +3
-1* 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. */ The above is for ALU64.
We also have ALU32 version:
} 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) src_reg->id = ++env->id_gen; copy_register_state(dst_reg, src_reg); ...
Quoted 2 lines
Do you think we should do the same thing if
src_regis a constant, not to changesrc_reg->id?
This is a good point, thank you. Adding the same check for 32-bit case actually helps with the verifier performance a bit:
$ ./veristat -e file,prog,states -f 'insns_pct>1' -C master-baseline.log current.log File Program States (A) States (B) States (DIFF) --------- ------------------------------ ---------- ---------- ------------- bpf_xdp.o tail_handle_nat_fwd_ipv6 648 660 +12 (+1.85%) bpf_xdp.o tail_nodeport_nat_ingress_ipv4 375 455 +80 (+21.33%) bpf_xdp.o tail_rev_nodeport_lb4 398 472 +74 (+18.59%)
(all +1% - +3% cases from the cover letter are gone).
Quoted 2 lines
If this is added, could you have a test case for 32-bit subregister as well?
I will add the 32-bit test case.
Quoted 28 lines
Quoted 28 lines
kernel/bpf/verifier.c +21
-0src_reg->id = ++env->id_gen;copy_register_state (dst_reg, src_reg);@@ -15151,6 +15153,33 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : +/* Why check_ids() for precise 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 would start from (5), because of the jump at (3). +* The only state difference between first and second visits of (5) is +* bpf_reg_state::id assignments for r6 and r7: (b, b) vs (a, b). +* Thus, use check_ids() to distinguish these states. +* +* The `rold->precise` check is a performance optimization. If `rold->id`
Quoted 8 lines
kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 15181
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+* was ever used to access memory / predict jump, the `rold` or any +* register used in `rold = r?` / `r? = rold` operations would be marked +* as precise, otherwise it's ID is not really interesting. +*/ +if (rold->precise && rold->id && !check_ids (rold->id, rcur->id, idmap))Do we need
rold->idchecking in the above?check_idsshould haverold->id= 0 properly. Or this is just an optimization?
You are correct, the check_ids() handles this case and it should be inlined, so there is no need to check rold->id in this 'if' branch.
Quoted 4 lines
regs_exact()hascheck_idsas well. Not sure whether it makes sense to create a functionregs_exact_scalar()just for scalar and include the above code. Otherwise, it is strange we docheck_idsin different places.
I'm not sure how to best re-organize code here, regs_exact() is a nice compartmentalized abstraction. It is possible to merge my additional check_ids() call with the main 'precise' processing part as below:
@@ -15152,21 +15154,22 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
switch (base_type(rold->type)) {
case SCALAR_VALUE:
if (regs_exact(rold, rcur, idmap))
return true;
if (env->explore_alu_limits)
return false;
if (!rold->precise)
return true;
/* new val must satisfy old val 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);I'd say that extending /* new val must satisfy ... */ comment to explain why check_ids() is needed should be sufficient, but I'm open for suggestions.
Quoted 5 lines
Quoted 5 lines
kernel/bpf/verifier.c +1
-0+return false;if (regs_exact (rold, rcur, idmap))return true;if (env->explore_alu_limits)
Eduard Zingerman
maintainerRe: [PATCH bpf-next v1 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()
On Sat, 2023-05-27 at 15:21 +0300, Eduard Zingerman wrote:
[...]
Quoted 61 lines
Quoted 25 lines
Quoted 25 lines
kernel/bpf/verifier.c +21
-0@@ -15151,6 +15153,33 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : +/* Why check_ids() for precise 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 would start from (5), because of the jump at (3). +* The only state difference between first and second visits of (5) is +* bpf_reg_state::id assignments for r6 and r7: (b, b) vs (a, b). +* Thus, use check_ids() to distinguish these states. +* +* The `rold->precise` check is a performance optimization. If `rold->id` Quoted 8 lines
kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 15181
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+* was ever used to access memory / predict jump, the `rold` or any +* register used in `rold = r?` / `r? = rold` operations would be marked +* as precise, otherwise it's ID is not really interesting. +*/ +if (rold->precise && rold->id && !check_ids (rold->id, rcur->id, idmap))Do we need
rold->idchecking in the above?check_idsshould haverold->id= 0 properly. Or this is just an optimization?You are correct, the
check_ids()handles this case and it should be inlined, so there is no need to checkrold->idin this 'if' branch.Quoted 4 lines
regs_exact()hascheck_idsas well. Not sure whether it makes sense to create a functionregs_exact_scalar()just for scalar and include the above code. Otherwise, it is strange we docheck_idsin different places.I'm not sure how to best re-organize code here,
regs_exact()is a nice compartmentalized abstraction. It is possible to merge my additionalcheck_ids()call with the main 'precise' processing part as below:(quoted diff) +2
-1@@ -15152,21 +15154,22 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, switch (base_type(rold->type)) { case SCALAR_VALUE: if (regs_exact(rold, rcur, idmap)) return true; if (env->explore_alu_limits) return false; if (!rold->precise) return true; /* new val must satisfy old val 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);
Quoted 3 lines
I'd say that extending /* new val must satisfy ... */ comment to explain why
check_ids()is needed should be sufficient, but I'm open for suggestions.
On the other hand, I wanted to have a separate 'if' branch like:
if (rold->precise && !check_ids(rold->id, rcur->id, idmap))
Specifically to explain that 'rold->precise' part is an optimization.
Quoted 7 lines
Quoted 6 lines
Quoted 6 lines
kernel/bpf/verifier.c +1
-0+return false;if (regs_exact (rold, rcur, idmap))return true;if (env->explore_alu_limits)
Re: [PATCH bpf-next v1 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 69 lines · Eduard Zingerman
On Sat, 2023-05-27 at 15:21 +0300, Eduard Zingerman wrote:
[...]Quoted 61 lines
Quoted 25 lines
Quoted 25 lines
kernel/bpf/verifier.c +21
-0@@ -15151,6 +15153,33 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : +/* Why check_ids() for precise 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 would start from (5), because of the jump at (3). +* The only state difference between first and second visits of (5) is +* bpf_reg_state::id assignments for r6 and r7: (b, b) vs (a, b). +* Thus, use check_ids() to distinguish these states. +* +* The `rold->precise` check is a performance optimization. If `rold->id` Quoted 8 lines
kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 15181
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+* was ever used to access memory / predict jump, the `rold` or any +* register used in `rold = r?` / `r? = rold` operations would be marked +* as precise, otherwise it's ID is not really interesting. +*/ +if (rold->precise && rold->id && !check_ids (rold->id, rcur->id, idmap))Do we need
rold->idchecking in the above?check_idsshould haverold->id= 0 properly. Or this is just an optimization?You are correct, the
check_ids()handles this case and it should be inlined, so there is no need to checkrold->idin this 'if' branch.Quoted 4 lines
regs_exact()hascheck_idsas well. Not sure whether it makes sense to create a functionregs_exact_scalar()just for scalar and include the above code. Otherwise, it is strange we docheck_idsin different places.I'm not sure how to best re-organize code here,
regs_exact()is a nice compartmentalized abstraction. It is possible to merge my additionalcheck_ids()call with the main 'precise' processing part as below:(quoted diff) +2
-1@@ -15152,21 +15154,22 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, switch (base_type(rold->type)) { case SCALAR_VALUE: if (regs_exact(rold, rcur, idmap)) return true; if (env->explore_alu_limits) return false; if (!rold->precise) return true; /* new val must satisfy old val 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);Quoted 3 lines
I'd say that extending /* new val must satisfy ... */ comment to explain why
check_ids()is needed should be sufficient, but I'm open for suggestions.On the other hand, I wanted to have a separate 'if' branch like:
Quoted 3 lines
if (rold->precise && !check_ids(rold->id, rcur->id, idmap))Specifically to explain that '
rold->precise' part is an optimization.
Okay, I think you could keep your original implementation. I do think checking rold->ref_obj_id in regs_exact is not needed for SCALAR_VALUE but it may not be that important. The check_ids checking in reg_exact (for SCALAR_VALUE) can also be skipped if !rold->precise as an optimization. That is why I mention to 'inline' regs_exact and re-arrange the codes. You can still mention that optimization w.r.t. rold->precise. Overall if the code is more complex, I am okay with your current change.
Quoted 9 lines
Quoted 8 lines
Quoted 7 lines
Quoted 7 lines
kernel/bpf/verifier.c +1
-0+return false;if (regs_exact (rold, rcur, idmap))return true;if (env->explore_alu_limits)
Eduard Zingerman
maintainerRe: [PATCH bpf-next v1 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 75 lines · Yonghong Song
Quoted 69 lines · Eduard Zingerman
On Sat, 2023-05-27 at 15:21 +0300, Eduard Zingerman wrote:
[...]Quoted 61 lines
Quoted 25 lines
Quoted 25 lines
kernel/bpf/verifier.c +21
-0@@ -15151,6 +15153,33 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : +/* Why check_ids() for precise 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 would start from (5), because of the jump at (3). +* The only state difference between first and second visits of (5) is +* bpf_reg_state::id assignments for r6 and r7: (b, b) vs (a, b). +* Thus, use check_ids() to distinguish these states. +* +* The `rold->precise` check is a performance optimization. If `rold->id` Quoted 8 lines
kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 15181
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+* was ever used to access memory / predict jump, the `rold` or any +* register used in `rold = r?` / `r? = rold` operations would be marked +* as precise, otherwise it's ID is not really interesting. +*/ +if (rold->precise && rold->id && !check_ids (rold->id, rcur->id, idmap))Do we need
rold->idchecking in the above?check_idsshould haverold->id= 0 properly. Or this is just an optimization?You are correct, the
check_ids()handles this case and it should be inlined, so there is no need to checkrold->idin this 'if' branch.Quoted 4 lines
regs_exact()hascheck_idsas well. Not sure whether it makes sense to create a functionregs_exact_scalar()just for scalar and include the above code. Otherwise, it is strange we docheck_idsin different places.I'm not sure how to best re-organize code here,
regs_exact()is a nice compartmentalized abstraction. It is possible to merge my additionalcheck_ids()call with the main 'precise' processing part as below:(quoted diff) +2
-1@@ -15152,21 +15154,22 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, switch (base_type(rold->type)) { case SCALAR_VALUE: if (regs_exact(rold, rcur, idmap)) return true; if (env->explore_alu_limits) return false; if (!rold->precise) return true; /* new val must satisfy old val 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);Quoted 3 lines
I'd say that extending /* new val must satisfy ... */ comment to explain why
check_ids()is needed should be sufficient, but I'm open for suggestions.On the other hand, I wanted to have a separate 'if' branch like:
Quoted 3 lines
if (rold->precise && !check_ids(rold->id, rcur->id, idmap))Specifically to explain that '
rold->precise' part is an optimization.
Quoted 8 lines
Okay, I think you could keep your original implementation. I do think checking
rold->ref_obj_idinregs_exactis not needed forSCALAR_VALUEbut it may not be that important. Thecheck_idschecking inreg_exact(forSCALAR_VALUE) can also be skipped if !rold->precise as an optimization. That is why I mention to 'inline'regs_exactand re-arrange the codes. You can still mention that optimization w.r.t.rold->precise. Overall if the code is more complex, I am okay with your current change.
I thought a bit more about this and came up with example that doesn't work with 'rold->precise' case:
/* Bump allocated stack */
1: r1 = 0;
*(u64*)(r10 - 8) = r1;
/* r9 = pointer to stack */
2: r9 = r10;
3: r9 += -8;
/* r8 = ktime_get_ns() */
4: call %[bpf_ktime_get_ns];
5: r8 = r0;
/* r7 = ktime_get_ns() */
6: call %[bpf_ktime_get_ns];
7: r7 = r0;
/* r6 = ktime_get_ns() */
8: call %[bpf_ktime_get_ns];
9: r6 = r0;
/* scratch .id from r0 */
10: r0 = 0;
/* if r6 > r7 is an unpredictable jump */
11: if r6 > r7 goto l1;
/* tie r6 and r7 .id */
12: r6 = r7;
l0:
/* if r7 > 4 exit(0) */
13: if r7 > 4 goto l2;
/* access memory at r9[r6] */
14: r9 += r6;
15: r0 = *(u8*)(r9 + 0);
l2:
16: r0 = 0;
17: exit;
l1:
/* tie r6 and r8 .id */ 18: r6 = r8;
19: goto l0;
This example is marked as safe, however it isn't.
What happens:
(a) path 1-17 is verified first, it is marked safe
- when 14 is processed mark_chain_precision() is called with regno set to r6;
- moving backwards mark_chain_precision() does *not* mark r7 as precise at 13
because mark_chain_precision() does not track register ids;
- thus, for checkpiont at 13 only r6 is marked as precise.
(b) path 1-11, 18-19, 13-17 is verified next:
- when insn 13 is processed the saved checkpiont is examined, the only precise register is r6, so check_ids() is called only for r6 and it returns true => checkpiont is considered safe.
However, in reality register ID assignments differ between (a) and (b) at insn 13:
(a) r6{id=A}, r7{id=A}, r8{id=B}
(b) r6{id=B}, r7{id=A}, r8{id=B}
So, simplest and safest change is as follows:
@@ -15152,4 +15154,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
switch (base_type(rold->type)) {
case SCALAR_VALUE: + if (!check_ids(rold->id, rcur->id, idmap))
+ return false;
if (regs_exact(rold, rcur, idmap))
return true;
Here regsafe() does not care about rold->precise marks, thus differences between (a) and (b) would be detected by check_ids, as all three registers r{6,7,8} would be fed to it.
However, it is also costly (note the filter by 40% processed states increase or more):
$ ./veristat -e file,prog,states -f 'states_pct>40' -C master-baseline.log current.log File Program States (A) States (B) States (DIFF) ----------- ----------------------------- ---------- ---------- -------------- bpf_host.o cil_from_host 37 52 +15 (+40.54%) bpf_host.o cil_from_netdev 28 46 +18 (+64.29%) bpf_host.o tail_handle_ipv4_from_host 225 350 +125 (+55.56%) bpf_host.o tail_handle_ipv4_from_netdev 109 173 +64 (+58.72%) bpf_host.o tail_handle_ipv6_from_host 250 387 +137 (+54.80%) bpf_host.o tail_handle_ipv6_from_netdev 132 194 +62 (+46.97%) bpf_host.o tail_ipv4_host_policy_ingress 103 167 +64 (+62.14%) bpf_host.o tail_ipv6_host_policy_ingress 98 160 +62 (+63.27%) bpf_xdp.o __send_drop_notify 8 14 +6 (+75.00%) bpf_xdp.o tail_handle_nat_fwd_ipv6 648 971 +323 (+49.85%) loop6.bpf.o trace_virtqueue_add_sgs 226 357 +131 (+57.96%)
I'll modify mark_chain_precision() to mark registers precise taking into account scalar IDs, when comparisons are processed. Will report on Monday.
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
Quoted 6 lines
Review static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 15182
Quoted 5 lines
(quoted diff) +1
-0+ return false; > > > > if (regs_exact(rold, rcur, idmap)) >return true; > > > > if (
env->explore_alu_limits)
Eduard Zingerman
maintainerPATCH 2/2 selftests/bpf: verify that check_ids() is used for scalars in regsafe()
In reply to Eduard ZingermanVerify 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
r6 = r7
if (r6 > X) goto exit
r9 += r7
*(u64 *)r9 = Y
--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 59 +++++++++++++++++++ 2 files changed, 61 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -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); }
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +59 -0
59 lines not on this page · raw message
Signature · 1 line
2.40.1