src/pattern.c

   1 /* dnsmasq is Copyright (c) 2000-2022 Simon Kelley
   2
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; version 2 dated June, 1991, or
   6    (at your option) version 3 dated 29 June, 2007.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12
  13    You should have received a copy of the GNU General Public License
  14    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  15 */
  16
  17 #include "dnsmasq.h"
  18
  19 #ifdef HAVE_CONNTRACK
  20
  21 #define LOG(...) \
  22   do { \
  23     my_syslog(LOG_DEBUG, __VA_ARGS__); \
  24   } while (0)
  25
  26 #define ASSERT(condition) \
  27   do { \
  28     if (!(condition)) \
  29       my_syslog(LOG_ERR, _("[pattern.c:%d] Assertion failure: %s"), __LINE__, #condition); \
  30   } while (0)
  31
  32 /**
  33  * Determines whether a given string value matches against a glob pattern
  34  * which may contain zero-or-more-character wildcards denoted by '*'.
  35  *
  36  * Based on "Glob Matching Can Be Simple And Fast Too" by Russ Cox,
  37  * See https://research.swtch.com/glob
  38  *
  39  * @param      value                A string value.
  40  * @param      num_value_bytes      The number of bytes of the string value.
  41  * @param      pattern              A glob pattern.
  42  * @param      num_pattern_bytes    The number of bytes of the glob pattern.
  43  *
  44  * @return 1                        If the provided value matches against the glob pattern.
  45  * @return 0                        Otherwise.
  46  */
  47 static int is_string_matching_glob_pattern(
  48   const char *value,
  49   size_t num_value_bytes,
  50   const char *pattern,
  51   size_t num_pattern_bytes)
  52 {
  53   ASSERT(value);
  54   ASSERT(pattern);
  55
  56   size_t value_index = 0;
  57   size_t next_value_index = 0;
  58   size_t pattern_index = 0;
  59   size_t next_pattern_index = 0;
  60   while (value_index < num_value_bytes || pattern_index < num_pattern_bytes)
  61     {
  62       if (pattern_index < num_pattern_bytes)
  63         {
  64           char pattern_character = pattern[pattern_index];
  65           if ('a' <= pattern_character && pattern_character <= 'z')
  66             pattern_character -= 'a' - 'A';
  67           if (pattern_character == '*')
  68             {
  69               /* zero-or-more-character wildcard */
  70               /* Try to match at value_index, otherwise restart at value_index + 1 next. */
  71               next_pattern_index = pattern_index;
  72               pattern_index++;
  73               if (value_index < num_value_bytes)
  74                 next_value_index = value_index + 1;
  75               else
  76                 next_value_index = 0;
  77               continue;
  78             }
  79           else
  80             {
  81               /* ordinary character */
  82               if (value_index < num_value_bytes)
  83                 {
  84                   char value_character = value[value_index];
  85                   if ('a' <= value_character && value_character <= 'z')
  86                     value_character -= 'a' - 'A';
  87                   if (value_character == pattern_character)
  88                     {
  89                       pattern_index++;
  90                       value_index++;
  91                       continue;
  92                     }
  93                 }
  94             }
  95         }
  96       if (next_value_index)
  97         {
  98           pattern_index = next_pattern_index;
  99           value_index = next_value_index;
 100           continue;
 101         }
 102       return 0;
 103     }
 104   return 1;
 105 }
 106
 107 /**
 108  * Determines whether a given string value represents a valid DNS name.
 109  *
 110  * - DNS names must adhere to RFC 1123: 1 to 253 characters in length, consisting of a sequence of labels
 111  *   delimited by dots ("."). Each label must be 1 to 63 characters in length, contain only
 112  *   ASCII letters ("a"-"Z"), digits ("0"-"9"), or hyphens ("-") and must not start or end with a hyphen.
 113  *
 114  * - A valid name must be fully qualified, i.e., consist of at least two labels.
 115  *   The final label must not be fully numeric, and must not be the "local" pseudo-TLD.
 116  *
 117  * - Examples:
 118  *   Valid: "example.com"
 119  *   Invalid: "ipcamera", "ipcamera.local", "8.8.8.8"
 120  *
 121  * @param      value                A string value.
 122  *
 123  * @return 1                        If the provided string value is a valid DNS name.
 124  * @return 0                        Otherwise.
 125  */
 126 int is_valid_dns_name(const char *value)
 127 {
 128   ASSERT(value);
 129
 130   size_t num_bytes = 0;
 131   size_t num_labels = 0;
 132   const char *c, *label = NULL;
 133   int is_label_numeric = 1;
 134   for (c = value;; c++)
 135     {
 136       if (*c &&
 137           *c != '-' && *c != '.' &&
 138           (*c < '0' || *c > '9') &&
 139           (*c < 'A' || *c > 'Z') &&
 140           (*c < 'a' || *c > 'z'))
 141         {
 142           LOG(_("Invalid DNS name: Invalid character %c."), *c);
 143           return 0;
 144         }
 145       if (*c)
 146         num_bytes++;
 147       if (!label)
 148         {
 149           if (!*c || *c == '.')
 150             {
 151               LOG(_("Invalid DNS name: Empty label."));
 152               return 0;
 153             }
 154           if (*c == '-')
 155             {
 156               LOG(_("Invalid DNS name: Label starts with hyphen."));
 157               return 0;
 158             }
 159           label = c;
 160         }
 161       if (*c && *c != '.')
 162         {
 163           if (*c < '0' || *c > '9')
 164             is_label_numeric = 0;
 165         }
 166       else
 167         {
 168           if (c[-1] == '-')
 169             {
 170               LOG(_("Invalid DNS name: Label ends with hyphen."));
 171               return 0;
 172             }
 173           size_t num_label_bytes = (size_t) (c - label);
 174           if (num_label_bytes > 63)
 175             {
 176               LOG(_("Invalid DNS name: Label is too long (%zu)."), num_label_bytes);
 177               return 0;
 178             }
 179           num_labels++;
 180           if (!*c)
 181             {
 182               if (num_labels < 2)
 183                 {
 184                   LOG(_("Invalid DNS name: Not enough labels (%zu)."), num_labels);
 185                   return 0;
 186                 }
 187               if (is_label_numeric)
 188                 {
 189                   LOG(_("Invalid DNS name: Final label is fully numeric."));
 190                   return 0;
 191                 }
 192               if (num_label_bytes == 5 &&
 193                   (label[0] == 'l' || label[0] == 'L') &&
 194                   (label[1] == 'o' || label[1] == 'O') &&
 195                   (label[2] == 'c' || label[2] == 'C') &&
 196                   (label[3] == 'a' || label[3] == 'A') &&
 197                   (label[4] == 'l' || label[4] == 'L'))
 198                 {
 199                   LOG(_("Invalid DNS name: \"local\" pseudo-TLD."));
 200                   return 0;
 201                 }
 202               if (num_bytes < 1 || num_bytes > 253)
 203                 {
 204                   LOG(_("DNS name has invalid length (%zu)."), num_bytes);
 205                   return 0;
 206                 }
 207               return 1;
 208             }
 209           label = NULL;
 210           is_label_numeric = 1;
 211         }
 212     }
 213 }
 214
 215 /**
 216  * Determines whether a given string value represents a valid DNS name pattern.
 217  *
 218  * - DNS names must adhere to RFC 1123: 1 to 253 characters in length, consisting of a sequence of labels
 219  *   delimited by dots ("."). Each label must be 1 to 63 characters in length, contain only
 220  *   ASCII letters ("a"-"Z"), digits ("0"-"9"), or hyphens ("-") and must not start or end with a hyphen.
 221  *
 222  * - Patterns follow the syntax of DNS names, but additionally allow the wildcard character "*" to be used up to
 223  *   twice per label to match 0 or more characters within that label. Note that the wildcard never matches a dot
 224  *   (e.g., "*.example.com" matches "api.example.com" but not "api.us.example.com").
 225  *
 226  * - A valid name or pattern must be fully qualified, i.e., consist of at least two labels.
 227  *   The final label must not be fully numeric, and must not be the "local" pseudo-TLD.
 228  *   A pattern must end with at least two literal (non-wildcard) labels.
 229  *
 230  * - Examples:
 231  *   Valid: "example.com", "*.example.com", "video*.example.com", "api*.*.example.com", "*-prod-*.example.com"
 232  *   Invalid: "ipcamera", "ipcamera.local", "*", "*.com", "8.8.8.8"
 233  *
 234  * @param      value                A string value.
 235  *
 236  * @return 1                        If the provided string value is a valid DNS name pattern.
 237  * @return 0                        Otherwise.
 238  */
 239 int is_valid_dns_name_pattern(const char *value)
 240 {
 241   ASSERT(value);
 242
 243   size_t num_bytes = 0;
 244   size_t num_labels = 0;
 245   const char *c, *label = NULL;
 246   int is_label_numeric = 1;
 247   size_t num_wildcards = 0;
 248   int previous_label_has_wildcard = 1;
 249   for (c = value;; c++)
 250     {
 251       if (*c &&
 252           *c != '*' && /* Wildcard. */
 253           *c != '-' && *c != '.' &&
 254           (*c < '0' || *c > '9') &&
 255           (*c < 'A' || *c > 'Z') &&
 256           (*c < 'a' || *c > 'z'))
 257         {
 258           LOG(_("Invalid DNS name pattern: Invalid character %c."), *c);
 259           return 0;
 260         }
 261       if (*c && *c != '*')
 262         num_bytes++;
 263       if (!label)
 264         {
 265           if (!*c || *c == '.')
 266             {
 267               LOG(_("Invalid DNS name pattern: Empty label."));
 268               return 0;
 269             }
 270           if (*c == '-')
 271             {
 272               LOG(_("Invalid DNS name pattern: Label starts with hyphen."));
 273               return 0;
 274             }
 275           label = c;
 276         }
 277       if (*c && *c != '.')
 278         {
 279           if (*c < '0' || *c > '9')
 280             is_label_numeric = 0;
 281           if (*c == '*')
 282             {
 283               if (num_wildcards >= 2)
 284                 {
 285                   LOG(_("Invalid DNS name pattern: Wildcard character used more than twice per label."));
 286                   return 0;
 287                 }
 288               num_wildcards++;
 289             }
 290         }
 291       else
 292         {
 293           if (c[-1] == '-')
 294             {
 295               LOG(_("Invalid DNS name pattern: Label ends with hyphen."));
 296               return 0;
 297             }
 298           size_t num_label_bytes = (size_t) (c - label) - num_wildcards;
 299           if (num_label_bytes > 63)
 300             {
 301               LOG(_("Invalid DNS name pattern: Label is too long (%zu)."), num_label_bytes);
 302               return 0;
 303             }
 304           num_labels++;
 305           if (!*c)
 306             {
 307               if (num_labels < 2)
 308                 {
 309                   LOG(_("Invalid DNS name pattern: Not enough labels (%zu)."), num_labels);
 310                   return 0;
 311                 }
 312               if (num_wildcards != 0 || previous_label_has_wildcard)
 313                 {
 314                   LOG(_("Invalid DNS name pattern: Wildcard within final two labels."));
 315                   return 0;
 316                 }
 317               if (is_label_numeric)
 318                 {
 319                   LOG(_("Invalid DNS name pattern: Final label is fully numeric."));
 320                   return 0;
 321                 }
 322               if (num_label_bytes == 5 &&
 323                   (label[0] == 'l' || label[0] == 'L') &&
 324                   (label[1] == 'o' || label[1] == 'O') &&
 325                   (label[2] == 'c' || label[2] == 'C') &&
 326                   (label[3] == 'a' || label[3] == 'A') &&
 327                   (label[4] == 'l' || label[4] == 'L'))
 328                 {
 329                   LOG(_("Invalid DNS name pattern: \"local\" pseudo-TLD."));
 330                   return 0;
 331                 }
 332               if (num_bytes < 1 || num_bytes > 253)
 333                 {
 334                   LOG(_("DNS name pattern has invalid length after removing wildcards (%zu)."), num_bytes);
 335                   return 0;
 336                 }
 337               return 1;
 338             }
 339             label = NULL;
 340             is_label_numeric = 1;
 341             previous_label_has_wildcard = num_wildcards != 0;
 342             num_wildcards = 0;
 343           }
 344     }
 345 }
 346
 347 /**
 348  * Determines whether a given DNS name matches against a DNS name pattern.
 349  *
 350  * @param      name                 A valid DNS name.
 351  * @param      pattern              A valid DNS name pattern.
 352  *
 353  * @return 1                        If the provided DNS name matches against the DNS name pattern.
 354  * @return 0                        Otherwise.
 355  */
 356 int is_dns_name_matching_pattern(const char *name, const char *pattern)
 357 {
 358   ASSERT(name);
 359   ASSERT(is_valid_dns_name(name));
 360   ASSERT(pattern);
 361   ASSERT(is_valid_dns_name_pattern(pattern));
 362
 363   const char *n = name;
 364   const char *p = pattern;
 365
 366   do {
 367     const char *name_label = n;
 368     while (*n && *n != '.')
 369       n++;
 370     const char *pattern_label = p;
 371     while (*p && *p != '.')
 372       p++;
 373     if (!is_string_matching_glob_pattern(
 374         name_label, (size_t) (n - name_label),
 375         pattern_label, (size_t) (p - pattern_label)))
 376       break;
 377     if (*n)
 378       n++;
 379     if (*p)
 380       p++;
 381   } while (*n && *p);
 382
 383   return !*n && !*p;
 384 }
 385
 386 #endif