netdev - Re: [RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

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] [day] [month] [year] [list]

Date:   Tue, 13 Feb 2018 23:30:52 +0000
From:   Jiong Wang <jiong.wang@...ronome.com>
To:     John Fastabend <john.fastabend@...il.com>
Cc:     Edward Cree <ecree@...arflare.com>,
        Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>, netdev@...r.kernel.org
Subject: Re: [RFC PATCH bpf-next 0/2] bpf/verifier: simplify subprog tracking

On 13/02/2018 05:09, John Fastabend wrote:
> To find these we do the following
>     1.a: Build the CFG of all the instructions so we can walk around the
>          program easily.
>     1.b: Find the basic blocks and build the basic block CFG. After this
>          with a few helper calls we can move around the CFG both at block
>          level and insn level.
>     1.c: Build the dom tree and post dom tree. This is a data structure that
>          allows us to actually find the natural loops. I can write more about
>          this later.
>     1.d: Using the post dom tree verify all the CFG loops are in fact
>          natural loops. I made some simplifications here and threw
>          out loops that have multiple jumps to the header node and nested
>          loops for now. Both can be handled with some additional complexity.
>
>    Versions of the above can be found in gcc and llvm so it appears to be
>    fairly regular stuff from the compiler side. For LLVM the passes are
>    --loops, --postdomtree. I dumped the various CFG into dot format and
>    and graphed them for fun.

This part of work are very interesting. It will be very helpful if these CFG
information are kept even after verification pass finished, or if the storage
overhead is a concern, made into reusable functions.

I plan to implement similar graph dump in bpftool, i.e. be able to dump eBPF
CFG into .dot graph and color the graph according to some simple static analysis,
these exactly need such CFG information.

Regards,
Jiong