Skip to contentSkip to conversation

bpf: make the verifier trace the "not qeual" for regs

PATCH Superseded Menglong Dong 3 participants 7 messages Dec 10, 2023 – Dec 12, 2023

Subsystems (2)

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bpf: make the verifier trace the "not qeual" for regs

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.

---
 kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 44 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +44 -1
index 727a59e4a647..7b074ac93190 100644
@@ -1764,6 +1764,40 @@ static void __mark_reg_const_zero(struct bpf_reg_state *reg)
 	reg->type = SCALAR_VALUE;
 }
 
+#define CHECK_REG_MIN(value)			\
+do {						\
+	if ((value) == (typeof(value))imm)	\
+		value++;			\
+} while (0)
+
+#define CHECK_REG_MAX(value)			\
+do {						\
+	if ((value) == (typeof(value))imm)	\
+		value--;			\
+} while (0)
+
+static void mark_reg32_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+		CHECK_REG_MIN(reg->s32_min_value);
+		CHECK_REG_MAX(reg->s32_max_value);
+		CHECK_REG_MIN(reg->u32_min_value);
+		CHECK_REG_MAX(reg->u32_max_value);
+}
+
+static void mark_reg_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+		CHECK_REG_MIN(reg->smin_value);
+		CHECK_REG_MAX(reg->smax_value);
+
+		CHECK_REG_MIN(reg->umin_value);
+		CHECK_REG_MAX(reg->umax_value);
+
+		CHECK_REG_MIN(reg->s32_min_value);
+		CHECK_REG_MAX(reg->s32_max_value);
+		CHECK_REG_MIN(reg->u32_min_value);
+		CHECK_REG_MAX(reg->u32_max_value);
+}
+
 static void mark_reg_known_zero(struct bpf_verifier_env *env,
 				struct bpf_reg_state *regs, u32 regno)
 {
@@ -14332,7 +14366,16 @@ 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 */
+		/* try to recompute the bound of reg1 if reg2 is a const and
+		 * is exactly the edge of reg1.
+		 */
+		if (is_reg_const(reg2, is_jmp32)) {
+			val = reg_const_value(reg2, is_jmp32);
+			if (is_jmp32)
+				mark_reg32_not_equal(reg1, val);
+			else
+				mark_reg_not_equal(reg1, val);
+		}
 		break;
 	case BPF_JSET:
 		if (!is_reg_const(reg2, is_jmp32))
Signature · 1 line
2.39.2
reviewer
#1 lore raw
Quoted 14 lines · 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 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);
   }

Could you have a C test to demonstrate this example? Also, you should have a set of inline asm code (progs/verifier*.c) to test various cases as in mark_reg32_not_equal() and mark_reg_not_equal().

Quoted 26 lines

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.

---
  kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++-
  1 file changed, 44 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +4 -0
index 727a59e4a647..7b074ac93190 100644
@@ -1764,6 +1764,40 @@ static void __mark_reg_const_zero(struct bpf_reg_state *reg)
  	reg->type = SCALAR_VALUE;
  }
 
+#define CHECK_REG_MIN(value)			\
+do {						\
+	if ((value) == (typeof(value))imm)	\
+		value++;			\

kernel/bpf/verifier.c static void __mark_reg_const_zero(struct bpf_reg_state *reg) · line 1780

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+} while (0)
+
+#define CHECK_REG_MAX(value)			\
+do {						\
+	if ((value) == (typeof(value))imm)	\
+		value--;			\
+} while (0)
+
+static void mark_reg32_not_equal(struct bpf_reg_state *reg, u64 imm)
+{

What if reg->s32_min_value == imm and reg->s32_max_value == imm? Has this been handled in previous verifier logic?

Quoted 41 lines
kernel/bpf/verifier.c +30 -1
+		CHECK_REG_MIN(reg->s32_min_value);
+		CHECK_REG_MAX(reg->s32_max_value);
+		CHECK_REG_MIN(reg->u32_min_value);
+		CHECK_REG_MAX(reg->u32_max_value);
+}
+
+static void mark_reg_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+		CHECK_REG_MIN(reg->smin_value);
+		CHECK_REG_MAX(reg->smax_value);
+
+		CHECK_REG_MIN(reg->umin_value);
+		CHECK_REG_MAX(reg->umax_value);
+
+		CHECK_REG_MIN(reg->s32_min_value);
+		CHECK_REG_MAX(reg->s32_max_value);
+		CHECK_REG_MIN(reg->u32_min_value);
+		CHECK_REG_MAX(reg->u32_max_value);
+}
+
  static void mark_reg_known_zero(struct bpf_verifier_env *env,
  				struct bpf_reg_state *regs, u32 regno)
  {
@@ -14332,7 +14366,16 @@ 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 */
+		/* try to recompute the bound of reg1 if reg2 is a const and
+		 * is exactly the edge of reg1.
+		 */
+		if (is_reg_const(reg2, is_jmp32)) {
+			val = reg_const_value(reg2, is_jmp32);
+			if (is_jmp32)
+				mark_reg32_not_equal(reg1, val);
+			else
+				mark_reg_not_equal(reg1, val);
+		}
  		break;
  	case BPF_JSET:
  		if (!is_reg_const(reg2, is_jmp32))
#2 lore raw

Hello,

Quoted 18 lines · Yonghong Song
Quoted 14 lines · 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 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);
   }
