* [PATCH v2 bpf-next 0/3] bpf: two stack check fixes
@ 2017-12-25 21:15 Alexei Starovoitov
2017-12-25 21:15 ` [PATCH v2 bpf-next 1/3] bpf: fix maximum stack depth tracking logic Alexei Starovoitov
` (3 more replies)
0 siblings, 4 replies; 5+ messages in thread
From: Alexei Starovoitov @ 2017-12-25 21:15 UTC (permalink / raw)
To: David S . Miller; +Cc: Daniel Borkmann, Jann Horn, netdev, kernel-team
Jann reported an issue with stack depth tracking. Fix it and add tests.
Also fix off-by-one error in MAX_CALL_FRAMES check.
This set is on top of Jann's "selftest for late caller stack size increase" test.
Alexei Starovoitov (3):
bpf: fix maximum stack depth tracking logic
selftests/bpf: additional stack depth tests
bpf: fix max call depth check
include/linux/bpf_verifier.h | 1 +
kernel/bpf/verifier.c | 86 +++++++++++----
tools/testing/selftests/bpf/test_verifier.c | 156 ++++++++++++++++++++++++++++
3 files changed, 225 insertions(+), 18 deletions(-)
--
2.9.5
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH v2 bpf-next 1/3] bpf: fix maximum stack depth tracking logic 2017-12-25 21:15 [PATCH v2 bpf-next 0/3] bpf: two stack check fixes Alexei Starovoitov @ 2017-12-25 21:15 ` Alexei Starovoitov 2017-12-25 21:15 ` [PATCH v2 bpf-next 2/3] selftests/bpf: additional stack depth tests Alexei Starovoitov ` (2 subsequent siblings) 3 siblings, 0 replies; 5+ messages in thread From: Alexei Starovoitov @ 2017-12-25 21:15 UTC (permalink / raw) To: David S . Miller; +Cc: Daniel Borkmann, Jann Horn, netdev, kernel-team Instead of computing max stack depth for current call chain during the main verifier pass track stack depth of each function independently and after do_check() is done do another pass over all instructions analyzing depth of all possible call stacks. Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)") Reported-by: Jann Horn <jannh@google.com> Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 82 +++++++++++++++++++++++++++++++++++--------- 2 files changed, 67 insertions(+), 16 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index aaac589e490c..94a02ceb1246 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -194,6 +194,7 @@ struct bpf_verifier_env { struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */ struct bpf_verifer_log log; u32 subprog_starts[BPF_MAX_SUBPROGS]; + /* computes the stack depth of each bpf function */ u16 subprog_stack_depth[BPF_MAX_SUBPROGS + 1]; u32 subprog_cnt; }; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 82ae580440b8..738e919efdf0 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1430,33 +1430,80 @@ static int update_stack_depth(struct bpf_verifier_env *env, const struct bpf_func_state *func, int off) { - u16 stack = env->subprog_stack_depth[func->subprogno], total = 0; - struct bpf_verifier_state *cur = env->cur_state; - int i; + u16 stack = env->subprog_stack_depth[func->subprogno]; if (stack >= -off) return 0; /* update known max for given subprogram */ env->subprog_stack_depth[func->subprogno] = -off; + return 0; +} - /* compute the total for current call chain */ - for (i = 0; i <= cur->curframe; i++) { - u32 depth = env->subprog_stack_depth[cur->frame[i]->subprogno]; - - /* round up to 32-bytes, since this is granularity - * of interpreter stack sizes - */ - depth = round_up(depth, 32); - total += depth; - } +/* starting from main bpf function walk all instructions of the function + * and recursively walk all callees that given function can call. + * Ignore jump and exit insns. + * Since recursion is prevented by check_cfg() this algorithm + * only needs a local stack of MAX_CALL_FRAMES to remember callsites + */ +static int check_max_stack_depth(struct bpf_verifier_env *env) +{ + int depth = 0, frame = 0, subprog = 0, i = 0, subprog_end; + struct bpf_insn *insn = env->prog->insnsi; + int insn_cnt = env->prog->len; + int ret_insn[MAX_CALL_FRAMES]; + int ret_prog[MAX_CALL_FRAMES]; - if (total > MAX_BPF_STACK) { +process_func: + /* round up to 32-bytes, since this is granularity + * of interpreter stack size + */ + depth += round_up(max_t(u32, env->subprog_stack_depth[subprog], 1), 32); + if (depth > MAX_BPF_STACK) { verbose(env, "combined stack size of %d calls is %d. Too large\n", - cur->curframe, total); + frame + 1, depth); return -EACCES; } - return 0; +continue_func: + if (env->subprog_cnt == subprog) + subprog_end = insn_cnt; + else + subprog_end = env->subprog_starts[subprog]; + for (; i < subprog_end; i++) { + if (insn[i].code != (BPF_JMP | BPF_CALL)) + continue; + if (insn[i].src_reg != BPF_PSEUDO_CALL) + continue; + /* remember insn and function to return to */ + ret_insn[frame] = i + 1; + ret_prog[frame] = subprog; + + /* find the callee */ + i = i + insn[i].imm + 1; + subprog = find_subprog(env, i); + if (subprog < 0) { + WARN_ONCE(1, "verifier bug. No program starts at insn %d\n", + i); + return -EFAULT; + } + subprog++; + frame++; + if (frame >= MAX_CALL_FRAMES) { + WARN_ONCE(1, "verifier bug. Call stack is too deep\n"); + return -EFAULT; + } + goto process_func; + } + /* end of for() loop means the last insn of the 'subprog' + * was reached. Doesn't matter whether it was JA or EXIT + */ + if (frame == 0) + return 0; + depth -= round_up(max_t(u32, env->subprog_stack_depth[subprog], 1), 32); + frame--; + i = ret_insn[frame]; + subprog = ret_prog[frame]; + goto continue_func; } static int get_callee_stack_depth(struct bpf_verifier_env *env, @@ -5404,6 +5451,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr) sanitize_dead_code(env); if (ret == 0) + ret = check_max_stack_depth(env); + + if (ret == 0) /* program is valid, convert *(u32*)(ctx + off) accesses */ ret = convert_ctx_accesses(env); -- 2.9.5 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH v2 bpf-next 2/3] selftests/bpf: additional stack depth tests 2017-12-25 21:15 [PATCH v2 bpf-next 0/3] bpf: two stack check fixes Alexei Starovoitov 2017-12-25 21:15 ` [PATCH v2 bpf-next 1/3] bpf: fix maximum stack depth tracking logic Alexei Starovoitov @ 2017-12-25 21:15 ` Alexei Starovoitov 2017-12-25 21:15 ` [PATCH v2 bpf-next 3/3] bpf: fix max call depth check Alexei Starovoitov 2017-12-27 23:08 ` [PATCH v2 bpf-next 0/3] bpf: two stack check fixes Daniel Borkmann 3 siblings, 0 replies; 5+ messages in thread From: Alexei Starovoitov @ 2017-12-25 21:15 UTC (permalink / raw) To: David S . Miller; +Cc: Daniel Borkmann, Jann Horn, netdev, kernel-team to test inner logic of stack depth tracking Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- tools/testing/selftests/bpf/test_verifier.c | 121 ++++++++++++++++++++++++++++ 1 file changed, 121 insertions(+) diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c index 41dcc7dbba42..b5a7a6c530dc 100644 --- a/tools/testing/selftests/bpf/test_verifier.c +++ b/tools/testing/selftests/bpf/test_verifier.c @@ -8764,6 +8764,127 @@ static struct bpf_test tests[] = { .result = REJECT, }, { + "calls: stack depth check using three frames. test1", + .insns = { + /* main */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 4), /* call A */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 5), /* call B */ + BPF_ST_MEM(BPF_B, BPF_REG_10, -32, 0), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + /* A */ + BPF_ST_MEM(BPF_B, BPF_REG_10, -256, 0), + BPF_EXIT_INSN(), + /* B */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, -3), /* call A */ + BPF_ST_MEM(BPF_B, BPF_REG_10, -64, 0), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_XDP, + /* stack_main=32, stack_A=256, stack_B=64 + * and max(main+A, main+A+B) < 512 + */ + .result = ACCEPT, + }, + { + "calls: stack depth check using three frames. test2", + .insns = { + /* main */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 4), /* call A */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 5), /* call B */ + BPF_ST_MEM(BPF_B, BPF_REG_10, -32, 0), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + /* A */ + BPF_ST_MEM(BPF_B, BPF_REG_10, -64, 0), + BPF_EXIT_INSN(), + /* B */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, -3), /* call A */ + BPF_ST_MEM(BPF_B, BPF_REG_10, -256, 0), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_XDP, + /* stack_main=32, stack_A=64, stack_B=256 + * and max(main+A, main+A+B) < 512 + */ + .result = ACCEPT, + }, + { + "calls: stack depth check using three frames. test3", + .insns = { + /* main */ + BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 6), /* call A */ + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 8), /* call B */ + BPF_JMP_IMM(BPF_JGE, BPF_REG_6, 0, 1), + BPF_ST_MEM(BPF_B, BPF_REG_10, -64, 0), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + /* A */ + BPF_JMP_IMM(BPF_JLT, BPF_REG_1, 10, 1), + BPF_EXIT_INSN(), + BPF_ST_MEM(BPF_B, BPF_REG_10, -224, 0), + BPF_JMP_IMM(BPF_JA, 0, 0, -3), + /* B */ + BPF_JMP_IMM(BPF_JGT, BPF_REG_1, 2, 1), + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, -6), /* call A */ + BPF_ST_MEM(BPF_B, BPF_REG_10, -256, 0), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_XDP, + /* stack_main=64, stack_A=224, stack_B=256 + * and max(main+A, main+A+B) > 512 + */ + .errstr = "combined stack", + .result = REJECT, + }, + { + "calls: stack depth check using three frames. test4", + /* void main(void) { + * func1(0); + * func1(1); + * func2(1); + * } + * void func1(int alloc_or_recurse) { + * if (alloc_or_recurse) { + * frame_pointer[-300] = 1; + * } else { + * func2(alloc_or_recurse); + * } + * } + * void func2(int alloc_or_recurse) { + * if (alloc_or_recurse) { + * frame_pointer[-300] = 1; + * } + * } + */ + .insns = { + /* main */ + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 6), /* call A */ + BPF_MOV64_IMM(BPF_REG_1, 1), + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 4), /* call A */ + BPF_MOV64_IMM(BPF_REG_1, 1), + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 7), /* call B */ + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + /* A */ + BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 2), + BPF_ST_MEM(BPF_B, BPF_REG_10, -300, 0), + BPF_EXIT_INSN(), + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call B */ + BPF_EXIT_INSN(), + /* B */ + BPF_JMP_IMM(BPF_JEQ, BPF_REG_1, 0, 1), + BPF_ST_MEM(BPF_B, BPF_REG_10, -300, 0), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_XDP, + .result = REJECT, + .errstr = "combined stack", + }, + { "calls: spill into caller stack frame", .insns = { BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), -- 2.9.5 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH v2 bpf-next 3/3] bpf: fix max call depth check 2017-12-25 21:15 [PATCH v2 bpf-next 0/3] bpf: two stack check fixes Alexei Starovoitov 2017-12-25 21:15 ` [PATCH v2 bpf-next 1/3] bpf: fix maximum stack depth tracking logic Alexei Starovoitov 2017-12-25 21:15 ` [PATCH v2 bpf-next 2/3] selftests/bpf: additional stack depth tests Alexei Starovoitov @ 2017-12-25 21:15 ` Alexei Starovoitov 2017-12-27 23:08 ` [PATCH v2 bpf-next 0/3] bpf: two stack check fixes Daniel Borkmann 3 siblings, 0 replies; 5+ messages in thread From: Alexei Starovoitov @ 2017-12-25 21:15 UTC (permalink / raw) To: David S . Miller; +Cc: Daniel Borkmann, Jann Horn, netdev, kernel-team fix off by one error in max call depth check and add a test Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)") Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- kernel/bpf/verifier.c | 4 ++-- tools/testing/selftests/bpf/test_verifier.c | 35 +++++++++++++++++++++++++++++ 2 files changed, 37 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 738e919efdf0..52ad60b3b8be 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2126,9 +2126,9 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn, struct bpf_func_state *caller, *callee; int i, subprog, target_insn; - if (state->curframe >= MAX_CALL_FRAMES) { + if (state->curframe + 1 >= MAX_CALL_FRAMES) { verbose(env, "the call stack of %d frames is too deep\n", - state->curframe); + state->curframe + 2); return -E2BIG; } diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c index b5a7a6c530dc..5d0a574ce270 100644 --- a/tools/testing/selftests/bpf/test_verifier.c +++ b/tools/testing/selftests/bpf/test_verifier.c @@ -8885,6 +8885,41 @@ static struct bpf_test tests[] = { .errstr = "combined stack", }, { + "calls: stack depth check using three frames. test5", + .insns = { + /* main */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call A */ + BPF_EXIT_INSN(), + /* A */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call B */ + BPF_EXIT_INSN(), + /* B */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call C */ + BPF_EXIT_INSN(), + /* C */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call D */ + BPF_EXIT_INSN(), + /* D */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call E */ + BPF_EXIT_INSN(), + /* E */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call F */ + BPF_EXIT_INSN(), + /* F */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call G */ + BPF_EXIT_INSN(), + /* G */ + BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 1), /* call H */ + BPF_EXIT_INSN(), + /* H */ + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_XDP, + .errstr = "call stack", + .result = REJECT, + }, + { "calls: spill into caller stack frame", .insns = { BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), -- 2.9.5 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v2 bpf-next 0/3] bpf: two stack check fixes 2017-12-25 21:15 [PATCH v2 bpf-next 0/3] bpf: two stack check fixes Alexei Starovoitov ` (2 preceding siblings ...) 2017-12-25 21:15 ` [PATCH v2 bpf-next 3/3] bpf: fix max call depth check Alexei Starovoitov @ 2017-12-27 23:08 ` Daniel Borkmann 3 siblings, 0 replies; 5+ messages in thread From: Daniel Borkmann @ 2017-12-27 23:08 UTC (permalink / raw) To: Alexei Starovoitov, David S . Miller; +Cc: Jann Horn, netdev, kernel-team On 12/25/2017 10:15 PM, Alexei Starovoitov wrote: > Jann reported an issue with stack depth tracking. Fix it and add tests. > Also fix off-by-one error in MAX_CALL_FRAMES check. > This set is on top of Jann's "selftest for late caller stack size increase" test. > > Alexei Starovoitov (3): > bpf: fix maximum stack depth tracking logic > selftests/bpf: additional stack depth tests > bpf: fix max call depth check > > include/linux/bpf_verifier.h | 1 + > kernel/bpf/verifier.c | 86 +++++++++++---- > tools/testing/selftests/bpf/test_verifier.c | 156 ++++++++++++++++++++++++++++ > 3 files changed, 225 insertions(+), 18 deletions(-) Applied to bpf-next, thanks Alexei! ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-12-27 23:09 UTC | newest] Thread overview: 5+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2017-12-25 21:15 [PATCH v2 bpf-next 0/3] bpf: two stack check fixes Alexei Starovoitov 2017-12-25 21:15 ` [PATCH v2 bpf-next 1/3] bpf: fix maximum stack depth tracking logic Alexei Starovoitov 2017-12-25 21:15 ` [PATCH v2 bpf-next 2/3] selftests/bpf: additional stack depth tests Alexei Starovoitov 2017-12-25 21:15 ` [PATCH v2 bpf-next 3/3] bpf: fix max call depth check Alexei Starovoitov 2017-12-27 23:08 ` [PATCH v2 bpf-next 0/3] bpf: two stack check fixes Daniel Borkmann
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).