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