Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
url_pattern_list.cc
Go to the documentation of this file.
1#include <fuzzer/FuzzedDataProvider.h>
2
3#include <cstdio>
4#include <cstdlib>
5#include <optional>
6#include <string>
7#include <vector>
8
9// The amalgamated ada.cpp carries the route-set compiler
10// (src/url_pattern_list_compiler.h), which is not part of the public
11// headers; the reference below uses its classification to rank routes.
12#include "ada.cpp"
13#include "ada.h"
14
15using regex_provider = ada::url_pattern_regex::std_regex_provider;
16using list_type = ada::url_pattern_list<regex_provider>;
17namespace compiler = ada::url_pattern_list_compiler;
18using groups_type = std::vector<std::optional<std::string>>;
19
20// One route of the independent reference: the compiler's classification
21// (for the priority order only) and the URLPattern object itself, whose
22// pathname component -- ada's own engine, regex_search included -- decides
23// whether the route matches and what its group values are.
25 compiler::route_info info{};
26 ada::url_pattern<regex_provider> pattern{};
27};
28
29// Mirrors the classification url_pattern_list performs and builds the
30// url_pattern oracle. Returns false when a pattern is rejected, in which
31// case parse_url_pattern_list must fail too.
32static bool build_reference(const std::vector<std::string>& patterns,
33 const ada::url_pattern_options& options,
34 std::vector<reference_route>& out) {
35 for (const std::string& pattern : patterns) {
36 auto compile_options = ada::url_pattern_compile_component_options::PATHNAME;
37 auto part_list = ada::url_pattern_helpers::parse_pattern_string(
38 pattern, compile_options,
39 ada::url_pattern_helpers::canonicalize_pathname);
40 if (!part_list) {
41 return false;
42 }
43 reference_route route{};
44 if (compiler::classify_parts(*part_list, route.info.segments,
45 route.info.group_names)) {
46 compiler::finalize_route(route.info);
47 } else {
48 compiler::approximate_kind_sequence(*part_list, route.info);
49 }
50 auto parsed = ada::parse_url_pattern<regex_provider>(
51 ada::url_pattern_init{.pathname = pattern}, nullptr, &options);
52 if (!parsed) {
53 return false;
54 }
55 route.pattern = std::move(*parsed);
56 out.push_back(std::move(route));
57 }
58 return true;
59}
60
61// The reference oracle: every route's URLPattern pathname component is
62// executed on the raw input (fast_match is exactly what url_pattern::exec
63// runs per component: regex_search for regexp components), and the winner
64// is the best match under the documented priority rule. Any disagreement
65// with url_pattern_list::match is a bug in the compiled tables.
66static int32_t reference_match(const std::vector<reference_route>& routes,
67 std::string_view pathname, groups_type& groups) {
68 int32_t best_route = -1;
69 for (size_t i = 0; i < routes.size(); i++) {
70 const reference_route& route = routes[i];
71 if (best_route >= 0 &&
72 !compiler::route_outranks(route.info, i,
73 routes[static_cast<size_t>(best_route)].info,
74 static_cast<size_t>(best_route))) {
75 continue;
76 }
77 auto result = route.pattern.pathname_component.fast_match(pathname);
78 if (result) {
79 groups = std::move(*result);
80 best_route = static_cast<int32_t>(i);
81 }
82 }
83 return best_route;
84}
85
86// Walk every field of a match result so nothing the public API hands out is
87// left unread under the sanitizers.
89 const ada::url_pattern_list_match_result& result) {
90 volatile uint64_t sink = 0;
91 sink += static_cast<uint64_t>(result.route_index);
92 sink += result.capture_count;
93 sink += result.captures_truncated ? 1 : 0;
94 sink += result.regexp_route ? 1 : 0;
95 sink += result.has_match() ? 1 : 0;
96 for (const auto& capture : result.captures) {
97 sink += capture.offset;
98 sink += capture.length;
99 }
100 for (const auto& group : result.regexp_groups) {
101 sink += group.has_value() ? group->size() : 0;
102 }
103 (void)sink;
104}
105
106static void fail(const char* what, const std::string& input,
107 const std::vector<std::string>& patterns) {
108 printf("url_pattern_list %s on input '%s'\n", what, input.c_str());
109 for (const std::string& pattern : patterns) {
110 printf(" pattern: '%s'\n", pattern.c_str());
111 }
112 abort();
113}
114
115static void check_agreement(const list_type& list,
116 const std::vector<reference_route>& reference,
117 const std::vector<std::string>& patterns,
118 const std::string& input) {
119 // The pathname is handed over as a view of an exactly sized heap buffer
120 // (not a null-terminated std::string), so that a read past its end is a
121 // heap-buffer-overflow under ASan rather than a silent read of the
122 // terminator.
123 const std::vector<char> exact(input.begin(), input.end());
124 const auto matched = list.match(std::string_view(exact.data(), exact.size()));
125 exercise_match_result(matched);
126 groups_type expected_groups;
127 const int32_t expected_route =
128 reference_match(reference, input, expected_groups);
129 if (matched.route_index != expected_route) {
130 printf("list=%d ref=%d\n", matched.route_index, expected_route);
131 fail("winner mismatch", input, patterns);
132 }
133 if (expected_route < 0) {
134 return;
135 }
136 const reference_route& winner =
137 reference[static_cast<size_t>(expected_route)];
138 const bool is_regexp =
139 winner.info.mode == ada::url_pattern_list_detail::route_mode::regexp;
140 if (matched.regexp_route != is_regexp) {
141 fail("capture form mismatch", input, patterns);
142 }
143 if (is_regexp) {
144 // Regexp winners: the provider's groups, verbatim.
145 if (matched.regexp_groups != expected_groups) {
146 fail("regexp group mismatch", input, patterns);
147 }
148 return;
149 }
150 // Subset winners: slices of the input equal to the oracle's group values,
151 // truncated at max_captures_per_route.
152 const size_t n_reported =
153 std::min<size_t>(expected_groups.size(),
154 ada::url_pattern_list_limits::max_captures_per_route);
155 if (matched.capture_count != n_reported ||
156 matched.captures_truncated != (expected_groups.size() > n_reported) ||
157 !matched.regexp_groups.empty()) {
158 fail("capture count mismatch", input, patterns);
159 }
160 for (size_t k = 0; k < n_reported; k++) {
161 const auto& capture = matched.captures[k];
162 if (capture.offset + capture.length > input.size() ||
163 !expected_groups[k].has_value() ||
164 input.compare(capture.offset, capture.length, *expected_groups[k]) !=
165 0) {
166 fail("capture slice mismatch", input, patterns);
167 }
168 }
169}
170
171extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size) {
172 FuzzedDataProvider fdp(data, size);
173 auto to_ascii = [](const std::string& source) -> std::string {
174 std::string result;
175 result.reserve(source.size());
176 for (char c : source) {
177 result.push_back(static_cast<unsigned char>(c) % 128);
178 }
179 return result;
180 };
181 // Tokens from a canonical-safe alphabet, so structured patterns compile
182 // often and derived inputs need no canonicalization. Upper-case letters
183 // exercise the ignore_case folding paths.
184 auto token = [&fdp]() -> std::string {
185 static constexpr char alphabet[] =
186 "abcdefghijklmnopqrstuvwxyzABCDEF0123456789-_.~";
187 const size_t length = fdp.ConsumeIntegralInRange<size_t>(1, 12);
188 std::string result;
189 result.reserve(length);
190 for (size_t j = 0; j < length; j++) {
191 result +=
192 alphabet[fdp.ConsumeIntegralInRange<size_t>(0, sizeof(alphabet) - 2)];
193 }
194 return result;
195 };
196
197 // --- strategy (i): construction over 1..64 derived pattern strings -------
198 const size_t n_patterns = fdp.ConsumeIntegralInRange<size_t>(1, 64);
199 std::vector<std::string> patterns;
200 patterns.reserve(n_patterns);
201 for (size_t i = 0; i < n_patterns; i++) {
202 const int mode = fdp.ConsumeIntegralInRange<int>(0, 6);
203 if (mode == 0) {
204 // Raw pattern bytes: URLPattern syntax errors are expected and must
205 // surface as a clean parse error, never as a crash.
206 patterns.push_back("/" + to_ascii(fdp.ConsumeRandomLengthString(40)));
207 } else if (mode == 1 && !patterns.empty()) {
208 // Duplicate an earlier pattern: the smaller index must win.
209 patterns.push_back(
210 patterns[fdp.ConsumeIntegralInRange<size_t>(0, patterns.size() - 1)]);
211 } else {
212 // Structured pattern in (and just beyond) the safe subset.
213 std::string pattern;
214 const size_t depth = fdp.ConsumeIntegralInRange<size_t>(1, 20);
215 int params = 0;
216 for (size_t d = 0; d < depth; d++) {
217 const int kind = fdp.ConsumeIntegralInRange<int>(0, 11);
218 if (kind == 0 && d + 1 == depth) {
219 pattern += "/*";
220 } else if (kind <= 3) {
221 pattern += "/:p" + std::to_string(params++);
222 } else if (kind == 4) {
223 // Witness-hostile literals: identical first/last windows.
224 pattern += "/aaaaaaaa";
225 pattern +=
226 static_cast<char>('A' + fdp.ConsumeIntegralInRange<int>(0, 25));
227 pattern += "aaaaaaaa";
228 } else if (kind == 5 && mode == 6) {
229 // Regexp-mode routes: custom groups, optional and mixed segments.
230 switch (fdp.ConsumeIntegralInRange<int>(0, 3)) {
231 case 0:
232 pattern += "/(\\d+)";
233 break;
234 case 1:
235 pattern += "/:q" + std::to_string(params++) + "?";
236 break;
237 case 2:
238 pattern += "/x-(\\w+)";
239 break;
240 default:
241 pattern += "/pre-:m" + std::to_string(params++);
242 break;
243 }
244 } else {
245 pattern += "/" + token();
246 }
247 }
248 patterns.push_back(std::move(pattern));
249 }
250 }
251 const ada::url_pattern_options options{.ignore_case = fdp.ConsumeBool()};
252 std::vector<std::string_view> views(patterns.begin(), patterns.end());
253 auto list_result =
254 ada::parse_url_pattern_list<regex_provider>(views, nullptr, &options);
255
256 // --- strategy (ii): the independent reference must agree on
257 // constructibility, on every winner, and on every capture ---------------
258 std::vector<reference_route> reference;
259 const bool reference_ok = build_reference(patterns, options, reference);
260 if (list_result.has_value() != reference_ok) {
261 printf("parse/reference disagreement: parse=%d reference=%d\n",
262 list_result.has_value() ? 1 : 0, reference_ok ? 1 : 0);
263 abort();
264 }
265 if (!list_result) {
266 return 0;
267 }
268 const list_type& list = *list_result;
269
270 // Exercise the full public surface.
271 volatile uint64_t sink = list.size();
272 sink += list.ignore_case() ? 1 : 0;
273 bool has_regexp_route = false;
274 for (size_t i = 0; i < list.size(); i++) {
275 sink += list.pattern(i).size();
276 for (const std::string& name : list.group_names(i)) {
277 sink += name.size();
278 }
279 has_regexp_route |= reference[i].info.mode ==
280 ada::url_pattern_list_detail::route_mode::regexp;
281 }
282 (void)sink;
283
284 const size_t n_inputs = fdp.ConsumeIntegralInRange<size_t>(1, 8);
285 for (size_t u = 0; u < n_inputs; u++) {
286 std::string input;
287 const int strategy = fdp.ConsumeIntegralInRange<int>(0, 9);
288 if (strategy >= 8 && !has_regexp_route) {
289 // --- strategy (iii): fast-path-gate crossings. Only exact for the
290 // regex-free subset, where long inputs cannot make std::regex
291 // pathological. ---
292 if (fdp.ConsumeBool()) {
293 // Segment counts crossing the 24-segment gate (23..27).
294 const size_t n_segments = fdp.ConsumeIntegralInRange<size_t>(23, 27);
295 const std::string segment = token();
296 for (size_t s = 0; s < n_segments; s++) {
297 input += "/";
298 input += segment;
299 }
300 } else {
301 // Lengths crossing the 4096-byte gate (4080..4110).
302 const size_t target = fdp.ConsumeIntegralInRange<size_t>(4080, 4110);
303 input = "/" + patterns[fdp.ConsumeIntegralInRange<size_t>(
304 0, patterns.size() - 1)];
305 while (input.size() < target) {
306 input += "/";
307 input += token();
308 }
309 input.resize(target);
310 }
311 } else if (strategy == 7) {
312 // Raw input bytes (match() accepts arbitrary bytes).
313 input = fdp.ConsumeRandomLengthString(64);
314 } else {
315 // Instantiate a derived route (regexp routes: their literal prefix),
316 // then mutate.
317 const reference_route& base =
318 reference[fdp.ConsumeIntegralInRange<size_t>(0,
319 reference.size() - 1)];
320 if (base.info.segments.empty()) {
321 input = "/" + to_ascii(fdp.ConsumeRandomLengthString(40));
322 } else {
323 for (const compiler::route_segment& segment : base.info.segments) {
324 if (segment.kind == compiler::segment_kind::literal) {
325 input += "/" + segment.text;
326 } else if (segment.kind == compiler::segment_kind::param) {
327 input += "/" + token();
328 } else {
329 const size_t tail = fdp.ConsumeIntegralInRange<size_t>(0, 3);
330 for (size_t t = 0; t < tail; t++) {
331 input += "/" + token();
332 }
333 if (tail == 0) {
334 input += "/";
335 }
336 }
337 }
338 }
339 switch (fdp.ConsumeIntegralInRange<int>(0, 6)) {
340 case 0:
341 if (!input.empty()) {
342 input[fdp.ConsumeIntegralInRange<size_t>(0, input.size() - 1)] =
343 static_cast<char>('a' + fdp.ConsumeIntegralInRange<int>(0, 25));
344 }
345 break;
346 case 1:
347 input += '/';
348 break;
349 case 2:
350 input.insert(fdp.ConsumeIntegralInRange<size_t>(0, input.size()),
351 "/");
352 break;
353 case 3:
354 input += "/" + token();
355 break;
356 case 4:
357 if (const size_t slash = input.find_last_of('/');
358 slash != std::string::npos && slash > 0) {
359 input.resize(slash);
360 }
361 break;
362 case 5:
363 // Flip the case of one byte (matters under ignore_case).
364 if (!input.empty()) {
365 char& c =
366 input[fdp.ConsumeIntegralInRange<size_t>(0, input.size() - 1)];
367 c = static_cast<char>(static_cast<unsigned char>(c) ^ 0x20);
368 }
369 break;
370 default:
371 break;
372 }
373 }
374 if (has_regexp_route && input.size() > 64) {
375 // Keep std::regex inputs short, as fuzz/url_pattern.cc does, to avoid
376 // catastrophic backtracking timeouts unrelated to url_pattern_list.
377 input.resize(64);
378 }
379 check_agreement(list, reference, patterns, input);
380 }
381 return 0;
382}
Main header for the Ada URL parser library.
ada::url_pattern< regex_provider > pattern
compiler::route_info info
ada::url_pattern_regex::std_regex_provider regex_provider
Definition url_pattern.cc:9
static int32_t reference_match(const std::vector< reference_route > &routes, std::string_view pathname, groups_type &groups)
std::vector< std::optional< std::string > > groups_type
static void exercise_match_result(const ada::url_pattern_list_match_result &result)
ada::url_pattern_list< regex_provider > list_type
static void check_agreement(const list_type &list, const std::vector< reference_route > &reference, const std::vector< std::string > &patterns, const std::string &input)
int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
static bool build_reference(const std::vector< std::string > &patterns, const ada::url_pattern_options &options, std::vector< reference_route > &out)
static void fail(const char *what, const std::string &input, const std::vector< std::string > &patterns)