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] git@xxxxxxxxxx: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
--
2.34.1
