netdev - Re: [PATCH bpf-next 0/7] bpf: improve verifier scalability

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]

Date:   Fri, 29 Mar 2019 20:35:16 -0700
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Jakub Kicinski <jakub.kicinski@...ronome.com>
Cc:     Alexei Starovoitov <ast@...nel.org>, davem@...emloft.net,
        daniel@...earbox.net, jannh@...gle.com, netdev@...r.kernel.org,
        bpf@...r.kernel.org, kernel-team@...com
Subject: Re: [PATCH bpf-next 0/7] bpf: improve verifier scalability

On Fri, Mar 29, 2019 at 08:18:28PM -0700, Jakub Kicinski wrote:
> On Fri, 29 Mar 2019 17:16:05 -0700, Alexei Starovoitov wrote:
> > Realize two key ideas to speed up verification speed by ~20 times
> > 1. every 'branching' instructions records all verifier states.
> >    not all of them are useful for search pruning.
> >    add a simple heuristic to keep states that were successful in search pruning
> >    and remove those that were not
> > 2. mark_reg_read walks parentage chain of registers to mark parents as LIVE_READ.
> >    Once the register is marked there is no need to remark it again in the future.
> >    Hence stop walking the chain once first LIVE_READ is seen.
> > 
> > 1st optimization gives 10x speed up on large programs
> > and 2nd optimization reduces the cost of mark_reg_read from ~40% of cpu to <1%.
> > Combined the deliver ~20x speedup on large programs.
> > 
> > Faster and bounded verification time allows to increase insn_processed
> > limit to 1 million from 130k.
> > 
> > Worst case it takes 1/10 of a second to process that many instructions
> > and peak memory consumption is peak_states * sizeof(struct bpf_verifier_state)
> > which is around ~5Mbyte.
> > 
> > Increase insn_per_program limit for root to insn_processed limit.
> > 
> > Add verification stats and stress tests for verifier scalability.
> > 
> > This patch set is the first step to be able to accept large programs.
> > The verifier still suffers from its brute force algorithm and
> > large programs can easily hit 1M insn_processed limit.
> > A lot more work is necessary to be able to verify large programs.
> 
> Very nice!
> 
> Hopefully this doesn't discourage people from working on loops ;)

Definitely not :) we desperately need loops.
llvm performs 'pragma unroll' only for relatively small loop counts.
Walking stack traces still not possible.
In the test from patch 7 doing jhash() over 64-bytes will not work,
because llvm will generate a loop ignoring pragma unroll.