Quoted 5 lines

Could you have a C test to demonstrate this example? Also, you should have a set of inline asm code (progs/verifier*.c) to test various cases as in mark_reg32_not_equal() and mark_reg_not_equal().

Yeah! I found that this part is tested in the test_progs/reg_bounds_crafted too, and this commit failed that test case, which I should fix in the next version.

Quoted 31 lines
Quoted 31 lines

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.

---
  kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++-
  1 file changed, 44 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +9 -0
index 727a59e4a647..7b074ac93190 100644
@@ -1764,6 +1764,40 @@ static void __mark_reg_const_zero(struct bpf_reg_state *reg)
      reg->type = SCALAR_VALUE;
  }
 
+#define CHECK_REG_MIN(value)                 \
+do {                                         \
+     if ((value) == (typeof(value))imm)      \
+             value++;                        \
+} while (0)
+
+#define CHECK_REG_MAX(value)                 \
+do {                                         \
+     if ((value) == (typeof(value))imm)      \
Quoted 8 lines

kernel/bpf/verifier.c static void __mark_reg_const_zero(struct bpf_reg_state *reg) · line 1780

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+             value--;                        \
+} while (0)
+
+static void mark_reg32_not_equal(struct bpf_reg_state *reg, u64 imm)
+{

What if reg->s32_min_value == imm and reg->s32_max_value == imm? Has this been handled in previous verifier logic?

Will such a case happen? In current code path, the src reg is a const, and the is_branch_taken() will return 0 or 1 if the dst_reg->s32_min_value == dst_reg->s32_max_value.

Enn......maybe we can do more checking here in case that someone calls this function in another place.

Thanks!
Menglong Dong

Quoted 42 lines
Quoted 42 lines
kernel/bpf/verifier.c +30 -1
+             CHECK_REG_MIN(reg->s32_min_value);
+             CHECK_REG_MAX(reg->s32_max_value);
+             CHECK_REG_MIN(reg->u32_min_value);
+             CHECK_REG_MAX(reg->u32_max_value);
+}
+
+static void mark_reg_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+             CHECK_REG_MIN(reg->smin_value);
+             CHECK_REG_MAX(reg->smax_value);
+
+             CHECK_REG_MIN(reg->umin_value);
+             CHECK_REG_MAX(reg->umax_value);
+
+             CHECK_REG_MIN(reg->s32_min_value);
+             CHECK_REG_MAX(reg->s32_max_value);
+             CHECK_REG_MIN(reg->u32_min_value);
+             CHECK_REG_MAX(reg->u32_max_value);
+}
+
  static void mark_reg_known_zero(struct bpf_verifier_env *env,
                              struct bpf_reg_state *regs, u32 regno)
  {
@@ -14332,7 +14366,16 @@ 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 */
+             /* try to recompute the bound of reg1 if reg2 is a const and
+              * is exactly the edge of reg1.
+              */
+             if (is_reg_const(reg2, is_jmp32)) {
+                     val = reg_const_value(reg2, is_jmp32);
+                     if (is_jmp32)
+                             mark_reg32_not_equal(reg1, val);
+                     else
+                             mark_reg_not_equal(reg1, val);
+             }
              break;
      case BPF_JSET:
              if (!is_reg_const(reg2, is_jmp32))
reviewer
#3 lore raw
Quoted 65 lines · Menglong Dong

Hello,

Quoted 16 lines · Yonghong Song
Quoted 14 lines · 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 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);
    }
