diff mbox series

[RFC,bpf-next,05/12] bpf/verifier: detect loops dynamically rather than statically

Message ID 0575362a-2b06-6a3a-f5a2-2d74ba62889a@solarflare.com
State RFC, archived
Delegated to: BPF Maintainers
Headers show
Series bounded loops for eBPF | expand

Commit Message

Edward Cree Feb. 23, 2018, 5:40 p.m. UTC 
Add in a new chain of parent states, which does not cross function-call
 boundaries, and check whether our current insn_idx appears anywhere in
 the chain.  Since all jump targets have state-list marks (now placed
 by prepare_cfg_marks(), which replaces check_cfg()), it suffices to
 thread this chain through the existing explored_states and check it
 only in is_state_visited().
By using this parent-state chain to detect loops, we open up the
 possibility that in future we could determine a loop to be bounded and
 thus accept it.
A few selftests had to be changed to ensure that all the insns walked
 before reaching the back-edge are valid.

Signed-off-by: Edward Cree <ecree@solarflare.com>
---
 include/linux/bpf_verifier.h                |   2 +
 kernel/bpf/verifier.c                       | 280 +++++++++-------------------
 tools/testing/selftests/bpf/test_verifier.c |  12 +-
 3 files changed, 97 insertions(+), 197 deletions(-)

Comments

John Fastabend Feb. 23, 2018, 10:27 p.m. UTC | #1 
On 02/23/2018 09:40 AM, Edward Cree wrote:
> Add in a new chain of parent states, which does not cross function-call
>  boundaries, and check whether our current insn_idx appears anywhere in
>  the chain.  Since all jump targets have state-list marks (now placed
>  by prepare_cfg_marks(), which replaces check_cfg()), it suffices to
>  thread this chain through the existing explored_states and check it
>  only in is_state_visited().
> By using this parent-state chain to detect loops, we open up the
>  possibility that in future we could determine a loop to be bounded and
>  thus accept it.
> A few selftests had to be changed to ensure that all the insns walked
>  before reaching the back-edge are valid.
> 

I still believe this needs to be done in an initial pass where we can
build a proper CFG and analyze the loops to ensure we have loops that
can be properly verified. Otherwise we end up trying to handle all the
special cases later like the comment in patch 7/12 'three-jump trick'.
So rather than try to handle all loops only handle "normal" loops. In
an early CFG stage with DOM tree the algorithm for this is already
used by gcc/clang so there is good precedent for this type of work.

Without this we are open to other "clever" goto programs that create
loops that we have to special case. Better to just reject all these
classes of loops because most users will never need them.

See more notes in 7/12 patch, sorry I've been busy and not had a chance
to push code to build cfg and dom tree yet.

Also case analysis in patch description describing types of loops
this handles (either here or in another patch) would help me understand
at least.

