| Message ID | 20211130181607.593149-1-maximmi@nvidia.com (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | 2fa7d94afc1afbb4d702760c058dc2d7ed30f226 |
| Delegated to: | BPF |
| Headers | show |
| Series | [bpf] bpf: Fix the off-by-two error in range markings | expand |
On 11/30/21 7:16 PM, Maxim Mikityanskiy wrote: > The first commit cited below attempts to fix the off-by-one error that > appeared in some comparisons with an open range. Due to this error, > arithmetically equivalent pieces of code could get different verdicts > from the verifier, for example (pseudocode): > > // 1. Passes the verifier: > if (data + 8 > data_end) > return early > read *(u64 *)data, i.e. [data; data+7] > > // 2. Rejected by the verifier (should still pass): > if (data + 7 >= data_end) > return early > read *(u64 *)data, i.e. [data; data+7] > > The attempted fix, however, shifts the range by one in a wrong > direction, so the bug not only remains, but also such piece of code > starts failing in the verifier: > > // 3. Rejected by the verifier, but the check is stricter than in #1. > if (data + 8 >= data_end) > return early > read *(u64 *)data, i.e. [data; data+7] > > The change performed by that fix converted an off-by-one bug into > off-by-two. The second commit cited below added the BPF selftests > written to ensure than code chunks like #3 are rejected, however, > they should be accepted. > > This commit fixes the off-by-two error by adjusting new_range in the > right direction and fixes the tests by changing the range into the one > that should actually fail. > > Fixes: fb2a311a31d3 ("bpf: fix off by one for range markings with L{T, E} patterns") > Fixes: b37242c773b2 ("bpf: add test cases to bpf selftests to cover all access tests") > Signed-off-by: Maxim Mikityanskiy <maximmi@nvidia.com> > --- > After this patch is merged, I'm going to submit another patch to > bpf-next, that will add new selftests for this bug. Thanks for the fix, pls post the selftests for bpf tree; it's okay to route them via bpf so they can go via CI for both trees eventually.
On 2021-11-30 23:40, Daniel Borkmann wrote: > On 11/30/21 7:16 PM, Maxim Mikityanskiy wrote: >> The first commit cited below attempts to fix the off-by-one error that >> appeared in some comparisons with an open range. Due to this error, >> arithmetically equivalent pieces of code could get different verdicts >> from the verifier, for example (pseudocode): >> >> // 1. Passes the verifier: >> if (data + 8 > data_end) >> return early >> read *(u64 *)data, i.e. [data; data+7] >> >> // 2. Rejected by the verifier (should still pass): >> if (data + 7 >= data_end) >> return early >> read *(u64 *)data, i.e. [data; data+7] >> >> The attempted fix, however, shifts the range by one in a wrong >> direction, so the bug not only remains, but also such piece of code >> starts failing in the verifier: >> >> // 3. Rejected by the verifier, but the check is stricter than in #1. >> if (data + 8 >= data_end) >> return early >> read *(u64 *)data, i.e. [data; data+7] >> >> The change performed by that fix converted an off-by-one bug into >> off-by-two. The second commit cited below added the BPF selftests >> written to ensure than code chunks like #3 are rejected, however, >> they should be accepted. >> >> This commit fixes the off-by-two error by adjusting new_range in the >> right direction and fixes the tests by changing the range into the one >> that should actually fail. >> >> Fixes: fb2a311a31d3 ("bpf: fix off by one for range markings with L{T, >> E} patterns") >> Fixes: b37242c773b2 ("bpf: add test cases to bpf selftests to cover >> all access tests") >> Signed-off-by: Maxim Mikityanskiy <maximmi@nvidia.com> >> --- >> After this patch is merged, I'm going to submit another patch to >> bpf-next, that will add new selftests for this bug. > > Thanks for the fix, pls post the selftests for bpf tree; it's okay to route > them via bpf so they can go via CI for both trees eventually. OK, one question though: if I want to cite the commit hash of this patch in that patch, shall I want till this one is merged and get the commit hash from the bpf tree or should I resubmit them together and just say "previous commit"? Also, I see in patchwork that bpf/vmtest-bpf failed: is it related to my patch or is it something known? Thanks, Max
Hello: This patch was applied to bpf/bpf.git (master) by Daniel Borkmann <daniel@iogearbox.net>: On Tue, 30 Nov 2021 20:16:07 +0200 you wrote: > The first commit cited below attempts to fix the off-by-one error that > appeared in some comparisons with an open range. Due to this error, > arithmetically equivalent pieces of code could get different verdicts > from the verifier, for example (pseudocode): > > // 1. Passes the verifier: > if (data + 8 > data_end) > return early > read *(u64 *)data, i.e. [data; data+7] > > [...] Here is the summary with links: - [bpf] bpf: Fix the off-by-two error in range markings https://git.kernel.org/bpf/bpf/c/2fa7d94afc1a You are awesome, thank you!
On 12/1/21 12:31 PM, Maxim Mikityanskiy wrote: > On 2021-11-30 23:40, Daniel Borkmann wrote: >> On 11/30/21 7:16 PM, Maxim Mikityanskiy wrote: >>> The first commit cited below attempts to fix the off-by-one error that >>> appeared in some comparisons with an open range. Due to this error, >>> arithmetically equivalent pieces of code could get different verdicts >>> from the verifier, for example (pseudocode): >>> >>> // 1. Passes the verifier: >>> if (data + 8 > data_end) >>> return early >>> read *(u64 *)data, i.e. [data; data+7] >>> >>> // 2. Rejected by the verifier (should still pass): >>> if (data + 7 >= data_end) >>> return early >>> read *(u64 *)data, i.e. [data; data+7] >>> >>> The attempted fix, however, shifts the range by one in a wrong >>> direction, so the bug not only remains, but also such piece of code >>> starts failing in the verifier: >>> >>> // 3. Rejected by the verifier, but the check is stricter than in #1. >>> if (data + 8 >= data_end) >>> return early >>> read *(u64 *)data, i.e. [data; data+7] >>> >>> The change performed by that fix converted an off-by-one bug into >>> off-by-two. The second commit cited below added the BPF selftests >>> written to ensure than code chunks like #3 are rejected, however, >>> they should be accepted. >>> >>> This commit fixes the off-by-two error by adjusting new_range in the >>> right direction and fixes the tests by changing the range into the one >>> that should actually fail. >>> >>> Fixes: fb2a311a31d3 ("bpf: fix off by one for range markings with L{T, E} patterns") >>> Fixes: b37242c773b2 ("bpf: add test cases to bpf selftests to cover all access tests") >>> Signed-off-by: Maxim Mikityanskiy <maximmi@nvidia.com> >>> --- >>> After this patch is merged, I'm going to submit another patch to >>> bpf-next, that will add new selftests for this bug. >> >> Thanks for the fix, pls post the selftests for bpf tree; it's okay to route >> them via bpf so they can go via CI for both trees eventually. > > OK, one question though: if I want to cite the commit hash of this patch in that patch, shall I want till this one is merged and get the commit hash from the bpf tree or should I resubmit them together and just say "previous commit"? I don't think you strictly need the commit hash, but took this one into bpf right now since it looks good anyway. Please submit your follow-up selftest patch against bpf tree as well then. > Also, I see in patchwork that bpf/vmtest-bpf failed: is it related to my patch or is it something known? Unrelated bpftool issue: bpftool: FAIL (returned 1) test_progs: PASS test_progs-no_alu32: PASS test_maps: PASS test_verifier: PASS Error: Process completed with exit code 1. Thanks, Daniel
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 50efda51515b..f3001937bbb9 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -8422,7 +8422,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: * diff --git a/tools/testing/selftests/bpf/verifier/xdp_direct_packet_access.c b/tools/testing/selftests/bpf/verifier/xdp_direct_packet_access.c index bfb97383e6b5..de172a5b8754 100644 --- a/tools/testing/selftests/bpf/verifier/xdp_direct_packet_access.c +++ b/tools/testing/selftests/bpf/verifier/xdp_direct_packet_access.c @@ -112,10 +112,10 @@ 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_ALU64_IMM(BPF_ADD, BPF_REG_1, 6), BPF_JMP_REG(BPF_JGT, BPF_REG_3, BPF_REG_1, 1), BPF_JMP_IMM(BPF_JA, 0, 0, 1), - BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8), + BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -6), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -167,10 +167,10 @@ 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_ALU64_IMM(BPF_ADD, BPF_REG_1, 6), BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_3, 1), BPF_JMP_IMM(BPF_JA, 0, 0, 1), - BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8), + BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -6), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -274,9 +274,9 @@ 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_ALU64_IMM(BPF_ADD, BPF_REG_1, 6), 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_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -6), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -437,9 +437,9 @@ 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_ALU64_IMM(BPF_ADD, BPF_REG_1, 6), BPF_JMP_REG(BPF_JLE, BPF_REG_3, BPF_REG_1, 1), - BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8), + BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -6), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -544,10 +544,10 @@ offsetof(struct xdp_md, data_meta)), BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct xdp_md, data)), BPF_MOV64_REG(BPF_REG_1, BPF_REG_2), - BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 8), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 6), BPF_JMP_REG(BPF_JGT, BPF_REG_3, BPF_REG_1, 1), BPF_JMP_IMM(BPF_JA, 0, 0, 1), - BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8), + BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -6), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -599,10 +599,10 @@ offsetof(struct xdp_md, data_meta)), BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct xdp_md, data)), BPF_MOV64_REG(BPF_REG_1, BPF_REG_2), - BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 8), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 6), BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_3, 1), BPF_JMP_IMM(BPF_JA, 0, 0, 1), - BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8), + BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -6), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -706,9 +706,9 @@ offsetof(struct xdp_md, data_meta)), BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct xdp_md, data)), BPF_MOV64_REG(BPF_REG_1, BPF_REG_2), - BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 8), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 6), 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_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -6), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, @@ -869,9 +869,9 @@ offsetof(struct xdp_md, data_meta)), BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct xdp_md, data)), BPF_MOV64_REG(BPF_REG_1, BPF_REG_2), - BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 8), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 6), BPF_JMP_REG(BPF_JLE, BPF_REG_3, BPF_REG_1, 1), - BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8), + BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -6), BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), },
The first commit cited below attempts to fix the off-by-one error that appeared in some comparisons with an open range. Due to this error, arithmetically equivalent pieces of code could get different verdicts from the verifier, for example (pseudocode): // 1. Passes the verifier: if (data + 8 > data_end) return early read *(u64 *)data, i.e. [data; data+7] // 2. Rejected by the verifier (should still pass): if (data + 7 >= data_end) return early read *(u64 *)data, i.e. [data; data+7] The attempted fix, however, shifts the range by one in a wrong direction, so the bug not only remains, but also such piece of code starts failing in the verifier: // 3. Rejected by the verifier, but the check is stricter than in #1. if (data + 8 >= data_end) return early read *(u64 *)data, i.e. [data; data+7] The change performed by that fix converted an off-by-one bug into off-by-two. The second commit cited below added the BPF selftests written to ensure than code chunks like #3 are rejected, however, they should be accepted. This commit fixes the off-by-two error by adjusting new_range in the right direction and fixes the tests by changing the range into the one that should actually fail. Fixes: fb2a311a31d3 ("bpf: fix off by one for range markings with L{T, E} patterns") Fixes: b37242c773b2 ("bpf: add test cases to bpf selftests to cover all access tests") Signed-off-by: Maxim Mikityanskiy <maximmi@nvidia.com> --- After this patch is merged, I'm going to submit another patch to bpf-next, that will add new selftests for this bug. kernel/bpf/verifier.c | 2 +- .../bpf/verifier/xdp_direct_packet_access.c | 32 +++++++++---------- 2 files changed, 17 insertions(+), 17 deletions(-)