[PATCH 4.19 00/12] bpf: fix verifier selftests, add CVE-2021-29155 fixes

[Ovidiu Panait <ovidiu.panait@windriver.com>]

This patchset is based on Frank van der Linden's backport of CVE-2021-29155
fixes to 5.4 and 4.14:
https://lore.kernel.org/stable/20210429220839.15667-1-fllinden@amazon.com/
https://lore.kernel.org/stable/20210501043014.33300-1-fllinden@amazon.com/

With this series, all verifier selftests but one (that has already been
failing, see [1] for more details) succeed.

What the series does is:
* Fix verifier selftests by backporting various bpf/selftest upstream commits +
  add two 4.19 specific fixes
* Backport fixes for CVE-2021-29155 from 5.4 stable, including selftest
  changes. Only minor context adjustements were made for 4.19 backport.

The following commits that fix selftests are 4.19 specific:
Ovidiu Panait (2):
   1. bpf: fix up selftests after backports were fixed

      This is the 4.19 equivalent of
      https://lore.kernel.org/stable/20210501043014.33300-3-fllinden@amazon.com/

      Basically a backport of upstream commit 80c9b2fae87b ("bpf: add various
      test cases to selftests") adapted to 4.19 in order to fix the
      selftests that began to fail after CVE-2019-7308 fixes.

  2. selftests/bpf: add selftest part of "bpf: improve verifier branch
     analysis"

     This is a cherry-pick of the selftest parts that have been left out when
     backporting 4f7b3e82589e0 ("bpf: improve verifier branch analysis") to 4.19.

[1] Note:
There is one verifier selftest that still fails:
...
#640/p bpf_get_stack return R0 within range FAIL
Failed to load prog 'Invalid argument'!
0: (bf) r6 = r1
1: (7a) *(u64 *)(r10 -8) = 0
2: (bf) r2 = r10
3: (07) r2 += -8
4: (18) r1 = 0xffff89a8f5503000
6: (85) call bpf_map_lookup_elem#1
7: (15) if r0 == 0x0 goto pc+28
 R0=map_value(id=0,off=0,ks=8,vs=48,imm=0) R6=ctx(id=0,off=0,imm=0) R10=fp0,call_-1
8: (bf) r7 = r0
9: (b7) r9 = 48
10: (bf) r1 = r6
11: (bf) r2 = r7
12: (b7) r3 = 48
13: (b7) r4 = 256
14: (85) call bpf_get_stack#67
 R0=map_value(id=0,off=0,ks=8,vs=48,imm=0) R1_w=ctx(id=0,off=0,imm=0) R2_w=map_value(id=0,off=0,ks=8,vs=48,imm=0) R3_w=inv48 R4_w=inv256 R6=ctx(id=0,off=0,imm=0) R7_w=map_value(id=0,off=0,ks=8,vs=48,imm=0) R9_w=inv48 R10=fp0,call_-1
15: (b7) r1 = 0
16: (bf) r8 = r0
17: (67) r8 <<= 32
18: (c7) r8 s>>= 32
19: (cd) if r1 s< r8 goto pc+16
 R0=inv(id=0,umax_value=48,var_off=(0x0; 0x3f)) R1=inv0 R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=8,vs=48,imm=0) R8=inv0 R9=inv48 R10=fp0,call_-1
20: (1f) r9 -= r8
21: (bf) r2 = r7
22: (0f) r2 += r8
23: (bf) r1 = r9
24: (67) r1 <<= 32
25: (c7) r1 s>>= 32
26: (bf) r3 = r2
27: (0f) r3 += r1
28: (bf) r1 = r7
29: (b7) r5 = 48
30: (0f) r1 += r5
31: (3d) if r3 >= r1 goto pc+4
 R0=inv(id=0,umax_value=48,var_off=(0x0; 0x3f)) R1=map_value(id=0,off=48,ks=8,vs=48,imm=0) R2=map_value(id=0,off=0,ks=8,vs=48,imm=0) R3=map_value(id=0,off=48,ks=8,vs=48,imm=0) R5=inv48 R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=8,vs=48,imm=0) R8=inv0 R9=inv48 R10=fp0,call_-1
