Skip to contentSkip to conversation

bpf: two stack check fixes

PATCH Applied Alexei Starovoitov 2 participants 5 messages Dec 25, 2017 – Dec 27, 2017

Subsystems (6)
Networking Network drivers Kselftest BPF +2 more subsystems
lore
Share & tools
lore

Alexei Starovoitov

author maintainer
#0 lore raw

v2 cover bpf: two stack check fixes

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(-)
Signature · 1 line
2.9.5
author maintainer
#1 lore raw

PATCH v2 1/3 bpf: fix maximum stack depth tracking logic

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 <[email protected]>
Signed-off-by Alexei Starovoitov <[email protected]>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 82 +++++++++++++++++++++++++++++++++++---------
 2 files changed, 67 insertions(+), 16 deletions(-)
include/linux/bpf_verifier.h +1 -0
index aaac589e490c..94a02ceb1246 100644
@@ -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;
 };
kernel/bpf/verifier.c +66 -16

105 lines not on this page · raw message

Signature · 1 line
2.9.5
author maintainer
#2 lore raw

PATCH v2 2/3 selftests/bpf: additional stack depth tests

In reply to Alexei Starovoitov

to test inner logic of stack depth tracking

Signed-off-by Alexei Starovoitov <[email protected]>
---
 tools/testing/selftests/bpf/test_verifier.c | 121 ++++++++++++++++++++++++++++
 1 file changed, 121 insertions(+)
tools/testing/selftests/bpf/test_verifier.c +121 -0
index 41dcc7dbba42..b5a7a6c530dc 100644
@@ -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),
Signature · 1 line
2.9.5
author maintainer
#3 lore raw

PATCH v2 3/3 bpf: fix max call depth check

In reply to Alexei Starovoitov

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 <[email protected]>
---
 kernel/bpf/verifier.c                       |  4 ++--
 tools/testing/selftests/bpf/test_verifier.c | 35 +++++++++++++++++++++++++++++
 2 files changed, 37 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +2 -2
index 738e919efdf0..52ad60b3b8be 100644
@@ -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;
 	}
tools/testing/selftests/bpf/test_verifier.c +35 -0
index b5a7a6c530dc..5d0a574ce270 100644
@@ -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),
Signature · 1 line
2.9.5
maintainer Applied
#4 lore raw
In reply to Alexei Starovoitov
Quoted 9 lines · Alexei Starovoitov

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

Quoted 4 lines
 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!