sys/net/bpf_filter.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-3-Clause
   3  *
   4  * Copyright (c) 1990, 1991, 1993
   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. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #include <sys/param.h>
  38
  39 #if !defined(_KERNEL)
  40 #include <strings.h>
  41 #endif
  42 #if !defined(_KERNEL) || defined(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 #else
  68 #include <stdlib.h>
  69 #endif
  70 #include <net/bpf.h>
  71 #ifdef _KERNEL
  72 #define MINDEX(m, k) \
  73 { \
  74         int len = m->m_len; \
  75  \
  76         while (k >= len) { \
  77                 k -= len; \
  78                 m = m->m_next; \
  79                 if (m == 0) \
  80                         return (0); \
  81                 len = m->m_len; \
  82         } \
  83 }
  84
  85 static u_int16_t        m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err);
  86 static u_int32_t        m_xword(struct mbuf *m, bpf_u_int32 k, int *err);
  87
  88 static u_int32_t
  89 m_xword(struct mbuf *m, bpf_u_int32 k, int *err)
  90 {
  91         size_t len;
  92         u_char *cp, *np;
  93         struct mbuf *m0;
  94
  95         len = m->m_len;
  96         while (k >= len) {
  97                 k -= len;
  98                 m = m->m_next;
  99                 if (m == NULL)
 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 == NULL || m0->m_len + len - k < 4)
 110                 goto bad;
 111         *err = 0;
 112         np = mtod(m0, u_char *);
 113         switch (len - k) {
 114         case 1:
 115                 return (((u_int32_t)cp[0] << 24) |
 116                     ((u_int32_t)np[0] << 16) |
 117                     ((u_int32_t)np[1] << 8)  |
 118                     (u_int32_t)np[2]);
 119
 120         case 2:
 121                 return (((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 (((u_int32_t)cp[0] << 24) |
 128                     ((u_int32_t)cp[1] << 16) |
 129                     ((u_int32_t)cp[2] << 8) |
 130                     (u_int32_t)np[0]);
 131         }
 132     bad:
 133         *err = 1;
 134         return (0);
 135 }
 136
 137 static u_int16_t
 138 m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err)
 139 {
 140         size_t len;
 141         u_char *cp;
 142         struct mbuf *m0;
 143
 144         len = m->m_len;
 145         while (k >= len) {
 146                 k -= len;
 147                 m = m->m_next;
 148                 if (m == NULL)
 149                         goto bad;
 150                 len = m->m_len;
 151         }
 152         cp = mtod(m, u_char *) + k;
 153         if (len - k >= 2) {
 154                 *err = 0;
 155                 return (EXTRACT_SHORT(cp));
 156         }
 157         m0 = m->m_next;
 158         if (m0 == NULL)
 159                 goto bad;
 160         *err = 0;
 161         return ((cp[0] << 8) | mtod(m0, u_char *)[0]);
 162  bad:
 163         *err = 1;
 164         return (0);
 165 }
 166 #endif
 167
 168 /*
 169  * Execute the filter program starting at pc on the packet p
 170  * wirelen is the length of the original packet
 171  * buflen is the amount of data present
 172  */
 173 u_int
 174 bpf_filter(const struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen)
 175 {
 176         u_int32_t A = 0, X = 0;
 177         bpf_u_int32 k;
 178         u_int32_t mem[BPF_MEMWORDS];
 179
 180         bzero(mem, sizeof(mem));
 181
 182         if (pc == NULL)
 183                 /*
 184                  * No filter means accept all.
 185                  */
 186                 return ((u_int)-1);
 187
 188         --pc;
 189         while (1) {
 190                 ++pc;
 191                 switch (pc->code) {
 192                 default:
 193 #ifdef _KERNEL
 194                         return (0);
 195 #else
 196                         abort();
 197 #endif
 198
 199                 case BPF_RET|BPF_K:
 200                         return ((u_int)pc->k);
 201
 202                 case BPF_RET|BPF_A:
 203                         return ((u_int)A);
 204
 205                 case BPF_LD|BPF_W|BPF_ABS:
 206                         k = pc->k;
 207                         if (k > buflen || sizeof(int32_t) > buflen - k) {
 208 #ifdef _KERNEL
 209                                 int merr;
 210
 211                                 if (buflen != 0)
 212                                         return (0);
 213                                 A = m_xword((struct mbuf *)p, k, &merr);
 214                                 if (merr != 0)
 215                                         return (0);
 216                                 continue;
 217 #else
 218                                 return (0);
 219 #endif
 220                         }
 221 #ifdef BPF_ALIGN
 222                         if (((intptr_t)(p + k) & 3) != 0)
 223                                 A = EXTRACT_LONG(&p[k]);
 224                         else
 225 #endif
 226                                 A = ntohl(*(int32_t *)(p + k));
 227                         continue;
 228
 229                 case BPF_LD|BPF_H|BPF_ABS:
 230                         k = pc->k;
 231                         if (k > buflen || sizeof(int16_t) > buflen - k) {
 232 #ifdef _KERNEL
 233                                 int merr;
 234
 235                                 if (buflen != 0)
 236                                         return (0);
 237                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 238                                 continue;
 239 #else
 240                                 return (0);
 241 #endif
 242                         }
 243                         A = EXTRACT_SHORT(&p[k]);
 244                         continue;
 245
 246                 case BPF_LD|BPF_B|BPF_ABS:
 247                         k = pc->k;
 248                         if (k >= buflen) {
 249 #ifdef _KERNEL
 250                                 struct mbuf *m;
 251
 252                                 if (buflen != 0)
 253                                         return (0);
 254                                 m = (struct mbuf *)p;
 255                                 MINDEX(m, k);
 256                                 A = mtod(m, u_char *)[k];
 257                                 continue;
 258 #else
 259                                 return (0);
 260 #endif
 261                         }
 262                         A = p[k];
 263                         continue;
 264
 265                 case BPF_LD|BPF_W|BPF_LEN:
 266                         A = wirelen;
 267                         continue;
 268
 269                 case BPF_LDX|BPF_W|BPF_LEN:
 270                         X = wirelen;
 271                         continue;
 272
 273                 case BPF_LD|BPF_W|BPF_IND:
 274                         k = X + pc->k;
 275                         if (pc->k > buflen || X > buflen - pc->k ||
 276                             sizeof(int32_t) > buflen - k) {
 277 #ifdef _KERNEL
 278                                 int merr;
 279
 280                                 if (buflen != 0)
 281                                         return (0);
 282                                 A = m_xword((struct mbuf *)p, k, &merr);
 283                                 if (merr != 0)
 284                                         return (0);
 285                                 continue;
 286 #else
 287                                 return (0);
 288 #endif
 289                         }
 290 #ifdef BPF_ALIGN
 291                         if (((intptr_t)(p + k) & 3) != 0)
 292                                 A = EXTRACT_LONG(&p[k]);
 293                         else
 294 #endif
 295                                 A = ntohl(*(int32_t *)(p + k));
 296                         continue;
 297
 298                 case BPF_LD|BPF_H|BPF_IND:
 299                         k = X + pc->k;
 300                         if (X > buflen || pc->k > buflen - X ||
 301                             sizeof(int16_t) > buflen - k) {
 302 #ifdef _KERNEL
 303                                 int merr;
 304
 305                                 if (buflen != 0)
 306                                         return (0);
 307                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 308                                 if (merr != 0)
 309                                         return (0);
 310                                 continue;
 311 #else
 312                                 return (0);
 313 #endif
 314                         }
 315                         A = EXTRACT_SHORT(&p[k]);
 316                         continue;
 317
 318                 case BPF_LD|BPF_B|BPF_IND:
 319                         k = X + pc->k;
 320                         if (pc->k >= buflen || X >= buflen - pc->k) {
 321 #ifdef _KERNEL
 322                                 struct mbuf *m;
 323
 324                                 if (buflen != 0)
 325                                         return (0);
 326                                 m = (struct mbuf *)p;
 327                                 MINDEX(m, k);
 328                                 A = mtod(m, u_char *)[k];
 329                                 continue;
 330 #else
 331                                 return (0);
 332 #endif
 333                         }
 334                         A = p[k];
 335                         continue;
 336
 337                 case BPF_LDX|BPF_MSH|BPF_B:
 338                         k = pc->k;
 339                         if (k >= buflen) {
 340 #ifdef _KERNEL
 341                                 struct mbuf *m;
 342
 343                                 if (buflen != 0)
 344                                         return (0);
 345                                 m = (struct mbuf *)p;
 346                                 MINDEX(m, k);
 347                                 X = (mtod(m, u_char *)[k] & 0xf) << 2;
 348                                 continue;
 349 #else
 350                                 return (0);
 351 #endif
 352                         }
 353                         X = (p[pc->k] & 0xf) << 2;
 354                         continue;
 355
 356                 case BPF_LD|BPF_IMM:
 357                         A = pc->k;
 358                         continue;
 359
 360                 case BPF_LDX|BPF_IMM:
 361                         X = pc->k;
 362                         continue;
 363
 364                 case BPF_LD|BPF_MEM:
 365                         A = mem[pc->k];
 366                         continue;
 367
 368                 case BPF_LDX|BPF_MEM:
 369                         X = mem[pc->k];
 370                         continue;
 371
 372                 case BPF_ST:
 373                         mem[pc->k] = A;
 374                         continue;
 375
 376                 case BPF_STX:
 377                         mem[pc->k] = X;
 378                         continue;
 379
 380                 case BPF_JMP|BPF_JA:
 381                         pc += pc->k;
 382                         continue;
 383
 384                 case BPF_JMP|BPF_JGT|BPF_K:
 385                         pc += (A > pc->k) ? pc->jt : pc->jf;
 386                         continue;
 387
 388                 case BPF_JMP|BPF_JGE|BPF_K:
 389                         pc += (A >= pc->k) ? pc->jt : pc->jf;
 390                         continue;
 391
 392                 case BPF_JMP|BPF_JEQ|BPF_K:
 393                         pc += (A == pc->k) ? pc->jt : pc->jf;
 394                         continue;
 395
 396                 case BPF_JMP|BPF_JSET|BPF_K:
 397                         pc += (A & pc->k) ? pc->jt : pc->jf;
 398                         continue;
 399
 400                 case BPF_JMP|BPF_JGT|BPF_X:
 401                         pc += (A > X) ? pc->jt : pc->jf;
 402                         continue;
 403
 404                 case BPF_JMP|BPF_JGE|BPF_X:
 405                         pc += (A >= X) ? pc->jt : pc->jf;
 406                         continue;
 407
 408                 case BPF_JMP|BPF_JEQ|BPF_X:
 409                         pc += (A == X) ? pc->jt : pc->jf;
 410                         continue;
 411
 412                 case BPF_JMP|BPF_JSET|BPF_X:
 413                         pc += (A & X) ? pc->jt : pc->jf;
 414                         continue;
 415
 416                 case BPF_ALU|BPF_ADD|BPF_X:
 417                         A += X;
 418                         continue;
 419
 420                 case BPF_ALU|BPF_SUB|BPF_X:
 421                         A -= X;
 422                         continue;
 423
 424                 case BPF_ALU|BPF_MUL|BPF_X:
 425                         A *= X;
 426                         continue;
 427
 428                 case BPF_ALU|BPF_DIV|BPF_X:
 429                         if (X == 0)
 430                                 return (0);
 431                         A /= X;
 432                         continue;
 433
 434                 case BPF_ALU|BPF_MOD|BPF_X:
 435                         if (X == 0)
 436                                 return (0);
 437                         A %= X;
 438                         continue;
 439
 440                 case BPF_ALU|BPF_AND|BPF_X:
 441                         A &= X;
 442                         continue;
 443
 444                 case BPF_ALU|BPF_OR|BPF_X:
 445                         A |= X;
 446                         continue;
 447
 448                 case BPF_ALU|BPF_XOR|BPF_X:
 449                         A ^= X;
 450                         continue;
 451
 452                 case BPF_ALU|BPF_LSH|BPF_X:
 453                         A <<= X;
 454                         continue;
 455
 456                 case BPF_ALU|BPF_RSH|BPF_X:
 457                         A >>= X;
 458                         continue;
 459
 460                 case BPF_ALU|BPF_ADD|BPF_K:
 461                         A += pc->k;
 462                         continue;
 463
 464                 case BPF_ALU|BPF_SUB|BPF_K:
 465                         A -= pc->k;
 466                         continue;
 467
 468                 case BPF_ALU|BPF_MUL|BPF_K:
 469                         A *= pc->k;
 470                         continue;
 471
 472                 case BPF_ALU|BPF_DIV|BPF_K:
 473                         A /= pc->k;
 474                         continue;
 475
 476                 case BPF_ALU|BPF_MOD|BPF_K:
 477                         A %= pc->k;
 478                         continue;
 479
 480                 case BPF_ALU|BPF_AND|BPF_K:
 481                         A &= pc->k;
 482                         continue;
 483
 484                 case BPF_ALU|BPF_OR|BPF_K:
 485                         A |= pc->k;
 486                         continue;
 487
 488                 case BPF_ALU|BPF_XOR|BPF_K:
 489                         A ^= pc->k;
 490                         continue;
 491
 492                 case BPF_ALU|BPF_LSH|BPF_K:
 493                         A <<= pc->k;
 494                         continue;
 495
 496                 case BPF_ALU|BPF_RSH|BPF_K:
 497                         A >>= pc->k;
 498                         continue;
 499
 500                 case BPF_ALU|BPF_NEG:
 501                         A = -A;
 502                         continue;
 503
 504                 case BPF_MISC|BPF_TAX:
 505                         X = A;
 506                         continue;
 507
 508                 case BPF_MISC|BPF_TXA:
 509                         A = X;
 510                         continue;
 511                 }
 512         }
 513 }
 514
 515 #ifdef _KERNEL
 516 static const u_short    bpf_code_map[] = {
 517         0x10ff, /* 0x00-0x0f: 1111111100001000 */
 518         0x3070, /* 0x10-0x1f: 0000111000001100 */
 519         0x3131, /* 0x20-0x2f: 1000110010001100 */
 520         0x3031, /* 0x30-0x3f: 1000110000001100 */
 521         0x3131, /* 0x40-0x4f: 1000110010001100 */
 522         0x1011, /* 0x50-0x5f: 1000100000001000 */
 523         0x1013, /* 0x60-0x6f: 1100100000001000 */
 524         0x1010, /* 0x70-0x7f: 0000100000001000 */
 525         0x0093, /* 0x80-0x8f: 1100100100000000 */
 526         0x1010, /* 0x90-0x9f: 0000100000001000 */
 527         0x1010, /* 0xa0-0xaf: 0000100000001000 */
 528         0x0002, /* 0xb0-0xbf: 0100000000000000 */
 529         0x0000, /* 0xc0-0xcf: 0000000000000000 */
 530         0x0000, /* 0xd0-0xdf: 0000000000000000 */
 531         0x0000, /* 0xe0-0xef: 0000000000000000 */
 532         0x0000  /* 0xf0-0xff: 0000000000000000 */
 533 };
 534
 535 #define BPF_VALIDATE_CODE(c)    \
 536     ((c) <= 0xff && (bpf_code_map[(c) >> 4] & (1 << ((c) & 0xf))) != 0)
 537
 538 /*
 539  * Return true if the 'fcode' is a valid filter program.
 540  * The constraints are that each jump be forward and to a valid
 541  * code.  The code must terminate with either an accept or reject.
 542  *
 543  * The kernel needs to be able to verify an application's filter code.
 544  * Otherwise, a bogus program could easily crash the system.
 545  */
 546 int
 547 bpf_validate(const struct bpf_insn *f, int len)
 548 {
 549         int i;
 550         const struct bpf_insn *p;
 551
 552         /* Do not accept negative length filter. */
 553         if (len < 0)
 554                 return (0);
 555
 556         /* An empty filter means accept all. */
 557         if (len == 0)
 558                 return (1);
 559
 560         for (i = 0; i < len; ++i) {
 561                 p = &f[i];
 562                 /*
 563                  * Check that the code is valid.
 564                  */
 565                 if (!BPF_VALIDATE_CODE(p->code))
 566                         return (0);
 567                 /*
 568                  * Check that the jumps are forward, and within
 569                  * the code block.
 570                  */
 571                 if (BPF_CLASS(p->code) == BPF_JMP) {
 572                         u_int offset;
 573
 574                         if (p->code == (BPF_JMP|BPF_JA))
 575                                 offset = p->k;
 576                         else
 577                                 offset = p->jt > p->jf ? p->jt : p->jf;
 578                         if (offset >= (u_int)(len - i) - 1)
 579                                 return (0);
 580                         continue;
 581                 }
 582                 /*
 583                  * Check that memory operations use valid addresses.
 584                  */
 585                 if (p->code == BPF_ST || p->code == BPF_STX ||
 586                     p->code == (BPF_LD|BPF_MEM) ||
 587                     p->code == (BPF_LDX|BPF_MEM)) {
 588                         if (p->k >= BPF_MEMWORDS)
 589                                 return (0);
 590                         continue;
 591                 }
 592                 /*
 593                  * Check for constant division by 0.
 594                  */
 595                 if ((p->code == (BPF_ALU|BPF_DIV|BPF_K) ||
 596                     p->code == (BPF_ALU|BPF_MOD|BPF_K)) && p->k == 0)
 597                         return (0);
 598         }
 599         return (BPF_CLASS(f[len - 1].code) == BPF_RET);
 600 }
 601 #endif