contrib/libpcap/bpf/net/bpf_filter.c

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