NetBSD Problem Report #32198
From www@netbsd.org Wed Nov 30 11:41:58 2005
Return-Path: <www@netbsd.org>
Received: by narn.netbsd.org (Postfix, from userid 31301)
id 51C9963B8C2; Wed, 30 Nov 2005 11:41:58 +0000 (UTC)
Message-Id: <20051130114158.51C9963B8C2@narn.netbsd.org>
Date: Wed, 30 Nov 2005 11:41:58 +0000 (UTC)
From: guy@alum.mit.edu
Reply-To: guy@alum.mit.edu
To: gnats-bugs@netbsd.org
Subject: bpf_validate() needs to do more checks
X-Send-Pr-Version: www-1.0
>Number: 32198
>Category: kern
>Synopsis: bpf_validate() needs to do more checks
>Confidential: no
>Severity: serious
>Priority: medium
>Responsible: rpaulo
>State: closed
>Class: sw-bug
>Submitter-Id: net
>Arrival-Date: Wed Nov 30 11:42:00 +0000 2005
>Closed-Date: Wed Nov 30 23:17:12 +0000 2005
>Last-Modified: Wed Nov 30 23:17:12 +0000 2005
>Originator: Guy Harris
>Release:
>Organization:
>Environment:
>Description:
OpenBSD's bpf_validate() in sys/net/bpf_filter.c does some additional checks to catch:
BPF programs with no instructions or with more than BPF_MAXINSNS instructions;
BPF_STX and BPF_LDX|BPF_MEM instructions that have out-of-range offsets (which could be made to fetch or store into arbitrary memory locations);
BPF_DIV instructions with a constant 0 divisor (that's a check also done at run time).
Here's a patch to make the NetBSD bpf_validate() match it (with some changes to comments; I've submitted the changes to comments to the OpenBSD bug database).
In addition, it makes the "k" field in BPF instructions unsigned, as it is in other BPF interpreters and in libpcap's BPF interpreter.
>How-To-Repeat:
>Fix:
Index: bpf.h
===================================================================
RCS file: /cvsroot/src/sys/net/bpf.h,v
retrieving revision 1.43
diff -u -r1.43 bpf.h
--- bpf.h 4 Aug 2005 19:30:47 -0000 1.43
+++ bpf.h 30 Nov 2005 11:38:44 -0000
@@ -167,7 +167,7 @@
#include <net/dlt.h>
/*
- * The instruction encondings.
+ * The instruction encodings.
*/
/* instruction classes */
#define BPF_CLASS(code) ((code) & 0x07)
@@ -229,7 +229,7 @@
u_int16_t code;
u_char jt;
u_char jf;
- int32_t k;
+ u_int32_t k;
};
/*
Index: bpf_filter.c
===================================================================
RCS file: /cvsroot/src/sys/net/bpf_filter.c,v
retrieving revision 1.21
diff -u -r1.21 bpf_filter.c
--- bpf_filter.c 26 Feb 2005 22:45:09 -0000 1.21
+++ bpf_filter.c 30 Nov 2005 11:38:45 -0000
@@ -82,13 +82,14 @@
} \
}
-static int m_xword __P((struct mbuf *, int, int *));
-static int m_xhalf __P((struct mbuf *, int, int *));
+static int m_xword __P((struct mbuf *, u_int32_t, int *));
+static int m_xhalf __P((struct mbuf *, u_int32_t, int *));
static int
m_xword(m, k, err)
struct mbuf *m;
- int k, *err;
+ u_int32_t k;
+ int *err;
{
int len;
u_char *cp, *np;
@@ -96,7 +97,7 @@
MINDEX(len, m, k);
cp = mtod(m, u_char *) + k;
- if (len - k >= 4) {
+ if (len >= k + 4) {
*err = 0;
return EXTRACT_LONG(cp);
}
@@ -124,7 +125,8 @@
static int
m_xhalf(m, k, err)
struct mbuf *m;
- int k, *err;
+ u_int32_t k;
+ int *err;
{
int len;
u_char *cp;
@@ -132,7 +134,7 @@
MINDEX(len, m, k);
cp = mtod(m, u_char *) + k;
- if (len - k >= 2) {
+ if (len >= k + 2) {
*err = 0;
return EXTRACT_SHORT(cp);
}
@@ -164,7 +166,7 @@
u_int buflen;
{
u_int32_t A, X;
- int k;
+ u_int32_t k;
int32_t mem[BPF_MEMWORDS];
if (pc == 0)
@@ -478,9 +480,10 @@
/*
* Return true if the 'fcode' is a valid filter program.
* The constraints are that each jump be forward and to a valid
- * code. The code must terminate with either an accept or reject.
- * 'valid' is an array for use by the routine (it must be at least
- * 'len' bytes long).
+ * code, that memory accesses are within valid ranges (to the
+ * extent that this can be checked statically; loads of packet
+ * data have to be, and are, also checked at run time), and that
+ * the code terminates with either an accept or reject.
*
* The kernel needs to be able to verify an application's filter code.
* Otherwise, a bogus program could easily crash the system.
@@ -490,40 +493,109 @@
struct bpf_insn *f;
int len;
{
- int i;
+ u_int i, from;
struct bpf_insn *p;
+ if (len < 1 || len > BPF_MAXINSNS)
+ return 0;
+
for (i = 0; i < len; ++i) {
+ p = &f[i];
+ switch (BPF_CLASS(p->code)) {
/*
- * Check that that jumps are forward, and within
- * the code block.
+ * Check that memory operations use valid addresses.
*/
- p = &f[i];
- if (BPF_CLASS(p->code) == BPF_JMP) {
- int from = i + 1;
-
- if (BPF_OP(p->code) == BPF_JA) {
- if ((p->k < 0) ||
- (from + p->k >= len) ||
- (from + p->k < 0))
+ case BPF_LD:
+ case BPF_LDX:
+ switch (BPF_MODE(p->code)) {
+ case BPF_IMM:
+ break;
+ case BPF_ABS:
+ case BPF_IND:
+ case BPF_MSH:
+ /*
+ * More strict check with actual packet length
+ * is done runtime.
+ */
+ if (p->k >= bpf_maxbufsize)
+ return 0;
+ break;
+ case BPF_MEM:
+ if (p->k >= BPF_MEMWORDS)
+ return 0;
+ break;
+ case BPF_LEN:
+ break;
+ default:
+ return 0;
+ }
+ break;
+ case BPF_ST:
+ case BPF_STX:
+ if (p->k >= BPF_MEMWORDS)
+ return 0;
+ break;
+ case BPF_ALU:
+ switch (BPF_OP(p->code)) {
+ case BPF_ADD:
+ case BPF_SUB:
+ case BPF_OR:
+ case BPF_AND:
+ case BPF_LSH:
+ case BPF_RSH:
+ case BPF_NEG:
+ break;
+ case BPF_DIV:
+ /*
+ * Check for constant division by 0.
+ */
+ if (BPF_RVAL(p->code) == BPF_K && p->k == 0)
return 0;
+ default:
+ return 0;
}
- else if (from + p->jt >= len || from + p->jf >= len)
+ break;
+ case BPF_JMP:
+ /*
+ * Check that jumps are within the code block,
+ * and that unconditional branches don't go
+ * backwards as a result of an overflow.
+ * Unconditional branches have a 32-bit offset,
+ * so they could overflow; we check to make
+ * sure they don't. Conditional branches have
+ * an 8-bit offset, and the from address is <=
+ * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
+ * is sufficiently small that adding 255 to it
+ * won't overflow.
+ *
+ * We know that len is <= BPF_MAXINSNS, and we
+ * assume that BPF_MAXINSNS is < the maximum size
+ * of a u_int, so that i + 1 doesn't overflow.
+ */
+ from = i + 1;
+ switch (BPF_OP(p->code)) {
+ case BPF_JA:
+ if (from + p->k < from || from + p->k >= len)
+ return 0;
+ break;
+ case BPF_JEQ:
+ case BPF_JGT:
+ case BPF_JGE:
+ case BPF_JSET:
+ if (from + p->jt >= len || from + p->jf >= len)
+ return 0;
+ break;
+ default:
return 0;
- }
- /*
- * Check that memory operations use valid addresses.
- */
- if ((BPF_CLASS(p->code) == BPF_ST ||
- (BPF_CLASS(p->code) == BPF_LD &&
- (p->code & 0xe0) == BPF_MEM)) &&
- (p->k >= BPF_MEMWORDS || p->k < 0))
- return 0;
- /*
- * Check for constant division by 0.
- */
- if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0)
+ }
+ break;
+ case BPF_RET:
+ break;
+ case BPF_MISC:
+ break;
+ default:
return 0;
+ }
}
return BPF_CLASS(f[len - 1].code) == BPF_RET;
}
>Release-Note:
>Audit-Trail:
Responsible-Changed-From-To: kern-bug-people->rpaulo
Responsible-Changed-By: rpaulo@netbsd.org
Responsible-Changed-When: Wed, 30 Nov 2005 12:04:14 +0000
Responsible-Changed-Why:
let me try to handle it
From: Rui Paulo <rpaulo@netbsd.org>
To: gnats-bugs@netbsd.org
Cc:
Subject: PR/32198 CVS commit: src/sys/net
Date: Wed, 30 Nov 2005 12:54:42 +0000 (UTC)
Module Name: src
Committed By: rpaulo
Date: Wed Nov 30 12:54:42 UTC 2005
Modified Files:
src/sys/net: bpf.h
Log Message:
Fix typo in comment found by Guy Harris (PR 32198).
To generate a diff of this commit:
cvs rdiff -r1.43 -r1.44 src/sys/net/bpf.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
From: Rui Paulo <rpaulo@fnop.net>
To: gnats-bugs@netbsd.org, guy@alum.mit.edu
Cc: kern-bug-people@netbsd.org, gnats-admin@netbsd.org,
netbsd-bugs@netbsd.org
Subject: Re: kern/32198: bpf_validate() needs to do more checks
Date: Wed, 30 Nov 2005 17:16:29 +0000
On 2005.11.30 11:42:00 +0000, guy@alum.mit.edu wrote:
| >Description:
| OpenBSD's bpf_validate() in sys/net/bpf_filter.c does some additional checks to catch:
|
| BPF programs with no instructions or with more than BPF_MAXINSNS instructions;
This is done in bpf_setf();
| BPF_STX and BPF_LDX|BPF_MEM instructions that have out-of-range offsets (which could be made to fetch or store into arbitrary memory locations);
|
| BPF_DIV instructions with a constant 0 divisor (that's a check also done at run time).
What's wrong with the current checks in bpf_validate() ?
-- Rui Paulo
From: Guy Harris <guy@alum.mit.edu>
To: Rui Paulo <rpaulo@fnop.net>
Cc: gnats-bugs@netbsd.org, kern-bug-people@netbsd.org,
gnats-admin@netbsd.org, netbsd-bugs@netbsd.org
Subject: Re: kern/32198: bpf_validate() needs to do more checks
Date: Wed, 30 Nov 2005 10:56:59 -0800
Rui Paulo wrote:
> On 2005.11.30 11:42:00 +0000, guy@alum.mit.edu wrote:
> | >Description:
> | OpenBSD's bpf_validate() in sys/net/bpf_filter.c does some additional checks to catch:
> |
> | BPF programs with no instructions or with more than BPF_MAXINSNS instructions;
>
> This is done in bpf_setf();
>
The check for no instructions isn't - is that check necessary?
> | BPF_STX and BPF_LDX|BPF_MEM instructions that have out-of-range offsets (which could be made to fetch or store into arbitrary memory locations);
> |
> | BPF_DIV instructions with a constant 0 divisor (that's a check also done at run time).
>
> What's wrong with the current checks in bpf_validate() ?
>
If that question applies to both of those items:
For the first item, to quote a message from Dawson Engler:
> we're developing a symbolic execution tool to find bugs in code and it
> seems to have turned up two errors in recent BPF code that appear to
> let filters read/write arbitrary memory. Vern recommended that I ask
> you guys if these were legitimate bugs.
>
> If you have a filter with either:
>
> code == BPF_STX;
> or
> code == BPF_LDX|BPF_MEM;
>
> then from what I can tell with testing bpf_validate forgets to check
> their associated offset stored in field "k" (it does check
> for BPF_ST and BPF_LD but not the *X versions):
>
> * Check that memory operations use valid addresses.
> */
> if ((BPF_CLASS(p->code) == BPF_ST ||
> (BPF_CLASS(p->code) == BPF_LD &&
> (p->code & 0xe0) == BPF_MEM)) &&
> p->k >= BPF_MEMWORDS)
> return 0;
>
> then the interpreter lets you read/write arbitrary offsets off of
> mem:
>
> case BPF_LDX|BPF_MEM:
> X = mem[pc->k];
> continue;
>
> case BPF_STX:
> mem[pc->k] = X;
> continue;
Did he miss something, or is that, indeed, a risk?
For the second item:
The install-time check isn't necessary, but it makes the code more
closely resemble the code in OpenBSD, to make keeping the code in sync
easier.
From: Rui Paulo <rpaulo@fnop.net>
To: Guy Harris <guy@alum.mit.edu>
Cc: gnats-bugs@netbsd.org, kern-bug-people@netbsd.org,
gnats-admin@netbsd.org, netbsd-bugs@netbsd.org
Subject: Re: kern/32198: bpf_validate() needs to do more checks
Date: Wed, 30 Nov 2005 20:00:54 +0000
On 2005.11.30 10:56:59 -0800, Guy Harris wrote:
| Rui Paulo wrote:
| >On 2005.11.30 11:42:00 +0000, guy@alum.mit.edu wrote:
| >| >Description:
| >| OpenBSD's bpf_validate() in sys/net/bpf_filter.c does some additional
| >checks to catch:
| >|
| >| BPF programs with no instructions or with more than BPF_MAXINSNS
| >instructions;
| >
| >This is done in bpf_setf();
| >
| The check for no instructions isn't - is that check necessary?
Ah, it returns EINVAL but still does an out-of-bounds access in
bpf_validate if len < 1...
| >| BPF_STX and BPF_LDX|BPF_MEM instructions that have out-of-range
| >offsets (which could be made to fetch or store into arbitrary memory
| >locations);
| >|
| >| BPF_DIV instructions with a constant 0 divisor (that's a check
| >also done at run time).
| >
| >What's wrong with the current checks in bpf_validate() ?
| >
| If that question applies to both of those items:
|
| For the first item, to quote a message from Dawson Engler:
| >we're developing a symbolic execution tool to find bugs in code and it
| >seems to have turned up two errors in recent BPF code that appear to
| >let filters read/write arbitrary memory. Vern recommended that I ask
| >you guys if these were legitimate bugs.
| >
| >If you have a filter with either:
| >
| > code == BPF_STX;
| > or
| > code == BPF_LDX|BPF_MEM;
| >
| >then from what I can tell with testing bpf_validate forgets to check
| >their associated offset stored in field "k" (it does check
| >for BPF_ST and BPF_LD but not the *X versions):
| >
| > * Check that memory operations use valid addresses.
| > */
| > if ((BPF_CLASS(p->code) == BPF_ST ||
| > (BPF_CLASS(p->code) == BPF_LD &&
| > (p->code & 0xe0) == BPF_MEM)) &&
| > p->k >= BPF_MEMWORDS)
| > return 0;
| >
| >then the interpreter lets you read/write arbitrary offsets off of
| >mem:
| >
| > case BPF_LDX|BPF_MEM:
| > X = mem[pc->k];
| > continue;
| >
| > case BPF_STX:
| > mem[pc->k] = X;
| > continue;
| Did he miss something, or is that, indeed, a risk?
Oh, that's really a problem.
| For the second item:
|
| The install-time check isn't necessary, but it makes the code more
| closely resemble the code in OpenBSD, to make keeping the code in sync
| easier.
IMHO this is not needed and the code already differs from the three
BSDs.
-- Rui Paulo
From: Rui Paulo <rpaulo@netbsd.org>
To: gnats-bugs@netbsd.org
Cc:
Subject: PR/32198 CVS commit: src/sys/net
Date: Wed, 30 Nov 2005 23:14:38 +0000 (UTC)
Module Name: src
Committed By: rpaulo
Date: Wed Nov 30 23:14:38 UTC 2005
Modified Files:
src/sys/net: bpf.h bpf_filter.c
Log Message:
PR 32198: bpf_validate() needs to do more checks, by Guy Harris.
Problems like out-of-bounds read/write in filter machine operations
were fixed.
To generate a diff of this commit:
cvs rdiff -r1.45 -r1.46 src/sys/net/bpf.h
cvs rdiff -r1.23 -r1.24 src/sys/net/bpf_filter.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
State-Changed-From-To: open->closed
State-Changed-By: rpaulo@netbsd.org
State-Changed-When: Wed, 30 Nov 2005 23:17:12 +0000
State-Changed-Why:
After some discussion I decided to commit your patch mainly as-is.
Thanks!
>Unformatted:
(Contact us)
$NetBSD: query-full-pr,v 1.39 2013/11/01 18:47:49 spz Exp $
$NetBSD: gnats_config.sh,v 1.8 2006/05/07 09:23:38 tsutsui Exp $
Copyright © 1994-2007
The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.
Home