Re: More BPF verifier questions

On Fri, Jun 2, 2017 at 7:42 AM, Edward Cree [off-list ref] wrote:

A couple of the tests in tools/testing/selftests/bpf/test_verifier.c seem to be bogus: Test "multiple registers share map_lookup_elem bad reg type" is supposed to
 error with "R3 invalid mem access 'inv'", but from my reading of it, R3 gets
 loaded with a map_value_or_null, that later gets null-checked (both directly
 and - through R0 - indirectly), and finally stored through.  I don't see
 what's supposed to make R3 become a bad pointer.

You are right. In this case,
r0 = bpf_map_lookup
r2 = r0
r3 = r0
r4 = r0
r5 = r0
if (r0 != 0)  <=== condition 1
  r1 = 1
if (r0 != 0)
  r1 = 2
if (r3 != 0)
  *r3 = 0
...

If (r0 != 0) if false, the current verifier marks r2/r3/r4/r5 as unknown value.
I guess here what you did to have precise value 0 helps and make verifier
complaint go away correctly.

Test "helper access to variable memory: stack, bitwise AND + JMP, correct
 bounds" is listed as expected to pass, but it passes zero in the 'size'
 argument, an ARG_CONST_SIZE, to bpf_probe_read; I believe this should fail
 (and with my WIP patch it does).

Probably a typo or mis-statement. "size" is not passed in with "zero", but
with an unknown value. Hence, it probably should fail.

      BPF_MOV64_IMM(BPF_REG_2, 16),
      BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128),
      BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128),
      BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 64),
      BPF_MOV64_IMM(BPF_REG_4, 0),
      BPF_JMP_REG(BPF_JGE, BPF_REG_4, BPF_REG_2, 2),
      BPF_MOV64_IMM(BPF_REG_3, 0),
      BPF_EMIT_CALL(BPF_FUNC_probe_read),


In kernel/bpf/verifier.c,

  } else if (arg_type == ARG_CONST_SIZE ||
       arg_type == ARG_CONST_SIZE_OR_ZERO) {
    expected_type = CONST_IMM;
    /* One exception. Allow UNKNOWN_VALUE registers when the
     * boundaries are known and don't cause unsafe memory accesses
     */
    if (type != UNKNOWN_VALUE && type != expected_type)
      goto err_type;

Maybe somebody can provide some historical context for this relaxation.

On 05/06/17 08:06, Y Song wrote:

On Fri, Jun 2, 2017 at 7:42 AM, Edward Cree [off-list ref] wrote:

quoted

Test "helper access to variable memory: stack, bitwise AND + JMP, correct
 bounds" is listed as expected to pass, but it passes zero in the 'size'
 argument, an ARG_CONST_SIZE, to bpf_probe_read; I believe this should fail
 (and with my WIP patch it does).

Probably a typo or mis-statement. "size" is not passed in with "zero", but
with an unknown value. Hence, it probably should fail.

      BPF_MOV64_IMM(BPF_REG_2, 16),
      BPF_STX_MEM(BPF_DW, BPF_REG_1, BPF_REG_2, -128),
      BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_1, -128),
      BPF_ALU64_IMM(BPF_AND, BPF_REG_2, 64),
      BPF_MOV64_IMM(BPF_REG_4, 0),
      BPF_JMP_REG(BPF_JGE, BPF_REG_4, BPF_REG_2, 2),
      BPF_MOV64_IMM(BPF_REG_3, 0),
      BPF_EMIT_CALL(BPF_FUNC_probe_read),

So, in fact this unknown value is really 16 & 64 == 0, but the verifier doesn't
 know that and concludes that it's either 0 or 64 (after the AND).  But then
 what I didn't spot before, and now have, is that the BPF_JGE tests if 0 >= size.
 Since we're in the false branch, that means size > 0, and so we're fine.
The test case is correct, and now that I've fixed the min/max tracking in my
 patches, the verifier accepts it again.

-Ed