This series updates verifier logic for callback functions handling.
Current master simulates callback body execution exactly once,
which leads to verifier not detecting unsafe programs like below:
static int unsafe_on_zero_iter_cb(__u32 idx, struct num_context *ctx)
{
ctx->i = 0;
return 0;
}
SEC("?raw_tp")
int unsafe_on_zero_iter(void *unused)
{
struct num_context loop_ctx = { .i = 32 };
__u8 choice_arr[2] = { 0, 1 };
bpf_loop(100, unsafe_on_zero_iter_cb, &loop_ctx, 0);
return choice_arr[loop_ctx.i];
}
This was reported previously in [0].
The basic idea of the fix is to schedule callback entry state for
verification in env->head until some identical, previously visited
state in current DFS state traversal is found. Same logic as with open
coded iterators, and builds on top recent fixes [1] for those.
The series is structured as follows:
- patches #1,2,3 update strobemeta, xdp_synproxy selftests and
bpf_loop_bench benchmark to allow convergence of the bpf_loop
callback states;
- patches #4,5 just shuffle the code a bit;
- patch #6 is the main part of the series;
- patch #7 adds test cases for #6;
- patch #8 extend patch #6 with same speculative scalar widening
logic, as used for open coded iterators;
- patch #9 adds test cases for #8;
- patch #10 extends patch #6 to track maximal number of callback
executions specifically for bpf_loop();
- patch #11 extends test_load based tests infra with __not_msg() macro;
- patch #12 adds test cases for #10 (and uses __not_msg() from #11).
Veristat results comparing this series to master+patches #1,2,3 using selftests
show the following difference:
File Program States (A) States (B) States (DIFF)
------------------------- ------------- ---------- ---------- -------------
bpf_loop_bench.bpf.o benchmark 1 2 +1 (+100.00%)
pyperf600_bpf_loop.bpf.o on_event 136 219 +83 (+61.03%)
strobemeta_bpf_loop.bpf.o on_event 113 152 +39 (+34.51%)
xdp_synproxy_kern.bpf.o syncookie_tc 341 298 -43 (-12.61%)
xdp_synproxy_kern.bpf.o syncookie_xdp 344 301 -43 (-12.50%)
Veristat results comparing this series to master using Tetragon BPF
files [2] also show some differences.
States diff varies from +2% to +15% on 23 programs out of 186,
no new failures.
[0] https://lore.kernel.org/bpf/CA+vRuzPChFNXmouzGG+wsy=6eMcfr1mFG0F3g7rbg-sedGKW3w@xxxxxxxxxxxxxx/
[1] https://lore.kernel.org/bpf/20231024000917.12153-1-eddyz87@xxxxxxxxx/
[2] git@xxxxxxxxxx:cilium/tetragon.git
Eduard Zingerman (12):
selftests/bpf: track tcp payload offset as scalar in xdp_synproxy
selftests/bpf: track string payload offset as scalar in strobemeta
selftests/bpf: fix bpf_loop_bench for new callback verification scheme
bpf: extract __check_reg_arg() utility function
bpf: extract setup_func_entry() utility function
bpf: verify callbacks as if they are called unknown number of times
selftests/bpf: tests for iterating callbacks
bpf: widening for callback iterators
selftests/bpf: test widening for iterating callbacks
bpf: keep track of max number of bpf_loop callback iterations
selftests/bpf: add __not_msg annotation for test_loader based tests
selftests/bpf: check if max number of bpf_loop iterations is tracked
include/linux/bpf_verifier.h | 14 +
kernel/bpf/verifier.c | 381 ++++++++++++------
.../selftests/bpf/prog_tests/cb_refs.c | 4 +-
.../selftests/bpf/prog_tests/verifier.c | 2 +
.../selftests/bpf/progs/bpf_loop_bench.c | 13 +-
tools/testing/selftests/bpf/progs/bpf_misc.h | 9 +
tools/testing/selftests/bpf/progs/cb_refs.c | 1 +
.../selftests/bpf/progs/exceptions_fail.c | 2 +
.../testing/selftests/bpf/progs/strobemeta.h | 78 ++--
.../bpf/progs/verifier_iterating_callbacks.c | 234 +++++++++++
.../bpf/progs/verifier_subprog_precision.c | 22 +-
.../selftests/bpf/progs/xdp_synproxy_kern.c | 84 ++--
tools/testing/selftests/bpf/test_loader.c | 82 ++--
13 files changed, 691 insertions(+), 235 deletions(-)
create mode 100644 tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
--
2.42.0
