netdev - Re: [PATCH bpf-next] bpf: relax verifier restriction on BPF_MOV

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <b4d7355e-95c8-f0a1-6933-ef4b1be9da57@netronome.com>
Date:   Wed, 5 Dec 2018 17:38:19 +0000
From:   Jiong Wang <jiong.wang@...ronome.com>
To:     Edward Cree <ecree@...arflare.com>, ast@...nel.org,
        daniel@...earbox.net
Cc:     netdev@...r.kernel.org, oss-drivers@...ronome.com
Subject: Re: [PATCH bpf-next] bpf: relax verifier restriction on BPF_MOV |
 BPF_ALU

On 05/12/2018 15:32, Jiong Wang wrote:
> On 05/12/2018 14:52, Edward Cree wrote:
>> On 05/12/18 09:46, Jiong Wang wrote:
>>> There is NO processed instruction number regression, either with or 
>>> without
>>> -mattr=+alu32.
>> <snip>
>>> Cilium bpf
>>> ===
>>> bpf_lb-DLB_L3.o         2110/2110    1730/1733
>> That looks like a regression of 3 insns in the 32-bit case.
>> May be worth investigating why.
>
> Will look into this.
>
Got some analysis from trace log, making a register contains accurate
integer could affect both path skip (conditional jump with immediate)
and path prune, details described below.

But I want to emphasis before this patch, turning a constant into unknown
could potentially causing verifier rejecting valid programs.

For example, for test_l4lb_noinline.c, there is the following code:

     struct real_definition *dst

1:  if (!get_packet_dst(&dst, &pckt, vip_info, is_ipv6))
2:    return TC_ACT_SHOT;
3:
4:  if (dst->flags & F_IPV6) {

get_packet_dst is responsible for initialize dst into valid pointer and
return true (1), otherwise return false (0).

As described in the patch description, the return sequence using alu32
will be:

   412: (54) (u32) r7 &= (u32) 1
   413: (bc) (u32) r0 = (u32) r7
   414: (95) exit

which would turn r0 into unknown value for all cases.

This is causing trouble when the code path hasn't initialized dst inside
get_packet_dst, for which case 0 is returned, and we would expect verifer
to skip the fall through path at C code line 4, otherwise it will complain
dst is not a pointer and will reject the program.

For why there are 3 more processed insn under -mattr=+alu32 for bpf_lb.o,
there are two places where verification logic diverges:

One is the following pattern:

  475: (bc) (u32) r1 = (u32) r7
  ...
  478: (55) if r1 != 0x7 goto pc+23
  ...

r1 gets its value from r7 which could be one of three different integer
0, 7, -157 when reached here.

Before this patch, insn 475 will make r1 into unknown while the integer
value is preserved after this patch.

So, if r1 is with value other than 0x7, the fall through path is skipped
after this patch.

But before the patch, after insn 478, verifier could also fix the value
of r1 into constant 0x7, and could do path prune for another path reaching
insn 478 if state comparison is safe.

 From the trace log, preserve r1's integer value wins here, path skipped
are more than path pruned, so after this patch, get fewer processed insn
for this part of sequence.

However there are another pattern:

  360: (bc) (u32) r7 = (u32) r1
  361: (05) goto pc+74
  436: (bc) (u32) r1 = (u32) r7
  437: (67) r1 <<= 32
  438: (c7) r1 s>>= 32

For this case, one more path prune happened when r7 is unknown value and
the pruned path is a long one which caused the total processed insn number
become 3 more.