1 //===- FuzzerDataFlowTrace.cpp - DataFlowTrace                ---*- C++ -* ===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 // fuzzer::DataFlowTrace
9 //===----------------------------------------------------------------------===//
10 
11 #include "FuzzerDataFlowTrace.h"
12 #include "FuzzerIO.h"
13 #include "FuzzerRandom.h"
14 
15 #include <cstdlib>
16 #include <fstream>
17 #include <numeric>
18 #include <sstream>
19 #include <string>
20 #include <vector>
21 
22 namespace fuzzer {
23 static const char *kFunctionsTxt = "functions.txt";
24 
25 bool BlockCoverage::AppendCoverage(const std::string &S) {
26   std::stringstream SS(S);
27   return AppendCoverage(SS);
28 }
29 
30 // Coverage lines have this form:
31 // CN X Y Z T
32 // where N is the number of the function, T is the total number of instrumented
33 // BBs, and X,Y,Z, if present, are the indecies of covered BB.
34 // BB #0, which is the entry block, is not explicitly listed.
35 bool BlockCoverage::AppendCoverage(std::istream &IN) {
36   std::string L;
37   while (std::getline(IN, L, '\n')) {
38     if (L.empty() || L[0] != 'C')
39       continue; // Ignore non-coverage lines.
40     std::stringstream SS(L.c_str() + 1);
41     size_t FunctionId  = 0;
42     SS >> FunctionId;
43     Vector<uint32_t> CoveredBlocks;
44     while (true) {
45       uint32_t BB = 0;
46       SS >> BB;
47       if (!SS) break;
48       CoveredBlocks.push_back(BB);
49     }
50     if (CoveredBlocks.empty()) return false;
51     uint32_t NumBlocks = CoveredBlocks.back();
52     CoveredBlocks.pop_back();
53     for (auto BB : CoveredBlocks)
54       if (BB >= NumBlocks) return false;
55     auto It = Functions.find(FunctionId);
56     auto &Counters =
57         It == Functions.end()
58             ? Functions.insert({FunctionId, Vector<uint32_t>(NumBlocks)})
59                   .first->second
60             : It->second;
61 
62     if (Counters.size() != NumBlocks) return false;  // wrong number of blocks.
63 
64     Counters[0]++;
65     for (auto BB : CoveredBlocks)
66       Counters[BB]++;
67   }
68   return true;
69 }
70 
71 // Assign weights to each function.
72 // General principles:
73 //   * any uncovered function gets weight 0.
74 //   * a function with lots of uncovered blocks gets bigger weight.
75 //   * a function with a less frequently executed code gets bigger weight.
76 Vector<double> BlockCoverage::FunctionWeights(size_t NumFunctions) const {
77   Vector<double> Res(NumFunctions);
78   for (auto It : Functions) {
79     auto FunctionID = It.first;
80     auto Counters = It.second;
81     auto &Weight = Res[FunctionID];
82     Weight = 1000.;  // this function is covered.
83     Weight /= SmallestNonZeroCounter(Counters);
84     Weight *= NumberOfUncoveredBlocks(Counters) + 1;  // make sure it's not 0.
85   }
86   return Res;
87 }
88 
89 void DataFlowTrace::ReadCoverage(const std::string &DirPath) {
90   Vector<SizedFile> Files;
91   GetSizedFilesFromDir(DirPath, &Files);
92   for (auto &SF : Files) {
93     auto Name = Basename(SF.File);
94     if (Name == kFunctionsTxt) continue;
95     std::ifstream IF(SF.File);
96     Coverage.AppendCoverage(IF);
97   }
98 }
99 
100 void DataFlowTrace::Init(const std::string &DirPath,
101                          std::string *FocusFunction,
102                          Random &Rand) {
103   if (DirPath.empty()) return;
104   Printf("INFO: DataFlowTrace: reading from '%s'\n", DirPath.c_str());
105   Vector<SizedFile> Files;
106   GetSizedFilesFromDir(DirPath, &Files);
107   std::string L;
108   size_t FocusFuncIdx = SIZE_MAX;
109   Vector<std::string> FunctionNames;
110 
111   // Read functions.txt
112   std::ifstream IF(DirPlusFile(DirPath, kFunctionsTxt));
113   size_t NumFunctions = 0;
114   while (std::getline(IF, L, '\n')) {
115     FunctionNames.push_back(L);
116     NumFunctions++;
117     if (*FocusFunction == L)
118       FocusFuncIdx = NumFunctions - 1;
119   }
120 
121   if (*FocusFunction == "auto") {
122     // AUTOFOCUS works like this:
123     // * reads the coverage data from the DFT files.
124     // * assigns weights to functions based on coverage.
125     // * chooses a random function according to the weights.
126     ReadCoverage(DirPath);
127     auto Weights = Coverage.FunctionWeights(NumFunctions);
128     Vector<double> Intervals(NumFunctions + 1);
129     std::iota(Intervals.begin(), Intervals.end(), 0);
130     auto Distribution = std::piecewise_constant_distribution<double>(
131         Intervals.begin(), Intervals.end(), Weights.begin());
132     FocusFuncIdx = static_cast<size_t>(Distribution(Rand));
133     *FocusFunction = FunctionNames[FocusFuncIdx];
134     assert(FocusFuncIdx < NumFunctions);
135     Printf("INFO: AUTOFOCUS: %zd %s\n", FocusFuncIdx,
136            FunctionNames[FocusFuncIdx].c_str());
137     for (size_t i = 0; i < NumFunctions; i++) {
138       if (!Weights[i]) continue;
139       Printf("  [%zd] W %g\tBB-tot %u\tBB-cov %u\tEntryFreq %u:\t%s\n", i,
140              Weights[i], Coverage.GetNumberOfBlocks(i),
141              Coverage.GetNumberOfCoveredBlocks(i), Coverage.GetCounter(i, 0),
142              FunctionNames[i].c_str());
143     }
144   }
145 
146   if (!NumFunctions || FocusFuncIdx == SIZE_MAX || Files.size() <= 1)
147     return;
148 
149   // Read traces.
150   size_t NumTraceFiles = 0;
151   size_t NumTracesWithFocusFunction = 0;
152   for (auto &SF : Files) {
153     auto Name = Basename(SF.File);
154     if (Name == kFunctionsTxt) continue;
155     auto ParseError = [&](const char *Err) {
156       Printf("DataFlowTrace: parse error: %s\n  File: %s\n  Line: %s\n", Err,
157              Name.c_str(), L.c_str());
158     };
159     NumTraceFiles++;
160     // Printf("=== %s\n", Name.c_str());
161     std::ifstream IF(SF.File);
162     while (std::getline(IF, L, '\n')) {
163       if (!L.empty() && L[0] == 'C')
164         continue; // Ignore coverage.
165       size_t SpacePos = L.find(' ');
166       if (SpacePos == std::string::npos)
167         return ParseError("no space in the trace line");
168       if (L.empty() || L[0] != 'F')
169         return ParseError("the trace line doesn't start with 'F'");
170       size_t N = std::atol(L.c_str() + 1);
171       if (N >= NumFunctions)
172         return ParseError("N is greater than the number of functions");
173       if (N == FocusFuncIdx) {
174         NumTracesWithFocusFunction++;
175         const char *Beg = L.c_str() + SpacePos + 1;
176         const char *End = L.c_str() + L.size();
177         assert(Beg < End);
178         size_t Len = End - Beg;
179         Vector<uint8_t> V(Len);
180         for (size_t I = 0; I < Len; I++) {
181           if (Beg[I] != '0' && Beg[I] != '1')
182             ParseError("the trace should contain only 0 or 1");
183           V[I] = Beg[I] == '1';
184         }
185         Traces[Name] = V;
186         // Print just a few small traces.
187         if (NumTracesWithFocusFunction <= 3 && Len <= 16)
188           Printf("%s => |%s|\n", Name.c_str(), L.c_str() + SpacePos + 1);
189         break;  // No need to parse the following lines.
190       }
191     }
192   }
193   assert(NumTraceFiles == Files.size() - 1);
194   Printf("INFO: DataFlowTrace: %zd trace files, %zd functions, "
195          "%zd traces with focus function\n",
196          NumTraceFiles, NumFunctions, NumTracesWithFocusFunction);
197 }
198 
199 int CollectDataFlow(const std::string &DFTBinary, const std::string &DirPath,
200                     const Vector<SizedFile> &CorporaFiles) {
201   Printf("INFO: collecting data flow for %zd files\n", CorporaFiles.size());
202   return 0;
203 }
204 
205 }  // namespace fuzzer
206 
207