[PATCH 18/25] bpf/validate: fix BPF_AND min calculations

[Marat Khalili <marat.khalili@huawei.com>]

Function `eval_and` calculated both signed (if positive) and unsigned
minimum values as bitwise AND between corresponding minimums, which is
incorrect since intermediate values can have zeroes in bits where
minimum values don't.

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

    Tested program:
        0:  mov r0, #0x0
        1:  ldxdw r2, [r1 + 0]
        2:  jlt r2, #0x6, L8
        3:  jgt r2, #0x8, L8
        4:  jslt r2, #0x6, L8
        5:  jsgt r2, #0x8, L8
        6:  and r2, #0x5  ; tested instruction
        7:  mov r0, #0x1
        8:  exit
    Pre-state:
       r2:  6..8
    Post-state:
       r2:  4..7

After the tested instruction validator considers r2 to be equal or
greater than 4, however if 8 was loaded on step 1 it is possible for it
to be zero (0x8 & 0x5 == 0).

Use zero as a new safe lower bound for both signed (if positive) and
unsigned minimum. Add test.

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

Signed-off-by: Marat Khalili <marat.khalili@huawei.com>
---
 app/test/test_bpf_validate.c | 17 +++++++++++++++++
 lib/bpf/bpf_validate.c       |  4 ++--
 2 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/app/test/test_bpf_validate.c b/app/test/test_bpf_validate.c
index 4b06918c5cea..646313cdacf2 100644
--- a/app/test/test_bpf_validate.c
+++ b/app/test/test_bpf_validate.c
@@ -1384,6 +1384,23 @@ test_alu64_add_x_scalar_scalar(void)
 REGISTER_FAST_TEST(bpf_validate_alu64_add_x_scalar_scalar_autotest, NOHUGE_OK, ASAN_OK,
 	test_alu64_add_x_scalar_scalar);
 
+/* 64-bit bitwise AND between a scalar range and immediate. */
+static int
+test_alu64_and_k(void)
+{
+	return verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (EBPF_ALU64 | BPF_AND | BPF_K),
+			.imm = 5,
+		},
+		.pre.dst = make_signed_domain(6, 8),
+		.post.dst = make_signed_domain(0, 7),
+	});
+}
+
+REGISTER_FAST_TEST(bpf_validate_alu64_and_k_autotest, NOHUGE_OK, ASAN_OK,
+	test_alu64_and_k);
+
 /* 64-bit division and modulo of UINT64_MAX*2/3. */
 static int
 test_alu64_div_mod_big_constant(void)
diff --git a/lib/bpf/bpf_validate.c b/lib/bpf/bpf_validate.c
index fbae70df924e..4dbf3a3ef892 100644
--- a/lib/bpf/bpf_validate.c
+++ b/lib/bpf/bpf_validate.c
@@ -848,7 +848,7 @@ eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 		rd->u.max &= rs->u.max;
 	} else {
 		rd->u.max = eval_uand_max(rd->u.max, rs->u.max, opsz);
-		rd->u.min &= rs->u.min;
+		rd->u.min = 0;
 	}
 
 	/* both operands are constants */
@@ -859,7 +859,7 @@ eval_and(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 	} 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);
-		rd->s.min &= rs->s.min;
+		rd->s.min = 0;
 	} else
 		eval_smax_bound(rd, msk);
 }
-- 
2.43.0