dist/ipf/bpf_filter.c

   1 /*      $NetBSD: bpf_filter.c,v 1.1.1.2 2006/04/04 16:08:18 martti Exp $        */
   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: /pub/NetBSD/misc/repositories/cvsroot/src/dist/ipf/bpf_filter.c,v 1.2 2006/05/14 02:37:46 christos 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 = 0;   /* XXX: GCC */
 199         int len;
 200
 201         if (buflen == 0) {
 202                 m = (mb_t *)p;
 203                 p = MTOD(m, u_char *);
 204                 buflen = M_LEN(m);
 205         } else
 206                 m = NULL;
 207
 208         if (pc == 0)
 209                 /*
 210                  * No filter means accept all.
 211                  */
 212                 return (u_int)-1;
 213         A = 0;
 214         X = 0;
 215         --pc;
 216         while (1) {
 217                 ++pc;
 218                 switch (pc->code) {
 219
 220                 default:
 221                         return 0;
 222                 case BPF_RET|BPF_K:
 223                         return (u_int)pc->k;
 224
 225                 case BPF_RET|BPF_A:
 226                         return (u_int)A;
 227
 228                 case BPF_LD|BPF_W|BPF_ABS:
 229                         k = pc->k;
 230                         if (k + sizeof(int32) > buflen) {
 231                                 if (m == NULL)
 232                                         return 0;
 233                                 A = m_xword(m, k, &merr);
 234                                 if (merr != 0)
 235                                         return 0;
 236                                 continue;
 237                         }
 238                         A = EXTRACT_LONG(&p[k]);
 239                         continue;
 240
 241                 case BPF_LD|BPF_H|BPF_ABS:
 242                         k = pc->k;
 243                         if (k + sizeof(short) > buflen) {
 244                                 if (m == NULL)
 245                                         return 0;
 246                                 A = m_xhalf(m, k, &merr);
 247                                 if (merr != 0)
 248                                         return 0;
 249                                 continue;
 250                         }
 251                         A = EXTRACT_SHORT(&p[k]);
 252                         continue;
 253
 254                 case BPF_LD|BPF_B|BPF_ABS:
 255                         k = pc->k;
 256                         if (k >= buflen) {
 257                                 if (m == NULL)
 258                                         return 0;
 259                                 n = m;
 260                                 MINDEX(len, n, k);
 261                                 A = MTOD(n, u_char *)[k];
 262                                 continue;
 263                         }
 264                         A = p[k];
 265                         continue;
 266
 267                 case BPF_LD|BPF_W|BPF_LEN:
 268                         A = wirelen;
 269                         continue;
 270
 271                 case BPF_LDX|BPF_W|BPF_LEN:
 272                         X = wirelen;
 273                         continue;
 274
 275                 case BPF_LD|BPF_W|BPF_IND:
 276                         k = X + pc->k;
 277                         if (k + sizeof(int32) > buflen) {
 278                                 if (m == NULL)
 279                                         return 0;
 280                                 A = m_xword(m, k, &merr);
 281                                 if (merr != 0)
 282                                         return 0;
 283                                 continue;
 284                         }
 285                         A = EXTRACT_LONG(&p[k]);
 286                         continue;
 287
 288                 case BPF_LD|BPF_H|BPF_IND:
 289                         k = X + pc->k;
 290                         if (k + sizeof(short) > buflen) {
 291                                 if (m == NULL)
 292                                         return 0;
 293                                 A = m_xhalf(m, k, &merr);
 294                                 if (merr != 0)
 295                                         return 0;
 296                                 continue;
 297                         }
 298                         A = EXTRACT_SHORT(&p[k]);
 299                         continue;
 300
 301                 case BPF_LD|BPF_B|BPF_IND:
 302                         k = X + pc->k;
 303                         if (k >= buflen) {
 304                                 if (m == NULL)
 305                                         return 0;
 306                                 n = m;
 307                                 MINDEX(len, n, k);
 308                                 A = MTOD(n, u_char *)[k];
 309                                 continue;
 310                         }
 311                         A = p[k];
 312                         continue;
 313
 314                 case BPF_LDX|BPF_MSH|BPF_B:
 315                         k = pc->k;
 316                         if (k >= buflen) {
 317                                 if (m == NULL)
 318                                         return 0;
 319                                 n = m;
 320                                 MINDEX(len, n, k);
 321                                 X = (MTOD(n, char *)[k] & 0xf) << 2;
 322                                 continue;
 323                         }
 324                         X = (p[pc->k] & 0xf) << 2;
 325                         continue;
 326
 327                 case BPF_LD|BPF_IMM:
 328                         A = pc->k;
 329                         continue;
 330
 331                 case BPF_LDX|BPF_IMM:
 332                         X = pc->k;
 333                         continue;
 334
 335                 case BPF_LD|BPF_MEM:
 336                         A = mem[pc->k];
 337                         continue;
 338
 339                 case BPF_LDX|BPF_MEM:
 340                         X = mem[pc->k];
 341                         continue;
 342
 343                 case BPF_ST:
 344                         mem[pc->k] = A;
 345                         continue;
 346
 347                 case BPF_STX:
 348                         mem[pc->k] = X;
 349                         continue;
 350
 351                 case BPF_JMP|BPF_JA:
 352                         pc += pc->k;
 353                         continue;
 354
 355                 case BPF_JMP|BPF_JGT|BPF_K:
 356                         pc += (A > pc->k) ? pc->jt : pc->jf;
 357                         continue;
 358
 359                 case BPF_JMP|BPF_JGE|BPF_K:
 360                         pc += (A >= pc->k) ? pc->jt : pc->jf;
 361                         continue;
 362
 363                 case BPF_JMP|BPF_JEQ|BPF_K:
 364                         pc += (A == pc->k) ? pc->jt : pc->jf;
 365                         continue;
 366
 367                 case BPF_JMP|BPF_JSET|BPF_K:
 368                         pc += (A & pc->k) ? pc->jt : pc->jf;
 369                         continue;
 370
 371                 case BPF_JMP|BPF_JGT|BPF_X:
 372                         pc += (A > X) ? pc->jt : pc->jf;
 373                         continue;
 374
 375                 case BPF_JMP|BPF_JGE|BPF_X:
 376                         pc += (A >= X) ? pc->jt : pc->jf;
 377                         continue;
 378
 379                 case BPF_JMP|BPF_JEQ|BPF_X:
 380                         pc += (A == X) ? pc->jt : pc->jf;
 381                         continue;
 382
 383                 case BPF_JMP|BPF_JSET|BPF_X:
 384                         pc += (A & X) ? pc->jt : pc->jf;
 385                         continue;
 386
 387                 case BPF_ALU|BPF_ADD|BPF_X:
 388                         A += X;
 389                         continue;
 390
 391                 case BPF_ALU|BPF_SUB|BPF_X:
 392                         A -= X;
 393                         continue;
 394
 395                 case BPF_ALU|BPF_MUL|BPF_X:
 396                         A *= X;
 397                         continue;
 398
 399                 case BPF_ALU|BPF_DIV|BPF_X:
 400                         if (X == 0)
 401                                 return 0;
 402                         A /= X;
 403                         continue;
 404
 405                 case BPF_ALU|BPF_AND|BPF_X:
 406                         A &= X;
 407                         continue;
 408
 409                 case BPF_ALU|BPF_OR|BPF_X:
 410                         A |= X;
 411                         continue;
 412
 413                 case BPF_ALU|BPF_LSH|BPF_X:
 414                         A <<= X;
 415                         continue;
 416
 417                 case BPF_ALU|BPF_RSH|BPF_X:
 418                         A >>= X;
 419                         continue;
 420
 421                 case BPF_ALU|BPF_ADD|BPF_K:
 422                         A += pc->k;
 423                         continue;
 424
 425                 case BPF_ALU|BPF_SUB|BPF_K:
 426                         A -= pc->k;
 427                         continue;
 428
 429                 case BPF_ALU|BPF_MUL|BPF_K:
 430                         A *= pc->k;
 431                         continue;
 432
 433                 case BPF_ALU|BPF_DIV|BPF_K:
 434                         A /= pc->k;
 435                         continue;
 436
 437                 case BPF_ALU|BPF_AND|BPF_K:
 438                         A &= pc->k;
 439                         continue;
 440
 441                 case BPF_ALU|BPF_OR|BPF_K:
 442                         A |= pc->k;
 443                         continue;
 444
 445                 case BPF_ALU|BPF_LSH|BPF_K:
 446                         A <<= pc->k;
 447                         continue;
 448
 449                 case BPF_ALU|BPF_RSH|BPF_K:
 450                         A >>= pc->k;
 451                         continue;
 452
 453                 case BPF_ALU|BPF_NEG:
 454                         A = -A;
 455                         continue;
 456
 457                 case BPF_MISC|BPF_TAX:
 458                         X = A;
 459                         continue;
 460
 461                 case BPF_MISC|BPF_TXA:
 462                         A = X;
 463                         continue;
 464                 }
 465         }
 466 }
 467
 468
 469 /*
 470  * Return true if the 'fcode' is a valid filter program.
 471  * The constraints are that each jump be forward and to a valid
 472  * code, that memory accesses are within valid ranges (to the
 473  * extent that this can be checked statically; loads of packet
 474  * data have to be, and are, also checked at run time), and that
 475  * the code terminates with either an accept or reject.
 476  *
 477  * The kernel needs to be able to verify an application's filter code.
 478  * Otherwise, a bogus program could easily crash the system.
 479  */
 480 int
 481 bpf_validate(f, len)
 482         struct bpf_insn *f;
 483         int len;
 484 {
 485         u_int i, from;
 486         const struct bpf_insn *p;
 487
 488         if (len == 0)
 489                 return 1;
 490
 491         if (len < 1 || len > BPF_MAXINSNS)
 492                 return 0;
 493
 494         for (i = 0; i < len; ++i) {
 495                 p = &f[i];
 496                 switch (BPF_CLASS(p->code)) {
 497                 /*
 498                  * Check that memory operations use valid addresses.
 499                  */
 500                 case BPF_LD:
 501                 case BPF_LDX:
 502                         switch (BPF_MODE(p->code)) {
 503                         case BPF_IMM:
 504                                 break;
 505                         case BPF_ABS:
 506                         case BPF_IND:
 507                         case BPF_MSH:
 508                                 /*
 509                                  * More strict check with actual packet length
 510                                  * is done runtime.
 511                                  */
 512 #if 0
 513                                 if (p->k >= bpf_maxbufsize)
 514                                         return 0;
 515 #endif
 516                                 break;
 517                         case BPF_MEM:
 518                                 if (p->k >= BPF_MEMWORDS)
 519                                         return 0;
 520                                 break;
 521                         case BPF_LEN:
 522                                 break;
 523                         default:
 524                                 return 0;
 525                         }
 526                         break;
 527                 case BPF_ST:
 528                 case BPF_STX:
 529                         if (p->k >= BPF_MEMWORDS)
 530                                 return 0;
 531                         break;
 532                 case BPF_ALU:
 533                         switch (BPF_OP(p->code)) {
 534                         case BPF_ADD:
 535                         case BPF_SUB:
 536                         case BPF_OR:
 537                         case BPF_AND:
 538                         case BPF_LSH:
 539                         case BPF_RSH:
 540                         case BPF_NEG:
 541                                 break;
 542                         case BPF_DIV:
 543                                 /*
 544                                  * Check for constant division by 0.
 545                                  */
 546                                 if (BPF_RVAL(p->code) == BPF_K && p->k == 0)
 547                                         return 0;
 548                         default:
 549                                 return 0;
 550                         }
 551                         break;
 552                 case BPF_JMP:
 553                         /*
 554                          * Check that jumps are within the code block,
 555                          * and that unconditional branches don't go
 556                          * backwards as a result of an overflow.
 557                          * Unconditional branches have a 32-bit offset,
 558                          * so they could overflow; we check to make
 559                          * sure they don't.  Conditional branches have
 560                          * an 8-bit offset, and the from address is <=
 561                          * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
 562                          * is sufficiently small that adding 255 to it
 563                          * won't overflow.
 564                          *
 565                          * We know that len is <= BPF_MAXINSNS, and we
 566                          * assume that BPF_MAXINSNS is < the maximum size
 567                          * of a u_int, so that i + 1 doesn't overflow.
 568                          */
 569                         from = i + 1;
 570                         switch (BPF_OP(p->code)) {
 571                         case BPF_JA:
 572                                 if (from + p->k < from || from + p->k >= len)
 573                                         return 0;
 574                                 break;
 575                         case BPF_JEQ:
 576                         case BPF_JGT:
 577                         case BPF_JGE:
 578                         case BPF_JSET:
 579                                 if (from + p->jt >= len || from + p->jf >= len)
 580                                         return 0;
 581                                 break;
 582                         default:
 583                                 return 0;
 584                         }
 585                         break;
 586                 case BPF_RET:
 587                         break;
 588                 case BPF_MISC:
 589                         break;
 590                 default:
 591                         return 0;
 592                 }
 593         }
 594         return BPF_CLASS(f[len - 1].code) == BPF_RET;
 595 }