[bpf,00/12] verify callbacks as if they are called unknown number of times

Message

Eduard Zingerman Nov. 16, 2023, 2:17 a.m. UTC

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=[e-mail]/
[1] https://lore.kernel.org/bpf/[e-mail]/
[2] [e-mail]: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