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