racko
commented
10 months ago I came across fuzztest grammars and noticed that they support a generation budget to limit recursion: https://github.com/google/fuzztest/blob/895ea4883cdd8c5d041a7c0def09205897572aee/fuzztest/internal/domains/in_grammar_impl.h#L197-L213
Grammars don't seem to be documented as far as I can tell. Here's what I found:
- A grammar: https://github.com/google/fuzztest/blob/895ea4883cdd8c5d041a7c0def09205897572aee/fuzztest/grammars/JSON.g4
- A bazel rule to generate a library out of it: https://github.com/google/fuzztest/blob/895ea4883cdd8c5d041a7c0def09205897572aee/fuzztest/grammars/BUILD#L28-L32
- A test that uses the grammar: https://github.com/google/fuzztest/blob/895ea4883cdd8c5d041a7c0def09205897572aee/domain_tests/in_grammar_domain_test.cc
- and its bazel definition where we see that we can depend on the grammar library: https://github.com/google/fuzztest/blob/895ea4883cdd8c5d041a7c0def09205897572aee/domain_tests/BUILD#L123-L136
A quick attempt at using this feature for my problem failed because the bazel macro can't be used outside of the fuzztest workspace:
ERROR: no such package 'fuzztest': BUILD file not found in any of the following directories. Add a BUILD file to a directory to mark it as a package.
- /path/to/my/workspace/fuzztest
ERROR: /path/to/my/workspace/some/package/BUILD:122:28: no such package 'fuzztest': BUILD file not found in any of the following directories. Add a BUILD file to a directory to mark it as a package.
- /path/to/my/workspace/fuzztest and referenced by '//some/package:regex_grammar'
ERROR: Analysis of target '//some/package:regex_grammar' failed; build aborted: Analysis failedhttps://github.com/google/fuzztest/blob/895ea4883cdd8c5d041a7c0def09205897572aee/build_defs/cc_fuzztest_grammar_library.bzl#L54
Bazel tries to resolve the //fuzztest reference to a package within my workspace instead of @com_google_fuzztest//fuzztest
I fixed it with
diff --git a/build_defs/cc_fuzztest_grammar_library.bzl b/build_defs/cc_fuzztest_grammar_library.bzl
index ea8de65..657958c 100644
--- a/build_defs/cc_fuzztest_grammar_library.bzl
+++ b/build_defs/cc_fuzztest_grammar_library.bzl
@@ -33,7 +33,7 @@ def cc_fuzztest_grammar_library(name, srcs, top_level_rule = None):
"""
output_file_name = name + ".h"
- cmd = "$(location //tools:grammar_domain_code_generator)" + \
+ cmd = "$(location @com_google_fuzztest//tools:grammar_domain_code_generator)" + \
" --output_header_file_path " + "$(@D)/" + output_file_name + \
" --input_grammar_files " + "`echo $(SRCS) | tr ' ' ','`"
if top_level_rule:
@@ -45,11 +45,11 @@ def cc_fuzztest_grammar_library(name, srcs, top_level_rule = None):
outs = [output_file_name],
cmd = cmd,
heuristic_label_expansion = False,
- tools = ["//tools:grammar_domain_code_generator"],
+ tools = ["@com_google_fuzztest//tools:grammar_domain_code_generator"],
)
native.cc_library(
name = name,
hdrs = [output_file_name],
- deps = ["//fuzztest:domain"],
+ deps = ["@com_google_fuzztest//fuzztest:domain"],
)Then I created the following grammar:
// regex.g4
grammar REGEX_GRAMMAR;
E : E '|' E | T ;
T : T T | F ;
F : F '*' | F '?' | G ;
G : '(' E ')' | '\\' H | [a-zA-Z0-9_] ;
H : '\\' | '|' | '*' | '(' | ')' ;
WSPACE : [ \t\n\r]+ -> skip;Used
# some/package/BUILD
load("@com_google_fuzztest//build_defs:cc_fuzztest_grammar_library.bzl", "cc_fuzztest_grammar_library")
cc_fuzztest_grammar_library(
name = "regex_grammar",
srcs = ["regex.g4"],
top_level_rule = "E",
)
cc_test(
name = "fuzztest",
size = "small",
srcs = ["fuzztest.cpp"],
deps = [
# ...
"@com_google_fuzztest//fuzztest",
"@com_google_fuzztest//fuzztest:fuzztest_gtest_main",
"@com_google_googletest//:gtest",
":regex_grammar",
],
)And finally
/// @file fuzztest.cpp
#include "some/package/regex_grammar.h"
// ...
FUZZ_TEST(Fixture, Test).WithDomains(fuzztest::InEGrammar());And it works :slightly_smiling_face: At least I got a test run that looked like it did what it's supposed to do.
With --config=fuzztest I got a different kind of stack related error. This time:
*** stack smashing detected ***: terminated
Program received signal SIGABRT, Aborted
0x00007ffff7a8783c in ?? () from /usr/lib/libc.so.6
(gdb) bt
#0 0x00007ffff7a8783c in ?? () from /usr/lib/libc.so.6
#1 0x00007ffff7a37668 in raise () from /usr/lib/libc.so.6
#2 0x00007ffff7a1f4b8 in abort () from /usr/lib/libc.so.6
#3 0x00007ffff7a20390 in ?? () from /usr/lib/libc.so.6
#4 0x00007ffff7b17b4b in __fortify_fail () from /usr/lib/libc.so.6
#5 0x00007ffff7b18e56 in __stack_chk_fail () from /usr/lib/libc.so.6
#6 0x0000555555b71fb5 in absl::container_internal::raw_hash_set<absl::container_internal::FlatHashMapPolicy<int, int>, absl::hash_internal::Hash<int>, std::equal_to<int>, std::allocator<std::pair<int const, int> > >::raw_hash_set (this=0x7fffffff7e28)
at external/com_google_absl/absl/container/internal/raw_hash_set.h:3206
#7 0x0000555555b71f15 in absl::container_internal::raw_hash_map<absl::container_internal::FlatHashMapPolicy<int, int>, absl::hash_internal::Hash<int>, std::equal_to<int>, std::allocator<std::pair<int const, int> > >::raw_hash_map (
this=<error reading variable: Cannot access memory at address 0xfffffffffffffff8>)
at external/com_google_absl/absl/container/internal/raw_hash_map.h:64
Backtrace stopped: previous frame inner to this frame (corrupt stack?)I need to investigate more when I find the time.
I won't close this issue because using DomainBuilder like this still results in stack overflows.
I was trying to define a domain of somewhat simple regexes:
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:I tried to see if simplifying the domain definition helps, and it does. The following takes a few seconds more to blow up:
And the following doesn't run into stack overflows at all:
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
Gettook additional parameters andSetcould 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: