contrib/libpcap/bpf_filter.c

   1 /*-
   2  * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997
   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  * 3. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  *
  38  *      @(#)bpf.c       7.5 (Berkeley) 7/15/91
  39  */
  40
  41 #ifdef HAVE_CONFIG_H
  42 #include <config.h>
  43 #endif
  44
  45 #include <pcap/pcap-inttypes.h>
  46 #include "pcap-types.h"
  47
  48 #ifndef _WIN32
  49 #include <sys/param.h>
  50 #include <sys/types.h>
  51 #include <sys/time.h>
  52 #endif /* _WIN32 */
  53
  54 #include <pcap-int.h>
  55
  56 #include <stdlib.h>
  57
  58 #define int32 bpf_int32
  59 #define u_int32 bpf_u_int32
  60
  61 #ifndef LBL_ALIGN
  62 /*
  63  * XXX - IA-64?  If not, this probably won't work on Win64 IA-64
  64  * systems, unless LBL_ALIGN is defined elsewhere for them.
  65  * XXX - SuperH?  If not, this probably won't work on WinCE SuperH
  66  * systems, unless LBL_ALIGN is defined elsewhere for them.
  67  */
  68 #if defined(sparc) || defined(__sparc__) || defined(mips) || \
  69     defined(ibm032) || defined(__alpha) || defined(__hpux) || \
  70     defined(__arm__)
  71 #define LBL_ALIGN
  72 #endif
  73 #endif
  74
  75 #ifndef LBL_ALIGN
  76 #ifndef _WIN32
  77 #include <netinet/in.h>
  78 #endif
  79
  80 #define EXTRACT_SHORT(p)        ((u_short)ntohs(*(u_short *)p))
  81 #define EXTRACT_LONG(p)         (ntohl(*(u_int32 *)p))
  82 #else
  83 #define EXTRACT_SHORT(p)\
  84         ((u_short)\
  85                 ((u_short)*((u_char *)p+0)<<8|\
  86                  (u_short)*((u_char *)p+1)<<0))
  87 #define EXTRACT_LONG(p)\
  88                 ((u_int32)*((u_char *)p+0)<<24|\
  89                  (u_int32)*((u_char *)p+1)<<16|\
  90                  (u_int32)*((u_char *)p+2)<<8|\
  91                  (u_int32)*((u_char *)p+3)<<0)
  92 #endif
  93
  94 #ifdef __linux__
  95 #include <linux/types.h>
  96 #include <linux/if_packet.h>
  97 #include <linux/filter.h>
  98 #endif
  99
 100 enum {
 101         BPF_S_ANC_NONE,
 102         BPF_S_ANC_VLAN_TAG,
 103         BPF_S_ANC_VLAN_TAG_PRESENT,
 104 };
 105
 106 /*
 107  * Execute the filter program starting at pc on the packet p
 108  * wirelen is the length of the original packet
 109  * buflen is the amount of data present
 110  * aux_data is auxiliary data, currently used only when interpreting
 111  * filters intended for the Linux kernel in cases where the kernel
 112  * rejects the filter; it contains VLAN tag information
 113  * For the kernel, p is assumed to be a pointer to an mbuf if buflen is 0,
 114  * in all other cases, p is a pointer to a buffer and buflen is its size.
 115  *
 116  * Thanks to Ani Sinha <ani@arista.com> for providing initial implementation
 117  */
 118 u_int
 119 bpf_filter_with_aux_data(const struct bpf_insn *pc, const u_char *p,
 120     u_int wirelen, u_int buflen, const struct bpf_aux_data *aux_data)
 121 {
 122         register u_int32 A, X;
 123         register bpf_u_int32 k;
 124         u_int32 mem[BPF_MEMWORDS];
 125
 126         if (pc == 0)
 127                 /*
 128                  * No filter means accept all.
 129                  */
 130                 return (u_int)-1;
 131         A = 0;
 132         X = 0;
 133         --pc;
 134         for (;;) {
 135                 ++pc;
 136                 switch (pc->code) {
 137
 138                 default:
 139                         abort();
 140                 case BPF_RET|BPF_K:
 141                         return (u_int)pc->k;
 142
 143                 case BPF_RET|BPF_A:
 144                         return (u_int)A;
 145
 146                 case BPF_LD|BPF_W|BPF_ABS:
 147                         k = pc->k;
 148                         if (k > buflen || sizeof(int32_t) > buflen - k) {
 149                                 return 0;
 150                         }
 151                         A = EXTRACT_LONG(&p[k]);
 152                         continue;
 153
 154                 case BPF_LD|BPF_H|BPF_ABS:
 155                         k = pc->k;
 156                         if (k > buflen || sizeof(int16_t) > buflen - k) {
 157                                 return 0;
 158                         }
 159                         A = EXTRACT_SHORT(&p[k]);
 160                         continue;
 161
 162                 case BPF_LD|BPF_B|BPF_ABS:
 163                         switch (pc->k) {
 164
 165 #if defined(SKF_AD_VLAN_TAG_PRESENT)
 166                         case SKF_AD_OFF + SKF_AD_VLAN_TAG:
 167                                 if (!aux_data)
 168                                         return 0;
 169                                 A = aux_data->vlan_tag;
 170                                 break;
 171
 172                         case SKF_AD_OFF + SKF_AD_VLAN_TAG_PRESENT:
 173                                 if (!aux_data)
 174                                         return 0;
 175                                 A = aux_data->vlan_tag_present;
 176                                 break;
 177 #endif
 178                         default:
 179                                 k = pc->k;
 180                                 if (k >= buflen) {
 181                                         return 0;
 182                                 }
 183                                 A = p[k];
 184                                 break;
 185                         }
 186                         continue;
 187
 188                 case BPF_LD|BPF_W|BPF_LEN:
 189                         A = wirelen;
 190                         continue;
 191
 192                 case BPF_LDX|BPF_W|BPF_LEN:
 193                         X = wirelen;
 194                         continue;
 195
 196                 case BPF_LD|BPF_W|BPF_IND:
 197                         k = X + pc->k;
 198                         if (pc->k > buflen || X > buflen - pc->k ||
 199                             sizeof(int32_t) > buflen - k) {
 200                                 return 0;
 201                         }
 202                         A = EXTRACT_LONG(&p[k]);
 203                         continue;
 204
 205                 case BPF_LD|BPF_H|BPF_IND:
 206                         k = X + pc->k;
 207                         if (X > buflen || pc->k > buflen - X ||
 208                             sizeof(int16_t) > buflen - k) {
 209                                 return 0;
 210                         }
 211                         A = EXTRACT_SHORT(&p[k]);
 212                         continue;
 213
 214                 case BPF_LD|BPF_B|BPF_IND:
 215                         k = X + pc->k;
 216                         if (pc->k >= buflen || X >= buflen - pc->k) {
 217                                 return 0;
 218                         }
 219                         A = p[k];
 220                         continue;
 221
 222                 case BPF_LDX|BPF_MSH|BPF_B:
 223                         k = pc->k;
 224                         if (k >= buflen) {
 225                                 return 0;
 226                         }
 227                         X = (p[pc->k] & 0xf) << 2;
 228                         continue;
 229
 230                 case BPF_LD|BPF_IMM:
 231                         A = pc->k;
 232                         continue;
 233
 234                 case BPF_LDX|BPF_IMM:
 235                         X = pc->k;
 236                         continue;
 237
 238                 case BPF_LD|BPF_MEM:
 239                         A = mem[pc->k];
 240                         continue;
 241
 242                 case BPF_LDX|BPF_MEM:
 243                         X = mem[pc->k];
 244                         continue;
 245
 246                 case BPF_ST:
 247                         mem[pc->k] = A;
 248                         continue;
 249
 250                 case BPF_STX:
 251                         mem[pc->k] = X;
 252                         continue;
 253
 254                 case BPF_JMP|BPF_JA:
 255                         /*
 256                          * XXX - we currently implement "ip6 protochain"
 257                          * with backward jumps, so sign-extend pc->k.
 258                          */
 259                         pc += (bpf_int32)pc->k;
 260                         continue;
 261
 262                 case BPF_JMP|BPF_JGT|BPF_K:
 263                         pc += (A > pc->k) ? pc->jt : pc->jf;
 264                         continue;
 265
 266                 case BPF_JMP|BPF_JGE|BPF_K:
 267                         pc += (A >= pc->k) ? pc->jt : pc->jf;
 268                         continue;
 269
 270                 case BPF_JMP|BPF_JEQ|BPF_K:
 271                         pc += (A == pc->k) ? pc->jt : pc->jf;
 272                         continue;
 273
 274                 case BPF_JMP|BPF_JSET|BPF_K:
 275                         pc += (A & pc->k) ? pc->jt : pc->jf;
 276                         continue;
 277
 278                 case BPF_JMP|BPF_JGT|BPF_X:
 279                         pc += (A > X) ? pc->jt : pc->jf;
 280                         continue;
 281
 282                 case BPF_JMP|BPF_JGE|BPF_X:
 283                         pc += (A >= X) ? pc->jt : pc->jf;
 284                         continue;
 285
 286                 case BPF_JMP|BPF_JEQ|BPF_X:
 287                         pc += (A == X) ? pc->jt : pc->jf;
 288                         continue;
 289
 290                 case BPF_JMP|BPF_JSET|BPF_X:
 291                         pc += (A & X) ? pc->jt : pc->jf;
 292                         continue;
 293
 294                 case BPF_ALU|BPF_ADD|BPF_X:
 295                         A += X;
 296                         continue;
 297
 298                 case BPF_ALU|BPF_SUB|BPF_X:
 299                         A -= X;
 300                         continue;
 301
 302                 case BPF_ALU|BPF_MUL|BPF_X:
 303                         A *= X;
 304                         continue;
 305
 306                 case BPF_ALU|BPF_DIV|BPF_X:
 307                         if (X == 0)
 308                                 return 0;
 309                         A /= X;
 310                         continue;
 311
 312                 case BPF_ALU|BPF_MOD|BPF_X:
 313                         if (X == 0)
 314                                 return 0;
 315                         A %= X;
 316                         continue;
 317
 318                 case BPF_ALU|BPF_AND|BPF_X:
 319                         A &= X;
 320                         continue;
 321
 322                 case BPF_ALU|BPF_OR|BPF_X:
 323                         A |= X;
 324                         continue;
 325
 326                 case BPF_ALU|BPF_XOR|BPF_X:
 327                         A ^= X;
 328                         continue;
 329
 330                 case BPF_ALU|BPF_LSH|BPF_X:
 331                         if (X < 32)
 332                                 A <<= X;
 333                         else
 334                                 A = 0;
 335                         continue;
 336
 337                 case BPF_ALU|BPF_RSH|BPF_X:
 338                         if (X < 32)
 339                                 A >>= X;
 340                         else
 341                                 A = 0;
 342                         continue;
 343
 344                 case BPF_ALU|BPF_ADD|BPF_K:
 345                         A += pc->k;
 346                         continue;
 347
 348                 case BPF_ALU|BPF_SUB|BPF_K:
 349                         A -= pc->k;
 350                         continue;
 351
 352                 case BPF_ALU|BPF_MUL|BPF_K:
 353                         A *= pc->k;
 354                         continue;
 355
 356                 case BPF_ALU|BPF_DIV|BPF_K:
 357                         A /= pc->k;
 358                         continue;
 359
 360                 case BPF_ALU|BPF_MOD|BPF_K:
 361                         A %= pc->k;
 362                         continue;
 363
 364                 case BPF_ALU|BPF_AND|BPF_K:
 365                         A &= pc->k;
 366                         continue;
 367
 368                 case BPF_ALU|BPF_OR|BPF_K:
 369                         A |= pc->k;
 370                         continue;
 371
 372                 case BPF_ALU|BPF_XOR|BPF_K:
 373                         A ^= pc->k;
 374                         continue;
 375
 376                 case BPF_ALU|BPF_LSH|BPF_K:
 377                         A <<= pc->k;
 378                         continue;
 379
 380                 case BPF_ALU|BPF_RSH|BPF_K:
 381                         A >>= pc->k;
 382                         continue;
 383
 384                 case BPF_ALU|BPF_NEG:
 385                         /*
 386                          * Most BPF arithmetic is unsigned, but negation
 387                          * can't be unsigned; respecify it as subtracting
 388                          * the accumulator from 0U, so that 1) we don't
 389                          * get compiler warnings about negating an unsigned
 390                          * value and 2) don't get UBSan warnings about
 391                          * the result of negating 0x80000000 being undefined.
 392                          */
 393                         A = (0U - A);
 394                         continue;
 395
 396                 case BPF_MISC|BPF_TAX:
 397                         X = A;
 398                         continue;
 399
 400                 case BPF_MISC|BPF_TXA:
 401                         A = X;
 402                         continue;
 403                 }
 404         }
 405 }
 406
 407 u_int
 408 bpf_filter(const struct bpf_insn *pc, const u_char *p, u_int wirelen,
 409     u_int buflen)
 410 {
 411         return bpf_filter_with_aux_data(pc, p, wirelen, buflen, NULL);
 412 }
 413
 414
 415 /*
 416  * Return true if the 'fcode' is a valid filter program.
 417  * The constraints are that each jump be forward and to a valid
 418  * code, that memory accesses are within valid ranges (to the
 419  * extent that this can be checked statically; loads of packet
 420  * data have to be, and are, also checked at run time), and that
 421  * the code terminates with either an accept or reject.
 422  *
 423  * The kernel needs to be able to verify an application's filter code.
 424  * Otherwise, a bogus program could easily crash the system.
 425  */
 426 int
 427 bpf_validate(const struct bpf_insn *f, int len)
 428 {
 429         u_int i, from;
 430         const struct bpf_insn *p;
 431
 432         if (len < 1)
 433                 return 0;
 434
 435         for (i = 0; i < (u_int)len; ++i) {
 436                 p = &f[i];
 437                 switch (BPF_CLASS(p->code)) {
 438                 /*
 439                  * Check that memory operations use valid addresses.
 440                  */
 441                 case BPF_LD:
 442                 case BPF_LDX:
 443                         switch (BPF_MODE(p->code)) {
 444                         case BPF_IMM:
 445                                 break;
 446                         case BPF_ABS:
 447                         case BPF_IND:
 448                         case BPF_MSH:
 449                                 /*
 450                                  * There's no maximum packet data size
 451                                  * in userland.  The runtime packet length
 452                                  * check suffices.
 453                                  */
 454                                 break;
 455                         case BPF_MEM:
 456                                 if (p->k >= BPF_MEMWORDS)
 457                                         return 0;
 458                                 break;
 459                         case BPF_LEN:
 460                                 break;
 461                         default:
 462                                 return 0;
 463                         }
 464                         break;
 465                 case BPF_ST:
 466                 case BPF_STX:
 467                         if (p->k >= BPF_MEMWORDS)
 468                                 return 0;
 469                         break;
 470                 case BPF_ALU:
 471                         switch (BPF_OP(p->code)) {
 472                         case BPF_ADD:
 473                         case BPF_SUB:
 474                         case BPF_MUL:
 475                         case BPF_OR:
 476                         case BPF_AND:
 477                         case BPF_XOR:
 478                         case BPF_LSH:
 479                         case BPF_RSH:
 480                         case BPF_NEG:
 481                                 break;
 482                         case BPF_DIV:
 483                         case BPF_MOD:
 484                                 /*
 485                                  * Check for constant division or modulus
 486                                  * by 0.
 487                                  */
 488                                 if (BPF_SRC(p->code) == BPF_K && p->k == 0)
 489                                         return 0;
 490                                 break;
 491                         default:
 492                                 return 0;
 493                         }
 494                         break;
 495                 case BPF_JMP:
 496                         /*
 497                          * Check that jumps are within the code block,
 498                          * and that unconditional branches don't go
 499                          * backwards as a result of an overflow.
 500                          * Unconditional branches have a 32-bit offset,
 501                          * so they could overflow; we check to make
 502                          * sure they don't.  Conditional branches have
 503                          * an 8-bit offset, and the from address is <=
 504                          * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
 505                          * is sufficiently small that adding 255 to it
 506                          * won't overflow.
 507                          *
 508                          * We know that len is <= BPF_MAXINSNS, and we
 509                          * assume that BPF_MAXINSNS is < the maximum size
 510                          * of a u_int, so that i + 1 doesn't overflow.
 511                          *
 512                          * For userland, we don't know that the from
 513                          * or len are <= BPF_MAXINSNS, but we know that
 514                          * from <= len, and, except on a 64-bit system,
 515                          * it's unlikely that len, if it truly reflects
 516                          * the size of the program we've been handed,
 517                          * will be anywhere near the maximum size of
 518                          * a u_int.  We also don't check for backward
 519                          * branches, as we currently support them in
 520                          * userland for the protochain operation.
 521                          */
 522                         from = i + 1;
 523                         switch (BPF_OP(p->code)) {
 524                         case BPF_JA:
 525                                 if (from + p->k >= (u_int)len)
 526                                         return 0;
 527                                 break;
 528                         case BPF_JEQ:
 529                         case BPF_JGT:
 530                         case BPF_JGE:
 531                         case BPF_JSET:
 532                                 if (from + p->jt >= (u_int)len || from + p->jf >= (u_int)len)
 533                                         return 0;
 534                                 break;
 535                         default:
 536                                 return 0;
 537                         }
 538                         break;
 539                 case BPF_RET:
 540                         break;
 541                 case BPF_MISC:
 542                         break;
 543                 default:
 544                         return 0;
 545                 }
 546         }
 547         return BPF_CLASS(f[len - 1].code) == BPF_RET;
 548 }