netdev - Re: [PATCH net-next v2 8/9] net: filter: rework/optimize internal BPF interpreter's instruction set

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:	Tue, 25 Mar 2014 18:58:14 -0700
From:	Alexei Starovoitov <ast@...mgrid.com>
To:	David Miller <davem@...emloft.net>
Cc:	hpa@...ux.intel.com, Daniel Borkmann <dborkman@...hat.com>,
	Network Development <netdev@...r.kernel.org>,
	Hagen Paul Pfeifer <hagen@...u.net>,
	Kees Cook <keescook@...omium.org>, pmoore@...hat.com,
	Ingo Molnar <mingo@...nel.org>,
	LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH net-next v2 8/9] net: filter: rework/optimize internal BPF
 interpreter's instruction set

On Tue, Mar 25, 2014 at 5:46 PM, David Miller <davem@...emloft.net> wrote:
> From: "H. Peter Anvin" <hpa@...ux.intel.com>
> Date: Tue, 25 Mar 2014 17:24:27 -0700
>
>> If you allow loops, it greatly increases the expressibility of the
>> language, but we would really need another control to limit CPU usage.
>
> We don't want super expressibility.
>
> We want an extremely simple, trivial to validate, filtering language.

Filtering language is unchanged. It's still the same classic BPF
and in this patch set all jumps are forward only.
We didn't touch sk_chk_filter(), so it's allowing forward only jumps.
Classic bpf and ebpf instruction sets can accommodate both.
It's bpf verifier (sk_chk_filter) that allows one or the other.

So I think we can debate backward jumps later when they actually
will be up for review.

I think we can allow backward jumps in the future, since it helps
llvm/gcc to generate more efficient code, reduce code duplication, etc
Extended bpf verifier is still simple enough and it detects loops
by doing DAG check.
See check_cfg() that was part of V1 series.
The DAG check is from the wikipedia. It's looking for a back-edge.
If back-edge is present, it means loop is possible, so whole ebpf
program is thrown out.
I think even classic BPF requires DAG check,
since today sk_chk_filter() allows unreachable instructions,
so attacker can write a bpf program that jumps over junk instructions.
I cannot imagine how this little hole can be exploited, but I think
it's safer to close it.
So we're planning to send patches to close this 10 year old
hole in the future series.

After extended verifier is reviewed and it still feels wrong, we can
make it more restrictive and disallow backward jumps, but that
will complicate llvm/gcc.

Thanks
Alexei
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html