netdev - Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func

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: <0c879399-ec66-938f-b49e-58dffb6a705e@solarflare.com>
Date:   Thu, 5 Apr 2018 09:49:40 +0100
From:   Edward Cree <ecree@...arflare.com>
To:     Alexei Starovoitov <alexei.starovoitov@...il.com>
CC:     Daniel Borkmann <daniel@...earbox.net>, <netdev@...r.kernel.org>
Subject: Re: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call
 simplifications

On 05/04/18 06:28, Alexei Starovoitov wrote:
> On Thu, Apr 05, 2018 at 12:58:46AM +0100, Edward Cree wrote:
>> On 04/04/18 00:37, Alexei Starovoitov wrote:
>>> hmm. that doesn't fail for me and any other bots didn't complain.
>>> Are you sure you're running the latest kernel and tests?
>> Ah, test_progs isn't actually rebuilding because __NR_bpf is undeclared;
>>  something must be going wrong with header files.
>> Never mind.
>>
>>> hmm. what's wrong with bsearch? It's trivial and fast. 
>> bsearch is O(log n), and the sort() call on the subprog_starts (which happens
>>  every time add_subprog() is called) is O(n log n).
>> Whereas reading aux->subprogno is O(1).
>> As far as I'm concerned, that's a sign that the latter data structure is the
>>  appropriate one.
> only if it can be done as separate _first_ pass before cfg.
As I think I already said, I'm working on a next version of the patch that
 does just that.

> No. It's worse. Your proposed approach to bounded loops completely
> relying on 'explore all paths' whereas John's does not.
> Can 'explore all paths' work with 1M bpf insns? No.
> Whereas an approach that builds dom graph, detects natural loops
> and loop invariants - can.
... IF it's possible at all, which I'm still doubtful about.

> This sounds like arbitrary assumptions what this new approach would do.
> Instead of rejecting it outright try to solve this very hard problem.
I'm not rejecting it outright; I'm just saying, be prepared for the possibility
 that it can't be solved, and try to leave a line of retreat / have a plan B in
 the case that it proves to be subject to a no-free-lunch theorem.  Because my
 intuition is that an entropy argument may require all algos to have the same
 superexponential worst-case running time as 'explore all paths' does.

> Before this discussion gets carried away too far let's get back to this patch set.
> Having seen all arguments I still think that only patch 3 is worth pursuing further.
I think the next version of the patch series (coming real soon now) answers at
 least most of your objections (and indeed the above debate isn't relevant to it).