bpf_validate() needs to do more checks

[Guy Harris]

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 DragonFly BSD bpf_validate() match it.

*** bpf_filter.c	Tue Jan  1 18:57:43 2008
--- bpf_filter.c.VALIDATE	Tue Jan  1 19:00:15 2008
***************
*** 498,505 ****
  #ifdef _KERNEL
  /*
   * Return true if the 'fcode' is a valid filter program.
!  * The constraints are that jump and memory accesses are within valid
!  * ranges, 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.
--- 498,508 ----
  #ifdef _KERNEL
  /*
   * Return true if the 'fcode' is a valid filter program.
!  * The constraints are that each jump be forward and to a valid
!  * 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.
***************
*** 507,544 ****
  int
  bpf_validate(const struct bpf_insn *f, int len)
  {
! 	int i;
  	const struct bpf_insn *p;
  	for (i = 0; i < len; ++i) {
  		/*
! 		 * Check that that jumps are within the code block.
  		 */
! 		p = &f[i];
! 		if (BPF_CLASS(p->code) == BPF_JMP) {
! 			int from = i + 1;
!
! 			if (BPF_OP(p->code) == BPF_JA) {
! 				if (from >= len || p->k >= len - from)
  					return 0;
  			}
! 			else if (from >= len || p->jt >= len - from ||
! 				 p->jf >= len - from)
  				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)
! 			return 0;
! 		/*
! 		 * Check for constant division by 0.
! 		 */
! 		if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0)
  			return 0;
  	}
  	return BPF_CLASS(f[len - 1].code) == BPF_RET;
  }
--- 510,620 ----
  int
  bpf_validate(const struct bpf_insn *f, int len)
  {
! 	u_int i, from;
  	const 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 memory operations use valid addresses.
  		 */
! 		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_MUL:
! 			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;
! 				break;
! 			default:
! 				return 0;
! 			}
! 			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;
! 			}
! 			break;
! 		case BPF_RET:
! 			break;
! 		case BPF_MISC:
! 			break;
! 		default:
  			return 0;
+ 		}
  	}
  	return BPF_CLASS(f[len - 1].code) == BPF_RET;
  }