Quoted 5 lines

Could you have a C test to demonstrate this example? Also, you should have a set of inline asm code (progs/verifier*.c) to test various cases as in mark_reg32_not_equal() and mark_reg_not_equal().

Yeah! I found that this part is tested in the test_progs/reg_bounds_crafted too, and this commit failed that test case, which I should fix in the next version.

Quoted 21 lines
Quoted 21 lines

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.

---
   kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++-
   1 file changed, 44 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +0 -0
index 727a59e4a647..7b074ac93190 100644
@@ -1764,6 +1764,40 @@ static void __mark_reg_const_zero(struct bpf_reg_state *reg)
       reg->type = SCALAR_VALUE;
   }
 
Quoted 16 lines
Quoted 4 lines
kernel/bpf/verifier.c +4 -0
+#define CHECK_REG_MIN(value)                 \
+do {                                         \
+     if ((value) == (typeof(value))imm)      \
+             value++;                        \

kernel/bpf/verifier.c static void __mark_reg_const_zero(struct bpf_reg_state *reg) · line 1780

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+} while (0)
+
+#define CHECK_REG_MAX(value)                 \
+do {                                         \
+     if ((value) == (typeof(value))imm)      \
+             value--;                        \
+} while (0)
+
+static void mark_reg32_not_equal(struct bpf_reg_state *reg, u64 imm)
+{

What if reg->s32_min_value == imm and reg->s32_max_value == imm? Has this been handled in previous verifier logic?

Quoted 6 lines

Will such a case happen? In current code path, the src reg is a const, and the is_branch_taken() will return 0 or 1 if the dst_reg->s32_min_value == dst_reg->s32_max_value.

Enn......maybe we can do more checking here in case that someone calls this function in another place.

I double checked the source code as well. Indeed, 'reg' should not be a constant as it has been handled in is_branch_taken() properly. Ignore my comments above then. Thanks!

Quoted 45 lines

Thanks!
Menglong Dong

Quoted 41 lines
Quoted 41 lines
kernel/bpf/verifier.c +30 -1
+             CHECK_REG_MIN(reg->s32_min_value);
+             CHECK_REG_MAX(reg->s32_max_value);
+             CHECK_REG_MIN(reg->u32_min_value);
+             CHECK_REG_MAX(reg->u32_max_value);
+}
+
+static void mark_reg_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+             CHECK_REG_MIN(reg->smin_value);
+             CHECK_REG_MAX(reg->smax_value);
+
+             CHECK_REG_MIN(reg->umin_value);
+             CHECK_REG_MAX(reg->umax_value);
+
+             CHECK_REG_MIN(reg->s32_min_value);
+             CHECK_REG_MAX(reg->s32_max_value);
+             CHECK_REG_MIN(reg->u32_min_value);
+             CHECK_REG_MAX(reg->u32_max_value);
+}
+
   static void mark_reg_known_zero(struct bpf_verifier_env *env,
                               struct bpf_reg_state *regs, u32 regno)
   {
@@ -14332,7 +14366,16 @@ 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 */
+             /* try to recompute the bound of reg1 if reg2 is a const and
+              * is exactly the edge of reg1.
+              */
+             if (is_reg_const(reg2, is_jmp32)) {
+                     val = reg_const_value(reg2, is_jmp32);
+                     if (is_jmp32)
+                             mark_reg32_not_equal(reg1, val);
+                     else
+                             mark_reg_not_equal(reg1, val);
+             }
               break;
       case BPF_JSET:
               if (!is_reg_const(reg2, is_jmp32))
#4 lore raw
In reply to Menglong Dong
Quoted 60 lines · 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 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.

---
 kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 44 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +23 -0
index 727a59e4a647..7b074ac93190 100644
@@ -1764,6 +1764,40 @@ static void __mark_reg_const_zero(struct bpf_reg_state *reg)
        reg->type = SCALAR_VALUE;
 }
 
