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
| ||
|
Date: Mon, 29 Sep 2014 18:50:00 -0700 From: Alexei Starovoitov <ast@...mgrid.com> To: "David S. Miller" <davem@...emloft.net> Cc: Ingo Molnar <mingo@...nel.org>, Linus Torvalds <torvalds@...ux-foundation.org>, Andy Lutomirski <luto@...capital.net>, Daniel Borkmann <dborkman@...hat.com>, Hannes Frederic Sowa <hannes@...essinduktion.org>, Chema Gonzalez <chema@...gle.com>, Eric Dumazet <edumazet@...gle.com>, Peter Zijlstra <a.p.zijlstra@...llo.nl>, Pablo Neira Ayuso <pablo@...filter.org>, "H. Peter Anvin" <hpa@...or.com>, Andrew Morton <akpm@...ux-foundation.org>, Kees Cook <keescook@...omium.org>, netdev@...r.kernel.org, linux-kernel@...r.kernel.org Subject: [PATCH net-next 0/2] bpf: add search pruning optimization and tests Hi All, patch #1 commit log explains why eBPF verifier has to examine some instructions multiple times and describes the search pruning optimization that improves verification speed for branchy programs and allows more complex programs to be verified successfully. This patch completes the core verifier logic. patch #2 adds more verifier tests related to branches and search pruning I'm still working on Andy's 'bitmask for stack slots' suggestion. It will be done on top of this patch. The current verifier algorithm is brute force depth first search with state pruning. If anyone can come up with another algorithm that demonstrates better results, we'll replace the algorithm without affecting user space. Note verifier doesn't guarantee that all possible valid programs are accepted. Overly complex programs may still be rejected. Verifier improvements/optimizations will guarantee that if a program was passing verification in the past, it will still be passing. Alexei Starovoitov (2): bpf: add search pruning optimization to verifier bpf: add tests to verifier testsuite kernel/bpf/verifier.c | 146 +++++++++++++++++++++++++++++++++++++++++++ samples/bpf/test_verifier.c | 130 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 276 insertions(+) -- 1.7.9.5 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists