xref: /illumos-gate/usr/src/uts/common/io/bpf/bpf_filter.c (revision 0a0e9771ca0211c15f3ac4466b661c145feeb9e4)
1 /*	$NetBSD: bpf_filter.c,v 1.35 2008/08/20 13:01:54 joerg Exp $	*/
2 
3 /*
4  * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997
5  *	The Regents of the University of California.  All rights reserved.
6  *
7  * This code is derived from the Stanford/CMU enet packet filter,
8  * (net/enet.c) distributed as part of 4.3BSD, and code contributed
9  * to Berkeley by Steven McCanne and Van Jacobson both of Lawrence
10  * Berkeley Laboratory.
11  *
12  * Redistribution and use in source and binary forms, with or without
13  * modification, are permitted provided that the following conditions
14  * are met:
15  * 1. Redistributions of source code must retain the above copyright
16  *    notice, this list of conditions and the following disclaimer.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in the
19  *    documentation and/or other materials provided with the distribution.
20  * 3. Neither the name of the University nor the names of its contributors
21  *    may be used to endorse or promote products derived from this software
22  *    without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  *
36  *	@(#)bpf_filter.c	8.1 (Berkeley) 6/10/93
37  */
38 /*
39  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
40  * Use is subject to license terms.
41  */
42 
43 #include <sys/param.h>
44 #include <sys/time.h>
45 #include <sys/stream.h>
46 #include <sys/byteorder.h>
47 #include <sys/sdt.h>
48 
49 #define	EXTRACT_SHORT(p)	BE_IN16(p)
50 #define	EXTRACT_LONG(p)		BE_IN32(p)
51 
52 #ifdef _KERNEL
53 #define	M_LEN(_m)	((_m)->b_wptr - (_m)->b_rptr)
54 #define	mtod(_a, _t)	((_t)((_a)->b_rptr))
55 #define	MINDEX(len, m, k) 		\
56 { 					\
57 	len = M_LEN(m); 		\
58 	while (k >= len) { 		\
59 		k -= len; 		\
60 		m = m->b_cont; 		\
61 		if (m == 0) 		\
62 			return (0); 	\
63 		len = M_LEN(m); 	\
64 	} 				\
65 }
66 
67 static int m_xword(mblk_t *, uint32_t, int *);
68 static int m_xhalf(mblk_t *, uint32_t, int *);
69 
70 static int
m_xword(mblk_t * m,uint32_t k,int * err)71 m_xword(mblk_t *m, uint32_t k, int *err)
72 {
73 	int len;
74 	uchar_t *cp, *np;
75 	mblk_t *m0;
76 
77 	*err = 1;
78 	MINDEX(len, m, k);
79 	cp = mtod(m, uchar_t *) + k;
80 	if (len >= k + 4) {
81 		*err = 0;
82 		return (EXTRACT_LONG(cp));
83 	}
84 	m0 = m->b_cont;
85 	if (m0 == 0 || M_LEN(m0) + len - k < 4) {
86 		DTRACE_PROBE3(mblk_xword_fail, mblk_t *, m0, int, len, int, k);
87 		return (0);
88 	}
89 	*err = 0;
90 	np = mtod(m0, uchar_t *);
91 	switch (len - k) {
92 
93 	case 1:
94 		return ((cp[0] << 24) | (np[0] << 16) | (np[1] << 8) | np[2]);
95 
96 	case 2:
97 		return ((cp[0] << 24) | (cp[1] << 16) | (np[0] << 8) | np[1]);
98 
99 	default:
100 		return ((cp[0] << 24) | (cp[1] << 16) | (cp[2] << 8) | np[0]);
101 	}
102 }
103 
104 static int
m_xhalf(mblk_t * m,uint32_t k,int * err)105 m_xhalf(mblk_t *m, uint32_t k, int *err)
106 {
107 	int len;
108 	uchar_t *cp;
109 	mblk_t *m0;
110 
111 	*err = 1;
112 	MINDEX(len, m, k);
113 	cp = mtod(m, uchar_t *) + k;
114 	if (len >= k + 2) {
115 		*err = 0;
116 		return (EXTRACT_SHORT(cp));
117 	}
118 	m0 = m->b_cont;
119 	if (m0 == 0) {
120 		DTRACE_PROBE3(mblk_xhalf_fail, mblk_t *, m0, int, len, int, k);
121 		return (0);
122 	}
123 	*err = 0;
124 	return ((cp[0] << 8) | mtod(m0, uchar_t *)[0]);
125 }
126 #else /* _KERNEL */
127 #include <stdlib.h>
128 #endif /* !_KERNEL */
129 
130 #include <net/bpf.h>
131 
132 /*
133  * Execute the filter program starting at pc on the packet p
134  * wirelen is the length of the original packet
135  * buflen is the amount of data present
136  * When buflen is non-0, p is a pointer to a the start of the packet and the
137  * packet is only in one mblk_t.
138  * When buflen is 0, p is an mblk_t pointer.
139  */
140 uint_t
bpf_filter(struct bpf_insn * pc,uchar_t * p,uint_t wirelen,uint_t buflen)141 bpf_filter(struct bpf_insn *pc, uchar_t *p, uint_t wirelen, uint_t buflen)
142 {
143 	uint32_t A, X, k;
144 	uint32_t mem[BPF_MEMWORDS];
145 
146 	if (pc == 0)
147 		/*
148 		 * No filter means accept all.
149 		 */
150 		return ((uint_t)-1);
151 	A = 0;
152 	X = 0;
153 	--pc;
154 	/* CONSTCOND */
155 	while (1) {
156 		++pc;
157 		switch (pc->code) {
158 
159 		default:
160 #ifdef _KERNEL
161 			DTRACE_PROBE1(bpf_insn_unknown,
162 			    struct bpf_insn *, pc);
163 			return (0);
164 #else
165 			abort();
166 #endif
167 		case BPF_RET|BPF_K:
168 			return ((uint_t)pc->k);
169 
170 		case BPF_RET|BPF_A:
171 			return ((uint_t)A);
172 
173 		case BPF_LD|BPF_W|BPF_ABS:
174 			k = pc->k;
175 			if (k + sizeof (int32_t) > buflen) {
176 #ifdef _KERNEL
177 				int merr = 0;
178 
179 				if (buflen != 0)
180 					return (0);
181 				A = m_xword((mblk_t *)p, k, &merr);
182 				if (merr != 0)
183 					return (0);
184 				continue;
185 #else
186 				return (0);
187 #endif
188 			}
189 			A = EXTRACT_LONG(&p[k]);
190 			continue;
191 
192 		case BPF_LD|BPF_H|BPF_ABS:
193 			k = pc->k;
194 			if (k + sizeof (int16_t) > buflen) {
195 #ifdef _KERNEL
196 				int merr;
197 
198 				if (buflen != 0)
199 					return (0);
200 				A = m_xhalf((mblk_t *)p, k, &merr);
201 				if (merr != 0)
202 					return (0);
203 				continue;
204 #else
205 				return (0);
206 #endif
207 			}
208 			A = EXTRACT_SHORT(&p[k]);
209 			continue;
210 
211 		case BPF_LD|BPF_B|BPF_ABS:
212 			k = pc->k;
213 			if (k >= buflen) {
214 #ifdef _KERNEL
215 				mblk_t *m;
216 				int len;
217 
218 				if (buflen != 0)
219 					return (0);
220 				m = (mblk_t *)p;
221 				MINDEX(len, m, k);
222 				A = mtod(m, uchar_t *)[k];
223 				continue;
224 #else
225 				return (0);
226 #endif
227 			}
228 			A = p[k];
229 			continue;
230 
231 		case BPF_LD|BPF_W|BPF_LEN:
232 			A = wirelen;
233 			continue;
234 
235 		case BPF_LDX|BPF_W|BPF_LEN:
236 			X = wirelen;
237 			continue;
238 
239 		case BPF_LD|BPF_W|BPF_IND:
240 			k = X + pc->k;
241 			if (k + sizeof (int32_t) > buflen) {
242 #ifdef _KERNEL
243 				int merr = 0;
244 
245 				if (buflen != 0)
246 					return (0);
247 				A = m_xword((mblk_t *)p, k, &merr);
248 				if (merr != 0)
249 					return (0);
250 				continue;
251 #else
252 				return (0);
253 #endif
254 			}
255 			A = EXTRACT_LONG(&p[k]);
256 			continue;
257 
258 		case BPF_LD|BPF_H|BPF_IND:
259 			k = X + pc->k;
260 			if (k + sizeof (int16_t) > buflen) {
261 #ifdef _KERNEL
262 				int merr = 0;
263 
264 				if (buflen != 0)
265 					return (0);
266 				A = m_xhalf((mblk_t *)p, k, &merr);
267 				if (merr != 0)
268 					return (0);
269 				continue;
270 #else
271 				return (0);
272 #endif
273 			}
274 			A = EXTRACT_SHORT(&p[k]);
275 			continue;
276 
277 		case BPF_LD|BPF_B|BPF_IND:
278 			k = X + pc->k;
279 			if (k >= buflen) {
280 #ifdef _KERNEL
281 				mblk_t *m;
282 				int len;
283 
284 				if (buflen != 0)
285 					return (0);
286 				m = (mblk_t *)p;
287 				MINDEX(len, m, k);
288 				A = mtod(m, uchar_t *)[k];
289 				continue;
290 #else
291 				return (0);
292 #endif
293 			}
294 			A = p[k];
295 			continue;
296 
297 		case BPF_LDX|BPF_MSH|BPF_B:
298 			k = pc->k;
299 			if (k >= buflen) {
300 #ifdef _KERNEL
301 				mblk_t *m;
302 				int len;
303 
304 				if (buflen != 0)
305 					return (0);
306 				m = (mblk_t *)p;
307 				MINDEX(len, m, k);
308 				X = (mtod(m, char *)[k] & 0xf) << 2;
309 				continue;
310 #else
311 				return (0);
312 #endif
313 			}
314 			X = (p[pc->k] & 0xf) << 2;
315 			continue;
316 
317 		case BPF_LD|BPF_IMM:
318 			A = pc->k;
319 			continue;
320 
321 		case BPF_LDX|BPF_IMM:
322 			X = pc->k;
323 			continue;
324 
325 		case BPF_LD|BPF_MEM:
326 			A = mem[pc->k];
327 			continue;
328 
329 		case BPF_LDX|BPF_MEM:
330 			X = mem[pc->k];
331 			continue;
332 
333 		case BPF_ST:
334 			mem[pc->k] = A;
335 			continue;
336 
337 		case BPF_STX:
338 			mem[pc->k] = X;
339 			continue;
340 
341 		case BPF_JMP|BPF_JA:
342 			pc += pc->k;
343 			continue;
344 
345 		case BPF_JMP|BPF_JGT|BPF_K:
346 			pc += (A > pc->k) ? pc->jt : pc->jf;
347 			continue;
348 
349 		case BPF_JMP|BPF_JGE|BPF_K:
350 			pc += (A >= pc->k) ? pc->jt : pc->jf;
351 			continue;
352 
353 		case BPF_JMP|BPF_JEQ|BPF_K:
354 			pc += (A == pc->k) ? pc->jt : pc->jf;
355 			continue;
356 
357 		case BPF_JMP|BPF_JSET|BPF_K:
358 			pc += (A & pc->k) ? pc->jt : pc->jf;
359 			continue;
360 
361 		case BPF_JMP|BPF_JGT|BPF_X:
362 			pc += (A > X) ? pc->jt : pc->jf;
363 			continue;
364 
365 		case BPF_JMP|BPF_JGE|BPF_X:
366 			pc += (A >= X) ? pc->jt : pc->jf;
367 			continue;
368 
369 		case BPF_JMP|BPF_JEQ|BPF_X:
370 			pc += (A == X) ? pc->jt : pc->jf;
371 			continue;
372 
373 		case BPF_JMP|BPF_JSET|BPF_X:
374 			pc += (A & X) ? pc->jt : pc->jf;
375 			continue;
376 
377 		case BPF_ALU|BPF_ADD|BPF_X:
378 			A += X;
379 			continue;
380 
381 		case BPF_ALU|BPF_SUB|BPF_X:
382 			A -= X;
383 			continue;
384 
385 		case BPF_ALU|BPF_MUL|BPF_X:
386 			A *= X;
387 			continue;
388 
389 		case BPF_ALU|BPF_DIV|BPF_X:
390 			if (X == 0)
391 				return (0);
392 			A /= X;
393 			continue;
394 
395 		case BPF_ALU|BPF_AND|BPF_X:
396 			A &= X;
397 			continue;
398 
399 		case BPF_ALU|BPF_OR|BPF_X:
400 			A |= X;
401 			continue;
402 
403 		case BPF_ALU|BPF_LSH|BPF_X:
404 			A <<= X;
405 			continue;
406 
407 		case BPF_ALU|BPF_RSH|BPF_X:
408 			A >>= X;
409 			continue;
410 
411 		case BPF_ALU|BPF_ADD|BPF_K:
412 			A += pc->k;
413 			continue;
414 
415 		case BPF_ALU|BPF_SUB|BPF_K:
416 			A -= pc->k;
417 			continue;
418 
419 		case BPF_ALU|BPF_MUL|BPF_K:
420 			A *= pc->k;
421 			continue;
422 
423 		case BPF_ALU|BPF_DIV|BPF_K:
424 			A /= pc->k;
425 			continue;
426 
427 		case BPF_ALU|BPF_AND|BPF_K:
428 			A &= pc->k;
429 			continue;
430 
431 		case BPF_ALU|BPF_OR|BPF_K:
432 			A |= pc->k;
433 			continue;
434 
435 		case BPF_ALU|BPF_LSH|BPF_K:
436 			A <<= pc->k;
437 			continue;
438 
439 		case BPF_ALU|BPF_RSH|BPF_K:
440 			A >>= pc->k;
441 			continue;
442 
443 		case BPF_ALU|BPF_NEG:
444 			A = -A;
445 			continue;
446 
447 		case BPF_MISC|BPF_TAX:
448 			X = A;
449 			continue;
450 
451 		case BPF_MISC|BPF_TXA:
452 			A = X;
453 			continue;
454 		}
455 	}
456 	/* NOTREACHED */
457 }
458 
459 #ifdef _KERNEL
460 /*
461  * Return true if the 'fcode' is a valid filter program.
462  * The constraints are that each jump be forward and to a valid
463  * code, that memory accesses are within valid ranges (to the
464  * extent that this can be checked statically; loads of packet
465  * data have to be, and are, also checked at run time), and that
466  * the code terminates with either an accept or reject.
467  *
468  * The kernel needs to be able to verify an application's filter code.
469  * Otherwise, a bogus program could easily crash the system.
470  */
471 int
bpf_validate(struct bpf_insn * f,int len)472 bpf_validate(struct bpf_insn *f, int len)
473 {
474 	uint_t i, from;
475 	struct bpf_insn *p;
476 
477 	if (len < 1 || len > BPF_MAXINSNS)
478 		return (0);
479 
480 	for (i = 0; i < len; ++i) {
481 		p = &f[i];
482 		DTRACE_PROBE1(bpf_valid_insn, struct bpf_insn *, p);
483 		switch (BPF_CLASS(p->code)) {
484 		/*
485 		 * Check that memory operations use valid addresses.
486 		 */
487 		case BPF_LD:
488 		case BPF_LDX:
489 			switch (BPF_MODE(p->code)) {
490 			case BPF_MEM:
491 				if (p->k >= BPF_MEMWORDS)
492 					return (0);
493 				break;
494 			case BPF_ABS:
495 			case BPF_IND:
496 			case BPF_MSH:
497 			case BPF_IMM:
498 			case BPF_LEN:
499 				break;
500 			default:
501 				return (0);
502 			}
503 			break;
504 		case BPF_ST:
505 		case BPF_STX:
506 			if (p->k >= BPF_MEMWORDS)
507 				return (0);
508 			break;
509 		case BPF_ALU:
510 			switch (BPF_OP(p->code)) {
511 			case BPF_ADD:
512 			case BPF_SUB:
513 			case BPF_MUL:
514 			case BPF_OR:
515 			case BPF_AND:
516 			case BPF_LSH:
517 			case BPF_RSH:
518 			case BPF_NEG:
519 				break;
520 			case BPF_DIV:
521 				/*
522 				 * Check for constant division by 0.
523 				 */
524 				if (BPF_RVAL(p->code) == BPF_K && p->k == 0)
525 					return (0);
526 				break;
527 			default:
528 				return (0);
529 			}
530 			break;
531 		case BPF_JMP:
532 			/*
533 			 * Check that jumps are within the code block,
534 			 * and that unconditional branches don't go
535 			 * backwards as a result of an overflow.
536 			 * Unconditional branches have a 32-bit offset,
537 			 * so they could overflow; we check to make
538 			 * sure they don't.  Conditional branches have
539 			 * an 8-bit offset, and the from address is <=
540 			 * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
541 			 * is sufficiently small that adding 255 to it
542 			 * won't overflow.
543 			 *
544 			 * We know that len is <= BPF_MAXINSNS, and we
545 			 * assume that BPF_MAXINSNS is < the maximum size
546 			 * of a uint_t, so that i + 1 doesn't overflow.
547 			 */
548 			from = i + 1;
549 			switch (BPF_OP(p->code)) {
550 			case BPF_JA:
551 				if (from + p->k < from || from + p->k >= len)
552 					return (0);
553 				break;
554 			case BPF_JEQ:
555 			case BPF_JGT:
556 			case BPF_JGE:
557 			case BPF_JSET:
558 				if (from + p->jt >= len || from + p->jf >= len)
559 					return (0);
560 				break;
561 			default:
562 				return (0);
563 			}
564 			break;
565 		case BPF_RET:
566 			break;
567 		case BPF_MISC:
568 			break;
569 		default:
570 			return (0);
571 		}
572 	}
573 
574 	return (BPF_CLASS(f[len - 1].code) == BPF_RET);
575 }
576 #endif
577