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: <5841CE97.3050302@gmail.com>
Date:   Fri, 2 Dec 2016 11:42:15 -0800
From:   John Fastabend <john.fastabend@...il.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 16-12-02 11:25 AM, Hannes Frederic Sowa wrote:
> Hi,
> 
> On 02.12.2016 19:39, Alexei Starovoitov wrote:
>> On Thu, Dec 01, 2016 at 10:27:12PM +0100, Hannes Frederic Sowa wrote:
>>> like") and the problematic of parsing DNS packets in XDP due to string
>>> processing and looping inside eBPF.
>>
>> Hannes,
>> Not too long ago you proposed a very interesting idea to add
>> support for bounded loops without adding any new bpf instructions and
>> changing llvm (which was way better than my 'rep' like instructions
>> I was experimenting with). I thought systemtap guys also wanted bounded
>> loops and you were cooperating on the design, so I gave up on my work and
>> was expecting an imminent patch from you. I guess it sounds like you know
>> believe that bounded loops are impossible or I misunderstand your statement ?
> 
> Your argument was that it would need a new verifier as the current first
> pass checks that we indeed can lay out the basic blocks as a DAG which
> the second pass depends on. This would be violated.
> 
> Because eBPF is available by non privileged users this would need a lot
> of effort to rewrite and verify (or indeed keep two verifiers in the
> kernel for priv and non-priv). The verifier itself is exposed to
> unprivileged users.

I missed this. Why the need for two verifiers?

> 
> Also, by design, if we keep the current limits, this would not give you
> more instructions to operate on compared to the flattened version of the
> program, it would merely reduce the numbers of optimizations in LLVM
> that let the verifier reject the program.
> 
> Only enabling the relaxed verifier for root users seemed thus being
> problematic as programs wouldn't be portable between nonprivileged and
> privileged users.

Still a bit lost what does the relaxed verifier provide here?

> 
>> As far as pattern search for DNS packets...
>> it was requested by Cloudflare guys back in March:
>> https://github.com/iovisor/bcc/issues/471
>> and it is useful for several tracing use cases as well.
>> Unfortunately no one had time to implement it yet.
> 
> The string operations you proposed on the other hand, which would count
> as one eBPF instructions, would give a lot more flexibility and allow
> more cycles to burn, but don't help parsing binary protocols like IPv6
> extension headers.

My rough thinking on this was the verifier had to start looking for loop
invariants and to guarantee termination. Sounds scary in general but
LLVM could put these in some normal form for us and the verifier could
only accept decreasing loops, the invariants could be required to be
integers, etc. By simplifying the loop enough the problem becomes
tractable.

I think this would be better than new instructions and/or multiple
verifiers.

.John

> 
> Bye,
> Hannes
>