[PATCH 15/25] bpf/validate: fix BPF_JGT/EBPF_JSGT no-jump max

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

Functions `eval_jgt_jle` and `eval_jsgt_jsle` reduced range maximum for
BPF_JGT and EBPF_JSGT instructions in the no-jump case to the minimum of
src register instead of the maximum, producing more conservative
estimate that could cause false positives.

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, #0x14, L15
        3:  jgt r2, #0x3c, L15
        4:  jslt r2, #0x14, L15
        5:  jsgt r2, #0x3c, L15
        6:  ldxdw r3, [r1 + 8]
        7:  jlt r3, #0x1e, L15
        8:  jgt r3, #0x32, L15
        9:  jslt r3, #0x1e, L15
       10:  jsgt r3, #0x32, L15
       11:  jgt r2, r3, L14  ; tested instruction
       12:  mov r0, #0x1
       13:  exit
       14:  mov r0, #0x2
       15:  exit
    Pre-state:
       r2:  20..60
       r3:  30..50
    Post-state:
       r2:  20..60 INTERSECT 0x14..0x1e (!)

Immediately after the tested instruction on step 12 validator expects r2
to contain values up to 60, for example 55, however for this value jump
condition r2 > r3 on step 11 would be always satisfied since r3 is known
to not exceed 50, and thus execution will always jump to step 14 instead
of continuing to step 12.

Fix range calculation, add tests for cases where range of src register
values is a strict subset of dst. Other cases will be covered in the
subsequent commits.

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 | 90 ++++++++++++++++++++++++++++++++++++
 lib/bpf/bpf_validate.c       |  4 +-
 2 files changed, 92 insertions(+), 2 deletions(-)

diff --git a/app/test/test_bpf_validate.c b/app/test/test_bpf_validate.c
index b4cb5d8cdf8d..359e50aaaf8f 100644
--- a/app/test/test_bpf_validate.c
+++ b/app/test/test_bpf_validate.c
@@ -1485,6 +1485,96 @@ test_jmp64_jslt_x(void)
 REGISTER_FAST_TEST(bpf_validate_jmp64_jslt_x_autotest, NOHUGE_OK, ASAN_OK,
 	test_jmp64_jslt_x);
 
+/* Jump on ordering relationship with narrower range. */
+static int
+test_jmp64_jxx_x_ordering_narrower(void)
+{
+	TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_JMP | BPF_JGT | BPF_X),
+		},
+		.pre.dst = make_signed_domain(20, 60),
+		.pre.src = make_signed_domain(30, 50),
+		.post.dst = make_signed_domain(20, 50),
+		.jump.dst = make_signed_domain(31, 60),
+	}), "(BPF_JMP | BPF_JGT | BPF_X) check");
+
+	TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_JMP | BPF_JGE | BPF_X),
+		},
+		.pre.dst = make_signed_domain(20, 60),
+		.pre.src = make_signed_domain(30, 50),
+		.post.dst = make_signed_domain(20, 49),
+		.jump.dst = make_signed_domain(30, 60),
+	}), "(BPF_JMP | BPF_JGE | BPF_X) check");
+
+	TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_JMP | EBPF_JLT | BPF_X),
+		},
+		.pre.dst = make_signed_domain(20, 60),
+		.pre.src = make_signed_domain(30, 50),
+		.post.dst = make_signed_domain(30, 60),
+		.jump.dst = make_signed_domain(20, 49),
+	}), "(BPF_JMP | EBPF_JLT | BPF_X) check");
+
+	TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_JMP | EBPF_JLE | BPF_X),
+		},
+		.pre.dst = make_signed_domain(20, 60),
+		.pre.src = make_signed_domain(30, 50),
+		.post.dst = make_signed_domain(31, 60),
+		.jump.dst = make_signed_domain(20, 50),
+	}), "(BPF_JMP | EBPF_JLE | BPF_X) check");
+
+	TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_JMP | EBPF_JSGT | BPF_X),
+		},
+		.pre.dst = make_signed_domain(20, 60),
+		.pre.src = make_signed_domain(30, 50),
+		.post.dst = make_signed_domain(20, 50),
+		.jump.dst = make_signed_domain(31, 60),
+	}), "(BPF_JMP | EBPF_JSGT | BPF_X) check");
+
+	TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_JMP | EBPF_JSGE | BPF_X),
+		},
+		.pre.dst = make_signed_domain(20, 60),
+		.pre.src = make_signed_domain(30, 50),
+		.post.dst = make_signed_domain(20, 49),
+		.jump.dst = make_signed_domain(30, 60),
+	}), "(BPF_JMP | EBPF_JSGE | BPF_X) check");
+
+	TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_JMP | EBPF_JSLT | BPF_X),
+		},
+		.pre.dst = make_signed_domain(20, 60),
+		.pre.src = make_signed_domain(30, 50),
+		.post.dst = make_signed_domain(30, 60),
+		.jump.dst = make_signed_domain(20, 49),
+	}), "(BPF_JMP | EBPF_JSLT | BPF_X) check");
+
+	TEST_ASSERT_SUCCESS(verify_instruction((struct verify_instruction_param){
+		.tested_instruction = {
+			.code = (BPF_JMP | EBPF_JSLE | BPF_X),
+		},
+		.pre.dst = make_signed_domain(20, 60),
+		.pre.src = make_signed_domain(30, 50),
+		.post.dst = make_signed_domain(31, 60),
+		.jump.dst = make_signed_domain(20, 50),
+	}), "(BPF_JMP | EBPF_JSLE | BPF_X) check");
+
+	return TEST_SUCCESS;
+}
+
+REGISTER_FAST_TEST(bpf_validate_jmp64_jxx_x_ordering_narrower_autotest, NOHUGE_OK, ASAN_OK,
+	test_jmp64_jxx_x_ordering_narrower);
+
 /* 64-bit load from heap (should be set to unknown). */
 static int
 test_mem_ldx_dw_heap(void)
diff --git a/lib/bpf/bpf_validate.c b/lib/bpf/bpf_validate.c
index a53048801a23..ddc468fa0dce 100644
--- a/lib/bpf/bpf_validate.c
+++ b/lib/bpf/bpf_validate.c
@@ -1521,7 +1521,7 @@ static void
 eval_jgt_jle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
 	struct bpf_reg_val *frd, struct bpf_reg_val *frs)
 {
-	frd->u.max = RTE_MIN(frd->u.max, frs->u.min);
+	frd->u.max = RTE_MIN(frd->u.max, frs->u.max);
 	trd->u.min = RTE_MAX(trd->u.min, trs->u.min + 1);
 }
 
@@ -1537,7 +1537,7 @@ static void
 eval_jsgt_jsle(struct bpf_reg_val *trd, struct bpf_reg_val *trs,
 	struct bpf_reg_val *frd, struct bpf_reg_val *frs)
 {
-	frd->s.max = RTE_MIN(frd->s.max, frs->s.min);
+	frd->s.max = RTE_MIN(frd->s.max, frs->s.max);
 	trd->s.min = RTE_MAX(trd->s.min, trs->s.min + 1);
 }
 
-- 
2.43.0