[SanitizerCoverage] implement instrumentation for lowest stack pointer value

[Quuxplusone]

Bugzilla Link	PR33857
Status	RESOLVED FIXED
Importance	P enhancement
Reported by	Kostya Serebryany (kcc@google.com)
Reported on	2017-07-19 18:41:43 -0700
Last modified on	2017-08-30 19:09:28 -0700
Version	unspecified
Hardware	PC Linux
CC	llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also

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;

[Quuxplusone]

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

[Quuxplusone]

r311427 disable the test as it fails on the bot

[Quuxplusone]

Which bot fails?

[Quuxplusone]

(In reply to Matt Morehouse from comment #3)
> 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 to `TLS 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 to `TLS 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.

[Quuxplusone]

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

[Quuxplusone]

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

[Quuxplusone]

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.

[Quuxplusone]

(In reply to Matt Morehouse from comment #7)
> 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.

[Quuxplusone]

(In reply to Kostya Serebryany from comment #8)
> 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.

[Quuxplusone]

> 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

[Quuxplusone]

r312185: Enable on Linux for -fsanitize=fuzzer.