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
  37 #include <sys/cdefs.h>
  38 __FBSDID("$FreeBSD$");
  39
  40 #include <sys/param.h>
  41
  42 #if !defined(_KERNEL)
  43 #include <strings.h>
  44 #endif
  45 #if !defined(_KERNEL) || defined(sun)
  46 #include <netinet/in.h>
  47 #endif
  48
  49 #ifndef __i386__
  50 #define BPF_ALIGN
  51 #endif
  52
  53 #ifndef BPF_ALIGN
  54 #define EXTRACT_SHORT(p)        ((u_int16_t)ntohs(*(u_int16_t *)p))
  55 #define EXTRACT_LONG(p)         (ntohl(*(u_int32_t *)p))
  56 #else
  57 #define EXTRACT_SHORT(p)\
  58         ((u_int16_t)\
  59                 ((u_int16_t)*((u_char *)p+0)<<8|\
  60                  (u_int16_t)*((u_char *)p+1)<<0))
  61 #define EXTRACT_LONG(p)\
  62                 ((u_int32_t)*((u_char *)p+0)<<24|\
  63                  (u_int32_t)*((u_char *)p+1)<<16|\
  64                  (u_int32_t)*((u_char *)p+2)<<8|\
  65                  (u_int32_t)*((u_char *)p+3)<<0)
  66 #endif
  67
  68 #ifdef _KERNEL
  69 #include <sys/mbuf.h>
  70 #else
  71 #include <stdlib.h>
  72 #endif
  73 #include <net/bpf.h>
  74 #ifdef _KERNEL
  75 #define MINDEX(m, k) \
  76 { \
  77         register int len = m->m_len; \
  78  \
  79         while (k >= len) { \
  80                 k -= len; \
  81                 m = m->m_next; \
  82                 if (m == 0) \
  83                         return (0); \
  84                 len = m->m_len; \
  85         } \
  86 }
  87
  88 static u_int16_t        m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err);
  89 static u_int32_t        m_xword(struct mbuf *m, bpf_u_int32 k, int *err);
  90
  91 static u_int32_t
  92 m_xword(struct mbuf *m, bpf_u_int32 k, int *err)
  93 {
  94         size_t len;
  95         u_char *cp, *np;
  96         struct mbuf *m0;
  97
  98         len = m->m_len;
  99         while (k >= len) {
 100                 k -= len;
 101                 m = m->m_next;
 102                 if (m == 0)
 103                         goto bad;
 104                 len = m->m_len;
 105         }
 106         cp = mtod(m, u_char *) + k;
 107         if (len - k >= 4) {
 108                 *err = 0;
 109                 return (EXTRACT_LONG(cp));
 110         }
 111         m0 = m->m_next;
 112         if (m0 == 0 || m0->m_len + len - k < 4)
 113                 goto bad;
 114         *err = 0;
 115         np = mtod(m0, u_char *);
 116         switch (len - k) {
 117         case 1:
 118                 return (((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 (((u_int32_t)cp[0] << 24) |
 125                     ((u_int32_t)cp[1] << 16) |
 126                     ((u_int32_t)np[0] << 8) |
 127                     (u_int32_t)np[1]);
 128
 129         default:
 130                 return (((u_int32_t)cp[0] << 24) |
 131                     ((u_int32_t)cp[1] << 16) |
 132                     ((u_int32_t)cp[2] << 8) |
 133                     (u_int32_t)np[0]);
 134         }
 135     bad:
 136         *err = 1;
 137         return (0);
 138 }
 139
 140 static u_int16_t
 141 m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err)
 142 {
 143         size_t len;
 144         u_char *cp;
 145         struct mbuf *m0;
 146
 147         len = m->m_len;
 148         while (k >= len) {
 149                 k -= len;
 150                 m = m->m_next;
 151                 if (m == 0)
 152                         goto bad;
 153                 len = m->m_len;
 154         }
 155         cp = mtod(m, u_char *) + k;
 156         if (len - k >= 2) {
 157                 *err = 0;
 158                 return (EXTRACT_SHORT(cp));
 159         }
 160         m0 = m->m_next;
 161         if (m0 == 0)
 162                 goto bad;
 163         *err = 0;
 164         return ((cp[0] << 8) | mtod(m0, u_char *)[0]);
 165  bad:
 166         *err = 1;
 167         return (0);
 168 }
 169 #endif
 170
 171 /*
 172  * Execute the filter program starting at pc on the packet p
 173  * wirelen is the length of the original packet
 174  * buflen is the amount of data present
 175  */
 176 u_int
 177 bpf_filter(const struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen)
 178 {
 179         u_int32_t A = 0, X = 0;
 180         bpf_u_int32 k;
 181         u_int32_t mem[BPF_MEMWORDS];
 182
 183         bzero(mem, sizeof(mem));
 184
 185         if (pc == NULL)
 186                 /*
 187                  * No filter means accept all.
 188                  */
 189                 return ((u_int)-1);
 190
 191         --pc;
 192         while (1) {
 193                 ++pc;
 194                 switch (pc->code) {
 195                 default:
 196 #ifdef _KERNEL
 197                         return (0);
 198 #else
 199                         abort();
 200 #endif
 201
 202                 case BPF_RET|BPF_K:
 203                         return ((u_int)pc->k);
 204
 205                 case BPF_RET|BPF_A:
 206                         return ((u_int)A);
 207
 208                 case BPF_LD|BPF_W|BPF_ABS:
 209                         k = pc->k;
 210                         if (k > buflen || sizeof(int32_t) > buflen - k) {
 211 #ifdef _KERNEL
 212                                 int merr;
 213
 214                                 if (buflen != 0)
 215                                         return (0);
 216                                 A = m_xword((struct mbuf *)p, k, &merr);
 217                                 if (merr != 0)
 218                                         return (0);
 219                                 continue;
 220 #else
 221                                 return (0);
 222 #endif
 223                         }
 224 #ifdef BPF_ALIGN
 225                         if (((intptr_t)(p + k) & 3) != 0)
 226                                 A = EXTRACT_LONG(&p[k]);
 227                         else
 228 #endif
 229                                 A = ntohl(*(int32_t *)(p + k));
 230                         continue;
 231
 232                 case BPF_LD|BPF_H|BPF_ABS:
 233                         k = pc->k;
 234                         if (k > buflen || sizeof(int16_t) > buflen - k) {
 235 #ifdef _KERNEL
 236                                 int merr;
 237
 238                                 if (buflen != 0)
 239                                         return (0);
 240                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 241                                 continue;
 242 #else
 243                                 return (0);
 244 #endif
 245                         }
 246                         A = EXTRACT_SHORT(&p[k]);
 247                         continue;
 248
 249                 case BPF_LD|BPF_B|BPF_ABS:
 250                         k = pc->k;
 251                         if (k >= buflen) {
 252 #ifdef _KERNEL
 253                                 struct mbuf *m;
 254
 255                                 if (buflen != 0)
 256                                         return (0);
 257                                 m = (struct mbuf *)p;
 258                                 MINDEX(m, k);
 259                                 A = mtod(m, u_char *)[k];
 260                                 continue;
 261 #else
 262                                 return (0);
 263 #endif
 264                         }
 265                         A = p[k];
 266                         continue;
 267
 268                 case BPF_LD|BPF_W|BPF_LEN:
 269                         A = wirelen;
 270                         continue;
 271
 272                 case BPF_LDX|BPF_W|BPF_LEN:
 273                         X = wirelen;
 274                         continue;
 275
 276                 case BPF_LD|BPF_W|BPF_IND:
 277                         k = X + pc->k;
 278                         if (pc->k > buflen || X > buflen - pc->k ||
 279                             sizeof(int32_t) > buflen - k) {
 280 #ifdef _KERNEL
 281                                 int merr;
 282
 283                                 if (buflen != 0)
 284                                         return (0);
 285                                 A = m_xword((struct mbuf *)p, k, &merr);
 286                                 if (merr != 0)
 287                                         return (0);
 288                                 continue;
 289 #else
 290                                 return (0);
 291 #endif
 292                         }
 293 #ifdef BPF_ALIGN
 294                         if (((intptr_t)(p + k) & 3) != 0)
 295                                 A = EXTRACT_LONG(&p[k]);
 296                         else
 297 #endif
 298                                 A = ntohl(*(int32_t *)(p + k));
 299                         continue;
 300
 301                 case BPF_LD|BPF_H|BPF_IND:
 302                         k = X + pc->k;
 303                         if (X > buflen || pc->k > buflen - X ||
 304                             sizeof(int16_t) > buflen - k) {
 305 #ifdef _KERNEL
 306                                 int merr;
 307
 308                                 if (buflen != 0)
 309                                         return (0);
 310                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 311                                 if (merr != 0)
 312                                         return (0);
 313                                 continue;
 314 #else
 315                                 return (0);
 316 #endif
 317                         }
 318                         A = EXTRACT_SHORT(&p[k]);
 319                         continue;
 320
 321                 case BPF_LD|BPF_B|BPF_IND:
 322                         k = X + pc->k;
 323                         if (pc->k >= buflen || X >= buflen - pc->k) {
 324 #ifdef _KERNEL
 325                                 struct mbuf *m;
 326
 327                                 if (buflen != 0)
 328                                         return (0);
 329                                 m = (struct mbuf *)p;
 330                                 MINDEX(m, k);
 331                                 A = mtod(m, u_char *)[k];
 332                                 continue;
 333 #else
 334                                 return (0);
 335 #endif
 336                         }
 337                         A = p[k];
 338                         continue;
 339
 340                 case BPF_LDX|BPF_MSH|BPF_B:
 341                         k = pc->k;
 342                         if (k >= buflen) {
 343 #ifdef _KERNEL
 344                                 register struct mbuf *m;
 345
 346                                 if (buflen != 0)
 347                                         return (0);
 348                                 m = (struct mbuf *)p;
 349                                 MINDEX(m, k);
 350                                 X = (mtod(m, u_char *)[k] & 0xf) << 2;
 351                                 continue;
 352 #else
 353                                 return (0);
 354 #endif
 355                         }
 356                         X = (p[pc->k] & 0xf) << 2;
 357                         continue;
 358
 359                 case BPF_LD|BPF_IMM:
 360                         A = pc->k;
 361                         continue;
 362
 363                 case BPF_LDX|BPF_IMM:
 364                         X = pc->k;
 365                         continue;
 366
 367                 case BPF_LD|BPF_MEM:
 368                         A = mem[pc->k];
 369                         continue;
 370
 371                 case BPF_LDX|BPF_MEM:
 372                         X = mem[pc->k];
 373                         continue;
 374
 375                 case BPF_ST:
 376                         mem[pc->k] = A;
 377                         continue;
 378
 379                 case BPF_STX:
 380                         mem[pc->k] = X;
 381                         continue;
 382
 383                 case BPF_JMP|BPF_JA:
 384                         pc += pc->k;
 385                         continue;
 386
 387                 case BPF_JMP|BPF_JGT|BPF_K:
 388                         pc += (A > pc->k) ? pc->jt : pc->jf;
 389                         continue;
 390
 391                 case BPF_JMP|BPF_JGE|BPF_K:
 392                         pc += (A >= pc->k) ? pc->jt : pc->jf;
 393                         continue;
 394
 395                 case BPF_JMP|BPF_JEQ|BPF_K:
 396                         pc += (A == pc->k) ? pc->jt : pc->jf;
 397                         continue;
 398
 399                 case BPF_JMP|BPF_JSET|BPF_K:
 400                         pc += (A & pc->k) ? pc->jt : pc->jf;
 401                         continue;
 402
 403                 case BPF_JMP|BPF_JGT|BPF_X:
 404                         pc += (A > X) ? pc->jt : pc->jf;
 405                         continue;
 406
 407                 case BPF_JMP|BPF_JGE|BPF_X:
 408                         pc += (A >= X) ? pc->jt : pc->jf;
 409                         continue;
 410
 411                 case BPF_JMP|BPF_JEQ|BPF_X:
 412                         pc += (A == X) ? pc->jt : pc->jf;
 413                         continue;
 414
 415                 case BPF_JMP|BPF_JSET|BPF_X:
 416                         pc += (A & X) ? pc->jt : pc->jf;
 417                         continue;
 418
 419                 case BPF_ALU|BPF_ADD|BPF_X:
 420                         A += X;
 421                         continue;
 422
 423                 case BPF_ALU|BPF_SUB|BPF_X:
 424                         A -= X;
 425                         continue;
 426
 427                 case BPF_ALU|BPF_MUL|BPF_X:
 428                         A *= X;
 429                         continue;
 430
 431                 case BPF_ALU|BPF_DIV|BPF_X:
 432                         if (X == 0)
 433                                 return (0);
 434                         A /= X;
 435                         continue;
 436
 437                 case BPF_ALU|BPF_AND|BPF_X:
 438                         A &= X;
 439                         continue;
 440
 441                 case BPF_ALU|BPF_OR|BPF_X:
 442                         A |= X;
 443                         continue;
 444
 445                 case BPF_ALU|BPF_LSH|BPF_X:
 446                         A <<= X;
 447                         continue;
 448
 449                 case BPF_ALU|BPF_RSH|BPF_X:
 450                         A >>= X;
 451                         continue;
 452
 453                 case BPF_ALU|BPF_ADD|BPF_K:
 454                         A += pc->k;
 455                         continue;
 456
 457                 case BPF_ALU|BPF_SUB|BPF_K:
 458                         A -= pc->k;
 459                         continue;
 460
 461                 case BPF_ALU|BPF_MUL|BPF_K:
 462                         A *= pc->k;
 463                         continue;
 464
 465                 case BPF_ALU|BPF_DIV|BPF_K:
 466                         A /= pc->k;
 467                         continue;
 468
 469                 case BPF_ALU|BPF_AND|BPF_K:
 470                         A &= pc->k;
 471                         continue;
 472
 473                 case BPF_ALU|BPF_OR|BPF_K:
 474                         A |= pc->k;
 475                         continue;
 476
 477                 case BPF_ALU|BPF_LSH|BPF_K:
 478                         A <<= pc->k;
 479                         continue;
 480
 481                 case BPF_ALU|BPF_RSH|BPF_K:
 482                         A >>= pc->k;
 483                         continue;
 484
 485                 case BPF_ALU|BPF_NEG:
 486                         A = -A;
 487                         continue;
 488
 489                 case BPF_MISC|BPF_TAX:
 490                         X = A;
 491                         continue;
 492
 493                 case BPF_MISC|BPF_TXA:
 494                         A = X;
 495                         continue;
 496                 }
 497         }
 498 }
 499
 500 #ifdef _KERNEL
 501 static const u_short    bpf_code_map[] = {
 502         0x10ff, /* 0x00-0x0f: 1111111100001000 */
 503         0x3070, /* 0x10-0x1f: 0000111000001100 */
 504         0x3131, /* 0x20-0x2f: 1000110010001100 */
 505         0x3031, /* 0x30-0x3f: 1000110000001100 */
 506         0x3131, /* 0x40-0x4f: 1000110010001100 */
 507         0x1011, /* 0x50-0x5f: 1000100000001000 */
 508         0x1013, /* 0x60-0x6f: 1100100000001000 */
 509         0x1010, /* 0x70-0x7f: 0000100000001000 */
 510         0x0093, /* 0x80-0x8f: 1100100100000000 */
 511         0x0000, /* 0x90-0x9f: 0000000000000000 */
 512         0x0000, /* 0xa0-0xaf: 0000000000000000 */
 513         0x0002, /* 0xb0-0xbf: 0100000000000000 */
 514         0x0000, /* 0xc0-0xcf: 0000000000000000 */
 515         0x0000, /* 0xd0-0xdf: 0000000000000000 */
 516         0x0000, /* 0xe0-0xef: 0000000000000000 */
 517         0x0000  /* 0xf0-0xff: 0000000000000000 */
 518 };
 519
 520 #define BPF_VALIDATE_CODE(c)    \
 521     ((c) <= 0xff && (bpf_code_map[(c) >> 4] & (1 << ((c) & 0xf))) != 0)
 522
 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  *
 528  * The kernel needs to be able to verify an application's filter code.
 529  * Otherwise, a bogus program could easily crash the system.
 530  */
 531 int
 532 bpf_validate(const struct bpf_insn *f, int len)
 533 {
 534         register int i;
 535         register const struct bpf_insn *p;
 536
 537         /* Do not accept negative length filter. */
 538         if (len < 0)
 539                 return (0);
 540
 541         /* An empty filter means accept all. */
 542         if (len == 0)
 543                 return (1);
 544
 545         for (i = 0; i < len; ++i) {
 546                 p = &f[i];
 547                 /*
 548                  * Check that the code is valid.
 549                  */
 550                 if (!BPF_VALIDATE_CODE(p->code))
 551                         return (0);
 552                 /*
 553                  * Check that that jumps are forward, and within
 554                  * the code block.
 555                  */
 556                 if (BPF_CLASS(p->code) == BPF_JMP) {
 557                         register u_int offset;
 558
 559                         if (p->code == (BPF_JMP|BPF_JA))
 560                                 offset = p->k;
 561                         else
 562                                 offset = p->jt > p->jf ? p->jt : p->jf;
 563                         if (offset >= (u_int)(len - i) - 1)
 564                                 return (0);
 565                         continue;
 566                 }
 567                 /*
 568                  * Check that memory operations use valid addresses.
 569                  */
 570                 if (p->code == BPF_ST || p->code == BPF_STX ||
 571                     p->code == (BPF_LD|BPF_MEM) ||
 572                     p->code == (BPF_LDX|BPF_MEM)) {
 573                         if (p->k >= BPF_MEMWORDS)
 574                                 return (0);
 575                         continue;
 576                 }
 577                 /*
 578                  * Check for constant division by 0.
 579                  */
 580                 if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0)
 581                         return (0);
 582         }
 583         return (BPF_CLASS(f[len - 1].code) == BPF_RET);
 584 }
 585 #endif