netdev - Re: bpf bounded loops. Was: [flamebait] xdp

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: <aafa452d-26dd-d58b-2649-21ccce9370a4@solarflare.com>
Date:   Mon, 5 Dec 2016 16:54:06 +0000
From:   Edward Cree <ecree@...arflare.com>
To:     Hannes Frederic Sowa <hannes@...essinduktion.org>,
        Alexei Starovoitov <alexei.starovoitov@...il.com>
CC:     Tom Herbert <tom@...bertland.com>, Thomas Graf <tgraf@...g.ch>,
        Linux Kernel Network Developers <netdev@...r.kernel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        "David S. Miller" <davem@...emloft.net>
Subject: Re: bpf bounded loops. Was: [flamebait] xdp

On 05/12/16 16:50, Hannes Frederic Sowa wrote:
> On 05.12.2016 17:40, Edward Cree wrote:
>> I may be completely mistaken here, but can't the verifier unroll the loop 'for
>> verification' without it actually being unrolled in the program?
>> I.e., any "proof that the loop terminates" should translate into "rewrite of
>> the directed graph to make it a DAG, possibly duplicating a lot of insns", and
>> you feed the rewritten graph to the verifier, while using the original loopy
>> version as the actual program to store and later execute.
>> Then the verifier happily checks things like array indices being valid, without
>> having to know about the bounded loops.
> That is what is already happening. E.g. __builtin_memset is expanded up
> to 128 rounds (which is a lot) but at some point llvm doesn't do enoug
> unrolling of that.
>
> The BPF target configures that in
> http://llvm.org/docs/doxygen/html/BPFISelLowering_8cpp_source.html on
> line 166-169.
I think you're talking about the _compiler_ unrolling loops before it
submits the program to the kernel.  I'm talking about having the _verifier_
unroll them, so that we can execute the original (non-unrolled) version.
Or am I misunderstanding?

-Ed