1 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
2 // See https://llvm.org/LICENSE.txt for license information.
3 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
4 
5 // Avoid ODR violations (LibFuzzer is built without ASan and this test is built
6 // with ASan) involving C++ standard library types when using libcxx.
7 #define _LIBCPP_HAS_NO_ASAN
8 
9 // Do not attempt to use LLVM ostream etc from gtest.
10 #define GTEST_NO_LLVM_SUPPORT 1
11 
12 #include "FuzzerCorpus.h"
13 #include "FuzzerDictionary.h"
14 #include "FuzzerInternal.h"
15 #include "FuzzerMerge.h"
16 #include "FuzzerMutate.h"
17 #include "FuzzerRandom.h"
18 #include "FuzzerTracePC.h"
19 #include "gtest/gtest.h"
20 #include <memory>
21 #include <set>
22 #include <sstream>
23 
24 using namespace fuzzer;
25 
26 // For now, have LLVMFuzzerTestOneInput just to make it link.
27 // Later we may want to make unittests that actually call
28 // LLVMFuzzerTestOneInput.
29 extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
30   abort();
31 }
32 
33 TEST(Fuzzer, Basename) {
34   EXPECT_EQ(Basename("foo/bar"), "bar");
35   EXPECT_EQ(Basename("bar"), "bar");
36   EXPECT_EQ(Basename("/bar"), "bar");
37   EXPECT_EQ(Basename("foo/x"), "x");
38   EXPECT_EQ(Basename("foo/"), "");
39 #if LIBFUZZER_WINDOWS
40   EXPECT_EQ(Basename("foo\\bar"), "bar");
41   EXPECT_EQ(Basename("foo\\bar/baz"), "baz");
42   EXPECT_EQ(Basename("\\bar"), "bar");
43   EXPECT_EQ(Basename("foo\\x"), "x");
44   EXPECT_EQ(Basename("foo\\"), "");
45 #endif
46 }
47 
48 TEST(Fuzzer, CrossOver) {
49   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
50   fuzzer::EF = t.get();
51   Random Rand(0);
52   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
53   Unit A({0, 1, 2}), B({5, 6, 7});
54   Unit C;
55   Unit Expected[] = {
56        { 0 },
57        { 0, 1 },
58        { 0, 5 },
59        { 0, 1, 2 },
60        { 0, 1, 5 },
61        { 0, 5, 1 },
62        { 0, 5, 6 },
63        { 0, 1, 2, 5 },
64        { 0, 1, 5, 2 },
65        { 0, 1, 5, 6 },
66        { 0, 5, 1, 2 },
67        { 0, 5, 1, 6 },
68        { 0, 5, 6, 1 },
69        { 0, 5, 6, 7 },
70        { 0, 1, 2, 5, 6 },
71        { 0, 1, 5, 2, 6 },
72        { 0, 1, 5, 6, 2 },
73        { 0, 1, 5, 6, 7 },
74        { 0, 5, 1, 2, 6 },
75        { 0, 5, 1, 6, 2 },
76        { 0, 5, 1, 6, 7 },
77        { 0, 5, 6, 1, 2 },
78        { 0, 5, 6, 1, 7 },
79        { 0, 5, 6, 7, 1 },
80        { 0, 1, 2, 5, 6, 7 },
81        { 0, 1, 5, 2, 6, 7 },
82        { 0, 1, 5, 6, 2, 7 },
83        { 0, 1, 5, 6, 7, 2 },
84        { 0, 5, 1, 2, 6, 7 },
85        { 0, 5, 1, 6, 2, 7 },
86        { 0, 5, 1, 6, 7, 2 },
87        { 0, 5, 6, 1, 2, 7 },
88        { 0, 5, 6, 1, 7, 2 },
89        { 0, 5, 6, 7, 1, 2 }
90   };
91   for (size_t Len = 1; Len < 8; Len++) {
92     std::set<Unit> FoundUnits, ExpectedUnitsWitThisLength;
93     for (int Iter = 0; Iter < 3000; Iter++) {
94       C.resize(Len);
95       size_t NewSize = MD->CrossOver(A.data(), A.size(), B.data(), B.size(),
96                                      C.data(), C.size());
97       C.resize(NewSize);
98       FoundUnits.insert(C);
99     }
100     for (const Unit &U : Expected)
101       if (U.size() <= Len)
102         ExpectedUnitsWitThisLength.insert(U);
103     EXPECT_EQ(ExpectedUnitsWitThisLength, FoundUnits);
104   }
105 }
106 
107 TEST(Fuzzer, Hash) {
108   uint8_t A[] = {'a', 'b', 'c'};
109   fuzzer::Unit U(A, A + sizeof(A));
110   EXPECT_EQ("a9993e364706816aba3e25717850c26c9cd0d89d", fuzzer::Hash(U));
111   U.push_back('d');
112   EXPECT_EQ("81fe8bfe87576c3ecb22426f8e57847382917acf", fuzzer::Hash(U));
113 }
114 
115 typedef size_t (MutationDispatcher::*Mutator)(uint8_t *Data, size_t Size,
116                                               size_t MaxSize);
117 
118 void TestEraseBytes(Mutator M, int NumIter) {
119   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
120   fuzzer::EF = t.get();
121   uint8_t REM0[8] = {0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
122   uint8_t REM1[8] = {0x00, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
123   uint8_t REM2[8] = {0x00, 0x11, 0x33, 0x44, 0x55, 0x66, 0x77};
124   uint8_t REM3[8] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x77};
125   uint8_t REM4[8] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x66, 0x77};
126   uint8_t REM5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x66, 0x77};
127   uint8_t REM6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x77};
128   uint8_t REM7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
129 
130   uint8_t REM8[6] = {0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
131   uint8_t REM9[6] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55};
132   uint8_t REM10[6] = {0x00, 0x11, 0x22, 0x55, 0x66, 0x77};
133 
134   uint8_t REM11[5] = {0x33, 0x44, 0x55, 0x66, 0x77};
135   uint8_t REM12[5] = {0x00, 0x11, 0x22, 0x33, 0x44};
136   uint8_t REM13[5] = {0x00, 0x44, 0x55, 0x66, 0x77};
137 
138 
139   Random Rand(0);
140   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
141   int FoundMask = 0;
142   for (int i = 0; i < NumIter; i++) {
143     uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
144     size_t NewSize = (*MD.*M)(T, sizeof(T), sizeof(T));
145     if (NewSize == 7 && !memcmp(REM0, T, 7)) FoundMask |= 1 << 0;
146     if (NewSize == 7 && !memcmp(REM1, T, 7)) FoundMask |= 1 << 1;
147     if (NewSize == 7 && !memcmp(REM2, T, 7)) FoundMask |= 1 << 2;
148     if (NewSize == 7 && !memcmp(REM3, T, 7)) FoundMask |= 1 << 3;
149     if (NewSize == 7 && !memcmp(REM4, T, 7)) FoundMask |= 1 << 4;
150     if (NewSize == 7 && !memcmp(REM5, T, 7)) FoundMask |= 1 << 5;
151     if (NewSize == 7 && !memcmp(REM6, T, 7)) FoundMask |= 1 << 6;
152     if (NewSize == 7 && !memcmp(REM7, T, 7)) FoundMask |= 1 << 7;
153 
154     if (NewSize == 6 && !memcmp(REM8, T, 6)) FoundMask |= 1 << 8;
155     if (NewSize == 6 && !memcmp(REM9, T, 6)) FoundMask |= 1 << 9;
156     if (NewSize == 6 && !memcmp(REM10, T, 6)) FoundMask |= 1 << 10;
157 
158     if (NewSize == 5 && !memcmp(REM11, T, 5)) FoundMask |= 1 << 11;
159     if (NewSize == 5 && !memcmp(REM12, T, 5)) FoundMask |= 1 << 12;
160     if (NewSize == 5 && !memcmp(REM13, T, 5)) FoundMask |= 1 << 13;
161   }
162   EXPECT_EQ(FoundMask, (1 << 14) - 1);
163 }
164 
165 TEST(FuzzerMutate, EraseBytes1) {
166   TestEraseBytes(&MutationDispatcher::Mutate_EraseBytes, 200);
167 }
168 TEST(FuzzerMutate, EraseBytes2) {
169   TestEraseBytes(&MutationDispatcher::Mutate, 2000);
170 }
171 
172 void TestInsertByte(Mutator M, int NumIter) {
173   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
174   fuzzer::EF = t.get();
175   Random Rand(0);
176   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
177   int FoundMask = 0;
178   uint8_t INS0[8] = {0xF1, 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
179   uint8_t INS1[8] = {0x00, 0xF2, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
180   uint8_t INS2[8] = {0x00, 0x11, 0xF3, 0x22, 0x33, 0x44, 0x55, 0x66};
181   uint8_t INS3[8] = {0x00, 0x11, 0x22, 0xF4, 0x33, 0x44, 0x55, 0x66};
182   uint8_t INS4[8] = {0x00, 0x11, 0x22, 0x33, 0xF5, 0x44, 0x55, 0x66};
183   uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF6, 0x55, 0x66};
184   uint8_t INS6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF7, 0x66};
185   uint8_t INS7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF8};
186   for (int i = 0; i < NumIter; i++) {
187     uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
188     size_t NewSize = (*MD.*M)(T, 7, 8);
189     if (NewSize == 8 && !memcmp(INS0, T, 8)) FoundMask |= 1 << 0;
190     if (NewSize == 8 && !memcmp(INS1, T, 8)) FoundMask |= 1 << 1;
191     if (NewSize == 8 && !memcmp(INS2, T, 8)) FoundMask |= 1 << 2;
192     if (NewSize == 8 && !memcmp(INS3, T, 8)) FoundMask |= 1 << 3;
193     if (NewSize == 8 && !memcmp(INS4, T, 8)) FoundMask |= 1 << 4;
194     if (NewSize == 8 && !memcmp(INS5, T, 8)) FoundMask |= 1 << 5;
195     if (NewSize == 8 && !memcmp(INS6, T, 8)) FoundMask |= 1 << 6;
196     if (NewSize == 8 && !memcmp(INS7, T, 8)) FoundMask |= 1 << 7;
197   }
198   EXPECT_EQ(FoundMask, 255);
199 }
200 
201 TEST(FuzzerMutate, InsertByte1) {
202   TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15);
203 }
204 TEST(FuzzerMutate, InsertByte2) {
205   TestInsertByte(&MutationDispatcher::Mutate, 1 << 17);
206 }
207 
208 void TestInsertRepeatedBytes(Mutator M, int NumIter) {
209   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
210   fuzzer::EF = t.get();
211   Random Rand(0);
212   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
213   int FoundMask = 0;
214   uint8_t INS0[7] = {0x00, 0x11, 0x22, 0x33, 'a', 'a', 'a'};
215   uint8_t INS1[7] = {0x00, 0x11, 0x22, 'a', 'a', 'a', 0x33};
216   uint8_t INS2[7] = {0x00, 0x11, 'a', 'a', 'a', 0x22, 0x33};
217   uint8_t INS3[7] = {0x00, 'a', 'a', 'a', 0x11, 0x22, 0x33};
218   uint8_t INS4[7] = {'a', 'a', 'a', 0x00, 0x11, 0x22, 0x33};
219 
220   uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 'b', 'b', 'b', 'b'};
221   uint8_t INS6[8] = {0x00, 0x11, 0x22, 'b', 'b', 'b', 'b', 0x33};
222   uint8_t INS7[8] = {0x00, 0x11, 'b', 'b', 'b', 'b', 0x22, 0x33};
223   uint8_t INS8[8] = {0x00, 'b', 'b', 'b', 'b', 0x11, 0x22, 0x33};
224   uint8_t INS9[8] = {'b', 'b', 'b', 'b', 0x00, 0x11, 0x22, 0x33};
225 
226   for (int i = 0; i < NumIter; i++) {
227     uint8_t T[8] = {0x00, 0x11, 0x22, 0x33};
228     size_t NewSize = (*MD.*M)(T, 4, 8);
229     if (NewSize == 7 && !memcmp(INS0, T, 7)) FoundMask |= 1 << 0;
230     if (NewSize == 7 && !memcmp(INS1, T, 7)) FoundMask |= 1 << 1;
231     if (NewSize == 7 && !memcmp(INS2, T, 7)) FoundMask |= 1 << 2;
232     if (NewSize == 7 && !memcmp(INS3, T, 7)) FoundMask |= 1 << 3;
233     if (NewSize == 7 && !memcmp(INS4, T, 7)) FoundMask |= 1 << 4;
234 
235     if (NewSize == 8 && !memcmp(INS5, T, 8)) FoundMask |= 1 << 5;
236     if (NewSize == 8 && !memcmp(INS6, T, 8)) FoundMask |= 1 << 6;
237     if (NewSize == 8 && !memcmp(INS7, T, 8)) FoundMask |= 1 << 7;
238     if (NewSize == 8 && !memcmp(INS8, T, 8)) FoundMask |= 1 << 8;
239     if (NewSize == 8 && !memcmp(INS9, T, 8)) FoundMask |= 1 << 9;
240 
241   }
242   EXPECT_EQ(FoundMask, (1 << 10) - 1);
243 }
244 
245 TEST(FuzzerMutate, InsertRepeatedBytes1) {
246   TestInsertRepeatedBytes(&MutationDispatcher::Mutate_InsertRepeatedBytes,
247                           10000);
248 }
249 TEST(FuzzerMutate, InsertRepeatedBytes2) {
250   TestInsertRepeatedBytes(&MutationDispatcher::Mutate, 300000);
251 }
252 
253 void TestChangeByte(Mutator M, int NumIter) {
254   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
255   fuzzer::EF = t.get();
256   Random Rand(0);
257   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
258   int FoundMask = 0;
259   uint8_t CH0[8] = {0xF0, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
260   uint8_t CH1[8] = {0x00, 0xF1, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
261   uint8_t CH2[8] = {0x00, 0x11, 0xF2, 0x33, 0x44, 0x55, 0x66, 0x77};
262   uint8_t CH3[8] = {0x00, 0x11, 0x22, 0xF3, 0x44, 0x55, 0x66, 0x77};
263   uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0xF4, 0x55, 0x66, 0x77};
264   uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF5, 0x66, 0x77};
265   uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF5, 0x77};
266   uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7};
267   for (int i = 0; i < NumIter; i++) {
268     uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
269     size_t NewSize = (*MD.*M)(T, 8, 9);
270     if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0;
271     if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1;
272     if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2;
273     if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3;
274     if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4;
275     if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
276     if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
277     if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
278   }
279   EXPECT_EQ(FoundMask, 255);
280 }
281 
282 TEST(FuzzerMutate, ChangeByte1) {
283   TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15);
284 }
285 TEST(FuzzerMutate, ChangeByte2) {
286   TestChangeByte(&MutationDispatcher::Mutate, 1 << 17);
287 }
288 
289 void TestChangeBit(Mutator M, int NumIter) {
290   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
291   fuzzer::EF = t.get();
292   Random Rand(0);
293   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
294   int FoundMask = 0;
295   uint8_t CH0[8] = {0x01, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
296   uint8_t CH1[8] = {0x00, 0x13, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
297   uint8_t CH2[8] = {0x00, 0x11, 0x02, 0x33, 0x44, 0x55, 0x66, 0x77};
298   uint8_t CH3[8] = {0x00, 0x11, 0x22, 0x37, 0x44, 0x55, 0x66, 0x77};
299   uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x54, 0x55, 0x66, 0x77};
300   uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x54, 0x66, 0x77};
301   uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x76, 0x77};
302   uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7};
303   for (int i = 0; i < NumIter; i++) {
304     uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
305     size_t NewSize = (*MD.*M)(T, 8, 9);
306     if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0;
307     if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1;
308     if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2;
309     if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3;
310     if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4;
311     if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
312     if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
313     if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
314   }
315   EXPECT_EQ(FoundMask, 255);
316 }
317 
318 TEST(FuzzerMutate, ChangeBit1) {
319   TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16);
320 }
321 TEST(FuzzerMutate, ChangeBit2) {
322   TestChangeBit(&MutationDispatcher::Mutate, 1 << 18);
323 }
324 
325 void TestShuffleBytes(Mutator M, int NumIter) {
326   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
327   fuzzer::EF = t.get();
328   Random Rand(0);
329   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
330   int FoundMask = 0;
331   uint8_t CH0[7] = {0x00, 0x22, 0x11, 0x33, 0x44, 0x55, 0x66};
332   uint8_t CH1[7] = {0x11, 0x00, 0x33, 0x22, 0x44, 0x55, 0x66};
333   uint8_t CH2[7] = {0x00, 0x33, 0x11, 0x22, 0x44, 0x55, 0x66};
334   uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x33};
335   uint8_t CH4[7] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x44, 0x66};
336   for (int i = 0; i < NumIter; i++) {
337     uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
338     size_t NewSize = (*MD.*M)(T, 7, 7);
339     if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0;
340     if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1;
341     if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2;
342     if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3;
343     if (NewSize == 7 && !memcmp(CH4, T, 7)) FoundMask |= 1 << 4;
344   }
345   EXPECT_EQ(FoundMask, 31);
346 }
347 
348 TEST(FuzzerMutate, ShuffleBytes1) {
349   TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 17);
350 }
351 TEST(FuzzerMutate, ShuffleBytes2) {
352   TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 20);
353 }
354 
355 void TestCopyPart(Mutator M, int NumIter) {
356   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
357   fuzzer::EF = t.get();
358   Random Rand(0);
359   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
360   int FoundMask = 0;
361   uint8_t CH0[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11};
362   uint8_t CH1[7] = {0x55, 0x66, 0x22, 0x33, 0x44, 0x55, 0x66};
363   uint8_t CH2[7] = {0x00, 0x55, 0x66, 0x33, 0x44, 0x55, 0x66};
364   uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x66};
365   uint8_t CH4[7] = {0x00, 0x11, 0x11, 0x22, 0x33, 0x55, 0x66};
366 
367   for (int i = 0; i < NumIter; i++) {
368     uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
369     size_t NewSize = (*MD.*M)(T, 7, 7);
370     if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0;
371     if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1;
372     if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2;
373     if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3;
374     if (NewSize == 7 && !memcmp(CH4, T, 7)) FoundMask |= 1 << 4;
375   }
376 
377   uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22};
378   uint8_t CH6[8] = {0x22, 0x33, 0x44, 0x00, 0x11, 0x22, 0x33, 0x44};
379   uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x33, 0x44};
380   uint8_t CH8[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x22, 0x33, 0x44};
381   uint8_t CH9[8] = {0x00, 0x11, 0x22, 0x22, 0x33, 0x44, 0x33, 0x44};
382 
383   for (int i = 0; i < NumIter; i++) {
384     uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
385     size_t NewSize = (*MD.*M)(T, 5, 8);
386     if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
387     if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
388     if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
389     if (NewSize == 8 && !memcmp(CH8, T, 8)) FoundMask |= 1 << 8;
390     if (NewSize == 8 && !memcmp(CH9, T, 8)) FoundMask |= 1 << 9;
391   }
392 
393   EXPECT_EQ(FoundMask, 1023);
394 }
395 
396 TEST(FuzzerMutate, CopyPart1) {
397   TestCopyPart(&MutationDispatcher::Mutate_CopyPart, 1 << 10);
398 }
399 TEST(FuzzerMutate, CopyPart2) {
400   TestCopyPart(&MutationDispatcher::Mutate, 1 << 13);
401 }
402 TEST(FuzzerMutate, CopyPartNoInsertAtMaxSize) {
403   // This (non exhaustively) tests if `Mutate_CopyPart` tries to perform an
404   // insert on an input of size `MaxSize`.  Performing an insert in this case
405   // will lead to the mutation failing.
406   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
407   fuzzer::EF = t.get();
408   Random Rand(0);
409   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
410   uint8_t Data[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22};
411   size_t MaxSize = sizeof(Data);
412   for (int count = 0; count < (1 << 18); ++count) {
413     size_t NewSize = MD->Mutate_CopyPart(Data, MaxSize, MaxSize);
414     ASSERT_EQ(NewSize, MaxSize);
415   }
416 }
417 
418 void TestAddWordFromDictionary(Mutator M, int NumIter) {
419   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
420   fuzzer::EF = t.get();
421   Random Rand(0);
422   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
423   uint8_t Word1[4] = {0xAA, 0xBB, 0xCC, 0xDD};
424   uint8_t Word2[3] = {0xFF, 0xEE, 0xEF};
425   MD->AddWordToManualDictionary(Word(Word1, sizeof(Word1)));
426   MD->AddWordToManualDictionary(Word(Word2, sizeof(Word2)));
427   int FoundMask = 0;
428   uint8_t CH0[7] = {0x00, 0x11, 0x22, 0xAA, 0xBB, 0xCC, 0xDD};
429   uint8_t CH1[7] = {0x00, 0x11, 0xAA, 0xBB, 0xCC, 0xDD, 0x22};
430   uint8_t CH2[7] = {0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0x11, 0x22};
431   uint8_t CH3[7] = {0xAA, 0xBB, 0xCC, 0xDD, 0x00, 0x11, 0x22};
432   uint8_t CH4[6] = {0x00, 0x11, 0x22, 0xFF, 0xEE, 0xEF};
433   uint8_t CH5[6] = {0x00, 0x11, 0xFF, 0xEE, 0xEF, 0x22};
434   uint8_t CH6[6] = {0x00, 0xFF, 0xEE, 0xEF, 0x11, 0x22};
435   uint8_t CH7[6] = {0xFF, 0xEE, 0xEF, 0x00, 0x11, 0x22};
436   for (int i = 0; i < NumIter; i++) {
437     uint8_t T[7] = {0x00, 0x11, 0x22};
438     size_t NewSize = (*MD.*M)(T, 3, 7);
439     if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0;
440     if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1;
441     if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2;
442     if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3;
443     if (NewSize == 6 && !memcmp(CH4, T, 6)) FoundMask |= 1 << 4;
444     if (NewSize == 6 && !memcmp(CH5, T, 6)) FoundMask |= 1 << 5;
445     if (NewSize == 6 && !memcmp(CH6, T, 6)) FoundMask |= 1 << 6;
446     if (NewSize == 6 && !memcmp(CH7, T, 6)) FoundMask |= 1 << 7;
447   }
448   EXPECT_EQ(FoundMask, 255);
449 }
450 
451 TEST(FuzzerMutate, AddWordFromDictionary1) {
452   TestAddWordFromDictionary(
453       &MutationDispatcher::Mutate_AddWordFromManualDictionary, 1 << 15);
454 }
455 
456 TEST(FuzzerMutate, AddWordFromDictionary2) {
457   TestAddWordFromDictionary(&MutationDispatcher::Mutate, 1 << 15);
458 }
459 
460 void TestChangeASCIIInteger(Mutator M, int NumIter) {
461   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
462   fuzzer::EF = t.get();
463   Random Rand(0);
464   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
465 
466   uint8_t CH0[8] = {'1', '2', '3', '4', '5', '6', '7', '7'};
467   uint8_t CH1[8] = {'1', '2', '3', '4', '5', '6', '7', '9'};
468   uint8_t CH2[8] = {'2', '4', '6', '9', '1', '3', '5', '6'};
469   uint8_t CH3[8] = {'0', '6', '1', '7', '2', '8', '3', '9'};
470   int FoundMask = 0;
471   for (int i = 0; i < NumIter; i++) {
472     uint8_t T[8] = {'1', '2', '3', '4', '5', '6', '7', '8'};
473     size_t NewSize = (*MD.*M)(T, 8, 8);
474     /**/ if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0;
475     else if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1;
476     else if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2;
477     else if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3;
478     else if (NewSize == 8)                       FoundMask |= 1 << 4;
479   }
480   EXPECT_EQ(FoundMask, 31);
481 }
482 
483 TEST(FuzzerMutate, ChangeASCIIInteger1) {
484   TestChangeASCIIInteger(&MutationDispatcher::Mutate_ChangeASCIIInteger,
485                          1 << 15);
486 }
487 
488 TEST(FuzzerMutate, ChangeASCIIInteger2) {
489   TestChangeASCIIInteger(&MutationDispatcher::Mutate, 1 << 15);
490 }
491 
492 void TestChangeBinaryInteger(Mutator M, int NumIter) {
493   std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
494   fuzzer::EF = t.get();
495   Random Rand(0);
496   std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
497 
498   uint8_t CH0[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x79};
499   uint8_t CH1[8] = {0x00, 0x11, 0x22, 0x31, 0x44, 0x55, 0x66, 0x77};
500   uint8_t CH2[8] = {0xff, 0x10, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
501   uint8_t CH3[8] = {0x00, 0x11, 0x2a, 0x33, 0x44, 0x55, 0x66, 0x77};
502   uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x4f, 0x66, 0x77};
503   uint8_t CH5[8] = {0xff, 0xee, 0xdd, 0xcc, 0xbb, 0xaa, 0x99, 0x88};
504   uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x00, 0x00, 0x00, 0x08, 0x77}; // Size
505   uint8_t CH7[8] = {0x00, 0x08, 0x00, 0x33, 0x44, 0x55, 0x66, 0x77}; // Sw(Size)
506 
507   int FoundMask = 0;
508   for (int i = 0; i < NumIter; i++) {
509     uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
510     size_t NewSize = (*MD.*M)(T, 8, 8);
511     /**/ if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0;
512     else if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1;
513     else if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2;
514     else if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3;
515     else if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4;
516     else if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
517     else if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
518     else if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
519   }
520   EXPECT_EQ(FoundMask, 255);
521 }
522 
523 TEST(FuzzerMutate, ChangeBinaryInteger1) {
524   TestChangeBinaryInteger(&MutationDispatcher::Mutate_ChangeBinaryInteger,
525                          1 << 12);
526 }
527 
528 TEST(FuzzerMutate, ChangeBinaryInteger2) {
529   TestChangeBinaryInteger(&MutationDispatcher::Mutate, 1 << 15);
530 }
531 
532 
533 TEST(FuzzerDictionary, ParseOneDictionaryEntry) {
534   Unit U;
535   EXPECT_FALSE(ParseOneDictionaryEntry("", &U));
536   EXPECT_FALSE(ParseOneDictionaryEntry(" ", &U));
537   EXPECT_FALSE(ParseOneDictionaryEntry("\t  ", &U));
538   EXPECT_FALSE(ParseOneDictionaryEntry("  \" ", &U));
539   EXPECT_FALSE(ParseOneDictionaryEntry("  zz\" ", &U));
540   EXPECT_FALSE(ParseOneDictionaryEntry("  \"zz ", &U));
541   EXPECT_FALSE(ParseOneDictionaryEntry("  \"\" ", &U));
542   EXPECT_TRUE(ParseOneDictionaryEntry("\"a\"", &U));
543   EXPECT_EQ(U, Unit({'a'}));
544   EXPECT_TRUE(ParseOneDictionaryEntry("\"abc\"", &U));
545   EXPECT_EQ(U, Unit({'a', 'b', 'c'}));
546   EXPECT_TRUE(ParseOneDictionaryEntry("abc=\"abc\"", &U));
547   EXPECT_EQ(U, Unit({'a', 'b', 'c'}));
548   EXPECT_FALSE(ParseOneDictionaryEntry("\"\\\"", &U));
549   EXPECT_TRUE(ParseOneDictionaryEntry("\"\\\\\"", &U));
550   EXPECT_EQ(U, Unit({'\\'}));
551   EXPECT_TRUE(ParseOneDictionaryEntry("\"\\xAB\"", &U));
552   EXPECT_EQ(U, Unit({0xAB}));
553   EXPECT_TRUE(ParseOneDictionaryEntry("\"\\xABz\\xDE\"", &U));
554   EXPECT_EQ(U, Unit({0xAB, 'z', 0xDE}));
555   EXPECT_TRUE(ParseOneDictionaryEntry("\"#\"", &U));
556   EXPECT_EQ(U, Unit({'#'}));
557   EXPECT_TRUE(ParseOneDictionaryEntry("\"\\\"\"", &U));
558   EXPECT_EQ(U, Unit({'"'}));
559 }
560 
561 TEST(FuzzerDictionary, ParseDictionaryFile) {
562   std::vector<Unit> Units;
563   EXPECT_FALSE(ParseDictionaryFile("zzz\n", &Units));
564   EXPECT_FALSE(ParseDictionaryFile("", &Units));
565   EXPECT_TRUE(ParseDictionaryFile("\n", &Units));
566   EXPECT_EQ(Units.size(), 0U);
567   EXPECT_TRUE(ParseDictionaryFile("#zzzz a b c d\n", &Units));
568   EXPECT_EQ(Units.size(), 0U);
569   EXPECT_TRUE(ParseDictionaryFile(" #zzzz\n", &Units));
570   EXPECT_EQ(Units.size(), 0U);
571   EXPECT_TRUE(ParseDictionaryFile("  #zzzz\n", &Units));
572   EXPECT_EQ(Units.size(), 0U);
573   EXPECT_TRUE(ParseDictionaryFile("  #zzzz\naaa=\"aa\"", &Units));
574   EXPECT_EQ(Units, std::vector<Unit>({Unit({'a', 'a'})}));
575   EXPECT_TRUE(
576       ParseDictionaryFile("  #zzzz\naaa=\"aa\"\n\nabc=\"abc\"", &Units));
577   EXPECT_EQ(Units,
578             std::vector<Unit>({Unit({'a', 'a'}), Unit({'a', 'b', 'c'})}));
579 }
580 
581 TEST(FuzzerUtil, Base64) {
582   EXPECT_EQ("", Base64({}));
583   EXPECT_EQ("YQ==", Base64({'a'}));
584   EXPECT_EQ("eA==", Base64({'x'}));
585   EXPECT_EQ("YWI=", Base64({'a', 'b'}));
586   EXPECT_EQ("eHk=", Base64({'x', 'y'}));
587   EXPECT_EQ("YWJj", Base64({'a', 'b', 'c'}));
588   EXPECT_EQ("eHl6", Base64({'x', 'y', 'z'}));
589   EXPECT_EQ("YWJjeA==", Base64({'a', 'b', 'c', 'x'}));
590   EXPECT_EQ("YWJjeHk=", Base64({'a', 'b', 'c', 'x', 'y'}));
591   EXPECT_EQ("YWJjeHl6", Base64({'a', 'b', 'c', 'x', 'y', 'z'}));
592 }
593 
594 TEST(Corpus, Distribution) {
595   DataFlowTrace DFT;
596   Random Rand(0);
597   struct EntropicOptions Entropic = {false, 0xFF, 100, false};
598   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
599   size_t N = 10;
600   size_t TriesPerUnit = 1<<16;
601   for (size_t i = 0; i < N; i++)
602     C->AddToCorpus(Unit{static_cast<uint8_t>(i)}, /*NumFeatures*/ 1,
603                    /*MayDeleteFile*/ false, /*HasFocusFunction*/ false,
604                    /*ForceAddToCorpus*/ false,
605                    /*TimeOfUnit*/ std::chrono::microseconds(0),
606                    /*FeatureSet*/ {}, DFT,
607                    /*BaseII*/ nullptr);
608 
609   std::vector<size_t> Hist(N);
610   for (size_t i = 0; i < N * TriesPerUnit; i++) {
611     Hist[C->ChooseUnitIdxToMutate(Rand)]++;
612   }
613   for (size_t i = 0; i < N; i++) {
614     // A weak sanity check that every unit gets invoked.
615     EXPECT_GT(Hist[i], TriesPerUnit / N / 3);
616   }
617 }
618 
619 template <typename T>
620 void EQ(const std::vector<T> &A, const std::vector<T> &B) {
621   EXPECT_EQ(A, B);
622 }
623 
624 template <typename T> void EQ(const std::set<T> &A, const std::vector<T> &B) {
625   EXPECT_EQ(A, std::set<T>(B.begin(), B.end()));
626 }
627 
628 void EQ(const std::vector<MergeFileInfo> &A,
629         const std::vector<std::string> &B) {
630   std::set<std::string> a;
631   for (const auto &File : A)
632     a.insert(File.Name);
633   std::set<std::string> b(B.begin(), B.end());
634   EXPECT_EQ(a, b);
635 }
636 
637 #define TRACED_EQ(A, ...)                                                      \
638   {                                                                            \
639     SCOPED_TRACE(#A);                                                          \
640     EQ(A, __VA_ARGS__);                                                        \
641   }
642 
643 TEST(Merger, Parse) {
644   Merger M;
645 
646   const char *kInvalidInputs[] = {
647       // Bad file numbers
648       "",
649       "x",
650       "0\n0",
651       "3\nx",
652       "2\n3",
653       "2\n2",
654       // Bad file names
655       "2\n2\nA\n",
656       "2\n2\nA\nB\nC\n",
657       // Unknown markers
658       "2\n1\nA\nSTARTED 0\nBAD 0 0x0",
659       // Bad file IDs
660       "1\n1\nA\nSTARTED 1",
661       "2\n1\nA\nSTARTED 0\nFT 1 0x0",
662   };
663   for (auto S : kInvalidInputs) {
664     SCOPED_TRACE(S);
665     EXPECT_FALSE(M.Parse(S, false));
666   }
667 
668   // Parse initial control file
669   EXPECT_TRUE(M.Parse("1\n0\nAA\n", false));
670   ASSERT_EQ(M.Files.size(), 1U);
671   EXPECT_EQ(M.NumFilesInFirstCorpus, 0U);
672   EXPECT_EQ(M.Files[0].Name, "AA");
673   EXPECT_TRUE(M.LastFailure.empty());
674   EXPECT_EQ(M.FirstNotProcessedFile, 0U);
675 
676   // Parse control file that failed on first attempt
677   EXPECT_TRUE(M.Parse("2\n1\nAA\nBB\nSTARTED 0 42\n", false));
678   ASSERT_EQ(M.Files.size(), 2U);
679   EXPECT_EQ(M.NumFilesInFirstCorpus, 1U);
680   EXPECT_EQ(M.Files[0].Name, "AA");
681   EXPECT_EQ(M.Files[1].Name, "BB");
682   EXPECT_EQ(M.LastFailure, "AA");
683   EXPECT_EQ(M.FirstNotProcessedFile, 1U);
684 
685   // Parse control file that failed on later attempt
686   EXPECT_TRUE(M.Parse("3\n1\nAA\nBB\nC\n"
687                       "STARTED 0 1000\n"
688                       "FT 0 1 2 3\n"
689                       "STARTED 1 1001\n"
690                       "FT 1 4 5 6 \n"
691                       "STARTED 2 1002\n"
692                       "",
693                       true));
694   ASSERT_EQ(M.Files.size(), 3U);
695   EXPECT_EQ(M.NumFilesInFirstCorpus, 1U);
696   EXPECT_EQ(M.Files[0].Name, "AA");
697   EXPECT_EQ(M.Files[0].Size, 1000U);
698   EXPECT_EQ(M.Files[1].Name, "BB");
699   EXPECT_EQ(M.Files[1].Size, 1001U);
700   EXPECT_EQ(M.Files[2].Name, "C");
701   EXPECT_EQ(M.Files[2].Size, 1002U);
702   EXPECT_EQ(M.LastFailure, "C");
703   EXPECT_EQ(M.FirstNotProcessedFile, 3U);
704   TRACED_EQ(M.Files[0].Features, {1, 2, 3});
705   TRACED_EQ(M.Files[1].Features, {4, 5, 6});
706 
707   // Parse control file without features or PCs
708   EXPECT_TRUE(M.Parse("2\n0\nAA\nBB\n"
709                       "STARTED 0 1000\n"
710                       "FT 0\n"
711                       "COV 0\n"
712                       "STARTED 1 1001\n"
713                       "FT 1\n"
714                       "COV 1\n"
715                       "",
716                       true));
717   ASSERT_EQ(M.Files.size(), 2U);
718   EXPECT_EQ(M.NumFilesInFirstCorpus, 0U);
719   EXPECT_TRUE(M.LastFailure.empty());
720   EXPECT_EQ(M.FirstNotProcessedFile, 2U);
721   EXPECT_TRUE(M.Files[0].Features.empty());
722   EXPECT_TRUE(M.Files[0].Cov.empty());
723   EXPECT_TRUE(M.Files[1].Features.empty());
724   EXPECT_TRUE(M.Files[1].Cov.empty());
725 
726   // Parse features and PCs
727   EXPECT_TRUE(M.Parse("3\n2\nAA\nBB\nC\n"
728                       "STARTED 0 1000\n"
729                       "FT 0 1 2 3\n"
730                       "COV 0 11 12 13\n"
731                       "STARTED 1 1001\n"
732                       "FT 1 4 5 6\n"
733                       "COV 1 7 8 9\n"
734                       "STARTED 2 1002\n"
735                       "FT 2 6 1 3\n"
736                       "COV 2 16 11 13\n"
737                       "",
738                       true));
739   ASSERT_EQ(M.Files.size(), 3U);
740   EXPECT_EQ(M.NumFilesInFirstCorpus, 2U);
741   EXPECT_TRUE(M.LastFailure.empty());
742   EXPECT_EQ(M.FirstNotProcessedFile, 3U);
743   TRACED_EQ(M.Files[0].Features, {1, 2, 3});
744   TRACED_EQ(M.Files[0].Cov, {11, 12, 13});
745   TRACED_EQ(M.Files[1].Features, {4, 5, 6});
746   TRACED_EQ(M.Files[1].Cov, {7, 8, 9});
747   TRACED_EQ(M.Files[2].Features, {1, 3, 6});
748   TRACED_EQ(M.Files[2].Cov, {16});
749 }
750 
751 TEST(Merger, Merge) {
752   Merger M;
753   std::set<uint32_t> Features, NewFeatures;
754   std::set<uint32_t> Cov, NewCov;
755   std::vector<std::string> NewFiles;
756 
757   // Adds new files and features
758   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
759                       "STARTED 0 1000\n"
760                       "FT 0 1 2 3\n"
761                       "STARTED 1 1001\n"
762                       "FT 1 4 5 6 \n"
763                       "STARTED 2 1002\n"
764                       "FT 2 6 1 3\n"
765                       "",
766                       true));
767   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 6U);
768   TRACED_EQ(M.Files, {"A", "B", "C"});
769   TRACED_EQ(NewFiles, {"A", "B"});
770   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
771 
772   // Doesn't return features or files in the initial corpus.
773   EXPECT_TRUE(M.Parse("3\n1\nA\nB\nC\n"
774                       "STARTED 0 1000\n"
775                       "FT 0 1 2 3\n"
776                       "STARTED 1 1001\n"
777                       "FT 1 4 5 6 \n"
778                       "STARTED 2 1002\n"
779                       "FT 2 6 1 3\n"
780                       "",
781                       true));
782   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
783   TRACED_EQ(M.Files, {"A", "B", "C"});
784   TRACED_EQ(NewFiles, {"B"});
785   TRACED_EQ(NewFeatures, {4, 5, 6});
786 
787   // No new features, so no new files
788   EXPECT_TRUE(M.Parse("3\n2\nA\nB\nC\n"
789                       "STARTED 0 1000\n"
790                       "FT 0 1 2 3\n"
791                       "STARTED 1 1001\n"
792                       "FT 1 4 5 6 \n"
793                       "STARTED 2 1002\n"
794                       "FT 2 6 1 3\n"
795                       "",
796                       true));
797   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 0U);
798   TRACED_EQ(M.Files, {"A", "B", "C"});
799   TRACED_EQ(NewFiles, {});
800   TRACED_EQ(NewFeatures, {});
801 
802   // Can pass initial features and coverage.
803   Features = {1, 2, 3};
804   Cov = {};
805   EXPECT_TRUE(M.Parse("2\n0\nA\nB\n"
806                       "STARTED 0 1000\n"
807                       "FT 0 1 2 3\n"
808                       "STARTED 1 1001\n"
809                       "FT 1 4 5 6\n"
810                       "",
811                       true));
812   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
813   TRACED_EQ(M.Files, {"A", "B"});
814   TRACED_EQ(NewFiles, {"B"});
815   TRACED_EQ(NewFeatures, {4, 5, 6});
816   Features.clear();
817   Cov.clear();
818 
819   // Parse smaller files first
820   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
821                       "STARTED 0 2000\n"
822                       "FT 0 1 2 3\n"
823                       "STARTED 1 1001\n"
824                       "FT 1 4 5 6 \n"
825                       "STARTED 2 1002\n"
826                       "FT 2 6 1 3 \n"
827                       "",
828                       true));
829   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 6U);
830   TRACED_EQ(M.Files, {"B", "C", "A"});
831   TRACED_EQ(NewFiles, {"B", "C", "A"});
832   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
833 
834   EXPECT_TRUE(M.Parse("4\n0\nA\nB\nC\nD\n"
835                       "STARTED 0 2000\n"
836                       "FT 0 1 2 3\n"
837                       "STARTED 1 1101\n"
838                       "FT 1 4 5 6 \n"
839                       "STARTED 2 1102\n"
840                       "FT 2 6 1 3 100 \n"
841                       "STARTED 3 1000\n"
842                       "FT 3 1  \n"
843                       "",
844                       true));
845   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 7U);
846   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
847   TRACED_EQ(NewFiles, {"D", "B", "C", "A"});
848   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6, 100});
849 
850   // For same sized file, parse more features first
851   EXPECT_TRUE(M.Parse("4\n1\nA\nB\nC\nD\n"
852                       "STARTED 0 2000\n"
853                       "FT 0 4 5 6 7 8\n"
854                       "STARTED 1 1100\n"
855                       "FT 1 1 2 3 \n"
856                       "STARTED 2 1100\n"
857                       "FT 2 2 3 \n"
858                       "STARTED 3 1000\n"
859                       "FT 3 1  \n"
860                       "",
861                       true));
862   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
863   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
864   TRACED_EQ(NewFiles, {"D", "B"});
865   TRACED_EQ(NewFeatures, {1, 2, 3});
866 }
867 
868 #undef TRACED_EQ
869 
870 TEST(DFT, BlockCoverage) {
871   BlockCoverage Cov;
872   // Assuming C0 has 5 instrumented blocks,
873   // C1: 7 blocks, C2: 4, C3: 9, C4 never covered, C5: 15,
874 
875   // Add C0
876   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
877   EXPECT_EQ(Cov.GetCounter(0, 0), 1U);
878   EXPECT_EQ(Cov.GetCounter(0, 1), 0U);  // not seen this BB yet.
879   EXPECT_EQ(Cov.GetCounter(0, 5), 0U);  // BB ID out of bounds.
880   EXPECT_EQ(Cov.GetCounter(1, 0), 0U);  // not seen this function yet.
881 
882   EXPECT_EQ(Cov.GetNumberOfBlocks(0), 5U);
883   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 1U);
884   EXPECT_EQ(Cov.GetNumberOfBlocks(1), 0U);
885 
886   // Various errors.
887   EXPECT_FALSE(Cov.AppendCoverage("C0\n"));  // No total number.
888   EXPECT_FALSE(Cov.AppendCoverage("C0 7\n"));  // No total number.
889   EXPECT_FALSE(Cov.AppendCoverage("CZ\n"));  // Wrong function number.
890   EXPECT_FALSE(Cov.AppendCoverage("C1 7 7"));  // BB ID is too big.
891   EXPECT_FALSE(Cov.AppendCoverage("C1 100 7")); // BB ID is too big.
892 
893   // Add C0 more times.
894   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
895   EXPECT_EQ(Cov.GetCounter(0, 0), 2U);
896   EXPECT_TRUE(Cov.AppendCoverage("C0 1 2 5\n"));
897   EXPECT_EQ(Cov.GetCounter(0, 0), 3U);
898   EXPECT_EQ(Cov.GetCounter(0, 1), 1U);
899   EXPECT_EQ(Cov.GetCounter(0, 2), 1U);
900   EXPECT_EQ(Cov.GetCounter(0, 3), 0U);
901   EXPECT_EQ(Cov.GetCounter(0, 4), 0U);
902   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 3U);
903   EXPECT_TRUE(Cov.AppendCoverage("C0 1 3 4 5\n"));
904   EXPECT_EQ(Cov.GetCounter(0, 0), 4U);
905   EXPECT_EQ(Cov.GetCounter(0, 1), 2U);
906   EXPECT_EQ(Cov.GetCounter(0, 2), 1U);
907   EXPECT_EQ(Cov.GetCounter(0, 3), 1U);
908   EXPECT_EQ(Cov.GetCounter(0, 4), 1U);
909   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 5U);
910 
911   EXPECT_TRUE(Cov.AppendCoverage("C1 7\nC2 4\nC3 9\nC5 15\nC0 5\n"));
912   EXPECT_EQ(Cov.GetCounter(0, 0), 5U);
913   EXPECT_EQ(Cov.GetCounter(1, 0), 1U);
914   EXPECT_EQ(Cov.GetCounter(2, 0), 1U);
915   EXPECT_EQ(Cov.GetCounter(3, 0), 1U);
916   EXPECT_EQ(Cov.GetCounter(4, 0), 0U);
917   EXPECT_EQ(Cov.GetCounter(5, 0), 1U);
918 
919   EXPECT_TRUE(Cov.AppendCoverage("C3 4 5 9\nC5 11 12 15"));
920   EXPECT_EQ(Cov.GetCounter(0, 0), 5U);
921   EXPECT_EQ(Cov.GetCounter(1, 0), 1U);
922   EXPECT_EQ(Cov.GetCounter(2, 0), 1U);
923   EXPECT_EQ(Cov.GetCounter(3, 0), 2U);
924   EXPECT_EQ(Cov.GetCounter(3, 4), 1U);
925   EXPECT_EQ(Cov.GetCounter(3, 5), 1U);
926   EXPECT_EQ(Cov.GetCounter(3, 6), 0U);
927   EXPECT_EQ(Cov.GetCounter(4, 0), 0U);
928   EXPECT_EQ(Cov.GetCounter(5, 0), 2U);
929   EXPECT_EQ(Cov.GetCounter(5, 10), 0U);
930   EXPECT_EQ(Cov.GetCounter(5, 11), 1U);
931   EXPECT_EQ(Cov.GetCounter(5, 12), 1U);
932 }
933 
934 TEST(DFT, FunctionWeights) {
935   BlockCoverage Cov;
936   // unused function gets zero weight.
937   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
938   auto Weights = Cov.FunctionWeights(2);
939   EXPECT_GT(Weights[0], 0.);
940   EXPECT_EQ(Weights[1], 0.);
941 
942   // Less frequently used function gets less weight.
943   Cov.clear();
944   EXPECT_TRUE(Cov.AppendCoverage("C0 5\nC1 5\nC1 5\n"));
945   Weights = Cov.FunctionWeights(2);
946   EXPECT_GT(Weights[0], Weights[1]);
947 
948   // A function with more uncovered blocks gets more weight.
949   Cov.clear();
950   EXPECT_TRUE(Cov.AppendCoverage("C0 1 2 3 5\nC1 2 4\n"));
951   Weights = Cov.FunctionWeights(2);
952   EXPECT_GT(Weights[1], Weights[0]);
953 
954   // A function with DFT gets more weight than the function w/o DFT.
955   Cov.clear();
956   EXPECT_TRUE(Cov.AppendCoverage("F1 111\nC0 3\nC1 1 2 3\n"));
957   Weights = Cov.FunctionWeights(2);
958   EXPECT_GT(Weights[1], Weights[0]);
959 }
960 
961 
962 TEST(Fuzzer, ForEachNonZeroByte) {
963   const size_t N = 64;
964   alignas(64) uint8_t Ar[N + 8] = {
965     0, 0, 0, 0, 0, 0, 0, 0,
966     1, 2, 0, 0, 0, 0, 0, 0,
967     0, 0, 3, 0, 4, 0, 0, 0,
968     0, 0, 0, 0, 0, 0, 0, 0,
969     0, 0, 0, 5, 0, 6, 0, 0,
970     0, 0, 0, 0, 0, 0, 7, 0,
971     0, 0, 0, 0, 0, 0, 0, 0,
972     0, 0, 0, 0, 0, 0, 0, 8,
973     9, 9, 9, 9, 9, 9, 9, 9,
974   };
975   typedef std::vector<std::pair<size_t, uint8_t>> Vec;
976   Vec Res, Expected;
977   auto CB = [&](size_t FirstFeature, size_t Idx, uint8_t V) {
978     Res.push_back({FirstFeature + Idx, V});
979   };
980   ForEachNonZeroByte(Ar, Ar + N, 100, CB);
981   Expected = {{108, 1}, {109, 2}, {118, 3}, {120, 4},
982               {135, 5}, {137, 6}, {146, 7}, {163, 8}};
983   EXPECT_EQ(Res, Expected);
984 
985   Res.clear();
986   ForEachNonZeroByte(Ar + 9, Ar + N, 109, CB);
987   Expected = {          {109, 2}, {118, 3}, {120, 4},
988               {135, 5}, {137, 6}, {146, 7}, {163, 8}};
989   EXPECT_EQ(Res, Expected);
990 
991   Res.clear();
992   ForEachNonZeroByte(Ar + 9, Ar + N - 9, 109, CB);
993   Expected = {          {109, 2}, {118, 3}, {120, 4},
994               {135, 5}, {137, 6}, {146, 7}};
995   EXPECT_EQ(Res, Expected);
996 }
997 
998 // FuzzerCommand unit tests. The arguments in the two helper methods below must
999 // match.
1000 static void makeCommandArgs(std::vector<std::string> *ArgsToAdd) {
1001   assert(ArgsToAdd);
1002   ArgsToAdd->clear();
1003   ArgsToAdd->push_back("foo");
1004   ArgsToAdd->push_back("-bar=baz");
1005   ArgsToAdd->push_back("qux");
1006   ArgsToAdd->push_back(Command::ignoreRemainingArgs());
1007   ArgsToAdd->push_back("quux");
1008   ArgsToAdd->push_back("-grault=garply");
1009 }
1010 
1011 static std::string makeCmdLine(const char *separator, const char *suffix) {
1012   std::string CmdLine("foo -bar=baz qux ");
1013   if (strlen(separator) != 0) {
1014     CmdLine += separator;
1015     CmdLine += " ";
1016   }
1017   CmdLine += Command::ignoreRemainingArgs();
1018   CmdLine += " quux -grault=garply";
1019   if (strlen(suffix) != 0) {
1020     CmdLine += " ";
1021     CmdLine += suffix;
1022   }
1023   return CmdLine;
1024 }
1025 
1026 TEST(FuzzerCommand, Create) {
1027   std::string CmdLine;
1028 
1029   // Default constructor
1030   Command DefaultCmd;
1031 
1032   CmdLine = DefaultCmd.toString();
1033   EXPECT_EQ(CmdLine, "");
1034 
1035   // Explicit constructor
1036   std::vector<std::string> ArgsToAdd;
1037   makeCommandArgs(&ArgsToAdd);
1038   Command InitializedCmd(ArgsToAdd);
1039 
1040   CmdLine = InitializedCmd.toString();
1041   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1042 
1043   // Compare each argument
1044   auto InitializedArgs = InitializedCmd.getArguments();
1045   auto i = ArgsToAdd.begin();
1046   auto j = InitializedArgs.begin();
1047   while (i != ArgsToAdd.end() && j != InitializedArgs.end()) {
1048     EXPECT_EQ(*i++, *j++);
1049   }
1050   EXPECT_EQ(i, ArgsToAdd.end());
1051   EXPECT_EQ(j, InitializedArgs.end());
1052 
1053   // Copy constructor
1054   Command CopiedCmd(InitializedCmd);
1055 
1056   CmdLine = CopiedCmd.toString();
1057   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1058 
1059   // Assignment operator
1060   Command AssignedCmd;
1061   AssignedCmd = CopiedCmd;
1062 
1063   CmdLine = AssignedCmd.toString();
1064   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1065 }
1066 
1067 TEST(FuzzerCommand, ModifyArguments) {
1068   std::vector<std::string> ArgsToAdd;
1069   makeCommandArgs(&ArgsToAdd);
1070   Command Cmd;
1071   std::string CmdLine;
1072 
1073   Cmd.addArguments(ArgsToAdd);
1074   CmdLine = Cmd.toString();
1075   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1076 
1077   Cmd.addArgument("waldo");
1078   EXPECT_TRUE(Cmd.hasArgument("waldo"));
1079 
1080   CmdLine = Cmd.toString();
1081   EXPECT_EQ(CmdLine, makeCmdLine("waldo", ""));
1082 
1083   Cmd.removeArgument("waldo");
1084   EXPECT_FALSE(Cmd.hasArgument("waldo"));
1085 
1086   CmdLine = Cmd.toString();
1087   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1088 }
1089 
1090 TEST(FuzzerCommand, ModifyFlags) {
1091   std::vector<std::string> ArgsToAdd;
1092   makeCommandArgs(&ArgsToAdd);
1093   Command Cmd(ArgsToAdd);
1094   std::string Value, CmdLine;
1095   ASSERT_FALSE(Cmd.hasFlag("fred"));
1096 
1097   Value = Cmd.getFlagValue("fred");
1098   EXPECT_EQ(Value, "");
1099 
1100   CmdLine = Cmd.toString();
1101   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1102 
1103   Cmd.addFlag("fred", "plugh");
1104   EXPECT_TRUE(Cmd.hasFlag("fred"));
1105 
1106   Value = Cmd.getFlagValue("fred");
1107   EXPECT_EQ(Value, "plugh");
1108 
1109   CmdLine = Cmd.toString();
1110   EXPECT_EQ(CmdLine, makeCmdLine("-fred=plugh", ""));
1111 
1112   Cmd.removeFlag("fred");
1113   EXPECT_FALSE(Cmd.hasFlag("fred"));
1114 
1115   Value = Cmd.getFlagValue("fred");
1116   EXPECT_EQ(Value, "");
1117 
1118   CmdLine = Cmd.toString();
1119   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1120 }
1121 
1122 TEST(FuzzerCommand, SetOutput) {
1123   std::vector<std::string> ArgsToAdd;
1124   makeCommandArgs(&ArgsToAdd);
1125   Command Cmd(ArgsToAdd);
1126   std::string CmdLine;
1127   ASSERT_FALSE(Cmd.hasOutputFile());
1128   ASSERT_FALSE(Cmd.isOutAndErrCombined());
1129 
1130   Cmd.combineOutAndErr(true);
1131   EXPECT_TRUE(Cmd.isOutAndErrCombined());
1132 
1133   CmdLine = Cmd.toString();
1134   EXPECT_EQ(CmdLine, makeCmdLine("", "2>&1"));
1135 
1136   Cmd.combineOutAndErr(false);
1137   EXPECT_FALSE(Cmd.isOutAndErrCombined());
1138 
1139   Cmd.setOutputFile("xyzzy");
1140   EXPECT_TRUE(Cmd.hasOutputFile());
1141 
1142   CmdLine = Cmd.toString();
1143   EXPECT_EQ(CmdLine, makeCmdLine("", ">xyzzy"));
1144 
1145   Cmd.setOutputFile("thud");
1146   EXPECT_TRUE(Cmd.hasOutputFile());
1147 
1148   CmdLine = Cmd.toString();
1149   EXPECT_EQ(CmdLine, makeCmdLine("", ">thud"));
1150 
1151   Cmd.combineOutAndErr();
1152   EXPECT_TRUE(Cmd.isOutAndErrCombined());
1153 
1154   CmdLine = Cmd.toString();
1155   EXPECT_EQ(CmdLine, makeCmdLine("", ">thud 2>&1"));
1156 }
1157 
1158 TEST(Entropic, UpdateFrequency) {
1159   const size_t One = 1, Two = 2;
1160   const size_t FeatIdx1 = 0, FeatIdx2 = 42, FeatIdx3 = 12, FeatIdx4 = 26;
1161   size_t Index;
1162   // Create input corpus with default entropic configuration
1163   struct EntropicOptions Entropic = {true, 0xFF, 100, false};
1164   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
1165   std::unique_ptr<InputInfo> II(new InputInfo());
1166 
1167   C->AddRareFeature(FeatIdx1);
1168   C->UpdateFeatureFrequency(II.get(), FeatIdx1);
1169   EXPECT_EQ(II->FeatureFreqs.size(), One);
1170   C->AddRareFeature(FeatIdx2);
1171   C->UpdateFeatureFrequency(II.get(), FeatIdx1);
1172   C->UpdateFeatureFrequency(II.get(), FeatIdx2);
1173   EXPECT_EQ(II->FeatureFreqs.size(), Two);
1174   EXPECT_EQ(II->FeatureFreqs[0].second, 2);
1175   EXPECT_EQ(II->FeatureFreqs[1].second, 1);
1176 
1177   C->AddRareFeature(FeatIdx3);
1178   C->AddRareFeature(FeatIdx4);
1179   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1180   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1181   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1182   C->UpdateFeatureFrequency(II.get(), FeatIdx4);
1183 
1184   for (Index = 1; Index < II->FeatureFreqs.size(); Index++)
1185     EXPECT_LT(II->FeatureFreqs[Index - 1].first, II->FeatureFreqs[Index].first);
1186 
1187   II->DeleteFeatureFreq(FeatIdx3);
1188   for (Index = 1; Index < II->FeatureFreqs.size(); Index++)
1189     EXPECT_LT(II->FeatureFreqs[Index - 1].first, II->FeatureFreqs[Index].first);
1190 }
1191 
1192 double SubAndSquare(double X, double Y) {
1193   double R = X - Y;
1194   R = R * R;
1195   return R;
1196 }
1197 
1198 TEST(Entropic, ComputeEnergy) {
1199   const double Precision = 0.01;
1200   struct EntropicOptions Entropic = {true, 0xFF, 100, false};
1201   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
1202   std::unique_ptr<InputInfo> II(new InputInfo());
1203   std::vector<std::pair<uint32_t, uint16_t>> FeatureFreqs = {
1204       {1, 3}, {2, 3}, {3, 3}};
1205   II->FeatureFreqs = FeatureFreqs;
1206   II->NumExecutedMutations = 0;
1207   II->UpdateEnergy(4, false, std::chrono::microseconds(0));
1208   EXPECT_LT(SubAndSquare(II->Energy, 1.450805), Precision);
1209 
1210   II->NumExecutedMutations = 9;
1211   II->UpdateEnergy(5, false, std::chrono::microseconds(0));
1212   EXPECT_LT(SubAndSquare(II->Energy, 1.525496), Precision);
1213 
1214   II->FeatureFreqs[0].second++;
1215   II->FeatureFreqs.push_back(std::pair<uint32_t, uint16_t>(42, 6));
1216   II->NumExecutedMutations = 20;
1217   II->UpdateEnergy(10, false, std::chrono::microseconds(0));
1218   EXPECT_LT(SubAndSquare(II->Energy, 1.792831), Precision);
1219 }
1220 
1221 int main(int argc, char **argv) {
1222   testing::InitGoogleTest(&argc, argv);
1223   return RUN_ALL_TESTS();
1224 }
1225