> Signed-off-by: Edward Cree <ecree@solarflare.com>
> ---
>  include/linux/bpf_verifier.h                |   2 +
>  kernel/bpf/verifier.c                       | 280 +++++++++-------------------
>  tools/testing/selftests/bpf/test_verifier.c |  12 +-
>  3 files changed, 97 insertions(+), 197 deletions(-)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 0bc49c768585..24ddbc1ed3b2 100644
>
Edward Cree Feb. 26, 2018, 12:53 p.m. UTC | #2 
On 23/02/18 22:27, John Fastabend wrote:
> On 02/23/2018 09:40 AM, Edward Cree wrote:
>> Add in a new chain of parent states, which does not cross function-call
>>  boundaries, and check whether our current insn_idx appears anywhere in
>>  the chain.  Since all jump targets have state-list marks (now placed
>>  by prepare_cfg_marks(), which replaces check_cfg()), it suffices to
>>  thread this chain through the existing explored_states and check it
>>  only in is_state_visited().
>> By using this parent-state chain to detect loops, we open up the
>>  possibility that in future we could determine a loop to be bounded and
>>  thus accept it.
>> A few selftests had to be changed to ensure that all the insns walked
>>  before reaching the back-edge are valid.
>>
> I still believe this needs to be done in an initial pass where we can
> build a proper CFG and analyze the loops to ensure we have loops that
> can be properly verified. Otherwise we end up trying to handle all the
> special cases later like the comment in patch 7/12 'three-jump trick'.
It's not so much that the 'three-jump trick' is a special case with special
 code to handle it; more that it's the simplest construction I found for
 defeating the case where you make a purely local decision and just look at
 whether there's a progressing test in the current loop body.  That & the
 entire class of trickery it represents is dealt with by saying that once a
 test has been determined to be bounded, it has to stay bounded on all
 subsequent loop iterations.  (I considered various relaxed versions of
 this constraint but they're harder to reason about.)

I would be happier if I could write out a proof that the verifier does what
 I think it does; but I'm not really sure how to formally define "what I
 think it does"...

> So rather than try to handle all loops only handle "normal" loops. In
> an early CFG stage with DOM tree the algorithm for this is already
> used by gcc/clang so there is good precedent for this type of work.
>
> Without this we are open to other "clever" goto programs that create
> loops that we have to special case. Better to just reject all these
> classes of loops because most users will never need them.
If we want to be narrow (perhaps just initially), we could also just say
 that the loop body can't contain any other conditional jumps.  But that
 would be awkward since, while users may not need loop-in-loop, they are
 quite likely to need if-in-loop, and I don't yet quite have a solid
 algorithm for disallowing only the former.

> See more notes in 7/12 patch, sorry I've been busy and not had a chance
> to push code to build cfg and dom tree yet.
That's fine, gives me more time to polish mine so that it looks like the
 better option when your version does come out ;-)

> Also case analysis in patch description describing types of loops
> this handles (either here or in another patch) would help me understand
> at least.
Yes, I didn't really describe that very much, did I?  Here's a précis:
From a 'loop structure' point of view, this basically handles anything;
 if the verifier walks it and arrives at an insn it's already visited,
 then the loop handling fires.  The current implementation does have
 the restriction that the conditional branch that's responsible for loop
 termination has to loop in the 'true' branch, i.e.
    loop:   /* do things */
            jr cc, loop
 rather than
    loop:   /* do things */
            jr cc, break
            ja loop
    break:  /* etc. */
 but that's really just because only one case is handled so far in
 is_loop_bounded(), and there's no reason the latter kind can't be
 handled too.
Interestingly, if it didn't have a separate check for recursion, it
 would also handle boundedly recursive calls, like in the test_verifier
 test case "bounded recursion" added in patch #8.  It _really_ doesn't
 care about the 'structure' of the loop...

The other constraint at the moment is that only JLT is handled as the
 back-edge jump, and the 'src' has to be a constant.  Extending it to
 cover other insns than JLT should be pretty trivial (just need an
 is_reg_decreasing() function and signed equivalents, mainly); adding
 support for variable src would be harder & probably unnecessary.

So currently it will handle loops like
    loop:    /* do things, including arithmetic on rX */
             jr <, rX, 16, loop
 or even like
    loop:    /* do things */
             jr <, rX, 16, more
             ja break
    more:    /* do more things */
             ja loop /* or jr cc, loop; so long as this isn't sometimes-bounded */
    break:   /* etc. */

From a C perspective, this should mean things like
    int i;
    for (i = 0; i < 10; i++)
        /* do things */;
 where that 'do things' can include all kinds of jumps, including
 conditional ones (mostly), and can even have extra 'i++' statements.
 This last is necessary for the (potential) use case of IPv6 options
 parsing, which would look something like:
    int nh_off;
    for (nh_off = iph_off + 40;
         nh_off < ARBITRARY_MAXIMUM && data + nh_off + 2 < data_end;
         ) {
        u8 nexthdr = data[nh_off];
        u16 exthdrlen = (data[nh_off + 1] + 1) * 8;

        if (!is_option(nexthdr)) break;
        nh_off += exthdrlen;
    }
Note that it takes some value analysis (noting that exthdrlen >= 8)
 to determine that nh_off is increasing; I think there is at least
 *some* advantage in keeping all of that value analysis in one place
 (the existing walker) rather than having some potentially duplicate
 code trying to prove similar things on the dominance tree.

