contrib/ipfilter/bpf_filter.c

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