[PATCH] bpf/validate: fix 32-bit BPF_AND/OR/XOR shift UBs

[PATCH] bpf/validate: fix 32-bit BPF_AND/OR/XOR shift UBs

[Marat Khalili]

Function `eval_umax_bits`  when calculating the mask matching the
register value counted leading zeroes in 64-bit representation but then
subtracted it from the instruction width (32 for BPF_ALU instructions)
producing zero or negative mask length, all unsupported by macro
`RTE_LEN2MASK`. This function is used by functions `eval_and`, `eval_or`
and `eval_xor` evaluating `BPF_ALU | BPF_AND`, `BPF_ALU | BPF_OR` and
`BPF_ALU | BPF_XOR` correspondingly

E.g. consider the following program with the current validation code:

    Tested program:
        0:  mov r0, #0x0
        1:  ldxdw r2, [r1 + 0]
        2:  jgt r2, #0x7fffffff, L7
        3:  jslt r2, #0x0, L7
        4:  jsgt r2, #0x7fffffff, L7
        5:  and32 r2, #0x7fffffff  ; tested instruction
        6:  mov r0, #0x1
        7:  exit
    Pre-state:
       r2:  0..INT32_MAX
    Post-state:
       r2:  0..INT64_MAX

At step 6 validator presumed that r2 may have values up to INT64_MAX,
which is impossible for the 32-bit bitwise operation on 32-bit operands
and could cause false positives.

With sanitizer the following diagnostic is generated:

    lib/bpf/bpf_validate.c:821:9: runtime error: shift exponent 65 is
    too large for 64-bit type 'long unsigned int'
        #0 0x00000837d9b5 in eval_umax_bits lib/bpf/bpf_validate.c:821
        #1 0x00000837d9f3 in eval_uand_max lib/bpf/bpf_validate.c:828
        #2 0x00000837df83 in eval_and lib/bpf/bpf_validate.c:851
        #3 0x000008384faf in eval_alu lib/bpf/bpf_validate.c:1155
        #4 0x000008396c24 in evaluate lib/bpf/bpf_validate.c:2999

Similarly for `or32 r2, #0x0`, `xor32 r2, #0x0`.

Found using ESBMC (https://esbmc.github.io/docs/) through an agentic
verification workflow, with integer-overflow and undefined-shift checks
enabled.

To fix the issue change to subtracting clz64 result from 64 instead of
instruction width, add tests. Remove no-longer-used opsz argument
(truncation of inputs to 32 bits is handled by the caller `eval_alu`).

Fixes: 8021917293d0 ("bpf: add extra validation for input BPF program")
Cc: stable@dpdk.org

Reported-by: Sebti Mouelhi <sebti.mouelhi@huawei.com>
Signed-off-by: Marat Khalili <marat.khalili@huawei.com>
Acked-by: Konstantin Ananyev <konstantin.ananyev@huawei.com>
---
 app/test/test_bpf_validate.c | 45 ++++++++++++++++++++++++++++++++++++
 lib/bpf/bpf_validate.c       | 43 ++++++++++++++++------------------
 2 files changed, 65 insertions(+), 23 deletions(-)

diff --git a/app/test/test_bpf_validate.c b/app/test/test_bpf_validate.c
index 066f1fa156ae..e1c35a41a4f9 100644
--- a/app/test/test_bpf_validate.c
+++ b/app/test/test_bpf_validate.c
@@ -1277,6 +1277,48 @@ verify_comparison(struct verify_instruction_param prm, bool also_signed)
 
 /* TESTS FOR SPECIFIC INSTRUCTIONS */
 
+/* 32-bit bitwise AND between a scalar range and immediate, triggering UB. */
+static int
+test_alu32_and_k_ub(void)
+{
+	return verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_ALU | BPF_AND | BPF_K),
+			.imm = INT32_MAX,
+		},
+		.pre.dst = make_unsigned_domain(0, INT32_MAX),
+		.post.dst = make_unsigned_domain(0, INT32_MAX),
+	});
+}
+
+/* 32-bit bitwise OR between a scalar range and immediate, triggering UB. */
+static int
+test_alu32_or_k_ub(void)
+{
+	return verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_ALU | BPF_OR | BPF_K),
+			.imm = 0,
+		},
+		.pre.dst = make_unsigned_domain(0, INT32_MAX),
+		.post.dst = make_unsigned_domain(0, INT32_MAX),
+	});
+}
+
+/* 32-bit bitwise XOR between a scalar range and immediate, triggering UB. */
+static int
+test_alu32_xor_k_ub(void)
+{
+	return verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_ALU | BPF_XOR | BPF_K),
+			.imm = 0,
+		},
+		.pre.dst = make_unsigned_domain(0, INT32_MAX),
+		.post.dst = make_unsigned_domain(0, INT32_MAX),
+	});
+}
+
 /* 64-bit addition of immediate to a range. */
 static int
 test_alu64_add_k(void)
