1 //===- FuzzerDataFlowTrace.h - Internal header for the Fuzzer ---*- 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; reads and handles a data-flow trace.
9 //
10 // A data flow trace is generated by e.g. dataflow/DataFlow.cpp
11 // and is stored on disk in a separate directory.
12 //
13 // The trace dir contains a file 'functions.txt' which lists function names,
14 // oner per line, e.g.
15 // ==> functions.txt <==
16 // Func2
17 // LLVMFuzzerTestOneInput
18 // Func1
19 //
20 // All other files in the dir are the traces, see dataflow/DataFlow.cpp.
21 // The name of the file is sha1 of the input used to generate the trace.
22 //
23 // Current status:
24 //   the data is parsed and the summary is printed, but the data is not yet
25 //   used in any other way.
26 //===----------------------------------------------------------------------===//
27 
28 #ifndef LLVM_FUZZER_DATA_FLOW_TRACE
29 #define LLVM_FUZZER_DATA_FLOW_TRACE
30 
31 #include "FuzzerDefs.h"
32 #include "FuzzerIO.h"
33 
34 #include <unordered_map>
35 #include <unordered_set>
36 #include <vector>
37 #include <string>
38 
39 namespace fuzzer {
40 
41 int CollectDataFlow(const std::string &DFTBinary, const std::string &DirPath,
42                     const Vector<SizedFile> &CorporaFiles);
43 
44 class BlockCoverage {
45  public:
46   bool AppendCoverage(std::istream &IN);
47   bool AppendCoverage(const std::string &S);
48 
NumCoveredFunctions()49   size_t NumCoveredFunctions() const { return Functions.size(); }
50 
GetCounter(size_t FunctionId,size_t BasicBlockId)51   uint32_t GetCounter(size_t FunctionId, size_t BasicBlockId) {
52     auto It = Functions.find(FunctionId);
53     if (It == Functions.end()) return 0;
54     const auto &Counters = It->second;
55     if (BasicBlockId < Counters.size())
56       return Counters[BasicBlockId];
57     return 0;
58   }
59 
GetNumberOfBlocks(size_t FunctionId)60   uint32_t GetNumberOfBlocks(size_t FunctionId) {
61     auto It = Functions.find(FunctionId);
62     if (It == Functions.end()) return 0;
63     const auto &Counters = It->second;
64     return Counters.size();
65   }
66 
GetNumberOfCoveredBlocks(size_t FunctionId)67   uint32_t GetNumberOfCoveredBlocks(size_t FunctionId) {
68     auto It = Functions.find(FunctionId);
69     if (It == Functions.end()) return 0;
70     const auto &Counters = It->second;
71     uint32_t Result = 0;
72     for (auto Cnt: Counters)
73       if (Cnt)
74         Result++;
75     return Result;
76   }
77 
78   Vector<double> FunctionWeights(size_t NumFunctions) const;
clear()79   void clear() { Functions.clear(); }
80 
81  private:
82 
83   typedef Vector<uint32_t> CoverageVector;
84 
NumberOfCoveredBlocks(const CoverageVector & Counters)85   uint32_t NumberOfCoveredBlocks(const CoverageVector &Counters) const {
86     uint32_t Res = 0;
87     for (auto Cnt : Counters)
88       if (Cnt)
89         Res++;
90     return Res;
91   }
92 
NumberOfUncoveredBlocks(const CoverageVector & Counters)93   uint32_t NumberOfUncoveredBlocks(const CoverageVector &Counters) const {
94     return Counters.size() - NumberOfCoveredBlocks(Counters);
95   }
96 
SmallestNonZeroCounter(const CoverageVector & Counters)97   uint32_t SmallestNonZeroCounter(const CoverageVector &Counters) const {
98     assert(!Counters.empty());
99     uint32_t Res = Counters[0];
100     for (auto Cnt : Counters)
101       if (Cnt)
102         Res = Min(Res, Cnt);
103     assert(Res);
104     return Res;
105   }
106 
107   // Function ID => vector of counters.
108   // Each counter represents how many input files trigger the given basic block.
109   std::unordered_map<size_t, CoverageVector> Functions;
110   // Functions that have DFT entry.
111   std::unordered_set<size_t> FunctionsWithDFT;
112 };
113 
114 class DataFlowTrace {
115  public:
116   void ReadCoverage(const std::string &DirPath);
117   bool Init(const std::string &DirPath, std::string *FocusFunction,
118             Vector<SizedFile> &CorporaFiles, Random &Rand);
Clear()119   void Clear() { Traces.clear(); }
Get(const std::string & InputSha1)120   const Vector<uint8_t> *Get(const std::string &InputSha1) const {
121     auto It = Traces.find(InputSha1);
122     if (It != Traces.end())
123       return &It->second;
124     return nullptr;
125   }
126 
127  private:
128   // Input's sha1 => DFT for the FocusFunction.
129   std::unordered_map<std::string, Vector<uint8_t> > Traces;
130   BlockCoverage Coverage;
131   std::unordered_set<std::string> CorporaHashes;
132 };
133 }  // namespace fuzzer
134 
135 #endif // LLVM_FUZZER_DATA_FLOW_TRACE
136