sys/net/bpf_filter.c

   1 /*      $NetBSD: bpf_filter.c,v 1.34 2008/01/02 15:58:01 christos Exp $ */
   2
   3 /*-
   4  * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from the Stanford/CMU enet packet filter,
   8  * (net/enet.c) distributed as part of 4.3BSD, and code contributed
   9  * to Berkeley by Steven McCanne and Van Jacobson both of Lawrence
  10  * Berkeley Laboratory.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  * 3. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  *
  36  *      @(#)bpf_filter.c        8.1 (Berkeley) 6/10/93
  37  */
  38
  39 #include <sys/cdefs.h>
  40 __KERNEL_RCSID(0, "$NetBSD: bpf_filter.c,v 1.34 2008/01/02 15:58:01 christos Exp $");
  41
  42 #if 0
  43 #if !(defined(lint) || defined(KERNEL))
  44 static const char rcsid[] =
  45     "@(#) Header: bpf_filter.c,v 1.33 97/04/26 13:37:18 leres Exp  (LBL)";
  46 #endif
  47 #endif
  48
  49 #include <sys/param.h>
  50 #include <sys/time.h>
  51 #include <sys/endian.h>
  52
  53 #define EXTRACT_SHORT(p)        be16dec(p)
  54 #define EXTRACT_LONG(p)         be32dec(p)
  55
  56 #ifdef _KERNEL
  57 #include <sys/mbuf.h>
  58 #define MINDEX(len, m, k)               \
  59 {                                       \
  60         len = m->m_len;                 \
  61         while (k >= len) {              \
  62                 k -= len;               \
  63                 m = m->m_next;          \
  64                 if (m == 0)             \
  65                         return 0;       \
  66                 len = m->m_len;         \
  67         }                               \
  68 }
  69
  70 static int m_xword (struct mbuf *, uint32_t, int *);
  71 static int m_xhalf (struct mbuf *, uint32_t, int *);
  72
  73 static int
  74 m_xword(struct mbuf *m, uint32_t k, int *err)
  75 {
  76         int len;
  77         u_char *cp, *np;
  78         struct mbuf *m0;
  79
  80         *err = 1;
  81         MINDEX(len, m, k);
  82         cp = mtod(m, u_char *) + k;
  83         if (len >= k + 4) {
  84                 *err = 0;
  85                 return EXTRACT_LONG(cp);
  86         }
  87         m0 = m->m_next;
  88         if (m0 == 0 || m0->m_len + len - k < 4)
  89                 return 0;
  90         *err = 0;
  91         np = mtod(m0, u_char *);
  92         switch (len - k) {
  93
  94         case 1:
  95                 return (cp[0] << 24) | (np[0] << 16) | (np[1] << 8) | np[2];
  96
  97         case 2:
  98                 return (cp[0] << 24) | (cp[1] << 16) | (np[0] << 8) | np[1];
  99
 100         default:
 101                 return (cp[0] << 24) | (cp[1] << 16) | (cp[2] << 8) | np[0];
 102         }
 103 }
 104
 105 static int
 106 m_xhalf(struct mbuf *m, uint32_t k, int *err)
 107 {
 108         int len;
 109         u_char *cp;
 110         struct mbuf *m0;
 111
 112         *err = 1;
 113         MINDEX(len, m, k);
 114         cp = mtod(m, u_char *) + k;
 115         if (len >= k + 2) {
 116                 *err = 0;
 117                 return EXTRACT_SHORT(cp);
 118         }
 119         m0 = m->m_next;
 120         if (m0 == 0)
 121                 return 0;
 122         *err = 0;
 123         return (cp[0] << 8) | mtod(m0, u_char *)[0];
 124 }
 125 #else /* _KERNEL */
 126 #include <stdlib.h>
 127 #endif /* !_KERNEL */
 128
 129 #include <net/bpf.h>
 130
 131 /*
 132  * Execute the filter program starting at pc on the packet p
 133  * wirelen is the length of the original packet
 134  * buflen is the amount of data present
 135  */
 136 u_int
 137 bpf_filter(struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen)
 138 {
 139         uint32_t A, X, k;
 140         uint32_t mem[BPF_MEMWORDS];
 141
 142         if (pc == 0)
 143                 /*
 144                  * No filter means accept all.
 145                  */
 146                 return (u_int)-1;
 147         A = 0;
 148         X = 0;
 149         --pc;
 150         /* CONSTCOND */
 151         while (1) {
 152                 ++pc;
 153                 switch (pc->code) {
 154
 155                 default:
 156 #ifdef _KERNEL
 157                         return 0;
 158 #else
 159                         abort();
 160 #endif
 161                 case BPF_RET|BPF_K:
 162                         return (u_int)pc->k;
 163
 164                 case BPF_RET|BPF_A:
 165                         return (u_int)A;
 166
 167                 case BPF_LD|BPF_W|BPF_ABS:
 168                         k = pc->k;
 169                         if (k + sizeof(int32_t) > buflen) {
 170 #ifdef _KERNEL
 171                                 int merr = 0;   /* XXX: GCC */
 172
 173                                 if (buflen != 0)
 174                                         return 0;
 175                                 A = m_xword((struct mbuf *)p, k, &merr);
 176                                 if (merr != 0)
 177                                         return 0;
 178                                 continue;
 179 #else
 180                                 return 0;
 181 #endif
 182                         }
 183                         A = EXTRACT_LONG(&p[k]);
 184                         continue;
 185
 186                 case BPF_LD|BPF_H|BPF_ABS:
 187                         k = pc->k;
 188                         if (k + sizeof(int16_t) > buflen) {
 189 #ifdef _KERNEL
 190                                 int merr;
 191
 192                                 if (buflen != 0)
 193                                         return 0;
 194                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 195                                 if (merr != 0)
 196                                         return 0;
 197                                 continue;
 198 #else
 199                                 return 0;
 200 #endif
 201                         }
 202                         A = EXTRACT_SHORT(&p[k]);
 203                         continue;
 204
 205                 case BPF_LD|BPF_B|BPF_ABS:
 206                         k = pc->k;
 207                         if (k >= buflen) {
 208 #ifdef _KERNEL
 209                                 struct mbuf *m;
 210                                 int len;
 211
 212                                 if (buflen != 0)
 213                                         return 0;
 214                                 m = (struct mbuf *)p;
 215                                 MINDEX(len, m, k);
 216                                 A = mtod(m, u_char *)[k];
 217                                 continue;
 218 #else
 219                                 return 0;
 220 #endif
 221                         }
 222                         A = p[k];
 223                         continue;
 224
 225                 case BPF_LD|BPF_W|BPF_LEN:
 226                         A = wirelen;
 227                         continue;
 228
 229                 case BPF_LDX|BPF_W|BPF_LEN:
 230                         X = wirelen;
 231                         continue;
 232
 233                 case BPF_LD|BPF_W|BPF_IND:
 234                         k = X + pc->k;
 235                         if (k + sizeof(int32_t) > buflen) {
 236 #ifdef _KERNEL
 237                                 int merr = 0;   /* XXX: GCC */
 238
 239                                 if (buflen != 0)
 240                                         return 0;
 241                                 A = m_xword((struct mbuf *)p, k, &merr);
 242                                 if (merr != 0)
 243                                         return 0;
 244                                 continue;
 245 #else
 246                                 return 0;
 247 #endif
 248                         }
 249                         A = EXTRACT_LONG(&p[k]);
 250                         continue;
 251
 252                 case BPF_LD|BPF_H|BPF_IND:
 253                         k = X + pc->k;
 254                         if (k + sizeof(int16_t) > buflen) {
 255 #ifdef _KERNEL
 256                                 int merr = 0;   /* XXX: GCC */
 257
 258                                 if (buflen != 0)
 259                                         return 0;
 260                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 261                                 if (merr != 0)
 262                                         return 0;
 263                                 continue;
 264 #else
 265                                 return 0;
 266 #endif
 267                         }
 268                         A = EXTRACT_SHORT(&p[k]);
 269                         continue;
 270
 271                 case BPF_LD|BPF_B|BPF_IND:
 272                         k = X + pc->k;
 273                         if (k >= buflen) {
 274 #ifdef _KERNEL
 275                                 struct mbuf *m;
 276                                 int len;
 277
 278                                 if (buflen != 0)
 279                                         return 0;
 280                                 m = (struct mbuf *)p;
 281                                 MINDEX(len, m, k);
 282                                 A = mtod(m, u_char *)[k];
 283                                 continue;
 284 #else
 285                                 return 0;
 286 #endif
 287                         }
 288                         A = p[k];
 289                         continue;
 290
 291                 case BPF_LDX|BPF_MSH|BPF_B:
 292                         k = pc->k;
 293                         if (k >= buflen) {
 294 #ifdef _KERNEL
 295                                 struct mbuf *m;
 296                                 int len;
 297
 298                                 if (buflen != 0)
 299                                         return 0;
 300                                 m = (struct mbuf *)p;
 301                                 MINDEX(len, m, k);
 302                                 X = (mtod(m, char *)[k] & 0xf) << 2;
 303                                 continue;
 304 #else
 305                                 return 0;
 306 #endif
 307                         }
 308                         X = (p[pc->k] & 0xf) << 2;
 309                         continue;
 310
 311                 case BPF_LD|BPF_IMM:
 312                         A = pc->k;
 313                         continue;
 314
 315                 case BPF_LDX|BPF_IMM:
 316                         X = pc->k;
 317                         continue;
 318
 319                 case BPF_LD|BPF_MEM:
 320                         A = mem[pc->k];
 321                         continue;
 322
 323                 case BPF_LDX|BPF_MEM:
 324                         X = mem[pc->k];
 325                         continue;
 326
 327                 case BPF_ST:
 328                         mem[pc->k] = A;
 329                         continue;
 330
 331                 case BPF_STX:
 332                         mem[pc->k] = X;
 333                         continue;
 334
 335                 case BPF_JMP|BPF_JA:
 336                         pc += pc->k;
 337                         continue;
 338
 339                 case BPF_JMP|BPF_JGT|BPF_K:
 340                         pc += (A > pc->k) ? pc->jt : pc->jf;
 341                         continue;
 342
 343                 case BPF_JMP|BPF_JGE|BPF_K:
 344                         pc += (A >= pc->k) ? pc->jt : pc->jf;
 345                         continue;
 346
 347                 case BPF_JMP|BPF_JEQ|BPF_K:
 348                         pc += (A == pc->k) ? pc->jt : pc->jf;
 349                         continue;
 350
 351                 case BPF_JMP|BPF_JSET|BPF_K:
 352                         pc += (A & pc->k) ? pc->jt : pc->jf;
 353                         continue;
 354
 355                 case BPF_JMP|BPF_JGT|BPF_X:
 356                         pc += (A > X) ? pc->jt : pc->jf;
 357                         continue;
 358
 359                 case BPF_JMP|BPF_JGE|BPF_X:
 360                         pc += (A >= X) ? pc->jt : pc->jf;
 361                         continue;
 362
 363                 case BPF_JMP|BPF_JEQ|BPF_X:
 364                         pc += (A == X) ? pc->jt : pc->jf;
 365                         continue;
 366
 367                 case BPF_JMP|BPF_JSET|BPF_X:
 368                         pc += (A & X) ? pc->jt : pc->jf;
 369                         continue;
 370
 371                 case BPF_ALU|BPF_ADD|BPF_X:
 372                         A += X;
 373                         continue;
 374
 375                 case BPF_ALU|BPF_SUB|BPF_X:
 376                         A -= X;
 377                         continue;
 378
 379                 case BPF_ALU|BPF_MUL|BPF_X:
 380                         A *= X;
 381                         continue;
 382
 383                 case BPF_ALU|BPF_DIV|BPF_X:
 384                         if (X == 0)
 385                                 return 0;
 386                         A /= X;
 387                         continue;
 388
 389                 case BPF_ALU|BPF_AND|BPF_X:
 390                         A &= X;
 391                         continue;
 392
 393                 case BPF_ALU|BPF_OR|BPF_X:
 394                         A |= X;
 395                         continue;
 396
 397                 case BPF_ALU|BPF_LSH|BPF_X:
 398                         A <<= X;
 399                         continue;
 400
 401                 case BPF_ALU|BPF_RSH|BPF_X:
 402                         A >>= X;
 403                         continue;
 404
 405                 case BPF_ALU|BPF_ADD|BPF_K:
 406                         A += pc->k;
 407                         continue;
 408
 409                 case BPF_ALU|BPF_SUB|BPF_K:
 410                         A -= pc->k;
 411                         continue;
 412
 413                 case BPF_ALU|BPF_MUL|BPF_K:
 414                         A *= pc->k;
 415                         continue;
 416
 417                 case BPF_ALU|BPF_DIV|BPF_K:
 418                         A /= pc->k;
 419                         continue;
 420
 421                 case BPF_ALU|BPF_AND|BPF_K:
 422                         A &= pc->k;
 423                         continue;
 424
 425                 case BPF_ALU|BPF_OR|BPF_K:
 426                         A |= pc->k;
 427                         continue;
 428
 429                 case BPF_ALU|BPF_LSH|BPF_K:
 430                         A <<= pc->k;
 431                         continue;
 432
 433                 case BPF_ALU|BPF_RSH|BPF_K:
 434                         A >>= pc->k;
 435                         continue;
 436
 437                 case BPF_ALU|BPF_NEG:
 438                         A = -A;
 439                         continue;
 440
 441                 case BPF_MISC|BPF_TAX:
 442                         X = A;
 443                         continue;
 444
 445                 case BPF_MISC|BPF_TXA:
 446                         A = X;
 447                         continue;
 448                 }
 449         }
 450 }
 451
 452 #ifdef _KERNEL
 453 /*
 454  * Return true if the 'fcode' is a valid filter program.
 455  * The constraints are that each jump be forward and to a valid
 456  * code, that memory accesses are within valid ranges (to the
 457  * extent that this can be checked statically; loads of packet
 458  * data have to be, and are, also checked at run time), and that
 459  * the code terminates with either an accept or reject.
 460  *
 461  * The kernel needs to be able to verify an application's filter code.
 462  * Otherwise, a bogus program could easily crash the system.
 463  */
 464 int
 465 bpf_validate(struct bpf_insn *f, int len)
 466 {
 467         u_int i, from;
 468         struct bpf_insn *p;
 469
 470         if (len < 1 || len > BPF_MAXINSNS)
 471                 return 0;
 472
 473         for (i = 0; i < len; ++i) {
 474                 p = &f[i];
 475                 switch (BPF_CLASS(p->code)) {
 476                 /*
 477                  * Check that memory operations use valid addresses.
 478                  */
 479                 case BPF_LD:
 480                 case BPF_LDX:
 481                         switch (BPF_MODE(p->code)) {
 482                         case BPF_MEM:
 483                                 if (p->k >= BPF_MEMWORDS)
 484                                         return 0;
 485                                 break;
 486                         case BPF_ABS:
 487                         case BPF_IND:
 488                         case BPF_MSH:
 489                         case BPF_IMM:
 490                         case BPF_LEN:
 491                                 break;
 492                         default:
 493                                 return 0;
 494                         }
 495                         break;
 496                 case BPF_ST:
 497                 case BPF_STX:
 498                         if (p->k >= BPF_MEMWORDS)
 499                                 return 0;
 500                         break;
 501                 case BPF_ALU:
 502                         switch (BPF_OP(p->code)) {
 503                         case BPF_ADD:
 504                         case BPF_SUB:
 505                         case BPF_MUL:
 506                         case BPF_OR:
 507                         case BPF_AND:
 508                         case BPF_LSH:
 509                         case BPF_RSH:
 510                         case BPF_NEG:
 511                                 break;
 512                         case BPF_DIV:
 513                                 /*
 514                                  * Check for constant division by 0.
 515                                  */
 516                                 if (BPF_RVAL(p->code) == BPF_K && p->k == 0)
 517                                         return 0;
 518                                 break;
 519                         default:
 520                                 return 0;
 521                         }
 522                         break;
 523                 case BPF_JMP:
 524                         /*
 525                          * Check that jumps are within the code block,
 526                          * and that unconditional branches don't go
 527                          * backwards as a result of an overflow.
 528                          * Unconditional branches have a 32-bit offset,
 529                          * so they could overflow; we check to make
 530                          * sure they don't.  Conditional branches have
 531                          * an 8-bit offset, and the from address is <=
 532                          * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
 533                          * is sufficiently small that adding 255 to it
 534                          * won't overflow.
 535                          *
 536                          * We know that len is <= BPF_MAXINSNS, and we
 537                          * assume that BPF_MAXINSNS is < the maximum size
 538                          * of a u_int, so that i + 1 doesn't overflow.
 539                          */
 540                         from = i + 1;
 541                         switch (BPF_OP(p->code)) {
 542                         case BPF_JA:
 543                                 if (from + p->k < from || from + p->k >= len)
 544                                         return 0;
 545                                 break;
 546                         case BPF_JEQ:
 547                         case BPF_JGT:
 548                         case BPF_JGE:
 549                         case BPF_JSET:
 550                                 if (from + p->jt >= len || from + p->jf >= len)
 551                                         return 0;
 552                                 break;
 553                         default:
 554                                 return 0;
 555                         }
 556                         break;
 557                 case BPF_RET:
 558                         break;
 559                 case BPF_MISC:
 560                         break;
 561                 default:
 562                         return 0;
 563                 }
 564         }
 565
 566         return BPF_CLASS(f[len - 1].code) == BPF_RET;
 567 }
 568 #endif