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