[PATCH 19/25] bpf/validate: fix BPF_LSH shift-out-of-bounds UB

[Marat Khalili]

Function `eval_lsh` when validating left shift by 63 invoked macro
`RTE_LEN2MASK(0, int64_t)` which triggered shift-out-of-bounds undefined
behaviour.

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, #0x3, L8
        3:  jgt r2, #0x5, L8
        4:  jslt r2, #0x3, L8
        5:  jsgt r2, #0x5, L8
        6:  lsh r2, #0x3f  ; tested instruction
        7:  mov r0, #0x1
        8:  exit
    Pre-state:
       r2:  3..5
    Post-state:
       r2:  0..UINT64_MAX

With sanitizer the following diagnostic is generated:

    lib/bpf/bpf_validate.c:785:4: runtime error: shift exponent 64 is
    too large for 64-bit type 'long unsigned int'
        #0 0x00000274d5e0 in eval_lsh lib/bpf/bpf_validate.c:785
        #1 0x00000275a2ea in eval_alu lib/bpf/bpf_validate.c:1310
        #2 0x00000276ce3d in evaluate lib/bpf/bpf_validate.c:3284

Add guard for this case, add test.

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

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

diff --git a/app/test/test_bpf_validate.c b/app/test/test_bpf_validate.c
index 646313cdacf2..64047af44e4a 100644
--- a/app/test/test_bpf_validate.c
+++ b/app/test/test_bpf_validate.c
@@ -1536,6 +1536,23 @@ test_alu64_div_mod_overflow(void)
 REGISTER_FAST_TEST(bpf_validate_alu64_div_mod_overflow_autotest, NOHUGE_OK, 
ASAN_OK,
        test_alu64_div_mod_overflow);
 
+/* 64-bit left shift by 63. */
+static int
+test_alu64_lsh_63(void)
+{
+       return verify_instruction((struct verify_instruction_param){
+               .tested_instruction = {
+                       .code = (EBPF_ALU64 | BPF_LSH | BPF_K),
+                       .imm = 63,
+               },
+               .pre.dst = make_signed_domain(3, 5),
+               .post.dst = unknown,
+       });
+}
+
+REGISTER_FAST_TEST(bpf_validate_alu64_lsh_63_autotest, NOHUGE_OK, ASAN_OK,
+       test_alu64_lsh_63);
+
 /* 64-bit multiplication of constant and immediate with overflow. */
 static int
 test_alu64_mul_k_overflow(void)
diff --git a/lib/bpf/bpf_validate.c b/lib/bpf/bpf_validate.c
index 4dbf3a3ef892..2c61e5d96a5f 100644
--- a/lib/bpf/bpf_validate.c
+++ b/lib/bpf/bpf_validate.c
@@ -746,7 +746,8 @@ eval_lsh(struct bpf_reg_val *rd, const struct bpf_reg_val 
*rs, size_t opsz,
 
        /* check that dreg values are and would remain always positive */
        if ((uint64_t)rd->s.min >> (opsz - 1) != 0 || rd->s.max >=
-                       RTE_LEN2MASK(opsz - rs->u.max - 1, int64_t))
+                       (rs->u.max == opsz - 1 ? 0 :
+                                RTE_LEN2MASK(opsz - rs->u.max - 1, int64_t)))
                eval_smax_bound(rd, msk);
        else {
                rd->s.max <<= rs->u.max;
-- 
2.43.0