Fix the corpus value validation for `InRegexp`. The function `RegexpDFA::DFAPathToString()` that is used in the corpus value validation wasn't checking that the DFA path is consistent with the DFA, i.e., that the states along the path are really the ones appearing in the DFA if we follow the path. It also wasn't checking that the path reaches the end state. I also cleaned up the code a bit and added a few general improvements. PiperOrigin-RevId: 756386731
diff --git a/domain_tests/BUILD b/domain_tests/BUILD index 436a2c9..d71a93b 100644 --- a/domain_tests/BUILD +++ b/domain_tests/BUILD
@@ -154,10 +154,7 @@ ":domain_testing", "@abseil-cpp//absl/container:flat_hash_set", "@abseil-cpp//absl/random", - "@abseil-cpp//absl/types:span", "@com_google_fuzztest//fuzztest:domain", - "@com_google_fuzztest//fuzztest:logging", - "@com_google_fuzztest//fuzztest:type_support", "@googletest//:gtest_main", "@re2", ],
diff --git a/domain_tests/CMakeLists.txt b/domain_tests/CMakeLists.txt index a99142a..703ee49 100644 --- a/domain_tests/CMakeLists.txt +++ b/domain_tests/CMakeLists.txt
@@ -134,10 +134,7 @@ fuzztest::domain_testing absl::flat_hash_set absl::random_random - absl::span fuzztest::domain - fuzztest::logging - fuzztest::type_support GTest::gmock_main re2::re2 )
diff --git a/domain_tests/in_regexp_domain_test.cc b/domain_tests/in_regexp_domain_test.cc index c7fe54d..3491d2a 100644 --- a/domain_tests/in_regexp_domain_test.cc +++ b/domain_tests/in_regexp_domain_test.cc
@@ -23,11 +23,8 @@ #include "gtest/gtest.h" #include "absl/container/flat_hash_set.h" #include "absl/random/random.h" -#include "absl/types/span.h" #include "./fuzztest/domain.h" #include "./domain_tests/domain_testing.h" -#include "./fuzztest/internal/logging.h" -#include "./fuzztest/internal/type_support.h" #include "re2/re2.h" namespace fuzztest { @@ -191,6 +188,45 @@ "Invalid DFA path.")); } +// Additional validation test with values from a real bug (b/339306132). +TEST(InRegexp, ValidationRejectsInvalidValueRegression) { + auto domain_a = + InRegexp(R"re(^(sheet|empty_sheet|email_message|email_thread)$)re"); + auto domain_b = InRegexp( + R"re(^(sheet|empty_sheet|email_message|email_thread|chat_message|chat_context)$)re"); + + auto sheet_a = domain_a.FromValue("sheet"); + auto empty_sheet_a = domain_a.FromValue("empty_sheet"); + auto email_message_a = domain_a.FromValue("email_message"); + auto email_thread_a = domain_a.FromValue("email_thread"); + + ASSERT_TRUE(sheet_a.has_value()); + ASSERT_TRUE(empty_sheet_a.has_value()); + ASSERT_TRUE(email_message_a.has_value()); + ASSERT_TRUE(email_thread_a.has_value()); + + EXPECT_OK(domain_a.ValidateCorpusValue(*sheet_a)); + EXPECT_OK(domain_a.ValidateCorpusValue(*empty_sheet_a)); + EXPECT_OK(domain_a.ValidateCorpusValue(*email_message_a)); + EXPECT_OK(domain_a.ValidateCorpusValue(*email_thread_a)); + + // Even though `domain_b` subsumes `domain_a` in terms of user values, under + // the hood the DFAs are structurally different, so the corpus values (DFA + // paths) from one domain may not be valid for the other domain. + EXPECT_TRUE(!domain_b.ValidateCorpusValue(*sheet_a).ok() || + domain_b.GetValue(*sheet_a) == "sheet") + << "GetValue() returns \"" << domain_b.GetValue(*sheet_a) << "\""; + EXPECT_TRUE(!domain_b.ValidateCorpusValue(*empty_sheet_a).ok() || + domain_b.GetValue(*empty_sheet_a) == "empty_sheet") + << "GetValue() returns \"" << domain_b.GetValue(*empty_sheet_a) << "\""; + EXPECT_TRUE(!domain_b.ValidateCorpusValue(*email_message_a).ok() || + domain_b.GetValue(*email_message_a) == "email_message") + << "GetValue() returns \"" << domain_b.GetValue(*email_message_a) << "\""; + EXPECT_TRUE(!domain_b.ValidateCorpusValue(*email_thread_a).ok() || + domain_b.GetValue(*email_thread_a) == "email_thread") + << "GetValue() returns \"" << domain_b.GetValue(*email_thread_a) << "\""; +} + struct InRegexString { std::string regexp; std::string string_in_domain;
diff --git a/fuzztest/internal/domains/in_grammar_impl.h b/fuzztest/internal/domains/in_grammar_impl.h index 216c680..ac34361 100644 --- a/fuzztest/internal/domains/in_grammar_impl.h +++ b/fuzztest/internal/domains/in_grammar_impl.h
@@ -33,6 +33,7 @@ #include "./fuzztest/internal/domains/container_of_impl.h" #include "./fuzztest/internal/domains/domain_base.h" #include "./fuzztest/internal/domains/in_regexp_impl.h" +#include "./fuzztest/internal/domains/regexp_dfa.h" #include "./fuzztest/internal/logging.h" #include "./fuzztest/internal/meta.h" #include "./fuzztest/internal/serialization.h" @@ -51,7 +52,7 @@ struct ASTNode { ASTTypeId type_id; std::variant<std::monostate, // If the node is a string terminal. - DFAPath, // If the node is a regex terminal. + RegexpDFA::Path, // If the node is a regex terminal. std::vector<ASTNode>> // If the node is a non-terminal. children; @@ -158,32 +159,33 @@ static void Mutate(ASTNode& val, absl::BitGenRef prng, const domain_implementor::MutationMetadata& metadata, bool only_shrink) { - GetInnerRegexpDomain().Mutate(std::get<DFAPath>(val.children), prng, + GetInnerRegexpDomain().Mutate(std::get<RegexpDFA::Path>(val.children), prng, metadata, only_shrink); } static ASTTypeId TypeId() { return id; } static void ToString(std::string& output, const ASTNode& val) { - FUZZTEST_INTERNAL_CHECK(CheckASTNodeTypeIdAndChildType<DFAPath>(val, id), - "Not a regex literal!"); + FUZZTEST_INTERNAL_CHECK( + CheckASTNodeTypeIdAndChildType<RegexpDFA::Path>(val, id), + "Not a regex literal!"); absl::StrAppend(&output, GetInnerRegexpDomain().GetValue( - std::get<DFAPath>(val.children))); + std::get<RegexpDFA::Path>(val.children))); } static bool IsMutable(const ASTNode& /*val*/) { return true; } static IRObject SerializeCorpus(const ASTNode& astnode) { FUZZTEST_INTERNAL_CHECK( - CheckASTNodeTypeIdAndChildType<DFAPath>(astnode, id), + CheckASTNodeTypeIdAndChildType<RegexpDFA::Path>(astnode, id), "Not a regex literal!"); - return WrapASTIntoIRObject(astnode, - GetInnerRegexpDomain().SerializeCorpus( - std::get<DFAPath>(astnode.children))); + return WrapASTIntoIRObject( + astnode, GetInnerRegexpDomain().SerializeCorpus( + std::get<RegexpDFA::Path>(astnode.children))); } static std::optional<ASTNode> ParseCorpus(const IRObject& obj) { - if (!CheckASTCorpusStructure<DFAPath>(obj)) { + if (!CheckASTCorpusStructure<RegexpDFA::Path>(obj)) { return std::nullopt; } auto subs = obj.Subs(); @@ -195,12 +197,12 @@ if (!path) { return std::nullopt; } - result.children.emplace<DFAPath>(*path); + result.children.emplace<RegexpDFA::Path>(*path); return result; } static absl::Status ValidateCorpusValue(const ASTNode& astnode) { - if (!CheckASTNodeTypeIdAndChildType<DFAPath>(astnode, id)) { + if (!CheckASTNodeTypeIdAndChildType<RegexpDFA::Path>(astnode, id)) { return absl::InvalidArgumentError("Not a regex literal!"); } return absl::OkStatus();
diff --git a/fuzztest/internal/domains/in_regexp_impl.cc b/fuzztest/internal/domains/in_regexp_impl.cc index 03210ce..81d8141 100644 --- a/fuzztest/internal/domains/in_regexp_impl.cc +++ b/fuzztest/internal/domains/in_regexp_impl.cc
@@ -40,16 +40,16 @@ InRegexpImpl::InRegexpImpl(std::string_view regex_str) : regex_str_(regex_str), dfa_(RegexpDFA::Create(regex_str_)) {} -DFAPath InRegexpImpl::Init(absl::BitGenRef prng) { +RegexpDFA::Path InRegexpImpl::Init(absl::BitGenRef prng) { if (auto seed = MaybeGetRandomSeed(prng)) return *seed; - absl::StatusOr<DFAPath> path = - dfa_.StringToDFAPath(dfa_.GenerateString(prng)); + absl::StatusOr<RegexpDFA::Path> path = + dfa_.StringToPath(dfa_.GenerateString(prng)); FUZZTEST_INTERNAL_CHECK_PRECONDITION(path.ok(), "Init should generate valid paths"); return *path; } -void InRegexpImpl::Mutate(DFAPath& path, absl::BitGenRef prng, +void InRegexpImpl::Mutate(RegexpDFA::Path& path, absl::BitGenRef prng, const domain_implementor::MutationMetadata&, bool only_shrink) { if (only_shrink) { @@ -73,12 +73,12 @@ if (sink_states_first_appearance[state_id].has_value()) continue; sink_states_first_appearance[state_id] = i; } - std::vector<RegexpDFA::Edge> new_subpath = dfa_.FindPath( - prng, path[rand_offset].from_state_id, sink_states_first_appearance); + RegexpDFA::Path new_subpath = dfa_.FindPath( + path[rand_offset].from_state_id, sink_states_first_appearance, prng); int to_state_id = new_subpath.back().from_state_id; new_subpath.pop_back(); - DFAPath new_path; + RegexpDFA::Path new_path; for (size_t i = 0; i < rand_offset; ++i) { new_path.push_back(path[i]); } @@ -101,14 +101,14 @@ StringPrinter InRegexpImpl::GetPrinter() const { return StringPrinter{}; } InRegexpImpl::value_type InRegexpImpl::GetValue(const corpus_type& v) const { - absl::StatusOr<std::string> val = dfa_.DFAPathToString(v); + absl::StatusOr<std::string> val = dfa_.PathToString(v); FUZZTEST_INTERNAL_CHECK(val.ok(), "Corpus is invalid!"); return *val; } std::optional<InRegexpImpl::corpus_type> InRegexpImpl::FromValue( const value_type& v) const { - absl::StatusOr<corpus_type> path = dfa_.StringToDFAPath(v); + absl::StatusOr<corpus_type> path = dfa_.StringToPath(v); if (!path.ok()) return std::nullopt; return *path; } @@ -142,20 +142,21 @@ absl::Status InRegexpImpl::ValidateCorpusValue( const corpus_type& corpus_value) const { // Check whether this is a valid path in the DFA. - absl::StatusOr<std::string> str = dfa_.DFAPathToString(corpus_value); + absl::StatusOr<std::string> str = dfa_.PathToString(corpus_value); if (str.ok()) return absl::OkStatus(); return Prefix(str.status(), absl::StrCat("Invalid value for InRegexp(\"", regex_str_, "\")")); } -void InRegexpImpl::ValidatePathRoundtrip(const DFAPath& path) const { - absl::StatusOr<std::string> str = dfa_.DFAPathToString(path); +void InRegexpImpl::ValidatePathRoundtrip(const RegexpDFA::Path& path) const { + absl::StatusOr<std::string> str = dfa_.PathToString(path); FUZZTEST_INTERNAL_CHECK(str.ok(), "Invalid path in the DFA!"); - absl::StatusOr<DFAPath> new_path = dfa_.StringToDFAPath(*str); + absl::StatusOr<RegexpDFA::Path> new_path = dfa_.StringToPath(*str); FUZZTEST_INTERNAL_CHECK(new_path.ok(), "Invalid path in the DFA!"); } -bool InRegexpImpl::ShrinkByRemoveLoop(absl::BitGenRef prng, DFAPath& path) { +bool InRegexpImpl::ShrinkByRemoveLoop(absl::BitGenRef prng, + RegexpDFA::Path& path) { std::vector<std::vector<int>> state_appearances(dfa_.state_count()); for (int i = 0; i < path.size(); ++i) { state_appearances[path[i].from_state_id].push_back(i); @@ -180,7 +181,7 @@ } bool InRegexpImpl::ShrinkByFindShorterSubPath(absl::BitGenRef prng, - DFAPath& path) { + RegexpDFA::Path& path) { if (path.size() <= 1) { return false; } @@ -214,12 +215,12 @@ if (length == 1) continue; - std::vector<RegexpDFA::Edge> new_subpath = - dfa_.FindPathWithinLengthDFS(prng, from_state_id, to_state_id, length); + RegexpDFA::Path new_subpath = + dfa_.FindPathWithinLengthDFS(from_state_id, to_state_id, length, prng); // If the size is unchanged, keep trying. if (new_subpath.size() == length) continue; - DFAPath new_path(path.begin(), path.begin() + from_index); + RegexpDFA::Path new_path(path.begin(), path.begin() + from_index); new_path.insert(new_path.end(), new_subpath.begin(), new_subpath.end()); for (size_t idx = to_index; idx < path.size(); ++idx) { new_path.push_back(path[idx]);
diff --git a/fuzztest/internal/domains/in_regexp_impl.h b/fuzztest/internal/domains/in_regexp_impl.h index c607539..12f00be 100644 --- a/fuzztest/internal/domains/in_regexp_impl.h +++ b/fuzztest/internal/domains/in_regexp_impl.h
@@ -18,7 +18,6 @@ #include <optional> #include <string> #include <string_view> -#include <vector> #include "absl/random/bit_gen_ref.h" #include "absl/status/status.h" @@ -29,20 +28,18 @@ namespace fuzztest::internal { -using DFAPath = std::vector<RegexpDFA::Edge>; - class InRegexpImpl : public domain_implementor::DomainBase<InRegexpImpl, std::string, - DFAPath> { + RegexpDFA::Path> { public: explicit InRegexpImpl(std::string_view regex_str); - DFAPath Init(absl::BitGenRef prng); + RegexpDFA::Path Init(absl::BitGenRef prng); // Strategy: Parse the input string into a path in the DFA. Pick a node in the // path and random walk from the node until we reach an end state or go back // to the original path. - void Mutate(DFAPath& path, absl::BitGenRef prng, + void Mutate(RegexpDFA::Path& path, absl::BitGenRef prng, const domain_implementor::MutationMetadata&, bool only_shrink); StringPrinter GetPrinter() const; @@ -58,17 +55,17 @@ absl::Status ValidateCorpusValue(const corpus_type& corpus_value) const; private: - void ValidatePathRoundtrip(const DFAPath& path) const; + void ValidatePathRoundtrip(const RegexpDFA::Path& path) const; // Remove a random loop in the DFA path and return the string from the // modified path. A loop is a subpath that starts and ends with the same // state. - bool ShrinkByRemoveLoop(absl::BitGenRef prng, DFAPath& path); + bool ShrinkByRemoveLoop(absl::BitGenRef prng, RegexpDFA::Path& path); // Randomly pick a subpath and try to replace it with a shorter one. As this // might fail we keep trying until success or the maximum number of trials is // reached. - bool ShrinkByFindShorterSubPath(absl::BitGenRef prng, DFAPath& path); + bool ShrinkByFindShorterSubPath(absl::BitGenRef prng, RegexpDFA::Path& path); std::string regex_str_; RegexpDFA dfa_;
diff --git a/fuzztest/internal/domains/regexp_dfa.cc b/fuzztest/internal/domains/regexp_dfa.cc index 67d7e5b..ff6fa70 100644 --- a/fuzztest/internal/domains/regexp_dfa.cc +++ b/fuzztest/internal/domains/regexp_dfa.cc
@@ -49,18 +49,17 @@ std::string RegexpDFA::GenerateString(absl::BitGenRef prng) { std::string result; - State* state = &states_[0]; - while (true) { - FUZZTEST_INTERNAL_CHECK(!state->next.empty(), "Empty next state!"); - + State* state = &states_.front(); + while (!state->is_end_state()) { // Pick a random next state by weight. int rand_index = state->edge_weight_distribution(prng); - auto& [next_string, next_id] = state->next[rand_index]; + const auto& [fragment, next_id] = state->next[rand_index]; + result.insert(result.end(), fragment.begin(), fragment.end()); state = &states_[next_id]; - result.insert(result.end(), next_string.begin(), next_string.end()); - if (next_string.back() == kEndOfString) { - FUZZTEST_INTERNAL_CHECK(state->is_end_state(), - "EOS should lead to end state!"); + if (state->is_end_state()) { + FUZZTEST_INTERNAL_CHECK( + fragment.back() == kEndOfString, + "The last character leading to the end state should be EOS!"); result.pop_back(); break; } @@ -68,33 +67,33 @@ return result; } -std::vector<RegexpDFA::Edge> RegexpDFA::FindPath( - absl::BitGenRef prng, int from_state_id, - const std::vector<std::optional<int>>& to_state_ids) { - std::vector<Edge> path; +RegexpDFA::Path RegexpDFA::FindPath( + int from_state_id, const std::vector<std::optional<int>>& to_state_ids, + absl::BitGenRef prng) { + Path path; int cur_state_id = from_state_id; State* cur_state = &states_[cur_state_id]; + FUZZTEST_INTERNAL_CHECK(!cur_state->is_end_state(), + "Cannot start a DFA path from an end state!"); while (true) { - FUZZTEST_INTERNAL_CHECK(!cur_state->next.empty(), "Empty next state!"); - // Pick a random next state. int offset = cur_state->edge_weight_distribution(prng); - auto& [next_char, next_state_id] = cur_state->next[offset]; path.push_back({cur_state_id, offset}); - + const auto& [unused_next_fragment, next_state_id] = cur_state->next[offset]; cur_state_id = next_state_id; cur_state = &states_[cur_state_id]; // Reached an end state or found a state in the original path? - if (cur_state->is_end_state() || to_state_ids[next_state_id].has_value()) { - path.push_back({next_state_id, -1}); + if (cur_state->is_end_state() || to_state_ids[cur_state_id].has_value()) { + path.push_back({cur_state_id, -1}); break; } } return path; } -std::vector<RegexpDFA::Edge> RegexpDFA::FindPathWithinLengthDFS( - absl::BitGenRef prng, int from_state_id, int to_state_id, int length) { +RegexpDFA::Path RegexpDFA::FindPathWithinLengthDFS(int from_state_id, + int to_state_id, int length, + absl::BitGenRef prng) { // Each state maintains an edge and a counter for each possible length. The // edge is the last edge in the path from `from_state` to the state and can // be used to reconstruct the path. And the counter is the number of paths @@ -108,8 +107,12 @@ // Randomness for DFS. Instead of always starting to explore from edge index // 0, we start with a different random offset for each state. - std::vector<int> rand_edge_offsets(states_.size(), 0); - for (int& i : rand_edge_offsets) i = absl::Uniform<int>(prng, 0u, 256); + std::vector<int> rand_edge_offsets; + rand_edge_offsets.reserve(states_.size()); + for (const State& state : states_) { + rand_edge_offsets.push_back( + absl::Uniform<int>(prng, 0u, state.next.size())); + } std::vector<Edge> stack{Edge{from_state_id, 0}}; do { @@ -146,12 +149,12 @@ FUZZTEST_INTERNAL_CHECK(!candidate_lens.empty(), "Cannot find a path!"); int state_id = to_state_id; - std::vector<Edge> result; + Path result; for (int len = candidate_lens[absl::Uniform<int>(prng, 0, candidate_lens.size())]; len > 0; --len) { result.push_back(*(last_edges_and_counters[state_id][len].edge)); - state_id = last_edges_and_counters[state_id][len].edge->from_state_id; + state_id = result.back().from_state_id; } FUZZTEST_INTERNAL_CHECK(state_id == from_state_id, "Cannot find a path from from_state"); @@ -159,9 +162,9 @@ return result; } -absl::StatusOr<std::vector<RegexpDFA::Edge>> RegexpDFA::StringToDFAPath( +absl::StatusOr<RegexpDFA::Path> RegexpDFA::StringToPath( absl::string_view s) const { - std::vector<RegexpDFA::Edge> path; + RegexpDFA::Path path; int state_id = 0; std::vector<std::int16_t> characters; characters.reserve(s.size()); @@ -190,29 +193,31 @@ return path; } -absl::StatusOr<std::string> RegexpDFA::DFAPathToString( - const std::vector<RegexpDFA::Edge>& path, size_t start_offset, - std::optional<size_t> end_offset) const { - if (!end_offset.has_value()) end_offset = path.size(); - +absl::StatusOr<std::string> RegexpDFA::PathToString( + const RegexpDFA::Path& path) const { std::string result; - for (size_t i = start_offset; i < *end_offset; ++i) { - auto& [from_state_id, edge_index] = path[i]; + std::optional<int> next_state_id; + for (const auto& [from_state_id, edge_index] : path) { if (from_state_id >= states_.size() || - edge_index >= states_[from_state_id].next.size()) { + edge_index >= states_[from_state_id].next.size() || + (next_state_id.has_value() && next_state_id != from_state_id)) { return absl::InvalidArgumentError("Invalid DFA path."); } - const std::vector<std::int16_t>& chars_to_match = - states_[from_state_id].next[edge_index].chars_to_match; - result.insert(result.end(), chars_to_match.begin(), chars_to_match.end()); - if (chars_to_match.back() == kEndOfString) { - if (i != *end_offset - 1) { - return absl::InvalidArgumentError("End state should be the last."); - } + const State::StateTransition& transition = + states_[from_state_id].next[edge_index]; + next_state_id = transition.next_state_id; + const std::vector<std::int16_t>& fragment = transition.chars_to_match; + result.insert(result.end(), fragment.begin(), fragment.end()); + if (next_state_id == end_state_id_) { + FUZZTEST_INTERNAL_CHECK( + fragment.back() == kEndOfString, + "The last character leading to the end state should be EOS!"); result.pop_back(); - break; } } + if (next_state_id != end_state_id_) { + return absl::InternalError("DFA path doesn't end in the end state."); + } return result; } @@ -283,11 +288,8 @@ "i.e., any character) in your regular expression, or wait until " "the issue is fixed."); - auto& transition_vec = - transition_table.emplace_back(compiled_regexp->bytemap_range() + 1); - for (int b = 0; b < compiled_regexp->bytemap_range() + 1; ++b) { - transition_vec[b] = next[b]; - } + transition_table.emplace_back( + next, next + compiled_regexp->bytemap_range() + 1); end_vec.push_back(match); }); @@ -299,7 +301,7 @@ std::vector<int>& transition_vec = transition_table[i]; State& state = states_[i]; - for (int j = 0; j < transition_vec.size() - 1; ++j) { + for (int j = 0; j + 1 < transition_vec.size(); ++j) { // If `transition_vec[bytemap_idx] == state_id` at state `s`, it means // that given a character `c` whose bytemap index is `bytemap_idx`, // `s` will transition into state with id `state_id`. The bytemap index @@ -347,47 +349,44 @@ std::queue<int> q; q.push(end_state_id_); do { - size_t n = q.size(); - for (int i = 0; i < n; ++i) { - int state_id = q.front(); - q.pop(); - if (is_safe_node[state_id]) continue; - for (int j = 0; j < states_.size(); ++j) { - if (is_predecessor[state_id][j]) q.push(j); - } - State& state = states_[state_id]; - std::vector<int> edge_to_safe_nodes; - std::vector<int> edge_to_unsafe_nodes; - for (int j = 0; j < state.next.size(); ++j) { - if (is_safe_node[state.next[j].next_state_id]) - edge_to_safe_nodes.push_back(j); - else - edge_to_unsafe_nodes.push_back(j); - } - FUZZTEST_INTERNAL_CHECK( - state_id == end_state_id_ || !edge_to_safe_nodes.empty(), - "A non-end node must have at least one safe edge"); - double probability_to_safe_node = - edge_to_unsafe_nodes.empty() ? 1 : kProbToSafeNode; - - // Distribute `probability_to_safe_node` evenly to every edge that leads - // to a safe node. Also distribute 1-`probability_to_safe_node` to the - // unsafe edges. - std::vector<double> edge_weights(state.next.size()); - for (int edge_index : edge_to_safe_nodes) { - edge_weights[edge_index] = - probability_to_safe_node / - static_cast<double>(edge_to_safe_nodes.size()); - } - for (int edge_index : edge_to_unsafe_nodes) { - edge_weights[edge_index] = - (1.0 - probability_to_safe_node) / - static_cast<double>(edge_to_unsafe_nodes.size()); - } - is_safe_node[state_id] = true; - state.edge_weight_distribution = absl::discrete_distribution<int>( - edge_weights.begin(), edge_weights.end()); + int state_id = q.front(); + q.pop(); + if (is_safe_node[state_id]) continue; + for (int j = 0; j < states_.size(); ++j) { + if (is_predecessor[state_id][j]) q.push(j); } + State& state = states_[state_id]; + std::vector<int> edge_to_safe_nodes; + std::vector<int> edge_to_unsafe_nodes; + for (int j = 0; j < state.next.size(); ++j) { + if (is_safe_node[state.next[j].next_state_id]) { + edge_to_safe_nodes.push_back(j); + } else { + edge_to_unsafe_nodes.push_back(j); + } + } + FUZZTEST_INTERNAL_CHECK( + state_id == end_state_id_ || !edge_to_safe_nodes.empty(), + "A non-end node must have at least one safe edge"); + double probability_to_safe_node = + edge_to_unsafe_nodes.empty() ? 1 : kProbToSafeNode; + + // Distribute `probability_to_safe_node` evenly to every edge that leads + // to a safe node. Also distribute 1-`probability_to_safe_node` to the + // unsafe edges. + std::vector<double> edge_weights(state.next.size()); + for (int edge_index : edge_to_safe_nodes) { + edge_weights[edge_index] = probability_to_safe_node / + static_cast<double>(edge_to_safe_nodes.size()); + } + for (int edge_index : edge_to_unsafe_nodes) { + edge_weights[edge_index] = + (1.0 - probability_to_safe_node) / + static_cast<double>(edge_to_unsafe_nodes.size()); + } + is_safe_node[state_id] = true; + state.edge_weight_distribution = absl::discrete_distribution<int>( + edge_weights.begin(), edge_weights.end()); } while (!q.empty()); }
diff --git a/fuzztest/internal/domains/regexp_dfa.h b/fuzztest/internal/domains/regexp_dfa.h index 7a0c86a..506f02f 100644 --- a/fuzztest/internal/domains/regexp_dfa.h +++ b/fuzztest/internal/domains/regexp_dfa.h
@@ -55,30 +55,29 @@ int edge_index; }; + using Path = std::vector<Edge>; + static RegexpDFA Create(absl::string_view regexp); std::string GenerateString(absl::BitGenRef prng); // Randomly walk from the state of `from_state_id` to any state of // `to_state_ids` or an end state. - std::vector<Edge> FindPath( - absl::BitGenRef prng, int from_state_id, - const std::vector<std::optional<int>>& to_state_ids); + Path FindPath(int from_state_id, + const std::vector<std::optional<int>>& to_state_ids, + absl::BitGenRef prng); // Randomly DFS from the state of `from_state_id` to the state of // `to_state_id`, trying to find a path of length less than, if no, equal to // `length`. If we have multiple such paths, randomly pick one of them. Since // this (nearly) fully explores all the paths, there is no big difference in // the efficiency. And we prefer DFS to BFS for better readability. - std::vector<Edge> FindPathWithinLengthDFS(absl::BitGenRef prng, - int from_state_id, int to_state_id, - int length); + Path FindPathWithinLengthDFS(int from_state_id, int to_state_id, int length, + absl::BitGenRef prng); - absl::StatusOr<std::vector<Edge>> StringToDFAPath(absl::string_view s) const; + absl::StatusOr<Path> StringToPath(absl::string_view s) const; - absl::StatusOr<std::string> DFAPathToString( - const std::vector<Edge>& path, size_t start_offset = 0, - std::optional<size_t> end = std::nullopt) const; + absl::StatusOr<std::string> PathToString(const Path& path) const; size_t state_count() const { return states_.size(); }