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:18:28 -0700
From:   Jakub Kicinski <jakub.kicinski@...ronome.com>
To:     Alexei Starovoitov <ast@...nel.org>
Cc:     <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, 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 ;)