But if you (/maintainers) still think the static-analysis cfg/dom way
 is more appropriate after having seen mine, then go ahead and do it
 your way, I won't try to fight to have it done this way :-)

-Ed
diff mbox series

Patch

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 0bc49c768585..24ddbc1ed3b2 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -120,6 +120,8 @@  struct bpf_func_state {
 	 * zero == main subprog
 	 */
 	u32 subprogno;
+	/* loop detection; points into an explored_state */
+	struct bpf_func_state *parent;
 
 	/* should be second to last. See copy_func_state() */
 	int allocated_stack;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 7a08b5e8e071..e7d898f4fd29 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -429,6 +429,7 @@  static int copy_verifier_state(struct bpf_verifier_state *dst_state,
 		dst_state->frame[i] = NULL;
 	}
 	dst_state->curframe = src->curframe;
+
 	for (i = 0; i <= src->curframe; i++) {
 		dst = dst_state->frame[i];
 		if (!dst) {
@@ -716,6 +717,7 @@  static void init_func_state(struct bpf_verifier_env *env,
 			    int entry, int frameno, int subprogno)
 {
 	state->insn_idx = entry;
+	state->parent = NULL;
 	state->frameno = frameno;
 	state->subprogno = subprogno;
 	init_reg_state(env, state);
@@ -3747,211 +3749,85 @@  static int check_return_code(struct bpf_verifier_env *env)
 	return 0;
 }
 
-/* non-recursive DFS pseudo code
- * 1  procedure DFS-iterative(G,v):
- * 2      label v as discovered
- * 3      let S be a stack
- * 4      S.push(v)
- * 5      while S is not empty
- * 6            t <- S.pop()
- * 7            if t is what we're looking for:
- * 8                return t
- * 9            for all edges e in G.adjacentEdges(t) do
- * 10               if edge e is already labelled
- * 11                   continue with the next edge
- * 12               w <- G.adjacentVertex(t,e)
- * 13               if vertex w is not discovered and not explored
- * 14                   label e as tree-edge
- * 15                   label w as discovered
- * 16                   S.push(w)
- * 17                   continue at 5
- * 18               else if vertex w is discovered
- * 19                   label e as back-edge
- * 20               else
- * 21                   // vertex w is explored
- * 22                   label e as forward- or cross-edge
- * 23           label t as explored
- * 24           S.pop()
- *
- * convention:
- * 0x10 - discovered
- * 0x11 - discovered and fall-through edge labelled
- * 0x12 - discovered and fall-through and branch edges labelled
- * 0x20 - explored
- */
-
-enum {
-	DISCOVERED = 0x10,
-	EXPLORED = 0x20,
-	FALLTHROUGH = 1,
-	BRANCH = 2,
-};
-
 #define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
 
-static int *insn_stack;	/* stack of insns to process */
-static int cur_stack;	/* current stack index */
-static int *insn_state;
-
-/* t, w, e - match pseudo-code above:
- * t - index of current instruction
- * w - next instruction
- * e - edge
- */
-static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
+static int mark_jump_target(struct bpf_verifier_env *env, int from, int off)
 {
-	if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
-		return 0;
-
-	if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
-		return 0;
+	int to = from + off + 1;
 
-	if (w < 0 || w >= env->prog->len) {
-		verbose(env, "jump out of range from insn %d to %d\n", t, w);
+	if (to < 0 || to >= env->prog->len) {
+		verbose(env, "jump out of range from insn %d to %d\n", from, to);
 		return -EINVAL;
 	}
-
-	if (e == BRANCH)
-		/* mark branch target for state pruning */
-		env->explored_states[w] = STATE_LIST_MARK;
-
-	if (insn_state[w] == 0) {
-		/* tree-edge */
-		insn_state[t] = DISCOVERED | e;
-		insn_state[w] = DISCOVERED;
-		if (cur_stack >= env->prog->len)
-			return -E2BIG;
-		insn_stack[cur_stack++] = w;
-		return 1;
-	} else if ((insn_state[w] & 0xF0) == DISCOVERED) {
-		verbose(env, "back-edge from insn %d to %d\n", t, w);
-		return -EINVAL;
-	} else if (insn_state[w] == EXPLORED) {
-		/* forward- or cross-edge */
-		insn_state[t] = DISCOVERED | e;
-	} else {
-		verbose(env, "insn state internal bug\n");
-		return -EFAULT;
-	}
+	/* mark branch target for state pruning */
+	env->explored_states[to] = STATE_LIST_MARK;
 	return 0;
 }
 
-/* non-recursive depth-first-search to detect loops in BPF program
- * loop == back-edge in directed graph
- */
-static int check_cfg(struct bpf_verifier_env *env)
+/* Mark jump/branch targets for control flow tracking & state pruning */
+static int prepare_cfg_marks(struct bpf_verifier_env *env)
 {
 	struct bpf_insn *insns = env->prog->insnsi;
-	int insn_cnt = env->prog->len;
-	int ret = 0;
-	int i, t;
+	int insn_cnt = env->prog->len, i, err = 0;
 
-	insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
-	if (!insn_state)
-		return -ENOMEM;
-
-	insn_stack = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
-	if (!insn_stack) {
-		kfree(insn_state);
-		return -ENOMEM;
-	}
+	for (i = 0; i < insn_cnt; i++) {
+		u8 opcode = BPF_OP(insns[i].code);
 
-	insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */
-	insn_stack[0] = 0; /* 0 is the first instruction */
-	cur_stack = 1;
-
-peek_stack:
-	if (cur_stack == 0)
-		goto check_state;
-	t = insn_stack[cur_stack - 1];
-
-	if (BPF_CLASS(insns[t].code) == BPF_JMP) {
-		u8 opcode = BPF_OP(insns[t].code);
-
-		if (opcode == BPF_EXIT) {
-			goto mark_explored;
-		} else if (opcode == BPF_CALL) {
-			ret = push_insn(t, t + 1, FALLTHROUGH, env);
-			if (ret == 1)
-				goto peek_stack;
-			else if (ret < 0)
-				goto err_free;
-			if (t + 1 < insn_cnt)
-				env->explored_states[t + 1] = STATE_LIST_MARK;
-			if (insns[t].src_reg == BPF_PSEUDO_CALL) {
-				env->explored_states[t] = STATE_LIST_MARK;
-				ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env);
-				if (ret == 1)
-					goto peek_stack;
-				else if (ret < 0)
-					goto err_free;
-			}
-		} else if (opcode == BPF_JA) {
-			if (BPF_SRC(insns[t].code) != BPF_K) {
-				ret = -EINVAL;
-				goto err_free;
+		if (BPF_CLASS(insns[i].code) != BPF_JMP) {
+			if (i + 1 == insn_cnt) {
+				verbose(env, "no exit/jump at end of program (insn %d)\n",
+					i);
+				return -EINVAL;
 			}
-			/* unconditional jump with single edge */
-			ret = push_insn(t, t + insns[t].off + 1,
-					FALLTHROUGH, env);
-			if (ret == 1)
-				goto peek_stack;
-			else if (ret < 0)
-				goto err_free;
-			/* tell verifier to check for equivalent states
-			 * after every call and jump
-			 */
-			if (t + 1 < insn_cnt)
-				env->explored_states[t + 1] = STATE_LIST_MARK;
-		} else {
-			/* conditional jump with two edges */
-			env->explored_states[t] = STATE_LIST_MARK;
-			ret = push_insn(t, t + 1, FALLTHROUGH, env);
-			if (ret == 1)
-				goto peek_stack;
-			else if (ret < 0)
-				goto err_free;
-
-			ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);
-			if (ret == 1)
-				goto peek_stack;
-			else if (ret < 0)
-				goto err_free;
+			continue;
 		}
-	} else {
-		/* all other non-branch instructions with single
-		 * fall-through edge
-		 */
-		ret = push_insn(t, t + 1, FALLTHROUGH, env);
-		if (ret == 1)
-			goto peek_stack;
-		else if (ret < 0)
-			goto err_free;
-	}
-
-mark_explored:
-	insn_state[t] = EXPLORED;
-	if (cur_stack-- <= 0) {
-		verbose(env, "pop stack internal bug\n");
-		ret = -EFAULT;
-		goto err_free;
+		switch (opcode) {
+		case BPF_EXIT:
+			continue;
+		case BPF_CALL:
+			/* following insn is target of function return */
+			err = mark_jump_target(env, i, 0);
+			if (err)
+				return err;
+			if (insns[i].src_reg == BPF_PSEUDO_CALL)
+				err = mark_jump_target(env, i, insns[i].imm);
+			break;
+		case BPF_JA:
+			/* unconditional jump; mark target */
+			err = mark_jump_target(env, i, insns[i].off);
+			break;
+		default:
+			/* conditional jump; mark following insn and target */
+			err = mark_jump_target(env, i, 0);
+			if (err)
+				return err;
+			err = mark_jump_target(env, i, insns[i].off);
+		}
+		if (err)
+			return err;
 	}
-	goto peek_stack;
 
-check_state:
+	/* Second pass, to detect statically unreachable code.  Any target of
+	 * a jump or call will have a state-list mark
+	 */
 	for (i = 0; i < insn_cnt; i++) {
-		if (insn_state[i] != EXPLORED) {
-			verbose(env, "unreachable insn %d\n", i);
-			ret = -EINVAL;
-			goto err_free;
-		}
+		/* insn following a non-jump is statically reachable */
+		if (BPF_CLASS(insns[i].code) != BPF_JMP)
+			continue;
+		/* insn following a CALL or conditional jump will have been
+		 * marked by that insn (see above).  So if following insn is
+		 * not marked, then we're an EXIT or JA and thus the
+		 * following insn is statically unreachable.
+		 * If we're last insn, and we're not an EXIT or JA, then first
+		 * pass would have complained in mark_jump_target().
+		 */
+		if (i + 1 < insn_cnt)
+			if (env->explored_states[i + 1] != STATE_LIST_MARK) {
+				verbose(env, "unreachable insn %d\n", i + 1);
+				return -EINVAL;
+			}
 	}
-	ret = 0; /* cfg looks good */
-
-err_free:
-	kfree(insn_state);
-	kfree(insn_stack);
-	return ret;
+	return 0;
 }
 
 /* check %cur's range satisfies %old's */
@@ -4287,11 +4163,24 @@  static int propagate_liveness(struct bpf_verifier_env *env,
 	return err;
 }
 
-static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
+static struct bpf_func_state *find_loop(struct bpf_verifier_env *env)
+{
+	struct bpf_func_state *cur = cur_frame(env);
+	int insn_idx = cur->insn_idx;
+
+	while ((cur = cur->parent) != NULL)
+		if (cur->insn_idx == insn_idx)
+			return cur;
+	return NULL;
+}
+
+static int is_state_visited(struct bpf_verifier_env *env, int prev_insn_idx,
+			    int insn_idx)
 {
 	struct bpf_verifier_state_list *new_sl;
 	struct bpf_verifier_state_list *sl;
 	struct bpf_verifier_state *cur = env->cur_state, *new;
+	struct bpf_func_state *old;
 	int i, j, err;
 
 	sl = env->explored_states[insn_idx];
@@ -4301,6 +4190,14 @@  static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		 */
 		return 0;
 
+	/* Check our parentage chain: have we looped? */
+	old = find_loop(env);
+	if (old != NULL) {
+		verbose(env, "back-edge from insn %d to %d\n", prev_insn_idx,
+			insn_idx);
+		return -EINVAL;
+	}
+
 	while (sl != STATE_LIST_MARK) {
 		if (states_equal(env, &sl->state, cur)) {
 			/* reached equivalent register/stack state,
@@ -4342,7 +4239,7 @@  static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 	}
 	new_sl->next = env->explored_states[insn_idx];
 	env->explored_states[insn_idx] = new_sl;
-	/* connect new state to parentage chain */
+	/* connect new state's regs to parentage chain */
 	for (i = 0; i < BPF_REG_FP; i++)
 		cur_regs(env)[i].parent = &new->frame[new->curframe]->regs[i];
 	/* clear write marks in current state: the writes we did are not writes
@@ -4359,6 +4256,7 @@  static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		struct bpf_func_state *frame = cur->frame[j];
 		struct bpf_func_state *newframe = new->frame[j];
 
+		frame->parent = newframe;
 		for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) {
 			frame->stack[i].spilled_ptr.live = REG_LIVE_NONE;
 			frame->stack[i].spilled_ptr.parent =
@@ -4404,7 +4302,7 @@  static int do_check(struct bpf_verifier_env *env)
 		u8 class;
 		int err;
 
-		if (insn_idx >= insn_cnt) {
+		if (insn_idx < 0 || insn_idx >= insn_cnt) {
 			verbose(env, "invalid insn idx %d insn_cnt %d\n",
 				insn_idx, insn_cnt);
 			return -EFAULT;
@@ -4433,7 +4331,7 @@  static int do_check(struct bpf_verifier_env *env)
 		aux->subprogno = frame->subprogno;
 		aux->seen = true;
 
-		err = is_state_visited(env, insn_idx);
+		err = is_state_visited(env, prev_insn_idx, insn_idx);
 		if (err < 0)
 			return err;
 		if (err == 1) {
@@ -5581,7 +5479,7 @@  int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
 
 	env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
 
-	ret = check_cfg(env);
+	ret = prepare_cfg_marks(env);
 	if (ret < 0)
 		goto skip_full_check;
 
diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 9c7531887ee3..722a16b2e9c4 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -644,14 +644,13 @@  static struct bpf_test tests[] = {
 		.insns = {
 			BPF_ALU64_REG(BPF_MOV, BPF_REG_0, BPF_REG_2),
 		},
-		.errstr = "jump out of range",
+		.errstr = "no exit/jump at end of program",
 		.result = REJECT,
 	},
 	{
 		"loop (back-edge)",
 		.insns = {
 			BPF_JMP_IMM(BPF_JA, 0, 0, -1),
-			BPF_EXIT_INSN(),
 		},
 		.errstr = "back-edge",
 		.result = REJECT,
@@ -659,11 +658,11 @@  static struct bpf_test tests[] = {
 	{
 		"loop2 (back-edge)",
 		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 0),
 			BPF_MOV64_REG(BPF_REG_1, BPF_REG_0),
 			BPF_MOV64_REG(BPF_REG_2, BPF_REG_0),
 			BPF_MOV64_REG(BPF_REG_3, BPF_REG_0),
 			BPF_JMP_IMM(BPF_JA, 0, 0, -4),
-			BPF_EXIT_INSN(),
 		},
 		.errstr = "back-edge",
 		.result = REJECT,
@@ -671,6 +670,7 @@  static struct bpf_test tests[] = {
 	{
 		"conditional loop",
 		.insns = {
+			BPF_MOV64_IMM(BPF_REG_0, 0),
 			BPF_MOV64_REG(BPF_REG_1, BPF_REG_0),
 			BPF_MOV64_REG(BPF_REG_2, BPF_REG_0),
 			BPF_MOV64_REG(BPF_REG_3, BPF_REG_0),
@@ -9338,7 +9338,7 @@  static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "back-edge from insn 0 to 0",
+		.errstr = "frames is too deep",
 		.result = REJECT,
 	},
 	{
@@ -9666,7 +9666,7 @@  static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "back-edge",
+		.errstr = "frames is too deep",
 		.result = REJECT,
 	},
 	{
@@ -9678,7 +9678,7 @@  static struct bpf_test tests[] = {
 			BPF_EXIT_INSN(),
 		},
 		.prog_type = BPF_PROG_TYPE_TRACEPOINT,
-		.errstr = "back-edge",
+		.errstr = "frames is too deep",
 		.result = REJECT,
 	},
 	{