[PATCH bpf-next v4 0/3] bpf: support to track BPF_JNE

[PATCH bpf-next v4 0/3] bpf: support to track BPF_JNE

[Menglong Dong]

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 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 3rd patch, we convert the case above to a testcase and add it to
verifier_bounds.c.

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 (3):
  bpf: make the verifier tracks the "not equal" for regs
  selftests/bpf: activate the OP_NE login in range_cond()
  selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

 kernel/bpf/verifier.c                         | 38 ++++++++++++++++++-
 .../selftests/bpf/prog_tests/reg_bounds.c     | 20 +++++++---
 .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++
 3 files changed, 78 insertions(+), 7 deletions(-)

-- 
2.39.2

[PATCH bpf-next v4 1/3] bpf: make the verifier tracks the "not equal" for regs

[Menglong Dong]

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))
-- 
2.39.2

[PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

[Menglong Dong]

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.

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>
---
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     | 20 +++++++++++++------
 1 file changed, 14 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 0c9abd279e18..c9dc9fe73211 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,19 @@ static struct subtest_case crafted_cases[] = {
 	{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}},
+
+	/* edge overlap testings for BPF_NE, skipped some cases that already
+	 * exist above.
+	 */
+	{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}},
+	{S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
+	{S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+	{S32, U32, {(u32)(s32)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

[PATCH bpf-next v4 3/3] selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

[Menglong Dong]

Add testcase for the logic that the verifier tracks the BPF_JNE for regs.
The assembly function "reg_not_equal()" 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>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index ec430b71730b..3fe2ce2b3f21 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -1075,4 +1075,31 @@ l0_%=:	r0 = 0;						\
 	: __clobber_all);
 }
 
+SEC("tc")
+__description("bounds check with JMP_NE for reg edge")
+__success __retval(0)
+__naked void reg_not_equal(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;						\
+	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

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

[Alexei Starovoitov]

On Sun, Dec 17, 2023 at 5:18 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 login 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>
> ---
> 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     | 20 +++++++++++++------
>  1 file changed, 14 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 0c9abd279e18..c9dc9fe73211 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,19 @@ static struct subtest_case crafted_cases[] = {
>         {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}},
> +
> +       /* edge overlap testings for BPF_NE, skipped some cases that already
> +        * exist above.
> +        */
> +       {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}},
> +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
> +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
> +       {S32, U32, {(u32)(s32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},

I think you're copying the style of the casts from few lines above,
but (s32)S32_MIN is unnecessary. S32_MIN includes the cast already.
Please remove and fix the above lines too.

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

[Menglong Dong]

On Mon, Dec 18, 2023 at 2:20 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Sun, Dec 17, 2023 at 5:18 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 login 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>
> > ---
> > 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     | 20 +++++++++++++------
> >  1 file changed, 14 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 0c9abd279e18..c9dc9fe73211 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,19 @@ static struct subtest_case crafted_cases[] = {
> >         {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}},
> > +
> > +       /* edge overlap testings for BPF_NE, skipped some cases that already
> > +        * exist above.
> > +        */
> > +       {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}},
> > +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
> > +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
> > +       {S32, U32, {(u32)(s32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
>
> I think you're copying the style of the casts from few lines above,
> but (s32)S32_MIN is unnecessary. S32_MIN includes the cast already.
> Please remove and fix the above lines too.

Enn...yes, I simulated the usage of S32_MIN from the lines above.
You are right, the s32 casting is unnecessary, I'll just keep the
u32 casting.

I'll wait a while before sending the next version to see if
someone else any comments on this series.

Thanks!
Menglong Dong

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

[Andrii Nakryiko]

On Sun, Dec 17, 2023 at 5:18 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 login 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>
> ---
> 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     | 20 +++++++++++++------
>  1 file changed, 14 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 0c9abd279e18..c9dc9fe73211 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,19 @@ static struct subtest_case crafted_cases[] = {
>         {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}},
> +
> +       /* edge overlap testings for BPF_NE, skipped some cases that already
> +        * exist above.
> +        */
> +       {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}},

missing case where we compare against U32_MAX constant?

> +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
> +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
> +       {S32, U32, {(u32)(s32)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
>

Re: [PATCH bpf-next v4 3/3] selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

[Andrii Nakryiko]

On Sun, Dec 17, 2023 at 5:18 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()" 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>
> ---
>  .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++++++++
>  1 file changed, 27 insertions(+)
>

LGTM, but please add a comment that we rely on bpf_skb_store_byte's
4th argument being defined as ARG_CONST_SIZE, so zero is not allowed.
And that r4 == 0 check is providing us this exclusion of zero from
initial [0, 7] range.


> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> index ec430b71730b..3fe2ce2b3f21 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> @@ -1075,4 +1075,31 @@ l0_%=:   r0 = 0;                                         \
>         : __clobber_all);
>  }
>
> +SEC("tc")
> +__description("bounds check with JMP_NE for reg edge")
> +__success __retval(0)
> +__naked void reg_not_equal(void)

technically, you are testing `r4 == 0` :) so maybe call the test
reg_equal_const or something. And then add similar test where you
actually have `r4 != 0`, called req_no_equal_const?

> +{
> +       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;                                         \
> +       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
>

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

[Menglong Dong]

On Tue, Dec 19, 2023 at 1:58 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Sun, Dec 17, 2023 at 5:18 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 login 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>
> > ---
> > 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     | 20 +++++++++++++------
> >  1 file changed, 14 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 0c9abd279e18..c9dc9fe73211 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,19 @@ static struct subtest_case crafted_cases[] = {
> >         {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}},
> > +
> > +       /* edge overlap testings for BPF_NE, skipped some cases that already
> > +        * exist above.
> > +        */
> > +       {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}},
>
> missing case where we compare against U32_MAX constant?
>

Hello,

There seems to already be one existing above:

{U32, S32, {0, U32_MAX}, {U32_MAX, U32_MAX}},

> > +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
> > +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
> > +       {S32, U32, {(u32)(s32)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
> >

Re: [PATCH bpf-next v4 3/3] selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

[Menglong Dong]

On Tue, Dec 19, 2023 at 2:03 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Sun, Dec 17, 2023 at 5:18 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()" 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>
> > ---
> >  .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++++++++
> >  1 file changed, 27 insertions(+)
> >
>
> LGTM, but please add a comment that we rely on bpf_skb_store_byte's
> 4th argument being defined as ARG_CONST_SIZE, so zero is not allowed.
> And that r4 == 0 check is providing us this exclusion of zero from
> initial [0, 7] range.
>

Okay, sounds great! BTW, should I add such a comment to the
commit log or to the assembly function?

>
> > diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> > index ec430b71730b..3fe2ce2b3f21 100644
> > --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> > +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> > @@ -1075,4 +1075,31 @@ l0_%=:   r0 = 0;                                         \
> >         : __clobber_all);
> >  }
> >
> > +SEC("tc")
> > +__description("bounds check with JMP_NE for reg edge")
> > +__success __retval(0)
> > +__naked void reg_not_equal(void)
>
> technically, you are testing `r4 == 0` :) so maybe call the test
> reg_equal_const or something. And then add similar test where you
> actually have `r4 != 0`, called req_no_equal_const?
>

Yeah, that makes sense. I'll add such a test in the next version.

Thanks!
Menglong Dong

> > +{
> > +       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;                                         \
> > +       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
> >

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

[Andrii Nakryiko]

On Mon, Dec 18, 2023 at 6:22 PM Menglong Dong <menglong8.dong@gmail.com> wrote:
>
> On Tue, Dec 19, 2023 at 1:58 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Sun, Dec 17, 2023 at 5:18 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 login 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>
> > > ---
> > > 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     | 20 +++++++++++++------
> > >  1 file changed, 14 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 0c9abd279e18..c9dc9fe73211 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,19 @@ static struct subtest_case crafted_cases[] = {
> > >         {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}},
> > > +
> > > +       /* edge overlap testings for BPF_NE, skipped some cases that already
> > > +        * exist above.
> > > +        */
> > > +       {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}},
> >
> > missing case where we compare against U32_MAX constant?
> >
>
> Hello,
>
> There seems to already be one existing above:
>
> {U32, S32, {0, U32_MAX}, {U32_MAX, U32_MAX}},
>

This one is doing S32 comparisons. For == and != it doesn't matter,
but it is a different use case. So I'd add U32, U32 case nevertheless.

> > > +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
> > > +       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
> > > +       {S32, U32, {(u32)(s32)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
> > >

Re: [PATCH bpf-next v4 3/3] selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

[Andrii Nakryiko]

On Mon, Dec 18, 2023 at 6:27 PM Menglong Dong <menglong8.dong@gmail.com> wrote:
>
> On Tue, Dec 19, 2023 at 2:03 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Sun, Dec 17, 2023 at 5:18 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()" 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>
> > > ---
> > >  .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++++++++
> > >  1 file changed, 27 insertions(+)
> > >
> >
> > LGTM, but please add a comment that we rely on bpf_skb_store_byte's
> > 4th argument being defined as ARG_CONST_SIZE, so zero is not allowed.
> > And that r4 == 0 check is providing us this exclusion of zero from
> > initial [0, 7] range.
> >
>
> Okay, sounds great! BTW, should I add such a comment to the
> commit log or to the assembly function?
>

I'd leave it in the code, next to the function itself

> >
> > > diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> > > index ec430b71730b..3fe2ce2b3f21 100644
> > > --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> > > +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> > > @@ -1075,4 +1075,31 @@ l0_%=:   r0 = 0;                                         \
> > >         : __clobber_all);
> > >  }
> > >
> > > +SEC("tc")
> > > +__description("bounds check with JMP_NE for reg edge")
> > > +__success __retval(0)
> > > +__naked void reg_not_equal(void)
> >
> > technically, you are testing `r4 == 0` :) so maybe call the test
> > reg_equal_const or something. And then add similar test where you
> > actually have `r4 != 0`, called req_no_equal_const?
> >
>
> Yeah, that makes sense. I'll add such a test in the next version.
>
> Thanks!
> Menglong Dong
>
> > > +{
> > > +       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;                                         \
> > > +       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
> > >