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

[Eduard Zingerman <eddyz87@gmail.com>]

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@github.com: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