Out of bounds access with specially crafted regular expression

[alexsharoff]

Running the following program under debug gives an error xstring(1902) : Assertion failed: cannot dereference string iterator because it is out of range (e.g. an end iterator):

#include <boost/regex.hpp>
#include <string>

int main() {
   boost::regex rx("(*ACCEPT)*+\\1((*ACCEPT)*+\\K)");
   std::string str = "Z";
   boost::smatch what;
   boost::regex_search(str, what, rx, boost::match_default|boost::match_partial);
}

Tested on Windows, compiler: Visual Studio 2019.

The above regular expression was found via fuzzing.

[alexsharoff]

If found that after defining BOOST_REGEX_CXX03 boost::regex_search starts throwing an exception:
Invalid back reference: specified capturing group does not exist.

[cmazakas]

@jzmaddock I've made some progress on debugging this issue. It seems like it happens here: https://github.com/boostorg/regex/blob/develop/include/boost/regex/v5/match_results.hpp#L484

set_second() sets .second for the sub-match but the problem is, it doesn't readjust .first so what happens is, in the string "Z\0", we wind up having the submatch start at \0 and the second is at "Z".

I'm not sure what the correct step here is to rectify this issue. It seems like the if((pos == 2) && !escape_k) is the one we want to take but I'm not sure if changing this here is correct or not.

Edit:

Forgot add the callstack here, ha ha. This happens in match_endmark() as a result of skip_until_paren() as a result of match_accept(), which makes sense as our regex is created to use the (*ACCEPT) Perl extension.

Not sure why the named capture and the named backref make it break here, but it seems to find a case when re-adjusting the second itetator where we sort of trip over ourselves, so to speak.

[jzmaddock]

Our messages just crossed - see your email ;)

[jzmaddock]

Also forgot to say: this is a "should never happen" situation which should be asserted, but that's hard for bidirectional iterators as we can't assert i < j for these, or indeed order them generally.