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
39namespace fuzzer {
40
41int CollectDataFlow(const std::string &DFTBinary, const std::string &DirPath,
42                    const Vector<SizedFile> &CorporaFiles);
43
44class BlockCoverage {
45 public:
46  bool AppendCoverage(std::istream &IN);
47  bool AppendCoverage(const std::string &S);
48
49  size_t NumCoveredFunctions() const { return Functions.size(); }
50
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
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
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;
79  void clear() { Functions.clear(); }
80
81 private:
82
83  typedef Vector<uint32_t> CoverageVector;
84
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
93  uint32_t NumberOfUncoveredBlocks(const CoverageVector &Counters) const {
94    return Counters.size() - NumberOfCoveredBlocks(Counters);
95  }
96
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
114class 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);
119  void Clear() { Traces.clear(); }
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