[SanitizerCoverage] implement instrumentation for lowest stack pointer value

[kcc]

Bugzilla Link	33857
Resolution	FIXED
Resolved on	Aug 30, 2017 19:09
Version	unspecified
OS	Linux

Extended Description

r308577 adds a libFuzzer logic to use recursion depth as a signal (inspired by https://guidovranken.wordpress.com/2017/07/08/libfuzzer-gv-new-techniques-for-dramatically-faster-fuzzing/, "Stack-depth-guided fuzzing")

We need to extract the recursion depth with a dedicated inlined compiler instrumentation.

it should be something like -fsanitize-coverage=stack-depth that would insert this code at the beginning of every function:

uintptr_t current_stack = builtin_frame_address(0); if (sanitizer_cov_lowest_stack > current_stack) __sanitizer_cov_lowest_stack = current_stack;

// Users should declare this in their code (e.g. in libFuzzer) thread_local uintptr __sanitizer_cov_lowest_stack;

[morehouse]

r312185: Enable on Linux for -fsanitize=fuzzer.

[kcc]

I'm thinking we should be able to ignore all intrinsics. Even if the intrinsic isn't inlined, it seems unlikely that it would use recursion.

yep

[morehouse]

Yes, I think it's fine to scan for existing calls, where we could also ignore calls to (most?) intrinsics. This pass already does a linear scan over all instructions anyway.

I'm thinking we should be able to ignore all intrinsics. Even if the intrinsic isn't inlined, it seems unlikely that it would use recursion.

[kcc]

I haven't been able to find any leaf function indicator available at the LLVM pass level. But we can do a linear scan to determine if a function has any calls in it.

Yes, I think it's fine to scan for existing calls, where we could also ignore calls to (most?) intrinsics. This pass already does a linear scan over all instructions anyway.

[morehouse]

I haven't been able to find any leaf function indicator available at the LLVM pass level. But we can do a linear scan to determine if a function has any calls in it.

[kcc]

Also: make sure the accesses to __sancov_lowest_stack are not sanitized. Probably just apply SetNoSanitizeMetadata to the load and store insns

[morehouse]

r311490 switches to initialexec TLS type and eliminates calls to the TLS wrapper. Test has been re-enabled and bot is green.

[kcc]

Which bot fails?

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fuzzer/builds/7490/steps/check-fuzzer/logs/stdio

(I disabled the test, so the bot is green now).

FAIL: LLVMFuzzer :: deep-recursion.test (6 of 130) **** TEST 'LLVMFuzzer :: deep-recursion.test' FAILED **** Script:

/mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm_build0/./bin/clang -std=c++11 -lstdc++ -gline-tables-only -fsanitize=address,fuzzer -I/mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/projects/compiler-rt/lib/fuzzer -fsanitize-coverage=stack-depth /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/projects/compiler-rt/test/fuzzer/DeepRecursionTest.cpp -o /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm_build0/projects/compiler-rt/test/fuzzer/Output/deep-recursion.test.tmp not /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm_build0/projects/compiler-rt/test/fuzzer/Output/deep-recursion.test.tmp -seed=1 -runs=100000000 2>&1 | FileCheck /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/projects/compiler-rt/test/fuzzer/deep-recursion.test

Exit Code: 1

Command Output (stderr):

/tmp/lit_tmp_tEpVa6/DeepRecursionTest-c0b77c.o: In function Recursive(unsigned char const*, unsigned long, int)': /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/projects/compiler-rt/test/fuzzer/DeepRecursionTest.cpp:13: undefined reference toTLS wrapper function for __sancov_lowest_stack' /tmp/lit_tmp_tEpVa6/DeepRecursionTest-c0b77c.o: In function LLVMFuzzerTestOneInput': /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/projects/compiler-rt/test/fuzzer/DeepRecursionTest.cpp:21: undefined reference toTLS wrapper function for __sancov_lowest_stack' clang-6.0: error: linker command failed with exit code 1 (use -v to see invocation)

This passes on my machine though.

[morehouse]

Which bot fails?

[kcc]

r311427 disable the test as it fails on the bot

[kcc]

The basic code is there: http://llvm.org/viewvc/llvm-project?rev=311186&view=rev

However, it needs some more love:

• don't instrument leaf functions (??)
• if possible, use a faster TLS type to access __sancov_lowest_stack
• enable -fsanitize-coverage=stack-depth as part of -fsanitize=fuzzer

[kcc]

assigned to @morehouse