netdev - 4-year old off-by-two bug in the BPF verifier's boundary checks?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:   Tue, 2 Nov 2021 17:12:31 +0200
From:   Maxim Mikityanskiy <maximmi@...dia.com>
To:     Daniel Borkmann <daniel@...earbox.net>,
        Alexei Starovoitov <ast@...nel.org>,
        John Fastabend <john.fastabend@...il.com>
CC:     "David S. Miller" <davem@...emloft.net>,
        "netdev@...r.kernel.org" <netdev@...r.kernel.org>,
        Tariq Toukan <tariqt@...dia.com>
Subject: 4-year old off-by-two bug in the BPF verifier's boundary checks?

Hi guys,

I think I found cases where the BPF verifier mistakenly rejects valid 
BPF programs when doing pkt_end boundary checks, and the selftests for 
these cases test wrong things as well.

Daniel's commit fb2a311a31d3 ("bpf: fix off by one for range markings 
with L{T, E} patterns") [1] attempts to fix an off-by-one bug in 
boundary checks, but I think it shifts the index by 1 in a wrong 
direction, so instead of fixing, the bug becomes off-by-two.

A following commit b37242c773b2 ("bpf: add test cases to bpf selftests 
to cover all access tests") [2] adds unit tests to check the new 
behavior, but the tests look also wrong to me.

Let me analyze these two tests:

{
         "XDP pkt read, pkt_data' > pkt_end, good access",
         .insns = {
         BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, offsetof(struct 
xdp_md, data)),
         BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
                     offsetof(struct xdp_md, data_end)),
         BPF_MOV64_REG(BPF_REG_1, BPF_REG_2),
         BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 8),
         BPF_JMP_REG(BPF_JGT, BPF_REG_1, BPF_REG_3, 1),
         BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8),
         BPF_MOV64_IMM(BPF_REG_0, 0),
         BPF_EXIT_INSN(),
         },
         .result = ACCEPT,
         .prog_type = BPF_PROG_TYPE_XDP,
         .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},

{
         "XDP pkt read, pkt_data' >= pkt_end, bad access 1",
         .insns = {
         BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, offsetof(struct 
xdp_md, data)),
         BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1,
                     offsetof(struct xdp_md, data_end)),
         BPF_MOV64_REG(BPF_REG_1, BPF_REG_2),
         BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 8),
         BPF_JMP_REG(BPF_JGE, BPF_REG_1, BPF_REG_3, 1),
         BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8),
         BPF_MOV64_IMM(BPF_REG_0, 0),
         BPF_EXIT_INSN(),
         },
         .errstr = "R1 offset is outside of the packet",
         .result = REJECT,
         .prog_type = BPF_PROG_TYPE_XDP,
         .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},

The first program looks good both to me and the verifier: if data + 8 > 
data_end, we bail out, otherwise, if data + 8 <= data_end, we read 8 
bytes: [data; data+7].

The second program doesn't pass the verifier, and the test expects it to 
be rejected, but the program itself still looks fine to me: if data + 8 
 >= data_end, we bail out, otherwise, if data + 8 < data_end, we read 8 
bytes: [data; data+7], and this is fine, because data + 7 is for sure < 
data_end. The verifier considers data + 7 to be out of bounds, although 
both data + 7 and data + 8 are still valid offsets, hence the off-by-two 
bug.

Are my considerations valid, or am I stupidly missing anything?

I suggest to fix it like this:

--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8492,7 +8492,7 @@ static void find_good_pkt_pointers(struct 
bpf_verifier_state *vstate,

         new_range = dst_reg->off;
         if (range_right_open)
-               new_range--;
+               new_range++;

         /* Examples for register markings:
          *

I don't think this bug poses any security threat, since the checks are 
stricter than needed, but it's a huge functional issue.

Thanks,
Max

[1]: 
https://patchwork.ozlabs.org/project/netdev/patch/3df9cce096b139eb0efb3b0c7bf9fcc5c5dc6629.1508545543.git.daniel@iogearbox.net/
[2]: 
https://patchwork.ozlabs.org/project/netdev/patch/3bc01f5985324b0e233e86616f4fe171c0d4ca8b.1508545543.git.daniel@iogearbox.net/