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