1/*
2 * Copyright (c) 2000-2017 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/*
29 * Copyright (c) 1990, 1991, 1993
30 * The Regents of the University of California. All rights reserved.
31 *
32 * This code is derived from the Stanford/CMU enet packet filter,
33 * (net/enet.c) distributed as part of 4.3BSD, and code contributed
34 * to Berkeley by Steven McCanne and Van Jacobson both of Lawrence
35 * Berkeley Laboratory.
36 *
37 * Redistribution and use in source and binary forms, with or without
38 * modification, are permitted provided that the following conditions
39 * are met:
40 * 1. Redistributions of source code must retain the above copyright
41 * notice, this list of conditions and the following disclaimer.
42 * 2. Redistributions in binary form must reproduce the above copyright
43 * notice, this list of conditions and the following disclaimer in the
44 * documentation and/or other materials provided with the distribution.
45 * 3. All advertising materials mentioning features or use of this software
46 * must display the following acknowledgement:
47 * This product includes software developed by the University of
48 * California, Berkeley and its contributors.
49 * 4. Neither the name of the University nor the names of its contributors
50 * may be used to endorse or promote products derived from this software
51 * without specific prior written permission.
52 *
53 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
54 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
55 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
56 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
57 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
58 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
59 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
60 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
61 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
62 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
63 * SUCH DAMAGE.
64 *
65 * @(#)bpf_filter.c 8.1 (Berkeley) 6/10/93
66 *
67 * $FreeBSD: src/sys/net/bpf_filter.c,v 1.17 1999/12/29 04:38:31 peter Exp $
68 */
69
70#include <sys/param.h>
71#include <string.h>
72
73#ifdef sun
74#include <netinet/in.h>
75#endif
76
77#ifdef KERNEL
78#include <sys/mbuf.h>
79#endif
80#include <net/bpf.h>
81#ifdef KERNEL
82
83extern unsigned int bpf_maxbufsize;
84
85static inline u_int32_t
86get_word_from_buffers(u_char * cp, u_char * np, int num_from_cp)
87{
88 u_int32_t val;
89
90 switch (num_from_cp) {
91 case 1:
92 val = ((u_int32_t)cp[0] << 24) |
93 ((u_int32_t)np[0] << 16) |
94 ((u_int32_t)np[1] << 8) |
95 (u_int32_t)np[2];
96 break;
97
98 case 2:
99 val = ((u_int32_t)cp[0] << 24) |
100 ((u_int32_t)cp[1] << 16) |
101 ((u_int32_t)np[0] << 8) |
102 (u_int32_t)np[1];
103 break;
104 default:
105 val = ((u_int32_t)cp[0] << 24) |
106 ((u_int32_t)cp[1] << 16) |
107 ((u_int32_t)cp[2] << 8) |
108 (u_int32_t)np[0];
109 break;
110 }
111 return (val);
112}
113
114static u_char *
115m_hdr_offset(struct mbuf **m_p, void * hdr, size_t hdrlen, bpf_u_int32 * k_p,
116 size_t * len_p)
117{
118 u_char *cp;
119 bpf_u_int32 k = *k_p;
120 size_t len;
121
122 if (k >= hdrlen) {
123 struct mbuf *m = *m_p;
124
125 /* there's no header or the offset we want is past the header */
126 k -= hdrlen;
127 len = m->m_len;
128 while (k >= len) {
129 k -= len;
130 m = m->m_next;
131 if (m == NULL)
132 return (NULL);
133 len = m->m_len;
134 }
135 cp = mtod(m, u_char *) + k;
136
137 /* return next mbuf, in case it's needed */
138 *m_p = m->m_next;
139
140 /* update the offset */
141 *k_p = k;
142 } else {
143 len = hdrlen;
144 cp = (u_char *)hdr + k;
145 }
146 *len_p = len;
147 return (cp);
148}
149
150static u_int32_t
151m_xword(struct mbuf *m, void * hdr, size_t hdrlen, bpf_u_int32 k, int *err)
152{
153 size_t len;
154 u_char *cp, *np;
155
156 cp = m_hdr_offset(&m, hdr, hdrlen, &k, &len);
157 if (cp == NULL)
158 goto bad;
159 if (len - k >= 4) {
160 *err = 0;
161 return EXTRACT_LONG(cp);
162 }
163 if (m == 0 || m->m_len + len - k < 4)
164 goto bad;
165 *err = 0;
166 np = mtod(m, u_char *);
167 return get_word_from_buffers(cp, np, len - k);
168
169 bad:
170 *err = 1;
171 return 0;
172}
173
174static u_int16_t
175m_xhalf(struct mbuf *m, void * hdr, size_t hdrlen, bpf_u_int32 k, int *err)
176{
177 size_t len;
178 u_char *cp;
179
180 cp = m_hdr_offset(&m, hdr, hdrlen, &k, &len);
181 if (cp == NULL)
182 goto bad;
183 if (len - k >= 2) {
184 *err = 0;
185 return EXTRACT_SHORT(cp);
186 }
187 if (m == 0)
188 goto bad;
189 *err = 0;
190 return (cp[0] << 8) | mtod(m, u_char *)[0];
191 bad:
192 *err = 1;
193 return 0;
194}
195
196static u_int8_t
197m_xbyte(struct mbuf *m, void * hdr, size_t hdrlen, bpf_u_int32 k, int *err)
198{
199 size_t len;
200 u_char *cp;
201
202 cp = m_hdr_offset(&m, hdr, hdrlen, &k, &len);
203 if (cp == NULL)
204 goto bad;
205 *err = 0;
206 return (*cp);
207 bad:
208 *err = 1;
209 return 0;
210
211}
212
213
214static u_int32_t
215bp_xword(struct bpf_packet *bp, bpf_u_int32 k, int *err)
216{
217 void * hdr = bp->bpfp_header;
218 size_t hdrlen = bp->bpfp_header_length;
219
220 switch (bp->bpfp_type) {
221 case BPF_PACKET_TYPE_MBUF:
222 return m_xword(bp->bpfp_mbuf, hdr, hdrlen, k, err);
223 default:
224 break;
225 }
226 *err = 1;
227 return 0;
228
229}
230
231static u_int16_t
232bp_xhalf(struct bpf_packet *bp, bpf_u_int32 k, int *err)
233{
234 void * hdr = bp->bpfp_header;
235 size_t hdrlen = bp->bpfp_header_length;
236
237 switch (bp->bpfp_type) {
238 case BPF_PACKET_TYPE_MBUF:
239 return m_xhalf(bp->bpfp_mbuf, hdr, hdrlen, k, err);
240 default:
241 break;
242 }
243 *err = 1;
244 return 0;
245
246}
247
248static u_int8_t
249bp_xbyte(struct bpf_packet *bp, bpf_u_int32 k, int *err)
250{
251 void * hdr = bp->bpfp_header;
252 size_t hdrlen = bp->bpfp_header_length;
253
254 switch (bp->bpfp_type) {
255 case BPF_PACKET_TYPE_MBUF:
256 return m_xbyte(bp->bpfp_mbuf, hdr, hdrlen, k, err);
257 default:
258 break;
259 }
260 *err = 1;
261 return 0;
262
263}
264
265#endif
266
267/*
268 * Execute the filter program starting at pc on the packet p
269 * wirelen is the length of the original packet
270 * buflen is the amount of data present
271 */
272u_int
273bpf_filter(const struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen)
274{
275 u_int32_t A = 0, X = 0;
276 bpf_u_int32 k;
277 int32_t mem[BPF_MEMWORDS];
278#ifdef KERNEL
279 int merr;
280 struct bpf_packet * bp = (struct bpf_packet *)(void *)p;
281#endif /* KERNEL */
282
283 bzero(mem, sizeof(mem));
284
285 if (pc == 0)
286 /*
287 * No filter means accept all.
288 */
289 return (u_int)-1;
290
291 --pc;
292 while (1) {
293 ++pc;
294 switch (pc->code) {
295
296 default:
297#ifdef KERNEL
298 return 0;
299#else /* KERNEL */
300 abort();
301#endif /* KERNEL */
302 case BPF_RET|BPF_K:
303 return (u_int)pc->k;
304
305 case BPF_RET|BPF_A:
306 return (u_int)A;
307
308 case BPF_LD|BPF_W|BPF_ABS:
309 k = pc->k;
310 if (k > buflen || sizeof(int32_t) > buflen - k) {
311#ifdef KERNEL
312 if (buflen != 0)
313 return 0;
314 A = bp_xword(bp, k, &merr);
315 if (merr != 0)
316 return 0;
317 continue;
318#else /* KERNEL */
319 return 0;
320#endif /* KERNEL */
321 }
322#if BPF_ALIGN
323 if (((intptr_t)(p + k) & 3) != 0)
324 A = EXTRACT_LONG(&p[k]);
325 else
326#endif /* BPF_ALIGN */
327 A = ntohl(*(int32_t *)(void *)(p + k));
328 continue;
329
330 case BPF_LD|BPF_H|BPF_ABS:
331 k = pc->k;
332 if (k > buflen || sizeof(int16_t) > buflen - k) {
333#ifdef KERNEL
334 if (buflen != 0)
335 return 0;
336 A = bp_xhalf(bp, k, &merr);
337 if (merr != 0)
338 return 0;
339 continue;
340#else /* KERNEL */
341 return 0;
342#endif /* KERNEL */
343 }
344 A = EXTRACT_SHORT(&p[k]);
345 continue;
346
347 case BPF_LD|BPF_B|BPF_ABS:
348 k = pc->k;
349 if (k >= buflen) {
350#ifdef KERNEL
351 if (buflen != 0)
352 return 0;
353 A = bp_xbyte(bp, k, &merr);
354 if (merr != 0)
355 return 0;
356 continue;
357#else /* KERNEL */
358 return 0;
359#endif /* KERNEL */
360 }
361 A = p[k];
362 continue;
363
364 case BPF_LD|BPF_W|BPF_LEN:
365 A = wirelen;
366 continue;
367
368 case BPF_LDX|BPF_W|BPF_LEN:
369 X = wirelen;
370 continue;
371
372 case BPF_LD|BPF_W|BPF_IND:
373 k = X + pc->k;
374 if (pc->k > buflen || X > buflen - pc->k ||
375 sizeof(int32_t) > buflen - k) {
376#ifdef KERNEL
377 if (buflen != 0)
378 return 0;
379 A = bp_xword(bp, k, &merr);
380 if (merr != 0)
381 return 0;
382 continue;
383#else /* KERNEL */
384 return 0;
385#endif /* KERNEL */
386 }
387#if BPF_ALIGN
388 if (((intptr_t)(p + k) & 3) != 0)
389 A = EXTRACT_LONG(&p[k]);
390 else
391#endif /* BPF_ALIGN */
392 A = ntohl(*(int32_t *)(void *)(p + k));
393 continue;
394
395 case BPF_LD|BPF_H|BPF_IND:
396 k = X + pc->k;
397 if (X > buflen || pc->k > buflen - X ||
398 sizeof(int16_t) > buflen - k) {
399#ifdef KERNEL
400 if (buflen != 0)
401 return 0;
402 A = bp_xhalf(bp, k, &merr);
403 if (merr != 0)
404 return 0;
405 continue;
406#else /* KERNEL */
407 return 0;
408#endif /* KERNEL */
409 }
410 A = EXTRACT_SHORT(&p[k]);
411 continue;
412
413 case BPF_LD|BPF_B|BPF_IND:
414 k = X + pc->k;
415 if (pc->k >= buflen || X >= buflen - pc->k) {
416#ifdef KERNEL
417 if (buflen != 0)
418 return 0;
419 A = bp_xbyte(bp, k, &merr);
420 if (merr != 0)
421 return 0;
422 continue;
423#else /* KERNEL */
424 return 0;
425#endif /* KERNEL */
426 }
427 A = p[k];
428 continue;
429
430 case BPF_LDX|BPF_MSH|BPF_B:
431 k = pc->k;
432 if (k >= buflen) {
433#ifdef KERNEL
434 if (buflen != 0)
435 return 0;
436 X = bp_xbyte(bp, k, &merr);
437 if (merr != 0)
438 return 0;
439 X = (X & 0xf) << 2;
440 continue;
441#else
442 return 0;
443#endif
444 }
445 X = (p[pc->k] & 0xf) << 2;
446 continue;
447
448 case BPF_LD|BPF_IMM:
449 A = pc->k;
450 continue;
451
452 case BPF_LDX|BPF_IMM:
453 X = pc->k;
454 continue;
455
456 case BPF_LD|BPF_MEM:
457 A = mem[pc->k];
458 continue;
459
460 case BPF_LDX|BPF_MEM:
461 X = mem[pc->k];
462 continue;
463
464 case BPF_ST:
465 if (pc->k >= BPF_MEMWORDS)
466 return 0;
467 mem[pc->k] = A;
468 continue;
469
470 case BPF_STX:
471 if (pc->k >= BPF_MEMWORDS)
472 return 0;
473 mem[pc->k] = X;
474 continue;
475
476 case BPF_JMP|BPF_JA:
477 pc += pc->k;
478 continue;
479
480 case BPF_JMP|BPF_JGT|BPF_K:
481 pc += (A > pc->k) ? pc->jt : pc->jf;
482 continue;
483
484 case BPF_JMP|BPF_JGE|BPF_K:
485 pc += (A >= pc->k) ? pc->jt : pc->jf;
486 continue;
487
488 case BPF_JMP|BPF_JEQ|BPF_K:
489 pc += (A == pc->k) ? pc->jt : pc->jf;
490 continue;
491
492 case BPF_JMP|BPF_JSET|BPF_K:
493 pc += (A & pc->k) ? pc->jt : pc->jf;
494 continue;
495
496 case BPF_JMP|BPF_JGT|BPF_X:
497 pc += (A > X) ? pc->jt : pc->jf;
498 continue;
499
500 case BPF_JMP|BPF_JGE|BPF_X:
501 pc += (A >= X) ? pc->jt : pc->jf;
502 continue;
503
504 case BPF_JMP|BPF_JEQ|BPF_X:
505 pc += (A == X) ? pc->jt : pc->jf;
506 continue;
507
508 case BPF_JMP|BPF_JSET|BPF_X:
509 pc += (A & X) ? pc->jt : pc->jf;
510 continue;
511
512 case BPF_ALU|BPF_ADD|BPF_X:
513 A += X;
514 continue;
515
516 case BPF_ALU|BPF_SUB|BPF_X:
517 A -= X;
518 continue;
519
520 case BPF_ALU|BPF_MUL|BPF_X:
521 A *= X;
522 continue;
523
524 case BPF_ALU|BPF_DIV|BPF_X:
525 if (X == 0)
526 return 0;
527 A /= X;
528 continue;
529
530 case BPF_ALU|BPF_AND|BPF_X:
531 A &= X;
532 continue;
533
534 case BPF_ALU|BPF_OR|BPF_X:
535 A |= X;
536 continue;
537
538 case BPF_ALU|BPF_LSH|BPF_X:
539 A <<= X;
540 continue;
541
542 case BPF_ALU|BPF_RSH|BPF_X:
543 A >>= X;
544 continue;
545
546 case BPF_ALU|BPF_ADD|BPF_K:
547 A += pc->k;
548 continue;
549
550 case BPF_ALU|BPF_SUB|BPF_K:
551 A -= pc->k;
552 continue;
553
554 case BPF_ALU|BPF_MUL|BPF_K:
555 A *= pc->k;
556 continue;
557
558 case BPF_ALU|BPF_DIV|BPF_K:
559 A /= pc->k;
560 continue;
561
562 case BPF_ALU|BPF_AND|BPF_K:
563 A &= pc->k;
564 continue;
565
566 case BPF_ALU|BPF_OR|BPF_K:
567 A |= pc->k;
568 continue;
569
570 case BPF_ALU|BPF_LSH|BPF_K:
571 A <<= pc->k;
572 continue;
573
574 case BPF_ALU|BPF_RSH|BPF_K:
575 A >>= pc->k;
576 continue;
577
578 case BPF_ALU|BPF_NEG:
579 A = -A;
580 continue;
581
582 case BPF_MISC|BPF_TAX:
583 X = A;
584 continue;
585
586 case BPF_MISC|BPF_TXA:
587 A = X;
588 continue;
589 }
590 }
591}
592
593#ifdef KERNEL
594/*
595 * Return true if the 'fcode' is a valid filter program.
596 * The constraints are that each jump be forward and to a valid
597 * code, that memory accesses are within valid ranges (to the
598 * extent that this can be checked statically; loads of packet data
599 * have to be, and are, also checked at run time), and that
600 * the code terminates with either an accept or reject.
601 *
602 * The kernel needs to be able to verify an application's filter code.
603 * Otherwise, a bogus program could easily crash the system.
604 */
605int
606bpf_validate(const struct bpf_insn *f, int len)
607{
608 u_int i, from;
609 const struct bpf_insn *p;
610
611 if (len < 1 || len > BPF_MAXINSNS)
612 return 0;
613
614 for (i = 0; i < ((u_int)len); ++i) {
615 p = &f[i];
616 switch (BPF_CLASS(p->code)) {
617 /*
618 * Check that memory operations use valid addresses
619 */
620 case BPF_LD:
621 case BPF_LDX:
622 switch (BPF_MODE(p->code)) {
623 case BPF_IMM:
624 break;
625 case BPF_ABS:
626 case BPF_IND:
627 case BPF_MSH:
628 /*
629 * More strict check with actual packet length
630 * is done runtime.
631 */
632 if (p->k >= bpf_maxbufsize)
633 return 0;
634 break;
635 case BPF_MEM:
636 if (p->k >= BPF_MEMWORDS)
637 return 0;
638 break;
639 case BPF_LEN:
640 break;
641 default:
642 return 0;
643 }
644 break;
645 case BPF_ST:
646 case BPF_STX:
647 if (p->k >= BPF_MEMWORDS)
648 return 0;
649 break;
650 case BPF_ALU:
651 switch (BPF_OP(p->code)) {
652 case BPF_ADD:
653 case BPF_SUB:
654 case BPF_MUL:
655 case BPF_OR:
656 case BPF_AND:
657 case BPF_LSH:
658 case BPF_RSH:
659 case BPF_NEG:
660 break;
661 case BPF_DIV:
662 /*
663 * Check for constant division by 0
664 */
665 if(BPF_SRC(p->code) == BPF_K && p->k == 0)
666 return 0;
667 break;
668 default:
669 return 0;
670 }
671 break;
672 case BPF_JMP:
673 /*
674 * Check that jumps are within the code block,
675 * and that unconditional branches don't go
676 * backwards as a result of an overflow.
677 * Unconditional branches have a 32-bit offset,
678 * so they could overflow; we check to make
679 * sure they don't. Conditional branches have
680 * an 8-bit offset, and the from address is
681 * less than equal to BPF_MAXINSNS, and we assume that
682 * BPF_MAXINSNS is sufficiently small that adding 255
683 * to it won't overlflow
684 *
685 * We know that len is <= BPF_MAXINSNS, and we
686 * assume that BPF_MAXINSNS is less than the maximum
687 * size of a u_int, so that i+1 doesn't overflow
688 */
689 from = i+1;
690 switch (BPF_OP(p->code)) {
691 case BPF_JA:
692 if (from + p->k < from || from + p->k >= ((u_int)len))
693 return 0;
694 break;
695 case BPF_JEQ:
696 case BPF_JGT:
697 case BPF_JGE:
698 case BPF_JSET:
699 if (from + p->jt >= ((u_int)len) || from + p->jf >= ((u_int)len))
700 return 0;
701 break;
702 default:
703 return 0;
704 }
705 break;
706 case BPF_RET:
707 break;
708 case BPF_MISC:
709 break;
710 default:
711 return 0;
712 }
713 }
714 return BPF_CLASS(f[len - 1].code) == BPF_RET;
715}
716#endif
717