Re: 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.