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 u16 */
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].
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 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").
Changes since v1:
- simplify the code in the 1st patch
- introduce the 2nd patch for the testing
Menglong Dong (2):
bpf: make the verifier trace the "not qeual" for regs
selftests/bpf: activate the OP_NE login in range_cond()
kernel/bpf/verifier.c | 29 ++++++++++++++++++-
.../selftests/bpf/prog_tests/reg_bounds.c | 7 +----
2 files changed, 29 insertions(+), 7 deletions(-)
--
2.39.2
We can derive some new information for BPF_JNE in regs_refine_cond_op().
Take following code for example:
/* The type of "a" is u16 */
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 <[email protected]>
---
kernel/bpf/verifier.c | 29 ++++++++++++++++++++++++++++-
1 file changed, 28 insertions(+), 1 deletion(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 727a59e4a647..08ee0e02df96 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -14332,7 +14332,34 @@ 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) {
+ 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))
--
2.39.2
The edge range checking for the registers is supported by the verifier
now, so we can activate the extended login in
tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test
such logic.
Signed-off-by: Menglong Dong <[email protected]>
---
tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 7 +------
1 file changed, 1 insertion(+), 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 0c9abd279e18..49d8d4bafe99 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);
--
2.39.2
On Tue, 2023-12-12 at 21:10 +0800, Menglong Dong wrote:
> We can derive some new information for BPF_JNE in regs_refine_cond_op().
> Take following code for example:
>
> /* The type of "a" is u16 */
> 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 <[email protected]>
> ---
Acked-by: Eduard Zingerman <[email protected]>
> kernel/bpf/verifier.c | 29 ++++++++++++++++++++++++++++-
> 1 file changed, 28 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 727a59e4a647..08ee0e02df96 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -14332,7 +14332,34 @@ 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) {
> + if (reg1->u32_min_value == (u32)val)
> + reg1->u32_min_value++;
Nit: I spent an unreasonable amount of time trying to figure out if
overflow might be an issue here. Would it be helpful to add a
comment like below? (not sure, maybe it's obvious and I'm being slow)
/* 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.
*/
On Tue, 2023-12-12 at 21:10 +0800, Menglong Dong wrote:
> The edge range checking for the registers is supported by the verifier
> now, so we can activate the extended login in
> tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test
> such logic.
>
> Signed-off-by: Menglong Dong <[email protected]>
> ---
> tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 7 +------
> 1 file changed, 1 insertion(+), 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 0c9abd279e18..49d8d4bafe99 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);
I think that some crafted tests have to be added.
Note that reg_bounds only runs a subset of tests during CI
(controlled by variable SLOW_TESTS).
By default only randomized and crafted tests are run.
It appears to me that probability of randomly generating specific
ranges explored by this series is quite low.
On Tue, Dec 12, 2023 at 5:15 AM Menglong Dong <[email protected]> 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 u16 */
> 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].
>
> 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 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").
>
> Changes since v1:
> - simplify the code in the 1st patch
> - introduce the 2nd patch for the testing
>
> Menglong Dong (2):
> bpf: make the verifier trace the "not qeual" for regs
> selftests/bpf: activate the OP_NE login in range_cond()
>
> kernel/bpf/verifier.c | 29 ++++++++++++++++++-
> .../selftests/bpf/prog_tests/reg_bounds.c | 7 +----
> 2 files changed, 29 insertions(+), 7 deletions(-)
>
> --
> 2.39.2
>
+1 to all the feedback from Eduard. Besides that, please target
bpf-next tree (so, [PATH bpf-next] for subject prefix), thanks!
Also, instead of "verifier traces", I think "verifier tracks" is less
confusing wording. Tracing within the BPF ecosystem is usually used
for a completely different meaning.
Oh, and just to keep feedback in one place. In patch #2 you have a
typo in the subject "not qeual" -> "not equal".
On Wed, Dec 13, 2023 at 8:00 AM Andrii Nakryiko
<[email protected]> wrote:
>
> On Tue, Dec 12, 2023 at 5:15 AM Menglong Dong <[email protected]> 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 u16 */
> > 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].
> >
> > 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 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").
> >
> > Changes since v1:
> > - simplify the code in the 1st patch
> > - introduce the 2nd patch for the testing
> >
> > Menglong Dong (2):
> > bpf: make the verifier trace the "not qeual" for regs
> > selftests/bpf: activate the OP_NE login in range_cond()
> >
> > kernel/bpf/verifier.c | 29 ++++++++++++++++++-
> > .../selftests/bpf/prog_tests/reg_bounds.c | 7 +----
> > 2 files changed, 29 insertions(+), 7 deletions(-)
> >
> > --
> > 2.39.2
> >
>
> +1 to all the feedback from Eduard. Besides that, please target
> bpf-next tree (so, [PATH bpf-next] for subject prefix), thanks!
>
Opps, sorry that I offered a wrong tag......:/
> Also, instead of "verifier traces", I think "verifier tracks" is less
> confusing wording. Tracing within the BPF ecosystem is usually used
> for a completely different meaning.
>
Yeah, sounds better.
> Oh, and just to keep feedback in one place. In patch #2 you have a
> typo in the subject "not qeual" -> "not equal".
Ok, I'll fix it in the next version.
Thanks!
Menglong Dong
On Wed, Dec 13, 2023 at 7:23 AM Eduard Zingerman <[email protected]> wrote:
>
> On Tue, 2023-12-12 at 21:10 +0800, Menglong Dong wrote:
> > We can derive some new information for BPF_JNE in regs_refine_cond_op().
> > Take following code for example:
> >
> > /* The type of "a" is u16 */
> > 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 <[email protected]>
> > ---
>
> Acked-by: Eduard Zingerman <[email protected]>
>
> > kernel/bpf/verifier.c | 29 ++++++++++++++++++++++++++++-
> > 1 file changed, 28 insertions(+), 1 deletion(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 727a59e4a647..08ee0e02df96 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -14332,7 +14332,34 @@ 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) {
> > + if (reg1->u32_min_value == (u32)val)
> > + reg1->u32_min_value++;
>
> Nit: I spent an unreasonable amount of time trying to figure out if
> overflow might be an issue here. Would it be helpful to add a
> comment like below? (not sure, maybe it's obvious and I'm being slow)
>
> /* 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.
> */
Okay, I'll add this comment in the next version.
Thanks!
Menglong Dong
Hello,
On Wed, Dec 13, 2023 at 7:37 AM Eduard Zingerman <[email protected]> wrote:
>
> On Tue, 2023-12-12 at 21:10 +0800, Menglong Dong wrote:
> > The edge range checking for the registers is supported by the verifier
> > now, so we can activate the extended login in
> > tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test
> > such logic.
> >
> > Signed-off-by: Menglong Dong <[email protected]>
> > ---
> > tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 7 +------
> > 1 file changed, 1 insertion(+), 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 0c9abd279e18..49d8d4bafe99 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);
>
> I think that some crafted tests have to be added.
> Note that reg_bounds only runs a subset of tests during CI
> (controlled by variable SLOW_TESTS).
> By default only randomized and crafted tests are run.
> It appears to me that probability of randomly generating specific
> ranges explored by this series is quite low.
You are right, I'll add some cases to the "crafted_cases" for
this logic.
Thanks!
Menglong Dong