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