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 #ifdef __GLIBC__
595 class PrintfCapture {
596  public:
597   PrintfCapture() {
598     OldOutputFile = GetOutputFile();
599     SetOutputFile(open_memstream(&Buffer, &Size));
600   }
601   ~PrintfCapture() {
602     fclose(GetOutputFile());
603     SetOutputFile(OldOutputFile);
604     free(Buffer);
605   }
606   std::string str() { return std::string(Buffer, Size); }
607 
608  private:
609   char *Buffer;
610   size_t Size;
611   FILE *OldOutputFile;
612 };
613 
614 TEST(FuzzerUtil, PrintASCII) {
615   auto f = [](const char *Str, const char *PrintAfter = "") {
616     PrintfCapture Capture;
617     PrintASCII(reinterpret_cast<const uint8_t*>(Str), strlen(Str), PrintAfter);
618     return Capture.str();
619   };
620   EXPECT_EQ("hello", f("hello"));
621   EXPECT_EQ("c:\\\\", f("c:\\"));
622   EXPECT_EQ("\\\"hi\\\"", f("\"hi\""));
623   EXPECT_EQ("\\011a", f("\ta"));
624   EXPECT_EQ("\\0111", f("\t1"));
625   EXPECT_EQ("hello\\012", f("hello\n"));
626   EXPECT_EQ("hello\n", f("hello", "\n"));
627 }
628 #endif
629 
630 TEST(Corpus, Distribution) {
631   DataFlowTrace DFT;
632   Random Rand(0);
633   struct EntropicOptions Entropic = {false, 0xFF, 100, false};
634   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
635   size_t N = 10;
636   size_t TriesPerUnit = 1<<16;
637   for (size_t i = 0; i < N; i++)
638     C->AddToCorpus(Unit{static_cast<uint8_t>(i)}, /*NumFeatures*/ 1,
639                    /*MayDeleteFile*/ false, /*HasFocusFunction*/ false,
640                    /*ForceAddToCorpus*/ false,
641                    /*TimeOfUnit*/ std::chrono::microseconds(0),
642                    /*FeatureSet*/ {}, DFT,
643                    /*BaseII*/ nullptr);
644 
645   std::vector<size_t> Hist(N);
646   for (size_t i = 0; i < N * TriesPerUnit; i++) {
647     Hist[C->ChooseUnitIdxToMutate(Rand)]++;
648   }
649   for (size_t i = 0; i < N; i++) {
650     // A weak sanity check that every unit gets invoked.
651     EXPECT_GT(Hist[i], TriesPerUnit / N / 3);
652   }
653 }
654 
655 template <typename T>
656 void EQ(const std::vector<T> &A, const std::vector<T> &B) {
657   EXPECT_EQ(A, B);
658 }
659 
660 template <typename T> void EQ(const std::set<T> &A, const std::vector<T> &B) {
661   EXPECT_EQ(A, std::set<T>(B.begin(), B.end()));
662 }
663 
664 void EQ(const std::vector<MergeFileInfo> &A,
665         const std::vector<std::string> &B) {
666   std::set<std::string> a;
667   for (const auto &File : A)
668     a.insert(File.Name);
669   std::set<std::string> b(B.begin(), B.end());
670   EXPECT_EQ(a, b);
671 }
672 
673 #define TRACED_EQ(A, ...)                                                      \
674   {                                                                            \
675     SCOPED_TRACE(#A);                                                          \
676     EQ(A, __VA_ARGS__);                                                        \
677   }
678 
679 TEST(Merger, Parse) {
680   Merger M;
681 
682   const char *kInvalidInputs[] = {
683       // Bad file numbers
684       "",
685       "x",
686       "0\n0",
687       "3\nx",
688       "2\n3",
689       "2\n2",
690       // Bad file names
691       "2\n2\nA\n",
692       "2\n2\nA\nB\nC\n",
693       // Unknown markers
694       "2\n1\nA\nSTARTED 0\nBAD 0 0x0",
695       // Bad file IDs
696       "1\n1\nA\nSTARTED 1",
697       "2\n1\nA\nSTARTED 0\nFT 1 0x0",
698   };
699   for (auto S : kInvalidInputs) {
700     SCOPED_TRACE(S);
701     EXPECT_FALSE(M.Parse(S, false));
702   }
703 
704   // Parse initial control file
705   EXPECT_TRUE(M.Parse("1\n0\nAA\n", false));
706   ASSERT_EQ(M.Files.size(), 1U);
707   EXPECT_EQ(M.NumFilesInFirstCorpus, 0U);
708   EXPECT_EQ(M.Files[0].Name, "AA");
709   EXPECT_TRUE(M.LastFailure.empty());
710   EXPECT_EQ(M.FirstNotProcessedFile, 0U);
711 
712   // Parse control file that failed on first attempt
713   EXPECT_TRUE(M.Parse("2\n1\nAA\nBB\nSTARTED 0 42\n", false));
714   ASSERT_EQ(M.Files.size(), 2U);
715   EXPECT_EQ(M.NumFilesInFirstCorpus, 1U);
716   EXPECT_EQ(M.Files[0].Name, "AA");
717   EXPECT_EQ(M.Files[1].Name, "BB");
718   EXPECT_EQ(M.LastFailure, "AA");
719   EXPECT_EQ(M.FirstNotProcessedFile, 1U);
720 
721   // Parse control file that failed on later attempt
722   EXPECT_TRUE(M.Parse("3\n1\nAA\nBB\nC\n"
723                       "STARTED 0 1000\n"
724                       "FT 0 1 2 3\n"
725                       "STARTED 1 1001\n"
726                       "FT 1 4 5 6 \n"
727                       "STARTED 2 1002\n"
728                       "",
729                       true));
730   ASSERT_EQ(M.Files.size(), 3U);
731   EXPECT_EQ(M.NumFilesInFirstCorpus, 1U);
732   EXPECT_EQ(M.Files[0].Name, "AA");
733   EXPECT_EQ(M.Files[0].Size, 1000U);
734   EXPECT_EQ(M.Files[1].Name, "BB");
735   EXPECT_EQ(M.Files[1].Size, 1001U);
736   EXPECT_EQ(M.Files[2].Name, "C");
737   EXPECT_EQ(M.Files[2].Size, 1002U);
738   EXPECT_EQ(M.LastFailure, "C");
739   EXPECT_EQ(M.FirstNotProcessedFile, 3U);
740   TRACED_EQ(M.Files[0].Features, {1, 2, 3});
741   TRACED_EQ(M.Files[1].Features, {4, 5, 6});
742 
743   // Parse control file without features or PCs
744   EXPECT_TRUE(M.Parse("2\n0\nAA\nBB\n"
745                       "STARTED 0 1000\n"
746                       "FT 0\n"
747                       "COV 0\n"
748                       "STARTED 1 1001\n"
749                       "FT 1\n"
750                       "COV 1\n"
751                       "",
752                       true));
753   ASSERT_EQ(M.Files.size(), 2U);
754   EXPECT_EQ(M.NumFilesInFirstCorpus, 0U);
755   EXPECT_TRUE(M.LastFailure.empty());
756   EXPECT_EQ(M.FirstNotProcessedFile, 2U);
757   EXPECT_TRUE(M.Files[0].Features.empty());
758   EXPECT_TRUE(M.Files[0].Cov.empty());
759   EXPECT_TRUE(M.Files[1].Features.empty());
760   EXPECT_TRUE(M.Files[1].Cov.empty());
761 
762   // Parse features and PCs
763   EXPECT_TRUE(M.Parse("3\n2\nAA\nBB\nC\n"
764                       "STARTED 0 1000\n"
765                       "FT 0 1 2 3\n"
766                       "COV 0 11 12 13\n"
767                       "STARTED 1 1001\n"
768                       "FT 1 4 5 6\n"
769                       "COV 1 7 8 9\n"
770                       "STARTED 2 1002\n"
771                       "FT 2 6 1 3\n"
772                       "COV 2 16 11 13\n"
773                       "",
774                       true));
775   ASSERT_EQ(M.Files.size(), 3U);
776   EXPECT_EQ(M.NumFilesInFirstCorpus, 2U);
777   EXPECT_TRUE(M.LastFailure.empty());
778   EXPECT_EQ(M.FirstNotProcessedFile, 3U);
779   TRACED_EQ(M.Files[0].Features, {1, 2, 3});
780   TRACED_EQ(M.Files[0].Cov, {11, 12, 13});
781   TRACED_EQ(M.Files[1].Features, {4, 5, 6});
782   TRACED_EQ(M.Files[1].Cov, {7, 8, 9});
783   TRACED_EQ(M.Files[2].Features, {1, 3, 6});
784   TRACED_EQ(M.Files[2].Cov, {16});
785 }
786 
787 TEST(Merger, Merge) {
788   Merger M;
789   std::set<uint32_t> Features, NewFeatures;
790   std::set<uint32_t> Cov, NewCov;
791   std::vector<std::string> NewFiles;
792 
793   // Adds new files and features
794   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
795                       "STARTED 0 1000\n"
796                       "FT 0 1 2 3\n"
797                       "STARTED 1 1001\n"
798                       "FT 1 4 5 6 \n"
799                       "STARTED 2 1002\n"
800                       "FT 2 6 1 3\n"
801                       "",
802                       true));
803   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 6U);
804   TRACED_EQ(M.Files, {"A", "B", "C"});
805   TRACED_EQ(NewFiles, {"A", "B"});
806   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
807 
808   // Doesn't return features or files in the initial corpus.
809   EXPECT_TRUE(M.Parse("3\n1\nA\nB\nC\n"
810                       "STARTED 0 1000\n"
811                       "FT 0 1 2 3\n"
812                       "STARTED 1 1001\n"
813                       "FT 1 4 5 6 \n"
814                       "STARTED 2 1002\n"
815                       "FT 2 6 1 3\n"
816                       "",
817                       true));
818   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
819   TRACED_EQ(M.Files, {"A", "B", "C"});
820   TRACED_EQ(NewFiles, {"B"});
821   TRACED_EQ(NewFeatures, {4, 5, 6});
822 
823   // No new features, so no new files
824   EXPECT_TRUE(M.Parse("3\n2\nA\nB\nC\n"
825                       "STARTED 0 1000\n"
826                       "FT 0 1 2 3\n"
827                       "STARTED 1 1001\n"
828                       "FT 1 4 5 6 \n"
829                       "STARTED 2 1002\n"
830                       "FT 2 6 1 3\n"
831                       "",
832                       true));
833   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 0U);
834   TRACED_EQ(M.Files, {"A", "B", "C"});
835   TRACED_EQ(NewFiles, {});
836   TRACED_EQ(NewFeatures, {});
837 
838   // Can pass initial features and coverage.
839   Features = {1, 2, 3};
840   Cov = {};
841   EXPECT_TRUE(M.Parse("2\n0\nA\nB\n"
842                       "STARTED 0 1000\n"
843                       "FT 0 1 2 3\n"
844                       "STARTED 1 1001\n"
845                       "FT 1 4 5 6\n"
846                       "",
847                       true));
848   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
849   TRACED_EQ(M.Files, {"A", "B"});
850   TRACED_EQ(NewFiles, {"B"});
851   TRACED_EQ(NewFeatures, {4, 5, 6});
852   Features.clear();
853   Cov.clear();
854 
855   // Parse smaller files first
856   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
857                       "STARTED 0 2000\n"
858                       "FT 0 1 2 3\n"
859                       "STARTED 1 1001\n"
860                       "FT 1 4 5 6 \n"
861                       "STARTED 2 1002\n"
862                       "FT 2 6 1 3 \n"
863                       "",
864                       true));
865   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 6U);
866   TRACED_EQ(M.Files, {"B", "C", "A"});
867   TRACED_EQ(NewFiles, {"B", "C", "A"});
868   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
869 
870   EXPECT_TRUE(M.Parse("4\n0\nA\nB\nC\nD\n"
871                       "STARTED 0 2000\n"
872                       "FT 0 1 2 3\n"
873                       "STARTED 1 1101\n"
874                       "FT 1 4 5 6 \n"
875                       "STARTED 2 1102\n"
876                       "FT 2 6 1 3 100 \n"
877                       "STARTED 3 1000\n"
878                       "FT 3 1  \n"
879                       "",
880                       true));
881   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 7U);
882   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
883   TRACED_EQ(NewFiles, {"D", "B", "C", "A"});
884   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6, 100});
885 
886   // For same sized file, parse more features first
887   EXPECT_TRUE(M.Parse("4\n1\nA\nB\nC\nD\n"
888                       "STARTED 0 2000\n"
889                       "FT 0 4 5 6 7 8\n"
890                       "STARTED 1 1100\n"
891                       "FT 1 1 2 3 \n"
892                       "STARTED 2 1100\n"
893                       "FT 2 2 3 \n"
894                       "STARTED 3 1000\n"
895                       "FT 3 1  \n"
896                       "",
897                       true));
898   EXPECT_EQ(M.Merge(Features, &NewFeatures, Cov, &NewCov, &NewFiles), 3U);
899   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
900   TRACED_EQ(NewFiles, {"D", "B"});
901   TRACED_EQ(NewFeatures, {1, 2, 3});
902 }
903 
904 TEST(Merger, SetCoverMerge) {
905   Merger M;
906   std::set<uint32_t> Features, NewFeatures;
907   std::set<uint32_t> Cov, NewCov;
908   std::vector<std::string> NewFiles;
909 
910   // Adds new files and features
911   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
912                       "STARTED 0 1000\n"
913                       "FT 0 1 2 3\n"
914                       "STARTED 1 1001\n"
915                       "FT 1 4 5 6 \n"
916                       "STARTED 2 1002\n"
917                       "FT 2 6 1 3\n"
918                       "",
919                       true));
920   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
921             6U);
922   TRACED_EQ(M.Files, {"A", "B", "C"});
923   TRACED_EQ(NewFiles, {"A", "B"});
924   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
925 
926   // Doesn't return features or files in the initial corpus.
927   EXPECT_TRUE(M.Parse("3\n1\nA\nB\nC\n"
928                       "STARTED 0 1000\n"
929                       "FT 0 1 2 3\n"
930                       "STARTED 1 1001\n"
931                       "FT 1 4 5 6 \n"
932                       "STARTED 2 1002\n"
933                       "FT 2 6 1 3\n"
934                       "",
935                       true));
936   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
937             3U);
938   TRACED_EQ(M.Files, {"A", "B", "C"});
939   TRACED_EQ(NewFiles, {"B"});
940   TRACED_EQ(NewFeatures, {4, 5, 6});
941 
942   // No new features, so no new files
943   EXPECT_TRUE(M.Parse("3\n2\nA\nB\nC\n"
944                       "STARTED 0 1000\n"
945                       "FT 0 1 2 3\n"
946                       "STARTED 1 1001\n"
947                       "FT 1 4 5 6 \n"
948                       "STARTED 2 1002\n"
949                       "FT 2 6 1 3\n"
950                       "",
951                       true));
952   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
953             0U);
954   TRACED_EQ(M.Files, {"A", "B", "C"});
955   TRACED_EQ(NewFiles, {});
956   TRACED_EQ(NewFeatures, {});
957 
958   // Can pass initial features and coverage.
959   Features = {1, 2, 3};
960   Cov = {};
961   EXPECT_TRUE(M.Parse("2\n0\nA\nB\n"
962                       "STARTED 0 1000\n"
963                       "FT 0 1 2 3\n"
964                       "STARTED 1 1001\n"
965                       "FT 1 4 5 6\n"
966                       "",
967                       true));
968   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
969             3U);
970   TRACED_EQ(M.Files, {"A", "B"});
971   TRACED_EQ(NewFiles, {"B"});
972   TRACED_EQ(NewFeatures, {4, 5, 6});
973   Features.clear();
974   Cov.clear();
975 
976   // Prefer files with a lot of features first (C has 4 features)
977   // Then prefer B over A due to the smaller size. After choosing C and B,
978   // A and D have no new features to contribute.
979   EXPECT_TRUE(M.Parse("4\n0\nA\nB\nC\nD\n"
980                       "STARTED 0 2000\n"
981                       "FT 0 3 5 6\n"
982                       "STARTED 1 1000\n"
983                       "FT 1 4 5 6 \n"
984                       "STARTED 2 1000\n"
985                       "FT 2 1 2 3 4 \n"
986                       "STARTED 3 500\n"
987                       "FT 3 1  \n"
988                       "",
989                       true));
990   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
991             6U);
992   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
993   TRACED_EQ(NewFiles, {"C", "B"});
994   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
995 
996   // Only 1 file covers all features.
997   EXPECT_TRUE(M.Parse("4\n1\nA\nB\nC\nD\n"
998                       "STARTED 0 2000\n"
999                       "FT 0 4 5 6 7 8\n"
1000                       "STARTED 1 1100\n"
1001                       "FT 1 1 2 3 \n"
1002                       "STARTED 2 1100\n"
1003                       "FT 2 2 3 \n"
1004                       "STARTED 3 1000\n"
1005                       "FT 3 1  \n"
1006                       "",
1007                       true));
1008   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
1009             3U);
1010   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
1011   TRACED_EQ(NewFiles, {"B"});
1012   TRACED_EQ(NewFeatures, {1, 2, 3});
1013 
1014   // A Feature has a value greater than (1 << 21) and hence
1015   // there are collisions in the underlying `covered features`
1016   // bitvector.
1017   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
1018                       "STARTED 0 2000\n"
1019                       "FT 0 1 2 3\n"
1020                       "STARTED 1 1000\n"
1021                       "FT 1 3 4 5 \n"
1022                       "STARTED 2 1000\n"
1023                       "FT 2 3 2097153 \n" // Last feature is (2^21 + 1).
1024                       "",
1025                       true));
1026   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
1027             5U);
1028   TRACED_EQ(M.Files, {"A", "B", "C"});
1029   // File 'C' is not added because it's last feature is considered
1030   // covered due to collision with feature 1.
1031   TRACED_EQ(NewFiles, {"B", "A"});
1032   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5});
1033 }
1034 
1035 #undef TRACED_EQ
1036 
1037 TEST(DFT, BlockCoverage) {
1038   BlockCoverage Cov;
1039   // Assuming C0 has 5 instrumented blocks,
1040   // C1: 7 blocks, C2: 4, C3: 9, C4 never covered, C5: 15,
1041 
1042   // Add C0
1043   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
1044   EXPECT_EQ(Cov.GetCounter(0, 0), 1U);
1045   EXPECT_EQ(Cov.GetCounter(0, 1), 0U);  // not seen this BB yet.
1046   EXPECT_EQ(Cov.GetCounter(0, 5), 0U);  // BB ID out of bounds.
1047   EXPECT_EQ(Cov.GetCounter(1, 0), 0U);  // not seen this function yet.
1048 
1049   EXPECT_EQ(Cov.GetNumberOfBlocks(0), 5U);
1050   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 1U);
1051   EXPECT_EQ(Cov.GetNumberOfBlocks(1), 0U);
1052 
1053   // Various errors.
1054   EXPECT_FALSE(Cov.AppendCoverage("C0\n"));  // No total number.
1055   EXPECT_FALSE(Cov.AppendCoverage("C0 7\n"));  // No total number.
1056   EXPECT_FALSE(Cov.AppendCoverage("CZ\n"));  // Wrong function number.
1057   EXPECT_FALSE(Cov.AppendCoverage("C1 7 7"));  // BB ID is too big.
1058   EXPECT_FALSE(Cov.AppendCoverage("C1 100 7")); // BB ID is too big.
1059 
1060   // Add C0 more times.
1061   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
1062   EXPECT_EQ(Cov.GetCounter(0, 0), 2U);
1063   EXPECT_TRUE(Cov.AppendCoverage("C0 1 2 5\n"));
1064   EXPECT_EQ(Cov.GetCounter(0, 0), 3U);
1065   EXPECT_EQ(Cov.GetCounter(0, 1), 1U);
1066   EXPECT_EQ(Cov.GetCounter(0, 2), 1U);
1067   EXPECT_EQ(Cov.GetCounter(0, 3), 0U);
1068   EXPECT_EQ(Cov.GetCounter(0, 4), 0U);
1069   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 3U);
1070   EXPECT_TRUE(Cov.AppendCoverage("C0 1 3 4 5\n"));
1071   EXPECT_EQ(Cov.GetCounter(0, 0), 4U);
1072   EXPECT_EQ(Cov.GetCounter(0, 1), 2U);
1073   EXPECT_EQ(Cov.GetCounter(0, 2), 1U);
1074   EXPECT_EQ(Cov.GetCounter(0, 3), 1U);
1075   EXPECT_EQ(Cov.GetCounter(0, 4), 1U);
1076   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 5U);
1077 
1078   EXPECT_TRUE(Cov.AppendCoverage("C1 7\nC2 4\nC3 9\nC5 15\nC0 5\n"));
1079   EXPECT_EQ(Cov.GetCounter(0, 0), 5U);
1080   EXPECT_EQ(Cov.GetCounter(1, 0), 1U);
1081   EXPECT_EQ(Cov.GetCounter(2, 0), 1U);
1082   EXPECT_EQ(Cov.GetCounter(3, 0), 1U);
1083   EXPECT_EQ(Cov.GetCounter(4, 0), 0U);
1084   EXPECT_EQ(Cov.GetCounter(5, 0), 1U);
1085 
1086   EXPECT_TRUE(Cov.AppendCoverage("C3 4 5 9\nC5 11 12 15"));
1087   EXPECT_EQ(Cov.GetCounter(0, 0), 5U);
1088   EXPECT_EQ(Cov.GetCounter(1, 0), 1U);
1089   EXPECT_EQ(Cov.GetCounter(2, 0), 1U);
1090   EXPECT_EQ(Cov.GetCounter(3, 0), 2U);
1091   EXPECT_EQ(Cov.GetCounter(3, 4), 1U);
1092   EXPECT_EQ(Cov.GetCounter(3, 5), 1U);
1093   EXPECT_EQ(Cov.GetCounter(3, 6), 0U);
1094   EXPECT_EQ(Cov.GetCounter(4, 0), 0U);
1095   EXPECT_EQ(Cov.GetCounter(5, 0), 2U);
1096   EXPECT_EQ(Cov.GetCounter(5, 10), 0U);
1097   EXPECT_EQ(Cov.GetCounter(5, 11), 1U);
1098   EXPECT_EQ(Cov.GetCounter(5, 12), 1U);
1099 }
1100 
1101 TEST(DFT, FunctionWeights) {
1102   BlockCoverage Cov;
1103   // unused function gets zero weight.
1104   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
1105   auto Weights = Cov.FunctionWeights(2);
1106   EXPECT_GT(Weights[0], 0.);
1107   EXPECT_EQ(Weights[1], 0.);
1108 
1109   // Less frequently used function gets less weight.
1110   Cov.clear();
1111   EXPECT_TRUE(Cov.AppendCoverage("C0 5\nC1 5\nC1 5\n"));
1112   Weights = Cov.FunctionWeights(2);
1113   EXPECT_GT(Weights[0], Weights[1]);
1114 
1115   // A function with more uncovered blocks gets more weight.
1116   Cov.clear();
1117   EXPECT_TRUE(Cov.AppendCoverage("C0 1 2 3 5\nC1 2 4\n"));
1118   Weights = Cov.FunctionWeights(2);
1119   EXPECT_GT(Weights[1], Weights[0]);
1120 
1121   // A function with DFT gets more weight than the function w/o DFT.
1122   Cov.clear();
1123   EXPECT_TRUE(Cov.AppendCoverage("F1 111\nC0 3\nC1 1 2 3\n"));
1124   Weights = Cov.FunctionWeights(2);
1125   EXPECT_GT(Weights[1], Weights[0]);
1126 }
1127 
1128 
1129 TEST(Fuzzer, ForEachNonZeroByte) {
1130   const size_t N = 64;
1131   alignas(64) uint8_t Ar[N + 8] = {
1132     0, 0, 0, 0, 0, 0, 0, 0,
1133     1, 2, 0, 0, 0, 0, 0, 0,
1134     0, 0, 3, 0, 4, 0, 0, 0,
1135     0, 0, 0, 0, 0, 0, 0, 0,
1136     0, 0, 0, 5, 0, 6, 0, 0,
1137     0, 0, 0, 0, 0, 0, 7, 0,
1138     0, 0, 0, 0, 0, 0, 0, 0,
1139     0, 0, 0, 0, 0, 0, 0, 8,
1140     9, 9, 9, 9, 9, 9, 9, 9,
1141   };
1142   typedef std::vector<std::pair<size_t, uint8_t>> Vec;
1143   Vec Res, Expected;
1144   auto CB = [&](size_t FirstFeature, size_t Idx, uint8_t V) {
1145     Res.push_back({FirstFeature + Idx, V});
1146   };
1147   ForEachNonZeroByte(Ar, Ar + N, 100, CB);
1148   Expected = {{108, 1}, {109, 2}, {118, 3}, {120, 4},
1149               {135, 5}, {137, 6}, {146, 7}, {163, 8}};
1150   EXPECT_EQ(Res, Expected);
1151 
1152   Res.clear();
1153   ForEachNonZeroByte(Ar + 9, Ar + N, 109, CB);
1154   Expected = {          {109, 2}, {118, 3}, {120, 4},
1155               {135, 5}, {137, 6}, {146, 7}, {163, 8}};
1156   EXPECT_EQ(Res, Expected);
1157 
1158   Res.clear();
1159   ForEachNonZeroByte(Ar + 9, Ar + N - 9, 109, CB);
1160   Expected = {          {109, 2}, {118, 3}, {120, 4},
1161               {135, 5}, {137, 6}, {146, 7}};
1162   EXPECT_EQ(Res, Expected);
1163 }
1164 
1165 // FuzzerCommand unit tests. The arguments in the two helper methods below must
1166 // match.
1167 static void makeCommandArgs(std::vector<std::string> *ArgsToAdd) {
1168   assert(ArgsToAdd);
1169   ArgsToAdd->clear();
1170   ArgsToAdd->push_back("foo");
1171   ArgsToAdd->push_back("-bar=baz");
1172   ArgsToAdd->push_back("qux");
1173   ArgsToAdd->push_back(Command::ignoreRemainingArgs());
1174   ArgsToAdd->push_back("quux");
1175   ArgsToAdd->push_back("-grault=garply");
1176 }
1177 
1178 static std::string makeCmdLine(const char *separator, const char *suffix) {
1179   std::string CmdLine("foo -bar=baz qux ");
1180   if (strlen(separator) != 0) {
1181     CmdLine += separator;
1182     CmdLine += " ";
1183   }
1184   CmdLine += Command::ignoreRemainingArgs();
1185   CmdLine += " quux -grault=garply";
1186   if (strlen(suffix) != 0) {
1187     CmdLine += " ";
1188     CmdLine += suffix;
1189   }
1190   return CmdLine;
1191 }
1192 
1193 TEST(FuzzerCommand, Create) {
1194   std::string CmdLine;
1195 
1196   // Default constructor
1197   Command DefaultCmd;
1198 
1199   CmdLine = DefaultCmd.toString();
1200   EXPECT_EQ(CmdLine, "");
1201 
1202   // Explicit constructor
1203   std::vector<std::string> ArgsToAdd;
1204   makeCommandArgs(&ArgsToAdd);
1205   Command InitializedCmd(ArgsToAdd);
1206 
1207   CmdLine = InitializedCmd.toString();
1208   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1209 
1210   // Compare each argument
1211   auto InitializedArgs = InitializedCmd.getArguments();
1212   auto i = ArgsToAdd.begin();
1213   auto j = InitializedArgs.begin();
1214   while (i != ArgsToAdd.end() && j != InitializedArgs.end()) {
1215     EXPECT_EQ(*i++, *j++);
1216   }
1217   EXPECT_EQ(i, ArgsToAdd.end());
1218   EXPECT_EQ(j, InitializedArgs.end());
1219 
1220   // Copy constructor
1221   Command CopiedCmd(InitializedCmd);
1222 
1223   CmdLine = CopiedCmd.toString();
1224   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1225 
1226   // Assignment operator
1227   Command AssignedCmd;
1228   AssignedCmd = CopiedCmd;
1229 
1230   CmdLine = AssignedCmd.toString();
1231   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1232 }
1233 
1234 TEST(FuzzerCommand, ModifyArguments) {
1235   std::vector<std::string> ArgsToAdd;
1236   makeCommandArgs(&ArgsToAdd);
1237   Command Cmd;
1238   std::string CmdLine;
1239 
1240   Cmd.addArguments(ArgsToAdd);
1241   CmdLine = Cmd.toString();
1242   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1243 
1244   Cmd.addArgument("waldo");
1245   EXPECT_TRUE(Cmd.hasArgument("waldo"));
1246 
1247   CmdLine = Cmd.toString();
1248   EXPECT_EQ(CmdLine, makeCmdLine("waldo", ""));
1249 
1250   Cmd.removeArgument("waldo");
1251   EXPECT_FALSE(Cmd.hasArgument("waldo"));
1252 
1253   CmdLine = Cmd.toString();
1254   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1255 }
1256 
1257 TEST(FuzzerCommand, ModifyFlags) {
1258   std::vector<std::string> ArgsToAdd;
1259   makeCommandArgs(&ArgsToAdd);
1260   Command Cmd(ArgsToAdd);
1261   std::string Value, CmdLine;
1262   ASSERT_FALSE(Cmd.hasFlag("fred"));
1263 
1264   Value = Cmd.getFlagValue("fred");
1265   EXPECT_EQ(Value, "");
1266 
1267   CmdLine = Cmd.toString();
1268   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1269 
1270   Cmd.addFlag("fred", "plugh");
1271   EXPECT_TRUE(Cmd.hasFlag("fred"));
1272 
1273   Value = Cmd.getFlagValue("fred");
1274   EXPECT_EQ(Value, "plugh");
1275 
1276   CmdLine = Cmd.toString();
1277   EXPECT_EQ(CmdLine, makeCmdLine("-fred=plugh", ""));
1278 
1279   Cmd.removeFlag("fred");
1280   EXPECT_FALSE(Cmd.hasFlag("fred"));
1281 
1282   Value = Cmd.getFlagValue("fred");
1283   EXPECT_EQ(Value, "");
1284 
1285   CmdLine = Cmd.toString();
1286   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1287 }
1288 
1289 TEST(FuzzerCommand, SetOutput) {
1290   std::vector<std::string> ArgsToAdd;
1291   makeCommandArgs(&ArgsToAdd);
1292   Command Cmd(ArgsToAdd);
1293   std::string CmdLine;
1294   ASSERT_FALSE(Cmd.hasOutputFile());
1295   ASSERT_FALSE(Cmd.isOutAndErrCombined());
1296 
1297   Cmd.combineOutAndErr(true);
1298   EXPECT_TRUE(Cmd.isOutAndErrCombined());
1299 
1300   CmdLine = Cmd.toString();
1301   EXPECT_EQ(CmdLine, makeCmdLine("", "2>&1"));
1302 
1303   Cmd.combineOutAndErr(false);
1304   EXPECT_FALSE(Cmd.isOutAndErrCombined());
1305 
1306   Cmd.setOutputFile("xyzzy");
1307   EXPECT_TRUE(Cmd.hasOutputFile());
1308 
1309   CmdLine = Cmd.toString();
1310   EXPECT_EQ(CmdLine, makeCmdLine("", ">xyzzy"));
1311 
1312   Cmd.setOutputFile("thud");
1313   EXPECT_TRUE(Cmd.hasOutputFile());
1314 
1315   CmdLine = Cmd.toString();
1316   EXPECT_EQ(CmdLine, makeCmdLine("", ">thud"));
1317 
1318   Cmd.combineOutAndErr();
1319   EXPECT_TRUE(Cmd.isOutAndErrCombined());
1320 
1321   CmdLine = Cmd.toString();
1322   EXPECT_EQ(CmdLine, makeCmdLine("", ">thud 2>&1"));
1323 }
1324 
1325 TEST(Entropic, UpdateFrequency) {
1326   const size_t One = 1, Two = 2;
1327   const size_t FeatIdx1 = 0, FeatIdx2 = 42, FeatIdx3 = 12, FeatIdx4 = 26;
1328   size_t Index;
1329   // Create input corpus with default entropic configuration
1330   struct EntropicOptions Entropic = {true, 0xFF, 100, false};
1331   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
1332   std::unique_ptr<InputInfo> II(new InputInfo());
1333 
1334   C->AddRareFeature(FeatIdx1);
1335   C->UpdateFeatureFrequency(II.get(), FeatIdx1);
1336   EXPECT_EQ(II->FeatureFreqs.size(), One);
1337   C->AddRareFeature(FeatIdx2);
1338   C->UpdateFeatureFrequency(II.get(), FeatIdx1);
1339   C->UpdateFeatureFrequency(II.get(), FeatIdx2);
1340   EXPECT_EQ(II->FeatureFreqs.size(), Two);
1341   EXPECT_EQ(II->FeatureFreqs[0].second, 2);
1342   EXPECT_EQ(II->FeatureFreqs[1].second, 1);
1343 
1344   C->AddRareFeature(FeatIdx3);
1345   C->AddRareFeature(FeatIdx4);
1346   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1347   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1348   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1349   C->UpdateFeatureFrequency(II.get(), FeatIdx4);
1350 
1351   for (Index = 1; Index < II->FeatureFreqs.size(); Index++)
1352     EXPECT_LT(II->FeatureFreqs[Index - 1].first, II->FeatureFreqs[Index].first);
1353 
1354   II->DeleteFeatureFreq(FeatIdx3);
1355   for (Index = 1; Index < II->FeatureFreqs.size(); Index++)
1356     EXPECT_LT(II->FeatureFreqs[Index - 1].first, II->FeatureFreqs[Index].first);
1357 }
1358 
1359 double SubAndSquare(double X, double Y) {
1360   double R = X - Y;
1361   R = R * R;
1362   return R;
1363 }
1364 
1365 TEST(Entropic, ComputeEnergy) {
1366   const double Precision = 0.01;
1367   struct EntropicOptions Entropic = {true, 0xFF, 100, false};
1368   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
1369   std::unique_ptr<InputInfo> II(new InputInfo());
1370   std::vector<std::pair<uint32_t, uint16_t>> FeatureFreqs = {
1371       {1, 3}, {2, 3}, {3, 3}};
1372   II->FeatureFreqs = FeatureFreqs;
1373   II->NumExecutedMutations = 0;
1374   II->UpdateEnergy(4, false, std::chrono::microseconds(0));
1375   EXPECT_LT(SubAndSquare(II->Energy, 1.450805), Precision);
1376 
1377   II->NumExecutedMutations = 9;
1378   II->UpdateEnergy(5, false, std::chrono::microseconds(0));
1379   EXPECT_LT(SubAndSquare(II->Energy, 1.525496), Precision);
1380 
1381   II->FeatureFreqs[0].second++;
1382   II->FeatureFreqs.push_back(std::pair<uint32_t, uint16_t>(42, 6));
1383   II->NumExecutedMutations = 20;
1384   II->UpdateEnergy(10, false, std::chrono::microseconds(0));
1385   EXPECT_LT(SubAndSquare(II->Energy, 1.792831), Precision);
1386 }
1387 
1388 int main(int argc, char **argv) {
1389   testing::InitGoogleTest(&argc, argv);
1390   return RUN_ALL_TESTS();
1391 }
1392