On Tue, Nov 2, 2021 at 8:12 AM Maxim Mikityanskiy <maximmi@xxxxxxxxxx> 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.
