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
  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         switch (bpf.code) {
  63         default:
  64                 op = "unimp";
  65                 fmt = "0x%x";
  66                 v = bpf.code;
  67                 break;
  68         case BPF_RET | BPF_K:
  69                 op = "ret";
  70                 fmt = "#%d";
  71                 break;
  72         case BPF_RET | BPF_A:
  73                 op = "ret";
  74                 fmt = "";
  75                 break;
  76         case BPF_LD | BPF_W | BPF_ABS:
  77                 op = "ld";
  78                 fmt = "[%d]";
  79                 break;
  80         case BPF_LD | BPF_H | BPF_ABS:
  81                 op = "ldh";
  82                 fmt = "[%d]";
  83                 break;
  84         case BPF_LD | BPF_B | BPF_ABS:
  85                 op = "ldb";
  86                 fmt = "[%d]";
  87                 break;
  88         case BPF_LD | BPF_W | BPF_LEN:
  89                 op = "ld";
  90                 fmt = "#pktlen";
  91                 break;
  92         case BPF_LD | BPF_W | BPF_IND:
  93                 op = "ld";
  94                 fmt = "[x + %d]";
  95                 break;
  96         case BPF_LD | BPF_H | BPF_IND:
  97                 op = "ldh";
  98                 fmt = "[x + %d]";
  99                 break;
 100         case BPF_LD | BPF_B | BPF_IND:
 101                 op = "ldb";
 102                 fmt = "[x + %d]";
 103                 break;
 104         case BPF_LD | BPF_IMM:
 105                 op = "ld";
 106                 fmt = "#0x%x";
 107                 break;
 108         case BPF_LDX | BPF_IMM:
 109                 op = "ldx";
 110                 fmt = "#0x%x";
 111                 break;
 112         case BPF_LDX | BPF_MSH | BPF_B:
 113                 op = "ldxb";
 114                 fmt = "4*([%d]&0xf)";
 115                 break;
 116         case BPF_LD | BPF_MEM:
 117                 op = "ld";
 118                 fmt = "M[%d]";
 119                 break;
 120         case BPF_LDX | BPF_MEM:
 121                 op = "ldx";
 122                 fmt = "M[%d]";
 123                 break;
 124         case BPF_ST:
 125                 op = "st";
 126                 fmt = "M[%d]";
 127                 break;
 128         case BPF_STX:
 129                 op = "stx";
 130                 fmt = "M[%d]";
 131                 break;
 132         case BPF_JMP | BPF_JA:
 133                 op = "ja";
 134                 fmt = "%d";
 135                 v = n + 1 + bpf.k;
 136                 break;
 137         case BPF_JMP | BPF_JGT | BPF_K:
 138                 op = "jgt";
 139                 fmt = "#0x%x";
 140                 break;
 141         case BPF_JMP | BPF_JGE | BPF_K:
 142                 op = "jge";
 143                 fmt = "#0x%x";
 144                 break;
 145         case BPF_JMP | BPF_JEQ | BPF_K:
 146                 op = "jeq";
 147                 fmt = "#0x%x";
 148                 break;
 149         case BPF_JMP | BPF_JSET | BPF_K:
 150                 op = "jset";
 151                 fmt = "#0x%x";
 152                 break;
 153         case BPF_JMP | BPF_JGT | BPF_X:
 154                 op = "jgt";
 155                 fmt = "x";
 156                 break;
 157         case BPF_JMP | BPF_JGE | BPF_X:
 158                 op = "jge";
 159                 fmt = "x";
 160                 break;
 161         case BPF_JMP | BPF_JEQ | BPF_X:
 162                 op = "jeq";
 163                 fmt = "x";
 164                 break;
 165         case BPF_JMP | BPF_JSET | BPF_X:
 166                 op = "jset";
 167                 fmt = "x";
 168                 break;
 169         case BPF_ALU | BPF_ADD | BPF_X:
 170                 op = "add";
 171                 fmt = "x";
 172                 break;
 173         case BPF_ALU | BPF_SUB | BPF_X:
 174                 op = "sub";
 175                 fmt = "x";
 176                 break;
 177         case BPF_ALU | BPF_MUL | BPF_X:
 178                 op = "mul";
 179                 fmt = "x";
 180                 break;
 181         case BPF_ALU | BPF_DIV | BPF_X:
 182                 op = "div";
 183                 fmt = "x";
 184                 break;
 185         case BPF_ALU | BPF_AND | BPF_X:
 186                 op = "and";
 187                 fmt = "x";
 188                 break;
 189         case BPF_ALU | BPF_OR | BPF_X:
 190                 op = "or";
 191                 fmt = "x";
 192                 break;
 193         case BPF_ALU | BPF_LSH | BPF_X:
 194                 op = "lsh";
 195                 fmt = "x";
 196                 break;
 197         case BPF_ALU | BPF_RSH | BPF_X:
 198                 op = "rsh";
 199                 fmt = "x";
 200                 break;
 201         case BPF_ALU | BPF_ADD | BPF_K:
 202                 op = "add";
 203                 fmt = "#%d";
 204                 break;
 205         case BPF_ALU | BPF_SUB | BPF_K:
 206                 op = "sub";
 207                 fmt = "#%d";
 208                 break;
 209         case BPF_ALU | BPF_MUL | BPF_K:
 210                 op = "mul";
 211                 fmt = "#%d";
 212                 break;
 213         case BPF_ALU | BPF_DIV | BPF_K:
 214                 op = "div";
 215                 fmt = "#%d";
 216                 break;
 217         case BPF_ALU | BPF_AND | BPF_K:
 218                 op = "and";
 219                 fmt = "#0x%x";
 220                 break;
 221         case BPF_ALU | BPF_OR | BPF_K:
 222                 op = "or";
 223                 fmt = "#0x%x";
 224                 break;
 225         case BPF_ALU | BPF_LSH | BPF_K:
 226                 op = "lsh";
 227                 fmt = "#%d";
 228                 break;
 229         case BPF_ALU | BPF_RSH | BPF_K:
 230                 op = "rsh";
 231                 fmt = "#%d";
 232                 break;
 233         case BPF_ALU | BPF_NEG:
 234                 op = "neg";
 235                 fmt = "";
 236                 break;
 237         case BPF_MISC | BPF_TAX:
 238                 op = "tax";
 239                 fmt = "";
 240                 break;
 241         case BPF_MISC | BPF_TXA:
 242                 op = "txa";
 243                 fmt = "";
 244                 break;
 245         }
 246         slprintf(operand, sizeof(operand), fmt, v);
 247         slprintf(image, sizeof(image),
 248                  (BPF_CLASS(bpf.code) == BPF_JMP &&
 249                   BPF_OP(bpf.code) != BPF_JA) ?
 250                  "(%03d) %-8s %-16s jt %d\tjf %d" : "(%03d) %-8s %s",
 251                  n, op, operand, n + 1 + bpf.jt, n + 1 + bpf.jf);
 252         return image;
 253 }
 254
 255 void bpf_dump_all(struct sock_fprog *bpf)
 256 {
 257         int i;
 258         for (i = 0; i < bpf->len; ++i)
 259                 printf("%s\n", bpf_dump(bpf->filter[i], i));
 260 }
 261
 262 void bpf_attach_to_sock(int sock, struct sock_fprog *bpf)
 263 {
 264         int ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, bpf,
 265                              sizeof(*bpf));
 266         if (ret < 0)
 267                 panic("Cannot attach filter to socket!\n");
 268 }
 269
 270 void bpf_detach_from_sock(int sock)
 271 {
 272         int ret, empty = 0;
 273         ret = setsockopt(sock, SOL_SOCKET, SO_DETACH_FILTER, &empty,
 274                          sizeof(empty));
 275         if (ret < 0)
 276                 panic("Cannot detach filter from socket!\n");
 277 }
 278
 279 int bpf_validate(const struct sock_fprog *bpf)
 280 {
 281         uint32_t i, from;
 282         const struct sock_filter *p;
 283
 284         if (!bpf)
 285                 return 0;
 286         if (bpf->len < 1)
 287                 return 0;
 288         for (i = 0; i < bpf->len; ++i) {
 289                 p = &bpf->filter[i];
 290                 switch (BPF_CLASS(p->code)) {
 291                         /*
 292                          * Check that memory operations use valid addresses.
 293                          */
 294                 case BPF_LD:
 295                 case BPF_LDX:
 296                         switch (BPF_MODE(p->code)) {
 297                         case BPF_IMM:
 298                                 break;
 299                         case BPF_ABS:
 300                         case BPF_IND:
 301                         case BPF_MSH:
 302                                 /*
 303                                  * There's no maximum packet data size
 304                                  * in userland.  The runtime packet length
 305                                  * check suffices.
 306                                  */
 307                                 break;
 308                         case BPF_MEM:
 309                                 if (p->k >= BPF_MEMWORDS)
 310                                         return 0;
 311                                 break;
 312                         case BPF_LEN:
 313                                 break;
 314                         default:
 315                                 return 0;
 316                         }
 317                         break;
 318                 case BPF_ST:
 319                 case BPF_STX:
 320                         if (p->k >= BPF_MEMWORDS)
 321                                 return 0;
 322                         break;
 323                 case BPF_ALU:
 324                         switch (BPF_OP(p->code)) {
 325                         case BPF_ADD:
 326                         case BPF_SUB:
 327                         case BPF_MUL:
 328                         case BPF_OR:
 329                         case BPF_AND:
 330                         case BPF_LSH:
 331                         case BPF_RSH:
 332                         case BPF_NEG:
 333                                 break;
 334                         case BPF_DIV:
 335                                 /*
 336                                  * Check for constant division by 0.
 337                                  */
 338                                 if (BPF_RVAL(p->code) == BPF_K && p->k == 0)
 339                                         return 0;
 340                                 break;
 341                         default:
 342                                 return 0;
 343                         }
 344                         break;
 345                 case BPF_JMP:
 346                         /*
 347                          * Check that jumps are within the code block,
 348                          * and that unconditional branches don't go
 349                          * backwards as a result of an overflow.
 350                          * Unconditional branches have a 32-bit offset,
 351                          * so they could overflow; we check to make
 352                          * sure they don't.  Conditional branches have
 353                          * an 8-bit offset, and the from address is <=
 354                          * BPF_MAXINSNS, and we assume that BPF_MAXINSNS
 355                          * is sufficiently small that adding 255 to it
 356                          * won't overflow.
 357                          *
 358                          * We know that len is <= BPF_MAXINSNS, and we
 359                          * assume that BPF_MAXINSNS is < the maximum size
 360                          * of a u_int, so that i + 1 doesn't overflow.
 361                          *
 362                          * For userland, we don't know that the from
 363                          * or len are <= BPF_MAXINSNS, but we know that
 364                          * from <= len, and, except on a 64-bit system,
 365                          * it's unlikely that len, if it truly reflects
 366                          * the size of the program we've been handed,
 367                          * will be anywhere near the maximum size of
 368                          * a u_int.  We also don't check for backward
 369                          * branches, as we currently support them in
 370                          * userland for the protochain operation.
 371                          */
 372                         from = i + 1;
 373                         switch (BPF_OP(p->code)) {
 374                         case BPF_JA:
 375                                 if (from + p->k >= bpf->len)
 376                                         return 0;
 377                                 break;
 378                         case BPF_JEQ:
 379                         case BPF_JGT:
 380                         case BPF_JGE:
 381                         case BPF_JSET:
 382                                 if (from + p->jt >= bpf->len ||
 383                                     from + p->jf >= bpf->len)
 384                                         return 0;
 385                                 break;
 386                         default:
 387                                 return 0;
 388                         }
 389                         break;
 390                 case BPF_RET:
 391                         break;
 392                 case BPF_MISC:
 393                         break;
 394                 default:
 395                         return 0;
 396                 }
 397         }
 398
 399         return BPF_CLASS(bpf->filter[bpf->len - 1].code) == BPF_RET;
 400 }
 401
 402 uint32_t bpf_run_filter(const struct sock_fprog * fcode, uint8_t * packet,
 403                         size_t plen)
 404 {
 405         /* XXX: caplen == len */
 406         uint32_t A, X;
 407         uint32_t k;
 408         struct sock_filter *bpf;
 409         int32_t mem[BPF_MEMWORDS];
 410
 411         if (fcode == NULL || fcode->filter == NULL || fcode->len == 0)
 412                 return 0xFFFFFFFF;
 413
 414         A = 0;
 415         X = 0;
 416         bpf = fcode->filter;
 417         --bpf;
 418         while (1) {
 419                 ++bpf;
 420
 421                 switch (bpf->code) {
 422                 default:
 423                         return 0;
 424                 case BPF_RET | BPF_K:
 425                         return (uint32_t) bpf->k;
 426                 case BPF_RET | BPF_A:
 427                         return (uint32_t) A;
 428                 case BPF_LD | BPF_W | BPF_ABS:
 429                         k = bpf->k;
 430                         if (k + sizeof(int32_t) > plen)
 431                                 return 0;
 432                         A = EXTRACT_LONG(&packet[k]);
 433                         continue;
 434                 case BPF_LD | BPF_H | BPF_ABS:
 435                         k = bpf->k;
 436                         if (k + sizeof(short) > plen)
 437                                 return 0;
 438                         A = EXTRACT_SHORT(&packet[k]);
 439                         continue;
 440                 case BPF_LD | BPF_B | BPF_ABS:
 441                         k = bpf->k;
 442                         if (k >= plen)
 443                                 return 0;
 444                         A = packet[k];
 445                         continue;
 446                 case BPF_LD | BPF_W | BPF_LEN:
 447                         A = plen;
 448                         continue;
 449                 case BPF_LDX | BPF_W | BPF_LEN:
 450                         X = plen;
 451                         continue;
 452                 case BPF_LD | BPF_W | BPF_IND:
 453                         k = X + bpf->k;
 454                         if (k + sizeof(int32_t) > plen)
 455                                 return 0;
 456                         A = EXTRACT_LONG(&packet[k]);
 457                         continue;
 458                 case BPF_LD | BPF_H | BPF_IND:
 459                         k = X + bpf->k;
 460                         if (k + sizeof(short) > plen)
 461                                 return 0;
 462                         A = EXTRACT_SHORT(&packet[k]);
 463                         continue;
 464                 case BPF_LD | BPF_B | BPF_IND:
 465                         k = X + bpf->k;
 466                         if (k >= plen)
 467                                 return 0;
 468                         A = packet[k];
 469                         continue;
 470                 case BPF_LDX | BPF_MSH | BPF_B:
 471                         k = bpf->k;
 472                         if (k >= plen)
 473                                 return 0;
 474                         X = (packet[bpf->k] & 0xf) << 2;
 475                         continue;
 476                 case BPF_LD | BPF_IMM:
 477                         A = bpf->k;
 478                         continue;
 479                 case BPF_LDX | BPF_IMM:
 480                         X = bpf->k;
 481                         continue;
 482                 case BPF_LD | BPF_MEM:
 483                         A = mem[bpf->k];
 484                         continue;
 485                 case BPF_LDX | BPF_MEM:
 486                         X = mem[bpf->k];
 487                         continue;
 488                 case BPF_ST:
 489                         mem[bpf->k] = A;
 490                         continue;
 491                 case BPF_STX:
 492                         mem[bpf->k] = X;
 493                         continue;
 494                 case BPF_JMP | BPF_JA:
 495                         bpf += bpf->k;
 496                         continue;
 497                 case BPF_JMP | BPF_JGT | BPF_K:
 498                         bpf += (A > bpf->k) ? bpf->jt : bpf->jf;
 499                         continue;
 500                 case BPF_JMP | BPF_JGE | BPF_K:
 501                         bpf += (A >= bpf->k) ? bpf->jt : bpf->jf;
 502                         continue;
 503                 case BPF_JMP | BPF_JEQ | BPF_K:
 504                         bpf += (A == bpf->k) ? bpf->jt : bpf->jf;
 505                         continue;
 506                 case BPF_JMP | BPF_JSET | BPF_K:
 507                         bpf += (A & bpf->k) ? bpf->jt : bpf->jf;
 508                         continue;
 509                 case BPF_JMP | BPF_JGT | BPF_X:
 510                         bpf += (A > X) ? bpf->jt : bpf->jf;
 511                         continue;
 512                 case BPF_JMP | BPF_JGE | BPF_X:
 513                         bpf += (A >= X) ? bpf->jt : bpf->jf;
 514                         continue;
 515                 case BPF_JMP | BPF_JEQ | BPF_X:
 516                         bpf += (A == X) ? bpf->jt : bpf->jf;
 517                         continue;
 518                 case BPF_JMP | BPF_JSET | BPF_X:
 519                         bpf += (A & X) ? bpf->jt : bpf->jf;
 520                         continue;
 521                 case BPF_ALU | BPF_ADD | BPF_X:
 522                         A += X;
 523                         continue;
 524                 case BPF_ALU | BPF_SUB | BPF_X:
 525                         A -= X;
 526                         continue;
 527                 case BPF_ALU | BPF_MUL | BPF_X:
 528                         A *= X;
 529                         continue;
 530                 case BPF_ALU | BPF_DIV | BPF_X:
 531                         if (X == 0)
 532                                 return 0;
 533                         A /= X;
 534                         continue;
 535                 case BPF_ALU | BPF_AND | BPF_X:
 536                         A &= X;
 537                         continue;
 538                 case BPF_ALU | BPF_OR | BPF_X:
 539                         A |= X;
 540                         continue;
 541                 case BPF_ALU | BPF_LSH | BPF_X:
 542                         A <<= X;
 543                         continue;
 544                 case BPF_ALU | BPF_RSH | BPF_X:
 545                         A >>= X;
 546                         continue;
 547                 case BPF_ALU | BPF_ADD | BPF_K:
 548                         A += bpf->k;
 549                         continue;
 550                 case BPF_ALU | BPF_SUB | BPF_K:
 551                         A -= bpf->k;
 552                         continue;
 553                 case BPF_ALU | BPF_MUL | BPF_K:
 554                         A *= bpf->k;
 555                         continue;
 556                 case BPF_ALU | BPF_DIV | BPF_K:
 557                         A /= bpf->k;
 558                         continue;
 559                 case BPF_ALU | BPF_AND | BPF_K:
 560                         A &= bpf->k;
 561                         continue;
 562                 case BPF_ALU | BPF_OR | BPF_K:
 563                         A |= bpf->k;
 564                         continue;
 565                 case BPF_ALU | BPF_LSH | BPF_K:
 566                         A <<= bpf->k;
 567                         continue;
 568                 case BPF_ALU | BPF_RSH | BPF_K:
 569                         A >>= bpf->k;
 570                         continue;
 571                 case BPF_ALU | BPF_NEG:
 572                         A = -A;
 573                         continue;
 574                 case BPF_MISC | BPF_TAX:
 575                         X = A;
 576                         continue;
 577                 case BPF_MISC | BPF_TXA:
 578                         A = X;
 579                         continue;
 580                 }
 581         }
 582 }
 583
 584 void bpf_parse_rules(char *rulefile, struct sock_fprog *bpf)
 585 {
 586         int ret;
 587         char buff[256];
 588         struct sock_filter sf_single = { 0x06, 0, 0, 0xFFFFFFFF };
 589
 590         if (rulefile == NULL) {
 591                 bpf->len = 1;
 592                 bpf->filter = xmalloc(sizeof(sf_single));
 593                 memcpy(&bpf->filter[0], &sf_single, sizeof(sf_single));
 594                 return;
 595         }
 596
 597         FILE *fp = fopen(rulefile, "r");
 598         if (!fp)
 599                 panic("Cannot read BPF rule file!\n");
 600         memset(buff, 0, sizeof(buff));
 601
 602         while (fgets(buff, sizeof(buff), fp) != NULL) {
 603                 buff[sizeof(buff) - 1] = 0;
 604                 /* A comment. Skip this line */
 605                 if (buff[0] != '{') {
 606                         memset(buff, 0, sizeof(buff));
 607                         continue;
 608                 }
 609
 610                 memset(&sf_single, 0, sizeof(sf_single));
 611                 ret = sscanf(buff, "{ 0x%x, %u, %u, 0x%08x },",
 612                              (unsigned int *) &sf_single.code,
 613                              (unsigned int *) &sf_single.jt,
 614                              (unsigned int *) &sf_single.jf,
 615                              (unsigned int *) &sf_single.k);
 616                 if (ret != 4)
 617                         /* No valid bpf opcode format or a syntax error */
 618                         panic("BPF syntax error!\n");
 619                 bpf->len++;
 620                 bpf->filter = xrealloc(bpf->filter, 1,
 621                                        bpf->len * sizeof(sf_single));
 622                 memcpy(&bpf->filter[bpf->len - 1], &sf_single,
 623                        sizeof(sf_single));
 624
 625                 memset(buff, 0, sizeof(buff));
 626         }
 627
 628         fclose(fp);
 629         if (bpf_validate(bpf) == 0)
 630                 panic("This is not a valid BPF program!\n");
 631 }