Suppose the verifier state exploration graph looks as follows:
.-> A --. Suppose:
| | | - state A is at iterator 'next';
| v v - path A -> B -> A is verified first;
'-- B C - path A -> C is verified next;
- B does not impose a read mark for register R1;
- C imposes a read mark for register R1;
Under such conditions:
- when B is explored and A is identified as its loop entry, the read
marks are copied from A to B by propagate_liveness(), but these
marks do not include R1;
- when C is explored, the read mark for R1 is propagated to A,
but not to B.
- at this point, state A has its branch count at zero, but state
B has incomplete read marks.
The same logic applies to precision marks.
This means that states with a loop entry can have incomplete read and
precision marks, regardless of whether the loop entry itself has
branches.
The current verification logic does not account for this. An example
of an unsafe program accepted by the verifier is the selftest included
in the next patch.
Fix this by removing bpf_verifier_state->branches checks for loop
entries in clean_live_states() and is_state_visited().
Verification performance impact for selftests and sched_ext:
========= selftests: master vs patch =========
File Program States (A) States (B) States (DIFF)
---------------------------------- ----------------- ---------- ---------- -------------
iters.bpf.o clean_live_states 66 67 +1 (+1.52%)
verifier_iterating_callbacks.bpf.o cond_break2 10 13 +3 (+30.00%)
Total progs: 3579
Old success: 2061
New success: 2061
States diff min: 0.00%
States diff max: 30.00%
0 .. 5 %: 3578
30 .. 35 %: 1
========= sched_ext: master vs patch =========
File Program States (A) States (B) States (DIFF)
-------------- ---------------- ---------- ---------- -------------
bpf.bpf.o layered_dispatch 501 516 +15 (+2.99%)
bpf.bpf.o layered_dump 237 252 +15 (+6.33%)
bpf.bpf.o layered_init 423 432 +9 (+2.13%)
bpf.bpf.o p2dq_init 142 144 +2 (+1.41%)
scx_pair.bpf.o pair_dispatch 111 138 +27 (+24.32%)
scx_qmap.bpf.o qmap_dump 22 30 +8 (+36.36%)
scx_qmap.bpf.o qmap_init 654 656 +2 (+0.31%)
Total progs: 216
Old success: 186
New success: 186
States diff min: 0.00%
States diff max: 36.36%
0 .. 5 %: 213
5 .. 15 %: 1
20 .. 30 %: 1
35 .. 40 %: 1
Fixes: 2a0992829ea3 ("bpf: correct loop detection for iterators convergence")
Signed-off-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
---
kernel/bpf/verifier.c | 9 ++++-----
1 file changed, 4 insertions(+), 5 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3303a3605ee8..6c18628fa9d8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18111,7 +18111,7 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
if (sl->state.branches)
continue;
loop_entry = get_loop_entry(env, &sl->state);
- if (!IS_ERR_OR_NULL(loop_entry) && loop_entry->branches)
+ if (!IS_ERR_OR_NULL(loop_entry))
continue;
if (sl->state.insn_idx != insn ||
!same_callsites(&sl->state, cur))
@@ -18816,7 +18816,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
struct bpf_verifier_state_list *sl;
struct bpf_verifier_state *cur = env->cur_state, *new, *loop_entry;
int i, j, n, err, states_cnt = 0;
- bool force_new_state, add_new_state, force_exact;
+ bool force_new_state, add_new_state;
struct list_head *pos, *tmp, *head;
force_new_state = env->test_state_freq || is_force_checkpoint(env, insn_idx) ||
@@ -18996,9 +18996,8 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
loop_entry = get_loop_entry(env, &sl->state);
if (IS_ERR(loop_entry))
return PTR_ERR(loop_entry);
- force_exact = loop_entry && loop_entry->branches > 0;
- if (states_equal(env, &sl->state, cur, force_exact ? RANGE_WITHIN : NOT_EXACT)) {
- if (force_exact)
+ if (states_equal(env, &sl->state, cur, loop_entry ? RANGE_WITHIN : NOT_EXACT)) {
+ if (loop_entry)
update_loop_entry(env, cur, loop_entry);
hit:
sl->hit_cnt++;
--
2.48.1
