Stack overflow due to excessive recursion when using DomainBuilder
- Dominant language
- C++
- Stars
- 1.1k
- Forks
- 137
- Avg merge
- 3d 6h
- Merged PRs (30d)
- 22
Description
I was trying to define a domain of somewhat simple regexes:
```cpp
// E -> E '|' E | T
// T -> T T | F
// F -> F* | F? | G
// G -> (E) | \\H | [characters]
// H -> \\ | '|' | * | ( | )
auto ArbitraryRegex()
{
DomainBuilder builder;
builder.Set("E",
OneOf(Map([](const std::string& e1, const std::string& e2) { return e1 + '|' + e2; },
builder.Get("E"),
builder.Get("E")),
builder.Get("T")));
builder.Set("T",
OneOf(Map([](const std::string& e1, const std::string& e2) { return e1 + e2; },
builder.Get("T"),
builder.Get("T")),
builder.Get("F")));
builder.Set("F",
OneOf(Map([](const std::string& f) { return f + '*'; }, builder.Get("F")),
Map([](const std::string& f) { return f + '?'; }, builder.Get("F")),
builder.Get("G")));
builder.Set(
"G",
OneOf(Map([](const std::string& e) { return '(' + e + ')'; }, builder.Get("E")),
Map([](const char h) { return std::string{"\\"} + h; }, builder.Get("H")),
StringOf(AlphaNumericChar()).WithSize(1)));
builder.Set("H", ElementOf({'\\', '|', '*', '(', ')'}));
return std::move(builder).Finalize("E");
}
```
The recursion in this domain blows up even 100MB of stack (`ulimit -s 100000`) almost immediately after starting fuzzing runs. Here's the bottom of the stack trace:
```
...
#355197 0x00005555557ed20e in fuzztest::internal::DomainBase, std::allocator > >, (fuzztest::internal::RequireCustomCorpusType)0, fuzztest::Domain, std::allocator > > >, std::tuple, std::allocator > > >::UntypedInit (
this=0x6020000030f0, ref=...) at external/com_google_fuzztest/./fuzztest/internal/domains/domain_base.h:133
#355198 0x0000555555866022 in fuzztest::internal::FuzzTestFuzzerImpl::InitializeCorpus (this=0x613000000040, prng=...)
at external/com_google_fuzztest/fuzztest/internal/runtime.cc:555
#355199 0x0000555555867290 in fuzztest::internal::FuzzTestFuzzerImpl::RunInFuzzingMode(int*, char***)::$_5::operator()() const (this=0x7fffffffd210)
at external/com_google_fuzztest/fuzztest/internal/runtime.cc:743
#355200 0x0000555555866fe3 in fuzztest::internal::FuzzTestFuzzerImpl::RunInFuzzingMode (this=0x613000000040)
at external/com_google_fuzztest/fuzztest/internal/runtime.cc:709
#355201 0x0000555555856ee9 in fuzztest::internal::GTest_TestAdaptor::TestBody (this=0x604000000c50)
at external/com_google_fuzztest/./fuzztest/googletest_adaptor.h:60
#355202 0x0000555555bb394b in testing::internal::HandleSehExceptionsInMethodIfSupported (object=0x604000000c50,
method=&virtual testing::Test::TestBody(), location=0x555555c0bf20 "the test body") at external/com_google_googletest/googletest/src/gtest.cc:2599
#355203 0x0000555555b96cad in testing::internal::HandleExceptionsInMethodIfSupported (object=0x604000000c50,
method=&virtual testing::Test::TestBody(), location=0x555555c0bf20 "the test body") at external/com_google_googletest/googletest/src/gtest.cc:2635
#355204 0x0000555555b78f63 in testing::Test::Run (this=0x604000000c50) at external/com_google_googletest/googletest/src/gtest.cc:2674
#355205 0x0000555555b79bad in testing::TestInfo::Run (this=0x612000000640) at external/com_google_googletest/googletest/src/gtest.cc:2853
#355206 0x0000555555b7a44a in testing::TestSuite::Run (this=0x6120000007c0) at external/com_google_googletest/googletest/src/gtest.cc:3012
#355207 0x0000555555b8c6ff in testing::internal::UnitTestImpl::RunAllTests (this=0x616000005780)
at external/com_google_googletest/googletest/src/gtest.cc:5870
#355208 0x0000555555bb422b in testing::internal::HandleSehExceptionsInMethodIfSupported (object=0x616000005780,
method=(bool (testing::internal::UnitTestImpl::*)(testing::internal::UnitTestImpl * const)) 0x555555b8c280 , location=0x555555c0c884 "auxiliary test code (environments or event listeners)") at external/com_google_googletest/googletest/src/gtest.cc:2599
#355209 0x0000555555b99633 in testing::internal::HandleExceptionsInMethodIfSupported (object=0x616000005780,
method=(bool (testing::internal::UnitTestImpl::*)(testing::internal::UnitTestImpl * const)) 0x555555b8c280 , location=0x555555c0c884 "auxiliary test code (environments or event listeners)") at external/com_google_googletest/googletest/src/gtest.cc:2635
#355210 0x0000555555b8c218 in testing::UnitTest::Run (this=0x5555566bdcb8 )
at external/com_google_googletest/googletest/src/gtest.cc:5444
#355211 0x0000555555854861 in RUN_ALL_TESTS () at external/com_google_googletest/googletest/include/gtest/gtest.h:2293
#355212 0x0000555555851bae in main (argc=2, argv=0x7fffffffdba8) at external/com_google_fuzztest/fuzztest/fuzztest_gtest_main.cc:76
```
I tried to see if simplifying the domain definition helps, and it does. The following takes a few seconds more to blow up:
```cpp
auto ArbitraryRecursive()
{
DomainBuilder builder;
builder.Set("E",
OneOf(Map([](const std::string& e1, const std::string& e2) { return e1 + '|' + e2; },
builder.Get("E"),
builder.Get("E")),
Just(std::string{})));
return std::move(builder).Finalize("E");
}
```
And the following doesn't run into stack overflows at all:
```cpp
auto ArbitraryRecursive()
{
DomainBuilder builder;
builder.Set("E",
OneOf(Map([](const std::string& inner) { return inner + '*'; },
builder.Get("E")),
Just(std::string{})));
return std::move(builder).Finalize("E");
}
```
I'm thinking about how I could limit the recursion by changing the domain definition (e.g. introduce a "max depth" parameter. But I can't see how, because I can't pass additional parameters to `DomainBuilder::Get`.
If `Get` took additional parameters and `Set` could take a function (instead of the domain) which in turn takes these parameters and returns a domain, then I could consciously limit recursion, I think :thinking:
Contributor guide
Assessment
This issue has not been assessed yet.