tests/test-strstr.c

   1 /*
   2  * Copyright (C) 2004, 2007-2024 Free Software Foundation, Inc.
   3  * Written by Bruno Haible and Eric Blake
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include <string.h>
  21
  22 #include "signature.h"
  23 SIGNATURE_CHECK (strstr, char *, (char const *, char const *));
  24
  25 #include <signal.h>
  26 #include <stdlib.h>
  27 #include <unistd.h>
  28
  29 #include "zerosize-ptr.h"
  30 #include "macros.h"
  31
  32 int
  33 main (int argc, char *argv[])
  34 {
  35 #if HAVE_DECL_ALARM
  36   /* Declare failure if test takes too long, by using default abort
  37      caused by SIGALRM.  All known platforms that lack alarm also have
  38      a quadratic strstr, and the replacement strstr is known to not
  39      take too long.  */
  40   int alarm_value = 50;
  41   signal (SIGALRM, SIG_DFL);
  42   alarm (alarm_value);
  43 #endif
  44
  45   {
  46     const char input[] = "foo";
  47     const char *result = strstr (input, "");
  48     ASSERT (result == input);
  49   }
  50
  51   {
  52     const char input[] = "foo";
  53     const char *result = strstr (input, "o");
  54     ASSERT (result == input + 1);
  55   }
  56
  57   {
  58     /* On some platforms, the memchr() functions reads past the first
  59        occurrence of the byte to be searched, leading to an out-of-bounds
  60        read access for strstr().
  61        See <https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=521737>.
  62        This is a bug in memchr(), see the Austin Group's clarification
  63        <https://www.opengroup.org/austin/docs/austin_454.txt>.  */
  64     const char *fix = "aBaaaaaaaaaaax";
  65     char *page_boundary = (char *) zerosize_ptr ();
  66     size_t len = strlen (fix) + 1;
  67     char *input = page_boundary ? page_boundary - len : malloc (len);
  68     const char *result;
  69
  70     strcpy (input, fix);
  71     result = strstr (input, "B1x");
  72     ASSERT (result == NULL);
  73     if (!page_boundary)
  74       free (input);
  75   }
  76
  77   {
  78     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  79     const char *result = strstr (input, "ABCDABD");
  80     ASSERT (result == input + 15);
  81   }
  82
  83   {
  84     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  85     const char *result = strstr (input, "ABCDABE");
  86     ASSERT (result == NULL);
  87   }
  88
  89   {
  90     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  91     const char *result = strstr (input, "ABCDABCD");
  92     ASSERT (result == input + 11);
  93   }
  94
  95   /* Check that a long periodic needle does not cause false positives.  */
  96   {
  97     const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
  98                          "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
  99                          "_C3_A7_20_EF_BF_BD";
 100     const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 101     const char *result = strstr (input, need);
 102     ASSERT (result == NULL);
 103   }
 104   {
 105     const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 106                          "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 107                          "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
 108                          "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 109     const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 110     const char *result = strstr (input, need);
 111     ASSERT (result == input + 115);
 112   }
 113
 114   /* Check that a very long haystack is handled quickly if the needle is
 115      short and occurs near the beginning.  */
 116   {
 117     size_t repeat = 10000;
 118     size_t m = 1000000;
 119     const char *needle =
 120       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 121       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
 122     char *haystack = (char *) malloc (m + 1);
 123     if (haystack != NULL)
 124       {
 125         memset (haystack, 'A', m);
 126         haystack[0] = 'B';
 127         haystack[m] = '\0';
 128
 129         for (; repeat > 0; repeat--)
 130           {
 131             ASSERT (strstr (haystack, needle) == haystack + 1);
 132           }
 133
 134         free (haystack);
 135       }
 136   }
 137
 138   /* Check that a very long needle is discarded quickly if the haystack is
 139      short.  */
 140   {
 141     size_t repeat = 10000;
 142     size_t m = 1000000;
 143     const char *haystack =
 144       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 145       "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
 146     char *needle = (char *) malloc (m + 1);
 147     if (needle != NULL)
 148       {
 149         memset (needle, 'A', m);
 150         needle[m] = '\0';
 151
 152         for (; repeat > 0; repeat--)
 153           {
 154             ASSERT (strstr (haystack, needle) == NULL);
 155           }
 156
 157         free (needle);
 158       }
 159   }
 160
 161   /* Check that the asymptotic worst-case complexity is not quadratic.  */
 162   {
 163     size_t m = 1000000;
 164     char *haystack = (char *) malloc (2 * m + 2);
 165     char *needle = (char *) malloc (m + 2);
 166     if (haystack != NULL && needle != NULL)
 167       {
 168         const char *result;
 169
 170         memset (haystack, 'A', 2 * m);
 171         haystack[2 * m] = 'B';
 172         haystack[2 * m + 1] = '\0';
 173
 174         memset (needle, 'A', m);
 175         needle[m] = 'B';
 176         needle[m + 1] = '\0';
 177
 178         result = strstr (haystack, needle);
 179         ASSERT (result == haystack + m);
 180       }
 181     free (needle);
 182     free (haystack);
 183   }
 184
 185   /* Sublinear speed is only possible in memmem; strstr must examine
 186      every character of haystack to find its length.  */
 187
 188
 189   {
 190     /* Ensure that with a barely periodic "short" needle, strstr's
 191        search does not mistakenly skip just past the match point.
 192        This use of strstr would mistakenly return NULL before
 193        gnulib v0.0-4927.  */
 194     const char *haystack =
 195       "\n"
 196       "with_build_libsubdir\n"
 197       "with_local_prefix\n"
 198       "with_gxx_include_dir\n"
 199       "with_cpp_install_dir\n"
 200       "enable_generated_files_in_srcdir\n"
 201       "with_gnu_ld\n"
 202       "with_ld\n"
 203       "with_demangler_in_ld\n"
 204       "with_gnu_as\n"
 205       "with_as\n"
 206       "enable_largefile\n"
 207       "enable_werror_always\n"
 208       "enable_checking\n"
 209       "enable_coverage\n"
 210       "enable_gather_detailed_mem_stats\n"
 211       "enable_build_with_cxx\n"
 212       "with_stabs\n"
 213       "enable_multilib\n"
 214       "enable___cxa_atexit\n"
 215       "enable_decimal_float\n"
 216       "enable_fixed_point\n"
 217       "enable_threads\n"
 218       "enable_tls\n"
 219       "enable_objc_gc\n"
 220       "with_dwarf2\n"
 221       "enable_shared\n"
 222       "with_build_sysroot\n"
 223       "with_sysroot\n"
 224       "with_specs\n"
 225       "with_pkgversion\n"
 226       "with_bugurl\n"
 227       "enable_languages\n"
 228       "with_multilib_list\n";
 229     const char *needle = "\n"
 230       "with_gnu_ld\n";
 231     const char* p = strstr (haystack, needle);
 232     ASSERT (p - haystack == 114);
 233   }
 234
 235   {
 236     /* Same bug, shorter trigger.  */
 237     const char *haystack = "..wi.d.";
 238     const char *needle = ".d.";
 239     const char* p = strstr (haystack, needle);
 240     ASSERT (p - haystack == 4);
 241   }
 242
 243   {
 244     /* Like the above, but trigger the flaw in two_way_long_needle
 245        by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
 246        Rather than trying to find the right alignment manually, I've
 247        arbitrarily chosen the following needle and template for the
 248        haystack, and ensure that for each placement of the needle in
 249        that haystack, strstr finds it.  */
 250     const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n";
 251     const char *h =
 252       "\n"
 253       "with_build_libsubdir\n"
 254       "with_local_prefix\n"
 255       "with_gxx_include_dir\n"
 256       "with_cpp_install_dir\n"
 257       "with_e_\n"
 258       "..............................\n"
 259       "with_FGHIJKLMNOPQRSTUVWXYZ\n"
 260       "with_567890123456789\n"
 261       "with_multilib_list\n";
 262     size_t h_len = strlen (h);
 263     char *haystack = malloc (h_len + 1);
 264     size_t i;
 265     ASSERT (haystack);
 266     for (i = 0; i < h_len - strlen (needle); i++)
 267       {
 268         const char *p;
 269         memcpy (haystack, h, h_len + 1);
 270         memcpy (haystack + i, needle, strlen (needle) + 1);
 271         p = strstr (haystack, needle);
 272         ASSERT (p);
 273         ASSERT (p - haystack == i);
 274       }
 275     free (haystack);
 276   }
 277
 278   /* Test case from Yves Bastide.
 279      <https://www.openwall.com/lists/musl/2014/04/18/2>  */
 280   {
 281     const char input[] = "playing play play play always";
 282     const char *result = strstr (input, "play play play");
 283     ASSERT (result == input + 8);
 284   }
 285
 286   /* Test long needles.  */
 287   {
 288     size_t m = 1024;
 289     char *haystack = (char *) malloc (2 * m + 1);
 290     char *needle = (char *) malloc (m + 1);
 291     if (haystack != NULL && needle != NULL)
 292       {
 293         const char *p;
 294         haystack[0] = 'x';
 295         memset (haystack + 1, ' ', m - 1);
 296         memset (haystack + m, 'x', m);
 297         haystack[2 * m] = '\0';
 298         memset (needle, 'x', m);
 299         needle[m] = '\0';
 300         p = strstr (haystack, needle);
 301         ASSERT (p);
 302         ASSERT (p - haystack == m);
 303       }
 304     free (needle);
 305     free (haystack);
 306   }
 307
 308   return test_exit_status;
 309 }