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.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 <net/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
 141 static int
 142 m_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
 177 static int
 178 m_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  */
 210 u_int
 211 bpf_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  */
 546 int
 547 bpf_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 }