Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1675644 > unrolled thread
| Started by | Edward Cree <ecree@solarflare.com> |
|---|---|
| First post | 2017-06-27 15:00 +0200 |
| Last post | 2017-06-28 20:30 +0200 |
| Articles | 20 on this page of 24 — 4 participants |
Back to article view | Back to linux.kernel
[PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
[PATCH v3 net-next 06/12] selftests/bpf: change test_verifier expectations Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
[PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
Re: [PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 22:50 +0200
Re: [PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures Jakub Kicinski <jakub.kicinski@netronome.com> - 2017-06-29 05:50 +0200
[PATCH v3 net-next 01/12] selftests/bpf: add test for mixed signed and unsigned bounds checks Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
Re: [PATCH v3 net-next 01/12] selftests/bpf: add test for mixed signed and unsigned bounds checks Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 16:00 +0200
[PATCH v3 net-next 07/12] selftests/bpf: rewrite test_align Edward Cree <ecree@solarflare.com> - 2017-06-27 15:00 +0200
[PATCH v3 net-next 09/12] selftests/bpf: add test for bogus operations on pointers Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
[PATCH v3 net-next 12/12] selftests/bpf: variable offset negative tests Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
[PATCH v3 net-next 08/12] selftests/bpf: add a test to test_align Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
[PATCH v3 net-next 10/12] selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
[PATCH v3 net-next 11/12] selftests/bpf: add tests for subtraction & negative numbers Edward Cree <ecree@solarflare.com> - 2017-06-27 15:10 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 16:00 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-06-28 16:20 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 22:50 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Alexei Starovoitov <alexei.starovoitov@gmail.com> - 2017-06-28 23:40 +0200
Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-06-30 18:50 +0200
[TEST PATCH] bpf/verifier: roll back ptr&const handling, and fix signed bounds Edward Cree <ecree@solarflare.com> - 2017-06-30 19:40 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 17:20 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Edward Cree <ecree@solarflare.com> - 2017-06-28 18:10 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 21:50 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Daniel Borkmann <daniel@iogearbox.net> - 2017-06-28 20:00 +0200
Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking Edward Cree <ecree@solarflare.com> - 2017-06-28 20:30 +0200
Page 1 of 2 [1] 2 Next page →
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:00 +0200 |
| Subject | [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier |
| Message-ID | <tWYg2-C4-5@gated-at.bofh.it> |
This series simplifies alignment tracking, generalises bounds tracking and
fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on
packet pointers, stack pointers, map value pointers and context pointers has
been unified, and bounds on these pointers are only checked when the pointer
is dereferenced.
Operations on pointers which destroy all relation to the original pointer
(such as multiplies and shifts) are disallowed if !env->allow_ptr_leaks,
otherwise they convert the pointer to an unknown scalar and feed it to the
normal scalar arithmetic handling.
Pointer types have been unified with the corresponding adjusted-pointer types
where those existed (e.g. PTR_TO_MAP_VALUE[_ADJ] or FRAME_PTR vs
PTR_TO_STACK); similarly, CONST_IMM and UNKNOWN_VALUE have been unified into
SCALAR_VALUE.
Pointer types (except CONST_PTR_TO_MAP, PTR_TO_MAP_VALUE_OR_NULL and
PTR_TO_PACKET_END, which do not allow arithmetic) have a 'fixed offset' and
a 'variable offset'; the former is used when e.g. adding an immediate or a
known-constant register, as long as it does not overflow. Otherwise the
latter is used, and any operation creating a new variable offset creates a
new 'id' (and, for PTR_TO_PACKET, clears the 'range').
SCALAR_VALUEs use the 'variable offset' fields to track the range of possible
values; the 'fixed offset' should never be set on a scalar.
As of patch 12/12, all tests of tools/testing/selftests/bpf/test_verifier
and tools/testing/selftests/bpf/test_align pass.
v3: added a few more tests; removed RFC tags.
v2: fixed nfp build, made test_align pass again and extended it with a few
new tests (though still need to add more).
Edward Cree (12):
selftests/bpf: add test for mixed signed and unsigned bounds checks
bpf/verifier: rework value tracking
nfp: change bpf verifier hooks to match new verifier data structures
bpf/verifier: track signed and unsigned min/max values
bpf/verifier: more concise register state logs for constant var_off
selftests/bpf: change test_verifier expectations
selftests/bpf: rewrite test_align
selftests/bpf: add a test to test_align
selftests/bpf: add test for bogus operations on pointers
selftests/bpf: don't try to access past MAX_PACKET_OFF in
test_verifier
selftests/bpf: add tests for subtraction & negative numbers
selftests/bpf: variable offset negative tests
drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 24 +-
include/linux/bpf.h | 34 +-
include/linux/bpf_verifier.h | 56 +-
include/linux/tnum.h | 81 +
kernel/bpf/Makefile | 2 +-
kernel/bpf/tnum.c | 180 ++
kernel/bpf/verifier.c | 1943 ++++++++++++---------
tools/testing/selftests/bpf/test_align.c | 462 ++++-
tools/testing/selftests/bpf/test_verifier.c | 293 ++--
9 files changed, 2034 insertions(+), 1041 deletions(-)
create mode 100644 include/linux/tnum.h
create mode 100644 kernel/bpf/tnum.c
[toc] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:00 +0200 |
| Subject | [PATCH v3 net-next 06/12] selftests/bpf: change test_verifier expectations |
| Message-ID | <tWYg3-C4-35@gated-at.bofh.it> |
| In reply to | #1675644 |
Some of the verifier's error messages have changed, and some constructs
that previously couldn't be verified are now accepted.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
tools/testing/selftests/bpf/test_verifier.c | 226 ++++++++++++++--------------
1 file changed, 116 insertions(+), 110 deletions(-)
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index fceed67..210a031 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -421,7 +421,7 @@ static struct bpf_test tests[] = {
BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
- .errstr_unpriv = "R1 pointer arithmetic",
+ .errstr_unpriv = "R1 subtraction from stack pointer",
.result_unpriv = REJECT,
.errstr = "R1 invalid mem access",
.result = REJECT,
@@ -603,8 +603,9 @@ static struct bpf_test tests[] = {
BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_2, -4),
BPF_EXIT_INSN(),
},
- .errstr = "misaligned access",
+ .errstr = "misaligned stack access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"invalid map_fd for function call",
@@ -650,8 +651,9 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map1 = { 3 },
- .errstr = "misaligned access",
+ .errstr = "misaligned value access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"sometimes access memory with incorrect alignment",
@@ -672,6 +674,7 @@ static struct bpf_test tests[] = {
.errstr = "R0 invalid mem access",
.errstr_unpriv = "R0 leaks addr",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"jump test 1",
@@ -1215,8 +1218,9 @@ static struct bpf_test tests[] = {
offsetof(struct __sk_buff, cb[0]) + 1),
BPF_EXIT_INSN(),
},
- .errstr = "misaligned access",
+ .errstr = "misaligned context access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"check __sk_buff->hash, offset 0, half store not permitted",
@@ -1319,8 +1323,9 @@ static struct bpf_test tests[] = {
offsetof(struct __sk_buff, cb[0]) + 2),
BPF_EXIT_INSN(),
},
- .errstr = "misaligned access",
+ .errstr = "misaligned context access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"check cb access: word, unaligned 2",
@@ -1330,8 +1335,9 @@ static struct bpf_test tests[] = {
offsetof(struct __sk_buff, cb[4]) + 1),
BPF_EXIT_INSN(),
},
- .errstr = "misaligned access",
+ .errstr = "misaligned context access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"check cb access: word, unaligned 3",
@@ -1341,8 +1347,9 @@ static struct bpf_test tests[] = {
offsetof(struct __sk_buff, cb[4]) + 2),
BPF_EXIT_INSN(),
},
- .errstr = "misaligned access",
+ .errstr = "misaligned context access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"check cb access: word, unaligned 4",
@@ -1352,8 +1359,9 @@ static struct bpf_test tests[] = {
offsetof(struct __sk_buff, cb[4]) + 3),
BPF_EXIT_INSN(),
},
- .errstr = "misaligned access",
+ .errstr = "misaligned context access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"check cb access: double",
@@ -1379,8 +1387,9 @@ static struct bpf_test tests[] = {
offsetof(struct __sk_buff, cb[1])),
BPF_EXIT_INSN(),
},
- .errstr = "misaligned access",
+ .errstr = "misaligned context access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"check cb access: double, unaligned 2",
@@ -1390,8 +1399,9 @@ static struct bpf_test tests[] = {
offsetof(struct __sk_buff, cb[3])),
BPF_EXIT_INSN(),
},
- .errstr = "misaligned access",
+ .errstr = "misaligned context access",
.result = REJECT,
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"check cb access: double, oob 1",
@@ -1523,7 +1533,8 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "misaligned access off -6 size 8",
+ .errstr = "misaligned stack access off (0x0; 0x0)+-8+2 size 8",
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"PTR_TO_STACK store/load - bad alignment on reg",
@@ -1535,7 +1546,8 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "misaligned access off -2 size 8",
+ .errstr = "misaligned stack access off (0x0; 0x0)+-10+8 size 8",
+ .flags = F_LOAD_WITH_STRICT_ALIGNMENT,
},
{
"PTR_TO_STACK store/load - out of bounds low",
@@ -1579,8 +1591,6 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = ACCEPT,
- .result_unpriv = REJECT,
- .errstr_unpriv = "R1 pointer arithmetic",
},
{
"unpriv: add pointer to pointer",
@@ -1591,7 +1601,7 @@ static struct bpf_test tests[] = {
},
.result = ACCEPT,
.result_unpriv = REJECT,
- .errstr_unpriv = "R1 pointer arithmetic",
+ .errstr_unpriv = "R1 pointer += pointer",
},
{
"unpriv: neg pointer",
@@ -1932,10 +1942,7 @@ static struct bpf_test tests[] = {
BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, -8),
BPF_EXIT_INSN(),
},
- .errstr_unpriv = "pointer arithmetic prohibited",
- .result_unpriv = REJECT,
- .errstr = "R1 invalid mem access",
- .result = REJECT,
+ .result = ACCEPT,
},
{
"unpriv: cmp of stack pointer",
@@ -1999,7 +2006,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "invalid stack type R3",
+ .errstr = "R4 min value is negative",
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
@@ -2016,7 +2023,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "invalid stack type R3",
+ .errstr = "R4 min value is negative",
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
@@ -2218,7 +2225,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "invalid stack type R3 off=-1 access_size=-1",
+ .errstr = "R4 min value is negative",
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
@@ -2235,7 +2242,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "invalid stack type R3 off=-1 access_size=2147483647",
+ .errstr = "R4 unbounded memory access, use 'var &= const' or 'if (var < const)'",
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
@@ -2252,7 +2259,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "invalid stack type R3 off=-512 access_size=2147483647",
+ .errstr = "R4 unbounded memory access, use 'var &= const' or 'if (var < const)'",
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
@@ -2652,7 +2659,7 @@ static struct bpf_test tests[] = {
BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1),
BPF_JMP_A(-6),
},
- .errstr = "misaligned packet access off 2+15+-4 size 4",
+ .errstr = "misaligned packet access off 2+(0x0; 0x0)+15+-4 size 4",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
.flags = F_LOAD_WITH_STRICT_ALIGNMENT,
@@ -2947,7 +2954,7 @@ static struct bpf_test tests[] = {
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
- "helper access to packet: test14, cls helper fail sub",
+ "helper access to packet: test14, cls helper ok sub",
.insns = {
BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_1,
offsetof(struct __sk_buff, data)),
@@ -2967,12 +2974,36 @@ static struct bpf_test tests[] = {
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
+ .result = ACCEPT,
+ .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+ },
+ {
+ "helper access to packet: test15, cls helper fail sub",
+ .insns = {
+ BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_1,
+ offsetof(struct __sk_buff, data)),
+ BPF_LDX_MEM(BPF_W, BPF_REG_7, BPF_REG_1,
+ offsetof(struct __sk_buff, data_end)),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 1),
+ BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 7),
+ BPF_JMP_REG(BPF_JGT, BPF_REG_1, BPF_REG_7, 6),
+ BPF_ALU64_IMM(BPF_SUB, BPF_REG_1, 12),
+ BPF_MOV64_IMM(BPF_REG_2, 4),
+ BPF_MOV64_IMM(BPF_REG_3, 0),
+ BPF_MOV64_IMM(BPF_REG_4, 0),
+ BPF_MOV64_IMM(BPF_REG_5, 0),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+ BPF_FUNC_csum_diff),
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+ BPF_EXIT_INSN(),
+ },
.result = REJECT,
- .errstr = "type=inv expected=fp",
+ .errstr = "invalid access to packet",
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
- "helper access to packet: test15, cls helper fail range 1",
+ "helper access to packet: test16, cls helper fail range 1",
.insns = {
BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_1,
offsetof(struct __sk_buff, data)),
@@ -2997,7 +3028,7 @@ static struct bpf_test tests[] = {
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
- "helper access to packet: test16, cls helper fail range 2",
+ "helper access to packet: test17, cls helper fail range 2",
.insns = {
BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_1,
offsetof(struct __sk_buff, data)),
@@ -3018,11 +3049,11 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "invalid access to packet",
+ .errstr = "R2 min value is negative",
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
- "helper access to packet: test17, cls helper fail range 3",
+ "helper access to packet: test18, cls helper fail range 3",
.insns = {
BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_1,
offsetof(struct __sk_buff, data)),
@@ -3043,11 +3074,11 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.result = REJECT,
- .errstr = "invalid access to packet",
+ .errstr = "R2 min value is negative",
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
- "helper access to packet: test18, cls helper fail range zero",
+ "helper access to packet: test19, cls helper fail range zero",
.insns = {
BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_1,
offsetof(struct __sk_buff, data)),
@@ -3072,7 +3103,7 @@ static struct bpf_test tests[] = {
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
- "helper access to packet: test19, pkt end as input",
+ "helper access to packet: test20, pkt end as input",
.insns = {
BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_1,
offsetof(struct __sk_buff, data)),
@@ -3097,7 +3128,7 @@ static struct bpf_test tests[] = {
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
{
- "helper access to packet: test20, wrong reg",
+ "helper access to packet: test21, wrong reg",
.insns = {
BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_1,
offsetof(struct __sk_buff, data)),
@@ -3157,7 +3188,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 leaks addr",
.result_unpriv = REJECT,
.result = ACCEPT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
@@ -3181,7 +3212,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 leaks addr",
.result_unpriv = REJECT,
.result = ACCEPT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
@@ -3209,7 +3240,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 leaks addr",
.result_unpriv = REJECT,
.result = ACCEPT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
@@ -3250,9 +3281,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
.errstr = "R0 min value is outside of the array range",
- .result_unpriv = REJECT,
.result = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},
@@ -3274,9 +3303,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
- .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
- .result_unpriv = REJECT,
+ .errstr = "R0 unbounded memory access, make sure to bounds check any array access into a map",
.result = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},
@@ -3290,7 +3317,7 @@ static struct bpf_test tests[] = {
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 7),
- BPF_LDX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0),
+ BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
BPF_MOV32_IMM(BPF_REG_2, MAX_ENTRIES),
BPF_JMP_REG(BPF_JSGT, BPF_REG_2, BPF_REG_1, 1),
BPF_MOV32_IMM(BPF_REG_1, 0),
@@ -3301,8 +3328,8 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
- .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+ .errstr_unpriv = "R0 leaks addr",
+ .errstr = "R0 unbounded memory access",
.result_unpriv = REJECT,
.result = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
@@ -3328,7 +3355,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 leaks addr",
.errstr = "invalid access to map value, value_size=48 off=44 size=8",
.result_unpriv = REJECT,
.result = REJECT,
@@ -3358,8 +3385,8 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3, 11 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
- .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+ .errstr_unpriv = "R0 pointer += pointer",
+ .errstr = "R0 invalid mem access 'inv'",
.result_unpriv = REJECT,
.result = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
@@ -3501,34 +3528,6 @@ static struct bpf_test tests[] = {
.prog_type = BPF_PROG_TYPE_SCHED_CLS
},
{
- "multiple registers share map_lookup_elem bad reg type",
- .insns = {
- BPF_MOV64_IMM(BPF_REG_1, 10),
- BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_1, -8),
- BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
- BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
- BPF_LD_MAP_FD(BPF_REG_1, 0),
- BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
- BPF_FUNC_map_lookup_elem),
- BPF_MOV64_REG(BPF_REG_2, BPF_REG_0),
- BPF_MOV64_REG(BPF_REG_3, BPF_REG_0),
- BPF_MOV64_REG(BPF_REG_4, BPF_REG_0),
- BPF_MOV64_REG(BPF_REG_5, BPF_REG_0),
- BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
- BPF_MOV64_IMM(BPF_REG_1, 1),
- BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
- BPF_MOV64_IMM(BPF_REG_1, 2),
- BPF_JMP_IMM(BPF_JEQ, BPF_REG_3, 0, 1),
- BPF_ST_MEM(BPF_DW, BPF_REG_3, 0, 0),
- BPF_MOV64_IMM(BPF_REG_1, 3),
- BPF_EXIT_INSN(),
- },
- .fixup_map1 = { 4 },
- .result = REJECT,
- .errstr = "R3 invalid mem access 'inv'",
- .prog_type = BPF_PROG_TYPE_SCHED_CLS
- },
- {
"invalid map access from else condition",
.insns = {
BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
@@ -3546,9 +3545,9 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr = "R0 unbounded memory access, make sure to bounds check any array access into a map",
+ .errstr = "R0 unbounded memory access",
.result = REJECT,
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 leaks addr",
.result_unpriv = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},
@@ -3860,7 +3859,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr = "invalid access to map value, value_size=48 off=0 size=-8",
+ .errstr = "R2 min value is negative",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
@@ -3972,7 +3971,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr = "invalid access to map value, value_size=48 off=4 size=-8",
+ .errstr = "R2 min value is negative",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
@@ -3994,7 +3993,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr = "R1 min value is outside of the array range",
+ .errstr = "R2 min value is negative",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
@@ -4110,7 +4109,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr = "invalid access to map value, value_size=48 off=4 size=-8",
+ .errstr = "R2 min value is negative",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
@@ -4133,7 +4132,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr = "R1 min value is outside of the array range",
+ .errstr = "R2 min value is negative",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
@@ -4221,13 +4220,13 @@ static struct bpf_test tests[] = {
BPF_MOV64_REG(BPF_REG_1, BPF_REG_0),
BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_0, 0),
BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_3),
- BPF_MOV64_IMM(BPF_REG_2, 0),
+ BPF_MOV64_IMM(BPF_REG_2, 1),
BPF_MOV64_IMM(BPF_REG_3, 0),
BPF_EMIT_CALL(BPF_FUNC_probe_read),
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr = "R1 min value is negative, either use unsigned index or do a if (index >=0) check",
+ .errstr = "R1 unbounded memory access",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
@@ -4347,7 +4346,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 leaks addr",
.result = ACCEPT,
.result_unpriv = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
@@ -4375,7 +4374,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 leaks addr",
.result = ACCEPT,
.result_unpriv = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
@@ -4394,7 +4393,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 bitwise operator &= on pointer",
.errstr = "invalid mem access 'inv'",
.result = REJECT,
.result_unpriv = REJECT,
@@ -4413,7 +4412,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 32-bit pointer arithmetic prohibited",
.errstr = "invalid mem access 'inv'",
.result = REJECT,
.result_unpriv = REJECT,
@@ -4432,7 +4431,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 pointer arithmetic with /= operator",
.errstr = "invalid mem access 'inv'",
.result = REJECT,
.result_unpriv = REJECT,
@@ -4475,10 +4474,8 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 invalid mem access 'inv'",
.errstr = "R0 invalid mem access 'inv'",
.result = REJECT,
- .result_unpriv = REJECT,
},
{
"map element value is preserved across register spilling",
@@ -4500,7 +4497,7 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr_unpriv = "R0 leaks addr",
.result = ACCEPT,
.result_unpriv = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
@@ -4682,7 +4679,8 @@ static struct bpf_test tests[] = {
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
- .errstr = "R2 unbounded memory access",
+ /* because max wasn't checked, signed min is negative */
+ .errstr = "R2 min value is negative, either use unsigned or 'var &= const'",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
@@ -4738,7 +4736,7 @@ static struct bpf_test tests[] = {
BPF_JMP_IMM(BPF_JSGT, BPF_REG_2,
sizeof(struct test_val), 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
- BPF_JMP_REG(BPF_JGE, BPF_REG_4, BPF_REG_2, 2),
+ BPF_JMP_REG(BPF_JSGE, BPF_REG_4, BPF_REG_2, 2),
BPF_MOV64_IMM(BPF_REG_3, 0),
BPF_EMIT_CALL(BPF_FUNC_probe_read),
BPF_MOV64_IMM(BPF_REG_0, 0),
@@ -4764,7 +4762,7 @@ static struct bpf_test tests[] = {
BPF_JMP_IMM(BPF_JSGT, BPF_REG_2,
sizeof(struct test_val) + 1, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
- BPF_JMP_REG(BPF_JGE, BPF_REG_4, BPF_REG_2, 2),
+ BPF_JMP_REG(BPF_JSGE, BPF_REG_4, BPF_REG_2, 2),
BPF_MOV64_IMM(BPF_REG_3, 0),
BPF_EMIT_CALL(BPF_FUNC_probe_read),
BPF_MOV64_IMM(BPF_REG_0, 0),
@@ -4792,7 +4790,7 @@ static struct bpf_test tests[] = {
BPF_JMP_IMM(BPF_JSGT, BPF_REG_2,
sizeof(struct test_val) - 20, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
- BPF_JMP_REG(BPF_JGE, BPF_REG_4, BPF_REG_2, 2),
+ BPF_JMP_REG(BPF_JSGE, BPF_REG_4, BPF_REG_2, 2),
BPF_MOV64_IMM(BPF_REG_3, 0),
BPF_EMIT_CALL(BPF_FUNC_probe_read),
BPF_MOV64_IMM(BPF_REG_0, 0),
@@ -4819,7 +4817,7 @@ static struct bpf_test tests[] = {
BPF_JMP_IMM(BPF_JSGT, BPF_REG_2,
sizeof(struct test_val) - 19, 4),
BPF_MOV64_IMM(BPF_REG_4, 0),
- BPF_JMP_REG(BPF_JGE, BPF_REG_4, BPF_REG_2, 2),
+ BPF_JMP_REG(BPF_JSGE, BPF_REG_4, BPF_REG_2, 2),
BPF_MOV64_IMM(BPF_REG_3, 0),
BPF_EMIT_CALL(BPF_FUNC_probe_read),
BPF_MOV64_IMM(BPF_REG_0, 0),
@@ -4831,6 +4829,20 @@ static struct bpf_test tests[] = {
.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
+ "helper access to variable memory: size = 0 allowed on NULL",
+ .insns = {
+ BPF_MOV64_IMM(BPF_REG_1, 0),
+ BPF_MOV64_IMM(BPF_REG_2, 0),
+ BPF_MOV64_IMM(BPF_REG_3, 0),
+ BPF_MOV64_IMM(BPF_REG_4, 0),
+ BPF_MOV64_IMM(BPF_REG_5, 0),
+ BPF_EMIT_CALL(BPF_FUNC_csum_diff),
+ BPF_EXIT_INSN(),
+ },
+ .result = ACCEPT,
+ .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+ },
+ {
"helper access to variable memory: size > 0 not allowed on NULL",
.insns = {
BPF_MOV64_IMM(BPF_REG_1, 0),
@@ -4844,7 +4856,7 @@ static struct bpf_test tests[] = {
BPF_EMIT_CALL(BPF_FUNC_csum_diff),
BPF_EXIT_INSN(),
},
- .errstr = "R1 type=imm expected=fp",
+ .errstr = "R1 type=inv expected=fp",
.result = REJECT,
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
},
@@ -4929,7 +4941,7 @@ static struct bpf_test tests[] = {
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4),
- BPF_MOV64_IMM(BPF_REG_1, 6),
+ BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0),
BPF_ALU64_IMM(BPF_AND, BPF_REG_1, -4),
BPF_ALU64_IMM(BPF_LSH, BPF_REG_1, 2),
BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
@@ -4938,10 +4950,8 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
- .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+ .errstr = "R0 max value is outside of the array range",
.result = REJECT,
- .result_unpriv = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},
{
@@ -4970,10 +4980,8 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map2 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
- .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+ .errstr = "R0 max value is outside of the array range",
.result = REJECT,
- .result_unpriv = REJECT,
.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},
{
@@ -5020,7 +5028,7 @@ static struct bpf_test tests[] = {
},
.fixup_map_in_map = { 3 },
.errstr = "R1 type=inv expected=map_ptr",
- .errstr_unpriv = "R1 pointer arithmetic prohibited",
+ .errstr_unpriv = "R1 pointer arithmetic on CONST_PTR_TO_MAP prohibited",
.result = REJECT,
},
{
@@ -5300,10 +5308,8 @@ static struct bpf_test tests[] = {
BPF_EXIT_INSN(),
},
.fixup_map1 = { 3 },
- .errstr_unpriv = "R0 pointer arithmetic prohibited",
.errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
.result = REJECT,
- .result_unpriv = REJECT,
},
};
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:00 +0200 |
| Subject | [PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures |
| Message-ID | <tWYg3-C4-43@gated-at.bofh.it> |
| In reply to | #1675644 |
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 24 +++++++++++++----------
kernel/bpf/tnum.c | 1 +
2 files changed, 15 insertions(+), 10 deletions(-)
diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
index d696ba4..5b783a9 100644
--- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
+++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c
@@ -79,28 +79,32 @@ nfp_bpf_check_exit(struct nfp_prog *nfp_prog,
const struct bpf_verifier_env *env)
{
const struct bpf_reg_state *reg0 = &env->cur_state.regs[0];
+ u64 imm;
if (nfp_prog->act == NN_ACT_XDP)
return 0;
- if (reg0->type != CONST_IMM) {
- pr_info("unsupported exit state: %d, imm: %llx\n",
- reg0->type, reg0->imm);
+ if (!(reg0->type == SCALAR_VALUE && tnum_is_const(reg0->var_off))) {
+ char tn_buf[48];
+
+ tnum_strn(tn_buf, sizeof(tn_buf), reg0->var_off);
+ pr_info("unsupported exit state: %d, var_off: %s\n",
+ reg0->type, tn_buf);
return -EINVAL;
}
- if (nfp_prog->act != NN_ACT_DIRECT &&
- reg0->imm != 0 && (reg0->imm & ~0U) != ~0U) {
+ imm = reg0->var_off.value;
+ if (nfp_prog->act != NN_ACT_DIRECT && imm != 0 && (imm & ~0U) != ~0U) {
pr_info("unsupported exit state: %d, imm: %llx\n",
- reg0->type, reg0->imm);
+ reg0->type, imm);
return -EINVAL;
}
- if (nfp_prog->act == NN_ACT_DIRECT && reg0->imm <= TC_ACT_REDIRECT &&
- reg0->imm != TC_ACT_SHOT && reg0->imm != TC_ACT_STOLEN &&
- reg0->imm != TC_ACT_QUEUED) {
+ if (nfp_prog->act == NN_ACT_DIRECT && imm <= TC_ACT_REDIRECT &&
+ imm != TC_ACT_SHOT && imm != TC_ACT_STOLEN &&
+ imm != TC_ACT_QUEUED) {
pr_info("unsupported exit state: %d, imm: %llx\n",
- reg0->type, reg0->imm);
+ reg0->type, imm);
return -EINVAL;
}
diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
index 803bd0d..92eeeb1 100644
--- a/kernel/bpf/tnum.c
+++ b/kernel/bpf/tnum.c
@@ -141,6 +141,7 @@ int tnum_strn(char *str, size_t size, struct tnum a)
{
return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask);
}
+EXPORT_SYMBOL_GPL(tnum_strn);
int tnum_sbin(char *str, size_t size, struct tnum a)
{
[toc] | [prev] | [next] | [standalone]
| From | Daniel Borkmann <daniel@iogearbox.net> |
|---|---|
| Date | 2017-06-28 22:50 +0200 |
| Subject | Re: [PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures |
| Message-ID | <tXs4q-2d9-17@gated-at.bofh.it> |
| In reply to | #1675647 |
On 06/27/2017 02:57 PM, Edward Cree wrote: > Signed-off-by: Edward Cree <ecree@solarflare.com> Acked-by: Daniel Borkmann <daniel@iogearbox.net>
[toc] | [prev] | [next] | [standalone]
| From | Jakub Kicinski <jakub.kicinski@netronome.com> |
|---|---|
| Date | 2017-06-29 05:50 +0200 |
| Subject | Re: [PATCH v3 net-next 03/12] nfp: change bpf verifier hooks to match new verifier data structures |
| Message-ID | <tXyCS-2nE-5@gated-at.bofh.it> |
| In reply to | #1675647 |
On Tue, 27 Jun 2017 13:57:34 +0100, Edward Cree wrote: > Signed-off-by: Edward Cree <ecree@solarflare.com> Acked-by: Jakub Kicinski <jakub.kicinski@netronome.com> Sorry about the delay.
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:00 +0200 |
| Subject | [PATCH v3 net-next 01/12] selftests/bpf: add test for mixed signed and unsigned bounds checks |
| Message-ID | <tWYg4-C4-65@gated-at.bofh.it> |
| In reply to | #1675644 |
Currently fails due to bug in verifier bounds handling.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
tools/testing/selftests/bpf/test_verifier.c | 26 ++++++++++++++++++++++++++
1 file changed, 26 insertions(+)
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index c0af019..fceed67 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -5279,6 +5279,32 @@ static struct bpf_test tests[] = {
.errstr = "invalid bpf_context access",
.prog_type = BPF_PROG_TYPE_LWT_IN,
},
+ {
+ "bounds checks mixing signed and unsigned",
+ .insns = {
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+ BPF_LD_MAP_FD(BPF_REG_1, 0),
+ BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0,
+ BPF_FUNC_map_lookup_elem),
+ BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 7),
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, -16, -8),
+ BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_10, -16),
+ BPF_MOV64_IMM(BPF_REG_2, -1),
+ BPF_JMP_REG(BPF_JGT, BPF_REG_1, BPF_REG_2, 3),
+ BPF_JMP_IMM(BPF_JSGT, BPF_REG_1, 1, 2),
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
+ BPF_ST_MEM(BPF_B, BPF_REG_0, 0, 0),
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+ BPF_EXIT_INSN(),
+ },
+ .fixup_map1 = { 3 },
+ .errstr_unpriv = "R0 pointer arithmetic prohibited",
+ .errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
+ .result = REJECT,
+ .result_unpriv = REJECT,
+ },
};
static int probe_filter_length(const struct bpf_insn *fp)
[toc] | [prev] | [next] | [standalone]
| From | Daniel Borkmann <daniel@iogearbox.net> |
|---|---|
| Date | 2017-06-28 16:00 +0200 |
| Subject | Re: [PATCH v3 net-next 01/12] selftests/bpf: add test for mixed signed and unsigned bounds checks |
| Message-ID | <tXlFF-7uy-25@gated-at.bofh.it> |
| In reply to | #1675656 |
On 06/27/2017 02:56 PM, Edward Cree wrote: > Currently fails due to bug in verifier bounds handling. > > Signed-off-by: Edward Cree <ecree@solarflare.com> Acked-by: Daniel Borkmann <daniel@iogearbox.net>
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:00 +0200 |
| Subject | [PATCH v3 net-next 07/12] selftests/bpf: rewrite test_align |
| Message-ID | <tWYg5-C4-113@gated-at.bofh.it> |
| In reply to | #1675644 |
Expectations have changed, as has the format of the logged state.
To make the tests easier to read, add a line-matching framework so that
each match need only quote the register it cares about. (Multiple
matches may refer to the same line, but matches must be listed in
order of increasing line.)
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
tools/testing/selftests/bpf/test_align.c | 225 ++++++++++++++++++-------------
1 file changed, 132 insertions(+), 93 deletions(-)
diff --git a/tools/testing/selftests/bpf/test_align.c b/tools/testing/selftests/bpf/test_align.c
index bccebd9..031bba8 100644
--- a/tools/testing/selftests/bpf/test_align.c
+++ b/tools/testing/selftests/bpf/test_align.c
@@ -27,6 +27,11 @@
#define MAX_INSNS 512
#define MAX_MATCHES 16
+struct bpf_reg_match {
+ unsigned int line;
+ const char *match;
+};
+
struct bpf_align_test {
const char *descr;
struct bpf_insn insns[MAX_INSNS];
@@ -36,10 +41,14 @@ struct bpf_align_test {
REJECT
} result;
enum bpf_prog_type prog_type;
- const char *matches[MAX_MATCHES];
+ /* Matches must be in order of increasing line */
+ struct bpf_reg_match matches[MAX_MATCHES];
};
static struct bpf_align_test tests[] = {
+ /* Four tests of known constants. These aren't staggeringly
+ * interesting since we track exact values now.
+ */
{
.descr = "mov",
.insns = {
@@ -53,11 +62,13 @@ static struct bpf_align_test tests[] = {
},
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
.matches = {
- "1: R1=ctx R3=imm2,min_value=2,max_value=2,min_align=2 R10=fp",
- "2: R1=ctx R3=imm4,min_value=4,max_value=4,min_align=4 R10=fp",
- "3: R1=ctx R3=imm8,min_value=8,max_value=8,min_align=8 R10=fp",
- "4: R1=ctx R3=imm16,min_value=16,max_value=16,min_align=16 R10=fp",
- "5: R1=ctx R3=imm32,min_value=32,max_value=32,min_align=32 R10=fp",
+ {1, "R1=ctx(id=0,off=0,imm=0)"},
+ {1, "R10=fp0"},
+ {1, "R3=inv2"},
+ {2, "R3=inv4"},
+ {3, "R3=inv8"},
+ {4, "R3=inv16"},
+ {5, "R3=inv32"},
},
},
{
@@ -79,17 +90,19 @@ static struct bpf_align_test tests[] = {
},
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
.matches = {
- "1: R1=ctx R3=imm1,min_value=1,max_value=1,min_align=1 R10=fp",
- "2: R1=ctx R3=imm2,min_value=2,max_value=2,min_align=2 R10=fp",
- "3: R1=ctx R3=imm4,min_value=4,max_value=4,min_align=4 R10=fp",
- "4: R1=ctx R3=imm8,min_value=8,max_value=8,min_align=8 R10=fp",
- "5: R1=ctx R3=imm16,min_value=16,max_value=16,min_align=16 R10=fp",
- "6: R1=ctx R3=imm1,min_value=1,max_value=1,min_align=1 R10=fp",
- "7: R1=ctx R3=imm1,min_value=1,max_value=1,min_align=1 R4=imm32,min_value=32,max_value=32,min_align=32 R10=fp",
- "8: R1=ctx R3=imm1,min_value=1,max_value=1,min_align=1 R4=imm16,min_value=16,max_value=16,min_align=16 R10=fp",
- "9: R1=ctx R3=imm1,min_value=1,max_value=1,min_align=1 R4=imm8,min_value=8,max_value=8,min_align=8 R10=fp",
- "10: R1=ctx R3=imm1,min_value=1,max_value=1,min_align=1 R4=imm4,min_value=4,max_value=4,min_align=4 R10=fp",
- "11: R1=ctx R3=imm1,min_value=1,max_value=1,min_align=1 R4=imm2,min_value=2,max_value=2,min_align=2 R10=fp",
+ {1, "R1=ctx(id=0,off=0,imm=0)"},
+ {1, "R10=fp0"},
+ {1, "R3=inv1"},
+ {2, "R3=inv2"},
+ {3, "R3=inv4"},
+ {4, "R3=inv8"},
+ {5, "R3=inv16"},
+ {6, "R3=inv1"},
+ {7, "R4=inv32"},
+ {8, "R4=inv16"},
+ {9, "R4=inv8"},
+ {10, "R4=inv4"},
+ {11, "R4=inv2"},
},
},
{
@@ -106,12 +119,14 @@ static struct bpf_align_test tests[] = {
},
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
.matches = {
- "1: R1=ctx R3=imm4,min_value=4,max_value=4,min_align=4 R10=fp",
- "2: R1=ctx R3=imm8,min_value=8,max_value=8,min_align=4 R10=fp",
- "3: R1=ctx R3=imm10,min_value=10,max_value=10,min_align=2 R10=fp",
- "4: R1=ctx R3=imm10,min_value=10,max_value=10,min_align=2 R4=imm8,min_value=8,max_value=8,min_align=8 R10=fp",
- "5: R1=ctx R3=imm10,min_value=10,max_value=10,min_align=2 R4=imm12,min_value=12,max_value=12,min_align=4 R10=fp",
- "6: R1=ctx R3=imm10,min_value=10,max_value=10,min_align=2 R4=imm14,min_value=14,max_value=14,min_align=2 R10=fp",
+ {1, "R1=ctx(id=0,off=0,imm=0)"},
+ {1, "R10=fp0"},
+ {1, "R3=inv4"},
+ {2, "R3=inv8"},
+ {3, "R3=inv10"},
+ {4, "R4=inv8"},
+ {5, "R4=inv12"},
+ {6, "R4=inv14"},
},
},
{
@@ -126,13 +141,16 @@ static struct bpf_align_test tests[] = {
},
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
.matches = {
- "1: R1=ctx R3=imm7,min_value=7,max_value=7,min_align=1 R10=fp",
- "2: R1=ctx R3=imm7,min_value=7,max_value=7,min_align=1 R10=fp",
- "3: R1=ctx R3=imm14,min_value=14,max_value=14,min_align=2 R10=fp",
- "4: R1=ctx R3=imm56,min_value=56,max_value=56,min_align=4 R10=fp",
+ {1, "R1=ctx(id=0,off=0,imm=0)"},
+ {1, "R10=fp0"},
+ {1, "R3=inv7"},
+ {2, "R3=inv7"},
+ {3, "R3=inv14"},
+ {4, "R3=inv56"},
},
},
+ /* Tests using unknown values */
#define PREP_PKT_POINTERS \
BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, \
offsetof(struct __sk_buff, data)), \
@@ -166,17 +184,19 @@ static struct bpf_align_test tests[] = {
},
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
.matches = {
- "7: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R10=fp",
- "8: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv55,min_align=2 R10=fp",
- "9: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv54,min_align=4 R10=fp",
- "10: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv53,min_align=8 R10=fp",
- "11: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv52,min_align=16 R10=fp",
- "18: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv56 R10=fp",
- "19: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv51,min_align=32 R10=fp",
- "20: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv52,min_align=16 R10=fp",
- "21: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv53,min_align=8 R10=fp",
- "22: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv54,min_align=4 R10=fp",
- "23: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv55,min_align=2 R10=fp",
+ {7, "R0=pkt(id=0,off=8,r=8,imm=0)"},
+ {7, "R3=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {8, "R3=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
+ {9, "R3=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ {10, "R3=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
+ {11, "R3=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
+ {18, "R3=pkt_end(id=0,off=0,imm=0)"},
+ {18, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {19, "R4=inv(id=0,umax_value=8160,var_off=(0x0; 0x1fe0))"},
+ {20, "R4=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
+ {21, "R4=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
+ {22, "R4=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ {23, "R4=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
},
},
{
@@ -197,16 +217,16 @@ static struct bpf_align_test tests[] = {
},
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
.matches = {
- "7: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R10=fp",
- "8: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv56 R10=fp",
- "9: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv55,min_align=1 R10=fp",
- "10: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv56 R10=fp",
- "11: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv54,min_align=2 R10=fp",
- "12: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv56 R10=fp",
- "13: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv53,min_align=4 R10=fp",
- "14: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv56 R10=fp",
- "15: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv52,min_align=8 R10=fp",
- "16: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=inv56 R4=inv50,min_align=8 R10=fp"
+ {7, "R3=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {8, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {9, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {10, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {11, "R4=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
+ {12, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {13, "R4=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ {14, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {15, "R4=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
+ {16, "R4=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
},
},
{
@@ -237,12 +257,14 @@ static struct bpf_align_test tests[] = {
},
.prog_type = BPF_PROG_TYPE_SCHED_CLS,
.matches = {
- "4: R0=imm0,min_value=0,max_value=0,min_align=2147483648 R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R5=pkt(id=0,off=0,r=0) R10=fp",
- "5: R0=imm0,min_value=0,max_value=0,min_align=2147483648 R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R5=pkt(id=0,off=14,r=0) R10=fp",
- "6: R0=imm0,min_value=0,max_value=0,min_align=2147483648 R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R4=pkt(id=0,off=14,r=0) R5=pkt(id=0,off=14,r=0) R10=fp",
- "10: R0=imm0,min_value=0,max_value=0,min_align=2147483648 R1=ctx R2=pkt(id=0,off=0,r=18) R3=pkt_end R4=inv56 R5=pkt(id=0,off=14,r=18) R10=fp",
- "14: R0=imm0,min_value=0,max_value=0,min_align=2147483648 R1=ctx R2=pkt(id=0,off=0,r=18) R3=pkt_end R4=inv48 R5=pkt(id=0,off=14,r=18) R10=fp",
- "15: R0=imm0,min_value=0,max_value=0,min_align=2147483648 R1=ctx R2=pkt(id=0,off=0,r=18) R3=pkt_end R4=inv48 R5=pkt(id=0,off=14,r=18) R10=fp",
+ {4, "R5=pkt(id=0,off=0,r=0,imm=0)"},
+ {5, "R5=pkt(id=0,off=14,r=0,imm=0)"},
+ {6, "R4=pkt(id=0,off=14,r=0,imm=0)"},
+ {10, "R2=pkt(id=0,off=0,r=18,imm=0)"},
+ {10, "R5=pkt(id=0,off=14,r=18,imm=0)"},
+ {10, "R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
+ {14, "R4=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))"},
+ {15, "R4=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))"},
},
},
{
@@ -297,62 +319,59 @@ static struct bpf_align_test tests[] = {
/* Calculated offset in R6 has unknown value, but known
* alignment of 4.
*/
- "8: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R6=inv54,min_align=4 R10=fp",
-
- /* Offset is added to packet pointer R5, resulting in known
- * auxiliary alignment and offset.
+ {8, "R2=pkt(id=0,off=0,r=8,imm=0)"},
+ {8, "R6=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ /* Offset is added to packet pointer R5, resulting in
+ * known fixed offset, and variable offset from R6.
*/
- "11: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R5=pkt(id=1,off=0,r=0),aux_off=14,aux_off_align=4 R6=inv54,min_align=4 R10=fp",
-
+ {11, "R5=pkt(id=1,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
/* At the time the word size load is performed from R5,
* it's total offset is NET_IP_ALIGN + reg->off (0) +
* reg->aux_off (14) which is 16. Then the variable
* offset is considered using reg->aux_off_align which
* is 4 and meets the load's requirements.
*/
- "15: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=pkt(id=1,off=4,r=4),aux_off=14,aux_off_align=4 R5=pkt(id=1,off=0,r=4),aux_off=14,aux_off_align=4 R6=inv54,min_align=4 R10=fp",
-
-
+ {15, "R4=pkt(id=1,off=18,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ {15, "R5=pkt(id=1,off=14,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
/* Variable offset is added to R5 packet pointer,
* resulting in auxiliary alignment of 4.
*/
- "18: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv,aux_off=14,aux_off_align=4 R5=pkt(id=2,off=0,r=0),aux_off_align=4 R6=inv54,min_align=4 R10=fp",
-
+ {18, "R5=pkt(id=2,off=0,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
/* Constant offset is added to R5, resulting in
* reg->off of 14.
*/
- "19: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv,aux_off=14,aux_off_align=4 R5=pkt(id=2,off=14,r=0),aux_off_align=4 R6=inv54,min_align=4 R10=fp",
-
+ {19, "R5=pkt(id=2,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
/* At the time the word size load is performed from R5,
- * it's total offset is NET_IP_ALIGN + reg->off (14) which
- * is 16. Then the variable offset is considered using
- * reg->aux_off_align which is 4 and meets the load's
- * requirements.
+ * its total fixed offset is NET_IP_ALIGN + reg->off
+ * (14) which is 16. Then the variable offset is 4-byte
+ * aligned, so the total offset is 4-byte aligned and
+ * meets the load's requirements.
*/
- "23: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=pkt(id=2,off=18,r=18),aux_off_align=4 R5=pkt(id=2,off=14,r=18),aux_off_align=4 R6=inv54,min_align=4 R10=fp",
-
+ {23, "R4=pkt(id=2,off=18,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ {23, "R5=pkt(id=2,off=14,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
/* Constant offset is added to R5 packet pointer,
* resulting in reg->off value of 14.
*/
- "26: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv,aux_off_align=4 R5=pkt(id=0,off=14,r=8) R6=inv54,min_align=4 R10=fp",
- /* Variable offset is added to R5, resulting in an
- * auxiliary offset of 14, and an auxiliary alignment of 4.
+ {26, "R5=pkt(id=0,off=14,r=8"},
+ /* Variable offset is added to R5, resulting in a
+ * variable offset of (4n).
*/
- "27: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv,aux_off_align=4 R5=pkt(id=3,off=0,r=0),aux_off=14,aux_off_align=4 R6=inv54,min_align=4 R10=fp",
- /* Constant is added to R5 again, setting reg->off to 4. */
- "28: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv,aux_off_align=4 R5=pkt(id=3,off=4,r=0),aux_off=14,aux_off_align=4 R6=inv54,min_align=4 R10=fp",
- /* And once more we add a variable, which causes an accumulation
- * of reg->off into reg->aux_off_align, with resulting value of
- * 18. The auxiliary alignment stays at 4.
+ {27, "R5=pkt(id=3,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ /* Constant is added to R5 again, setting reg->off to 18. */
+ {28, "R5=pkt(id=3,off=18,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ /* And once more we add a variable; resulting var_off
+ * is still (4n), fixed offset is not changed.
+ * Also, we create a new reg->id.
*/
- "29: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=inv,aux_off_align=4 R5=pkt(id=4,off=0,r=0),aux_off=18,aux_off_align=4 R6=inv54,min_align=4 R10=fp",
+ {29, "R5=pkt(id=4,off=18,r=0,umax_value=2040,var_off=(0x0; 0x7fc))"},
/* At the time the word size load is performed from R5,
- * it's total offset is NET_IP_ALIGN + reg->off (0) +
- * reg->aux_off (18) which is 20. Then the variable offset
- * is considered using reg->aux_off_align which is 4 and meets
- * the load's requirements.
+ * its total fixed offset is NET_IP_ALIGN + reg->off (18)
+ * which is 20. Then the variable offset is (4n), so
+ * the total offset is 4-byte aligned and meets the
+ * load's requirements.
*/
- "33: R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R4=pkt(id=4,off=4,r=4),aux_off=18,aux_off_align=4 R5=pkt(id=4,off=0,r=4),aux_off=18,aux_off_align=4 R6=inv54,min_align=4 R10=fp",
+ {33, "R4=pkt(id=4,off=22,r=22,umax_value=2040,var_off=(0x0; 0x7fc))"},
+ {33, "R5=pkt(id=4,off=18,r=22,umax_value=2040,var_off=(0x0; 0x7fc))"},
},
},
};
@@ -373,6 +392,9 @@ static int do_test_single(struct bpf_align_test *test)
{
struct bpf_insn *prog = test->insns;
int prog_type = test->prog_type;
+ char bpf_vlog_copy[32768];
+ const char *line_ptr;
+ int cur_line = -1;
int prog_len, i;
int fd_prog;
int ret;
@@ -387,14 +409,31 @@ static int do_test_single(struct bpf_align_test *test)
ret = 1;
} else {
ret = 0;
+ /* We make a local copy so that we can strtok() it */
+ strncpy(bpf_vlog_copy, bpf_vlog, sizeof(bpf_vlog_copy));
+ line_ptr = strtok(bpf_vlog_copy, "\n");
for (i = 0; i < MAX_MATCHES; i++) {
- const char *t, *m = test->matches[i];
+ struct bpf_reg_match m = test->matches[i];
- if (!m)
+ if (!m.match)
break;
- t = strstr(bpf_vlog, m);
- if (!t) {
- printf("Failed to find match: %s\n", m);
+ while (line_ptr) {
+ cur_line = -1;
+ sscanf(line_ptr, "%u: ", &cur_line);
+ if (cur_line == m.line)
+ break;
+ line_ptr = strtok(NULL, "\n");
+ }
+ if (!line_ptr) {
+ printf("Failed to find line %u for match: %s\n",
+ m.line, m.match);
+ ret = 1;
+ printf("%s", bpf_vlog);
+ break;
+ }
+ if (!strstr(line_ptr, m.match)) {
+ printf("Failed to find match %u: %s\n",
+ m.line, m.match);
ret = 1;
printf("%s", bpf_vlog);
break;
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:10 +0200 |
| Subject | [PATCH v3 net-next 09/12] selftests/bpf: add test for bogus operations on pointers |
| Message-ID | <tWYpH-WT-9@gated-at.bofh.it> |
| In reply to | #1675644 |
Tests non-add/sub operations (AND, LSH) on pointers decaying them to
unknown scalars.
Also tests that a pkt_ptr add which could potentially overflow is rejected
(find_good_pkt_pointers ignores it and doesn't give us any reg->range).
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
tools/testing/selftests/bpf/test_align.c | 66 +++++++++++++++++++++++++++++++-
1 file changed, 64 insertions(+), 2 deletions(-)
diff --git a/tools/testing/selftests/bpf/test_align.c b/tools/testing/selftests/bpf/test_align.c
index 5165d8e..dfd96c6 100644
--- a/tools/testing/selftests/bpf/test_align.c
+++ b/tools/testing/selftests/bpf/test_align.c
@@ -441,6 +441,62 @@ static struct bpf_align_test tests[] = {
{23, "R5=pkt(id=2,off=0,r=4,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc))"},
},
},
+ {
+ .descr = "dubious pointer arithmetic",
+ .insns = {
+ PREP_PKT_POINTERS,
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+ /* ptr & const => unknown & const */
+ BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
+ BPF_ALU64_IMM(BPF_AND, BPF_REG_5, 0x40),
+ /* ptr << const => unknown << const */
+ BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
+ BPF_ALU64_IMM(BPF_LSH, BPF_REG_5, 2),
+ /* We have a (4n) value. Let's make a packet offset
+ * out of it. First add 14, to make it a (4n+2)
+ */
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
+ /* Then make sure it's nonnegative */
+ BPF_JMP_IMM(BPF_JSGE, BPF_REG_5, 0, 1),
+ BPF_EXIT_INSN(),
+ /* Add it to packet pointer */
+ BPF_MOV64_REG(BPF_REG_6, BPF_REG_2),
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_5),
+ /* Check bounds and perform a read */
+ BPF_MOV64_REG(BPF_REG_4, BPF_REG_6),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
+ BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
+ BPF_EXIT_INSN(),
+ BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_6, 0),
+ BPF_EXIT_INSN(),
+ },
+ .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+ .result = REJECT,
+ .matches = {
+ {4, "R5=pkt(id=0,off=0,r=0,imm=0)"},
+ /* ptr & 0x40 == either 0 or 0x40 */
+ {5, "R5=inv(id=0,umax_value=64,var_off=(0x0; 0x40))"},
+ /* ptr << 2 == unknown, (4n) */
+ {7, "R5=inv(id=0,smax_value=9223372036854775804,umax_value=18446744073709551612,var_off=(0x0; 0xfffffffffffffffc))"},
+ /* (4n) + 14 == (4n+2). We blow our bounds, because
+ * the add could overflow.
+ */
+ {8, "R5=inv(id=0,var_off=(0x2; 0xfffffffffffffffc))"},
+ /* Checked s>=0 */
+ {10, "R5=inv(id=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
+ /* packet pointer + nonnegative (4n+2) */
+ {12, "R6=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
+ {14, "R4=pkt(id=1,off=4,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
+ /* NET_IP_ALIGN + (4n+2) == (4n), alignment is fine.
+ * We checked the bounds, but it might have been able
+ * to overflow if the packet pointer started in the
+ * upper half of the address space.
+ * So we did not get a 'range' on R6, and the access
+ * attempt will fail.
+ */
+ {16, "R6=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
+ }
+ },
};
static int probe_filter_length(const struct bpf_insn *fp)
@@ -470,10 +526,15 @@ static int do_test_single(struct bpf_align_test *test)
fd_prog = bpf_verify_program(prog_type ? : BPF_PROG_TYPE_SOCKET_FILTER,
prog, prog_len, 1, "GPL", 0,
bpf_vlog, sizeof(bpf_vlog));
- if (fd_prog < 0) {
+ if (fd_prog < 0 && test->result != REJECT) {
printf("Failed to load program.\n");
printf("%s", bpf_vlog);
ret = 1;
+ } else if (fd_prog >= 0 && test->result == REJECT) {
+ printf("Unexpected success to load!\n");
+ printf("%s", bpf_vlog);
+ ret = 1;
+ close(fd_prog);
} else {
ret = 0;
/* We make a local copy so that we can strtok() it */
@@ -506,7 +567,8 @@ static int do_test_single(struct bpf_align_test *test)
break;
}
}
- close(fd_prog);
+ if (fd_prog >= 0)
+ close(fd_prog);
}
return ret;
}
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:10 +0200 |
| Subject | [PATCH v3 net-next 12/12] selftests/bpf: variable offset negative tests |
| Message-ID | <tWYpH-WT-7@gated-at.bofh.it> |
| In reply to | #1675644 |
Variable ctx accesses and stack accesses aren't allowed, because we can't
determine what type of value will be read.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
tools/testing/selftests/bpf/test_verifier.c | 41 +++++++++++++++++++++++++++++
1 file changed, 41 insertions(+)
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 7df3c34..471fbee 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -5311,6 +5311,47 @@ static struct bpf_test tests[] = {
.errstr = "R0 min value is negative, either use unsigned index or do a if (index >=0) check.",
.result = REJECT,
},
+ {
+ "variable-offset ctx access",
+ .insns = {
+ /* Get an unknown value */
+ BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
+ /* Make it small and 4-byte aligned */
+ BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 4),
+ /* add it to skb. We now have either &skb->len or
+ * &skb->pkt_type, but we don't know which
+ */
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_2),
+ /* dereference it */
+ BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, 0),
+ BPF_EXIT_INSN(),
+ },
+ .errstr = "variable ctx access var_off=(0x0; 0x4)",
+ .result = REJECT,
+ .prog_type = BPF_PROG_TYPE_LWT_IN,
+ },
+ {
+ "variable-offset stack access",
+ .insns = {
+ /* Fill the top 8 bytes of the stack */
+ BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+ /* Get an unknown value */
+ BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
+ /* Make it small and 4-byte aligned */
+ BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 4),
+ BPF_ALU64_IMM(BPF_SUB, BPF_REG_2, 8),
+ /* add it to fp. We now have either fp-4 or fp-8, but
+ * we don't know which
+ */
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_10),
+ /* dereference it */
+ BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_2, 0),
+ BPF_EXIT_INSN(),
+ },
+ .errstr = "variable stack access var_off=(0xfffffffffffffff8; 0x4)",
+ .result = REJECT,
+ .prog_type = BPF_PROG_TYPE_LWT_IN,
+ },
};
static int probe_filter_length(const struct bpf_insn *fp)
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:10 +0200 |
| Subject | [PATCH v3 net-next 08/12] selftests/bpf: add a test to test_align |
| Message-ID | <tWYpH-WT-13@gated-at.bofh.it> |
| In reply to | #1675644 |
New test adds 14 to the unknown value before adding to the packet pointer,
meaning there's no 'fixed offset' field and instead we add into the
var_off, yielding a '4n+2' value.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
tools/testing/selftests/bpf/test_align.c | 67 ++++++++++++++++++++++++++++++++
1 file changed, 67 insertions(+)
diff --git a/tools/testing/selftests/bpf/test_align.c b/tools/testing/selftests/bpf/test_align.c
index 031bba8..5165d8e 100644
--- a/tools/testing/selftests/bpf/test_align.c
+++ b/tools/testing/selftests/bpf/test_align.c
@@ -374,6 +374,73 @@ static struct bpf_align_test tests[] = {
{33, "R5=pkt(id=4,off=18,r=22,umax_value=2040,var_off=(0x0; 0x7fc))"},
},
},
+ {
+ .descr = "packet variable offset 2",
+ .insns = {
+ /* Create an unknown offset, (4n+2)-aligned */
+ LOAD_UNKNOWN(BPF_REG_6),
+ BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
+ /* Add it to the packet pointer */
+ BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
+ /* Check bounds and perform a read */
+ BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
+ BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
+ BPF_EXIT_INSN(),
+ BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
+ /* Make a (4n) offset from the value we just read */
+ BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0xff),
+ BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
+ /* Add it to the packet pointer */
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
+ /* Check bounds and perform a read */
+ BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
+ BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
+ BPF_EXIT_INSN(),
+ BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+ BPF_EXIT_INSN(),
+ },
+ .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+ .matches = {
+ /* Calculated offset in R6 has unknown value, but known
+ * alignment of 4.
+ */
+ {8, "R2=pkt(id=0,off=0,r=8,imm=0)"},
+ {8, "R6=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ /* Adding 14 makes R6 be (4n+2) */
+ {9, "R6=inv(id=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
+ /* Packet pointer has (4n+2) offset */
+ {11, "R5=pkt(id=1,off=0,r=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
+ {13, "R4=pkt(id=1,off=4,r=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
+ /* At the time the word size load is performed from R5,
+ * its total fixed offset is NET_IP_ALIGN + reg->off (0)
+ * which is 2. Then the variable offset is (4n+2), so
+ * the total offset is 4-byte aligned and meets the
+ * load's requirements.
+ */
+ {15, "R5=pkt(id=1,off=0,r=4,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
+ /* Newly read value in R6 was shifted left by 2, so has
+ * known alignment of 4.
+ */
+ {18, "R6=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ /* Added (4n) to packet pointer's (4n+2) var_off, giving
+ * another (4n+2).
+ */
+ {19, "R5=pkt(id=2,off=0,r=0,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc))"},
+ {21, "R4=pkt(id=2,off=4,r=0,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc))"},
+ /* At the time the word size load is performed from R5,
+ * its total fixed offset is NET_IP_ALIGN + reg->off (0)
+ * which is 2. Then the variable offset is (4n+2), so
+ * the total offset is 4-byte aligned and meets the
+ * load's requirements.
+ */
+ {23, "R5=pkt(id=2,off=0,r=4,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc))"},
+ },
+ },
};
static int probe_filter_length(const struct bpf_insn *fp)
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:10 +0200 |
| Subject | [PATCH v3 net-next 10/12] selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier |
| Message-ID | <tWYpI-WT-25@gated-at.bofh.it> |
| In reply to | #1675644 |
"direct packet access: test2" was potentially reading four bytes from
pkt + 0xffff, which could take it past the verifier's limit, causing
the program to be rejected.
Increase the shifts by one so that R2 is now mask 0x7fff instead of
mask 0xffff.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
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 210a031..7df3c34 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -2330,8 +2330,8 @@ static struct bpf_test tests[] = {
offsetof(struct __sk_buff, data)),
BPF_ALU64_REG(BPF_ADD, BPF_REG_3, BPF_REG_4),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
- BPF_ALU64_IMM(BPF_LSH, BPF_REG_2, 48),
- BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 48),
+ BPF_ALU64_IMM(BPF_LSH, BPF_REG_2, 49),
+ BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 49),
BPF_ALU64_REG(BPF_ADD, BPF_REG_3, BPF_REG_2),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_3),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 8),
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-27 15:10 +0200 |
| Subject | [PATCH v3 net-next 11/12] selftests/bpf: add tests for subtraction & negative numbers |
| Message-ID | <tWYpI-WT-31@gated-at.bofh.it> |
| In reply to | #1675644 |
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
tools/testing/selftests/bpf/test_align.c | 104 +++++++++++++++++++++++++++++++
1 file changed, 104 insertions(+)
diff --git a/tools/testing/selftests/bpf/test_align.c b/tools/testing/selftests/bpf/test_align.c
index dfd96c6..6bc2ceb 100644
--- a/tools/testing/selftests/bpf/test_align.c
+++ b/tools/testing/selftests/bpf/test_align.c
@@ -497,6 +497,110 @@ static struct bpf_align_test tests[] = {
{16, "R6=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
}
},
+ {
+ .descr = "variable subtraction",
+ .insns = {
+ /* Create an unknown offset, (4n+2)-aligned */
+ LOAD_UNKNOWN(BPF_REG_6),
+ BPF_MOV64_REG(BPF_REG_7, BPF_REG_6),
+ BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
+ /* Create another unknown, (4n)-aligned, and subtract
+ * it from the first one
+ */
+ BPF_ALU64_IMM(BPF_LSH, BPF_REG_7, 2),
+ BPF_ALU64_REG(BPF_SUB, BPF_REG_6, BPF_REG_7),
+ /* Bounds-check the result */
+ BPF_JMP_IMM(BPF_JSGE, BPF_REG_6, 0, 1),
+ BPF_EXIT_INSN(),
+ /* Add it to the packet pointer */
+ BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
+ /* Check bounds and perform a read */
+ BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
+ BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
+ BPF_EXIT_INSN(),
+ BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
+ BPF_EXIT_INSN(),
+ },
+ .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+ .matches = {
+ /* Calculated offset in R6 has unknown value, but known
+ * alignment of 4.
+ */
+ {7, "R2=pkt(id=0,off=0,r=8,imm=0)"},
+ {9, "R6=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ /* Adding 14 makes R6 be (4n+2) */
+ {10, "R6=inv(id=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
+ /* New unknown value in R7 is (4n) */
+ {11, "R7=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
+ /* Subtracting it from R6 blows our unsigned bounds */
+ {12, "R6=inv(id=0,smin_value=-1006,smax_value=1034,var_off=(0x2; 0xfffffffffffffffc))"},
+ /* Checked s>= 0 */
+ {14, "R6=inv(id=0,umin_value=2,umax_value=1034,var_off=(0x2; 0x7fc))"},
+ /* At the time the word size load is performed from R5,
+ * its total fixed offset is NET_IP_ALIGN + reg->off (0)
+ * which is 2. Then the variable offset is (4n+2), so
+ * the total offset is 4-byte aligned and meets the
+ * load's requirements.
+ */
+ {20, "R5=pkt(id=1,off=0,r=4,umin_value=2,umax_value=1034,var_off=(0x2; 0x7fc))"},
+ },
+ },
+ {
+ .descr = "pointer variable subtraction",
+ .insns = {
+ /* Create an unknown offset, (4n+2)-aligned and bounded
+ * to [14,74]
+ */
+ LOAD_UNKNOWN(BPF_REG_6),
+ BPF_MOV64_REG(BPF_REG_7, BPF_REG_6),
+ BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0xf),
+ BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
+ /* Subtract it from the packet pointer */
+ BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
+ BPF_ALU64_REG(BPF_SUB, BPF_REG_5, BPF_REG_6),
+ /* Create another unknown, (4n)-aligned and >= 74.
+ * That in fact means >= 76, since 74 % 4 == 2
+ */
+ BPF_ALU64_IMM(BPF_LSH, BPF_REG_7, 2),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_7, 76),
+ /* Add it to the packet pointer */
+ BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_7),
+ /* Check bounds and perform a read */
+ BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
+ BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
+ BPF_EXIT_INSN(),
+ BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
+ BPF_EXIT_INSN(),
+ },
+ .prog_type = BPF_PROG_TYPE_SCHED_CLS,
+ .matches = {
+ /* Calculated offset in R6 has unknown value, but known
+ * alignment of 4.
+ */
+ {7, "R2=pkt(id=0,off=0,r=8,imm=0)"},
+ {10, "R6=inv(id=0,umax_value=60,var_off=(0x0; 0x3c))"},
+ /* Adding 14 makes R6 be (4n+2) */
+ {11, "R6=inv(id=0,umin_value=14,umax_value=74,var_off=(0x2; 0x7c))"},
+ /* Subtracting from packet pointer overflows ubounds */
+ {13, "R5=pkt(id=1,off=0,r=8,umin_value=18446744073709551542,umax_value=18446744073709551602,var_off=(0xffffffffffffff82; 0x7c))"},
+ /* New unknown value in R7 is (4n), >= 76 */
+ {15, "R7=inv(id=0,umin_value=76,umax_value=1096,var_off=(0x0; 0x7fc))"},
+ /* Adding it to packet pointer gives nice bounds again */
+ {16, "R5=pkt(id=2,off=0,r=0,umin_value=2,umax_value=1082,var_off=(0x2; 0x7fc))"},
+ /* At the time the word size load is performed from R5,
+ * its total fixed offset is NET_IP_ALIGN + reg->off (0)
+ * which is 2. Then the variable offset is (4n+2), so
+ * the total offset is 4-byte aligned and meets the
+ * load's requirements.
+ */
+ {20, "R5=pkt(id=2,off=0,r=4,umin_value=2,umax_value=1082,var_off=(0x2; 0x7fc))"},
+ },
+ },
};
static int probe_filter_length(const struct bpf_insn *fp)
[toc] | [prev] | [next] | [standalone]
| From | Daniel Borkmann <daniel@iogearbox.net> |
|---|---|
| Date | 2017-06-28 16:00 +0200 |
| Message-ID | <tXlFF-7uy-33@gated-at.bofh.it> |
| In reply to | #1675644 |
Hi Edward, On 06/27/2017 02:53 PM, Edward Cree wrote: > This series simplifies alignment tracking, generalises bounds tracking and > fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on > packet pointers, stack pointers, map value pointers and context pointers has > been unified, and bounds on these pointers are only checked when the pointer > is dereferenced. > Operations on pointers which destroy all relation to the original pointer > (such as multiplies and shifts) are disallowed if !env->allow_ptr_leaks, > otherwise they convert the pointer to an unknown scalar and feed it to the > normal scalar arithmetic handling. > Pointer types have been unified with the corresponding adjusted-pointer types > where those existed (e.g. PTR_TO_MAP_VALUE[_ADJ] or FRAME_PTR vs > PTR_TO_STACK); similarly, CONST_IMM and UNKNOWN_VALUE have been unified into > SCALAR_VALUE. > Pointer types (except CONST_PTR_TO_MAP, PTR_TO_MAP_VALUE_OR_NULL and > PTR_TO_PACKET_END, which do not allow arithmetic) have a 'fixed offset' and > a 'variable offset'; the former is used when e.g. adding an immediate or a > known-constant register, as long as it does not overflow. Otherwise the > latter is used, and any operation creating a new variable offset creates a > new 'id' (and, for PTR_TO_PACKET, clears the 'range'). > SCALAR_VALUEs use the 'variable offset' fields to track the range of possible > values; the 'fixed offset' should never be set on a scalar. > > As of patch 12/12, all tests of tools/testing/selftests/bpf/test_verifier > and tools/testing/selftests/bpf/test_align pass. > > v3: added a few more tests; removed RFC tags. Did you also have a chance in the meantime to look at reducing complexity along with your unification? I did run the cilium test suite with your latest set from here and current # worst case processed insns that verifier has to go through for cilium progs increases from ~53k we have right now to ~76k. I'm a bit worried that this quickly gets us close to the upper ~98k max limit starting to reject programs again. Alternative is to bump the complexity limit again in near future once run into it, but preferably there's a way to optimize it along with the rewrite? Do you see any possibilities worth exploring? > v2: fixed nfp build, made test_align pass again and extended it with a few > new tests (though still need to add more). > > Edward Cree (12): > selftests/bpf: add test for mixed signed and unsigned bounds checks > bpf/verifier: rework value tracking > nfp: change bpf verifier hooks to match new verifier data structures > bpf/verifier: track signed and unsigned min/max values > bpf/verifier: more concise register state logs for constant var_off > selftests/bpf: change test_verifier expectations > selftests/bpf: rewrite test_align > selftests/bpf: add a test to test_align > selftests/bpf: add test for bogus operations on pointers > selftests/bpf: don't try to access past MAX_PACKET_OFF in > test_verifier > selftests/bpf: add tests for subtraction & negative numbers > selftests/bpf: variable offset negative tests > > drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 24 +- > include/linux/bpf.h | 34 +- > include/linux/bpf_verifier.h | 56 +- > include/linux/tnum.h | 81 + > kernel/bpf/Makefile | 2 +- > kernel/bpf/tnum.c | 180 ++ > kernel/bpf/verifier.c | 1943 ++++++++++++--------- > tools/testing/selftests/bpf/test_align.c | 462 ++++- > tools/testing/selftests/bpf/test_verifier.c | 293 ++-- > 9 files changed, 2034 insertions(+), 1041 deletions(-) > create mode 100644 include/linux/tnum.h > create mode 100644 kernel/bpf/tnum.c > Thanks, Daniel
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-28 16:20 +0200 |
| Message-ID | <tXlYZ-7Qx-1@gated-at.bofh.it> |
| In reply to | #1676686 |
On 28/06/17 14:50, Daniel Borkmann wrote: > Hi Edward, > > Did you also have a chance in the meantime to look at reducing complexity > along with your unification? I did run the cilium test suite with your > latest set from here and current # worst case processed insns that > verifier has to go through for cilium progs increases from ~53k we have > right now to ~76k. I'm a bit worried that this quickly gets us close to > the upper ~98k max limit starting to reject programs again. Alternative > is to bump the complexity limit again in near future once run into it, > but preferably there's a way to optimize it along with the rewrite? Do > you see any possibilities worth exploring? The trouble, I think, is that as we're now tracking more information about each register value, we're less able to prune branches. But often that information is not actually being used in reaching the exit state. So it seems like the way to tackle this would be to track what information is used — or at least, which registers are read from (including e.g. writing through them or passing them to helper calls) — in reaching a safe state. Then only registers which are used are required to match for pruning. But that tracking would presumably have to propagate backwards through the verifier stack, and I'm not sure how easily that could be done. Someone (was it you?) was talking about replacing the current DAG walking and pruning with some kind of basic-block thing, which would help with this. Summary: I think it could be done, but I haven't looked into the details of implementation yet; if it's not actually breaking your programs (yet), maybe leave it for a followup patch series? -Ed
[toc] | [prev] | [next] | [standalone]
| From | Daniel Borkmann <daniel@iogearbox.net> |
|---|---|
| Date | 2017-06-28 22:50 +0200 |
| Message-ID | <tXs4q-2d9-27@gated-at.bofh.it> |
| In reply to | #1676698 |
On 06/28/2017 04:11 PM, Edward Cree wrote: > On 28/06/17 14:50, Daniel Borkmann wrote: >> Hi Edward, >> >> Did you also have a chance in the meantime to look at reducing complexity >> along with your unification? I did run the cilium test suite with your >> latest set from here and current # worst case processed insns that >> verifier has to go through for cilium progs increases from ~53k we have >> right now to ~76k. I'm a bit worried that this quickly gets us close to >> the upper ~98k max limit starting to reject programs again. Alternative >> is to bump the complexity limit again in near future once run into it, >> but preferably there's a way to optimize it along with the rewrite? Do >> you see any possibilities worth exploring? > The trouble, I think, is that as we're now tracking more information about > each register value, we're less able to prune branches. But often that > information is not actually being used in reaching the exit state. So it Agree. > seems like the way to tackle this would be to track what information is > used — or at least, which registers are read from (including e.g. writing > through them or passing them to helper calls) — in reaching a safe state. > Then only registers which are used are required to match for pruning. > But that tracking would presumably have to propagate backwards through the > verifier stack, and I'm not sure how easily that could be done. Someone > (was it you?) was talking about replacing the current DAG walking and > pruning with some kind of basic-block thing, which would help with this. > Summary: I think it could be done, but I haven't looked into the details > of implementation yet; if it's not actually breaking your programs (yet), > maybe leave it for a followup patch series? Could we adapt the limit to 128k perhaps as part of this set given we know that we're tracking more meta data here anyway? Then we could potentially avoid going via -stable later on, biggest pain point is usually tracking differences in LLVM code generation (e.g. differences in optimizations) along with verifier changes to make sure that programs still keep loading on older kernels with e.g. newer LLVM; one of the issues is that pruning can be quite fragile. E.g. worst case adding a simple var in a branch that LLVM assigns a stack slot that was otherwise not used throughout the prog can cause a significant increase of verifier work (run into this multiple times in the past and is a bit of a pain to track down actually). If we could keep some buffer in BPF_COMPLEXITY_LIMIT_INSNS at least when we know that more work is needed anyway from that point onward, that would be good.
[toc] | [prev] | [next] | [standalone]
| From | Alexei Starovoitov <alexei.starovoitov@gmail.com> |
|---|---|
| Date | 2017-06-28 23:40 +0200 |
| Message-ID | <tXsQO-v0-27@gated-at.bofh.it> |
| In reply to | #1677164 |
On Wed, Jun 28, 2017 at 10:38:02PM +0200, Daniel Borkmann wrote: > On 06/28/2017 04:11 PM, Edward Cree wrote: > > On 28/06/17 14:50, Daniel Borkmann wrote: > > > Hi Edward, > > > > > > Did you also have a chance in the meantime to look at reducing complexity > > > along with your unification? I did run the cilium test suite with your > > > latest set from here and current # worst case processed insns that > > > verifier has to go through for cilium progs increases from ~53k we have > > > right now to ~76k. I'm a bit worried that this quickly gets us close to > > > the upper ~98k max limit starting to reject programs again. Alternative > > > is to bump the complexity limit again in near future once run into it, > > > but preferably there's a way to optimize it along with the rewrite? Do > > > you see any possibilities worth exploring? > > The trouble, I think, is that as we're now tracking more information about > > each register value, we're less able to prune branches. But often that > > information is not actually being used in reaching the exit state. So it > > Agree. > > > seems like the way to tackle this would be to track what information is > > used — or at least, which registers are read from (including e.g. writing > > through them or passing them to helper calls) — in reaching a safe state. > > Then only registers which are used are required to match for pruning. > > But that tracking would presumably have to propagate backwards through the > > verifier stack, and I'm not sure how easily that could be done. Someone > > (was it you?) was talking about replacing the current DAG walking and > > pruning with some kind of basic-block thing, which would help with this. > > Summary: I think it could be done, but I haven't looked into the details > > of implementation yet; if it's not actually breaking your programs (yet), > > maybe leave it for a followup patch series? > > Could we adapt the limit to 128k perhaps as part of this set > given we know that we're tracking more meta data here anyway? Increasing the limit is must have, since pruning suffered so much. Going from 53k to 76k is pretty substantial. What is the % increase for tests in selftests/ ? I think we need to pin point exactly the reason. Saying we just track more data is not enough. We've tried v2 set on our load balancer and also saw ~20% increase. I don't remember the absolute numbers. These jumps don't make me comfortable with these extra tracking. Can you try to roll back ptr&const and full negative/positive tracking and see whether it gets back to what we had before? I agree that long term it's better to do proper basic block based liveness, but we need to do understand what's causing the increase today. If tnum is causing it that would be reasonable trade off to make, but if it's full neg/pos tracking that has no use today other than (the whole thing is cleaner) I would rather drop it then. We can always come back to it later once pruning issues are solved.
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-30 18:50 +0200 |
| Message-ID | <tY7hf-7Sv-3@gated-at.bofh.it> |
| In reply to | #1677201 |
On 28/06/17 22:37, Alexei Starovoitov wrote: > Increasing the limit is must have, since pruning suffered so much. > Going from 53k to 76k is pretty substantial. > What is the % increase for tests in selftests/ ? When I tried to measure the test_verifier tests, they changed hardly at all, only a couple of percent iirc. But that's with (a) only the accepted progs get measured, since rejected don't print the #insns line - and most of the tests in test_verifier are rejected; and (b) those test progs are pretty small, usually with only a couple of jumps and not much chance for pruning to occur. So it's really not a great test case for pruning effectiveness. I haven't measured the test_progs ones, because I *still* haven't gotten around to actually setting up a BPF toolchain (it doesn't help that I'm building everything on a test server that gets reimaged every night to run our nightly tests...). > I think we need to pin point exactly the reason. > Saying we just track more data is not enough. > We've tried v2 set on our load balancer and also saw ~20% increase. > I don't remember the absolute numbers. > These jumps don't make me comfortable with these extra tracking. > Can you try to roll back ptr&const and full negative/positive tracking > and see whether it gets back to what we had before? The ptr&const bit shouldn't be relevant unless your programs are actually doing that (i.e. ops on pointers other than +/-), which seems surprising. But if you really are, then it's not too hard to roll it back - just need to change how adjust_reg_min_max_vals() deals with EACCES. For a version without full negative/positive tracking, just take the first 3 patches; some of the selftests will fail but hopefully your progs will still be accepted. If not, we can try jbacik's patch (off-list response to v2). I will followup this email with a patch to apply on top of the first 3 that does that and rolls back ptr&const. > If tnum is causing it that would be reasonable trade off to make, > but if it's full neg/pos tracking that has no use today other than > (the whole thing is cleaner) I would rather drop it then. Well, the full neg/pos tracking was a result of needing to fix the bug I found with patch #1, and not wanting to confuse myself with the min/max range while doing my signed/unsigned tracking. But if we can make it work with jbacik's approach of 'remember whether our current bounds came from a signed or an unsigned compare', then we can drop or delay the full neg/pos tracking unless/until pruning is sorted out. -Ed
[toc] | [prev] | [next] | [standalone]
| From | Edward Cree <ecree@solarflare.com> |
|---|---|
| Date | 2017-06-30 19:40 +0200 |
| Subject | [TEST PATCH] bpf/verifier: roll back ptr&const handling, and fix signed bounds |
| Message-ID | <tY83D-8nx-11@gated-at.bofh.it> |
| In reply to | #1678986 |
I'm far from sure that my adjust_reg_min_max_vals() code remains correct
in the face of maybe-signed-maybe-not bounds, even with the checks I've
added in. So this probably has security leaks in it; but it should
suffice for measuring the effect on pruning.
The treat_as_signed part is loosely based on a patch by Josef Bacik <jbacik@fb.com>.
Build-tested only. Applies on top of patches 1-3.
Signed-off-by: Edward Cree <ecree@solarflare.com>
---
include/linux/bpf_verifier.h | 5 +-
kernel/bpf/verifier.c | 179 ++++++++++++++++++++++++++-----------------
2 files changed, 111 insertions(+), 73 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index ca7e2ce..ad02a9d 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -51,8 +51,9 @@ struct bpf_reg_state {
* These refer to the same value as var_off, not necessarily the actual
* contents of the register.
*/
- s64 min_value; /* minimum possible (s64)value */
- u64 max_value; /* maximum possible (u64)value */
+ bool treat_as_signed; /* Do below limits come from a JSGT/JSGE? */
+ s64 min_value;
+ u64 max_value;
};
enum bpf_stack_slot_type {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 82823f1..b59c09b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -474,6 +474,7 @@ static void __mark_reg_known_zero(struct bpf_reg_state *reg)
reg->var_off = tnum_const(0);
reg->min_value = 0;
reg->max_value = 0;
+ reg->treat_as_signed = false;
}
static void mark_reg_known_zero(struct bpf_reg_state *regs, u32 regno)
@@ -497,6 +498,7 @@ static void __mark_reg_unknown(struct bpf_reg_state *reg)
reg->var_off = tnum_unknown;
reg->min_value = BPF_REGISTER_MIN_RANGE;
reg->max_value = BPF_REGISTER_MAX_RANGE;
+ reg->treat_as_signed = false;
}
static void mark_reg_unknown(struct bpf_reg_state *regs, u32 regno)
@@ -1087,6 +1089,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
state->regs[value_regno].var_off.value |
state->regs[value_regno].var_off.mask,
BPF_REGISTER_MAX_RANGE);
+ state->regs[value_regno].treat_as_signed = false;
}
return err;
}
@@ -1601,6 +1604,9 @@ static void check_reg_overflow(struct bpf_reg_state *reg)
if (reg->min_value < BPF_REGISTER_MIN_RANGE ||
reg->min_value > BPF_REGISTER_MAX_RANGE)
reg->min_value = BPF_REGISTER_MIN_RANGE;
+ /* Unsigned cannot be < 0 */
+ if (!reg->treat_as_signed && reg->min_value < 0)
+ reg->min_value = 0;
}
static void coerce_reg_to_32(struct bpf_reg_state *reg)
@@ -1612,10 +1618,12 @@ static void coerce_reg_to_32(struct bpf_reg_state *reg)
reg->var_off = tnum_cast(reg->var_off, 4);
/* Did value become known? Then update bounds */
if (tnum_is_const(reg->var_off)) {
- if ((s64)reg->var_off.value > BPF_REGISTER_MIN_RANGE)
+ /* We're treating as unsigned, so min is always >= 0 */
+ if (reg->var_off.value < BPF_REGISTER_MAX_RANGE) {
reg->min_value = reg->var_off.value;
- if (reg->var_off.value < BPF_REGISTER_MAX_RANGE)
reg->max_value = reg->var_off.value;
+ }
+ reg->treat_as_signed = false;
}
}
@@ -1637,6 +1645,18 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
u8 opcode = BPF_OP(insn->code);
u32 dst = insn->dst_reg;
+ /* If we can cross the sign boundary, don't trust our bounds.
+ * Normally the program should have given us both upper and lower
+ * bounds (e.g. two signed checks or one unsigned upper bound), in
+ * which case this won't fire.
+ */
+ if (off_reg->treat_as_signed) {
+ if (min_val == BPF_REGISTER_MIN_RANGE)
+ max_val = BPF_REGISTER_MAX_RANGE;
+ } else {
+ if (max_val == BPF_REGISTER_MAX_RANGE)
+ min_val = BPF_REGISTER_MIN_RANGE;
+ }
dst_reg = ®s[dst];
if (WARN_ON_ONCE(known && (min_val != max_val))) {
@@ -1677,6 +1697,11 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
*/
dst_reg->type = ptr_reg->type;
dst_reg->id = ptr_reg->id;
+ /* We also inherit the signedness of our offset.
+ * XXX If we already had an offset of a different signedness, this
+ * might lead to trouble!
+ */
+ dst_reg->treat_as_signed = off_reg->treat_as_signed;
switch (opcode) {
case BPF_ADD:
@@ -1820,6 +1845,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
}
min_val = src_reg->min_value;
max_val = src_reg->max_value;
+ /* If we can cross the sign boundary, don't trust our bounds.
+ * Normally the program should have given us both upper and lower
+ * bounds (e.g. two signed checks or one unsigned upper bound), in
+ * which case this won't fire.
+ */
+ if (src_reg->treat_as_signed) {
+ if (min_val == BPF_REGISTER_MIN_RANGE)
+ max_val = BPF_REGISTER_MAX_RANGE;
+ } else {
+ if (max_val == BPF_REGISTER_MAX_RANGE)
+ min_val = BPF_REGISTER_MIN_RANGE;
+ }
src_known = tnum_is_const(src_reg->var_off);
dst_known = tnum_is_const(dst_reg->var_off);
@@ -2004,10 +2041,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
src_reg, dst_reg);
if (rc == -EACCES && env->allow_ptr_leaks) {
/* scalar += unknown scalar */
- __mark_reg_unknown(&off_reg);
- return adjust_scalar_min_max_vals(
- env, insn,
- dst_reg, &off_reg);
+ __mark_reg_unknown(dst_reg);
}
return rc;
}
@@ -2018,8 +2052,6 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
if (rc == -EACCES && env->allow_ptr_leaks) {
/* unknown scalar += scalar */
__mark_reg_unknown(dst_reg);
- return adjust_scalar_min_max_vals(
- env, insn, dst_reg, src_reg);
}
return rc;
}
@@ -2031,6 +2063,7 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
off_reg.var_off = tnum_const(insn->imm);
off_reg.min_value = insn->imm;
off_reg.max_value = insn->imm;
+ off_reg.treat_as_signed = false;
src_reg = &off_reg;
if (ptr_reg) { /* pointer += K */
rc = adjust_ptr_min_max_vals(env, insn,
@@ -2038,8 +2071,6 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
if (rc == -EACCES && env->allow_ptr_leaks) {
/* unknown scalar += K */
__mark_reg_unknown(dst_reg);
- return adjust_scalar_min_max_vals(
- env, insn, dst_reg, &off_reg);
}
return rc;
}
@@ -2151,6 +2182,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
regs[insn->dst_reg].var_off = tnum_const(insn->imm);
regs[insn->dst_reg].max_value = insn->imm;
regs[insn->dst_reg].min_value = insn->imm;
+ regs[insn->dst_reg].treat_as_signed = false;
regs[insn->dst_reg].id = 0;
}
@@ -2271,12 +2303,15 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
struct bpf_reg_state *false_reg, u64 val,
u8 opcode)
{
+ bool treat_as_signed = true;
+
switch (opcode) {
case BPF_JEQ:
/* If this is false then we know nothing Jon Snow, but if it is
* true then we know for sure.
*/
true_reg->max_value = true_reg->min_value = val;
+ true_reg->treat_as_signed = false;
true_reg->var_off = tnum_const(val);
break;
case BPF_JNE:
@@ -2284,45 +2319,42 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
* we know the value for sure;
*/
false_reg->max_value = false_reg->min_value = val;
+ false_reg->treat_as_signed = false;
false_reg->var_off = tnum_const(val);
break;
case BPF_JGT:
- /* Unsigned comparison, can only tell us about max_value (since
- * min_value is signed), unless we learn sign bit.
- */
- false_reg->max_value = val;
- /* If we're not unsigned-greater-than a positive value, then
- * we can't be negative.
- */
- if ((s64)val >= 0 && false_reg->min_value < 0)
- false_reg->min_value = 0;
- break;
+ /* Unsigned comparison, min_value is 0 */
+ true_reg->min_value = 0;
+ treat_as_signed = false;
case BPF_JSGT:
- /* Signed comparison, can only tell us about min_value (since
- * max_value is unsigned), unless we already know sign bit.
+ /* r > k => true->min = k+1
+ * r <= k => false->max = k
*/
+ false_reg->max_value = val;
true_reg->min_value = val + 1;
- /* If we're not signed-greater than val, and we're not negative,
- * then we can't be unsigned-greater than val either.
- */
- if (false_reg->min_value >= 0)
- false_reg->max_value = val;
+ if (false_reg->treat_as_signed != treat_as_signed)
+ false_reg->min_value = BPF_REGISTER_MIN_RANGE;
+ if (true_reg->treat_as_signed != treat_as_signed)
+ true_reg->max_value = BPF_REGISTER_MAX_RANGE;
+ false_reg->treat_as_signed = treat_as_signed;
+ true_reg->treat_as_signed = treat_as_signed;
break;
case BPF_JGE:
- false_reg->max_value = val - 1;
- /* If we're not unsigned-ge a positive value, then we can't be
- * negative.
- */
- if ((s64)val >= 0 && false_reg->min_value < 0)
- false_reg->min_value = 0;
- break;
+ /* Unsigned comparison, min_value is 0 */
+ true_reg->min_value = 0;
+ treat_as_signed = false;
case BPF_JSGE:
- true_reg->min_value = val;
- /* If we're not signed-ge val, and we're not negative, then we
- * can't be unsigned-ge val either.
+ /* r >= k => true->min = k
+ * r < k => false->max = k-1
*/
- if (false_reg->min_value >= 0)
- false_reg->max_value = val - 1;
+ false_reg->max_value = val - 1;
+ true_reg->min_value = val;
+ if (false_reg->treat_as_signed != treat_as_signed)
+ false_reg->min_value = BPF_REGISTER_MIN_RANGE;
+ if (true_reg->treat_as_signed != treat_as_signed)
+ true_reg->max_value = BPF_REGISTER_MAX_RANGE;
+ false_reg->treat_as_signed = treat_as_signed;
+ true_reg->treat_as_signed = treat_as_signed;
break;
default:
break;
@@ -2339,12 +2371,15 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
struct bpf_reg_state *false_reg, u64 val,
u8 opcode)
{
+ bool treat_as_signed = true;
+
switch (opcode) {
case BPF_JEQ:
/* If this is false then we know nothing Jon Snow, but if it is
* true then we know for sure.
*/
true_reg->max_value = true_reg->min_value = val;
+ true_reg->treat_as_signed = false;
true_reg->var_off = tnum_const(val);
break;
case BPF_JNE:
@@ -2352,45 +2387,42 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
* we know the value for sure;
*/
false_reg->max_value = false_reg->min_value = val;
+ false_reg->treat_as_signed = false;
false_reg->var_off = tnum_const(val);
break;
case BPF_JGT:
- /* Unsigned comparison, can only tell us about max_value (since
- * min_value is signed), unless we learn sign bit.
- */
- true_reg->max_value = val - 1;
- /* If a positive value is unsigned-greater-than us, then we
- * can't be negative.
- */
- if ((s64)val >= 0 && true_reg->min_value < 0)
- true_reg->min_value = 0;
- break;
+ /* Unsigned comparison, min_value is 0 */
+ true_reg->min_value = 0;
+ treat_as_signed = false;
case BPF_JSGT:
- /* Signed comparison, can only tell us about min_value (since
- * max_value is unsigned), unless we already know sign bit.
+ /* k > r => true->max = k-1
+ * k <= r => false->min = k
*/
false_reg->min_value = val;
- /* If val is signed-greater-than us, and we're not negative,
- * then val must be unsigned-greater-than us.
- */
- if (true_reg->min_value >= 0)
- true_reg->max_value = val - 1;
+ true_reg->max_value = val - 1;
+ if (true_reg->treat_as_signed != treat_as_signed)
+ true_reg->min_value = BPF_REGISTER_MIN_RANGE;
+ if (false_reg->treat_as_signed != treat_as_signed)
+ false_reg->max_value = BPF_REGISTER_MAX_RANGE;
+ false_reg->treat_as_signed = treat_as_signed;
+ true_reg->treat_as_signed = treat_as_signed;
break;
case BPF_JGE:
- true_reg->max_value = val;
- /* If a positive value is unsigned-ge us, then we can't be
- * negative.
- */
- if ((s64)val >= 0 && true_reg->min_value < 0)
- true_reg->min_value = 0;
- break;
+ /* Unsigned comparison, min_value is 0 */
+ true_reg->min_value = 0;
+ treat_as_signed = false;
case BPF_JSGE:
- false_reg->min_value = val + 1;
- /* If val is signed-ge us, and we're not negative, then val
- * must be unsigned-ge us.
+ /* k >= r => true->max = k
+ * k < r => false->min = k + 1
*/
- if (true_reg->min_value >= 0)
- true_reg->max_value = val;
+ false_reg->min_value = val + 1;
+ true_reg->max_value = val;
+ if (true_reg->treat_as_signed != treat_as_signed)
+ true_reg->min_value = BPF_REGISTER_MIN_RANGE;
+ if (false_reg->treat_as_signed != treat_as_signed)
+ false_reg->max_value = BPF_REGISTER_MAX_RANGE;
+ false_reg->treat_as_signed = treat_as_signed;
+ true_reg->treat_as_signed = treat_as_signed;
break;
default:
break;
@@ -2404,12 +2436,14 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
static void __reg_combine_min_max(struct bpf_reg_state *src_reg,
struct bpf_reg_state *dst_reg)
{
+ src_reg->var_off = dst_reg->var_off = tnum_intersect(src_reg->var_off,
+ dst_reg->var_off);
+ if (src_reg->treat_as_signed != dst_reg->treat_as_signed)
+ return;
src_reg->min_value = dst_reg->min_value = max(src_reg->min_value,
dst_reg->min_value);
src_reg->max_value = dst_reg->max_value = min(src_reg->max_value,
dst_reg->max_value);
- src_reg->var_off = dst_reg->var_off = tnum_intersect(src_reg->var_off,
- dst_reg->var_off);
check_reg_overflow(src_reg);
check_reg_overflow(dst_reg);
}
@@ -2443,6 +2477,7 @@ static void mark_map_reg(struct bpf_reg_state *regs, u32 regno, u32 id,
reg->var_off.value || reg->var_off.mask ||
reg->off)) {
reg->min_value = reg->max_value = reg->off = 0;
+ reg->treat_as_signed = false;
reg->var_off = tnum_const(0);
}
if (is_null) {
@@ -2637,6 +2672,7 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
regs[insn->dst_reg].type = SCALAR_VALUE;
regs[insn->dst_reg].min_value = imm;
regs[insn->dst_reg].max_value = imm;
+ regs[insn->dst_reg].treat_as_signed = false;
check_reg_overflow(®s[insn->dst_reg]);
regs[insn->dst_reg].var_off = tnum_const(imm);
regs[insn->dst_reg].id = 0;
@@ -2927,7 +2963,8 @@ static int check_cfg(struct bpf_verifier_env *env)
static bool range_within(struct bpf_reg_state *old,
struct bpf_reg_state *cur)
{
- return old->min_value <= cur->min_value &&
+ return old->treat_as_signed == cur->treat_as_signed &&
+ old->min_value <= cur->min_value &&
old->max_value >= cur->max_value;
}
[toc] | [prev] | [next] | [standalone]
| From | Daniel Borkmann <daniel@iogearbox.net> |
|---|---|
| Date | 2017-06-28 17:20 +0200 |
| Subject | Re: [PATCH v3 net-next 02/12] bpf/verifier: rework value tracking |
| Message-ID | <tXmV6-8uj-67@gated-at.bofh.it> |
| In reply to | #1675644 |
On 06/27/2017 02:56 PM, Edward Cree wrote:
> Tracks value alignment by means of tracking known & unknown bits.
> Tightens some min/max value checks and fixes a couple of bugs therein.
You mean the one in relation to patch 1/12? Would be good to elaborate
here since otherwise this gets forgotten few weeks later.
Could you also document all the changes that verifier will then start
allowing for after the patch?
> If pointer leaks are allowed, and adjust_ptr_min_max_vals returns -EACCES,
> treat the pointer as an unknown scalar and try again, because we might be
> able to conclude something about the result (e.g. pointer & 0x40 is either
> 0 or 0x40).
>
> Signed-off-by: Edward Cree <ecree@solarflare.com>
[...]
> /* check whether memory at (regno + off) is accessible for t = (read | write)
> @@ -899,52 +965,79 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> struct bpf_reg_state *reg = &state->regs[regno];
> int size, err = 0;
>
> - if (reg->type == PTR_TO_STACK)
> - off += reg->imm;
> -
> size = bpf_size_to_bytes(bpf_size);
> if (size < 0)
> return size;
>
[...]
> - if (reg->type == PTR_TO_MAP_VALUE ||
> - reg->type == PTR_TO_MAP_VALUE_ADJ) {
> + /* for access checks, reg->off is just part of off */
> + off += reg->off;
Could you elaborate on why removing the reg->type == PTR_TO_STACK?
Also in context of below PTR_TO_CTX.
[...]
> } else if (reg->type == PTR_TO_CTX) {
> - enum bpf_reg_type reg_type = UNKNOWN_VALUE;
> + enum bpf_reg_type reg_type = SCALAR_VALUE;
>
> if (t == BPF_WRITE && value_regno >= 0 &&
> is_pointer_value(env, value_regno)) {
> verbose("R%d leaks addr into ctx\n", value_regno);
> return -EACCES;
> }
> + /* ctx accesses must be at a fixed offset, so that we can
> + * determine what type of data were returned.
> + */
> + if (!tnum_is_const(reg->var_off)) {
> + char tn_buf[48];
> +
> + tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
> + verbose("variable ctx access var_off=%s off=%d size=%d",
> + tn_buf, off, size);
> + return -EACCES;
> + }
> + off += reg->var_off.value;
... f.e. in PTR_TO_CTX case the only access that is currently
allowed is LDX/STX with fixed offset from insn->off, which is
passed as off param to check_mem_access(). Can you elaborate on
off += reg->var_off.value? Meaning we make this more dynamic
as long as access is known const?
> err = check_ctx_access(env, insn_idx, off, size, t, ®_type);
> if (!err && t == BPF_READ && value_regno >= 0) {
> - mark_reg_unknown_value_and_range(state->regs,
> - value_regno);
> - /* note that reg.[id|off|range] == 0 */
> + /* ctx access returns either a scalar, or a
> + * PTR_TO_PACKET[_END]. In the latter case, we know
> + * the offset is zero.
> + */
> + if (reg_type == SCALAR_VALUE)
> + mark_reg_unknown(state->regs, value_regno);
> + else
> + mark_reg_known_zero(state->regs, value_regno);
> + state->regs[value_regno].id = 0;
> + state->regs[value_regno].off = 0;
> + state->regs[value_regno].range = 0;
> state->regs[value_regno].type = reg_type;
> - state->regs[value_regno].aux_off = 0;
> - state->regs[value_regno].aux_off_align = 0;
> }
>
> - } else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
> + } else if (reg->type == PTR_TO_STACK) {
[...]
[toc] | [prev] | [next] | [standalone]
Page 1 of 2 [1] 2 Next page →
Back to top | Article view | linux.kernel
csiph-web