[PR] records: bound regex backtracking in record lookup [trafficserver]

["brbzull0 (via GitHub)" <gi...@apache.org>]

brbzull0 opened a new pull request, #13634:
URL: https://github.com/apache/trafficserver/pull/13634

   `RecLookupMatchingRecords()` compiles a caller-supplied pattern and runs it
   against every record and metric name with no complexity bound. It backs the
   `admin_lookup_records` JSONRPC method, which is served inline on the RPC
   server's single thread, so a pattern that backtracks heavily stalls that thread
   for the duration.
   
   Measured on a stock server carrying 1328 names: roughly 19s of CPU per request
   unbounded, against about 123ms with the limit in this change.
   
   ### Change
   
   - `include/tsutil/Regex.h`: add `RE_ERROR_MATCHLIMIT` (-47) to `REErrors`,
     alongside the existing `RE_ERROR_NOMATCH` and `RE_ERROR_NULL`.
   - `src/tsutil/Regex.cc`: add the matching `static_assert` against
     `PCRE2_ERROR_MATCHLIMIT`, following the pattern already used for the other two.
   - `src/records/RecCore.cc`: give all four `regex.exec()` call sites in
     `RecLookupMatchingRecords()` a `RegexMatchContext` with a 50,000 step match
     limit.
   
   Exhausting the limit is not a match verdict, so those names are counted and
   reported once per lookup via `Warning()` rather than silently dropped from the
   caller's results. Any other negative return keeps the existing
   treat-as-no-match behaviour. The pattern itself is deliberately not echoed into
   the log.
   
   On the choice of 50,000: raising the limit costs run time linearly, while the
   longest name a pattern can still resolve grows only as its square root, since
   proving no match costs about L^2/2 steps. 50,000 resolves names up to ~310
   characters, 4.7x the 66 character longest name a stock build registers. The 1750
   used elsewhere in the tree reaches only ~59 characters and cannot resolve what
   ships.
   
   ### Tests
   
   **Unit** -- `src/records/unit_tests/test_RecLookupMatchingRecords.cc`, three
   cases covering config records, metrics (counter and static string) and hidden
   metrics. `test_records` goes from 317 assertions in 44 cases on master to 636 in
   49.
   
   **Autest** -- `tests/gold_tests/traffic_ctl/traffic_ctl_config_match_limit.test.py`
   drives `traffic_ctl config match` with `^([a-z.]+)+[~=]` and asserts three
   things: the command returns promptly with no matches, an ordinary lookup
   afterwards still answers (so the RPC server was not left wedged), and the diags
   log carries the incomplete-results warning rather than silently returning a
   short answer.
   
   Two details in that pattern are load bearing, and are commented in the test. The
   tail must be a character class rather than a literal, because for an absent
   literal PCRE2's required-code-unit check rejects each name up front and no
   backtracking happens -- the test would then pass with or without the change. And
   it must be unsatisfiable rather than merely unlikely: an earlier `[0-9]\z` tail
   matched `proxy.config.ssl.TLSv1`, since lookups are case insensitive. The
   commonly cited `(a+)+$` is useless here, as no real record name holds two
   consecutive `a` characters to backtrack over.
   
   Asserting on the warning rather than on elapsed time keeps the test independent
   of machine speed.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] records: bound regex backtracking in record lookup [trafficserver]

["Copilot (via GitHub)" <gi...@apache.org>]

Copilot commented on code in PR #13634:
URL: https://github.com/apache/trafficserver/pull/13634#discussion_r3932263252


##########
src/records/RecCore.cc:
##########
@@ -582,11 +583,34 @@ RecLookupMatchingRecords(unsigned rec_type, const char *match, void (*callback)(
     return REC_ERR_FAIL;
   }
 
+  // The pattern comes from the admin_lookup_records RPC and is run against every record name,
+  // and that RPC is served inline on a single thread, so an unbounded pattern stalls it: 19s per
+  // request across a stock server's 1328 names, against 123ms at this limit.
+  //
+  // Raising the limit costs run time linearly, while the longest name a pattern can still resolve
+  // grows only as its square root, since proving no match costs about L^2/2 steps. 50,000 resolves
+  // names up to ~310 characters, 4.7x the 66 character longest a stock build registers. The 1750
+  // used elsewhere in the tree reaches only ~59 and cannot resolve what ships.
+  static constexpr uint32_t REC_REGEX_MATCH_LIMIT = 50000;
+
+  RegexMatchContext match_context;
+  match_context.set_match_limit(REC_REGEX_MATCH_LIMIT);
+  RegexMatches matches;
+
+  // Exhausting the limit is the only failure this bound provokes, and it is not a verdict, so count
+  // those names and report once per lookup instead of silently dropping records from the caller's
+  // results. Any other negative return keeps the pre-existing treat-as-no-match behavior.
+  unsigned indeterminate = 0;
+
   if ((rec_type & (RECT_PROCESS | RECT_NODE | RECT_PLUGIN))) {
     // First find the new metrics, this is a bit of a hack, because we still use the old
     // librecords callback with a "pseudo" record.
     for (auto &&[name, type, val] : ts::Metrics::instance()) {
-      if (regex.exec(name.data())) {
+      int const rc = regex.exec(name.data(), matches, 0, &match_context);
+

Review Comment:
   `ts::Metrics::instance()` yields `std::string_view` names; passing `name.data()` forces an extra `strlen()` and loses the known length. Pass `name` directly to `Regex::exec()` to avoid the redundant scan and handle any embedded NULs correctly.
   
   This issue also appears on line 655 of the same file.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] records: bound regex backtracking in record lookup [trafficserver]

["brbzull0 (via GitHub)" <gi...@apache.org>]

brbzull0 closed pull request #13634: records: bound regex backtracking in record lookup
URL: https://github.com/apache/trafficserver/pull/13634


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@trafficserver.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org