netdev - Re: 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-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 4 Nov 2021 19:14:30 -0700
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Maxim Mikityanskiy <maximmi@...dia.com>
Cc:     Daniel Borkmann <daniel@...earbox.net>,
        Alexei Starovoitov <ast@...nel.org>,
        John Fastabend <john.fastabend@...il.com>,
        "David S. Miller" <davem@...emloft.net>,
        "netdev@...r.kernel.org" <netdev@...r.kernel.org>,
        Tariq Toukan <tariqt@...dia.com>, bpf <bpf@...r.kernel.org>
Subject: Re: 4-year old off-by-two bug in the BPF verifier's boundary checks?

On Tue, Nov 2, 2021 at 8:12 AM Maxim Mikityanskiy <maximmi@...dia.com> wrote:
>
> 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 for the analysis.
It looks correct to me.
Hopefully Daniel will take a look soon.