Redistribute energy for Corpus

I found that the initial corpus allocation of fork mode has certain defects.
I designed a new initial corpus allocation strategy based on size grouping.
This method ca

Redistribute energy for Corpus

I found that the initial corpus allocation of fork mode has certain defects.
I designed a new initial corpus allocation strategy based on size grouping.
This method can give more energy to the small seeds in the corpus and
increase the throughput of the test.

Fuzzbench data (glibfuzzer is -fork_corpus_groups=1):
https://www.fuzzbench.com/reports/experimental/2021-08-05-parallel/index.html

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D105084

show more ...

Greedy set cover implementation of `Merger::Merge`

Extend the existing single-pass algorithm for `Merger::Merge` with an algorithm that gives better results. This new implementation can be used with

Greedy set cover implementation of `Merger::Merge`

Extend the existing single-pass algorithm for `Merger::Merge` with an algorithm that gives better results. This new implementation can be used with a new **set_cover_merge=1** flag.

This greedy set cover implementation gives a substantially smaller final corpus (40%-80% less testcases) while preserving the same features/coverage. At the same time, the execution time penalty is not that significant (+50% for ~1M corpus files and far less for smaller corpora). These results were obtained by comparing several targets with varying size corpora.

Change `Merger::CrashResistantMergeInternalStep` to collect all features from each file and not just unique ones. This is needed for the set cover algorithm to work correctly. The implementation of the algorithm in `Merger::SetCoverMerge` uses a bitvector to store features that are covered by a file while performing the pass. Collisions while indexing the bitvector are ignored similarly to the fuzzer.

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D105284

show more ...

[libFuzzer] replace Vector/Set with std::vector/std::set. The custom names are not required any more since we now build with a private version of libc++. Fix some of the 81+ character lines. Mechanic

[libFuzzer] replace Vector/Set with std::vector/std::set. The custom names are not required any more since we now build with a private version of libc++. Fix some of the 81+ character lines. Mechanical change, NFC expected.

[libFuzzer] replace Vector/Set with std::vector/std::set.

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D107374

show more ...

Revert "Refactor mutation strategies into a standalone library"

This reverts commit 361f742f168de0f0f256802a329c19d081615d0d.

Refactor mutation strategies into a standalone library

This change introduces libMutagen/libclang_rt.mutagen.a as a subset of libFuzzer/libclang_rt.fuzzer.a. This library contains only the fuzzing s

Refactor mutation strategies into a standalone library

This change introduces libMutagen/libclang_rt.mutagen.a as a subset of libFuzzer/libclang_rt.fuzzer.a. This library contains only the fuzzing strategies used by libFuzzer to produce new test inputs from provided inputs, dictionaries, and SanitizerCoverage feedback.

Most of this change is simply moving sections of code to one side or the other of the library boundary. The only meaningful new code is:

