1 /*
2  * Copyright (C) 2004, 2007-2020 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
main(int argc,char * argv[])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 long needles.  */
279   {
280     size_t m = 1024;
281     char *haystack = (char *) malloc (2 * m + 1);
282     char *needle = (char *) malloc (m + 1);
283     if (haystack != NULL && needle != NULL)
284       {
285         const char *p;
286         haystack[0] = 'x';
287         memset (haystack + 1, ' ', m - 1);
288         memset (haystack + m, 'x', m);
289         haystack[2 * m] = '\0';
290         memset (needle, 'x', m);
291         needle[m] = '\0';
292         p = strstr (haystack, needle);
293         ASSERT (p);
294         ASSERT (p - haystack == m);
295       }
296     free (needle);
297     free (haystack);
298   }
299 
300   return 0;
301 }
302