diff options
author | Daniel Borkmann <daniel@iogearbox.net> | 2019-06-19 02:22:53 +0200 |
---|---|---|
committer | Daniel Borkmann <daniel@iogearbox.net> | 2019-06-19 02:22:53 +0200 |
commit | 94079b64255fe40b9b53fd2e4081f68b9b14f54a (patch) | |
tree | 2901e802c5161bb29dc5882fa14043f46de96cd0 /tools/testing/selftests/bpf/verifier | |
parent | libbpf: constify getter APIs (diff) | |
parent | bpf: precise scalar_value tracking (diff) | |
download | linux-dev-94079b64255fe40b9b53fd2e4081f68b9b14f54a.tar.xz linux-dev-94079b64255fe40b9b53fd2e4081f68b9b14f54a.zip |
Merge branch 'bpf-bounded-loops'
Alexei Starovoitov says:
====================
v2->v3: fixed issues in backtracking pointed out by Andrii.
The next step is to add a lot more tests for backtracking.
v1->v2: addressed Andrii's feedback.
this patch set introduces verifier support for bounded loops and
adds several other improvements.
Ideally they would be introduced one at a time,
but to support bounded loop the verifier needs to 'step back'
in the patch 1. That patch introduces tracking of spill/fill
of constants through the stack. Though it's a useful feature
it hurts cilium tests.
Patch 3 introduces another feature by extending is_branch_taken
logic to 'if rX op rY' conditions. This feature is also
necessary to support bounded loops.
Then patch 4 adds support for the loops while adding
key heuristics with jmp_processed.
Introduction of parentage chain of verifier states in patch 4
allows patch 9 to add backtracking of precise scalar registers
which finally resolves degradation from patch 1.
The end result is much faster verifier for existing programs
and new support for loops.
See patch 8 for many kinds of loops that are now validated.
Patch 9 is the most tricky one and could be rewritten with
a different algorithm in the future.
====================
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Diffstat (limited to 'tools/testing/selftests/bpf/verifier')
-rw-r--r-- | tools/testing/selftests/bpf/verifier/calls.c | 22 | ||||
-rw-r--r-- | tools/testing/selftests/bpf/verifier/cfg.c | 11 | ||||
-rw-r--r-- | tools/testing/selftests/bpf/verifier/direct_packet_access.c | 3 | ||||
-rw-r--r-- | tools/testing/selftests/bpf/verifier/helper_access_var_len.c | 28 | ||||
-rw-r--r-- | tools/testing/selftests/bpf/verifier/loops1.c | 161 |
5 files changed, 198 insertions, 27 deletions
diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c index 9093a8f64dc6..2d752c4f8d9d 100644 --- a/tools/testing/selftests/bpf/verifier/calls.c +++ b/tools/testing/selftests/bpf/verifier/calls.c @@ -215,9 +215,11 @@ BPF_MOV64_IMM(BPF_REG_0, 3), BPF_JMP_IMM(BPF_JA, 0, 0, -6), }, - .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "back-edge from insn", - .result = REJECT, + .prog_type = BPF_PROG_TYPE_SOCKET_FILTER, + .errstr_unpriv = "back-edge from insn", + .result_unpriv = REJECT, + .result = ACCEPT, + .retval = 1, }, { "calls: conditional call 4", @@ -250,22 +252,24 @@ BPF_MOV64_IMM(BPF_REG_0, 3), BPF_EXIT_INSN(), }, - .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "back-edge from insn", - .result = REJECT, + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .result = ACCEPT, + .retval = 1, }, { "calls: conditional call 6", .insns = { + BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 2), - BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, -2), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, -3), BPF_EXIT_INSN(), BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, offsetof(struct __sk_buff, mark)), BPF_EXIT_INSN(), }, - .prog_type = BPF_PROG_TYPE_TRACEPOINT, - .errstr = "back-edge from insn", + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .errstr = "infinite loop detected", .result = REJECT, }, { diff --git a/tools/testing/selftests/bpf/verifier/cfg.c b/tools/testing/selftests/bpf/verifier/cfg.c index 349c0862fb4c..4eb76ed739ce 100644 --- a/tools/testing/selftests/bpf/verifier/cfg.c +++ b/tools/testing/selftests/bpf/verifier/cfg.c @@ -41,7 +41,8 @@ BPF_JMP_IMM(BPF_JA, 0, 0, -1), BPF_EXIT_INSN(), }, - .errstr = "back-edge", + .errstr = "unreachable insn 1", + .errstr_unpriv = "back-edge", .result = REJECT, }, { @@ -53,18 +54,20 @@ BPF_JMP_IMM(BPF_JA, 0, 0, -4), BPF_EXIT_INSN(), }, - .errstr = "back-edge", + .errstr = "unreachable insn 4", + .errstr_unpriv = "back-edge", .result = REJECT, }, { "conditional loop", .insns = { - BPF_MOV64_REG(BPF_REG_1, BPF_REG_0), + BPF_MOV64_REG(BPF_REG_0, BPF_REG_1), BPF_MOV64_REG(BPF_REG_2, BPF_REG_0), BPF_MOV64_REG(BPF_REG_3, BPF_REG_0), BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, -3), BPF_EXIT_INSN(), }, - .errstr = "back-edge", + .errstr = "infinite loop detected", + .errstr_unpriv = "back-edge", .result = REJECT, }, diff --git a/tools/testing/selftests/bpf/verifier/direct_packet_access.c b/tools/testing/selftests/bpf/verifier/direct_packet_access.c index d5c596fdc4b9..2c5fbe7bcd27 100644 --- a/tools/testing/selftests/bpf/verifier/direct_packet_access.c +++ b/tools/testing/selftests/bpf/verifier/direct_packet_access.c @@ -511,7 +511,8 @@ offsetof(struct __sk_buff, data)), BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct __sk_buff, data_end)), - BPF_MOV64_IMM(BPF_REG_0, 0xffffffff), + BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, + offsetof(struct __sk_buff, mark)), BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -8), BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_10, -8), BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 0xffff), diff --git a/tools/testing/selftests/bpf/verifier/helper_access_var_len.c b/tools/testing/selftests/bpf/verifier/helper_access_var_len.c index 1f39d845c64f..67ab12410050 100644 --- a/tools/testing/selftests/bpf/verifier/helper_access_var_len.c +++ b/tools/testing/selftests/bpf/verifier/helper_access_var_len.c @@ -29,9 +29,9 @@ { "helper access to variable memory: stack, bitwise AND, zero included", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -64), - BPF_MOV64_IMM(BPF_REG_2, 16), BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128), BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 64), @@ -46,9 +46,9 @@ { "helper access to variable memory: stack, bitwise AND + JMP, wrong max", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -64), - BPF_MOV64_IMM(BPF_REG_2, 16), BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128), BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 65), @@ -122,9 +122,9 @@ { "helper access to variable memory: stack, JMP, bounds + offset", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -64), - BPF_MOV64_IMM(BPF_REG_2, 16), BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128), BPF_JMP_IMM(BPF_JGT, BPF_REG_2, 64, 5), @@ -143,9 +143,9 @@ { "helper access to variable memory: stack, JMP, wrong max", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -64), - BPF_MOV64_IMM(BPF_REG_2, 16), BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128), BPF_JMP_IMM(BPF_JGT, BPF_REG_2, 65, 4), @@ -163,9 +163,9 @@ { "helper access to variable memory: stack, JMP, no max check", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -64), - BPF_MOV64_IMM(BPF_REG_2, 16), BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128), BPF_MOV64_IMM(BPF_REG_4, 0), @@ -183,9 +183,9 @@ { "helper access to variable memory: stack, JMP, no min check", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -64), - BPF_MOV64_IMM(BPF_REG_2, 16), BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128), BPF_JMP_IMM(BPF_JGT, BPF_REG_2, 64, 3), @@ -201,9 +201,9 @@ { "helper access to variable memory: stack, JMP (signed), no min check", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -64), - BPF_MOV64_IMM(BPF_REG_2, 16), BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128), BPF_JMP_IMM(BPF_JSGT, BPF_REG_2, 64, 3), @@ -244,6 +244,7 @@ { "helper access to variable memory: map, JMP, wrong max", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), @@ -251,7 +252,7 @@ BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 10), BPF_MOV64_REG(BPF_REG_1, BPF_REG_0), - BPF_MOV64_IMM(BPF_REG_2, sizeof(struct test_val)), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_6), BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_10, -128), BPF_JMP_IMM(BPF_JSGT, BPF_REG_2, sizeof(struct test_val) + 1, 4), @@ -262,7 +263,7 @@ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, - .fixup_map_hash_48b = { 3 }, + .fixup_map_hash_48b = { 4 }, .errstr = "invalid access to map value, value_size=48 off=0 size=49", .result = REJECT, .prog_type = BPF_PROG_TYPE_TRACEPOINT, @@ -296,6 +297,7 @@ { "helper access to variable memory: map adjusted, JMP, wrong max", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), @@ -304,7 +306,7 @@ BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 11), BPF_MOV64_REG(BPF_REG_1, BPF_REG_0), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 20), - BPF_MOV64_IMM(BPF_REG_2, sizeof(struct test_val)), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_6), BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_10, -128), BPF_JMP_IMM(BPF_JSGT, BPF_REG_2, sizeof(struct test_val) - 19, 4), @@ -315,7 +317,7 @@ BPF_MOV64_IMM(BPF_REG_0, 0), BPF_EXIT_INSN(), }, - .fixup_map_hash_48b = { 3 }, + .fixup_map_hash_48b = { 4 }, .errstr = "R1 min value is outside of the array range", .result = REJECT, .prog_type = BPF_PROG_TYPE_TRACEPOINT, @@ -337,8 +339,8 @@ { "helper access to variable memory: size > 0 not allowed on NULL (ARG_PTR_TO_MEM_OR_NULL)", .insns = { + BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0), BPF_MOV64_IMM(BPF_REG_1, 0), - BPF_MOV64_IMM(BPF_REG_2, 1), BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_10, -128), BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 64), @@ -562,6 +564,7 @@ { "helper access to variable memory: 8 bytes leak", .insns = { + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, 8), BPF_MOV64_REG(BPF_REG_1, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -64), BPF_MOV64_IMM(BPF_REG_0, 0), @@ -572,7 +575,6 @@ BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -24), BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -16), BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -8), - BPF_MOV64_IMM(BPF_REG_2, 1), BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_2, -128), BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_10, -128), BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 63), diff --git a/tools/testing/selftests/bpf/verifier/loops1.c b/tools/testing/selftests/bpf/verifier/loops1.c new file mode 100644 index 000000000000..5e980a5ab69d --- /dev/null +++ b/tools/testing/selftests/bpf/verifier/loops1.c @@ -0,0 +1,161 @@ +{ + "bounded loop, count to 4", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .retval = 4, +}, +{ + "bounded loop, count to 20", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 3), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 20, -2), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, +}, +{ + "bounded loop, count from positive unknown to 4", + .insns = { + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32), + BPF_JMP_IMM(BPF_JSLT, BPF_REG_0, 0, 2), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .retval = 4, +}, +{ + "bounded loop, count from totally unknown to 4", + .insns = { + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, +}, +{ + "bounded loop, count to 4 with equality", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 4, -2), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, +}, +{ + "bounded loop, start in the middle", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_JMP_A(1), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "back-edge", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .retval = 4, +}, +{ + "bounded loop containing a forward jump", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP_REG(BPF_JEQ, BPF_REG_0, BPF_REG_0, 0), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -3), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .retval = 4, +}, +{ + "bounded loop that jumps out rather than in", + .insns = { + BPF_MOV64_IMM(BPF_REG_6, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 1), + BPF_JMP_IMM(BPF_JGT, BPF_REG_6, 10000, 2), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32), + BPF_JMP_A(-4), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, +}, +{ + "infinite loop after a conditional jump", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 5), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, 2), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP_A(-2), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "program is too large", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, +}, +{ + "bounded recursion", + .insns = { + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1), + BPF_EXIT_INSN(), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_MOV64_REG(BPF_REG_0, BPF_REG_1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_1, 4, 1), + BPF_EXIT_INSN(), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, -5), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "back-edge", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, +}, +{ + "infinite loop in two jumps", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_JMP_A(0), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 4, -2), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "loop detected", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, +}, +{ + "infinite loop: three-jump trick", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, 1), + BPF_EXIT_INSN(), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, 1), + BPF_EXIT_INSN(), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 1), + BPF_JMP_IMM(BPF_JLT, BPF_REG_0, 2, -11), + BPF_EXIT_INSN(), + }, + .result = REJECT, + .errstr = "loop detected", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, +}, |