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 TEST(Merger, SetCoverMerge) {
869   Merger M;
870   std::set<uint32_t> Features, NewFeatures;
871   std::set<uint32_t> Cov, NewCov;
872   std::vector<std::string> NewFiles;
873 
874   // Adds new files and features
875   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
876                       "STARTED 0 1000\n"
877                       "FT 0 1 2 3\n"
878                       "STARTED 1 1001\n"
879                       "FT 1 4 5 6 \n"
880                       "STARTED 2 1002\n"
881                       "FT 2 6 1 3\n"
882                       "",
883                       true));
884   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
885             6U);
886   TRACED_EQ(M.Files, {"A", "B", "C"});
887   TRACED_EQ(NewFiles, {"A", "B"});
888   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
889 
890   // Doesn't return features or files in the initial corpus.
891   EXPECT_TRUE(M.Parse("3\n1\nA\nB\nC\n"
892                       "STARTED 0 1000\n"
893                       "FT 0 1 2 3\n"
894                       "STARTED 1 1001\n"
895                       "FT 1 4 5 6 \n"
896                       "STARTED 2 1002\n"
897                       "FT 2 6 1 3\n"
898                       "",
899                       true));
900   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
901             3U);
902   TRACED_EQ(M.Files, {"A", "B", "C"});
903   TRACED_EQ(NewFiles, {"B"});
904   TRACED_EQ(NewFeatures, {4, 5, 6});
905 
906   // No new features, so no new files
907   EXPECT_TRUE(M.Parse("3\n2\nA\nB\nC\n"
908                       "STARTED 0 1000\n"
909                       "FT 0 1 2 3\n"
910                       "STARTED 1 1001\n"
911                       "FT 1 4 5 6 \n"
912                       "STARTED 2 1002\n"
913                       "FT 2 6 1 3\n"
914                       "",
915                       true));
916   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
917             0U);
918   TRACED_EQ(M.Files, {"A", "B", "C"});
919   TRACED_EQ(NewFiles, {});
920   TRACED_EQ(NewFeatures, {});
921 
922   // Can pass initial features and coverage.
923   Features = {1, 2, 3};
924   Cov = {};
925   EXPECT_TRUE(M.Parse("2\n0\nA\nB\n"
926                       "STARTED 0 1000\n"
927                       "FT 0 1 2 3\n"
928                       "STARTED 1 1001\n"
929                       "FT 1 4 5 6\n"
930                       "",
931                       true));
932   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
933             3U);
934   TRACED_EQ(M.Files, {"A", "B"});
935   TRACED_EQ(NewFiles, {"B"});
936   TRACED_EQ(NewFeatures, {4, 5, 6});
937   Features.clear();
938   Cov.clear();
939 
940   // Prefer files with a lot of features first (C has 4 features)
941   // Then prefer B over A due to the smaller size. After choosing C and B,
942   // A and D have no new features to contribute.
943   EXPECT_TRUE(M.Parse("4\n0\nA\nB\nC\nD\n"
944                       "STARTED 0 2000\n"
945                       "FT 0 3 5 6\n"
946                       "STARTED 1 1000\n"
947                       "FT 1 4 5 6 \n"
948                       "STARTED 2 1000\n"
949                       "FT 2 1 2 3 4 \n"
950                       "STARTED 3 500\n"
951                       "FT 3 1  \n"
952                       "",
953                       true));
954   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
955             6U);
956   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
957   TRACED_EQ(NewFiles, {"C", "B"});
958   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5, 6});
959 
960   // Only 1 file covers all features.
961   EXPECT_TRUE(M.Parse("4\n1\nA\nB\nC\nD\n"
962                       "STARTED 0 2000\n"
963                       "FT 0 4 5 6 7 8\n"
964                       "STARTED 1 1100\n"
965                       "FT 1 1 2 3 \n"
966                       "STARTED 2 1100\n"
967                       "FT 2 2 3 \n"
968                       "STARTED 3 1000\n"
969                       "FT 3 1  \n"
970                       "",
971                       true));
972   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
973             3U);
974   TRACED_EQ(M.Files, {"A", "B", "C", "D"});
975   TRACED_EQ(NewFiles, {"B"});
976   TRACED_EQ(NewFeatures, {1, 2, 3});
977 
978   // A Feature has a value greater than (1 << 21) and hence
979   // there are collisions in the underlying `covered features`
980   // bitvector.
981   EXPECT_TRUE(M.Parse("3\n0\nA\nB\nC\n"
982                       "STARTED 0 2000\n"
983                       "FT 0 1 2 3\n"
984                       "STARTED 1 1000\n"
985                       "FT 1 3 4 5 \n"
986                       "STARTED 2 1000\n"
987                       "FT 2 3 2097153 \n" // Last feature is (2^21 + 1).
988                       "",
989                       true));
990   EXPECT_EQ(M.SetCoverMerge(Features, &NewFeatures, Cov, &NewCov, &NewFiles),
991             5U);
992   TRACED_EQ(M.Files, {"A", "B", "C"});
993   // File 'C' is not added because it's last feature is considered
994   // covered due to collision with feature 1.
995   TRACED_EQ(NewFiles, {"B", "A"});
996   TRACED_EQ(NewFeatures, {1, 2, 3, 4, 5});
997 }
998 
999 #undef TRACED_EQ
1000 
1001 TEST(DFT, BlockCoverage) {
1002   BlockCoverage Cov;
1003   // Assuming C0 has 5 instrumented blocks,
1004   // C1: 7 blocks, C2: 4, C3: 9, C4 never covered, C5: 15,
1005 
1006   // Add C0
1007   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
1008   EXPECT_EQ(Cov.GetCounter(0, 0), 1U);
1009   EXPECT_EQ(Cov.GetCounter(0, 1), 0U);  // not seen this BB yet.
1010   EXPECT_EQ(Cov.GetCounter(0, 5), 0U);  // BB ID out of bounds.
1011   EXPECT_EQ(Cov.GetCounter(1, 0), 0U);  // not seen this function yet.
1012 
1013   EXPECT_EQ(Cov.GetNumberOfBlocks(0), 5U);
1014   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 1U);
1015   EXPECT_EQ(Cov.GetNumberOfBlocks(1), 0U);
1016 
1017   // Various errors.
1018   EXPECT_FALSE(Cov.AppendCoverage("C0\n"));  // No total number.
1019   EXPECT_FALSE(Cov.AppendCoverage("C0 7\n"));  // No total number.
1020   EXPECT_FALSE(Cov.AppendCoverage("CZ\n"));  // Wrong function number.
1021   EXPECT_FALSE(Cov.AppendCoverage("C1 7 7"));  // BB ID is too big.
1022   EXPECT_FALSE(Cov.AppendCoverage("C1 100 7")); // BB ID is too big.
1023 
1024   // Add C0 more times.
1025   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
1026   EXPECT_EQ(Cov.GetCounter(0, 0), 2U);
1027   EXPECT_TRUE(Cov.AppendCoverage("C0 1 2 5\n"));
1028   EXPECT_EQ(Cov.GetCounter(0, 0), 3U);
1029   EXPECT_EQ(Cov.GetCounter(0, 1), 1U);
1030   EXPECT_EQ(Cov.GetCounter(0, 2), 1U);
1031   EXPECT_EQ(Cov.GetCounter(0, 3), 0U);
1032   EXPECT_EQ(Cov.GetCounter(0, 4), 0U);
1033   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 3U);
1034   EXPECT_TRUE(Cov.AppendCoverage("C0 1 3 4 5\n"));
1035   EXPECT_EQ(Cov.GetCounter(0, 0), 4U);
1036   EXPECT_EQ(Cov.GetCounter(0, 1), 2U);
1037   EXPECT_EQ(Cov.GetCounter(0, 2), 1U);
1038   EXPECT_EQ(Cov.GetCounter(0, 3), 1U);
1039   EXPECT_EQ(Cov.GetCounter(0, 4), 1U);
1040   EXPECT_EQ(Cov.GetNumberOfCoveredBlocks(0), 5U);
1041 
1042   EXPECT_TRUE(Cov.AppendCoverage("C1 7\nC2 4\nC3 9\nC5 15\nC0 5\n"));
1043   EXPECT_EQ(Cov.GetCounter(0, 0), 5U);
1044   EXPECT_EQ(Cov.GetCounter(1, 0), 1U);
1045   EXPECT_EQ(Cov.GetCounter(2, 0), 1U);
1046   EXPECT_EQ(Cov.GetCounter(3, 0), 1U);
1047   EXPECT_EQ(Cov.GetCounter(4, 0), 0U);
1048   EXPECT_EQ(Cov.GetCounter(5, 0), 1U);
1049 
1050   EXPECT_TRUE(Cov.AppendCoverage("C3 4 5 9\nC5 11 12 15"));
1051   EXPECT_EQ(Cov.GetCounter(0, 0), 5U);
1052   EXPECT_EQ(Cov.GetCounter(1, 0), 1U);
1053   EXPECT_EQ(Cov.GetCounter(2, 0), 1U);
1054   EXPECT_EQ(Cov.GetCounter(3, 0), 2U);
1055   EXPECT_EQ(Cov.GetCounter(3, 4), 1U);
1056   EXPECT_EQ(Cov.GetCounter(3, 5), 1U);
1057   EXPECT_EQ(Cov.GetCounter(3, 6), 0U);
1058   EXPECT_EQ(Cov.GetCounter(4, 0), 0U);
1059   EXPECT_EQ(Cov.GetCounter(5, 0), 2U);
1060   EXPECT_EQ(Cov.GetCounter(5, 10), 0U);
1061   EXPECT_EQ(Cov.GetCounter(5, 11), 1U);
1062   EXPECT_EQ(Cov.GetCounter(5, 12), 1U);
1063 }
1064 
1065 TEST(DFT, FunctionWeights) {
1066   BlockCoverage Cov;
1067   // unused function gets zero weight.
1068   EXPECT_TRUE(Cov.AppendCoverage("C0 5\n"));
1069   auto Weights = Cov.FunctionWeights(2);
1070   EXPECT_GT(Weights[0], 0.);
1071   EXPECT_EQ(Weights[1], 0.);
1072 
1073   // Less frequently used function gets less weight.
1074   Cov.clear();
1075   EXPECT_TRUE(Cov.AppendCoverage("C0 5\nC1 5\nC1 5\n"));
1076   Weights = Cov.FunctionWeights(2);
1077   EXPECT_GT(Weights[0], Weights[1]);
1078 
1079   // A function with more uncovered blocks gets more weight.
1080   Cov.clear();
1081   EXPECT_TRUE(Cov.AppendCoverage("C0 1 2 3 5\nC1 2 4\n"));
1082   Weights = Cov.FunctionWeights(2);
1083   EXPECT_GT(Weights[1], Weights[0]);
1084 
1085   // A function with DFT gets more weight than the function w/o DFT.
1086   Cov.clear();
1087   EXPECT_TRUE(Cov.AppendCoverage("F1 111\nC0 3\nC1 1 2 3\n"));
1088   Weights = Cov.FunctionWeights(2);
1089   EXPECT_GT(Weights[1], Weights[0]);
1090 }
1091 
1092 
1093 TEST(Fuzzer, ForEachNonZeroByte) {
1094   const size_t N = 64;
1095   alignas(64) uint8_t Ar[N + 8] = {
1096     0, 0, 0, 0, 0, 0, 0, 0,
1097     1, 2, 0, 0, 0, 0, 0, 0,
1098     0, 0, 3, 0, 4, 0, 0, 0,
1099     0, 0, 0, 0, 0, 0, 0, 0,
1100     0, 0, 0, 5, 0, 6, 0, 0,
1101     0, 0, 0, 0, 0, 0, 7, 0,
1102     0, 0, 0, 0, 0, 0, 0, 0,
1103     0, 0, 0, 0, 0, 0, 0, 8,
1104     9, 9, 9, 9, 9, 9, 9, 9,
1105   };
1106   typedef std::vector<std::pair<size_t, uint8_t>> Vec;
1107   Vec Res, Expected;
1108   auto CB = [&](size_t FirstFeature, size_t Idx, uint8_t V) {
1109     Res.push_back({FirstFeature + Idx, V});
1110   };
1111   ForEachNonZeroByte(Ar, Ar + N, 100, CB);
1112   Expected = {{108, 1}, {109, 2}, {118, 3}, {120, 4},
1113               {135, 5}, {137, 6}, {146, 7}, {163, 8}};
1114   EXPECT_EQ(Res, Expected);
1115 
1116   Res.clear();
1117   ForEachNonZeroByte(Ar + 9, Ar + N, 109, CB);
1118   Expected = {          {109, 2}, {118, 3}, {120, 4},
1119               {135, 5}, {137, 6}, {146, 7}, {163, 8}};
1120   EXPECT_EQ(Res, Expected);
1121 
1122   Res.clear();
1123   ForEachNonZeroByte(Ar + 9, Ar + N - 9, 109, CB);
1124   Expected = {          {109, 2}, {118, 3}, {120, 4},
1125               {135, 5}, {137, 6}, {146, 7}};
1126   EXPECT_EQ(Res, Expected);
1127 }
1128 
1129 // FuzzerCommand unit tests. The arguments in the two helper methods below must
1130 // match.
1131 static void makeCommandArgs(std::vector<std::string> *ArgsToAdd) {
1132   assert(ArgsToAdd);
1133   ArgsToAdd->clear();
1134   ArgsToAdd->push_back("foo");
1135   ArgsToAdd->push_back("-bar=baz");
1136   ArgsToAdd->push_back("qux");
1137   ArgsToAdd->push_back(Command::ignoreRemainingArgs());
1138   ArgsToAdd->push_back("quux");
1139   ArgsToAdd->push_back("-grault=garply");
1140 }
1141 
1142 static std::string makeCmdLine(const char *separator, const char *suffix) {
1143   std::string CmdLine("foo -bar=baz qux ");
1144   if (strlen(separator) != 0) {
1145     CmdLine += separator;
1146     CmdLine += " ";
1147   }
1148   CmdLine += Command::ignoreRemainingArgs();
1149   CmdLine += " quux -grault=garply";
1150   if (strlen(suffix) != 0) {
1151     CmdLine += " ";
1152     CmdLine += suffix;
1153   }
1154   return CmdLine;
1155 }
1156 
1157 TEST(FuzzerCommand, Create) {
1158   std::string CmdLine;
1159 
1160   // Default constructor
1161   Command DefaultCmd;
1162 
1163   CmdLine = DefaultCmd.toString();
1164   EXPECT_EQ(CmdLine, "");
1165 
1166   // Explicit constructor
1167   std::vector<std::string> ArgsToAdd;
1168   makeCommandArgs(&ArgsToAdd);
1169   Command InitializedCmd(ArgsToAdd);
1170 
1171   CmdLine = InitializedCmd.toString();
1172   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1173 
1174   // Compare each argument
1175   auto InitializedArgs = InitializedCmd.getArguments();
1176   auto i = ArgsToAdd.begin();
1177   auto j = InitializedArgs.begin();
1178   while (i != ArgsToAdd.end() && j != InitializedArgs.end()) {
1179     EXPECT_EQ(*i++, *j++);
1180   }
1181   EXPECT_EQ(i, ArgsToAdd.end());
1182   EXPECT_EQ(j, InitializedArgs.end());
1183 
1184   // Copy constructor
1185   Command CopiedCmd(InitializedCmd);
1186 
1187   CmdLine = CopiedCmd.toString();
1188   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1189 
1190   // Assignment operator
1191   Command AssignedCmd;
1192   AssignedCmd = CopiedCmd;
1193 
1194   CmdLine = AssignedCmd.toString();
1195   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1196 }
1197 
1198 TEST(FuzzerCommand, ModifyArguments) {
1199   std::vector<std::string> ArgsToAdd;
1200   makeCommandArgs(&ArgsToAdd);
1201   Command Cmd;
1202   std::string CmdLine;
1203 
1204   Cmd.addArguments(ArgsToAdd);
1205   CmdLine = Cmd.toString();
1206   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1207 
1208   Cmd.addArgument("waldo");
1209   EXPECT_TRUE(Cmd.hasArgument("waldo"));
1210 
1211   CmdLine = Cmd.toString();
1212   EXPECT_EQ(CmdLine, makeCmdLine("waldo", ""));
1213 
1214   Cmd.removeArgument("waldo");
1215   EXPECT_FALSE(Cmd.hasArgument("waldo"));
1216 
1217   CmdLine = Cmd.toString();
1218   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1219 }
1220 
1221 TEST(FuzzerCommand, ModifyFlags) {
1222   std::vector<std::string> ArgsToAdd;
1223   makeCommandArgs(&ArgsToAdd);
1224   Command Cmd(ArgsToAdd);
1225   std::string Value, CmdLine;
1226   ASSERT_FALSE(Cmd.hasFlag("fred"));
1227 
1228   Value = Cmd.getFlagValue("fred");
1229   EXPECT_EQ(Value, "");
1230 
1231   CmdLine = Cmd.toString();
1232   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1233 
1234   Cmd.addFlag("fred", "plugh");
1235   EXPECT_TRUE(Cmd.hasFlag("fred"));
1236 
1237   Value = Cmd.getFlagValue("fred");
1238   EXPECT_EQ(Value, "plugh");
1239 
1240   CmdLine = Cmd.toString();
1241   EXPECT_EQ(CmdLine, makeCmdLine("-fred=plugh", ""));
1242 
1243   Cmd.removeFlag("fred");
1244   EXPECT_FALSE(Cmd.hasFlag("fred"));
1245 
1246   Value = Cmd.getFlagValue("fred");
1247   EXPECT_EQ(Value, "");
1248 
1249   CmdLine = Cmd.toString();
1250   EXPECT_EQ(CmdLine, makeCmdLine("", ""));
1251 }
1252 
1253 TEST(FuzzerCommand, SetOutput) {
1254   std::vector<std::string> ArgsToAdd;
1255   makeCommandArgs(&ArgsToAdd);
1256   Command Cmd(ArgsToAdd);
1257   std::string CmdLine;
1258   ASSERT_FALSE(Cmd.hasOutputFile());
1259   ASSERT_FALSE(Cmd.isOutAndErrCombined());
1260 
1261   Cmd.combineOutAndErr(true);
1262   EXPECT_TRUE(Cmd.isOutAndErrCombined());
1263 
1264   CmdLine = Cmd.toString();
1265   EXPECT_EQ(CmdLine, makeCmdLine("", "2>&1"));
1266 
1267   Cmd.combineOutAndErr(false);
1268   EXPECT_FALSE(Cmd.isOutAndErrCombined());
1269 
1270   Cmd.setOutputFile("xyzzy");
1271   EXPECT_TRUE(Cmd.hasOutputFile());
1272 
1273   CmdLine = Cmd.toString();
1274   EXPECT_EQ(CmdLine, makeCmdLine("", ">xyzzy"));
1275 
1276   Cmd.setOutputFile("thud");
1277   EXPECT_TRUE(Cmd.hasOutputFile());
1278 
1279   CmdLine = Cmd.toString();
1280   EXPECT_EQ(CmdLine, makeCmdLine("", ">thud"));
1281 
1282   Cmd.combineOutAndErr();
1283   EXPECT_TRUE(Cmd.isOutAndErrCombined());
1284 
1285   CmdLine = Cmd.toString();
1286   EXPECT_EQ(CmdLine, makeCmdLine("", ">thud 2>&1"));
1287 }
1288 
1289 TEST(Entropic, UpdateFrequency) {
1290   const size_t One = 1, Two = 2;
1291   const size_t FeatIdx1 = 0, FeatIdx2 = 42, FeatIdx3 = 12, FeatIdx4 = 26;
1292   size_t Index;
1293   // Create input corpus with default entropic configuration
1294   struct EntropicOptions Entropic = {true, 0xFF, 100, false};
1295   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
1296   std::unique_ptr<InputInfo> II(new InputInfo());
1297 
1298   C->AddRareFeature(FeatIdx1);
1299   C->UpdateFeatureFrequency(II.get(), FeatIdx1);
1300   EXPECT_EQ(II->FeatureFreqs.size(), One);
1301   C->AddRareFeature(FeatIdx2);
1302   C->UpdateFeatureFrequency(II.get(), FeatIdx1);
1303   C->UpdateFeatureFrequency(II.get(), FeatIdx2);
1304   EXPECT_EQ(II->FeatureFreqs.size(), Two);
1305   EXPECT_EQ(II->FeatureFreqs[0].second, 2);
1306   EXPECT_EQ(II->FeatureFreqs[1].second, 1);
1307 
1308   C->AddRareFeature(FeatIdx3);
1309   C->AddRareFeature(FeatIdx4);
1310   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1311   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1312   C->UpdateFeatureFrequency(II.get(), FeatIdx3);
1313   C->UpdateFeatureFrequency(II.get(), FeatIdx4);
1314 
1315   for (Index = 1; Index < II->FeatureFreqs.size(); Index++)
1316     EXPECT_LT(II->FeatureFreqs[Index - 1].first, II->FeatureFreqs[Index].first);
1317 
1318   II->DeleteFeatureFreq(FeatIdx3);
1319   for (Index = 1; Index < II->FeatureFreqs.size(); Index++)
1320     EXPECT_LT(II->FeatureFreqs[Index - 1].first, II->FeatureFreqs[Index].first);
1321 }
1322 
1323 double SubAndSquare(double X, double Y) {
1324   double R = X - Y;
1325   R = R * R;
1326   return R;
1327 }
1328 
1329 TEST(Entropic, ComputeEnergy) {
1330   const double Precision = 0.01;
1331   struct EntropicOptions Entropic = {true, 0xFF, 100, false};
1332   std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
1333   std::unique_ptr<InputInfo> II(new InputInfo());
1334   std::vector<std::pair<uint32_t, uint16_t>> FeatureFreqs = {
1335       {1, 3}, {2, 3}, {3, 3}};
1336   II->FeatureFreqs = FeatureFreqs;
1337   II->NumExecutedMutations = 0;
1338   II->UpdateEnergy(4, false, std::chrono::microseconds(0));
1339   EXPECT_LT(SubAndSquare(II->Energy, 1.450805), Precision);
1340 
1341   II->NumExecutedMutations = 9;
1342   II->UpdateEnergy(5, false, std::chrono::microseconds(0));
1343   EXPECT_LT(SubAndSquare(II->Energy, 1.525496), Precision);
1344 
1345   II->FeatureFreqs[0].second++;
1346   II->FeatureFreqs.push_back(std::pair<uint32_t, uint16_t>(42, 6));
1347   II->NumExecutedMutations = 20;
1348   II->UpdateEnergy(10, false, std::chrono::microseconds(0));
1349   EXPECT_LT(SubAndSquare(II->Energy, 1.792831), Precision);
1350 }
1351 
1352 int main(int argc, char **argv) {
1353   testing::InitGoogleTest(&argc, argv);
1354   return RUN_ALL_TESTS();
1355 }
1356