[PATCH 21/25] bpf/validate: fix BPF_SUB signed max zero case

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

Function `eval_sub` used source register signed minimum to detect
overflow of the difference (operation result) signed minimum, and source
register signed maximum to detect overflow of the difference signed
maximum. However in the actual formula for difference source register
bounds are swapped (correctly, since we subtract it), so in overflow
detection we should also have swapped them. It caused false negatives in
certain cases.

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, L7
        3:  ldxdw r3, [r1 + 8]
        4:  jsgt r3, #0x0, L7
        5:  sub r2, r3  ; tested instruction
        6:  mov r0, #0x1
        7:  exit
    Pre-state:
       r2:  INT64_MIN..0
       r3:  INT64_MIN..0
    Post-state:
       r2:  INT64_MIN

Validator ignores overflow of signed minimum and considers result to
always equal INT64_MIN. However, if -1 was loaded on step 1 and -2 was
loaded on step 3 it is possible for the difference to equal 1.

Swap source register signed minimum and maximum in the overflow
condition to match the new range formula, 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 9d3e48b5f93c..44e08062b3ee 100644
--- a/app/test/test_bpf_validate.c
+++ b/app/test/test_bpf_validate.c
@@ -1747,6 +1747,23 @@ test_alu64_or_k_positive(void)
 REGISTER_FAST_TEST(bpf_validate_alu64_or_k_positive_autotest, NOHUGE_OK, ASAN_OK,
 	test_alu64_or_k_positive);
 
+/* 64-bit difference between two negative ranges.. */
+static int
+test_alu64_sub_x_src_signed_max_zero(void)
+{
+	return verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (EBPF_ALU64 | BPF_SUB | BPF_X),
+		},
+		.pre.dst = make_signed_domain(INT64_MIN, 0),
+		.pre.src = make_signed_domain(INT64_MIN, 0),
+		.post.dst = unknown,
+	});
+}
+
+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);
+
 /* 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 d9ee0563c9d3..a500ad662c1b 100644
--- a/lib/bpf/bpf_validate.c
+++ b/lib/bpf/bpf_validate.c
@@ -716,9 +716,9 @@ eval_sub(struct bpf_reg_val *rd, const struct bpf_reg_val *rs, uint64_t msk)
 		eval_umax_bound(&rv, msk);
 
 	if ((rd->s.min != rd->s.max || rs->s.min != rs->s.max) &&
-			(((rs->s.min < 0 && rv.s.min < rd->s.min) ||
+			(((rs->s.max < 0 && rv.s.min < rd->s.min) ||
 			rv.s.min > rd->s.min) ||
-			((rs->s.max < 0 && rv.s.max < rd->s.max) ||
+			((rs->s.min < 0 && rv.s.max < rd->s.max) ||
 			rv.s.max > rd->s.max)))
 		eval_smax_bound(&rv, msk);
 
-- 
2.43.0