1/*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1990, 1991, 1993
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
37#include <sys/param.h>
38
39#if !defined(_KERNEL)
40#include <strings.h>
41#endif
42#if !defined(_KERNEL) || defined(sun)
43#include <netinet/in.h>
44#endif
45
46#ifndef __i386__
47#define BPF_ALIGN
48#endif
49
50#ifndef BPF_ALIGN
51#define EXTRACT_SHORT(p)	((u_int16_t)ntohs(*(u_int16_t *)p))
52#define EXTRACT_LONG(p)		(ntohl(*(u_int32_t *)p))
53#else
54#define EXTRACT_SHORT(p)\
55	((u_int16_t)\
56		((u_int16_t)*((u_char *)p+0)<<8|\
57		 (u_int16_t)*((u_char *)p+1)<<0))
58#define EXTRACT_LONG(p)\
59		((u_int32_t)*((u_char *)p+0)<<24|\
60		 (u_int32_t)*((u_char *)p+1)<<16|\
61		 (u_int32_t)*((u_char *)p+2)<<8|\
62		 (u_int32_t)*((u_char *)p+3)<<0)
63#endif
64
65#ifdef _KERNEL
66#include <sys/mbuf.h>
67#else
68#include <stdlib.h>
69#endif
70#include <net/bpf.h>
71#ifdef _KERNEL
72#define MINDEX(m, k) \
73{ \
74	int len = m->m_len; \
75 \
76	while (k >= len) { \
77		k -= len; \
78		m = m->m_next; \
79		if (m == 0) \
80			return (0); \
81		len = m->m_len; \
82	} \
83}
84
85static u_int16_t	m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err);
86static u_int32_t	m_xword(struct mbuf *m, bpf_u_int32 k, int *err);
87
88static u_int32_t
89m_xword(struct mbuf *m, bpf_u_int32 k, int *err)
90{
91	size_t len;
92	u_char *cp, *np;
93	struct mbuf *m0;
94
95	len = m->m_len;
96	while (k >= len) {
97		k -= len;
98		m = m->m_next;
99		if (m == NULL)
100			goto bad;
101		len = m->m_len;
102	}
103	cp = mtod(m, u_char *) + k;
104	if (len - k >= 4) {
105		*err = 0;
106		return (EXTRACT_LONG(cp));
107	}
108	m0 = m->m_next;
109	if (m0 == NULL || m0->m_len + len - k < 4)
110		goto bad;
111	*err = 0;
112	np = mtod(m0, u_char *);
113	switch (len - k) {
114	case 1:
115		return (((u_int32_t)cp[0] << 24) |
116		    ((u_int32_t)np[0] << 16) |
117		    ((u_int32_t)np[1] << 8)  |
118		    (u_int32_t)np[2]);
119
120	case 2:
121		return (((u_int32_t)cp[0] << 24) |
122		    ((u_int32_t)cp[1] << 16) |
123		    ((u_int32_t)np[0] << 8) |
124		    (u_int32_t)np[1]);
125
126	default:
127		return (((u_int32_t)cp[0] << 24) |
128		    ((u_int32_t)cp[1] << 16) |
129		    ((u_int32_t)cp[2] << 8) |
130		    (u_int32_t)np[0]);
131	}
132    bad:
133	*err = 1;
134	return (0);
135}
136
137static u_int16_t
138m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err)
139{
140	size_t len;
141	u_char *cp;
142	struct mbuf *m0;
143
144	len = m->m_len;
145	while (k >= len) {
146		k -= len;
147		m = m->m_next;
148		if (m == NULL)
149			goto bad;
150		len = m->m_len;
151	}
152	cp = mtod(m, u_char *) + k;
153	if (len - k >= 2) {
154		*err = 0;
155		return (EXTRACT_SHORT(cp));
156	}
157	m0 = m->m_next;
158	if (m0 == NULL)
159		goto bad;
160	*err = 0;
161	return ((cp[0] << 8) | mtod(m0, u_char *)[0]);
162 bad:
163	*err = 1;
164	return (0);
165}
166#endif
167
168/*
169 * Execute the filter program starting at pc on the packet p
170 * wirelen is the length of the original packet
171 * buflen is the amount of data present
172 */
173u_int
174bpf_filter(const struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen)
175{
176	u_int32_t A = 0, X = 0;
177	bpf_u_int32 k;
178	u_int32_t mem[BPF_MEMWORDS];
179
180	bzero(mem, sizeof(mem));
181
182	if (pc == NULL)
183		/*
184		 * No filter means accept all.
185		 */
186		return ((u_int)-1);
187
188	--pc;
189	while (1) {
190		++pc;
191		switch (pc->code) {
192		default:
193#ifdef _KERNEL
194			return (0);
195#else
196			abort();
197#endif
198
199		case BPF_RET|BPF_K:
200			return ((u_int)pc->k);
201
202		case BPF_RET|BPF_A:
203			return ((u_int)A);
204
205		case BPF_LD|BPF_W|BPF_ABS:
206			k = pc->k;
207			if (k > buflen || sizeof(int32_t) > buflen - k) {
208#ifdef _KERNEL
209				int merr;
210
211				if (buflen != 0)
212					return (0);
213				A = m_xword((struct mbuf *)p, k, &merr);
214				if (merr != 0)
215					return (0);
216				continue;
217#else
218				return (0);
219#endif
220			}
221#ifdef BPF_ALIGN
222			if (((intptr_t)(p + k) & 3) != 0)
223				A = EXTRACT_LONG(&p[k]);
224			else
225#endif
226				A = ntohl(*(int32_t *)(p + k));
227			continue;
228
229		case BPF_LD|BPF_H|BPF_ABS:
230			k = pc->k;
231			if (k > buflen || sizeof(int16_t) > buflen - k) {
232#ifdef _KERNEL
233				int merr;
234
235				if (buflen != 0)
236					return (0);
237				A = m_xhalf((struct mbuf *)p, k, &merr);
238				continue;
239#else
240				return (0);
241#endif
242			}
243			A = EXTRACT_SHORT(&p[k]);
244			continue;
245
246		case BPF_LD|BPF_B|BPF_ABS:
247			k = pc->k;
248			if (k >= buflen) {
249#ifdef _KERNEL
250				struct mbuf *m;
251
252				if (buflen != 0)
253					return (0);
254				m = (struct mbuf *)p;
255				MINDEX(m, k);
256				A = mtod(m, u_char *)[k];
257				continue;
258#else
259				return (0);
260#endif
261			}
262			A = p[k];
263			continue;
264
265		case BPF_LD|BPF_W|BPF_LEN:
266			A = wirelen;
267			continue;
268
269		case BPF_LDX|BPF_W|BPF_LEN:
270			X = wirelen;
271			continue;
272
273		case BPF_LD|BPF_W|BPF_IND:
274			k = X + pc->k;
275			if (pc->k > buflen || X > buflen - pc->k ||
276			    sizeof(int32_t) > buflen - k) {
277#ifdef _KERNEL
278				int merr;
279
280				if (buflen != 0)
281					return (0);
282				A = m_xword((struct mbuf *)p, k, &merr);
283				if (merr != 0)
284					return (0);
285				continue;
286#else
287				return (0);
288#endif
289			}
290#ifdef BPF_ALIGN
291			if (((intptr_t)(p + k) & 3) != 0)
292				A = EXTRACT_LONG(&p[k]);
293			else
294#endif
295				A = ntohl(*(int32_t *)(p + k));
296			continue;
297
298		case BPF_LD|BPF_H|BPF_IND:
299			k = X + pc->k;
300			if (X > buflen || pc->k > buflen - X ||
301			    sizeof(int16_t) > buflen - k) {
302#ifdef _KERNEL
303				int merr;
304
305				if (buflen != 0)
306					return (0);
307				A = m_xhalf((struct mbuf *)p, k, &merr);
308				if (merr != 0)
309					return (0);
310				continue;
311#else
312				return (0);
313#endif
314			}
315			A = EXTRACT_SHORT(&p[k]);
316			continue;
317
318		case BPF_LD|BPF_B|BPF_IND:
319			k = X + pc->k;
320			if (pc->k >= buflen || X >= buflen - pc->k) {
321#ifdef _KERNEL
322				struct mbuf *m;
323
324				if (buflen != 0)
325					return (0);
326				m = (struct mbuf *)p;
327				MINDEX(m, k);
328				A = mtod(m, u_char *)[k];
329				continue;
330#else
331				return (0);
332#endif
333			}
334			A = p[k];
335			continue;
336
337		case BPF_LDX|BPF_MSH|BPF_B:
338			k = pc->k;
339			if (k >= buflen) {
340#ifdef _KERNEL
341				struct mbuf *m;
342
343				if (buflen != 0)
344					return (0);
345				m = (struct mbuf *)p;
346				MINDEX(m, k);
347				X = (mtod(m, u_char *)[k] & 0xf) << 2;
348				continue;
349#else
350				return (0);
351#endif
352			}
353			X = (p[pc->k] & 0xf) << 2;
354			continue;
355
356		case BPF_LD|BPF_IMM:
357			A = pc->k;
358			continue;
359
360		case BPF_LDX|BPF_IMM:
361			X = pc->k;
362			continue;
363
364		case BPF_LD|BPF_MEM:
365			A = mem[pc->k];
366			continue;
367
368		case BPF_LDX|BPF_MEM:
369			X = mem[pc->k];
370			continue;
371
372		case BPF_ST:
373			mem[pc->k] = A;
374			continue;
375
376		case BPF_STX:
377			mem[pc->k] = X;
378			continue;
379
380		case BPF_JMP|BPF_JA:
381			pc += pc->k;
382			continue;
383
384		case BPF_JMP|BPF_JGT|BPF_K:
385			pc += (A > pc->k) ? pc->jt : pc->jf;
386			continue;
387
388		case BPF_JMP|BPF_JGE|BPF_K:
389			pc += (A >= pc->k) ? pc->jt : pc->jf;
390			continue;
391
392		case BPF_JMP|BPF_JEQ|BPF_K:
393			pc += (A == pc->k) ? pc->jt : pc->jf;
394			continue;
395
396		case BPF_JMP|BPF_JSET|BPF_K:
397			pc += (A & pc->k) ? pc->jt : pc->jf;
398			continue;
399
400		case BPF_JMP|BPF_JGT|BPF_X:
401			pc += (A > X) ? pc->jt : pc->jf;
402			continue;
403
404		case BPF_JMP|BPF_JGE|BPF_X:
405			pc += (A >= X) ? pc->jt : pc->jf;
406			continue;
407
408		case BPF_JMP|BPF_JEQ|BPF_X:
409			pc += (A == X) ? pc->jt : pc->jf;
410			continue;
411
412		case BPF_JMP|BPF_JSET|BPF_X:
413			pc += (A & X) ? pc->jt : pc->jf;
414			continue;
415
416		case BPF_ALU|BPF_ADD|BPF_X:
417			A += X;
418			continue;
419
420		case BPF_ALU|BPF_SUB|BPF_X:
421			A -= X;
422			continue;
423
424		case BPF_ALU|BPF_MUL|BPF_X:
425			A *= X;
426			continue;
427
428		case BPF_ALU|BPF_DIV|BPF_X:
429			if (X == 0)
430				return (0);
431			A /= X;
432			continue;
433
434		case BPF_ALU|BPF_MOD|BPF_X:
435			if (X == 0)
436				return (0);
437			A %= X;
438			continue;
439
440		case BPF_ALU|BPF_AND|BPF_X:
441			A &= X;
442			continue;
443
444		case BPF_ALU|BPF_OR|BPF_X:
445			A |= X;
446			continue;
447
448		case BPF_ALU|BPF_XOR|BPF_X:
449			A ^= X;
450			continue;
451
452		case BPF_ALU|BPF_LSH|BPF_X:
453			A <<= X;
454			continue;
455
456		case BPF_ALU|BPF_RSH|BPF_X:
457			A >>= X;
458			continue;
459
460		case BPF_ALU|BPF_ADD|BPF_K:
461			A += pc->k;
462			continue;
463
464		case BPF_ALU|BPF_SUB|BPF_K:
465			A -= pc->k;
466			continue;
467
468		case BPF_ALU|BPF_MUL|BPF_K:
469			A *= pc->k;
470			continue;
471
472		case BPF_ALU|BPF_DIV|BPF_K:
473			A /= pc->k;
474			continue;
475
476		case BPF_ALU|BPF_MOD|BPF_K:
477			A %= pc->k;
478			continue;
479
480		case BPF_ALU|BPF_AND|BPF_K:
481			A &= pc->k;
482			continue;
483
484		case BPF_ALU|BPF_OR|BPF_K:
485			A |= pc->k;
486			continue;
487
488		case BPF_ALU|BPF_XOR|BPF_K:
489			A ^= pc->k;
490			continue;
491
492		case BPF_ALU|BPF_LSH|BPF_K:
493			A <<= pc->k;
494			continue;
495
496		case BPF_ALU|BPF_RSH|BPF_K:
497			A >>= pc->k;
498			continue;
499
500		case BPF_ALU|BPF_NEG:
501			A = -A;
502			continue;
503
504		case BPF_MISC|BPF_TAX:
505			X = A;
506			continue;
507
508		case BPF_MISC|BPF_TXA:
509			A = X;
510			continue;
511		}
512	}
513}
514
515#ifdef _KERNEL
516static const u_short	bpf_code_map[] = {
517	0x10ff,	/* 0x00-0x0f: 1111111100001000 */
518	0x3070,	/* 0x10-0x1f: 0000111000001100 */
519	0x3131,	/* 0x20-0x2f: 1000110010001100 */
520	0x3031,	/* 0x30-0x3f: 1000110000001100 */
521	0x3131,	/* 0x40-0x4f: 1000110010001100 */
522	0x1011,	/* 0x50-0x5f: 1000100000001000 */
523	0x1013,	/* 0x60-0x6f: 1100100000001000 */
524	0x1010,	/* 0x70-0x7f: 0000100000001000 */
525	0x0093,	/* 0x80-0x8f: 1100100100000000 */
526	0x1010,	/* 0x90-0x9f: 0000100000001000 */
527	0x1010,	/* 0xa0-0xaf: 0000100000001000 */
528	0x0002,	/* 0xb0-0xbf: 0100000000000000 */
529	0x0000,	/* 0xc0-0xcf: 0000000000000000 */
530	0x0000,	/* 0xd0-0xdf: 0000000000000000 */
531	0x0000,	/* 0xe0-0xef: 0000000000000000 */
532	0x0000	/* 0xf0-0xff: 0000000000000000 */
533};
534
535#define	BPF_VALIDATE_CODE(c)	\
536    ((c) <= 0xff && (bpf_code_map[(c) >> 4] & (1 << ((c) & 0xf))) != 0)
537
538/*
539 * Return true if the 'fcode' is a valid filter program.
540 * The constraints are that each jump be forward and to a valid
541 * code.  The code must terminate with either an accept or reject.
542 *
543 * The kernel needs to be able to verify an application's filter code.
544 * Otherwise, a bogus program could easily crash the system.
545 */
546int
547bpf_validate(const struct bpf_insn *f, int len)
548{
549	int i;
550	const struct bpf_insn *p;
551
552	/* Do not accept negative length filter. */
553	if (len < 0)
554		return (0);
555
556	/* An empty filter means accept all. */
557	if (len == 0)
558		return (1);
559
560	for (i = 0; i < len; ++i) {
561		p = &f[i];
562		/*
563		 * Check that the code is valid.
564		 */
565		if (!BPF_VALIDATE_CODE(p->code))
566			return (0);
567		/*
568		 * Check that the jumps are forward, and within
569		 * the code block.
570		 */
571		if (BPF_CLASS(p->code) == BPF_JMP) {
572			u_int offset;
573
574			if (p->code == (BPF_JMP|BPF_JA))
575				offset = p->k;
576			else
577				offset = p->jt > p->jf ? p->jt : p->jf;
578			if (offset >= (u_int)(len - i) - 1)
579				return (0);
580			continue;
581		}
582		/*
583		 * Check that memory operations use valid addresses.
584		 */
585		if (p->code == BPF_ST || p->code == BPF_STX ||
586		    p->code == (BPF_LD|BPF_MEM) ||
587		    p->code == (BPF_LDX|BPF_MEM)) {
588			if (p->k >= BPF_MEMWORDS)
589				return (0);
590			continue;
591		}
592		/*
593		 * Check for constant division by 0.
594		 */
595		if ((p->code == (BPF_ALU|BPF_DIV|BPF_K) ||
596		    p->code == (BPF_ALU|BPF_MOD|BPF_K)) && p->k == 0)
597			return (0);
598	}
599	return (BPF_CLASS(f[len - 1].code) == BPF_RET);
600}
601#endif
602