bsd/net/bpf_filter.c

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