bpf_filter.c revision 264457 
1270866Simp/*-
2270866Simp * Copyright (c) 1990, 1991, 1993
3270866Simp *	The Regents of the University of California.  All rights reserved.
4270866Simp *
5270866Simp * This code is derived from the Stanford/CMU enet packet filter,
6270866Simp * (net/enet.c) distributed as part of 4.3BSD, and code contributed
7270866Simp * to Berkeley by Steven McCanne and Van Jacobson both of Lawrence
8270866Simp * Berkeley Laboratory.
9270866Simp *
10270866Simp * Redistribution and use in source and binary forms, with or without
11270866Simp * modification, are permitted provided that the following conditions
12270866Simp * are met:
13270866Simp * 1. Redistributions of source code must retain the above copyright
14270866Simp *    notice, this list of conditions and the following disclaimer.
15270866Simp * 2. Redistributions in binary form must reproduce the above copyright
16270866Simp *    notice, this list of conditions and the following disclaimer in the
17270866Simp *    documentation and/or other materials provided with the distribution.
18270866Simp * 4. Neither the name of the University nor the names of its contributors
19270866Simp *    may be used to endorse or promote products derived from this software
20270866Simp *    without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 *
34 *      @(#)bpf_filter.c	8.1 (Berkeley) 6/10/93
35 */
36
37#include <sys/cdefs.h>
38__FBSDID("$FreeBSD: stable/10/sys/net/bpf_filter.c 264457 2014-04-14 13:30:08Z jmmv $");
39
40#include <sys/param.h>
41
42#if !defined(_KERNEL)
43#include <strings.h>
44#endif
45#if !defined(_KERNEL) || defined(sun)
46#include <netinet/in.h>
47#endif
48
49#ifndef __i386__
50#define BPF_ALIGN
51#endif
52
53#ifndef BPF_ALIGN
54#define EXTRACT_SHORT(p)	((u_int16_t)ntohs(*(u_int16_t *)p))
55#define EXTRACT_LONG(p)		(ntohl(*(u_int32_t *)p))
56#else
57#define EXTRACT_SHORT(p)\
58	((u_int16_t)\
59		((u_int16_t)*((u_char *)p+0)<<8|\
60		 (u_int16_t)*((u_char *)p+1)<<0))
61#define EXTRACT_LONG(p)\
62		((u_int32_t)*((u_char *)p+0)<<24|\
63		 (u_int32_t)*((u_char *)p+1)<<16|\
64		 (u_int32_t)*((u_char *)p+2)<<8|\
65		 (u_int32_t)*((u_char *)p+3)<<0)
66#endif
67
68#ifdef _KERNEL
69#include <sys/mbuf.h>
70#else
71#include <stdlib.h>
72#endif
73#include <net/bpf.h>
74#ifdef _KERNEL
75#define MINDEX(m, k) \
76{ \
77	register int len = m->m_len; \
78 \
79	while (k >= len) { \
80		k -= len; \
81		m = m->m_next; \
82		if (m == 0) \
83			return (0); \
84		len = m->m_len; \
85	} \
86}
87
88static u_int16_t	m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err);
89static u_int32_t	m_xword(struct mbuf *m, bpf_u_int32 k, int *err);
90
91static u_int32_t
92m_xword(struct mbuf *m, bpf_u_int32 k, int *err)
93{
94	size_t len;
95	u_char *cp, *np;
96	struct mbuf *m0;
97
98	len = m->m_len;
99	while (k >= len) {
100		k -= len;
101		m = m->m_next;
102		if (m == 0)
103			goto bad;
104		len = m->m_len;
105	}
106	cp = mtod(m, u_char *) + k;
107	if (len - k >= 4) {
108		*err = 0;
109		return (EXTRACT_LONG(cp));
110	}
111	m0 = m->m_next;
112	if (m0 == 0 || m0->m_len + len - k < 4)
113		goto bad;
114	*err = 0;
115	np = mtod(m0, u_char *);
116	switch (len - k) {
117	case 1:
118		return (((u_int32_t)cp[0] << 24) |
119		    ((u_int32_t)np[0] << 16) |
120		    ((u_int32_t)np[1] << 8)  |
121		    (u_int32_t)np[2]);
122
123	case 2:
124		return (((u_int32_t)cp[0] << 24) |
125		    ((u_int32_t)cp[1] << 16) |
126		    ((u_int32_t)np[0] << 8) |
127		    (u_int32_t)np[1]);
128
129	default:
130		return (((u_int32_t)cp[0] << 24) |
131		    ((u_int32_t)cp[1] << 16) |
132		    ((u_int32_t)cp[2] << 8) |
133		    (u_int32_t)np[0]);
134	}
135    bad:
136	*err = 1;
137	return (0);
138}
139
140static u_int16_t
141m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err)
142{
143	size_t len;
144	u_char *cp;
145	struct mbuf *m0;
146
147	len = m->m_len;
148	while (k >= len) {
149		k -= len;
150		m = m->m_next;
151		if (m == 0)
152			goto bad;
153		len = m->m_len;
154	}
155	cp = mtod(m, u_char *) + k;
156	if (len - k >= 2) {
157		*err = 0;
158		return (EXTRACT_SHORT(cp));
159	}
160	m0 = m->m_next;
161	if (m0 == 0)
162		goto bad;
163	*err = 0;
164	return ((cp[0] << 8) | mtod(m0, u_char *)[0]);
165 bad:
166	*err = 1;
167	return (0);
168}
169#endif
170
171/*
172 * Execute the filter program starting at pc on the packet p
173 * wirelen is the length of the original packet
174 * buflen is the amount of data present
175 */
176u_int
177bpf_filter(const struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen)
178{
179	u_int32_t A = 0, X = 0;
180	bpf_u_int32 k;
181	u_int32_t mem[BPF_MEMWORDS];
182
183	bzero(mem, sizeof(mem));
184
185	if (pc == NULL)
186		/*
187		 * No filter means accept all.
188		 */
189		return ((u_int)-1);
190
191	--pc;
192	while (1) {
193		++pc;
194		switch (pc->code) {
195		default:
196#ifdef _KERNEL
197			return (0);
198#else
199			abort();
200#endif
201
202		case BPF_RET|BPF_K:
203			return ((u_int)pc->k);
204
205		case BPF_RET|BPF_A:
206			return ((u_int)A);
207
208		case BPF_LD|BPF_W|BPF_ABS:
209			k = pc->k;
210			if (k > buflen || sizeof(int32_t) > buflen - k) {
211#ifdef _KERNEL
212				int merr;
213
214				if (buflen != 0)
215					return (0);
216				A = m_xword((struct mbuf *)p, k, &merr);
217				if (merr != 0)
218					return (0);
219				continue;
220#else
221				return (0);
222#endif
223			}
224#ifdef BPF_ALIGN
225			if (((intptr_t)(p + k) & 3) != 0)
226				A = EXTRACT_LONG(&p[k]);
227			else
228#endif
229				A = ntohl(*(int32_t *)(p + k));
230			continue;
231
232		case BPF_LD|BPF_H|BPF_ABS:
233			k = pc->k;
234			if (k > buflen || sizeof(int16_t) > buflen - k) {
235#ifdef _KERNEL
236				int merr;
237
238				if (buflen != 0)
239					return (0);
240				A = m_xhalf((struct mbuf *)p, k, &merr);
241				continue;
242#else
243				return (0);
244#endif
245			}
246			A = EXTRACT_SHORT(&p[k]);
247			continue;
248
249		case BPF_LD|BPF_B|BPF_ABS:
250			k = pc->k;
251			if (k >= buflen) {
252#ifdef _KERNEL
253				struct mbuf *m;
254
255				if (buflen != 0)
256					return (0);
257				m = (struct mbuf *)p;
258				MINDEX(m, k);
259				A = mtod(m, u_char *)[k];
260				continue;
261#else
262				return (0);
263#endif
264			}
265			A = p[k];
266			continue;
267
268		case BPF_LD|BPF_W|BPF_LEN:
269			A = wirelen;
270			continue;
271
272		case BPF_LDX|BPF_W|BPF_LEN:
273			X = wirelen;
274			continue;
275
276		case BPF_LD|BPF_W|BPF_IND:
277			k = X + pc->k;
278			if (pc->k > buflen || X > buflen - pc->k ||
279			    sizeof(int32_t) > buflen - k) {
280#ifdef _KERNEL
281				int merr;
282
283				if (buflen != 0)
284					return (0);
285				A = m_xword((struct mbuf *)p, k, &merr);
286				if (merr != 0)
287					return (0);
288				continue;
289#else
290				return (0);
291#endif
292			}
293#ifdef BPF_ALIGN
294			if (((intptr_t)(p + k) & 3) != 0)
295				A = EXTRACT_LONG(&p[k]);
296			else
297#endif
298				A = ntohl(*(int32_t *)(p + k));
299			continue;
300
301		case BPF_LD|BPF_H|BPF_IND:
302			k = X + pc->k;
303			if (X > buflen || pc->k > buflen - X ||
304			    sizeof(int16_t) > buflen - k) {
305#ifdef _KERNEL
306				int merr;
307
308				if (buflen != 0)
309					return (0);
310				A = m_xhalf((struct mbuf *)p, k, &merr);
311				if (merr != 0)
312					return (0);
313				continue;
314#else
315				return (0);
316#endif
317			}
318			A = EXTRACT_SHORT(&p[k]);
319			continue;
320
321		case BPF_LD|BPF_B|BPF_IND:
322			k = X + pc->k;
323			if (pc->k >= buflen || X >= buflen - pc->k) {
324#ifdef _KERNEL
325				struct mbuf *m;
326
327				if (buflen != 0)
328					return (0);
329				m = (struct mbuf *)p;
330				MINDEX(m, k);
331				A = mtod(m, u_char *)[k];
332				continue;
333#else
334				return (0);
335#endif
336			}
337			A = p[k];
338			continue;
339
340		case BPF_LDX|BPF_MSH|BPF_B:
341			k = pc->k;
342			if (k >= buflen) {
343#ifdef _KERNEL
344				register struct mbuf *m;
345
346				if (buflen != 0)
347					return (0);
348				m = (struct mbuf *)p;
349				MINDEX(m, k);
350				X = (mtod(m, u_char *)[k] & 0xf) << 2;
351				continue;
352#else
353				return (0);
354#endif
355			}
356			X = (p[pc->k] & 0xf) << 2;
357			continue;
358
359		case BPF_LD|BPF_IMM:
360			A = pc->k;
361			continue;
362
363		case BPF_LDX|BPF_IMM:
364			X = pc->k;
365			continue;
366
367		case BPF_LD|BPF_MEM:
368			A = mem[pc->k];
369			continue;
370
371		case BPF_LDX|BPF_MEM:
372			X = mem[pc->k];
373			continue;
374
375		case BPF_ST:
376			mem[pc->k] = A;
377			continue;
378
379		case BPF_STX:
380			mem[pc->k] = X;
381			continue;
382
383		case BPF_JMP|BPF_JA:
384			pc += pc->k;
385			continue;
386
387		case BPF_JMP|BPF_JGT|BPF_K:
388			pc += (A > pc->k) ? pc->jt : pc->jf;
389			continue;
390
391		case BPF_JMP|BPF_JGE|BPF_K:
392			pc += (A >= pc->k) ? pc->jt : pc->jf;
393			continue;
394
395		case BPF_JMP|BPF_JEQ|BPF_K:
396			pc += (A == pc->k) ? pc->jt : pc->jf;
397			continue;
398
399		case BPF_JMP|BPF_JSET|BPF_K:
400			pc += (A & pc->k) ? pc->jt : pc->jf;
401			continue;
402
403		case BPF_JMP|BPF_JGT|BPF_X:
404			pc += (A > X) ? pc->jt : pc->jf;
405			continue;
406
407		case BPF_JMP|BPF_JGE|BPF_X:
408			pc += (A >= X) ? pc->jt : pc->jf;
409			continue;
410
411		case BPF_JMP|BPF_JEQ|BPF_X:
412			pc += (A == X) ? pc->jt : pc->jf;
413			continue;
414
415		case BPF_JMP|BPF_JSET|BPF_X:
416			pc += (A & X) ? pc->jt : pc->jf;
417			continue;
418
419		case BPF_ALU|BPF_ADD|BPF_X:
420			A += X;
421			continue;
422
423		case BPF_ALU|BPF_SUB|BPF_X:
424			A -= X;
425			continue;
426
427		case BPF_ALU|BPF_MUL|BPF_X:
428			A *= X;
429			continue;
430
431		case BPF_ALU|BPF_DIV|BPF_X:
432			if (X == 0)
433				return (0);
434			A /= X;
435			continue;
436
437		case BPF_ALU|BPF_AND|BPF_X:
438			A &= X;
439			continue;
440
441		case BPF_ALU|BPF_OR|BPF_X:
442			A |= X;
443			continue;
444
445		case BPF_ALU|BPF_LSH|BPF_X:
446			A <<= X;
447			continue;
448
449		case BPF_ALU|BPF_RSH|BPF_X:
450			A >>= X;
451			continue;
452
453		case BPF_ALU|BPF_ADD|BPF_K:
454			A += pc->k;
455			continue;
456
457		case BPF_ALU|BPF_SUB|BPF_K:
458			A -= pc->k;
459			continue;
460
461		case BPF_ALU|BPF_MUL|BPF_K:
462			A *= pc->k;
463			continue;
464
465		case BPF_ALU|BPF_DIV|BPF_K:
466			A /= pc->k;
467			continue;
468
469		case BPF_ALU|BPF_AND|BPF_K:
470			A &= pc->k;
471			continue;
472
473		case BPF_ALU|BPF_OR|BPF_K:
474			A |= pc->k;
475			continue;
476
477		case BPF_ALU|BPF_LSH|BPF_K:
478			A <<= pc->k;
479			continue;
480
481		case BPF_ALU|BPF_RSH|BPF_K:
482			A >>= pc->k;
483			continue;
484
485		case BPF_ALU|BPF_NEG:
486			A = -A;
487			continue;
488
489		case BPF_MISC|BPF_TAX:
490			X = A;
491			continue;
492
493		case BPF_MISC|BPF_TXA:
494			A = X;
495			continue;
496		}
497	}
498}
499
500#ifdef _KERNEL
501static const u_short	bpf_code_map[] = {
502	0x10ff,	/* 0x00-0x0f: 1111111100001000 */
503	0x3070,	/* 0x10-0x1f: 0000111000001100 */
504	0x3131,	/* 0x20-0x2f: 1000110010001100 */
505	0x3031,	/* 0x30-0x3f: 1000110000001100 */
506	0x3131,	/* 0x40-0x4f: 1000110010001100 */
507	0x1011,	/* 0x50-0x5f: 1000100000001000 */
508	0x1013,	/* 0x60-0x6f: 1100100000001000 */
509	0x1010,	/* 0x70-0x7f: 0000100000001000 */
510	0x0093,	/* 0x80-0x8f: 1100100100000000 */
511	0x0000,	/* 0x90-0x9f: 0000000000000000 */
512	0x0000,	/* 0xa0-0xaf: 0000000000000000 */
513	0x0002,	/* 0xb0-0xbf: 0100000000000000 */
514	0x0000,	/* 0xc0-0xcf: 0000000000000000 */
515	0x0000,	/* 0xd0-0xdf: 0000000000000000 */
516	0x0000,	/* 0xe0-0xef: 0000000000000000 */
517	0x0000	/* 0xf0-0xff: 0000000000000000 */
518};
519
520#define	BPF_VALIDATE_CODE(c)	\
521    ((c) <= 0xff && (bpf_code_map[(c) >> 4] & (1 << ((c) & 0xf))) != 0)
522
523/*
524 * Return true if the 'fcode' is a valid filter program.
525 * The constraints are that each jump be forward and to a valid
526 * code.  The code must terminate with either an accept or reject.
527 *
528 * The kernel needs to be able to verify an application's filter code.
529 * Otherwise, a bogus program could easily crash the system.
530 */
531int
532bpf_validate(const struct bpf_insn *f, int len)
533{
534	register int i;
535	register const struct bpf_insn *p;
536
537	/* Do not accept negative length filter. */
538	if (len < 0)
539		return (0);
540
541	/* An empty filter means accept all. */
542	if (len == 0)
543		return (1);
544
545	for (i = 0; i < len; ++i) {
546		p = &f[i];
547		/*
548		 * Check that the code is valid.
549		 */
550		if (!BPF_VALIDATE_CODE(p->code))
551			return (0);
552		/*
553		 * Check that that jumps are forward, and within
554		 * the code block.
555		 */
556		if (BPF_CLASS(p->code) == BPF_JMP) {
557			register u_int offset;
558
559			if (p->code == (BPF_JMP|BPF_JA))
560				offset = p->k;
561			else
562				offset = p->jt > p->jf ? p->jt : p->jf;
563			if (offset >= (u_int)(len - i) - 1)
564				return (0);
565			continue;
566		}
567		/*
568		 * Check that memory operations use valid addresses.
569		 */
570		if (p->code == BPF_ST || p->code == BPF_STX ||
571		    p->code == (BPF_LD|BPF_MEM) ||
572		    p->code == (BPF_LDX|BPF_MEM)) {
573			if (p->k >= BPF_MEMWORDS)
574				return (0);
575			continue;
576		}
577		/*
578		 * Check for constant division by 0.
579		 */
580		if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0)
581			return (0);
582	}
583	return (BPF_CLASS(f[len - 1].code) == BPF_RET);
584}
585#endif
586