[DTrace-devel] BPF verifier issues with conditional branches

[Kris Van Hees]

Here are two issues I have found.  I am adding them into the BPF-ISSUES file
in the source tree (which incidentally needs to be cleaned up quite a bit)
but I wanted to mention them here also.

Submitting kernel patches for these could be a useful contribution.

- The BPF verifier does not handle branch prediction and value range tracking
  correctly for conditional branches that perform a comparison between two
  registers where the src register hold a value ramge and the dst register
  holds a constant value.  It should handle that similar to when the src
  register holds the constant value.  One way to implement this is to use the
  flip_opcode() function along with switching src and dst so that the actual
  work can still be done using is_branch_taken().

- The BPF verifier does not update value range information when a conditional
  branch between two registers is encountered where both registers hold a value
  range.  This should be possible because the condition does provide
  information for the two possible outcomes.

  E.g. R3=invP(id=5,umin_value=1,umax_value=4294967295,
               var_off=(0x0; 0xffffffff))
       R6=invP(id=8,umax_value=256,var_off=(0x0; 0xffffffff))

       jle  %r6, %r3, <delta>

  This comparison could update the value ranges as follows:

       TRUE:  (No change)
       FALSE: R3=invP(id=5,umin_value=1,umax_value=255,
                      var_off=(0x0; 0xffffffff))
              R6=invP(id=8,umax_value=256,var_off=(0x0; 0xffffffff))