>Number:         32198
>Category:       kern
>Synopsis:       bpf_validate() needs to do more checks
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    kern-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Wed Nov 30 11:42:00 +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;
 }