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