From: Eduard Zingerman This renaming will also help reshuffle the different parts in the subsequent patch. Signed-off-by: Eduard Zingerman Signed-off-by: Paul Chaignon --- kernel/bpf/verifier.c | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 4fbacd2149cd..189e951886ed 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2448,7 +2448,7 @@ static void __update_reg_bounds(struct bpf_reg_state *reg) } /* Uses signed min/max values to inform unsigned, and vice-versa */ -static void __reg32_deduce_bounds(struct bpf_reg_state *reg) +static void deduce_bounds_32_from_64(struct bpf_reg_state *reg) { /* If upper 32 bits of u64/s64 range don't change, we can use lower 32 * bits to improve our u32/s32 boundaries. @@ -2518,6 +2518,10 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg) reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value); reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value); } +} + +static void deduce_bounds_32_from_32(struct bpf_reg_state *reg) +{ /* if u32 range forms a valid s32 range (due to matching sign bit), * try to learn from that */ @@ -2559,7 +2563,7 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg) } } -static void __reg64_deduce_bounds(struct bpf_reg_state *reg) +static void deduce_bounds_64_from_64(struct bpf_reg_state *reg) { /* If u64 range forms a valid s64 range (due to matching sign bit), * try to learn from that. Let's do a bit of ASCII art to see when @@ -2694,7 +2698,7 @@ static void __reg64_deduce_bounds(struct bpf_reg_state *reg) } } -static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) +static void deduce_bounds_64_from_32(struct bpf_reg_state *reg) { /* Try to tighten 64-bit bounds from 32-bit knowledge, using 32-bit * values on both sides of 64-bit range in hope to have tighter range. @@ -2763,9 +2767,10 @@ static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) static void __reg_deduce_bounds(struct bpf_reg_state *reg) { - __reg32_deduce_bounds(reg); - __reg64_deduce_bounds(reg); - __reg_deduce_mixed_bounds(reg); + deduce_bounds_32_from_64(reg); + deduce_bounds_32_from_32(reg); + deduce_bounds_64_from_64(reg); + deduce_bounds_64_from_32(reg); } /* Attempts to improve var_off based on unsigned min/max information */ -- 2.43.0 In commit 5dbb19b16ac49 ("bpf: Add third round of bounds deduction"), I added a new round of bounds deduction because two rounds were not enough to converge to a fixed point. This commit slightly refactor the bounds deduction logic such that two rounds are enough. In [1], Eduard noticed that after we improved the refinement logic, a third call to the bounds deduction (__reg_deduce_bounds) was needed to converge to a fixed point. More specifically, we needed this third call to improve the s64 range using the s32 range. We added the third call and postponed a more detailed analysis of the refinement logic. I've been looking into this more recently. The register refinement consists of the following calls. __update_reg_bounds(); 3 x __reg_deduce_bounds() { deduce_bounds_32_from_64(); deduce_bounds_32_from_32(); deduce_bounds_64_from_64(); deduce_bounds_64_from_32(); }; __reg_bound_offset(); __update_reg_bounds(); From this, we can observe that we first improve the 32bit ranges from the 64bit ranges in deduce_bounds_32_from_64, then improve the 64bit ranges on their own in deduce_bounds_64_from_64. Intuitively, if we were to improve the 64bit ranges on their own *before* we use them to improve the 32bit ranges, we may reach a fixed point earlier. In a similar manner, using CBMC, Eduard found that it's best to improve the 32bit ranges on their own *after* we've improve them using the 64bit ranges. That is, running deduce_bounds_32_from_32 after deduce_bounds_32_from_64. These changes allow us to lose one call to __reg_deduce_bounds. Without this reordering, the test "verifier_bounds/bounds deduction cross sign boundary, negative overlap" fails when removing one call to __reg_deduce_bounds. In some cases, this change can even improve precision a little bit, as illustrated in the new selftest in the next patch. As expected, this change didn't have any impact on the number of instructions processed when running it through the Cilium complexity test suite [2]. Link: https://lore.kernel.org/bpf/aIKtSK9LjQXB8FLY@mail.gmail.com/ [1] Link: https://pchaigno.github.io/test-verifier-complexity.html [2] Acked-by: Shung-Hsi Yu Co-developed-by: Eduard Zingerman Signed-off-by: Eduard Zingerman Signed-off-by: Paul Chaignon --- kernel/bpf/verifier.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 189e951886ed..e29f15419fcb 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2767,9 +2767,9 @@ static void deduce_bounds_64_from_32(struct bpf_reg_state *reg) static void __reg_deduce_bounds(struct bpf_reg_state *reg) { + deduce_bounds_64_from_64(reg); deduce_bounds_32_from_64(reg); deduce_bounds_32_from_32(reg); - deduce_bounds_64_from_64(reg); deduce_bounds_64_from_32(reg); } @@ -2793,7 +2793,6 @@ static void reg_bounds_sync(struct bpf_reg_state *reg) /* We might have learned something about the sign bit. */ __reg_deduce_bounds(reg); __reg_deduce_bounds(reg); - __reg_deduce_bounds(reg); /* We might have learned some bits from the bounds. */ __reg_bound_offset(reg); /* Intersecting with the old var_off might have improved our bounds -- 2.43.0 This new selftest demonstrates the improvement of bounds refinement from the previous patch. It is inspired from a set of reg_bounds_sync inputs generated using CBMC [1] by Shung-Hsi: reg.smin_value=0x8000000000000002 reg.smax_value=2 reg.umin_value=2 reg.umax_value=19 reg.s32_min_value=2 reg.s32_max_value=3 reg.u32_min_value=2 reg.u32_max_value=3 reg_bounds_sync returns R=[2; 3] without the previous patch, and R=2 with it. __reg64_deduce_bounds is able to derive that u64=2, but before the previous patch, those bounds are overwritten in __reg_deduce_mixed_bounds using the 32bits bounds. To arrive to these reg_bounds_sync inputs, we bound the 32bits value first to [2; 3]. We can then upper-bound s64 without impacting u64. At that point, the refinement to u64=2 doesn't happen because the ranges still overlap in two points: 0 umin=2 umax=0xff..ff00..03 U64_MAX | [xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] | |----------------------------|------------------------------| |xx] [xxxxxxxxxxxxxxxxxxxxxxxxxxxx| 0 smax=2 smin=0x800..02 -1 With an upper-bound check at value 19, we can reach the above inputs for reg_bounds_sync. At that point, the refinement to u64=2 happens and because it isn't overwritten by __reg_deduce_mixed_bounds anymore, reg_bounds_sync returns with reg=2. The test validates this result by including an illegal instruction in the (dead) branch reg != 2. Link: https://github.com/shunghsiyu/reg_bounds_sync-review/ [1] Co-developed-by: Shung-Hsi Yu Signed-off-by: Shung-Hsi Yu Signed-off-by: Paul Chaignon --- .../selftests/bpf/progs/verifier_bounds.c | 33 +++++++++++++++++++ 1 file changed, 33 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c index ce09379130aa..3724d5e5bcb3 100644 --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c @@ -2037,4 +2037,37 @@ __naked void signed_unsigned_intersection32_case2(void *ctx) : __clobber_all); } +/* After instruction 3, the u64 and s64 ranges look as follows: + * 0 umin=2 umax=0xff..ff00..03 U64_MAX + * | [xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] | + * |----------------------------|------------------------------| + * |xx] [xxxxxxxxxxxxxxxxxxxxxxxxxxxx| + * 0 smax=2 smin=0x800..02 -1 + * + * The two ranges can't be refined because they overlap in two places. Once we + * add an upper-bound to u64 at instruction 4, the refinement can happen. This + * test validates that this refinement does happen and is not overwritten by + * the less-precise 32bits ranges. + */ +SEC("socket") +__description("bounds refinement: 64bits ranges not overwritten by 32bits ranges") +__msg("3: (65) if r0 s> 0x2 {{.*}} R0=scalar(smin=0x8000000000000002,smax=2,umin=smin32=umin32=2,umax=0xffffffff00000003,smax32=umax32=3") +__msg("4: (25) if r0 > 0x13 {{.*}} R0=2") +__success __log_level(2) +__naked void refinement_32bounds_not_overwriting_64bounds(void *ctx) +{ + asm volatile(" \ + call %[bpf_get_prandom_u32]; \ + if w0 < 2 goto +5; \ + if w0 > 3 goto +4; \ + if r0 s> 2 goto +3; \ + if r0 > 19 goto +2; \ + if r0 == 2 goto +1; \ + r10 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + char _license[] SEC("license") = "GPL"; -- 2.43.0