@@ -2187,6 +2229,9 @@ static struct
 unit_test_suite test_bpf_validate_suite  = {
 	.suite_name = "Test BPF Validate Unit Test Suite",
 	.unit_test_cases = {
+		TEST_CASE(test_alu32_and_k_ub),
+		TEST_CASE(test_alu32_or_k_ub),
+		TEST_CASE(test_alu32_xor_k_ub),
 		TEST_CASE(test_alu64_add_k),
 		TEST_CASE(test_alu64_add_k_pointer),
 		TEST_CASE(test_alu64_add_x_pointer_pointer),
diff --git a/lib/bpf/bpf_validate.c b/lib/bpf/bpf_validate.c
index f9960088a285..d3cd14f24683 100644
--- a/lib/bpf/bpf_validate.c
+++ b/lib/bpf/bpf_validate.c
@@ -812,43 +812,42 @@ eval_arsh(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 }
 
 static uint64_t
-eval_umax_bits(uint64_t v, size_t opsz)
+eval_umax_bits(uint64_t v)
 {
 	if (v == 0)
 		return 0;
 
 	v = rte_clz64(v);
-	return RTE_LEN2MASK(opsz - v, uint64_t);
+	return RTE_LEN2MASK(64 - v, uint64_t);
 }
 
 /* estimate max possible value for (v1 & v2) */
 static uint64_t
-eval_uand_max(uint64_t v1, uint64_t v2, size_t opsz)
+eval_uand_max(uint64_t v1, uint64_t v2)
 {
-	v1 = eval_umax_bits(v1, opsz);
-	v2 = eval_umax_bits(v2, opsz);
+	v1 = eval_umax_bits(v1);
+	v2 = eval_umax_bits(v2);
 	return (v1 & v2);
 }
 
 /* estimate max possible value for (v1 | v2) */
 static uint64_t
-eval_uor_max(uint64_t v1, uint64_t v2, size_t opsz)
+eval_uor_max(uint64_t v1, uint64_t v2)
 {
-	v1 = eval_umax_bits(v1, opsz);
-	v2 = eval_umax_bits(v2, opsz);
+	v1 = eval_umax_bits(v1);
+	v2 = eval_umax_bits(v2);
 	return (v1 | v2);
 }
 
 static void
-eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
-	uint64_t msk)
+eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
 {
 	/* both operands are constants */
 	if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
 		rd->u.min &= rs->u.min;
 		rd->u.max &= rs->u.max;
 	} else {
-		rd->u.max = eval_uand_max(rd->u.max, rs->u.max, opsz);
+		rd->u.max = eval_uand_max(rd->u.max, rs->u.max);
 		rd->u.min = 0;
 	}
 
@@ -859,22 +858,21 @@ eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 	/* at least one of operand is non-negative */
 	} else if (rd->s.min >= 0 || rs->s.min >= 0) {
 		rd->s.max = eval_uand_max(rd->s.max & (msk >> 1),
-			rs->s.max & (msk >> 1), opsz);
+			rs->s.max & (msk >> 1));
 		rd->s.min = 0;
 	} else
 		eval_smax_bound(rd, msk);
 }
 
 static void
