Skip to content

RFC bpf: verify scalar ids mapping in regsafe() using check_ids()

Eduard Zingerman bpf 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest2 patches 4 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/2bpf: verify scalar ids mapping in regsafe() using check_ids()kernel/bpf/verifier.c+85 -24 replies
2/2selftests/bpf: verify that check_ids() is used for scalars in regsafe()tools/testing/selftests/bpf/verifier/scalar_ids.c+61 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [RFC bpf-next 0/2] bpf: verify scalar ids mapping in regsafe() using check_ids()

Currently the following test case is considered safe by the 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 ... ; <-- suppose checkpoint state is created here
7: r9 += r7
8: *(u64 *)r9 = Y

This happens because function regsafe() used (indirectly) form is_state_visited() does not compare id mapping for scalar registers.

The following patch makes two chages:
- regsafe() is updated to use check_ids() for scalar registers;
- registers that obtain their range via find_equal_scalars() are marked as read in the parent checkpoint states. See mark_equal_scalars_as_read() for detailed explanation.

However, I'm not sure if mark_equal_scalars_as_read() is sufficient or mark_chain_precision() should be called / updated as well.

In current form the patch does not have a big impact on the tests verification time, as checked on BPF object files listed in tools/testing/selftests/bpf/veristat.cfg and Cilium object files obtained from [1]:

./veristat -e file,prog,insns,states -f 'insns_diff!=0' -C master.log current.log

File         Program                  Insns (A)  Insns (B)  Insns    (DIFF)  States (A)  States (B)  States (DIFF)
-----------  -----------------------  ---------  ---------  ---------------  ----------  ----------  -------------
bpf_host.o   cil_from_host                  556        603     +47 (+8.45%)          37          41   +4 (+10.81%)
bpf_xdp.o    tail_lb_ipv4                 77248      77302     +54 (+0.07%)        4643        4646    +3 (+0.06%)
loop6.bpf.o  trace_virtqueue_add_sgs      15144      18594  +3450 (+22.78%)         337         403  +66 (+19.58%)

A tweak adding !tnum_is_const(src_reg->var_off) in check_alu_op() is necessary to achieve this.

[1] [email protected]:anakryiko/cilium.git

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                         | 87 ++++++++++++++++++-
 .../selftests/bpf/verifier/scalar_ids.c       | 61 +++++++++++++
 2 files changed, 146 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/scalar_ids.c
Signature · 1 line
2.34.1