netdev - [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func

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

Message-ID: <d13f6b60-3632-3e4d-111a-2edb4198b473@solarflare.com>
Date:   Thu, 29 Mar 2018 23:44:17 +0100
From:   Edward Cree <ecree@...arflare.com>
To:     Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Daniel Borkmann <daniel@...earbox.net>
CC:     <netdev@...r.kernel.org>
Subject: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call
 simplifications

By storing subprog boundaries as a subprogno mark on each insn, rather than
 a start (and implicit end) for each subprog, we collect a number of gains:
* More efficient determination of which subprog contains a given insn, and
  thus of find_subprog (which subprog begins at a given insn).
* Number of verifier "full recursive walk" passes is reduced, since most of
  the work is done in the main insn walk (do_check()).  Leftover work in
  other passes is mostly linear scans (O(insn_cnt)) or, in the case of
  check_max_stack_depth(), a topological sort (O(subprog_cnt)).

Some other changes were also included to support this:
* Per-subprog info is stored in env->subprog_info, an array of structs,
  rather than several arrays with a common index.
* Call graph is now stored in the new bpf_subprog_info struct; used here
  for check_max_stack_depth() but may have other uses too.

Along with this, patch #3 puts parent pointers (used by liveness analysis)
 in the registers instead of the func_state or verifier_state, so that we
 don't need skip_callee() machinery.  This also does the right thing for
 stack slots, so they don't need their own special handling for liveness
 marking either.

Edward Cree (3):
  bpf/verifier: validate func_calls by marking at do_check() time
  bpf/verifier: update selftests
  bpf/verifier: per-register parent pointers

 include/linux/bpf_verifier.h                |  32 +-
 kernel/bpf/verifier.c                       | 631 +++++++++++++---------------
 tools/testing/selftests/bpf/test_verifier.c |  51 ++-
 3 files changed, 344 insertions(+), 370 deletions(-)