-eval_or(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
-	uint64_t msk)
+eval_or(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
 {
 	/* both operands are constants */
 	if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
 		rd->u.min |= rs->u.min;
 		rd->u.max |= rs->u.max;
 	} else {
-		rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
+		rd->u.max = eval_uor_max(rd->u.max, rs->u.max);
 		rd->u.min = RTE_MAX(rd->u.min, rs->u.min);
 	}
 
@@ -885,22 +883,21 @@ eval_or(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 
 	/* both operands are non-negative */
 	} else if (rd->s.min >= 0 && rs->s.min >= 0) {
-		rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
+		rd->s.max = eval_uor_max(rd->s.max, rs->s.max);
 		rd->s.min = RTE_MAX(rd->s.min, rs->s.min);
 	} else
 		eval_smax_bound(rd, msk);
 }
 
 static void
-eval_xor(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
-	uint64_t msk)
+eval_xor(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
 {
 	/* both operands are constants */
 	if (rd->u.min == rd->u.max && rs->u.min == rs->u.max) {
 		rd->u.min ^= rs->u.min;
 		rd->u.max ^= rs->u.max;
 	} else {
-		rd->u.max = eval_uor_max(rd->u.max, rs->u.max, opsz);
+		rd->u.max = eval_uor_max(rd->u.max, rs->u.max);
 		rd->u.min = 0;
 	}
 
@@ -911,7 +908,7 @@ eval_xor(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 
 	/* both operands are non-negative */
 	} else if (rd->s.min >= 0 && rs->s.min >= 0) {
-		rd->s.max = eval_uor_max(rd->s.max, rs->s.max, opsz);
+		rd->s.max = eval_uor_max(rd->s.max, rs->s.max);
 		rd->s.min = 0;
 	} else
 		eval_smax_bound(rd, msk);
@@ -1152,11 +1149,11 @@ eval_alu(struct bpf_verifier *bvf, const struct ebpf_insn *ins)
 	else if (op == EBPF_ARSH)
 		eval_arsh(rd, &rs, opsz, msk);
 	else if (op == BPF_AND)
-		eval_and(rd, &rs, opsz, msk);
+		eval_and(rd, &rs, msk);
 	else if (op == BPF_OR)
-		eval_or(rd, &rs, opsz, msk);
+		eval_or(rd, &rs, msk);
 	else if (op == BPF_XOR)
-		eval_xor(rd, &rs, opsz, msk);
+		eval_xor(rd, &rs, msk);
 	else if (op == BPF_MUL)
 		eval_mul(rd, &rs, opsz, msk);
 	else if (op == BPF_DIV || op == BPF_MOD)
-- 
2.43.0

RE: [PATCH] bpf/validate: fix 32-bit BPF_AND/OR/XOR shift UBs

[Marat Khalili]

Answering the multiple AI reviews (why are there 3 of them, all via Claude?):


1. Test naming

> +/* 32-bit bitwise AND between a scalar range and immediate, triggering UB. */
> +static int
> +test_alu32_and_k_ub(void)

I agree with the AI that test names (and comments) are somewhat minimalist and
would require reader to check the commit message to find out what's going on.
The suggestion by AI to replace `_ui` with `_range` is not improving things
much however, so only doing it to placate the AI in case of another iteration.

As far as I know DPDK does not have a strict policy for cross-referencing bugs,
fixes and tests, so in the interest of time and code brevity not putting a huge
effort into it unless asked by actual humans.


2. Test coverage

Not contesting that current test coverage of these instructions is rudimentary
and needs to be expanded; 32-bit instructions as a whole need a lot of work.
It is all out of scope of this patch however, the added tests are sufficient
for reproducing the specific bug and confirming the fix.


Not addressing the rest of AI comments, they are all non-issues IMO.

Re: [PATCH] bpf/validate: fix 32-bit BPF_AND/OR/XOR shift UBs

[Thomas Monjalon]

25/08/2026 11:55, Marat Khalili:
[...]
> To fix the issue change to subtracting clz64 result from 64 instead of
> instruction width, add tests. Remove no-longer-used opsz argument
> (truncation of inputs to 32 bits is handled by the caller `eval_alu`).
> 
> Fixes: 8021917293d0 ("bpf: add extra validation for input BPF program")
> Cc: stable@dpdk.org
> 
> Reported-by: Sebti Mouelhi <sebti.mouelhi@huawei.com>
> Signed-off-by: Marat Khalili <marat.khalili@huawei.com>
> Acked-by: Konstantin Ananyev <konstantin.ananyev@huawei.com>

Applied, thanks.