[PATCH v2 22/25] bpf/validate: fix BPF_XOR signed min calculation

[Marat Khalili]

Function `eval_xor` calculated signed minimum using essentially unsigned
algorithm as long as any of the operands have non-negative range, which
is incorrect since it ignores any negative numbers that may have the
sign or any other bits set.

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

    Tested program:
        0:  mov r0, #0x0
        1:  ldxdw r2, [r1 + 0]
        2:  jsgt r2, #0x0, L5
        3:  xor r2, #0x0  ; tested instruction
        4:  mov r0, #0x1
        5:  exit
    Pre-state:
       r2:  INT64_MIN..0
    Post-state:
       r2:  0

After the tested instruction validator considers r2 to equal 0, however
if -1 was loaded on step 1 it is possible for it to be -1.

Set signed range to full if any of the operands can be negative,
otherwise (if both operands are non-negative) use same algorithm as for
unsigned numbers. Add test.

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

Reported-by: Claudia Cauli <claudiacauli at gmail.com>
Signed-off-by: Marat Khalili <marat.khalili at huawei.com>
Acked-by: Konstantin Ananyev <konstantin.ananyev at huawei.com>
---
Depends-on: series-38149 ("bpf: introduce extensible load API")
 app/test/test_bpf_validate.c | 17 +++++++++++++++++
 lib/bpf/bpf_validate.c       |  2 +-
 2 files changed, 18 insertions(+), 1 deletion(-)

diff --git a/app/test/test_bpf_validate.c b/app/test/test_bpf_validate.c
index 205373a4f8..a06d3254d6 100644
--- a/app/test/test_bpf_validate.c
+++ b/app/test/test_bpf_validate.c
@@ -1764,6 +1764,23 @@ test_alu64_sub_x_src_signed_max_zero(void)
 REGISTER_FAST_TEST(bpf_validate_alu64_sub_x_src_signed_max_zero_autotest, NOHUGE_OK, ASAN_OK,
 	test_alu64_sub_x_src_signed_max_zero);
 
+/* 64-bit bitwise XOR between a negative scalar range and zero immediate. */
+static int
+test_alu64_xor_k_negative(void)
+{
+	return verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (EBPF_ALU64 | BPF_XOR | BPF_K),
+			.imm = 0,
+		},
+		.pre.dst = make_signed_domain(INT64_MIN, 0),
+		.post.dst = unknown,
+	});
+}
+
+REGISTER_FAST_TEST(bpf_validate_alu64_xor_k_negative_autotest, NOHUGE_OK, ASAN_OK,
+	test_alu64_xor_k_negative);
+
 /* Jump if greater than immediate. */
 static int
 test_jmp64_jeq_k(void)
diff --git a/lib/bpf/bpf_validate.c b/lib/bpf/bpf_validate.c
index a500ad662c..35b7d4ad83 100644
--- a/lib/bpf/bpf_validate.c
+++ b/lib/bpf/bpf_validate.c
@@ -910,7 +910,7 @@ eval_xor(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, size_t opsz,
 		rd->s.max ^= rs->s.max;
 
 	/* both operands are non-negative */
-	} else if (rd->s.min >= 0 || rs->s.min >= 0) {
+	} 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.min = 0;
 	} else
-- 
2.43.0