netdev - Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

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 for Android: free password hash cracker in your pocket

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

Message-ID: <788035e1-1974-b48e-3008-d294194a8b05@solarflare.com>
Date:   Wed, 28 Jun 2017 15:11:32 +0100
From:   Edward Cree <ecree@...arflare.com>
To:     Daniel Borkmann <daniel@...earbox.net>, <davem@...emloft.net>,
        "Alexei Starovoitov" <alexei.starovoitov@...il.com>,
        Alexei Starovoitov <ast@...com>
CC:     <netdev@...r.kernel.org>, <linux-kernel@...r.kernel.org>,
        iovisor-dev <iovisor-dev@...ts.iovisor.org>
Subject: Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

On 28/06/17 14:50, Daniel Borkmann wrote:
> Hi Edward,
>
> Did you also have a chance in the meantime to look at reducing complexity
> along with your unification? I did run the cilium test suite with your
> latest set from here and current # worst case processed insns that
> verifier has to go through for cilium progs increases from ~53k we have
> right now to ~76k. I'm a bit worried that this quickly gets us close to
> the upper ~98k max limit starting to reject programs again. Alternative
> is to bump the complexity limit again in near future once run into it,
> but preferably there's a way to optimize it along with the rewrite? Do
> you see any possibilities worth exploring? 
The trouble, I think, is that as we're now tracking more information about
 each register value, we're less able to prune branches.  But often that
 information is not actually being used in reaching the exit state.  So it
 seems like the way to tackle this would be to track what information is
 used — or at least, which registers are read from (including e.g. writing
 through them or passing them to helper calls) — in reaching a safe state.
 Then only registers which are used are required to match for pruning.
But that tracking would presumably have to propagate backwards through the
 verifier stack, and I'm not sure how easily that could be done.  Someone
 (was it you?) was talking about replacing the current DAG walking and
 pruning with some kind of basic-block thing, which would help with this.
Summary: I think it could be done, but I haven't looked into the details
 of implementation yet; if it's not actually breaking your programs (yet),
 maybe leave it for a followup patch series?

-Ed