Stack overflow due to excessive recursion when using DomainBuilder

再帰的な ArbitraryRegex と ArbitraryRecursive の例を再現し、fuzztest/internal/domains/domain_base.h と fuzztest/internal/runtime.cc にある DomainBuilder::Get/Set および再帰的な初期化パスを調査します。コーパスの初期化中に再帰的なドメインでスタックオーバーフローが発生しなくなり、再帰を制限する、またはその他の方法で処理する動作が適切なテストでカバーされた時点で作業完了です。

I was trying to define a domain of somewhat simple regexes:

// E -> E '|' E | T
// T -> T T | F
// F -> F* | F? | G
// G -> (E) | \\H | [characters]
// H -> \\ | '|' | * | ( | )
auto ArbitraryRegex()
{
    DomainBuilder builder;
    builder.Set<std::string>("E",
                             OneOf(Map([](const std::string& e1, const std::string& e2) { return e1 + '|' + e2; },
                                       builder.Get<std::string>("E"),
                                       builder.Get<std::string>("E")),
                                   builder.Get<std::string>("T")));
    builder.Set<std::string>("T",
                             OneOf(Map([](const std::string& e1, const std::string& e2) { return e1 + e2; },
                                       builder.Get<std::string>("T"),
                                       builder.Get<std::string>("T")),
                                   builder.Get<std::string>("F")));
    builder.Set<std::string>("F",
                             OneOf(Map([](const std::string& f) { return f + '*'; }, builder.Get<std::string>("F")),
                                   Map([](const std::string& f) { return f + '?'; }, builder.Get<std::string>("F")),
                                   builder.Get<std::string>("G")));
    builder.Set<std::string>(
        "G",
        OneOf(Map([](const std::string& e) { return '(' + e + ')'; }, builder.Get<std::string>("E")),
              Map([](const char h) { return std::string{"\\"} + h; }, builder.Get<char>("H")),
              StringOf(AlphaNumericChar()).WithSize(1)));
    builder.Set<char>("H", ElementOf({'\\', '|', '*', '(', ')'}));
    return std::move(builder).Finalize<std::string>("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<fuzztest::internal::AggregateOfImpl<std::tuple<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, (fuzztest::internal::RequireCustomCorpusType)0, fuzztest::Domain<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >, std::tuple<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >::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<testing::Test, void> (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<testing::Test, void> (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<testing::internal::UnitTestImpl, bool> (object=0x616000005780, 
    method=(bool (testing::internal::UnitTestImpl::*)(testing::internal::UnitTestImpl * const)) 0x555555b8c280 <testing::internal::UnitTestImpl::RunAllTests()>, 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<testing::internal::UnitTestImpl, bool> (object=0x616000005780, 
    method=(bool (testing::internal::UnitTestImpl::*)(testing::internal::UnitTestImpl * const)) 0x555555b8c280 <testing::internal::UnitTestImpl::RunAllTests()>, 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 <testing::UnitTest::GetInstance()::instance>)
    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:

auto ArbitraryRecursive()
{
    DomainBuilder builder;
    builder.Set<std::string>("E",
                             OneOf(Map([](const std::string& e1, const std::string& e2) { return e1 + '|' + e2; },
                                       builder.Get<std::string>("E"),
                                       builder.Get<std::string>("E")),
                                   Just(std::string{})));
    return std::move(builder).Finalize<std::string>("E");
}

And the following doesn't run into stack overflows at all:

auto ArbitraryRecursive()
{
    DomainBuilder builder;
    builder.Set<std::string>("E",
                             OneOf(Map([](const std::string& inner) { return inner + '*'; },
                                       builder.Get<std::string>("E")),
                                   Just(std::string{})));
    return std::move(builder).Finalize<std::string>("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 🤔