For now, the reg bounds is not handled for BPF_JNE case, which can cause the failure of following case:
/* The type of "a" is u32 */ if (a > 0 && a < 100) { /* the range of the register for a is [0, 99], not [1, 99], * and will cause the following error: * * invalid zero-sized read * * as a can be 0. */ bpf_skb_store_bytes(skb, xx, xx, a, 0); }
In the code above, "a > 0" will be compiled to "if a == 0 goto xxx". In the TRUE branch, the dst_reg will be marked as known to 0. However, in the fallthrough(FALSE) branch, the dst_reg will not be handled, which makes the [min, max] for a is [0, 99], not [1, 99].
In the 1st patch, we reduce the range of the dst reg if the src reg is a const and is exactly the edge of the dst reg For BPF_JNE.
In the 2nd patch, we remove reduplicated s32 casting in "crafted_cases".
In the 3rd patch, we just activate the test case for this logic in range_cond(), which is committed by Andrii in the commit 8863238993e2 ("selftests/bpf: BPF register range bounds tester").
In the 4th patch, we convert the case above to a testcase and add it to verifier_bounds.c.
Changes since v4: - add the 2nd patch - add "{U32, U32, {0, U32_MAX}, {U32_MAX, U32_MAX}}" that we missed in the 3rd patch - add some comments to the function that we add in the 4th patch - add reg_not_equal_const() in the 4th patch
Changes since v3: - do some adjustment to the crafted cases that we added in the 2nd patch - add the 3rd patch
Changes since v2: - fix a typo in the subject of the 1st patch - add some comments to the 1st patch, as Eduard advised - add some cases to the "crafted_cases"
Changes since v1: - simplify the code in the 1st patch - introduce the 2nd patch for the testing
Menglong Dong (4): bpf: make the verifier tracks the "not equal" for regs selftests/bpf: remove reduplicated s32 casting in "crafted_cases" selftests/bpf: activate the OP_NE logic in range_cond() selftests/bpf: add testcase to verifier_bounds.c for BPF_JNE
kernel/bpf/verifier.c | 38 +++++++++++- .../selftests/bpf/prog_tests/reg_bounds.c | 27 +++++--- .../selftests/bpf/progs/verifier_bounds.c | 62 +++++++++++++++++++ 3 files changed, 116 insertions(+), 11 deletions(-)
We can derive some new information for BPF_JNE in regs_refine_cond_op(). Take following code for example:
/* The type of "a" is u32 */ if (a > 0 && a < 100) { /* the range of the register for a is [0, 99], not [1, 99], * and will cause the following error: * * invalid zero-sized read * * as a can be 0. */ bpf_skb_store_bytes(skb, xx, xx, a, 0); }
In the code above, "a > 0" will be compiled to "jmp xxx if a == 0". In the TRUE branch, the dst_reg will be marked as known to 0. However, in the fallthrough(FALSE) branch, the dst_reg will not be handled, which makes the [min, max] for a is [0, 99], not [1, 99].
For BPF_JNE, we can reduce the range of the dst reg if the src reg is a const and is exactly the edge of the dst reg.
Signed-off-by: Menglong Dong menglong8.dong@gmail.com Acked-by: Andrii Nakryiko andrii@kernel.org Acked-by: Shung-Hsi Yu shung-hsi.yu@suse.com --- v2: - fix a typo in the subject - add some comments, as Eduard advised --- kernel/bpf/verifier.c | 38 +++++++++++++++++++++++++++++++++++++- 1 file changed, 37 insertions(+), 1 deletion(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 1863826a4ac3..29c41d66ea6f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -14343,7 +14343,43 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state } break; case BPF_JNE: - /* we don't derive any new information for inequality yet */ + if (!is_reg_const(reg2, is_jmp32)) + swap(reg1, reg2); + if (!is_reg_const(reg2, is_jmp32)) + break; + + /* try to recompute the bound of reg1 if reg2 is a const and + * is exactly the edge of reg1. + */ + val = reg_const_value(reg2, is_jmp32); + if (is_jmp32) { + /* u32_min_value is not equal to 0xffffffff at this point, + * because otherwise u32_max_value is 0xffffffff as well, + * in such a case both reg1 and reg2 would be constants, + * jump would be predicted and reg_set_min_max() won't + * be called. + * + * Same reasoning works for all {u,s}{min,max}{32,64} cases + * below. + */ + if (reg1->u32_min_value == (u32)val) + reg1->u32_min_value++; + if (reg1->u32_max_value == (u32)val) + reg1->u32_max_value--; + if (reg1->s32_min_value == (s32)val) + reg1->s32_min_value++; + if (reg1->s32_max_value == (s32)val) + reg1->s32_max_value--; + } else { + if (reg1->umin_value == (u64)val) + reg1->umin_value++; + if (reg1->umax_value == (u64)val) + reg1->umax_value--; + if (reg1->smin_value == (s64)val) + reg1->smin_value++; + if (reg1->smax_value == (s64)val) + reg1->smax_value--; + } break; case BPF_JSET: if (!is_reg_const(reg2, is_jmp32))
The "S32_MIN" is already defined with s32 casting, so there is no need to do it again.
Signed-off-by: Menglong Dong menglong8.dong@gmail.com --- tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c index 0c9abd279e18..3bf4ddd720a8 100644 --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c @@ -2097,10 +2097,10 @@ static struct subtest_case crafted_cases[] = {
{U32, S32, {0, U32_MAX}, {U32_MAX, U32_MAX}},
- {S32, U64, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)-255, 0}}, - {S32, S64, {(u32)(s32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}}, - {S32, S64, {0, 1}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}}, - {S32, U32, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}}, + {S32, U64, {(u32)S32_MIN, (u32)S32_MIN}, {(u32)(s32)-255, 0}}, + {S32, S64, {(u32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}}, + {S32, S64, {0, 1}, {(u32)S32_MIN, (u32)S32_MIN}}, + {S32, U32, {(u32)S32_MIN, (u32)S32_MIN}, {(u32)S32_MIN, (u32)S32_MIN}}, };
/* Go over crafted hard-coded cases. This is fast, so we do it as part of
On Tue, Dec 19, 2023 at 5:50 AM Menglong Dong menglong8.dong@gmail.com wrote:
The "S32_MIN" is already defined with s32 casting, so there is no need to do it again.
Signed-off-by: Menglong Dong menglong8.dong@gmail.com
tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
Acked-by: Andrii Nakryiko andrii@kernel.org
diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c index 0c9abd279e18..3bf4ddd720a8 100644 --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c @@ -2097,10 +2097,10 @@ static struct subtest_case crafted_cases[] = {
{U32, S32, {0, U32_MAX}, {U32_MAX, U32_MAX}},
{S32, U64, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)-255, 0}},{S32, S64, {(u32)(s32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},{S32, S64, {0, 1}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},{S32, U32, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
{S32, U64, {(u32)S32_MIN, (u32)S32_MIN}, {(u32)(s32)-255, 0}},{S32, S64, {(u32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},{S32, S64, {0, 1}, {(u32)S32_MIN, (u32)S32_MIN}},{S32, U32, {(u32)S32_MIN, (u32)S32_MIN}, {(u32)S32_MIN, (u32)S32_MIN}},};
/* Go over crafted hard-coded cases. This is fast, so we do it as part of
2.39.2
The edge range checking for the registers is supported by the verifier now, so we can activate the extended logic in tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test such logic.
Besides, I added some cases to the "crafted_cases" array for this logic. These cases are mainly used to test the edge of the src reg and dst reg.
All reg bounds testings has passed in the SLOW_TESTS mode:
$ export SLOW_TESTS=1 && ./test_progs -t reg_bounds -j Summary: 65/18959832 PASSED, 0 SKIPPED, 0 FAILED
Signed-off-by: Menglong Dong menglong8.dong@gmail.com --- v5: - add "{U32, U32, {0, U32_MAX}, {U32_MAX, U32_MAX}}" v4: - remove reduplicated s32 casting v3: - do some adjustment to the crafted cases that we added v2: - add some cases to the "crafted_cases" --- .../selftests/bpf/prog_tests/reg_bounds.c | 19 +++++++++++++------ 1 file changed, 13 insertions(+), 6 deletions(-)
diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c index 3bf4ddd720a8..820d0bcfc474 100644 --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c @@ -590,12 +590,7 @@ static void range_cond(enum num_t t, struct range x, struct range y, *newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b)); break; case OP_NE: - /* generic case, can't derive more information */ - *newx = range(t, x.a, x.b); - *newy = range(t, y.a, y.b); - break; - - /* below extended logic is not supported by verifier just yet */ + /* below logic is supported by the verifier now */ if (x.a == x.b && x.a == y.a) { /* X is a constant matching left side of Y */ *newx = range(t, x.a, x.b); @@ -2101,6 +2096,18 @@ static struct subtest_case crafted_cases[] = { {S32, S64, {(u32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}}, {S32, S64, {0, 1}, {(u32)S32_MIN, (u32)S32_MIN}}, {S32, U32, {(u32)S32_MIN, (u32)S32_MIN}, {(u32)S32_MIN, (u32)S32_MIN}}, + + /* edge overlap testings for BPF_NE */ + {U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}}, + {U64, U64, {0, U64_MAX}, {0, 0}}, + {S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}}, + {S64, U64, {S64_MIN, 0}, {0, 0}}, + {S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}}, + {U32, U32, {0, U32_MAX}, {0, 0}}, + {U32, U32, {0, U32_MAX}, {U32_MAX, U32_MAX}}, + {S32, U32, {(u32)S32_MIN, 0}, {0, 0}}, + {S32, U32, {(u32)S32_MIN, 0}, {(u32)S32_MIN, (u32)S32_MIN}}, + {S32, U32, {(u32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}}, };
/* Go over crafted hard-coded cases. This is fast, so we do it as part of
On Tue, Dec 19, 2023 at 5:50 AM Menglong Dong menglong8.dong@gmail.com wrote:
The edge range checking for the registers is supported by the verifier now, so we can activate the extended logic in tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test such logic.
Besides, I added some cases to the "crafted_cases" array for this logic. These cases are mainly used to test the edge of the src reg and dst reg.
All reg bounds testings has passed in the SLOW_TESTS mode:
$ export SLOW_TESTS=1 && ./test_progs -t reg_bounds -j Summary: 65/18959832 PASSED, 0 SKIPPED, 0 FAILED
Thanks for running SLOW_TESTS=1 mode as well!
Acked-by: Andrii Nakryiko andrii@kernel.org
Signed-off-by: Menglong Dong menglong8.dong@gmail.com
v5:
- add "{U32, U32, {0, U32_MAX}, {U32_MAX, U32_MAX}}"
v4:
- remove reduplicated s32 casting
v3:
- do some adjustment to the crafted cases that we added
v2:
- add some cases to the "crafted_cases"
.../selftests/bpf/prog_tests/reg_bounds.c | 19 +++++++++++++------ 1 file changed, 13 insertions(+), 6 deletions(-)
diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c index 3bf4ddd720a8..820d0bcfc474 100644 --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c @@ -590,12 +590,7 @@ static void range_cond(enum num_t t, struct range x, struct range y, *newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b)); break; case OP_NE:
/* generic case, can't derive more information */*newx = range(t, x.a, x.b);*newy = range(t, y.a, y.b);break;/* below extended logic is not supported by verifier just yet */
/* below logic is supported by the verifier now */ if (x.a == x.b && x.a == y.a) { /* X is a constant matching left side of Y */ *newx = range(t, x.a, x.b);@@ -2101,6 +2096,18 @@ static struct subtest_case crafted_cases[] = { {S32, S64, {(u32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}}, {S32, S64, {0, 1}, {(u32)S32_MIN, (u32)S32_MIN}}, {S32, U32, {(u32)S32_MIN, (u32)S32_MIN}, {(u32)S32_MIN, (u32)S32_MIN}},
/* edge overlap testings for BPF_NE */{U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}},{U64, U64, {0, U64_MAX}, {0, 0}},{S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}},{S64, U64, {S64_MIN, 0}, {0, 0}},{S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}},{U32, U32, {0, U32_MAX}, {0, 0}},{U32, U32, {0, U32_MAX}, {U32_MAX, U32_MAX}},{S32, U32, {(u32)S32_MIN, 0}, {0, 0}},{S32, U32, {(u32)S32_MIN, 0}, {(u32)S32_MIN, (u32)S32_MIN}},{S32, U32, {(u32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},};
/* Go over crafted hard-coded cases. This is fast, so we do it as part of
2.39.2
Add testcase for the logic that the verifier tracks the BPF_JNE for regs. The assembly function "reg_not_equal_const()" and "reg_equal_const" that we add is exactly converted from the following case:
u32 a = bpf_get_prandom_u32(); u64 b = 0;
a %= 8; /* the "a > 0" here will be optimized to "a != 0" */ if (a > 0) { /* now the range of a should be [1, 7] */ bpf_skb_store_bytes(skb, 0, &b, a, 0); }
Signed-off-by: Menglong Dong menglong8.dong@gmail.com --- v5: - add some comments to the function that we add - add reg_not_equal_const() --- .../selftests/bpf/progs/verifier_bounds.c | 62 +++++++++++++++++++ 1 file changed, 62 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c index ec430b71730b..960998f16306 100644 --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c @@ -1075,4 +1075,66 @@ l0_%=: r0 = 0; \ : __clobber_all); }
+SEC("tc") +__description("bounds check with JMP_NE for reg edge") +__success __retval(0) +__naked void reg_not_equal_const(void) +{ + asm volatile (" \ + r6 = r1; \ + r1 = 0; \ + *(u64*)(r10 - 8) = r1; \ + call %[bpf_get_prandom_u32]; \ + r4 = r0; \ + r4 &= 7; \ + if r4 != 0 goto l0_%=; \ + r0 = 0; \ + exit; \ +l0_%=: r1 = r6; \ + r2 = 0; \ + r3 = r10; \ + r3 += -8; \ + r5 = 0; \ + /* The 4th argument of bpf_skb_store_bytes is defined as \ + * ARG_CONST_SIZE, so 0 is not allowed. The 'r4 != 0' \ + * is providing us this exclusion of zero from initial \ + * [0, 7] range. \ + */ \ + call %[bpf_skb_store_bytes]; \ + r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32), + __imm(bpf_skb_store_bytes) + : __clobber_all); +} + +SEC("tc") +__description("bounds check with JMP_EQ for reg edge") +__success __retval(0) +__naked void reg_equal_const(void) +{ + asm volatile (" \ + r6 = r1; \ + r1 = 0; \ + *(u64*)(r10 - 8) = r1; \ + call %[bpf_get_prandom_u32]; \ + r4 = r0; \ + r4 &= 7; \ + if r4 == 0 goto l0_%=; \ + r1 = r6; \ + r2 = 0; \ + r3 = r10; \ + r3 += -8; \ + r5 = 0; \ + /* Just the same as what we do in reg_not_equal_const() */ \ + call %[bpf_skb_store_bytes]; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32), + __imm(bpf_skb_store_bytes) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
On Tue, Dec 19, 2023 at 5:51 AM Menglong Dong menglong8.dong@gmail.com wrote:
Add testcase for the logic that the verifier tracks the BPF_JNE for regs. The assembly function "reg_not_equal_const()" and "reg_equal_const" that we add is exactly converted from the following case:
u32 a = bpf_get_prandom_u32(); u64 b = 0;
a %= 8; /* the "a > 0" here will be optimized to "a != 0" */ if (a > 0) { /* now the range of a should be [1, 7] */ bpf_skb_store_bytes(skb, 0, &b, a, 0); }
Signed-off-by: Menglong Dong menglong8.dong@gmail.com
v5:
- add some comments to the function that we add
- add reg_not_equal_const()
.../selftests/bpf/progs/verifier_bounds.c | 62 +++++++++++++++++++ 1 file changed, 62 insertions(+)
LGTM
Acked-by: Andrii Nakryiko andrii@kernel.org
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c index ec430b71730b..960998f16306 100644 --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c @@ -1075,4 +1075,66 @@ l0_%=: r0 = 0; \ : __clobber_all); }
+SEC("tc") +__description("bounds check with JMP_NE for reg edge") +__success __retval(0) +__naked void reg_not_equal_const(void) +{
asm volatile (" \r6 = r1; \r1 = 0; \*(u64*)(r10 - 8) = r1; \call %[bpf_get_prandom_u32]; \r4 = r0; \r4 &= 7; \if r4 != 0 goto l0_%=; \r0 = 0; \exit; \+l0_%=: r1 = r6; \
r2 = 0; \r3 = r10; \r3 += -8; \r5 = 0; \/* The 4th argument of bpf_skb_store_bytes is defined as \* ARG_CONST_SIZE, so 0 is not allowed. The 'r4 != 0' \* is providing us this exclusion of zero from initial \* [0, 7] range. \*/ \call %[bpf_skb_store_bytes]; \r0 = 0; \exit; \+" :
: __imm(bpf_get_prandom_u32),__imm(bpf_skb_store_bytes): __clobber_all);+}
+SEC("tc") +__description("bounds check with JMP_EQ for reg edge") +__success __retval(0) +__naked void reg_equal_const(void) +{
asm volatile (" \r6 = r1; \r1 = 0; \*(u64*)(r10 - 8) = r1; \call %[bpf_get_prandom_u32]; \r4 = r0; \r4 &= 7; \if r4 == 0 goto l0_%=; \r1 = r6; \r2 = 0; \r3 = r10; \r3 += -8; \r5 = 0; \/* Just the same as what we do in reg_not_equal_const() */ \call %[bpf_skb_store_bytes]; \+l0_%=: r0 = 0; \
exit; \+" :
: __imm(bpf_get_prandom_u32),__imm(bpf_skb_store_bytes): __clobber_all);+}
char _license[] SEC("license") = "GPL";
2.39.2
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov ast@kernel.org:
On Tue, 19 Dec 2023 21:47:56 +0800 you wrote:
For now, the reg bounds is not handled for BPF_JNE case, which can cause the failure of following case:
/* The type of "a" is u32 */ if (a > 0 && a < 100) { /* the range of the register for a is [0, 99], not [1, 99], * and will cause the following error: * * invalid zero-sized read * * as a can be 0. */ bpf_skb_store_bytes(skb, xx, xx, a, 0); }
[...]
Here is the summary with links: - [bpf-next,v5,1/4] bpf: make the verifier tracks the "not equal" for regs https://git.kernel.org/bpf/bpf-next/c/d028f87517d6 - [bpf-next,v5,2/4] selftests/bpf: remove reduplicated s32 casting in "crafted_cases" https://git.kernel.org/bpf/bpf-next/c/1de584832375 - [bpf-next,v5,3/4] selftests/bpf: activate the OP_NE logic in range_cond() https://git.kernel.org/bpf/bpf-next/c/31d9cc96b1e3 - [bpf-next,v5,4/4] selftests/bpf: add testcase to verifier_bounds.c for BPF_JNE https://git.kernel.org/bpf/bpf-next/c/463ea64eb008
You are awesome, thank you!
linux-kselftest-mirror@lists.linaro.org
-
Andrii Nakryiko -
Menglong Dong -
patchwork-bot+netdevbpf＠kernel.org