[PATCH disco 0/3] Fix bfp test_verifier

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH disco 0/3] Fix bfp test_verifier

Thadeu Lima de Souza Cascardo-3
The upstream stable release process allow fixes to the bpf verifier without
requiring that the bpf test_verifier selftest still PASS.

That is very unfortunate to our testing process, as we want to make sure we
don't introduce regressions ourselves.

Instead of blindly accepting any failures, I took the path of looking at the
test changes upstream. Clean cherry picks were not always possible, so, in some
cases, I decided to go failure by failure, and fixing up the test with a change
that was already present upstream.

That will make cherry picks even harder in the future, but that's the cost of
maintaining something upstream doesn't care about.

Alexei Starovoitov (1):
  bpf: improve verifier branch analysis

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

Daniel Borkmann (1):
  bpf: add various test cases to selftests

 tools/testing/selftests/bpf/test_verifier.c | 71 +++++++++++++++++----
 1 file changed, 59 insertions(+), 12 deletions(-)

--
2.20.1


--
kernel-team mailing list
[hidden email]
https://lists.ubuntu.com/mailman/listinfo/kernel-team
Reply | Threaded
Open this post in threaded view
|

[PATCH disco 1/3] selftests/bpf: Test narrow loads with off > 0 in test_verifier

Thadeu Lima de Souza Cascardo-3
From: Andrey Ignatov <[hidden email]>

Test the following narrow loads in test_verifier for context __sk_buff:
* off=1, size=1 - ok;
* off=2, size=1 - ok;
* off=3, size=1 - ok;
* off=0, size=2 - ok;
* off=1, size=2 - fail;
* off=0, size=2 - ok;
* off=3, size=2 - fail.

Signed-off-by: Andrey Ignatov <[hidden email]>
Signed-off-by: Alexei Starovoitov <[hidden email]>
(cherry picked from commit 6c2afb674dbda9b736b8f09c976516e1e788860a)
Signed-off-by: Thadeu Lima de Souza Cascardo <[hidden email]>
---
 tools/testing/selftests/bpf/test_verifier.c | 48 ++++++++++++++++-----
 1 file changed, 38 insertions(+), 10 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 9db5a7378f40..d9adb492c2c8 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -2002,29 +2002,27 @@ static struct bpf_test tests[] = {
  .result = ACCEPT,
  },
  {
- "check skb->hash byte load not permitted 1",
+ "check skb->hash byte load permitted 1",
  .insns = {
  BPF_MOV64_IMM(BPF_REG_0, 0),
  BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_1,
     offsetof(struct __sk_buff, hash) + 1),
  BPF_EXIT_INSN(),
  },
