[bpf-next,v1,0/2] bpf: verify scalar ids mapping in regsafe()

Message

Eduard Zingerman May 26, 2023, 6:41 p.m. UTC

Update regsafe() to use check_ids() for scalar values.
Otherwise the following unsafe pattern is accepted by verifier:

  1: r9 = ... some pointer with range X ...
  2: r6 = ... unbound scalar ID=a ...
  3: r7 = ... unbound scalar ID=b ...
  4: if (r6 > r7) goto +1
  5: r6 = r7
  6: if (r6 > X) goto ...
  --- checkpoint ---
  7: r9 += r7
  8: *(u64 *)r9 = Y

See patch #1 for detailed description.

The change has limited impact on verification performance.
Here is veristat log comparing this patch with current master on a set
of selftest binaries listed in tools/testing/selftests/bpf/veristat.cfg
and cilium BPF binaries (see [1]):

$ ./veristat -e file,prog,states -f 'insns_pct>1' -C master-baseline.log current.log
File                      Program                         States (A)  States (B)  States   (DIFF)
------------------------  ------------------------------  ----------  ----------  ---------------
bpf_xdp.o                 tail_handle_nat_fwd_ipv6               648         660     +12 (+1.85%)
bpf_xdp.o                 tail_nodeport_nat_ingress_ipv4         375         455    +80 (+21.33%)
bpf_xdp.o                 tail_rev_nodeport_lb4                  398         472    +74 (+18.59%)
pyperf600_nounroll.bpf.o  on_event                             34169       39465  +5296 (+15.50%)
test_verif_scale1.bpf.o   balancer_ingress                      8636        8942    +306 (+3.54%)
test_verif_scale2.bpf.o   balancer_ingress                      3048        3149    +101 (+3.31%)
test_verif_scale3.bpf.o   balancer_ingress                      8636        8942    +306 (+3.54%)

This was previously posted as an RFC [2].

Changelog:
- RFC -> V1:
  - Function verifier.c:mark_equal_scalars_as_read() is dropped,
    as it was an incorrect fix for problem solved by commit [3].
  - check_ids() is called only for precise scalar values.
  - Test case updated to use inline assembly.

[1] [e-mail]:anakryiko/cilium.git
[2] https://lore.kernel.org/bpf/[e-mail]/
[3] commit 71f656a50176 ("bpf: Fix to preserve reg parent/live fields when copying range info")

Eduard Zingerman (2):
  bpf: verify scalar ids mapping in regsafe() using check_ids()
  selftests/bpf: verify that check_ids() is used for scalars in
    regsafe()

 kernel/bpf/verifier.c                         | 31 +++++++++-
 .../selftests/bpf/prog_tests/verifier.c       |  2 +
 .../selftests/bpf/progs/verifier_scalar_ids.c | 59 +++++++++++++++++++
 3 files changed, 91 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c