From mboxrd@z Thu Jan 1 00:00:00 1970 From: Alexei Starovoitov Subject: [PATCH bpf-next 1/2] bpf: fix maximum stack depth tracking logic Date: Fri, 22 Dec 2017 13:33:27 -0800 Message-ID: <20171222213328.993019-2-ast@kernel.org> References: <20171222213328.993019-1-ast@kernel.org> Mime-Version: 1.0 Content-Type: text/plain Cc: Daniel Borkmann , Jann Horn , , To: "David S . Miller" Return-path: Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:45162 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756086AbdLVVda (ORCPT ); Fri, 22 Dec 2017 16:33:30 -0500 Received: from pps.filterd (m0109333.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.21/8.16.0.21) with SMTP id vBMLUg17025509 for ; Fri, 22 Dec 2017 13:33:29 -0800 Received: from mail.thefacebook.com ([199.201.64.23]) by mx0a-00082601.pphosted.com with ESMTP id 2f16ed8q87-1 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Fri, 22 Dec 2017 13:33:29 -0800 In-Reply-To: <20171222213328.993019-1-ast@kernel.org> Sender: netdev-owner@vger.kernel.org List-ID: instead of computing max stack depth for current call chain only track the maximum possible stack depth of any function at given frame position. Such algorithm is simple and fast, but conservative, since it overestimates amount of stack used. Consider: main() // stack 32 { A(); B(); } A(){} // stack 256 B() // stack 64 { A(); } since A() is called at frame[1] and frame[2], the algorithm will estimate the max stack depth as 32 + 256 + 256 and will reject such program, though real max is 32 + 64 + 256. Fortunately the algorithm is good enough in practice. The alternative would be to track max stack of every function in the fast pass through the verifier and then do additional CFG walk just to compute max total. Fixes: f4d7e40a5b71 ("bpf: introduce function calls (verification)") Reported-by: Jann Horn Signed-off-by: Alexei Starovoitov --- include/linux/bpf_verifier.h | 17 +++++++++++++++++ kernel/bpf/verifier.c | 15 +++++++++------ 2 files changed, 26 insertions(+), 6 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index aaac589e490c..adc65ef093d1 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -194,7 +194,24 @@ 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]; + /* gradually computes the maximum stack depth out of all functions + * called at this frame position. Example: + * main() + * { + * a(); + * b(); + * } + * b() + * { + * a(); + * } + * frame_stack_depth[0] = stack depth of main() + * frame_stack_depth[1] = max { stack depth of a(), stack depth of b() } + * frame_stack_depth[2] = stack depth of a() + */ + u16 frame_stack_depth[MAX_CALL_FRAMES]; u32 subprog_cnt; }; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 4ae46b2cba88..096681bcb312 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -1434,15 +1434,18 @@ static int update_stack_depth(struct bpf_verifier_env *env, struct bpf_verifier_state *cur = env->cur_state; int i; + if (stack < -off) + /* update known max for given subprogram */ + env->subprog_stack_depth[func->subprogno] = -off; + + stack = env->frame_stack_depth[func->frameno]; if (stack >= -off) return 0; + env->frame_stack_depth[func->frameno] = -off; - /* update known max for given subprogram */ - env->subprog_stack_depth[func->subprogno] = -off; - - /* compute the total for current call chain */ - for (i = 0; i <= cur->curframe; i++) { - u32 depth = env->subprog_stack_depth[cur->frame[i]->subprogno]; + /* some frame changed its max, recompute the total */ + for (i = 0; i < MAX_CALL_FRAMES; i++) { + u32 depth = env->frame_stack_depth[i]; /* round up to 32-bytes, since this is granularity * of interpreter stack sizes -- 2.9.5