Aaron Ballman | ef11698 | 2015-01-29 16:58:29 +0000 | [diff] [blame] | 1 | //===- FuzzerMutate.cpp - Mutate a test input -----------------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // Mutate a test input. |
| 10 | //===----------------------------------------------------------------------===// |
| 11 | |
Kostya Serebryany | f342459 | 2015-05-22 22:35:31 +0000 | [diff] [blame] | 12 | #include <cstring> |
| 13 | |
Kostya Serebryany | 556894f | 2016-09-21 02:05:39 +0000 | [diff] [blame] | 14 | #include "FuzzerCorpus.h" |
| 15 | #include "FuzzerDefs.h" |
| 16 | #include "FuzzerExtFunctions.h" |
Kostya Serebryany | 6f5a804 | 2016-09-21 01:50:50 +0000 | [diff] [blame] | 17 | #include "FuzzerMutate.h" |
Kostya Serebryany | 556894f | 2016-09-21 02:05:39 +0000 | [diff] [blame] | 18 | #include "FuzzerOptions.h" |
Kostya Serebryany | bf29ff2 | 2015-08-06 01:29:13 +0000 | [diff] [blame] | 19 | |
Aaron Ballman | ef11698 | 2015-01-29 16:58:29 +0000 | [diff] [blame] | 20 | namespace fuzzer { |
| 21 | |
Kostya Serebryany | 2f13f22 | 2016-01-21 01:52:14 +0000 | [diff] [blame] | 22 | const size_t Dictionary::kMaxDictSize; |
| 23 | |
Kostya Serebryany | 6f5a804 | 2016-09-21 01:50:50 +0000 | [diff] [blame] | 24 | static void PrintASCII(const Word &W, const char *PrintAfter) { |
| 25 | PrintASCII(W.data(), W.size(), PrintAfter); |
| 26 | } |
| 27 | |
Mike Aizatsky | f0b3e85 | 2016-06-23 20:44:48 +0000 | [diff] [blame] | 28 | MutationDispatcher::MutationDispatcher(Random &Rand, |
| 29 | const FuzzingOptions &Options) |
| 30 | : Rand(Rand), Options(Options) { |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 31 | DefaultMutators.insert( |
| 32 | DefaultMutators.begin(), |
| 33 | { |
Kostya Serebryany | dfbe59b | 2016-08-15 17:48:28 +0000 | [diff] [blame] | 34 | {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"}, |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 35 | {&MutationDispatcher::Mutate_InsertByte, "InsertByte"}, |
Kostya Serebryany | dfbe59b | 2016-08-15 17:48:28 +0000 | [diff] [blame] | 36 | {&MutationDispatcher::Mutate_InsertRepeatedBytes, |
| 37 | "InsertRepeatedBytes"}, |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 38 | {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"}, |
| 39 | {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"}, |
| 40 | {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"}, |
| 41 | {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"}, |
Kostya Serebryany | 0c537b1 | 2016-08-17 21:30:30 +0000 | [diff] [blame] | 42 | {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"}, |
Kostya Serebryany | a7398ba | 2016-08-17 18:10:42 +0000 | [diff] [blame] | 43 | {&MutationDispatcher::Mutate_CopyPart, "CopyPart"}, |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 44 | {&MutationDispatcher::Mutate_CrossOver, "CrossOver"}, |
| 45 | {&MutationDispatcher::Mutate_AddWordFromManualDictionary, |
| 46 | "AddFromManualDict"}, |
| 47 | {&MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary, |
| 48 | "AddFromTempAutoDict"}, |
| 49 | {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary, |
| 50 | "AddFromPersAutoDict"}, |
| 51 | }); |
| 52 | |
Dan Liew | 1873a49 | 2016-06-07 23:32:50 +0000 | [diff] [blame] | 53 | if (EF->LLVMFuzzerCustomMutator) |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 54 | Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"}); |
| 55 | else |
| 56 | Mutators = DefaultMutators; |
Mike Aizatsky | 41d6683 | 2016-06-07 20:22:15 +0000 | [diff] [blame] | 57 | |
Dan Liew | 1873a49 | 2016-06-07 23:32:50 +0000 | [diff] [blame] | 58 | if (EF->LLVMFuzzerCustomCrossOver) |
Mike Aizatsky | 41d6683 | 2016-06-07 20:22:15 +0000 | [diff] [blame] | 59 | Mutators.push_back( |
| 60 | {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"}); |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 61 | } |
Kostya Serebryany | 2319496 | 2016-02-13 03:46:26 +0000 | [diff] [blame] | 62 | |
Kostya Serebryany | a399221 | 2016-02-13 03:00:53 +0000 | [diff] [blame] | 63 | static char RandCh(Random &Rand) { |
Kostya Serebryany | 404c69f | 2015-07-24 01:06:40 +0000 | [diff] [blame] | 64 | if (Rand.RandBool()) return Rand(256); |
Kostya Serebryany | a7398ba | 2016-08-17 18:10:42 +0000 | [diff] [blame] | 65 | const char *Special = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00"; |
Kostya Serebryany | 404c69f | 2015-07-24 01:06:40 +0000 | [diff] [blame] | 66 | return Special[Rand(sizeof(Special) - 1)]; |
Aaron Ballman | ef11698 | 2015-01-29 16:58:29 +0000 | [diff] [blame] | 67 | } |
| 68 | |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 69 | size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size, |
| 70 | size_t MaxSize) { |
Dan Liew | 1873a49 | 2016-06-07 23:32:50 +0000 | [diff] [blame] | 71 | return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize, Rand.Rand()); |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 72 | } |
| 73 | |
Mike Aizatsky | 41d6683 | 2016-06-07 20:22:15 +0000 | [diff] [blame] | 74 | size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size, |
| 75 | size_t MaxSize) { |
| 76 | if (!Corpus || Corpus->size() < 2 || Size == 0) |
| 77 | return 0; |
| 78 | size_t Idx = Rand(Corpus->size()); |
| 79 | const Unit &Other = (*Corpus)[Idx]; |
| 80 | if (Other.empty()) |
| 81 | return 0; |
| 82 | MutateInPlaceHere.resize(MaxSize); |
| 83 | auto &U = MutateInPlaceHere; |
Dan Liew | 1873a49 | 2016-06-07 23:32:50 +0000 | [diff] [blame] | 84 | size_t NewSize = EF->LLVMFuzzerCustomCrossOver( |
Mike Aizatsky | 41d6683 | 2016-06-07 20:22:15 +0000 | [diff] [blame] | 85 | Data, Size, Other.data(), Other.size(), U.data(), U.size(), Rand.Rand()); |
| 86 | if (!NewSize) |
| 87 | return 0; |
| 88 | assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit"); |
| 89 | memcpy(Data, U.data(), NewSize); |
| 90 | return NewSize; |
| 91 | } |
| 92 | |
Kostya Serebryany | ec2dcb1 | 2015-09-03 21:24:19 +0000 | [diff] [blame] | 93 | size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size, |
| 94 | size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 95 | if (Size > MaxSize) return 0; |
Kostya Serebryany | bf29ff2 | 2015-08-06 01:29:13 +0000 | [diff] [blame] | 96 | assert(Size); |
Kostya Serebryany | 152ac7a | 2016-01-07 01:49:35 +0000 | [diff] [blame] | 97 | size_t ShuffleAmount = |
| 98 | Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size. |
Kostya Serebryany | bf29ff2 | 2015-08-06 01:29:13 +0000 | [diff] [blame] | 99 | size_t ShuffleStart = Rand(Size - ShuffleAmount); |
| 100 | assert(ShuffleStart + ShuffleAmount <= Size); |
| 101 | std::random_shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, |
| 102 | Rand); |
| 103 | return Size; |
| 104 | } |
| 105 | |
Kostya Serebryany | dfbe59b | 2016-08-15 17:48:28 +0000 | [diff] [blame] | 106 | size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size, |
| 107 | size_t MaxSize) { |
Kostya Serebryany | 8ce7424 | 2015-08-01 01:42:51 +0000 | [diff] [blame] | 108 | assert(Size); |
Kostya Serebryany | b2e9897 | 2015-09-04 00:40:29 +0000 | [diff] [blame] | 109 | if (Size == 1) return 0; |
Kostya Serebryany | dfbe59b | 2016-08-15 17:48:28 +0000 | [diff] [blame] | 110 | size_t N = Rand(Size / 2) + 1; |
| 111 | assert(N < Size); |
| 112 | size_t Idx = Rand(Size - N + 1); |
| 113 | // Erase Data[Idx:Idx+N]. |
| 114 | memmove(Data + Idx, Data + Idx + N, Size - Idx - N); |
| 115 | // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx); |
| 116 | return Size - N; |
Kostya Serebryany | 8ce7424 | 2015-08-01 01:42:51 +0000 | [diff] [blame] | 117 | } |
| 118 | |
Kostya Serebryany | ec2dcb1 | 2015-09-03 21:24:19 +0000 | [diff] [blame] | 119 | size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size, |
| 120 | size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 121 | if (Size >= MaxSize) return 0; |
Kostya Serebryany | 86a5fba | 2015-08-01 02:23:06 +0000 | [diff] [blame] | 122 | size_t Idx = Rand(Size + 1); |
| 123 | // Insert new value at Data[Idx]. |
| 124 | memmove(Data + Idx + 1, Data + Idx, Size - Idx); |
| 125 | Data[Idx] = RandCh(Rand); |
| 126 | return Size + 1; |
| 127 | } |
| 128 | |
Kostya Serebryany | dfbe59b | 2016-08-15 17:48:28 +0000 | [diff] [blame] | 129 | size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data, |
| 130 | size_t Size, |
| 131 | size_t MaxSize) { |
| 132 | const size_t kMinBytesToInsert = 3; |
| 133 | if (Size + kMinBytesToInsert >= MaxSize) return 0; |
| 134 | size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128); |
| 135 | size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert; |
| 136 | assert(Size + N <= MaxSize && N); |
| 137 | size_t Idx = Rand(Size + 1); |
| 138 | // Insert new values at Data[Idx]. |
| 139 | memmove(Data + Idx + N, Data + Idx, Size - Idx); |
Kostya Serebryany | e72774d | 2016-08-17 21:50:54 +0000 | [diff] [blame] | 140 | // Give preference to 0x00 and 0xff. |
| 141 | uint8_t Byte = Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255); |
Kostya Serebryany | dfbe59b | 2016-08-15 17:48:28 +0000 | [diff] [blame] | 142 | for (size_t i = 0; i < N; i++) |
| 143 | Data[Idx + i] = Byte; |
| 144 | return Size + N; |
| 145 | } |
| 146 | |
Kostya Serebryany | ec2dcb1 | 2015-09-03 21:24:19 +0000 | [diff] [blame] | 147 | size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size, |
| 148 | size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 149 | if (Size > MaxSize) return 0; |
Kostya Serebryany | 86a5fba | 2015-08-01 02:23:06 +0000 | [diff] [blame] | 150 | size_t Idx = Rand(Size); |
| 151 | Data[Idx] = RandCh(Rand); |
| 152 | return Size; |
| 153 | } |
| 154 | |
Kostya Serebryany | ec2dcb1 | 2015-09-03 21:24:19 +0000 | [diff] [blame] | 155 | size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size, |
| 156 | size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 157 | if (Size > MaxSize) return 0; |
Kostya Serebryany | 86a5fba | 2015-08-01 02:23:06 +0000 | [diff] [blame] | 158 | size_t Idx = Rand(Size); |
Kostya Serebryany | a7398ba | 2016-08-17 18:10:42 +0000 | [diff] [blame] | 159 | Data[Idx] ^= 1 << Rand(8); |
Kostya Serebryany | 86a5fba | 2015-08-01 02:23:06 +0000 | [diff] [blame] | 160 | return Size; |
| 161 | } |
| 162 | |
Kostya Serebryany | 152ac7a | 2016-01-07 01:49:35 +0000 | [diff] [blame] | 163 | size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data, |
| 164 | size_t Size, |
| 165 | size_t MaxSize) { |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 166 | return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize); |
Kostya Serebryany | 152ac7a | 2016-01-07 01:49:35 +0000 | [diff] [blame] | 167 | } |
| 168 | |
Kostya Serebryany | 4b35874 | 2016-01-14 02:36:44 +0000 | [diff] [blame] | 169 | size_t MutationDispatcher::Mutate_AddWordFromTemporaryAutoDictionary( |
| 170 | uint8_t *Data, size_t Size, size_t MaxSize) { |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 171 | return AddWordFromDictionary(TempAutoDictionary, Data, Size, MaxSize); |
Kostya Serebryany | 4b35874 | 2016-01-14 02:36:44 +0000 | [diff] [blame] | 172 | } |
| 173 | |
| 174 | size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary( |
| 175 | uint8_t *Data, size_t Size, size_t MaxSize) { |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 176 | return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize); |
Kostya Serebryany | 152ac7a | 2016-01-07 01:49:35 +0000 | [diff] [blame] | 177 | } |
| 178 | |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 179 | size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data, |
| 180 | size_t Size, size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 181 | if (Size > MaxSize) return 0; |
Kostya Serebryany | b2e9897 | 2015-09-04 00:40:29 +0000 | [diff] [blame] | 182 | if (D.empty()) return 0; |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 183 | DictionaryEntry &DE = D[Rand(D.size())]; |
| 184 | const Word &W = DE.GetW(); |
| 185 | bool UsePositionHint = DE.HasPositionHint() && |
| 186 | DE.GetPositionHint() + W.size() < Size && Rand.RandBool(); |
Kostya Serebryany | 476f0ce | 2016-01-16 03:53:32 +0000 | [diff] [blame] | 187 | if (Rand.RandBool()) { // Insert W. |
| 188 | if (Size + W.size() > MaxSize) return 0; |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 189 | size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1); |
Kostya Serebryany | 476f0ce | 2016-01-16 03:53:32 +0000 | [diff] [blame] | 190 | memmove(Data + Idx + W.size(), Data + Idx, Size - Idx); |
| 191 | memcpy(Data + Idx, W.data(), W.size()); |
| 192 | Size += W.size(); |
| 193 | } else { // Overwrite some bytes with W. |
| 194 | if (W.size() > Size) return 0; |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 195 | size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size - W.size()); |
Kostya Serebryany | 476f0ce | 2016-01-16 03:53:32 +0000 | [diff] [blame] | 196 | memcpy(Data + Idx, W.data(), W.size()); |
Kostya Serebryany | 80eb76a | 2016-01-06 02:13:04 +0000 | [diff] [blame] | 197 | } |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 198 | DE.IncUseCount(); |
| 199 | CurrentDictionaryEntrySequence.push_back(&DE); |
Kostya Serebryany | 4174005 | 2016-01-12 02:36:59 +0000 | [diff] [blame] | 200 | return Size; |
Kostya Serebryany | 7d21166 | 2015-09-04 00:12:11 +0000 | [diff] [blame] | 201 | } |
| 202 | |
Kostya Serebryany | a7398ba | 2016-08-17 18:10:42 +0000 | [diff] [blame] | 203 | // Overwrites part of To[0,ToSize) with a part of From[0,FromSize). |
| 204 | // Returns ToSize. |
| 205 | size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize, |
| 206 | uint8_t *To, size_t ToSize) { |
| 207 | // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize). |
| 208 | size_t ToBeg = Rand(ToSize); |
| 209 | size_t CopySize = Rand(ToSize - ToBeg) + 1; |
| 210 | assert(ToBeg + CopySize <= ToSize); |
| 211 | CopySize = std::min(CopySize, FromSize); |
| 212 | size_t FromBeg = Rand(FromSize - CopySize + 1); |
| 213 | assert(FromBeg + CopySize <= FromSize); |
| 214 | memmove(To + ToBeg, From + FromBeg, CopySize); |
| 215 | return ToSize; |
| 216 | } |
| 217 | |
| 218 | // Inserts part of From[0,ToSize) into To. |
| 219 | // Returns new size of To on success or 0 on failure. |
| 220 | size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize, |
| 221 | uint8_t *To, size_t ToSize, |
| 222 | size_t MaxToSize) { |
| 223 | if (ToSize >= MaxToSize) return 0; |
| 224 | size_t AvailableSpace = MaxToSize - ToSize; |
| 225 | size_t MaxCopySize = std::min(AvailableSpace, FromSize); |
| 226 | size_t CopySize = Rand(MaxCopySize) + 1; |
| 227 | size_t FromBeg = Rand(FromSize - CopySize + 1); |
| 228 | assert(FromBeg + CopySize <= FromSize); |
| 229 | size_t ToInsertPos = Rand(ToSize + 1); |
| 230 | assert(ToInsertPos + CopySize <= MaxToSize); |
| 231 | size_t TailSize = ToSize - ToInsertPos; |
| 232 | if (To == From) { |
| 233 | MutateInPlaceHere.resize(MaxToSize); |
| 234 | memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize); |
| 235 | memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); |
| 236 | memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize); |
| 237 | } else { |
| 238 | memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize); |
| 239 | memmove(To + ToInsertPos, From + FromBeg, CopySize); |
| 240 | } |
| 241 | return ToSize + CopySize; |
| 242 | } |
| 243 | |
| 244 | size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size, |
| 245 | size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 246 | if (Size > MaxSize) return 0; |
Kostya Serebryany | a7398ba | 2016-08-17 18:10:42 +0000 | [diff] [blame] | 247 | if (Rand.RandBool()) |
| 248 | return CopyPartOf(Data, Size, Data, Size); |
| 249 | else |
| 250 | return InsertPartOf(Data, Size, Data, Size, MaxSize); |
| 251 | } |
| 252 | |
Kostya Serebryany | 25425ad | 2015-09-08 17:19:31 +0000 | [diff] [blame] | 253 | size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, |
| 254 | size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 255 | if (Size > MaxSize) return 0; |
Kostya Serebryany | 25425ad | 2015-09-08 17:19:31 +0000 | [diff] [blame] | 256 | size_t B = Rand(Size); |
| 257 | while (B < Size && !isdigit(Data[B])) B++; |
| 258 | if (B == Size) return 0; |
| 259 | size_t E = B; |
| 260 | while (E < Size && isdigit(Data[E])) E++; |
| 261 | assert(B < E); |
| 262 | // now we have digits in [B, E). |
| 263 | // strtol and friends don't accept non-zero-teminated data, parse it manually. |
| 264 | uint64_t Val = Data[B] - '0'; |
| 265 | for (size_t i = B + 1; i < E; i++) |
| 266 | Val = Val * 10 + Data[i] - '0'; |
| 267 | |
| 268 | // Mutate the integer value. |
| 269 | switch(Rand(5)) { |
| 270 | case 0: Val++; break; |
| 271 | case 1: Val--; break; |
| 272 | case 2: Val /= 2; break; |
| 273 | case 3: Val *= 2; break; |
| 274 | case 4: Val = Rand(Val * Val); break; |
| 275 | default: assert(0); |
| 276 | } |
| 277 | // Just replace the bytes with the new ones, don't bother moving bytes. |
| 278 | for (size_t i = B; i < E; i++) { |
| 279 | size_t Idx = E + B - i - 1; |
| 280 | assert(Idx >= B && Idx < E); |
| 281 | Data[Idx] = (Val % 10) + '0'; |
| 282 | Val /= 10; |
| 283 | } |
| 284 | return Size; |
| 285 | } |
| 286 | |
Kostya Serebryany | 0c537b1 | 2016-08-17 21:30:30 +0000 | [diff] [blame] | 287 | uint8_t Bswap(uint8_t x) { return x; } |
| 288 | uint16_t Bswap(uint16_t x) { return __builtin_bswap16(x); } |
| 289 | uint32_t Bswap(uint32_t x) { return __builtin_bswap32(x); } |
| 290 | uint64_t Bswap(uint64_t x) { return __builtin_bswap64(x); } |
| 291 | |
| 292 | template<class T> |
| 293 | size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) { |
| 294 | if (Size < sizeof(T)) return 0; |
| 295 | size_t Off = Rand(Size - sizeof(T) + 1); |
| 296 | assert(Off + sizeof(T) <= Size); |
| 297 | T Val; |
| 298 | memcpy(&Val, Data + Off, sizeof(Val)); |
| 299 | T Add = Rand(21); |
| 300 | Add -= 10; |
| 301 | if (Rand.RandBool()) |
| 302 | Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes. |
| 303 | else |
| 304 | Val = Val + Add; // Add assuming current endiannes. |
| 305 | if (Add == 0 || Rand.RandBool()) // Maybe negate. |
| 306 | Val = -Val; |
| 307 | memcpy(Data + Off, &Val, sizeof(Val)); |
| 308 | return Size; |
| 309 | } |
| 310 | |
| 311 | size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data, |
| 312 | size_t Size, |
| 313 | size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 314 | if (Size > MaxSize) return 0; |
Kostya Serebryany | 0c537b1 | 2016-08-17 21:30:30 +0000 | [diff] [blame] | 315 | switch (Rand(4)) { |
| 316 | case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand); |
| 317 | case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand); |
| 318 | case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand); |
| 319 | case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand); |
| 320 | default: assert(0); |
| 321 | } |
Kostya Serebryany | a533e51 | 2016-08-19 20:57:09 +0000 | [diff] [blame] | 322 | return 0; |
Kostya Serebryany | 0c537b1 | 2016-08-17 21:30:30 +0000 | [diff] [blame] | 323 | } |
| 324 | |
Kostya Serebryany | 27ab2d7 | 2015-12-19 02:49:09 +0000 | [diff] [blame] | 325 | size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size, |
| 326 | size_t MaxSize) { |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 327 | if (Size > MaxSize) return 0; |
Kostya Serebryany | 27ab2d7 | 2015-12-19 02:49:09 +0000 | [diff] [blame] | 328 | if (!Corpus || Corpus->size() < 2 || Size == 0) return 0; |
| 329 | size_t Idx = Rand(Corpus->size()); |
Kostya Serebryany | a7398ba | 2016-08-17 18:10:42 +0000 | [diff] [blame] | 330 | const Unit &O = (*Corpus)[Idx]; |
| 331 | if (O.empty()) return 0; |
Kostya Serebryany | 8a5bef0 | 2016-02-13 17:56:51 +0000 | [diff] [blame] | 332 | MutateInPlaceHere.resize(MaxSize); |
| 333 | auto &U = MutateInPlaceHere; |
Kostya Serebryany | a533e51 | 2016-08-19 20:57:09 +0000 | [diff] [blame] | 334 | size_t NewSize = 0; |
Kostya Serebryany | a7398ba | 2016-08-17 18:10:42 +0000 | [diff] [blame] | 335 | switch(Rand(3)) { |
| 336 | case 0: |
| 337 | NewSize = CrossOver(Data, Size, O.data(), O.size(), U.data(), U.size()); |
| 338 | break; |
| 339 | case 1: |
| 340 | NewSize = InsertPartOf(O.data(), O.size(), U.data(), U.size(), MaxSize); |
| 341 | if (NewSize) |
| 342 | break; |
Kostya Serebryany | 0c537b1 | 2016-08-17 21:30:30 +0000 | [diff] [blame] | 343 | // LLVM_FALLTHROUGH; |
Kostya Serebryany | a7398ba | 2016-08-17 18:10:42 +0000 | [diff] [blame] | 344 | case 2: |
| 345 | NewSize = CopyPartOf(O.data(), O.size(), U.data(), U.size()); |
| 346 | break; |
| 347 | default: assert(0); |
| 348 | } |
Kostya Serebryany | 27ab2d7 | 2015-12-19 02:49:09 +0000 | [diff] [blame] | 349 | assert(NewSize > 0 && "CrossOver returned empty unit"); |
| 350 | assert(NewSize <= MaxSize && "CrossOver returned overisized unit"); |
| 351 | memcpy(Data, U.data(), NewSize); |
| 352 | return NewSize; |
| 353 | } |
| 354 | |
Kostya Serebryany | 14c5028 | 2015-12-19 01:09:49 +0000 | [diff] [blame] | 355 | void MutationDispatcher::StartMutationSequence() { |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 356 | CurrentMutatorSequence.clear(); |
| 357 | CurrentDictionaryEntrySequence.clear(); |
Kostya Serebryany | 14c5028 | 2015-12-19 01:09:49 +0000 | [diff] [blame] | 358 | } |
| 359 | |
Kostya Serebryany | 4b35874 | 2016-01-14 02:36:44 +0000 | [diff] [blame] | 360 | // Copy successful dictionary entries to PersistentAutoDictionary. |
| 361 | void MutationDispatcher::RecordSuccessfulMutationSequence() { |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 362 | for (auto DE : CurrentDictionaryEntrySequence) { |
| 363 | // PersistentAutoDictionary.AddWithSuccessCountOne(DE); |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 364 | DE->IncSuccessCount(); |
Kostya Serebryany | 4b35874 | 2016-01-14 02:36:44 +0000 | [diff] [blame] | 365 | // Linear search is fine here as this happens seldom. |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 366 | if (!PersistentAutoDictionary.ContainsWord(DE->GetW())) |
| 367 | PersistentAutoDictionary.push_back({DE->GetW(), 1}); |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 368 | } |
Kostya Serebryany | 4b35874 | 2016-01-14 02:36:44 +0000 | [diff] [blame] | 369 | } |
| 370 | |
| 371 | void MutationDispatcher::PrintRecommendedDictionary() { |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 372 | std::vector<DictionaryEntry> V; |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 373 | for (auto &DE : PersistentAutoDictionary) |
| 374 | if (!ManualDictionary.ContainsWord(DE.GetW())) |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 375 | V.push_back(DE); |
Kostya Serebryany | 4b35874 | 2016-01-14 02:36:44 +0000 | [diff] [blame] | 376 | if (V.empty()) return; |
| 377 | Printf("###### Recommended dictionary. ######\n"); |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 378 | for (auto &DE: V) { |
Kostya Serebryany | 4b35874 | 2016-01-14 02:36:44 +0000 | [diff] [blame] | 379 | Printf("\""); |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 380 | PrintASCII(DE.GetW(), "\""); |
| 381 | Printf(" # Uses: %zd\n", DE.GetUseCount()); |
Kostya Serebryany | 4b35874 | 2016-01-14 02:36:44 +0000 | [diff] [blame] | 382 | } |
| 383 | Printf("###### End of recommended dictionary. ######\n"); |
| 384 | } |
| 385 | |
Kostya Serebryany | 14c5028 | 2015-12-19 01:09:49 +0000 | [diff] [blame] | 386 | void MutationDispatcher::PrintMutationSequence() { |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 387 | Printf("MS: %zd ", CurrentMutatorSequence.size()); |
| 388 | for (auto M : CurrentMutatorSequence) |
Kostya Serebryany | 14c5028 | 2015-12-19 01:09:49 +0000 | [diff] [blame] | 389 | Printf("%s-", M.Name); |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 390 | if (!CurrentDictionaryEntrySequence.empty()) { |
Kostya Serebryany | 4174005 | 2016-01-12 02:36:59 +0000 | [diff] [blame] | 391 | Printf(" DE: "); |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 392 | for (auto DE : CurrentDictionaryEntrySequence) { |
Kostya Serebryany | 4174005 | 2016-01-12 02:36:59 +0000 | [diff] [blame] | 393 | Printf("\""); |
Kostya Serebryany | 160dcba | 2016-01-22 23:55:14 +0000 | [diff] [blame] | 394 | PrintASCII(DE->GetW(), "\"-"); |
Kostya Serebryany | 4174005 | 2016-01-12 02:36:59 +0000 | [diff] [blame] | 395 | } |
| 396 | } |
Kostya Serebryany | 14c5028 | 2015-12-19 01:09:49 +0000 | [diff] [blame] | 397 | } |
| 398 | |
Kostya Serebryany | ec2dcb1 | 2015-09-03 21:24:19 +0000 | [diff] [blame] | 399 | size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) { |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 400 | return MutateImpl(Data, Size, MaxSize, Mutators); |
| 401 | } |
| 402 | |
| 403 | size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size, |
| 404 | size_t MaxSize) { |
| 405 | return MutateImpl(Data, Size, MaxSize, DefaultMutators); |
| 406 | } |
| 407 | |
| 408 | // Mutates Data in place, returns new size. |
| 409 | size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size, |
| 410 | size_t MaxSize, |
| 411 | const std::vector<Mutator> &Mutators) { |
Kostya Serebryany | f342459 | 2015-05-22 22:35:31 +0000 | [diff] [blame] | 412 | assert(MaxSize > 0); |
Kostya Serebryany | f342459 | 2015-05-22 22:35:31 +0000 | [diff] [blame] | 413 | if (Size == 0) { |
| 414 | for (size_t i = 0; i < MaxSize; i++) |
Kostya Serebryany | 404c69f | 2015-07-24 01:06:40 +0000 | [diff] [blame] | 415 | Data[i] = RandCh(Rand); |
Mike Aizatsky | f0b3e85 | 2016-06-23 20:44:48 +0000 | [diff] [blame] | 416 | if (Options.OnlyASCII) |
| 417 | ToASCII(Data, MaxSize); |
Kostya Serebryany | f342459 | 2015-05-22 22:35:31 +0000 | [diff] [blame] | 418 | return MaxSize; |
Kostya Serebryany | 5b266a8 | 2015-02-04 19:10:20 +0000 | [diff] [blame] | 419 | } |
Kostya Serebryany | f342459 | 2015-05-22 22:35:31 +0000 | [diff] [blame] | 420 | assert(Size > 0); |
Kostya Serebryany | b2e9897 | 2015-09-04 00:40:29 +0000 | [diff] [blame] | 421 | // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize), |
| 422 | // in which case they will return 0. |
| 423 | // Try several times before returning un-mutated data. |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 424 | for (int Iter = 0; Iter < 100; Iter++) { |
Mike Aizatsky | 70fd3e4 | 2016-06-03 21:34:29 +0000 | [diff] [blame] | 425 | auto M = Mutators[Rand(Mutators.size())]; |
Kostya Serebryany | 14c5028 | 2015-12-19 01:09:49 +0000 | [diff] [blame] | 426 | size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize); |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 427 | if (NewSize && NewSize <= MaxSize) { |
Mike Aizatsky | f0b3e85 | 2016-06-23 20:44:48 +0000 | [diff] [blame] | 428 | if (Options.OnlyASCII) |
| 429 | ToASCII(Data, NewSize); |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 430 | CurrentMutatorSequence.push_back(M); |
Kostya Serebryany | 14c5028 | 2015-12-19 01:09:49 +0000 | [diff] [blame] | 431 | return NewSize; |
| 432 | } |
Kostya Serebryany | b2e9897 | 2015-09-04 00:40:29 +0000 | [diff] [blame] | 433 | } |
Kostya Serebryany | 624f59f | 2016-09-22 01:34:58 +0000 | [diff] [blame^] | 434 | return std::min(Size, MaxSize); |
Aaron Ballman | ef11698 | 2015-01-29 16:58:29 +0000 | [diff] [blame] | 435 | } |
| 436 | |
Kostya Serebryany | 476f0ce | 2016-01-16 03:53:32 +0000 | [diff] [blame] | 437 | void MutationDispatcher::AddWordToManualDictionary(const Word &W) { |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 438 | ManualDictionary.push_back( |
Kostya Serebryany | 476f0ce | 2016-01-16 03:53:32 +0000 | [diff] [blame] | 439 | {W, std::numeric_limits<size_t>::max()}); |
Kostya Serebryany | 152ac7a | 2016-01-07 01:49:35 +0000 | [diff] [blame] | 440 | } |
| 441 | |
Kostya Serebryany | c135b55 | 2016-07-15 23:27:19 +0000 | [diff] [blame] | 442 | void MutationDispatcher::AddWordToAutoDictionary(DictionaryEntry DE) { |
Kostya Serebryany | b65805a | 2016-01-09 03:08:58 +0000 | [diff] [blame] | 443 | static const size_t kMaxAutoDictSize = 1 << 14; |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 444 | if (TempAutoDictionary.size() >= kMaxAutoDictSize) return; |
Kostya Serebryany | c135b55 | 2016-07-15 23:27:19 +0000 | [diff] [blame] | 445 | TempAutoDictionary.push_back(DE); |
Kostya Serebryany | 7d21166 | 2015-09-04 00:12:11 +0000 | [diff] [blame] | 446 | } |
| 447 | |
Kostya Serebryany | b65805a | 2016-01-09 03:08:58 +0000 | [diff] [blame] | 448 | void MutationDispatcher::ClearAutoDictionary() { |
Kostya Serebryany | 292cf03 | 2016-02-13 03:37:24 +0000 | [diff] [blame] | 449 | TempAutoDictionary.clear(); |
Kostya Serebryany | b65805a | 2016-01-09 03:08:58 +0000 | [diff] [blame] | 450 | } |
| 451 | |
Aaron Ballman | ef11698 | 2015-01-29 16:58:29 +0000 | [diff] [blame] | 452 | } // namespace fuzzer |