[libcxx, regex] Throw exception after too many steps.

[timshen]

Summary

This prevents the backtracking regex engines from "hanging forever"
under certain input.

[timshen]

Detect user defined _LIBCPP_REGEX_COMPLEXITY_FACTOR first.

[timshen]

I defined and exported a macro _LIBCPP_REGEX_COMPLEXITY_FACTOR in the hope that even when the library is shipped to the user, and when the user finds the factor to be inappropriate, they can override it.

I'm not aware of and exported macro policy though, please advice. :)

[mclow.lists]

Applied as revision 313056 (with minor editing)

libcxx/include/regex

 #include <deque>
 
 #include <__undef_min_max>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
+#define _LIBCPP_REGEX_COMPLEXITY_FACTOR 4096
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace regex_constants
 {
 
 // syntax_option_type
 
 enum syntax_option_type
if (__st)
         __states.back().__first_ = __first;
         __states.back().__current_ = __first;
         __states.back().__last_ = __last;
         __states.back().__sub_matches_.resize(mark_count(), __unmatched);
         __states.back().__loop_data_.resize(__loop_count());
         __states.back().__node_ = __st;
         __states.back().__flags_ = __flags;
         __states.back().__at_first_ = __at_first;
+        int __counter = 0;
+        int __length = __last - __first;
         do
         {
+            ++__counter;
+            if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
+                __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
+              __throw_regex_error<regex_constants::error_complexity>();
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
             switch (__s.__do_)
             {
             case __state::__end_state:
                 if ((__flags & regex_constants::match_not_null) &&
                     __s.__current_ == __first)
if (__st)
         __states.back().__first_ = __first;
         __states.back().__current_ = __first;
         __states.back().__last_ = __last;
         __states.back().__loop_data_.resize(__loop_count());
         __states.back().__node_ = __st;
         __states.back().__flags_ = __flags;
         __states.back().__at_first_ = __at_first;
         bool __matched = false;
+        int __counter = 0;
+        int __length = __last - __first;
         do
         {
+            ++__counter;
+            if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
+                __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
+              __throw_regex_error<regex_constants::error_complexity>();
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
             switch (__s.__do_)
             {
             case __state::__end_state:
                 if ((__flags & regex_constants::match_not_null) &&
                     __s.__current_ == __first)
if (__st)
         __states.back().__last_ = __last;
         __states.back().__sub_matches_.resize(mark_count(), __unmatched);
         __states.back().__loop_data_.resize(__loop_count());
         __states.back().__node_ = __st;
         __states.back().__flags_ = __flags;
         __states.back().__at_first_ = __at_first;
         const _CharT* __current = __first;
         bool __matched = false;
+        int __counter = 0;
+        int __length = __last - __first;
         do
         {
+            ++__counter;
+            if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
+                __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
+              __throw_regex_error<regex_constants::error_complexity>();
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
             switch (__s.__do_)
             {
             case __state::__end_state:
                 if ((__flags & regex_constants::match_not_null) &&
                     __s.__current_ == __first)

libcxx/test/std/re/re.alg/re.alg.match/exponential.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// template <class BidirectionalIterator, class Allocator, class charT, class traits>
+//     bool
+//     regex_match(BidirectionalIterator first, BidirectionalIterator last,
+//                  match_results<BidirectionalIterator, Allocator>& m,
+//                  const basic_regex<charT, traits>& e,
+//                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+// Throw exception after spent too many cycles with respect to the length of the input string.
+
+#include <regex>
+#include <cassert>
+
+int main() {
+  for (std::regex_constants::syntax_option_type op :
+       {std::regex::ECMAScript, std::regex::extended, std::regex::egrep,
+        std::regex::awk}) {
+    try {
+      std::regex_match(
+          "aaaaaaaaaaaaaaaaaaaa",
+          std::regex(
+              "a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaa",
+              op));
+      assert(false);
+    } catch (const std::regex_error &e) {
+      assert(e.code() == std::regex_constants::error_complexity);
+    }
+  }
+  std::string s(100000, 'a');
+  for (std::regex_constants::syntax_option_type op :
+       {std::regex::ECMAScript, std::regex::extended, std::regex::egrep,
+        std::regex::awk}) {
+    assert(std::regex_match(s, std::regex("a*", op)));
+  }
+  return 0;
+}

libcxx/test/std/re/re.alg/re.alg.search/exponential.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// template <class BidirectionalIterator, class Allocator, class charT, class traits>
+//     bool
+//     regex_match(BidirectionalIterator first, BidirectionalIterator last,
+//                  match_results<BidirectionalIterator, Allocator>& m,
+//                  const basic_regex<charT, traits>& e,
+//                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+// Throw exception after spent too many cycles with respect to the length of the input string.
+
+#include <regex>
+#include <cassert>
+
+int main() {
+  for (std::regex_constants::syntax_option_type op :
+       {std::regex::ECMAScript, std::regex::extended, std::regex::egrep,
+        std::regex::awk}) {
+    try {
+      std::regex_search(
+          "aaaaaaaaaaaaaaaaaaaa",
+          std::regex(
+              "a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaa",
+              op));
+      assert(false);
+    } catch (const std::regex_error &e) {
+      assert(e.code() == std::regex_constants::error_complexity);
+    }
+  }
+  std::string s(100000, 'a');
+  for (std::regex_constants::syntax_option_type op :
+       {std::regex::ECMAScript, std::regex::extended, std::regex::egrep,
+        std::regex::awk}) {
+    assert(std::regex_search(s, std::regex("a*", op)));
+  }
+  return 0;
+}