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