src/tun/regex.c

   1 /*
   2      This file is part of GNUnet
   3      (C) 2012, 2013 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20 /**
  21  * @file src/tun/regex.c
  22  * @brief functions to convert IP networks to regexes
  23  * @author Maximilian Szengel
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_util_lib.h"
  28 #include "gnunet_tun_lib.h"
  29
  30
  31 /**
  32  * Create a regex in @a rxstr from the given @a ip and @a netmask.
  33  *
  34  * @param ip IPv4 representation.
  35  * @param port destination port
  36  * @param rxstr generated regex, must be at least #GNUNET_TUN_IPV4_REGEXLEN
  37  *              bytes long.
  38  */
  39 void
  40 GNUNET_TUN_ipv4toregexsearch (const struct in_addr *ip,
  41                               uint16_t port,
  42                               char *rxstr)
  43 {
  44   GNUNET_snprintf (rxstr,
  45                    GNUNET_TUN_IPV4_REGEXLEN,
  46                    "4-%04X-%08X",
  47                    (unsigned int) port,
  48                    ntohl (ip->s_addr));
  49 }
  50
  51
  52 /**
  53  * Create a regex in @a rxstr from the given @a ipv6 and @a prefixlen.
  54  *
  55  * @param ipv6 IPv6 representation.
  56  * @param port destination port
  57  * @param rxstr generated regex, must be at least #GNUNET_TUN_IPV6_REGEXLEN
  58  *              bytes long.
  59  */
  60 void
  61 GNUNET_TUN_ipv6toregexsearch (const struct in6_addr *ipv6,
  62                               uint16_t port,
  63                               char *rxstr)
  64 {
  65   const uint32_t *addr;
  66
  67   addr = (const uint32_t *) ipv6;
  68   GNUNET_snprintf (rxstr,
  69                    GNUNET_TUN_IPV6_REGEXLEN,
  70                    "6-%04X-%08X%08X%08X%08X",
  71                    (unsigned int) port,
  72                    ntohl (addr[0]),
  73                    ntohl (addr[1]),
  74                    ntohl (addr[2]),
  75                    ntohl (addr[3]));
  76 }
  77
  78
  79 /**
  80  * Convert the given 4-bit (!) number to a regex.
  81  *
  82  * @param value the value, only the lowest 4 bits will be looked at
  83  * @param mask which bits in value are wildcards (any value)?
  84  */
  85 static char *
  86 nibble_to_regex (uint8_t value,
  87                  uint8_t mask)
  88 {
  89   char *ret;
  90
  91   value &= mask;
  92   switch (mask)
  93   {
  94   case 0:
  95     return GNUNET_strdup ("."); /* wildcard */
  96   case 8:
  97     GNUNET_asprintf (&ret,
  98                      "(%X|%X|%X|%X|%X|%X|%X|%X)",
  99                      value,
 100                      value + 1,
 101                      value + 2,
 102                      value + 3,
 103                      value + 4,
 104                      value + 5,
 105                      value + 6,
 106                      value + 7);
 107     return ret;
 108   case 12:
 109     GNUNET_asprintf (&ret,
 110                      "(%X|%X|%X|%X)",
 111                      value,
 112                      value + 1,
 113                      value + 2,
 114                      value + 3);
 115     return ret;
 116   case 14:
 117     GNUNET_asprintf (&ret,
 118                      "(%X|%X)",
 119                      value,
 120                      value + 1);
 121     return ret;
 122   case 15:
 123     GNUNET_asprintf (&ret,
 124                      "%X",
 125                      value);
 126     return ret;
 127   default:
 128     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 129                 _("Bad mask: %d\n"),
 130                 mask);
 131     GNUNET_break (0);
 132     return NULL;
 133   }
 134 }
 135
 136
 137 /**
 138  * Convert the given 16-bit number to a regex.
 139  *
 140  * @param value the value
 141  * @param mask which bits in value are wildcards (any value)?
 142  */
 143 static char *
 144 num_to_regex (uint16_t value,
 145               uint16_t mask)
 146 {
 147   const uint8_t *v = (const uint8_t *) &value;
 148   const uint8_t *m = (const uint8_t *) &mask;
 149   char *a;
 150   char *b;
 151   char *c;
 152   char *d;
 153   char *ret;
 154
 155   a = nibble_to_regex (v[0] >> 4, m[0] >> 4);
 156   b = nibble_to_regex (v[0] & 15, m[0] & 15);
 157   c = nibble_to_regex (v[1] >> 4, m[1] >> 4);
 158   d = nibble_to_regex (v[1] & 15, m[1] & 15);
 159   ret = NULL;
 160   if ( (NULL != a) &&
 161        (NULL != b) &&
 162        (NULL != c) &&
 163        (NULL != d) )
 164     GNUNET_asprintf (&ret,
 165                      "%s%s%s%s",
 166                      a, b, c, d);
 167   GNUNET_free_non_null (a);
 168   GNUNET_free_non_null (b);
 169   GNUNET_free_non_null (c);
 170   GNUNET_free_non_null (d);
 171   return ret;
 172 }
 173
 174
 175 /**
 176  * Do we need to put parents around the given argument?
 177  *
 178  * @param arg part of a regular expression
 179  * @return #GNUNET_YES if we should parens,
 180  *         #GNUNET_NO if not
 181  */
 182 static int
 183 needs_parens (const char *arg)
 184 {
 185   size_t off;
 186   size_t len;
 187   unsigned int op;
 188
 189   op = 0;
 190   len = strlen (arg);
 191   for (off=0;off<len;off++)
 192   {
 193     switch (arg[off])
 194     {
 195     case '(':
 196       op++;
 197       break;
 198     case ')':
 199       GNUNET_assert (op > 0);
 200       op--;
 201       break;
 202     case '|':
 203       if (0 == op)
 204         return GNUNET_YES;
 205       break;
 206     default:
 207       break;
 208     }
 209   }
 210   return GNUNET_NO;
 211 }
 212
 213
 214 /**
 215  * Compute port policy for the given range of
 216  * port numbers.
 217  *
 218  * @param start starting offset
 219  * @param end end offset
 220  * @param step increment level (power of 16)
 221  * @param pp port policy to convert
 222  * @return corresponding regex
 223  */
 224 static char *
 225 compute_policy (unsigned int start,
 226                 unsigned int end,
 227                 unsigned int step,
 228                 const struct GNUNET_STRINGS_PortPolicy *pp)
 229 {
 230   unsigned int i;
 231   char before[36]; /* 16 * 2 + 3 dots + 0-terminator */
 232   char middlel[33]; /* 16 * 2 + 0-terminator */
 233   char middleh[33]; /* 16 * 2 + 0-terminator */
 234   char after[36]; /* 16 * 2 + 3 dots + 0-terminator */
 235   char beforep[36+2]; /* 16 * 2 + 3 dots + 0-terminator + ()*/
 236   char middlehp[33+2]; /* 16 * 2 + 0-terminator + () */
 237   char middlelp[33+2]; /* 16 * 2 + 0-terminator + () */
 238   char afterp[36+2]; /* 16 * 2 + 3 dots + 0-terminator + () */
 239   char dots[4];
 240   char buf[3];
 241   char *middle;
 242   char *ret;
 243   unsigned int xstep;
 244   char *recl;
 245   char *rech;
 246   char *reclp;
 247   char *rechp;
 248   unsigned int start_port;
 249   unsigned int end_port;
 250
 251   GNUNET_assert (GNUNET_YES == pp->negate_portrange);
 252   start_port = pp->start_port;
 253   if (1 == start_port)
 254     start_port = 0;
 255   end_port = pp->end_port;
 256   GNUNET_assert ((end - start) / step <= 0xF);
 257   before[0] = '\0';
 258   middlel[0] = '\0';
 259   middleh[0] = '\0';
 260   after[0] = '\0';
 261   for (i=start;i<=end;i+=step)
 262   {
 263     GNUNET_snprintf (buf,
 264                      sizeof (buf),
 265                      "%X|",
 266                      (i - start) / step);
 267     if (i / step < start_port / step)
 268       strcat (before, buf);
 269     else if (i / step > end_port / step)
 270       strcat (after, buf);
 271     else if (i / step == start_port / step)
 272       strcat (middlel, buf);
 273     else if (i / step == end_port / step)
 274       strcat (middleh, buf);
 275   }
 276   if (strlen (before) > 0)
 277     before[strlen (before)-1] = '\0';
 278   if (strlen (middlel) > 0)
 279     middlel[strlen (middlel)-1] = '\0';
 280   if (strlen (middleh) > 0)
 281     middleh[strlen (middleh)-1] = '\0';
 282   if (strlen (after) > 0)
 283     after[strlen (after)-1] = '\0';
 284   if (needs_parens (before))
 285     GNUNET_snprintf (beforep,
 286                      sizeof (beforep),
 287                      "(%s)",
 288                      before);
 289   else
 290     strcpy (beforep, before);
 291   if (needs_parens (middlel))
 292     GNUNET_snprintf (middlelp,
 293                      sizeof (middlelp),
 294                      "(%s)",
 295                      middlel);
 296   else
 297     strcpy (middlelp, middlel);
 298   if (needs_parens (middleh))
 299     GNUNET_snprintf (middlehp,
 300                      sizeof (middlehp),
 301                      "(%s)",
 302                      middleh);
 303   else
 304     strcpy (middlehp, middleh);
 305   if (needs_parens (after))
 306     GNUNET_snprintf (afterp,
 307                      sizeof (afterp),
 308                      "(%s)",
 309                      after);
 310   else
 311     strcpy (afterp, after);
 312   dots[0] = '\0';
 313   for (xstep=step/16;xstep>0;xstep/=16)
 314     strcat (dots, ".");
 315   if (step >= 16)
 316   {
 317     if (strlen (middlel) > 0)
 318       recl = compute_policy ((start_port / step) * step,
 319                              (start_port / step) * step + step - 1,
 320                              step / 16,
 321                              pp);
 322     else
 323       recl = GNUNET_strdup ("");
 324     if (strlen (middleh) > 0)
 325       rech = compute_policy ((end_port / step) * step,
 326                              (end_port / step) * step + step - 1,
 327                              step / 16,
 328                              pp);
 329     else
 330       rech = GNUNET_strdup ("");
 331   }
 332   else
 333   {
 334     recl = GNUNET_strdup ("");
 335     rech = GNUNET_strdup ("");
 336     middlel[0] = '\0';
 337     middlelp[0] = '\0';
 338     middleh[0] = '\0';
 339     middlehp[0] = '\0';
 340   }
 341   if (needs_parens (recl))
 342     GNUNET_asprintf (&reclp,
 343                      "(%s)",
 344                      recl);
 345   else
 346     reclp = GNUNET_strdup (recl);
 347   if (needs_parens (rech))
 348     GNUNET_asprintf (&rechp,
 349                      "(%s)",
 350                      rech);
 351   else
 352     rechp = GNUNET_strdup (rech);
 353
 354   if ( (strlen (middleh) > 0) &&
 355        (strlen (rech) > 0) &&
 356        (strlen (middlel) > 0) &&
 357        (strlen (recl) > 0) )
 358   {
 359     GNUNET_asprintf (&middle,
 360                      "%s%s|%s%s",
 361                      middlel,
 362                      reclp,
 363                      middleh,
 364                      rechp);
 365   }
 366   else if ( (strlen (middleh) > 0) &&
 367             (strlen (rech) > 0) )
 368   {
 369     GNUNET_asprintf (&middle,
 370                      "%s%s",
 371                      middleh,
 372                      rechp);
 373   }
 374   else if ( (strlen (middlel) > 0) &&
 375             (strlen (recl) > 0) )
 376   {
 377     GNUNET_asprintf (&middle,
 378                      "%s%s",
 379                      middlel,
 380                      reclp);
 381   }
 382   else
 383   {
 384     middle = GNUNET_strdup ("");
 385   }
 386   if ( (strlen(before) > 0) &&
 387        (strlen(after) > 0) )
 388   {
 389     if (strlen (dots) > 0)
 390     {
 391       if (strlen (middle) > 0)
 392         GNUNET_asprintf (&ret,
 393                          "(%s%s|%s|%s%s)",
 394                          beforep, dots,
 395                          middle,
 396                          afterp, dots);
 397       else
 398         GNUNET_asprintf (&ret,
 399                          "(%s|%s)%s",
 400                          beforep,
 401                          afterp,
 402                          dots);
 403     }
 404     else
 405     {
 406       if (strlen (middle) > 0)
 407         GNUNET_asprintf (&ret,
 408                          "(%s|%s|%s)",
 409                          before,
 410                          middle,
 411                          after);
 412       else if (1 == step)
 413         GNUNET_asprintf (&ret,
 414                          "%s|%s",
 415                          before,
 416                          after);
 417       else
 418         GNUNET_asprintf (&ret,
 419                          "(%s|%s)",
 420                          before,
 421                          after);
 422     }
 423   }
 424   else if (strlen (before) > 0)
 425   {
 426     if (strlen (dots) > 0)
 427     {
 428       if (strlen (middle) > 0)
 429         GNUNET_asprintf (&ret,
 430                          "(%s%s|%s)",
 431                          beforep, dots,
 432                          middle);
 433       else
 434         GNUNET_asprintf (&ret,
 435                          "%s%s",
 436                          beforep, dots);
 437     }
 438     else
 439     {
 440       if (strlen (middle) > 0)
 441         GNUNET_asprintf (&ret,
 442                          "(%s|%s)",
 443                          before,
 444                          middle);
 445       else
 446         GNUNET_asprintf (&ret,
 447                          "%s",
 448                          before);
 449     }
 450   }
 451   else if (strlen (after) > 0)
 452   {
 453     if (strlen (dots) > 0)
 454     {
 455       if (strlen (middle) > 0)
 456         GNUNET_asprintf (&ret,
 457                          "(%s|%s%s)",
 458                          middle,
 459                          afterp, dots);
 460       else
 461         GNUNET_asprintf (&ret,
 462                          "%s%s",
 463                          afterp, dots);
 464     }
 465     else
 466     {
 467       if (strlen (middle) > 0)
 468         GNUNET_asprintf (&ret,
 469                          "%s|%s",
 470                          middle,
 471                          after);
 472       else
 473         GNUNET_asprintf (&ret,
 474                          "%s",
 475                          after);
 476     }
 477   }
 478   else if (strlen (middle) > 0)
 479   {
 480     GNUNET_asprintf (&ret,
 481                      "%s",
 482                      middle);
 483   }
 484   else
 485   {
 486     ret = GNUNET_strdup ("");
 487   }
 488   GNUNET_free (middle);
 489   GNUNET_free (reclp);
 490   GNUNET_free (rechp);
 491   GNUNET_free (recl);
 492   GNUNET_free (rech);
 493   return ret;
 494 }
 495
 496
 497 /**
 498  * Convert a port policy to a regular expression.  Note: this is a
 499  * very simplistic implementation, we might want to consider doing
 500  * something more sophisiticated (resulting in smaller regular
 501  * expressions) at a later time.
 502  *
 503  * @param pp port policy to convert
 504  * @return NULL on error
 505  */
 506 static char *
 507 port_to_regex (const struct GNUNET_STRINGS_PortPolicy *pp)
 508 {
 509   char *reg;
 510   char *ret;
 511   char *pos;
 512   unsigned int i;
 513   unsigned int cnt;
 514
 515   if ( (0 == pp->start_port) ||
 516        ( (1 == pp->start_port) &&
 517          (0xFFFF == pp->end_port) &&
 518          (GNUNET_NO == pp->negate_portrange)) )
 519     return GNUNET_strdup ("....");
 520   if ( (pp->start_port == pp->end_port) &&
 521        (GNUNET_NO == pp->negate_portrange))
 522   {
 523     GNUNET_asprintf (&ret,
 524                      "%04X",
 525                      pp->start_port);
 526     return ret;
 527   }
 528   if (pp->end_port < pp->start_port)
 529     return NULL;
 530
 531   if (GNUNET_YES == pp->negate_portrange)
 532   {
 533     ret = compute_policy (0, 0xFFFF, 0x1000, pp);
 534   }
 535   else
 536   {
 537     cnt = pp->end_port - pp->start_port + 1;
 538     reg = GNUNET_malloc (cnt * 5 + 1);
 539     pos = reg;
 540     for (i=1;i<=0xFFFF;i++)
 541     {
 542       if ( (i >= pp->start_port) && (i <= pp->end_port) )
 543       {
 544         if (pos == reg)
 545         {
 546           GNUNET_snprintf (pos,
 547                            5,
 548                            "%04X",
 549                            i);
 550         }
 551         else
 552         {
 553           GNUNET_snprintf (pos,
 554                            6,
 555                            "|%04X",
 556                            i);
 557         }
 558         pos += strlen (pos);
 559       }
 560     }
 561     GNUNET_asprintf (&ret,
 562                      "(%s)",
 563                      reg);
 564     GNUNET_free (reg);
 565   }
 566   return ret;
 567 }
 568
 569
 570 /**
 571  * Convert an address (IPv4 or IPv6) to a regex.
 572  *
 573  * @param addr address
 574  * @param mask network mask
 575  * @param len number of bytes in @a addr and @a mask
 576  * @return NULL on error, otherwise regex for the address
 577  */
 578 static char *
 579 address_to_regex (const void *addr,
 580                   const void *mask,
 581                   size_t len)
 582 {
 583   const uint16_t *a = addr;
 584   const uint16_t *m = mask;
 585   char *ret;
 586   char *tmp;
 587   char *reg;
 588   unsigned int i;
 589
 590   ret = NULL;
 591   GNUNET_assert (1 != (len % 2));
 592   for (i=0;i<len / 2;i++)
 593   {
 594     reg = num_to_regex (a[i], m[i]);
 595     if (NULL == reg)
 596     {
 597       GNUNET_free_non_null (ret);
 598       return NULL;
 599     }
 600     if (NULL == ret)
 601     {
 602       ret = reg;
 603     }
 604     else
 605     {
 606       GNUNET_asprintf (&tmp,
 607                        "%s%s",
 608                        ret, reg);
 609       GNUNET_free (ret);
 610       GNUNET_free (reg);
 611       ret = tmp;
 612     }
 613   }
 614   return ret;
 615 }
 616
 617
 618 /**
 619  * Convert a single line of an IPv4 policy to a regular expression.
 620  *
 621  * @param v4 line to convert
 622  * @return NULL on error
 623  */
 624 static char *
 625 ipv4_to_regex (const struct GNUNET_STRINGS_IPv4NetworkPolicy *v4)
 626 {
 627   char *reg;
 628   char *pp;
 629   char *ret;
 630
 631   reg = address_to_regex (&v4->network,
 632                           &v4->netmask,
 633                           sizeof (struct in_addr));
 634   if (NULL == reg)
 635     return NULL;
 636   pp = port_to_regex (&v4->pp);
 637   if (NULL == pp)
 638   {
 639     GNUNET_free (reg);
 640     return NULL;
 641   }
 642   GNUNET_asprintf (&ret,
 643                    "4-%s-%s",
 644                    pp, reg);
 645   GNUNET_free (pp);
 646   GNUNET_free (reg);
 647   return ret;
 648 }
 649
 650
 651 /**
 652  * Convert a single line of an IPv4 policy to a regular expression.
 653  *
 654  * @param v6 line to convert
 655  * @return NULL on error
 656  */
 657 static char *
 658 ipv6_to_regex (const struct GNUNET_STRINGS_IPv6NetworkPolicy *v6)
 659 {
 660   char *reg;
 661   char *pp;
 662   char *ret;
 663
 664   reg = address_to_regex (&v6->network,
 665                           &v6->netmask,
 666                           sizeof (struct in6_addr));
 667   if (NULL == reg)
 668     return NULL;
 669   pp = port_to_regex (&v6->pp);
 670   if (NULL == pp)
 671   {
 672     GNUNET_free (reg);
 673     return NULL;
 674   }
 675   GNUNET_asprintf (&ret,
 676                    "6-%s-%s",
 677                    pp, reg);
 678   GNUNET_free (pp);
 679   GNUNET_free (reg);
 680   return ret;
 681 }
 682
 683
 684 /**
 685  * Convert an exit policy to a regular expression.  The exit policy
 686  * specifies a set of subnets this peer is willing to serve as an
 687  * exit for; the resulting regular expression will match the
 688  * IPv4 address strings as returned by 'GNUNET_TUN_ipv4toregexsearch'.
 689  *
 690  * @param policy exit policy specification
 691  * @return regular expression, NULL on error
 692  */
 693 char *
 694 GNUNET_TUN_ipv4policy2regex (const char *policy)
 695 {
 696   struct GNUNET_STRINGS_IPv4NetworkPolicy *np;
 697   char *reg;
 698   char *tmp;
 699   char *line;
 700   unsigned int i;
 701
 702   np = GNUNET_STRINGS_parse_ipv4_policy (policy);
 703   if (NULL == np)
 704     return NULL;
 705   reg = NULL;
 706   for (i=0; (0 == i) || (0 != np[i].network.s_addr); i++)
 707   {
 708     line = ipv4_to_regex (&np[i]);
 709     if (NULL == line)
 710     {
 711       GNUNET_free_non_null (reg);
 712       GNUNET_free (np);
 713       return NULL;
 714     }
 715     if (NULL == reg)
 716     {
 717       reg = line;
 718     }
 719     else
 720     {
 721       GNUNET_asprintf (&tmp,
 722                        "%s|(%s)",
 723                        reg, line);
 724       GNUNET_free (reg);
 725       GNUNET_free (line);
 726       reg = tmp;
 727     }
 728     if (0 == np[i].network.s_addr)
 729       break;
 730   }
 731   GNUNET_free (np);
 732   return reg;
 733 }
 734
 735
 736 /**
 737  * Convert an exit policy to a regular expression.  The exit policy
 738  * specifies a set of subnets this peer is willing to serve as an
 739  * exit for; the resulting regular expression will match the
 740  * IPv6 address strings as returned by #GNUNET_TUN_ipv6toregexsearch().
 741  *
 742  * @param policy exit policy specification
 743  * @return regular expression, NULL on error
 744  */
 745 char *
 746 GNUNET_TUN_ipv6policy2regex (const char *policy)
 747 {
 748   struct in6_addr zero;
 749   struct GNUNET_STRINGS_IPv6NetworkPolicy *np;
 750   char *reg;
 751   char *tmp;
 752   char *line;
 753   unsigned int i;
 754
 755   np = GNUNET_STRINGS_parse_ipv6_policy (policy);
 756   if (NULL == np)
 757     return NULL;
 758   reg = NULL;
 759   memset (&zero, 0, sizeof (struct in6_addr));
 760   for (i=0; (0 == i) || (0 != memcmp (&zero, &np[i].network, sizeof (struct in6_addr))); i++)
 761   {
 762     line = ipv6_to_regex (&np[i]);
 763     if (NULL == line)
 764     {
 765       GNUNET_free_non_null (reg);
 766       GNUNET_free (np);
 767       return NULL;
 768     }
 769     if (NULL == reg)
 770     {
 771       reg = line;
 772     }
 773     else
 774     {
 775       GNUNET_asprintf (&tmp,
 776                        "%s|(%s)",
 777                        reg, line);
 778       GNUNET_free (reg);
 779       GNUNET_free (line);
 780       reg = tmp;
 781     }
 782     if (0 == memcmp (&zero, &np[i].network, sizeof (struct in6_addr)))
 783       break;
 784   }
 785   GNUNET_free (np);
 786   return reg;
 787 }
 788
 789
 790 /**
 791  * Hash the service name of a hosted service to the
 792  * hash code that is used to identify the service on
 793  * the network.
 794  *
 795  * @param service_name a string
 796  * @param hc corresponding hash
 797  */
 798 void
 799 GNUNET_TUN_service_name_to_hash (const char *service_name,
 800                                  struct GNUNET_HashCode *hc)
 801 {
 802   GNUNET_CRYPTO_hash (service_name,
 803                       strlen (service_name),
 804                       hc);
 805 }
 806
 807
 808 /* end of regex.c */