sys/net/bpf_filter.c

   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