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