- .errstr = "invalid bpf_context access",
- .result = REJECT,
+ .result = ACCEPT,
  },
  {
- "check skb->hash byte load not permitted 2",
+ "check skb->hash byte load permitted 2",
  .insns = {
  BPF_MOV64_IMM(BPF_REG_0, 0),
  BPF_LDX_MEM(BPF_B, BPF_REG_0, BPF_REG_1,
     offsetof(struct __sk_buff, hash) + 2),
  BPF_EXIT_INSN(),
  },
- .errstr = "invalid bpf_context access",
- .result = REJECT,
+ .result = ACCEPT,
  },
  {
- "check skb->hash byte load not permitted 3",
+ "check skb->hash byte load permitted 3",
  .insns = {
  BPF_MOV64_IMM(BPF_REG_0, 0),
 #if __BYTE_ORDER == __LITTLE_ENDIAN
@@ -2036,8 +2034,7 @@ static struct bpf_test tests[] = {
 #endif
  BPF_EXIT_INSN(),
  },
- .errstr = "invalid bpf_context access",
- .result = REJECT,
+ .result = ACCEPT,
  },
  {
  "check cb access: byte, wrong type",
@@ -2149,7 +2146,7 @@ static struct bpf_test tests[] = {
  .result = ACCEPT,
  },
  {
- "check skb->hash half load not permitted",
+ "check skb->hash half load permitted 2",
  .insns = {
  BPF_MOV64_IMM(BPF_REG_0, 0),
 #if __BYTE_ORDER == __LITTLE_ENDIAN
@@ -2158,6 +2155,37 @@ static struct bpf_test tests[] = {
 #else
  BPF_LDX_MEM(BPF_H, BPF_REG_0, BPF_REG_1,
     offsetof(struct __sk_buff, hash)),
+#endif
+ BPF_EXIT_INSN(),
+ },
+ .result = ACCEPT,
+ },
+ {
+ "check skb->hash half load not permitted, unaligned 1",
+ .insns = {
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+#if __BYTE_ORDER == __LITTLE_ENDIAN
+ BPF_LDX_MEM(BPF_H, BPF_REG_0, BPF_REG_1,
+    offsetof(struct __sk_buff, hash) + 1),
+#else
+ BPF_LDX_MEM(BPF_H, BPF_REG_0, BPF_REG_1,
+    offsetof(struct __sk_buff, hash) + 3),
+#endif
+ BPF_EXIT_INSN(),
+ },
+ .errstr = "invalid bpf_context access",
+ .result = REJECT,
+ },
+ {
+ "check skb->hash half load not permitted, unaligned 3",
+ .insns = {
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+#if __BYTE_ORDER == __LITTLE_ENDIAN
+ BPF_LDX_MEM(BPF_H, BPF_REG_0, BPF_REG_1,
+    offsetof(struct __sk_buff, hash) + 3),
+#else
+ BPF_LDX_MEM(BPF_H, BPF_REG_0, BPF_REG_1,
+    offsetof(struct __sk_buff, hash) + 1),
 #endif
  BPF_EXIT_INSN(),
  },
--
2.20.1


--
kernel-team mailing list
[hidden email]
https://lists.ubuntu.com/mailman/listinfo/kernel-team
Reply | Threaded
Open this post in threaded view
|

[PATCH disco 2/3] bpf: add various test cases to selftests

Thadeu Lima de Souza Cascardo-3
In reply to this post by Thadeu Lima de Souza Cascardo-3
From: Daniel Borkmann <[hidden email]>

Add various map value pointer related test cases to test_verifier
kselftest to reflect recent changes and improve test coverage. The
tests include basic masking functionality, unprivileged behavior
on pointer arithmetic which goes oob, mixed bounds tests, negative
unknown scalar but resulting positive offset for access and helper
range, handling of arithmetic from multiple maps, various masking
scenarios with subsequent map value access and others including two
test cases from Jann Horn for prior fixes.

Signed-off-by: Daniel Borkmann <[hidden email]>
Acked-by: Alexei Starovoitov <[hidden email]>
Signed-off-by: Alexei Starovoitov <[hidden email]>
(backported from 80c9b2fae87bb5c5698940da1a981f14f89518d1)
[cascardo: really picked only the few changes we needed to make test work again]
Signed-off-by: Thadeu Lima de Souza Cascardo <[hidden email]>
---
 tools/testing/selftests/bpf/test_verifier.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index d9adb492c2c8..e6c41217c7fa 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -2476,6 +2476,7 @@ static struct bpf_test tests[] = {
  },
  .result = REJECT,
  .errstr = "invalid stack off=-79992 size=8",
+ .errstr_unpriv = "R1 stack pointer arithmetic goes out of range",
  },
  {
  "PTR_TO_STACK store/load - out of bounds high",
@@ -2872,6 +2873,8 @@ static struct bpf_test tests[] = {
  BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, -8),
  BPF_EXIT_INSN(),
  },
+ .errstr_unpriv = "R1 stack pointer arithmetic goes out of range",
+ .result_unpriv = REJECT,
  .result = ACCEPT,
  },
  {
@@ -7485,6 +7488,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7509,6 +7513,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7535,6 +7540,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R8 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7560,6 +7566,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R8 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7608,6 +7615,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7679,6 +7687,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7730,6 +7739,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7757,6 +7767,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7783,6 +7794,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7812,6 +7824,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R7 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7842,6 +7855,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 4 },
  .errstr = "R0 invalid mem access 'inv'",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -7870,6 +7884,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "unbounded min value",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  .result_unpriv = REJECT,
  },
@@ -7922,6 +7937,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+ .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
  {
@@ -8294,6 +8310,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "pointer offset 1073741822",
+ .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range",
  .result = REJECT
  },
  {
@@ -8315,6 +8332,7 @@ static struct bpf_test tests[] = {
  },
  .fixup_map1 = { 3 },
  .errstr = "pointer offset -1073741822",
+ .errstr_unpriv = "R0 pointer arithmetic of map value goes out of range",
  .result = REJECT
  },
  {
@@ -8486,6 +8504,7 @@ static struct bpf_test tests[] = {
  BPF_EXIT_INSN()
  },
  .errstr = "fp pointer offset 1073741822",
+ .errstr_unpriv = "R1 stack pointer arithmetic goes out of range",
  .result = REJECT
  },
  {
--
2.20.1


--
kernel-team mailing list
[hidden email]
https://lists.ubuntu.com/mailman/listinfo/kernel-team
Reply | Threaded
Open this post in threaded view
|

[PATCH disco 3/3] bpf: improve verifier branch analysis

Thadeu Lima de Souza Cascardo-3
In reply to this post by Thadeu Lima de Souza Cascardo-3
From: Alexei Starovoitov <[hidden email]>

pathological bpf programs may try to force verifier to explode in
the number of branch states:
  20: (d5) if r1 s<= 0x24000028 goto pc+0
  21: (b5) if r0 <= 0xe1fa20 goto pc+2
  22: (d5) if r1 s<= 0x7e goto pc+0
  23: (b5) if r0 <= 0xe880e000 goto pc+0
  24: (c5) if r0 s< 0x2100ecf4 goto pc+0
  25: (d5) if r1 s<= 0xe880e000 goto pc+1
  26: (c5) if r0 s< 0xf4041810 goto pc+0
  27: (d5) if r1 s<= 0x1e007e goto pc+0
  28: (b5) if r0 <= 0xe86be000 goto pc+0
  29: (07) r0 += 16614
  30: (c5) if r0 s< 0x6d0020da goto pc+0
  31: (35) if r0 >= 0x2100ecf4 goto pc+0

Teach verifier to recognize always taken and always not taken branches.
This analysis is already done for == and != comparison.
Expand it to all other branches.

It also helps real bpf programs to be verified faster:
                       before  after
bpf_lb-DLB_L3.o         2003    1940
bpf_lb-DLB_L4.o         3173    3089
bpf_lb-DUNKNOWN.o       1080    1065
bpf_lxc-DDROP_ALL.o     29584   28052
bpf_lxc-DUNKNOWN.o      36916   35487
bpf_netdev.o            11188   10864
bpf_overlay.o           6679    6643
bpf_lcx_jit.o           39555   38437

Reported-by: Anatoly Trosinenko <[hidden email]>
Signed-off-by: Alexei Starovoitov <[hidden email]>
Acked-by: Daniel Borkmann <[hidden email]>
Acked-by: Edward Cree <[hidden email]>
Signed-off-by: Daniel Borkmann <[hidden email]>
(cherry picked from commit 4f7b3e82589e0de723780198ec7983e427144c0a)
[cascardo: really just pick the test parts, as this was already applied,
but without the test parts]
Signed-off-by: Thadeu Lima de Souza Cascardo <[hidden email]>
---
 tools/testing/selftests/bpf/test_verifier.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index e6c41217c7fa..65d3bcb95835 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -7854,7 +7854,7 @@ static struct bpf_test tests[] = {
  BPF_JMP_IMM(BPF_JA, 0, 0, -7),
  },
  .fixup_map1 = { 4 },
- .errstr = "R0 invalid mem access 'inv'",
+ .errstr = "unbounded min value",
  .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds",
  .result = REJECT,
  },
@@ -9831,7 +9831,7 @@ static struct bpf_test tests[] = {
  "check deducing bounds from const, 5",
  .insns = {
  BPF_MOV64_IMM(BPF_REG_0, 0),
- BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 0, 1),
+ BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 1, 1),
  BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_1),
  BPF_EXIT_INSN(),
  },
--
2.20.1


--
kernel-team mailing list
[hidden email]
https://lists.ubuntu.com/mailman/listinfo/kernel-team
Reply | Threaded
Open this post in threaded view
|

APPLIED: [PATCH disco 0/3] Fix bfp test_verifier

Seth Forshee
In reply to this post by Thadeu Lima de Souza Cascardo-3
On Fri, Feb 01, 2019 at 05:42:14PM -0200, Thadeu Lima de Souza Cascardo wrote:

> The upstream stable release process allow fixes to the bpf verifier without
> requiring that the bpf test_verifier selftest still PASS.
>
> That is very unfortunate to our testing process, as we want to make sure we
> don't introduce regressions ourselves.
>
> Instead of blindly accepting any failures, I took the path of looking at the
> test changes upstream. Clean cherry picks were not always possible, so, in some
> cases, I decided to go failure by failure, and fixing up the test with a change
> that was already present upstream.
>
> That will make cherry picks even harder in the future, but that's the cost of
> maintaining something upstream doesn't care about.

Applied, thanks!

--
kernel-team mailing list
[hidden email]
https://lists.ubuntu.com/mailman/listinfo/kernel-team