32: (bf) r1 = r6
33: (bf) r3 = r9
34: (b7) r4 = 0
35: (85) call bpf_get_stack#67
 R0=inv(id=0,umax_value=48,var_off=(0x0; 0x3f)) R1_w=ctx(id=0,off=0,imm=0) R2=map_value(id=0,off=0,ks=8,vs=48,imm=0) R3_w=inv48 R4_w=inv0 R5=inv48 R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=8,vs=48,imm=0) R8=inv0 R9=inv48 R10=fp0,call_-1
36: (95) exit

from 35 to 36: R0=inv(id=0,umin_value=18446744071562067968,var_off=(0xffffffff80000000; 0x7fffffff)) R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=8,vs=48,imm=0) R8=inv0 R9=inv48 R10=fp0,call_-1
36: (95) exit

from 31 to 36: safe

from 19 to 36: safe

from 14 to 15: R0=inv(id=0,umin_value=18446744071562067968,var_off=(0xffffffff80000000; 0x7fffffff)) R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=8,vs=48,imm=0) R9=inv48 R10=fp0,call_-1
15: (b7) r1 = 0
16: (bf) r8 = r0
17: (67) r8 <<= 32
18: (c7) r8 s>>= 32
19: (cd) if r1 s< r8 goto pc+16
 R0=inv(id=0,umin_value=18446744071562067968,var_off=(0xffffffff80000000; 0x7fffffff)) R1=inv0 R6=ctx(id=0,off=0,imm=0) R7=map_value(id=0,off=0,ks=8,vs=48,imm=0) R8=inv(id=0,umin_value=18446744071562067968,var_off=(0xffffffff80000000; 0x7fffffff)) R9=inv48 R10=fp0,call_-1
20: (1f) r9 -= r8
21: (bf) r2 = r7
22: (0f) r2 += r8
value -2147483648 makes map_value pointer be out of bounds

This failure was introduced after the following 4.19 fix:
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-4.19.y&id=e0b80b7d646646273af0770a2bd4d105719387e3

In 5.4 it was fixed by the following commits, but backporting them to 4.19 is
not enough to fix the failing test:
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-5.4.y&id=37e1cdff90c1bc448edb4d73a18d89e05e36ab55
https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/?h=linux-5.4.y&id=a801a05ca7145fd2b72dad35bd01977014241e55

After bisect, the following upstream commit needs to be present as well in
order for the selftest to pass, but I am not sure if it is suitable for stable
backport:
https://github.com/torvalds/linux/commit/2589726d12a1b12eaaa93c7f1ea64287e383c7a5

Andrey Ignatov (1):
  selftests/bpf: Test narrow loads with off > 0 in test_verifier

Daniel Borkmann (8):
  bpf: Move off_reg into sanitize_ptr_alu
  bpf: Ensure off_reg has no mixed signed bounds for all types
  bpf: Rework ptr_limit into alu_limit and add common error path
  bpf: Improve verifier error messages for users
  bpf: Refactor and streamline bounds check into helper
  bpf: Move sanitize_val_alu out of op switch
  bpf: Tighten speculative pointer arithmetic mask
  bpf: Update selftests to reflect new error states

Ovidiu Panait (2):
  bpf: fix up selftests after backports were fixed
  selftests/bpf: add selftest part of "bpf: improve verifier branch
    analysis"

Piotr Krysiuk (1):
  bpf, selftests: Fix up some test_verifier cases for unprivileged

 kernel/bpf/verifier.c                       | 229 ++++++++++++++------
 tools/testing/selftests/bpf/test_verifier.c | 104 +++++++--
 2 files changed, 241 insertions(+), 92 deletions(-)

-- 
2.17.1