* The Mutagen.h interface and its implementation in Mutagen.cpp.
* The following methods in MutagenDispatcher.cpp:
* UseCmp
* UseMemmem
* SetCustomMutator
* SetCustomCrossOver
* LateInitialize (similar to the MutationDispatcher's original constructor)
* Mutate_AddWordFromTORC (uses callbacks instead of accessing TPC directly)
* StartMutationSequence
* MutationSequence
* DictionaryEntrySequence
* RecommendDictionary
* RecommendDictionaryEntry
* FuzzerMutate.cpp (which now justs sets callbacks and handles printing)
* MutagenUnittest.cpp (which adds tests of Mutagen.h)

A note on performance: This change was tested with a 100 passes of test/fuzzer/LargeTest.cpp with 1000 runs per pass, both with and without the change. The running time distribution was qualitatively similar both with and without the change, and the average difference was within 30 microseconds (2.240 ms/run vs 2.212 ms/run, respectively). Both times were much higher than observed with the fully optimized system clang (~0.38 ms/run), most likely due to the combination of CMake "dev mode" settings (e.g. CMAKE_BUILD_TYPE="Debug", LLVM_ENABLE_LTO=OFF, etc.). The difference between the two versions built similarly seems to be "in the noise" and suggests no meaningful performance degradation.

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D102447

show more ...

Revert "Refactor mutation strategies into a standalone library"

This reverts commit c4a41cd77c15c2905ac74beeec09f8343a65a549 due to
buildbot failure.

Refactor mutation strategies into a standalone library

This change introduces libMutagen/libclang_rt.mutagen.a as a subset of libFuzzer/libclang_rt.fuzzer.a. This library contains only the fuzzing s

Refactor mutation strategies into a standalone library

This change introduces libMutagen/libclang_rt.mutagen.a as a subset of libFuzzer/libclang_rt.fuzzer.a. This library contains only the fuzzing strategies used by libFuzzer to produce new test inputs from provided inputs, dictionaries, and SanitizerCoverage feedback.

Most of this change is simply moving sections of code to one side or the other of the library boundary. The only meaningful new code is:

* The Mutagen.h interface and its implementation in Mutagen.cpp.
* The following methods in MutagenDispatcher.cpp:
* UseCmp
* UseMemmem
* SetCustomMutator
* SetCustomCrossOver
* LateInitialize (similar to the MutationDispatcher's original constructor)
* Mutate_AddWordFromTORC (uses callbacks instead of accessing TPC directly)
* StartMutationSequence
* MutationSequence
* DictionaryEntrySequence
* RecommendDictionary
* RecommendDictionaryEntry
* FuzzerMutate.cpp (which now justs sets callbacks and handles printing)
* MutagenUnittest.cpp (which adds tests of Mutagen.h)

A note on performance: This change was tested with a 100 passes of test/fuzzer/LargeTest.cpp with 1000 runs per pass, both with and without the change. The running time distribution was qualitatively similar both with and without the change, and the average difference was within 30 microseconds (2.240 ms/run vs 2.212 ms/run, respectively). Both times were much higher than observed with the fully optimized system clang (~0.38 ms/run), most likely due to the combination of CMake "dev mode" settings (e.g. CMAKE_BUILD_TYPE="Debug", LLVM_ENABLE_LTO=OFF, etc.). The difference between the two versions built similarly seems to be "in the noise" and suggests no meaningful performance degradation.

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D102447

show more ...

[crt][fuzzer] Fix up various numeric conversions

Attempting to build a standalone libFuzzer in Fuchsia's default toolchain for the purpose of cross-compiling the unit tests revealed a number of not

[crt][fuzzer] Fix up various numeric conversions

Attempting to build a standalone libFuzzer in Fuchsia's default toolchain for the purpose of cross-compiling the unit tests revealed a number of not-quite-proper type conversions. Fuchsia's toolchain include `-std=c++17` and `-Werror`, among others, leading to many errors like `-Wshorten-64-to-32`, `-Wimplicit-float-conversion`, etc.

Most of these have been addressed by simply making the conversion explicit with a `static_cast`. These typically fell into one of two categories: 1) conversions between types where high precision isn't critical, e.g. the "energy" calculations for `InputInfo`, and 2) conversions where the values will never reach the bits being truncated, e.g. `DftTimeInSeconds` is not going to exceed 136 years.

The major exception to this is the number of features: there are several places that treat features as `size_t`, and others as `uint32_t`. This change makes the decision to cap the features at 32 bits. The maximum value of a feature as produced by `TracePC::CollectFeatures` is roughly:
(NumPCsInPCTables + ValueBitMap::kMapSizeInBits + ExtraCountersBegin() - ExtraCountersEnd() + log2(SIZE_MAX)) * 8

It's conceivable for extremely large targets and/or extra counters that this limit could be reached. This shouldn't break fuzzing, but it will cause certain features to collide and lower the fuzzers overall precision. To address this, this change adds a warning to TracePC::PrintModuleInfo about excessive feature size if it is detected, and recommends refactoring the fuzzer into several smaller ones.

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D97992

show more ...

[fuzzer] Add Windows Visual C++ exception intercept

Adds a new option, `handle_winexcept` to try to intercept uncaught
Visual C++ exceptions on Windows. On Linux, such exceptions are handled
implici

[fuzzer] Add Windows Visual C++ exception intercept

Adds a new option, `handle_winexcept` to try to intercept uncaught
Visual C++ exceptions on Windows. On Linux, such exceptions are handled
implicitly by `std::terminate()` raising `SIBABRT`. This option brings the
Windows behavior in line with Linux.

Unfortunately this exception code is intentionally undocumented, however
has remained stable for the last decade. More information can be found
here: https://devblogs.microsoft.com/oldnewthing/20100730-00/?p=13273

Reviewed By: morehouse, metzman

Differential Revision: https://reviews.llvm.org/D89755

show more ...

[libFuzzer] Added -print_full_coverage flag.

-print_full_coverage=1 produces a detailed branch coverage dump when run on a single file.
Uses same infrastructure as -print_coverage flag, but prints a

[libFuzzer] Added -print_full_coverage flag.

-print_full_coverage=1 produces a detailed branch coverage dump when run on a single file.
Uses same infrastructure as -print_coverage flag, but prints all branches (regardless of coverage status) in an easy-to-parse format.
Usage: For internal use with machine learning fuzzing models which require detailed coverage information on seed files to generate mutations.

Differential Revision: https://reviews.llvm.org/D85928

show more ...

[libFuzzer] Enable entropic by default.

Entropic has performed at least on par with vanilla scheduling on
Clusterfuzz, and has shown a slight coverage improvement on FuzzBench:
https://www.fuzzbench

[libFuzzer] Enable entropic by default.

Entropic has performed at least on par with vanilla scheduling on
Clusterfuzz, and has shown a slight coverage improvement on FuzzBench:
https://www.fuzzbench.com/reports/2020-08-31/index.html

Reviewed By: Dor1s

Differential Revision: https://reviews.llvm.org/D87476

show more ...

[libFuzzer] Add a command-line option for tracing mutation of corpus inputs in the dot graph format.

This patch adds a new command-line option -mutation_graph_file=FILE for
debugging purposes, which

[libFuzzer] Add a command-line option for tracing mutation of corpus inputs in the dot graph format.

This patch adds a new command-line option -mutation_graph_file=FILE for
debugging purposes, which traces how corpus inputs evolve during a fuzzing
run. For each new input that is added to the corpus, a new vertex corresponding
to the added input, as well as a new edge that connects its base input to itself
are written to the given file. Each vertex is labeled with the filename of the
input, and each edge is labeled with the mutation sequence that led to the input
w.r.t. its base input.

The format of the mutation graph file is the dot file format. Once prepended and
appended with "graph {" and "}", respectively, the graph becomes a valid dot
file and can be visualized.

Differential Revision: https://reviews.llvm.org/D86560

show more ...

[libFuzzer] Scale energy assigned to each input based on input execution time.

This patch scales the energy computed by the Entropic schedule based on the
execution time of each input. The input exe

[libFuzzer] Scale energy assigned to each input based on input execution time.

This patch scales the energy computed by the Entropic schedule based on the
execution time of each input. The input execution time is compared with the
average execution time of inputs in the corpus, and, based on the amount by
which they differ, the energy is scaled from 0.1x (for inputs executing slow) to
3x (for inputs executing fast). Note that the exact scaling criteria and formula
is borrowed from AFL.

On FuzzBench, this gives a sizeable throughput increase, which in turn leads to
more coverage on several benchmarks. For details, see the following report.

https://storage.googleapis.com/fuzzer-test-suite-public/exectime-report/index.html

Differential Revision: https://reviews.llvm.org/D86092

show more ...

[libFuzzer] Evenly select inputs to cross over with from the corpus regardless of the input's coverage.

This patch adds an option "cross_over_uniform_dist", which, if 1, considers all
inputs in the

[libFuzzer] Evenly select inputs to cross over with from the corpus regardless of the input's coverage.

This patch adds an option "cross_over_uniform_dist", which, if 1, considers all
inputs in the corpus for the crossover input selection. More specifically, this
patch uses a uniform distribution of all inputs in the corpus for the CrossOver
input selection. Note that input selection for mutation is still fully
determined by the scheduling policy (i.e., vanilla or Entropic); the uniform
distribution only applies to the secondary input selection, only for the
crossover mutation of the base input chosen by the scheduling policy. This way
the corpus inputs that have useful fragments in them, even though they are
deprioritized by the scheduling policy, have chances of getting mixed with other
inputs that are prioritized and selected as base input for mutation.

Differential Revision: https://reviews.llvm.org/D86954

show more ...

[libFuzzer] Add an option to keep initial seed inputs around.

This patch adds an option "keep_seed" to keep all initial seed inputs in the
corpus. Previously, only the initial seed inputs that find

[libFuzzer] Add an option to keep initial seed inputs around.

This patch adds an option "keep_seed" to keep all initial seed inputs in the
corpus. Previously, only the initial seed inputs that find new coverage were
added to the corpus, and all the other initial inputs were discarded. We
observed in some circumstances that useful initial seed inputs are discarded as
they find no new coverage, even though they contain useful fragments in them
(e.g., SQLITE3 FuzzBench benchmark). This newly added option provides a way to
keeping seed inputs in the corpus for those circumstances. With this patch, and
with -keep_seed=1, all initial seed inputs are kept in the corpus regardless of
whether they find new coverage or not. Further, these seed inputs are not
replaced with smaller inputs even if -reduce_inputs=1.

Differential Revision: https://reviews.llvm.org/D86577

show more ...

[fuzzer] Create user provided fuzzer writeable directories when requested if they dont exist

Currently, libFuzzer will exit with an error message if a non-existent
directory is provided for any of t

[fuzzer] Create user provided fuzzer writeable directories when requested if they dont exist

Currently, libFuzzer will exit with an error message if a non-existent
directory is provided for any of the appropriate arguments. For cases
where libFuzzer is used in a specialized embedded environment, it would
be much easier to have libFuzzer create the directories for the user.

This patch accommodates for this scenario by allowing the user to provide
the argument `-create_missing_dirs=1` which makes libFuzzer attempt to
create the `artifact_prefix`, `exact_artifact_path`,
`features_dir` and/or corpus directory if they don't already exist rather
than throw an error and exit.

Split off from D84808 as requested [here](https://reviews.llvm.org/D84808#2208546).

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D86733

show more ...

Revert "[fuzzer] Create user provided fuzzer writeable directories when requested if they dont exist"

This reverts commit cb8912799d4372a3a1c0bf528bb4c4885caf4c45, since the
test fails on Windows.

[fuzzer] Create user provided fuzzer writeable directories when requested if they dont exist

Currently, libFuzzer will exit with an error message if a non-existent
directory is provided for any of t

[fuzzer] Create user provided fuzzer writeable directories when requested if they dont exist

Currently, libFuzzer will exit with an error message if a non-existent
directory is provided for any of the appropriate arguments. For cases
where libFuzzer is used in a specialized embedded environment, it would
be much easier to have libFuzzer create the directories for the user.

This patch accommodates for this scenario by allowing the user to provide
the argument `-create_missing_dirs=1` which makes libFuzzer attempt to
create the `artifact_prefix`, `exact_artifact_path`,
`features_dir` and/or corpus directory if they don't already exist rather
than throw an error and exit.

Split off from D84808 as requested [here](https://reviews.llvm.org/D84808#2208546).

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D86733

show more ...

[libFuzzer] Error and exit if user supplied fuzzer writeable directories don't exist

Currently, libFuzzer will exit with an error message if a non-existent
corpus directory is provided. However, if

[libFuzzer] Error and exit if user supplied fuzzer writeable directories don't exist

Currently, libFuzzer will exit with an error message if a non-existent
corpus directory is provided. However, if a user provides a non-existent
directory for the `artifact_prefix`, `exact_artifact_path`, or
`features_dir`, libFuzzer will continue execution but silently fail to
write artifacts/features.

To improve the user experience, this PR adds validation for the existence of
all user supplied directories before executing the main fuzzing loop. If they
don't exist, libFuzzer will exit with an error message.

Patch By: dgg5503

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D84808

show more ...

[libFuzzer] Fix minimizing timeouts

When one tries to minimize timeouts using -minimize_crash=1,
minimization immediately fails. The following sequence of events is
responsible for this:

[parent] S

[libFuzzer] Fix minimizing timeouts

When one tries to minimize timeouts using -minimize_crash=1,
minimization immediately fails. The following sequence of events is
responsible for this:

[parent] SIGALRM occurs
[parent] read() returns -EINTR (or -ERESTARTSYS according to strace)
[parent] fgets() returns NULL
[parent] ExecuteCommand() closes child's stdout and returns
[child ] SIGALRM occurs
[child ] AlarmCallback() attempts to write "ALARM: ..." to stdout
[child ] Dies with SIGPIPE without calling DumpCurrentUnit()
[parent] Does not see -exact_artifact_path and exits

When minimizing, the timer in parent is not necessary, so fix by not
setting it in this case.

Reviewed By: morehouse

Differential Revision: https://reviews.llvm.org/D85359

show more ...

Replace fuzzer::FuzzerDriver's INTERFACE marking with new LLVMRunFuzzerDriver.

This adds a new extern "C" function that serves the same purpose. This removes the need for external users to depend on

Replace fuzzer::FuzzerDriver's INTERFACE marking with new LLVMRunFuzzerDriver.

This adds a new extern "C" function that serves the same purpose. This removes the need for external users to depend on internal headers in order to use this feature. It also standardizes the interface in a way that other fuzzing engines will be able to match.

Patch By: IanPudney

Reviewed By: kcc

Differential Revision: https://reviews.llvm.org/D84561

show more ...

Corrected __libfuzzer_is_present symbol inclusion for MSVC x86 32-bit

The incorrect symbol will cause linking failures for 32-bit targets:

clang_rt.fuzzer-i386.lib(FuzzerDriver.obj) : error LNK2001

Corrected __libfuzzer_is_present symbol inclusion for MSVC x86 32-bit

The incorrect symbol will cause linking failures for 32-bit targets:

clang_rt.fuzzer-i386.lib(FuzzerDriver.obj) : error LNK2001: unresolved external symbol __libfuzzer_is_present

Verified no longer fails to link with this change for 32-bit and still succeeds for 64-bit MSVC.

Reviewed By: vitalybuka

Differential Revision: https://reviews.llvm.org/D83594

show more ...

[libFuzzer] Separate platform related macros out from FuzzerDefs.h into FuzzerPlatform.h, and adjust includes in other files.

Summary: This patch separates platform related macros in lib/fuzzer/Fuzz

[libFuzzer] Separate platform related macros out from FuzzerDefs.h into FuzzerPlatform.h, and adjust includes in other files.

Summary: This patch separates platform related macros in lib/fuzzer/FuzzerDefs.h into lib/fuzzer/FuzzerPlatform.h, and use FuzzerPlatform.h where necessary. This separation helps when compiling libFuzzer's interceptor module (under review); an unnecessary include of standard headers (such as string.h) may produce conflicts/ambiguation with the interceptor's declarations/definitions of library functions, which complicates interceptor implementation.

Reviewers: morehouse, hctim

Reviewed By: morehouse

Subscribers: krytarowski, #sanitizers

Tags: #sanitizers

Differential Revision: https://reviews.llvm.org/D83805

show more ...

Entropic: Boosting LibFuzzer Performance

Summary:
This is collaboration between Marcel Boehme @ Monash, Australia and Valentin Manès plus Sang Kil Cha @ KAIST, South Korea.

We have made a few modif

Entropic: Boosting LibFuzzer Performance

Summary:
This is collaboration between Marcel Boehme @ Monash, Australia and Valentin Manès plus Sang Kil Cha @ KAIST, South Korea.

We have made a few modifications to boost LibFuzzer performance by changing how weights are assigned to the seeds in the corpus. Essentially, seeds that reveal more "information" about globally rare features are assigned a higher weight. Our results on the Fuzzer Test Suite seem quite promising. In terms of bug finding, our Entropic patch usually finds the same errors much faster and in more runs. In terms of coverage, our version Entropic achieves the same coverage in less than half the time for the majority of subjects. For the lack of space, we shared more detailed performance results directly with @kcc. We'll publish the preprint with all the technical details as soon as it is accepted. Happy to share if you drop us an email.

There should be plenty of opportunities to optimise further. For instance, while Entropic achieves the same coverage in less than half the time, Entropic has a much lower #execs per second. We ran the perf-tool and found a few performance bottlenecks.

Thanks for open-sourcing LibFuzzer (and the entire LLVM Compiler Infrastructure)! This has been such a tremendous help to my research.

Patch By: Marcel Boehme

Reviewers: kcc, metzman, morehouse, Dor1s, vitalybuka

Reviewed By: kcc

Subscribers: dgg5503, Valentin, llvm-commits, kcc

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D73776

show more ...

[Fuzzer] Rename ExecuteCommandWithPopen to ExecuteCommandNon-Fushsia target will keep using popen/pclose implementation. OnFuchsia, Two-args version of `ExecuteCommand` is a simple wrapper of theone-

[Fuzzer] Rename ExecuteCommandWithPopen to ExecuteCommandNon-Fushsia target will keep using popen/pclose implementation. OnFuchsia, Two-args version of `ExecuteCommand` is a simple wrapper of theone-arg version. (Hopefully) Fix D73329 build on Fuchsia.

show more ...