+#define CHECK_REG_MIN(value)                   \
+do {                                           \
+       if ((value) == (typeof(value))imm)      \
+               value++;                        \
+} while (0)
+
+#define CHECK_REG_MAX(value)                   \
+do {                                           \
+       if ((value) == (typeof(value))imm)      \
+               value--;                        \
+} while (0)
+
+static void mark_reg32_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+               CHECK_REG_MIN(reg->s32_min_value);
+               CHECK_REG_MAX(reg->s32_max_value);
+               CHECK_REG_MIN(reg->u32_min_value);
+               CHECK_REG_MAX(reg->u32_max_value);
+}
+
+static void mark_reg_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+               CHECK_REG_MIN(reg->smin_value);

kernel/bpf/verifier.c static void __mark_reg_const_zero(struct bpf_reg_state *reg) · line 1799

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+               CHECK_REG_MAX(reg->smax_value);
+
+               CHECK_REG_MIN(reg->umin_value);
+               CHECK_REG_MAX(reg->umax_value);
+
+               CHECK_REG_MIN(reg->s32_min_value);
+               CHECK_REG_MAX(reg->s32_max_value);
+               CHECK_REG_MIN(reg->u32_min_value);
+               CHECK_REG_MAX(reg->u32_max_value);
+}

please don't use macros for this, this code is tricky enough without having to jump around double-checking what exactly macros are doing. Just code it explicitly.

Also I don't see the need for mark_reg32_not_equal() and mark_reg_not_equal() helper functions, there is just one place where this logic is going to be called from, so let's add code right there.

Quoted 25 lines
kernel/bpf/verifier.c +11 -2
+
 static void mark_reg_known_zero(struct bpf_verifier_env *env,
                                struct bpf_reg_state *regs, u32 regno)
 {
@@ -14332,7 +14366,16 @@ 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 */
+               /* try to recompute the bound of reg1 if reg2 is a const and
+                * is exactly the edge of reg1.
+                */
+               if (is_reg_const(reg2, is_jmp32)) {
+                       val = reg_const_value(reg2, is_jmp32);
+                       if (is_jmp32)
+                               mark_reg32_not_equal(reg1, val);
+                       else
+                               mark_reg_not_equal(reg1, val);
+               }
                break;
        case BPF_JSET:
                if (!is_reg_const(reg2, is_jmp32))
--

2.39.2

#5 lore raw
Quoted 68 lines · Andrii Nakryiko
Quoted 66 lines · 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 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.

---
 kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 44 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +29 -0
index 727a59e4a647..7b074ac93190 100644
@@ -1764,6 +1764,40 @@ static void __mark_reg_const_zero(struct bpf_reg_state *reg)
        reg->type = SCALAR_VALUE;
 }
 
+#define CHECK_REG_MIN(value)                   \
+do {                                           \
+       if ((value) == (typeof(value))imm)      \
+               value++;                        \
+} while (0)
+
+#define CHECK_REG_MAX(value)                   \
+do {                                           \
+       if ((value) == (typeof(value))imm)      \
+               value--;                        \
+} while (0)
+
+static void mark_reg32_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+               CHECK_REG_MIN(reg->s32_min_value);
+               CHECK_REG_MAX(reg->s32_max_value);
+               CHECK_REG_MIN(reg->u32_min_value);
+               CHECK_REG_MAX(reg->u32_max_value);
+}
+
+static void mark_reg_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+               CHECK_REG_MIN(reg->smin_value);
+               CHECK_REG_MAX(reg->smax_value);
+
+               CHECK_REG_MIN(reg->umin_value);
+               CHECK_REG_MAX(reg->umax_value);
+
+               CHECK_REG_MIN(reg->s32_min_value);
Quoted 9 lines

kernel/bpf/verifier.c static void __mark_reg_const_zero(struct bpf_reg_state *reg) · line 1785

Quoted 4 lines
kernel/bpf/verifier.c +4 -0
+               CHECK_REG_MAX(reg->s32_max_value);
+               CHECK_REG_MIN(reg->u32_min_value);
+               CHECK_REG_MAX(reg->u32_max_value);
+}

please don't use macros for this, this code is tricky enough without having to jump around double-checking what exactly macros are doing. Just code it explicitly.

Okay!

Quoted 4 lines

Also I don't see the need for mark_reg32_not_equal() and mark_reg_not_equal() helper functions, there is just one place where this logic is going to be called from, so let's add code right there.

Yeah, you are right. And I just found that you have already implemented the test case for this logic in reg_bounds.c/range_cond(). I wonder why this logic is not implemented in the verifier yet? Am I missing something?

