From 6cc3ed7cdddcd09a5905039054fbd306e414202d Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Fri, 4 Sep 2015 00:12:11 +0000 Subject: [PATCH] [libFuzzer] actually make the dictionaries work (+docs) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@246825 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/LibFuzzer.rst | 20 ++++++ lib/Fuzzer/FuzzerDriver.cpp | 11 ++-- lib/Fuzzer/FuzzerInterface.h | 13 +++- lib/Fuzzer/FuzzerLoop.cpp | 3 + lib/Fuzzer/FuzzerMutate.cpp | 54 +++++++++++++--- lib/Fuzzer/test/CMakeLists.txt | 1 + lib/Fuzzer/test/FuzzerUnittest.cpp | 80 +++++++++++++++++++++--- lib/Fuzzer/test/SimpleDictionaryTest.cpp | 25 ++++++++ lib/Fuzzer/test/dict1.txt | 4 ++ lib/Fuzzer/test/fuzzer.test | 3 + 10 files changed, 190 insertions(+), 24 deletions(-) create mode 100644 lib/Fuzzer/test/SimpleDictionaryTest.cpp create mode 100644 lib/Fuzzer/test/dict1.txt diff --git a/docs/LibFuzzer.rst b/docs/LibFuzzer.rst index dfcf06d7030..519c651bf00 100644 --- a/docs/LibFuzzer.rst +++ b/docs/LibFuzzer.rst @@ -256,6 +256,26 @@ Voila:: Advanced features ================= +Dictionaries +------------ +*EXPERIMENTAL*. +LibFuzzer supports user-supplied dictionaries with input language keywords +or other interesting byte sequences (e.g. multi-byte magic values). +Use ``-dict=DICTIONARY_FILE``. For some input languages using a dictionary +may significantly improve the search speed. +The dictionary syntax is similar to that used by AFL_ for its ``-x`` option:: + + # Lines starting with '#' and empty lines are ignored. + + # Adds "blah" (w/o quotes) to the dictionary. + kw1="blah" + # Use \\ for backslash and \" for quotes. + kw2="\"ac\\dc\"" + # Use \xAB for hex values + kw3="\xF7\xF8" + # the name of the keyword followed by '=' may be omitted: + "foo\x0Abar" + Data-flow-guided fuzzing ------------------------ diff --git a/lib/Fuzzer/FuzzerDriver.cpp b/lib/Fuzzer/FuzzerDriver.cpp index 7cb4f3dc1c5..8506fb48d0f 100644 --- a/lib/Fuzzer/FuzzerDriver.cpp +++ b/lib/Fuzzer/FuzzerDriver.cpp @@ -251,18 +251,17 @@ int FuzzerDriver(int argc, char **argv, UserSuppliedFuzzer &USF) { Options.SyncCommand = Flags.sync_command; Options.SyncTimeout = Flags.sync_timeout; Options.ReportSlowUnits = Flags.report_slow_units; - Fuzzer F(USF, Options); - - if (Flags.apply_tokens) - return ApplyTokens(F, Flags.apply_tokens); - if (Flags.dict) if (!ParseDictionaryFile(FileToString(Flags.dict), &Options.Dictionary)) return 1; - if (Flags.verbosity > 0 && !Options.Dictionary.empty()) Printf("Dictionary: %zd entries\n", Options.Dictionary.size()); + Fuzzer F(USF, Options); + + if (Flags.apply_tokens) + return ApplyTokens(F, Flags.apply_tokens); + unsigned Seed = Flags.seed; // Initialize Seed. if (Seed == 0) diff --git a/lib/Fuzzer/FuzzerInterface.h b/lib/Fuzzer/FuzzerInterface.h index d3843a47d1c..8798b650383 100644 --- a/lib/Fuzzer/FuzzerInterface.h +++ b/lib/Fuzzer/FuzzerInterface.h @@ -64,7 +64,8 @@ class FuzzerRandomLibc : public FuzzerRandomBase { class MutationDispatcher { public: - MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) {} + MutationDispatcher(FuzzerRandomBase &Rand); + ~MutationDispatcher(); /// Mutates data by shuffling bytes. size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize); /// Mutates data by erasing a byte. @@ -76,6 +77,10 @@ class MutationDispatcher { /// Mutates data by chanding one bit. size_t Mutate_ChangeBit(uint8_t *Data, size_t Size, size_t MaxSize); + /// Mutates data by adding a word from the dictionary. + size_t Mutate_AddWordFromDictionary(uint8_t *Data, size_t Size, + size_t MaxSize); + /// Applies one of the above mutations. /// Returns the new size of data which could be up to MaxSize. size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize); @@ -84,8 +89,12 @@ class MutationDispatcher { size_t CrossOver(const uint8_t *Data1, size_t Size1, const uint8_t *Data2, size_t Size2, uint8_t *Out, size_t MaxOutSize); + void AddWordToDictionary(const uint8_t *Word, size_t Size); + private: FuzzerRandomBase &Rand; + struct Impl; + Impl *MDImpl; }; // For backward compatibility only, deprecated. @@ -140,6 +149,8 @@ class UserSuppliedFuzzer { FuzzerRandomBase &GetRand() { return *Rand; } + MutationDispatcher &GetMD() { return MD; } + private: bool OwnRand = false; FuzzerRandomBase *Rand; diff --git a/lib/Fuzzer/FuzzerLoop.cpp b/lib/Fuzzer/FuzzerLoop.cpp index dd81616b455..e65bd331430 100644 --- a/lib/Fuzzer/FuzzerLoop.cpp +++ b/lib/Fuzzer/FuzzerLoop.cpp @@ -328,6 +328,9 @@ void Fuzzer::MutateAndTestOne(Unit *U) { } void Fuzzer::Loop(size_t NumIterations) { + for (auto &U: Options.Dictionary) + USF.GetMD().AddWordToDictionary(U.data(), U.size()); + for (size_t i = 1; i <= NumIterations; i++) { for (size_t J1 = 0; J1 < Corpus.size(); J1++) { SyncCorpus(); diff --git a/lib/Fuzzer/FuzzerMutate.cpp b/lib/Fuzzer/FuzzerMutate.cpp index 82cee646c06..70fa88da30a 100644 --- a/lib/Fuzzer/FuzzerMutate.cpp +++ b/lib/Fuzzer/FuzzerMutate.cpp @@ -17,6 +17,28 @@ namespace fuzzer { +typedef size_t (MutationDispatcher::*Mutator)(uint8_t *Data, size_t Size, + size_t Max); + +struct MutationDispatcher::Impl { + std::vector Dictionary; + std::vector Mutators; + Impl() { + Mutators.push_back(&MutationDispatcher::Mutate_EraseByte); + Mutators.push_back(&MutationDispatcher::Mutate_InsertByte); + Mutators.push_back(&MutationDispatcher::Mutate_ChangeByte); + Mutators.push_back(&MutationDispatcher::Mutate_ChangeBit); + Mutators.push_back(&MutationDispatcher::Mutate_ShuffleBytes); + } + void AddWordToDictionary(const uint8_t *Word, size_t Size) { + if (Dictionary.empty()) { + Mutators.push_back(&MutationDispatcher::Mutate_AddWordFromDictionary); + } + Dictionary.push_back(Unit(Word, Word + Size)); + } +}; + + static char FlipRandomBit(char X, FuzzerRandomBase &Rand) { int Bit = Rand(8); char Mask = 1 << Bit; @@ -80,6 +102,19 @@ size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, return Size; } +size_t MutationDispatcher::Mutate_AddWordFromDictionary(uint8_t *Data, + size_t Size, + size_t MaxSize) { + auto &D = MDImpl->Dictionary; + if (D.empty()) return Size; // FIXME: indicate failure. + const Unit &Word = D[Rand(D.size())]; + if (Size + Word.size() > MaxSize) return Size; + size_t Idx = Rand(Size + 1); + memmove(Data + Idx + Word.size(), Data + Idx, Size - Idx); + memcpy(Data + Idx, Word.data(), Word.size()); + return Size + Word.size(); +} + // Mutates Data in place, returns new size. size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { assert(MaxSize > 0); @@ -90,15 +125,20 @@ size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { return MaxSize; } assert(Size > 0); - switch (Rand(5)) { - case 0: Size = Mutate_EraseByte(Data, Size, MaxSize); break; - case 1: Size = Mutate_InsertByte(Data, Size, MaxSize); break; - case 2: Size = Mutate_ChangeByte(Data, Size, MaxSize); break; - case 3: Size = Mutate_ChangeBit(Data, Size, MaxSize); break; - case 4: Size = Mutate_ShuffleBytes(Data, Size, MaxSize); break; - } + size_t MutatorIdx = Rand(MDImpl->Mutators.size()); + Size = (this->*(MDImpl->Mutators[MutatorIdx]))(Data, Size, MaxSize); assert(Size > 0); return Size; } +void MutationDispatcher::AddWordToDictionary(const uint8_t *Word, size_t Size) { + MDImpl->AddWordToDictionary(Word, Size); +} + +MutationDispatcher::MutationDispatcher(FuzzerRandomBase &Rand) : Rand(Rand) { + MDImpl = new Impl; +} + +MutationDispatcher::~MutationDispatcher() { delete MDImpl; } + } // namespace fuzzer diff --git a/lib/Fuzzer/test/CMakeLists.txt b/lib/Fuzzer/test/CMakeLists.txt index 893274df9a5..a9e65708ede 100644 --- a/lib/Fuzzer/test/CMakeLists.txt +++ b/lib/Fuzzer/test/CMakeLists.txt @@ -21,6 +21,7 @@ set(Tests MemcmpTest NullDerefTest SimpleCmpTest + SimpleDictionaryTest SimpleTest StrcmpTest StrncmpTest diff --git a/lib/Fuzzer/test/FuzzerUnittest.cpp b/lib/Fuzzer/test/FuzzerUnittest.cpp index f070e4f5924..1a88aef3e1e 100644 --- a/lib/Fuzzer/test/FuzzerUnittest.cpp +++ b/lib/Fuzzer/test/FuzzerUnittest.cpp @@ -105,8 +105,12 @@ void TestEraseByte(Mutator M, int NumIter) { EXPECT_EQ(FoundMask, 255); } -TEST(FuzzerMutate, EraseByte1) { TestEraseByte(&MutationDispatcher::Mutate_EraseByte, 100); } -TEST(FuzzerMutate, EraseByte2) { TestEraseByte(&MutationDispatcher::Mutate, 1000); } +TEST(FuzzerMutate, EraseByte1) { + TestEraseByte(&MutationDispatcher::Mutate_EraseByte, 100); +} +TEST(FuzzerMutate, EraseByte2) { + TestEraseByte(&MutationDispatcher::Mutate, 1000); +} void TestInsertByte(Mutator M, int NumIter) { FuzzerRandomLibc Rand(0); @@ -135,8 +139,12 @@ void TestInsertByte(Mutator M, int NumIter) { EXPECT_EQ(FoundMask, 255); } -TEST(FuzzerMutate, InsertByte1) { TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15); } -TEST(FuzzerMutate, InsertByte2) { TestInsertByte(&MutationDispatcher::Mutate, 1 << 17); } +TEST(FuzzerMutate, InsertByte1) { + TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15); +} +TEST(FuzzerMutate, InsertByte2) { + TestInsertByte(&MutationDispatcher::Mutate, 1 << 17); +} void TestChangeByte(Mutator M, int NumIter) { FuzzerRandomLibc Rand(0); @@ -165,8 +173,12 @@ void TestChangeByte(Mutator M, int NumIter) { EXPECT_EQ(FoundMask, 255); } -TEST(FuzzerMutate, ChangeByte1) { TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15); } -TEST(FuzzerMutate, ChangeByte2) { TestChangeByte(&MutationDispatcher::Mutate, 1 << 17); } +TEST(FuzzerMutate, ChangeByte1) { + TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15); +} +TEST(FuzzerMutate, ChangeByte2) { + TestChangeByte(&MutationDispatcher::Mutate, 1 << 17); +} void TestChangeBit(Mutator M, int NumIter) { FuzzerRandomLibc Rand(0); @@ -195,8 +207,12 @@ void TestChangeBit(Mutator M, int NumIter) { EXPECT_EQ(FoundMask, 255); } -TEST(FuzzerMutate, ChangeBit1) { TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16); } -TEST(FuzzerMutate, ChangeBit2) { TestChangeBit(&MutationDispatcher::Mutate, 1 << 18); } +TEST(FuzzerMutate, ChangeBit1) { + TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16); +} +TEST(FuzzerMutate, ChangeBit2) { + TestChangeBit(&MutationDispatcher::Mutate, 1 << 18); +} void TestShuffleBytes(Mutator M, int NumIter) { FuzzerRandomLibc Rand(0); @@ -219,8 +235,52 @@ void TestShuffleBytes(Mutator M, int NumIter) { EXPECT_EQ(FoundMask, 31); } -TEST(FuzzerMutate, ShuffleBytes1) { TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 15); } -TEST(FuzzerMutate, ShuffleBytes2) { TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 16); } +TEST(FuzzerMutate, ShuffleBytes1) { + TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 15); +} +TEST(FuzzerMutate, ShuffleBytes2) { + TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 16); +} + +void TestAddWordFromDictionary(Mutator M, int NumIter) { + FuzzerRandomLibc Rand(0); + MutationDispatcher MD(Rand); + uint8_t Word1[4] = {0xAA, 0xBB, 0xCC, 0xDD}; + uint8_t Word2[3] = {0xFF, 0xEE, 0xEF}; + MD.AddWordToDictionary(Word1, sizeof(Word1)); + MD.AddWordToDictionary(Word2, sizeof(Word2)); + int FoundMask = 0; + uint8_t CH0[7] = {0x00, 0x11, 0x22, 0xAA, 0xBB, 0xCC, 0xDD}; + uint8_t CH1[7] = {0x00, 0x11, 0xAA, 0xBB, 0xCC, 0xDD, 0x22}; + uint8_t CH2[7] = {0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0x11, 0x22}; + uint8_t CH3[7] = {0xAA, 0xBB, 0xCC, 0xDD, 0x00, 0x11, 0x22}; + uint8_t CH4[6] = {0x00, 0x11, 0x22, 0xFF, 0xEE, 0xEF}; + uint8_t CH5[6] = {0x00, 0x11, 0xFF, 0xEE, 0xEF, 0x22}; + uint8_t CH6[6] = {0x00, 0xFF, 0xEE, 0xEF, 0x11, 0x22}; + uint8_t CH7[6] = {0xFF, 0xEE, 0xEF, 0x00, 0x11, 0x22}; + for (int i = 0; i < NumIter; i++) { + uint8_t T[7] = {0x00, 0x11, 0x22}; + size_t NewSize = (MD.*M)(T, 3, 7); + if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0; + if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1; + if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2; + if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3; + if (NewSize == 6 && !memcmp(CH4, T, 6)) FoundMask |= 1 << 4; + if (NewSize == 6 && !memcmp(CH5, T, 6)) FoundMask |= 1 << 5; + if (NewSize == 6 && !memcmp(CH6, T, 6)) FoundMask |= 1 << 6; + if (NewSize == 6 && !memcmp(CH7, T, 6)) FoundMask |= 1 << 7; + } + EXPECT_EQ(FoundMask, 255); +} + +TEST(FuzzerMutate, AddWordFromDictionary1) { + TestAddWordFromDictionary(&MutationDispatcher::Mutate_AddWordFromDictionary, + 1 << 15); +} + +TEST(FuzzerMutate, AddWordFromDictionary2) { + TestAddWordFromDictionary(&MutationDispatcher::Mutate, 1 << 15); +} TEST(FuzzerDictionary, ParseOneDictionaryEntry) { Unit U; diff --git a/lib/Fuzzer/test/SimpleDictionaryTest.cpp b/lib/Fuzzer/test/SimpleDictionaryTest.cpp new file mode 100644 index 00000000000..20c80674366 --- /dev/null +++ b/lib/Fuzzer/test/SimpleDictionaryTest.cpp @@ -0,0 +1,25 @@ +// Simple test for a fuzzer. +// The fuzzer must find a string based on dictionary words: +// "Elvis" +// "Presley" +#include +#include +#include +#include +#include + +static volatile int Zero = 0; + +extern "C" void LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + const char *Expected = "ElvisPresley"; + if (Size < strlen(Expected)) return; + size_t Match = 0; + for (size_t i = 0; Expected[i]; i++) + if (Expected[i] + Zero == Data[i]) + Match++; + if (Match == strlen(Expected)) { + std::cout << "BINGO; Found the target, exiting\n"; + exit(1); + } +} + diff --git a/lib/Fuzzer/test/dict1.txt b/lib/Fuzzer/test/dict1.txt new file mode 100644 index 00000000000..520d0cc7b7d --- /dev/null +++ b/lib/Fuzzer/test/dict1.txt @@ -0,0 +1,4 @@ +# Dictionary for SimpleDictionaryTest + +a="Elvis" +b="Presley" diff --git a/lib/Fuzzer/test/fuzzer.test b/lib/Fuzzer/test/fuzzer.test index 3b8cf09a9a9..d5bd9a39230 100644 --- a/lib/Fuzzer/test/fuzzer.test +++ b/lib/Fuzzer/test/fuzzer.test @@ -37,3 +37,6 @@ RUN: LLVMFuzzer-StrcmpTest -seed=1 -runs=1000000 2>&1 | FileC RUN: not LLVMFuzzer-SwitchTest -use_traces=1 -seed=1 -runs=1000000 2>&1 | FileCheck %s RUN: LLVMFuzzer-SwitchTest -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 + +RUN: not LLVMFuzzer-SimpleDictionaryTest -dict=%S/dict1.txt -seed=1 -runs=1000000 2>&1 | FileCheck %s +RUN: LLVMFuzzer-SimpleDictionaryTest -seed=1 -runs=1000000 2>&1 | FileCheck %s --check-prefix=Done1000000 -- 2.34.1