1 /*
2 * Copyright (C) 2004, 2007-2023 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 0;
309 }