[PATCH bpf] bpf: Fix the off-by-two error in range markings

[PATCH bpf] bpf: Fix the off-by-two error in range markings

[Maxim Mikityanskiy]

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(-)

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(),
 	},
-- 
2.30.2

Re: [PATCH bpf] bpf: Fix the off-by-two error in range markings

[Daniel Borkmann]

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.

Re: [PATCH bpf] bpf: Fix the off-by-two error in range markings

[Maxim Mikityanskiy]

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

Re: [PATCH bpf] bpf: Fix the off-by-two error in range markings

[patchwork-bot+netdevbpf]

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!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

Re: [PATCH bpf] bpf: Fix the off-by-two error in range markings

[Daniel Borkmann]

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