netdev - Re: [RFC PATCH bpf-next 05/12] bpf/verifier: detect loops dynamically rather than statically

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]

Date:   Fri, 23 Feb 2018 14:27:03 -0800
From:   John Fastabend <john.fastabend@...il.com>
To:     Edward Cree <ecree@...arflare.com>,
        netdev <netdev@...r.kernel.org>,
        Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>
Subject: Re: [RFC PATCH bpf-next 05/12] bpf/verifier: detect loops dynamically
 rather than statically

On 02/23/2018 09:40 AM, Edward Cree wrote:
> Add in a new chain of parent states, which does not cross function-call
>  boundaries, and check whether our current insn_idx appears anywhere in
>  the chain.  Since all jump targets have state-list marks (now placed
>  by prepare_cfg_marks(), which replaces check_cfg()), it suffices to
>  thread this chain through the existing explored_states and check it
>  only in is_state_visited().
> By using this parent-state chain to detect loops, we open up the
>  possibility that in future we could determine a loop to be bounded and
>  thus accept it.
> A few selftests had to be changed to ensure that all the insns walked
>  before reaching the back-edge are valid.
> 

I still believe this needs to be done in an initial pass where we can
build a proper CFG and analyze the loops to ensure we have loops that
can be properly verified. Otherwise we end up trying to handle all the
special cases later like the comment in patch 7/12 'three-jump trick'.
So rather than try to handle all loops only handle "normal" loops. In
an early CFG stage with DOM tree the algorithm for this is already
used by gcc/clang so there is good precedent for this type of work.

Without this we are open to other "clever" goto programs that create
loops that we have to special case. Better to just reject all these
classes of loops because most users will never need them.

See more notes in 7/12 patch, sorry I've been busy and not had a chance
to push code to build cfg and dom tree yet.

Also case analysis in patch description describing types of loops
this handles (either here or in another patch) would help me understand
at least.

> Signed-off-by: Edward Cree <ecree@...arflare.com>
> ---
>  include/linux/bpf_verifier.h                |   2 +
>  kernel/bpf/verifier.c                       | 280 +++++++++-------------------
>  tools/testing/selftests/bpf/test_verifier.c |  12 +-
>  3 files changed, 97 insertions(+), 197 deletions(-)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 0bc49c768585..24ddbc1ed3b2 100644
>