src/bpf.c

   1 /*
   2  * netsniff-ng - the packet sniffing beast
   3  * By Daniel Borkmann <daniel@netsniff-ng.org>
   4  * Copyright 2009, 2010 Daniel Borkmann.
   5  * Copyright 2009, 2010 Emmanuel Roullit.
   6  * Subject to the GPL, version 2.
   7  */
   8
   9 /*
  10  * Copyright (c) 1990, 1991, 1992, 1994, 1995, 1996
  11  *      The Regents of the University of California.  All rights reserved.
  12  *
  13  * Redistribution and use in source and binary forms, with or without
  14  * modification, are permitted provided that: (1) source code distributions
  15  * retain the above copyright notice and this paragraph in its entirety, (2)
  16  * distributions including binary code include the above copyright notice and
  17  * this paragraph in its entirety in the documentation or other materials
  18  * provided with the distribution, and (3) all advertising materials mentioning
  19  * features or use of this software display the following acknowledgement:
  20  * ``This product includes software developed by the University of California,
  21  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  22  * the University nor the names of its contributors may be used to endorse
  23  * or promote products derived from this software without specific prior
  24  * written permission.
  25  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  26  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  27  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  28  */
  29
  30 #include <stdint.h>
  31 #include <stdio.h>
  32 #include <assert.h>
  33 #include <arpa/inet.h>
  34
  35 #include "bpf.h"
  36 #include "xmalloc.h"
  37 #include "xstring.h"
  38 #include "die.h"
  39
  40 /* This is a bug in libpcap, they actually use 'unsigned long' instead
  41  * of short! */
  42 #define EXTRACT_SHORT(packet)                                           \
  43                 ((unsigned short) ntohs(*(unsigned short *) packet))
  44 #define EXTRACT_LONG(packet)                                            \
  45                 (ntohl(*(unsigned long *) packet))
  46
  47 /*
  48  * Number of scratch memory words for: BPF_ST and BPF_STX
  49  */
  50 #ifndef BPF_MEMWORDS
  51 # define BPF_MEMWORDS 16
  52 #endif /* BPF_MEMWORDS */
  53
  54 static char *bpf_dump(const struct sock_filter bpf, int n)
  55 {
  56         int v;
  57         const char *fmt, *op;
  58         static char image[256];
  59         char operand[64];
  60
  61         v = bpf.k;
  62
  63         switch (bpf.code) {
  64         default:
  65                 op = "unimp";
  66                 fmt = "0x%x";
  67                 v = bpf.code;
  68                 break;
  69
  70         case BPF_RET | BPF_K:
  71                 op = "ret";
  72                 fmt = "#%d";
  73                 break;
  74
  75         case BPF_RET | BPF_A:
  76                 op = "ret";
  77                 fmt = "";
  78                 break;
  79
  80         case BPF_LD | BPF_W | BPF_ABS:
  81                 op = "ld";
  82                 fmt = "[%d]";
  83                 break;
  84
  85         case BPF_LD | BPF_H | BPF_ABS:
  86                 op = "ldh";
  87                 fmt = "[%d]";
  88                 break;
  89
  90         case BPF_LD | BPF_B | BPF_ABS:
  91                 op = "ldb";
  92                 fmt = "[%d]";
  93                 break;
  94
  95         case BPF_LD | BPF_W | BPF_LEN:
  96                 op = "ld";
  97                 fmt = "#pktlen";
  98                 break;
  99
 100         case BPF_LD | BPF_W | BPF_IND:
 101                 op = "ld";
 102                 fmt = "[x + %d]";
 103                 break;
 104
 105         case BPF_LD | BPF_H | BPF_IND:
 106                 op = "ldh";
 107                 fmt = "[x + %d]";
 108                 break;
 109
 110         case BPF_LD | BPF_B | BPF_IND:
 111                 op = "ldb";
 112                 fmt = "[x + %d]";
 113                 break;
 114
 115         case BPF_LD | BPF_IMM:
 116                 op = "ld";
 117                 fmt = "#0x%x";
 118                 break;
 119
 120         case BPF_LDX | BPF_IMM:
 121                 op = "ldx";
 122                 fmt = "#0x%x";
 123                 break;
 124
 125         case BPF_LDX | BPF_MSH | BPF_B:
 126                 op = "ldxb";
 127                 fmt = "4*([%d]&0xf)";
 128                 break;
 129
 130         case BPF_LD | BPF_MEM:
 131                 op = "ld";
 132                 fmt = "M[%d]";
 133                 break;
 134
 135         case BPF_LDX | BPF_MEM:
 136                 op = "ldx";
 137                 fmt = "M[%d]";
 138                 break;
 139
 140         case BPF_ST:
 141                 op = "st";
 142                 fmt = "M[%d]";
 143                 break;
 144
 145         case BPF_STX:
 146                 op = "stx";
 147                 fmt = "M[%d]";
 148                 break;
 149
 150         case BPF_JMP | BPF_JA:
 151                 op = "ja";
 152                 fmt = "%d";
 153                 v = n + 1 + bpf.k;
 154                 break;
 155
 156         case BPF_JMP | BPF_JGT | BPF_K:
 157                 op = "jgt";
 158                 fmt = "#0x%x";
 159                 break;
 160
 161         case BPF_JMP | BPF_JGE | BPF_K:
 162                 op = "jge";
 163                 fmt = "#0x%x";
 164                 break;
 165
 166         case BPF_JMP | BPF_JEQ | BPF_K:
 167                 op = "jeq";
 168                 fmt = "#0x%x";
 169                 break;
 170
 171         case BPF_JMP | BPF_JSET | BPF_K:
 172                 op = "jset";
 173                 fmt = "#0x%x";
 174                 break;
 175
 176         case BPF_JMP | BPF_JGT | BPF_X:
 177                 op = "jgt";
 178                 fmt = "x";
 179                 break;
 180
 181         case BPF_JMP | BPF_JGE | BPF_X:
 182                 op = "jge";
 183                 fmt = "x";
 184                 break;
 185
 186         case BPF_JMP | BPF_JEQ | BPF_X:
 187                 op = "jeq";
 188                 fmt = "x";
 189                 break;
 190
 191         case BPF_JMP | BPF_JSET | BPF_X:
 192                 op = "jset";
 193                 fmt = "x";
 194                 break;
 195
 196         case BPF_ALU | BPF_ADD | BPF_X:
 197                 op = "add";
 198                 fmt = "x";
 199                 break;
 200
 201         case BPF_ALU | BPF_SUB | BPF_X:
 202                 op = "sub";
 203                 fmt = "x";
 204                 break;
 205
 206         case BPF_ALU | BPF_MUL | BPF_X:
 207                 op = "mul";
 208                 fmt = "x";
 209                 break;
 210
 211         case BPF_ALU | BPF_DIV | BPF_X:
 212                 op = "div";
 213                 fmt = "x";
 214                 break;
 215
 216         case BPF_ALU | BPF_AND | BPF_X:
 217                 op = "and";
 218                 fmt = "x";
 219                 break;
 220
 221         case BPF_ALU | BPF_OR | BPF_X:
 222                 op = "or";
 223                 fmt = "x";
 224                 break;
 225
 226         case BPF_ALU | BPF_LSH | BPF_X:
 227                 op = "lsh";
 228                 fmt = "x";
 229                 break;
 230
 231         case BPF_ALU | BPF_RSH | BPF_X:
 232                 op = "rsh";
 233                 fmt = "x";
 234                 break;
 235
 236         case BPF_ALU | BPF_ADD | BPF_K:
 237                 op = "add";
 238                 fmt = "#%d";
 239                 break;
 240
 241         case BPF_ALU | BPF_SUB | BPF_K:
 242                 op = "sub";
 243                 fmt = "#%d";
 244                 break;
 245
 246         case BPF_ALU | BPF_MUL | BPF_K:
 247                 op = "mul";
 248                 fmt = "#%d";
 249                 break;
 250
 251         case BPF_ALU | BPF_DIV | BPF_K:
 252                 op = "div";
 253                 fmt = "#%d";
 254                 break;
 255
 256         case BPF_ALU | BPF_AND | BPF_K:
 257                 op = "and";
 258                 fmt = "#0x%x";
 259                 break;
 260
 261         case BPF_ALU | BPF_OR | BPF_K:
 262                 op = "or";
 263                 fmt = "#0x%x";
 264                 break;
 265
 266         case BPF_ALU | BPF_LSH | BPF_K:
 267                 op = "lsh";
 268                 fmt = "#%d";
 269                 break;
 270
 271         case BPF_ALU | BPF_RSH | BPF_K:
 272                 op = "rsh";
 273                 fmt = "#%d";
 274                 break;
 275
 276         case BPF_ALU | BPF_NEG:
 277                 op = "neg";
 278                 fmt = "";
 279                 break;
 280
 281         case BPF_MISC | BPF_TAX:
 282                 op = "tax";
 283                 fmt = "";
 284                 break;
 285
 286         case BPF_MISC | BPF_TXA:
 287                 op = "txa";
 288                 fmt = "";
 289                 break;
 290         }
 291
 292         /* XXX: Tell gcc that this here is okay for us */
 293         slprintf(operand, sizeof(operand), fmt, v);
 294         slprintf(image, sizeof(image),
 295                  (BPF_CLASS(bpf.code) == BPF_JMP &&
 296                   BPF_OP(bpf.code) != BPF_JA) ?
 297                  "(%03d) %-8s %-16s jt %d\tjf %d" : "(%03d) %-8s %s",
 298                  n, op, operand, n + 1 + bpf.jt, n + 1 + bpf.jf);
 299         return image;
 300 }
 301
 302 void bpf_dump_all(struct sock_fprog *bpf)
 303 {
 304         int i;
 305         for (i = 0; i < bpf->len; ++i)
 306                 printf("%s\n", bpf_dump(bpf->filter[i], i));
 307 }
 308
 309 void bpf_attach_to_sock(int sock, struct sock_fprog *bpf)
 310 {
 311         int ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, bpf,
 312                              sizeof(*bpf));
 313         if (ret < 0)
 314                 panic("Cannot attach filter to socket!\n");
 315 }
 316
 317 void bpf_detach_from_sock(int sock)
 318 {
 319         int ret, empty = 0;
 320         ret = setsockopt(sock, SOL_SOCKET, SO_DETACH_FILTER, &empty,
 321                          sizeof(empty));
 322         if (ret < 0)
 323                 panic("Cannot detach filter from socket!\n");
 324 }
 325
 326 int bpf_validate(const struct sock_fprog *bpf)
 327 {
 328         uint32_t i, from;
 329         const struct sock_filter *p;
 330
 331         if (!bpf)
 332                 return 0;
 333         if (bpf->len < 1)
 334                 return 0;
 335
 336         for (i = 0; i < bpf->len; ++i) {
 337                 p = &bpf->filter[i];
 338                 switch (BPF_CLASS(p->code)) {
 339                         /*
 340                          * Check that memory operations use valid addresses.
 341                          */
 342                 case BPF_LD:
 343                 case BPF_LDX:
 344                         switch (BPF_MODE(p->code)) {
 345                         case BPF_IMM:
 346                                 break;
 347                         case BPF_ABS:
 348                         case BPF_IND:
 349                         case BPF_MSH:
 350                                 /*
 351                                  * There's no maximum packet data size
 352                                  * in userland.  The runtime packet length
 353                                  * check suffices.
 354                                  */
 355                                 break;
 356                         case BPF_MEM:
 357                                 if (p->k >= BPF_MEMWORDS)
 358                                         return 0;
 359                                 break;
 360                         case BPF_LEN:
 361                                 break;
 362                         default:
 363                                 return 0;
 364                         }
 365                         break;
 366                 case BPF_ST:
 367                 case BPF_STX:
 368                         if (p->k >= BPF_MEMWORDS)
 369                                 return 0;
 370                         break;
 371                 case BPF_ALU:
 372                         switch (BPF_OP(p->code)) {
 373                         case BPF_ADD:
 374                         case BPF_SUB:
 375                         case BPF_MUL:
 376                         case BPF_OR:
 377                         case BPF_AND:
 378                         case BPF_LSH:
 379                         case BPF_RSH:
 380                         case BPF_NEG:
 381                                 break;
 382                         case BPF_DIV:
 383                                 /*
 384                                  * Check for constant division by 0.
 385                                  */
 386                                 if (BPF_RVAL(p->code) == BPF_K && p->k == 0)
 387                                         return 0;
 388                                 break;
 389                         default:
 390                                 return 0;
 391                         }
 392                         break;
 393                 case BPF_JMP:
 394                         /*
 395                          * Check that jumps are within the code block,
 396                          * and that unconditional branches don't go
 397                          * backwards as a result of an overflow.
 398                          * Unconditional branches have a 32-bit offset,
 399                          * so they could overflow; we check to make
 400                          * sure they don't.  Conditional branches have
 401                          * an 8-bit offset, and the from address is <=
 402                          * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
 403                          * is sufficiently small that adding 255 to it
 404                          * won't overflow.
 405                          *
 406                          * We know that len is <= BPF_MAXINSNS, and we
 407                          * assume that BPF_MAXINSNS is < the maximum size
 408                          * of a u_int, so that i + 1 doesn't overflow.
 409                          *
 410                          * For userland, we don't know that the from
 411                          * or len are <= BPF_MAXINSNS, but we know that
 412                          * from <= len, and, except on a 64-bit system,
 413                          * it's unlikely that len, if it truly reflects
 414                          * the size of the program we've been handed,
 415                          * will be anywhere near the maximum size of
 416                          * a u_int.  We also don't check for backward
 417                          * branches, as we currently support them in
 418                          * userland for the protochain operation.
 419                          */
 420                         from = i + 1;
 421                         switch (BPF_OP(p->code)) {
 422                         case BPF_JA:
 423                                 if (from + p->k >= bpf->len)
 424                                         return 0;
 425                                 break;
 426                         case BPF_JEQ:
 427                         case BPF_JGT:
 428                         case BPF_JGE:
 429                         case BPF_JSET:
 430                                 if (from + p->jt >= bpf->len ||
 431                                     from + p->jf >= bpf->len)
 432                                         return 0;
 433                                 break;
 434                         default:
 435                                 return 0;
 436                         }
 437                         break;
 438                 case BPF_RET:
 439                         break;
 440                 case BPF_MISC:
 441                         break;
 442                 default:
 443                         return 0;
 444                 }
 445         }
 446
 447         return BPF_CLASS(bpf->filter[bpf->len - 1].code) == BPF_RET;
 448 }
 449
 450 uint32_t bpf_run_filter(const struct sock_fprog * fcode, uint8_t * packet,
 451                         size_t plen)
 452 {
 453         /* XXX: caplen == len */
 454         uint32_t A, X;
 455         uint32_t k;
 456         struct sock_filter *bpf;
 457         int32_t mem[BPF_MEMWORDS];
 458
 459         if (fcode == NULL || fcode->filter == NULL || fcode->len == 0)
 460                 return 0xFFFFFFFF;
 461
 462         A = 0;
 463         X = 0;
 464
 465         bpf = fcode->filter;
 466
 467         --bpf;
 468         while (1) {
 469
 470                 ++bpf;
 471
 472                 switch (bpf->code) {
 473                 default:
 474                         return 0;
 475                 case BPF_RET | BPF_K:
 476                         return (uint32_t) bpf->k;
 477
 478                 case BPF_RET | BPF_A:
 479                         return (uint32_t) A;
 480
 481                 case BPF_LD | BPF_W | BPF_ABS:
 482                         k = bpf->k;
 483                         if (k + sizeof(int32_t) > plen)
 484                                 return 0;
 485                         A = EXTRACT_LONG(&packet[k]);
 486                         continue;
 487
 488                 case BPF_LD | BPF_H | BPF_ABS:
 489                         k = bpf->k;
 490                         if (k + sizeof(short) > plen)
 491                                 return 0;
 492                         A = EXTRACT_SHORT(&packet[k]);
 493                         continue;
 494
 495                 case BPF_LD | BPF_B | BPF_ABS:
 496                         k = bpf->k;
 497                         if (k >= plen)
 498                                 return 0;
 499                         A = packet[k];
 500                         continue;
 501
 502                 case BPF_LD | BPF_W | BPF_LEN:
 503                         A = plen;
 504                         continue;
 505
 506                 case BPF_LDX | BPF_W | BPF_LEN:
 507                         X = plen;
 508                         continue;
 509
 510                 case BPF_LD | BPF_W | BPF_IND:
 511                         k = X + bpf->k;
 512                         if (k + sizeof(int32_t) > plen)
 513                                 return 0;
 514                         A = EXTRACT_LONG(&packet[k]);
 515                         continue;
 516
 517                 case BPF_LD | BPF_H | BPF_IND:
 518                         k = X + bpf->k;
 519                         if (k + sizeof(short) > plen)
 520                                 return 0;
 521                         A = EXTRACT_SHORT(&packet[k]);
 522                         continue;
 523
 524                 case BPF_LD | BPF_B | BPF_IND:
 525                         k = X + bpf->k;
 526                         if (k >= plen)
 527                                 return 0;
 528                         A = packet[k];
 529                         continue;
 530
 531                 case BPF_LDX | BPF_MSH | BPF_B:
 532                         k = bpf->k;
 533                         if (k >= plen)
 534                                 return 0;
 535                         X = (packet[bpf->k] & 0xf) << 2;
 536                         continue;
 537
 538                 case BPF_LD | BPF_IMM:
 539                         A = bpf->k;
 540                         continue;
 541
 542                 case BPF_LDX | BPF_IMM:
 543                         X = bpf->k;
 544                         continue;
 545
 546                 case BPF_LD | BPF_MEM:
 547                         A = mem[bpf->k];
 548                         continue;
 549
 550                 case BPF_LDX | BPF_MEM:
 551                         X = mem[bpf->k];
 552                         continue;
 553
 554                 case BPF_ST:
 555                         mem[bpf->k] = A;
 556                         continue;
 557
 558                 case BPF_STX:
 559                         mem[bpf->k] = X;
 560                         continue;
 561
 562                 case BPF_JMP | BPF_JA:
 563                         bpf += bpf->k;
 564                         continue;
 565
 566                 case BPF_JMP | BPF_JGT | BPF_K:
 567                         bpf += (A > bpf->k) ? bpf->jt : bpf->jf;
 568                         continue;
 569
 570                 case BPF_JMP | BPF_JGE | BPF_K:
 571                         bpf += (A >= bpf->k) ? bpf->jt : bpf->jf;
 572                         continue;
 573
 574                 case BPF_JMP | BPF_JEQ | BPF_K:
 575                         bpf += (A == bpf->k) ? bpf->jt : bpf->jf;
 576                         continue;
 577
 578                 case BPF_JMP | BPF_JSET | BPF_K:
 579                         bpf += (A & bpf->k) ? bpf->jt : bpf->jf;
 580                         continue;
 581
 582                 case BPF_JMP | BPF_JGT | BPF_X:
 583                         bpf += (A > X) ? bpf->jt : bpf->jf;
 584                         continue;
 585
 586                 case BPF_JMP | BPF_JGE | BPF_X:
 587                         bpf += (A >= X) ? bpf->jt : bpf->jf;
 588                         continue;
 589
 590                 case BPF_JMP | BPF_JEQ | BPF_X:
 591                         bpf += (A == X) ? bpf->jt : bpf->jf;
 592                         continue;
 593
 594                 case BPF_JMP | BPF_JSET | BPF_X:
 595                         bpf += (A & X) ? bpf->jt : bpf->jf;
 596                         continue;
 597
 598                 case BPF_ALU | BPF_ADD | BPF_X:
 599                         A += X;
 600                         continue;
 601
 602                 case BPF_ALU | BPF_SUB | BPF_X:
 603                         A -= X;
 604                         continue;
 605
 606                 case BPF_ALU | BPF_MUL | BPF_X:
 607                         A *= X;
 608                         continue;
 609
 610                 case BPF_ALU | BPF_DIV | BPF_X:
 611                         if (X == 0)
 612                                 return 0;
 613                         A /= X;
 614                         continue;
 615
 616                 case BPF_ALU | BPF_AND | BPF_X:
 617                         A &= X;
 618                         continue;
 619
 620                 case BPF_ALU | BPF_OR | BPF_X:
 621                         A |= X;
 622                         continue;
 623
 624                 case BPF_ALU | BPF_LSH | BPF_X:
 625                         A <<= X;
 626                         continue;
 627
 628                 case BPF_ALU | BPF_RSH | BPF_X:
 629                         A >>= X;
 630                         continue;
 631
 632                 case BPF_ALU | BPF_ADD | BPF_K:
 633                         A += bpf->k;
 634                         continue;
 635
 636                 case BPF_ALU | BPF_SUB | BPF_K:
 637                         A -= bpf->k;
 638                         continue;
 639
 640                 case BPF_ALU | BPF_MUL | BPF_K:
 641                         A *= bpf->k;
 642                         continue;
 643
 644                 case BPF_ALU | BPF_DIV | BPF_K:
 645                         A /= bpf->k;
 646                         continue;
 647
 648                 case BPF_ALU | BPF_AND | BPF_K:
 649                         A &= bpf->k;
 650                         continue;
 651
 652                 case BPF_ALU | BPF_OR | BPF_K:
 653                         A |= bpf->k;
 654                         continue;
 655
 656                 case BPF_ALU | BPF_LSH | BPF_K:
 657                         A <<= bpf->k;
 658                         continue;
 659
 660                 case BPF_ALU | BPF_RSH | BPF_K:
 661                         A >>= bpf->k;
 662                         continue;
 663
 664                 case BPF_ALU | BPF_NEG:
 665                         A = -A;
 666                         continue;
 667
 668                 case BPF_MISC | BPF_TAX:
 669                         X = A;
 670                         continue;
 671
 672                 case BPF_MISC | BPF_TXA:
 673                         A = X;
 674                         continue;
 675                 }
 676         }
 677 }
 678
 679 void bpf_parse_rules(char *rulefile, struct sock_fprog *bpf)
 680 {
 681         int ret;
 682         char buff[256];
 683         struct sock_filter sf_single = { 0x06, 0, 0, 0xFFFFFFFF };
 684
 685         if (rulefile == NULL) {
 686                 bpf->len = 1;
 687                 bpf->filter = xmalloc(sizeof(sf_single));
 688                 memcpy(&bpf->filter[0], &sf_single, sizeof(sf_single));
 689                 return;
 690         }
 691
 692         FILE *fp = fopen(rulefile, "r");
 693         if (!fp)
 694                 panic("Cannot read BPF rule file!\n");
 695
 696         memset(buff, 0, sizeof(buff));
 697
 698         while (fgets(buff, sizeof(buff), fp) != NULL) {
 699                 buff[sizeof(buff) - 1] = 0;
 700
 701                 /* A comment. Skip this line */
 702                 if (buff[0] != '{') {
 703                         memset(buff, 0, sizeof(buff));
 704                         continue;
 705                 }
 706
 707                 memset(&sf_single, 0, sizeof(sf_single));
 708                 ret = sscanf(buff, "{ 0x%x, %u, %u, 0x%08x },",
 709                              (unsigned int *) &sf_single.code,
 710                              (unsigned int *) &sf_single.jt,
 711                              (unsigned int *) &sf_single.jf,
 712                              (unsigned int *) &sf_single.k);
 713                 if (ret != 4)
 714                         /* No valid bpf opcode format or a syntax error */
 715                         panic("BPF syntax error!\n");
 716
 717                 bpf->len++;
 718                 bpf->filter = xrealloc(bpf->filter, 1,
 719                                        bpf->len * sizeof(sf_single));
 720                 memcpy(&bpf->filter[bpf->len - 1], &sf_single,
 721                        sizeof(sf_single));
 722
 723                 memset(buff, 0, sizeof(buff));
 724         }
 725
 726         fclose(fp);
 727
 728         if (bpf_validate(bpf) == 0)
 729                 panic("This is not a valid BPF program!\n");
 730 }