1 /* 2 * Copyright (c) 1990, 1991, 1993 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_filter.c 8.1 (Berkeley) 6/10/93 39 * 40 * $FreeBSD: src/sys/net/bpf_filter.c,v 1.17 1999/12/29 04:38:31 peter Exp $ 41 * $DragonFly: src/sys/net/bpf_filter.c,v 1.10 2008/01/02 12:30:34 sephe Exp $ 42 */ 43 44 #include <sys/systm.h> 45 #include <sys/param.h> 46 47 #if defined(sparc) || defined(mips) || defined(ibm032) 48 #define BPF_ALIGN 49 #endif 50 51 #ifndef BPF_ALIGN 52 #define EXTRACT_SHORT(p) ((u_int16_t)ntohs(*(u_int16_t *)p)) 53 #define EXTRACT_LONG(p) (ntohl(*(u_int32_t *)p)) 54 #else 55 #define EXTRACT_SHORT(p)\ 56 ((u_int16_t)\ 57 ((u_int16_t)*((u_char *)p+0)<<8|\ 58 (u_int16_t)*((u_char *)p+1)<<0)) 59 #define EXTRACT_LONG(p)\ 60 ((u_int32_t)*((u_char *)p+0)<<24|\ 61 (u_int32_t)*((u_char *)p+1)<<16|\ 62 (u_int32_t)*((u_char *)p+2)<<8|\ 63 (u_int32_t)*((u_char *)p+3)<<0) 64 #endif 65 66 #ifdef _KERNEL 67 #include <sys/mbuf.h> 68 #endif 69 #include <net/bpf.h> 70 #ifdef _KERNEL 71 #define MINDEX(m, k) \ 72 { \ 73 int len = m->m_len; \ 74 \ 75 while (k >= len) { \ 76 k -= len; \ 77 m = m->m_next; \ 78 if (m == 0) \ 79 return 0; \ 80 len = m->m_len; \ 81 } \ 82 } 83 84 extern int bpf_maxbufsize; 85 86 static u_int16_t m_xhalf (struct mbuf *m, bpf_u_int32 k, int *err); 87 static u_int32_t m_xword (struct mbuf *m, bpf_u_int32 k, int *err); 88 89 static u_int32_t 90 m_xword(struct mbuf *m, bpf_u_int32 k, int *err) 91 { 92 size_t len; 93 u_char *cp, *np; 94 struct mbuf *m0; 95 96 len = m->m_len; 97 while (k >= len) { 98 k -= len; 99 m = m->m_next; 100 if (m == 0) 101 goto bad; 102 len = m->m_len; 103 } 104 cp = mtod(m, u_char *) + k; 105 if (len - k >= 4) { 106 *err = 0; 107 return EXTRACT_LONG(cp); 108 } 109 m0 = m->m_next; 110 if (m0 == 0 || m0->m_len + len - k < 4) 111 goto bad; 112 *err = 0; 113 np = mtod(m0, u_char *); 114 switch (len - k) { 115 116 case 1: 117 return 118 ((u_int32_t)cp[0] << 24) | 119 ((u_int32_t)np[0] << 16) | 120 ((u_int32_t)np[1] << 8) | 121 (u_int32_t)np[2]; 122 123 case 2: 124 return 125 ((u_int32_t)cp[0] << 24) | 126 ((u_int32_t)cp[1] << 16) | 127 ((u_int32_t)np[0] << 8) | 128 (u_int32_t)np[1]; 129 130 default: 131 return 132 ((u_int32_t)cp[0] << 24) | 133 ((u_int32_t)cp[1] << 16) | 134 ((u_int32_t)cp[2] << 8) | 135 (u_int32_t)np[0]; 136 } 137 bad: 138 *err = 1; 139 return 0; 140 } 141 142 static u_int16_t 143 m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err) 144 { 145 size_t len; 146 u_char *cp; 147 struct mbuf *m0; 148 149 len = m->m_len; 150 while (k >= len) { 151 k -= len; 152 m = m->m_next; 153 if (m == 0) 154 goto bad; 155 len = m->m_len; 156 } 157 cp = mtod(m, u_char *) + k; 158 if (len - k >= 2) { 159 *err = 0; 160 return EXTRACT_SHORT(cp); 161 } 162 m0 = m->m_next; 163 if (m0 == 0) 164 goto bad; 165 *err = 0; 166 return (cp[0] << 8) | mtod(m0, u_char *)[0]; 167 bad: 168 *err = 1; 169 return 0; 170 } 171 #endif 172 173 /* 174 * Execute the filter program starting at pc on the packet p 175 * wirelen is the length of the original packet 176 * buflen is the amount of data present 177 */ 178 u_int 179 bpf_filter(const struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen) 180 { 181 u_int32_t A = 0, X = 0; 182 bpf_u_int32 k; 183 int32_t mem[BPF_MEMWORDS]; 184 185 bzero(mem, sizeof(mem)); 186 187 if (pc == 0) { 188 /* 189 * No filter means accept all. 190 */ 191 return (u_int)-1; 192 } 193 194 --pc; 195 while (1) { 196 ++pc; 197 switch (pc->code) { 198 199 default: 200 #ifdef _KERNEL 201 return 0; 202 #else 203 abort(); 204 #endif 205 case BPF_RET|BPF_K: 206 return (u_int)pc->k; 207 208 case BPF_RET|BPF_A: 209 return (u_int)A; 210 211 case BPF_LD|BPF_W|BPF_ABS: 212 k = pc->k; 213 if (k > buflen || sizeof(int32_t) > buflen - k) { 214 #ifdef _KERNEL 215 int merr; 216 217 if (buflen != 0) 218 return 0; 219 A = m_xword((struct mbuf *)p, k, &merr); 220 if (merr != 0) 221 return 0; 222 continue; 223 #else 224 return 0; 225 #endif 226 } 227 #ifdef BPF_ALIGN 228 if (((intptr_t)(p + k) & 3) != 0) 229 A = EXTRACT_LONG(&p[k]); 230 else 231 #endif 232 A = ntohl(*(int32_t *)(p + k)); 233 continue; 234 235 case BPF_LD|BPF_H|BPF_ABS: 236 k = pc->k; 237 if (k > buflen || sizeof(int16_t) > buflen - k) { 238 #ifdef _KERNEL 239 int merr; 240 241 if (buflen != 0) 242 return 0; 243 A = m_xhalf((struct mbuf *)p, k, &merr); 244 continue; 245 #else 246 return 0; 247 #endif 248 } 249 A = EXTRACT_SHORT(&p[k]); 250 continue; 251 252 case BPF_LD|BPF_B|BPF_ABS: 253 k = pc->k; 254 if (k >= buflen) { 255 #ifdef _KERNEL 256 struct mbuf *m; 257 258 if (buflen != 0) 259 return 0; 260 m = (struct mbuf *)p; 261 MINDEX(m, k); 262 A = mtod(m, u_char *)[k]; 263 continue; 264 #else 265 return 0; 266 #endif 267 } 268 A = p[k]; 269 continue; 270 271 case BPF_LD|BPF_W|BPF_LEN: 272 A = wirelen; 273 continue; 274 275 case BPF_LDX|BPF_W|BPF_LEN: 276 X = wirelen; 277 continue; 278 279 case BPF_LD|BPF_W|BPF_IND: 280 k = X + pc->k; 281 if (pc->k > buflen || X > buflen - pc->k || 282 sizeof(int32_t) > buflen - k) { 283 #ifdef _KERNEL 284 int merr; 285 286 if (buflen != 0) 287 return 0; 288 A = m_xword((struct mbuf *)p, k, &merr); 289 if (merr != 0) 290 return 0; 291 continue; 292 #else 293 return 0; 294 #endif 295 } 296 #ifdef BPF_ALIGN 297 if (((intptr_t)(p + k) & 3) != 0) 298 A = EXTRACT_LONG(&p[k]); 299 else 300 #endif 301 A = ntohl(*(int32_t *)(p + k)); 302 continue; 303 304 case BPF_LD|BPF_H|BPF_IND: 305 k = X + pc->k; 306 if (X > buflen || pc->k > buflen - X || 307 sizeof(int16_t) > buflen - k) { 308 #ifdef _KERNEL 309 int merr; 310 311 if (buflen != 0) 312 return 0; 313 A = m_xhalf((struct mbuf *)p, k, &merr); 314 if (merr != 0) 315 return 0; 316 continue; 317 #else 318 return 0; 319 #endif 320 } 321 A = EXTRACT_SHORT(&p[k]); 322 continue; 323 324 case BPF_LD|BPF_B|BPF_IND: 325 k = X + pc->k; 326 if (pc->k >= buflen || X >= buflen - pc->k) { 327 #ifdef _KERNEL 328 struct mbuf *m; 329 330 if (buflen != 0) 331 return 0; 332 m = (struct mbuf *)p; 333 MINDEX(m, k); 334 A = mtod(m, u_char *)[k]; 335 continue; 336 #else 337 return 0; 338 #endif 339 } 340 A = p[k]; 341 continue; 342 343 case BPF_LDX|BPF_MSH|BPF_B: 344 k = pc->k; 345 if (k >= buflen) { 346 #ifdef _KERNEL 347 struct mbuf *m; 348 349 if (buflen != 0) 350 return 0; 351 m = (struct mbuf *)p; 352 MINDEX(m, k); 353 X = (mtod(m, char *)[k] & 0xf) << 2; 354 continue; 355 #else 356 return 0; 357 #endif 358 } 359 X = (p[pc->k] & 0xf) << 2; 360 continue; 361 362 case BPF_LD|BPF_IMM: 363 A = pc->k; 364 continue; 365 366 case BPF_LDX|BPF_IMM: 367 X = pc->k; 368 continue; 369 370 case BPF_LD|BPF_MEM: 371 A = mem[pc->k]; 372 continue; 373 374 case BPF_LDX|BPF_MEM: 375 X = mem[pc->k]; 376 continue; 377 378 case BPF_ST: 379 mem[pc->k] = A; 380 continue; 381 382 case BPF_STX: 383 mem[pc->k] = X; 384 continue; 385 386 case BPF_JMP|BPF_JA: 387 pc += pc->k; 388 continue; 389 390 case BPF_JMP|BPF_JGT|BPF_K: 391 pc += (A > pc->k) ? pc->jt : pc->jf; 392 continue; 393 394 case BPF_JMP|BPF_JGE|BPF_K: 395 pc += (A >= pc->k) ? pc->jt : pc->jf; 396 continue; 397 398 case BPF_JMP|BPF_JEQ|BPF_K: 399 pc += (A == pc->k) ? pc->jt : pc->jf; 400 continue; 401 402 case BPF_JMP|BPF_JSET|BPF_K: 403 pc += (A & pc->k) ? pc->jt : pc->jf; 404 continue; 405 406 case BPF_JMP|BPF_JGT|BPF_X: 407 pc += (A > X) ? pc->jt : pc->jf; 408 continue; 409 410 case BPF_JMP|BPF_JGE|BPF_X: 411 pc += (A >= X) ? pc->jt : pc->jf; 412 continue; 413 414 case BPF_JMP|BPF_JEQ|BPF_X: 415 pc += (A == X) ? pc->jt : pc->jf; 416 continue; 417 418 case BPF_JMP|BPF_JSET|BPF_X: 419 pc += (A & X) ? pc->jt : pc->jf; 420 continue; 421 422 case BPF_ALU|BPF_ADD|BPF_X: 423 A += X; 424 continue; 425 426 case BPF_ALU|BPF_SUB|BPF_X: 427 A -= X; 428 continue; 429 430 case BPF_ALU|BPF_MUL|BPF_X: 431 A *= X; 432 continue; 433 434 case BPF_ALU|BPF_DIV|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_LSH|BPF_X: 449 A <<= X; 450 continue; 451 452 case BPF_ALU|BPF_RSH|BPF_X: 453 A >>= X; 454 continue; 455 456 case BPF_ALU|BPF_ADD|BPF_K: 457 A += pc->k; 458 continue; 459 460 case BPF_ALU|BPF_SUB|BPF_K: 461 A -= pc->k; 462 continue; 463 464 case BPF_ALU|BPF_MUL|BPF_K: 465 A *= pc->k; 466 continue; 467 468 case BPF_ALU|BPF_DIV|BPF_K: 469 A /= pc->k; 470 continue; 471 472 case BPF_ALU|BPF_AND|BPF_K: 473 A &= pc->k; 474 continue; 475 476 case BPF_ALU|BPF_OR|BPF_K: 477 A |= pc->k; 478 continue; 479 480 case BPF_ALU|BPF_LSH|BPF_K: 481 A <<= pc->k; 482 continue; 483 484 case BPF_ALU|BPF_RSH|BPF_K: 485 A >>= pc->k; 486 continue; 487 488 case BPF_ALU|BPF_NEG: 489 A = -A; 490 continue; 491 492 case BPF_MISC|BPF_TAX: 493 X = A; 494 continue; 495 496 case BPF_MISC|BPF_TXA: 497 A = X; 498 continue; 499 } 500 } 501 } 502 503 #ifdef _KERNEL 504 /* 505 * Return true if the 'fcode' is a valid filter program. 506 * The constraints are that each jump be forward and to a valid 507 * code, that memory accesses are within valid ranges (to the 508 * extent that this can be checked statically; loads of packet 509 * data have to be, and are, also checked at run time), and that 510 * the code terminates with either an accept or reject. 511 * 512 * The kernel needs to be able to verify an application's filter code. 513 * Otherwise, a bogus program could easily crash the system. 514 */ 515 int 516 bpf_validate(const struct bpf_insn *f, int len) 517 { 518 u_int i, from; 519 const struct bpf_insn *p; 520 521 if (len < 1 || len > BPF_MAXINSNS) 522 return 0; 523 524 for (i = 0; i < len; ++i) { 525 p = &f[i]; 526 switch (BPF_CLASS(p->code)) { 527 /* 528 * Check that memory operations use valid addresses. 529 */ 530 case BPF_LD: 531 case BPF_LDX: 532 switch (BPF_MODE(p->code)) { 533 case BPF_IMM: 534 break; 535 case BPF_ABS: 536 case BPF_IND: 537 case BPF_MSH: 538 /* 539 * More strict check with actual packet length 540 * is done runtime. 541 */ 542 if (p->k >= bpf_maxbufsize) 543 return 0; 544 break; 545 case BPF_MEM: 546 if (p->k >= BPF_MEMWORDS) 547 return 0; 548 break; 549 case BPF_LEN: 550 break; 551 default: 552 return 0; 553 } 554 break; 555 case BPF_ST: 556 case BPF_STX: 557 if (p->k >= BPF_MEMWORDS) 558 return 0; 559 break; 560 case BPF_ALU: 561 switch (BPF_OP(p->code)) { 562 case BPF_ADD: 563 case BPF_SUB: 564 case BPF_MUL: 565 case BPF_OR: 566 case BPF_AND: 567 case BPF_LSH: 568 case BPF_RSH: 569 case BPF_NEG: 570 break; 571 case BPF_DIV: 572 /* 573 * Check for constant division by 0. 574 */ 575 if (BPF_SRC(p->code) == BPF_K && p->k == 0) 576 return 0; 577 break; 578 default: 579 return 0; 580 } 581 break; 582 case BPF_JMP: 583 /* 584 * Check that jumps are within the code block, 585 * and that unconditional branches don't go 586 * backwards as a result of an overflow. 587 * Unconditional branches have a 32-bit offset, 588 * so they could overflow; we check to make 589 * sure they don't. Conditional branches have 590 * an 8-bit offset, and the from address is <= 591 * BPF_MAXINSNS, and we assume that BPF_MAXINSNS 592 * is sufficiently small that adding 255 to it 593 * won't overflow. 594 * 595 * We know that len is <= BPF_MAXINSNS, and we 596 * assume that BPF_MAXINSNS is < the maximum size 597 * of a u_int, so that i + 1 doesn't overflow. 598 */ 599 from = i + 1; 600 switch (BPF_OP(p->code)) { 601 case BPF_JA: 602 if (from + p->k < from || from + p->k >= len) 603 return 0; 604 break; 605 case BPF_JEQ: 606 case BPF_JGT: 607 case BPF_JGE: 608 case BPF_JSET: 609 if (from + p->jt >= len || from + p->jf >= len) 610 return 0; 611 break; 612 default: 613 return 0; 614 } 615 break; 616 case BPF_RET: 617 break; 618 case BPF_MISC: 619 break; 620 default: 621 return 0; 622 } 623 } 624 return BPF_CLASS(f[len - 1].code) == BPF_RET; 625 } 626 #endif 627