Thanks!
Menglong Dong

Quoted 25 lines
Quoted 25 lines
kernel/bpf/verifier.c +11 -2
+
 static void mark_reg_known_zero(struct bpf_verifier_env *env,
                                struct bpf_reg_state *regs, u32 regno)
 {
@@ -14332,7 +14366,16 @@ 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 */
+               /* try to recompute the bound of reg1 if reg2 is a const and
+                * is exactly the edge of reg1.
+                */
+               if (is_reg_const(reg2, is_jmp32)) {
+                       val = reg_const_value(reg2, is_jmp32);
+                       if (is_jmp32)
+                               mark_reg32_not_equal(reg1, val);
+                       else
+                               mark_reg_not_equal(reg1, val);
+               }
                break;
        case BPF_JSET:
                if (!is_reg_const(reg2, is_jmp32))
--

2.39.2

#6 lore raw
Quoted 88 lines · Menglong Dong
Quoted 68 lines · Andrii Nakryiko
Quoted 66 lines · 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 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.

---
 kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 44 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +29 -0
index 727a59e4a647..7b074ac93190 100644
@@ -1764,6 +1764,40 @@ static void __mark_reg_const_zero(struct bpf_reg_state *reg)
        reg->type = SCALAR_VALUE;
 }
 
+#define CHECK_REG_MIN(value)                   \
+do {                                           \
+       if ((value) == (typeof(value))imm)      \
+               value++;                        \
+} while (0)
+
+#define CHECK_REG_MAX(value)                   \
+do {                                           \
+       if ((value) == (typeof(value))imm)      \
+               value--;                        \
+} while (0)
+
+static void mark_reg32_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+               CHECK_REG_MIN(reg->s32_min_value);
+               CHECK_REG_MAX(reg->s32_max_value);
+               CHECK_REG_MIN(reg->u32_min_value);
+               CHECK_REG_MAX(reg->u32_max_value);
+}
+
+static void mark_reg_not_equal(struct bpf_reg_state *reg, u64 imm)
+{
+               CHECK_REG_MIN(reg->smin_value);
+               CHECK_REG_MAX(reg->smax_value);
+
+               CHECK_REG_MIN(reg->umin_value);
+               CHECK_REG_MAX(reg->umax_value);
+
+               CHECK_REG_MIN(reg->s32_min_value);
Quoted 9 lines

kernel/bpf/verifier.c static void __mark_reg_const_zero(struct bpf_reg_state *reg) · line 1785

Quoted 4 lines
kernel/bpf/verifier.c +4 -0
+               CHECK_REG_MAX(reg->s32_max_value);
+               CHECK_REG_MIN(reg->u32_min_value);
+               CHECK_REG_MAX(reg->u32_max_value);
+}

please don't use macros for this, this code is tricky enough without having to jump around double-checking what exactly macros are doing. Just code it explicitly.

Okay!

Quoted 4 lines

Also I don't see the need for mark_reg32_not_equal() and mark_reg_not_equal() helper functions, there is just one place where this logic is going to be called from, so let's add code right there.

Quoted 4 lines

Yeah, you are right. And I just found that you have already implemented the test case for this logic in reg_bounds.c/range_cond(). I wonder why this logic is not implemented in the verifier yet? Am I missing something?

No, I just didn't want to add yet more verifier changes in my original patch set on extending reg bounds logic.

Quoted 29 lines

Thanks!
Menglong Dong

Quoted 25 lines
Quoted 25 lines
kernel/bpf/verifier.c +11 -2
+
 static void mark_reg_known_zero(struct bpf_verifier_env *env,
                                struct bpf_reg_state *regs, u32 regno)
 {
@@ -14332,7 +14366,16 @@ 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 */
+               /* try to recompute the bound of reg1 if reg2 is a const and
+                * is exactly the edge of reg1.
+                */
+               if (is_reg_const(reg2, is_jmp32)) {
+                       val = reg_const_value(reg2, is_jmp32);
+                       if (is_jmp32)
+                               mark_reg32_not_equal(reg1, val);
+                       else
+                               mark_reg_not_equal(reg1, val);
+               }
                break;
        case BPF_JSET:
                if (!is_reg_const(reg2, is_jmp32))
--

2.39.2