Add graph centrality based seed scheduler: K-Scheduler (IEEE S&P22) for LibFuzzer.

[Dongdongshe]

Summary

K-Scheduler is a novel seed scheduler for LibFuzzer which can greatly improve LibFuzzer performance over the default seed scheduler entropic.
IEEE S&P 2022 paper link: https://arxiv.org/abs/2203.12064
Github repo: https://github.com/Dongdongshe/K-Scheduler
Intuition behind: Good seeds can reach more number of unvisited nodes and bad seeds can reach fewer number of unvisited nodes.
General idea: We approximate the potential code coverage gain (i.e., the number of reachable and unvisited nodes) for each seed using graph centrality scores. Then, we prioritize the seed with higher potential code coverage gain.
One minute video explanation: https://www.youtube.com/watch?v=VVZZpQiIsm4
Our original implementation is on llvm-11.0.1. We port K-Scheduler to llvm-14.0.0 and evaluate it on 8 programs. The results show consistent improvement as llvm-11.0.1.
Please check our evaluation result plot over 24 hours for 10 runs and corresponding reproduction package (including binaries and seed corpus) at https://github.com/Dongdongshe/K-Scheduler_llvm14_Benchmark

[Dongdongshe]

Add a graph centrality-based seed scheduler (K-Scheduler, IEEE S&P22) for LibFuzzer to improve fuzzing performance.

K-Scheduler: a novel seed scheduler for LibFuzzer which can greatly improve LibFuzzer performance over the default seed scheduler entropic.
IEEE S&P 2022 paper link: https://arxiv.org/abs/2203.12064
Github repo: https://github.com/Dongdongshe/K-Scheduler
Intuition behind: Good seeds can reach more number of unvisited nodes and bad seeds can reach fewer number of unvisited nodes.
General idea: We approximate the potential code coverage gain (i.e., the number of reachable and unvisited nodes) for each seed through the graph centrality scores. Then, we prioritize the seed with higher potential code coverage gain.
One minute video explanation: https://www.youtube.com/watch?v=VVZZpQiIsm4
Our original implementation is on llvm-11.0.1. We port K-Scheduler to llvm-14.0.0 and evaluate it on 8 programs. The results show consistent improvement as llvm-11.0.1.
Please check our evaluation result plot over 24 hours for 10 runs and corresponding reproduction package (including binaries and seed corpus) at https://github.com/Dongdongshe/K-Scheduler_llvm14_Benchmark

[Dongdongshe]

K-Scheduler is a novel seed scheduler for LibFuzzer which can greatly improve LibFuzzer performance over the default seed scheduler entropic.
IEEE S&P 2022 paper link: https://arxiv.org/abs/2203.12064
Github repo: https://github.com/Dongdongshe/K-Scheduler
Intuition behind: Good seeds can reach more number of unvisited nodes and bad seeds can reach fewer number of unvisited nodes.
General idea: We approximate the potential code coverage gain (i.e., the number of reachable and unvisited nodes) for each seed using graph centrality scores. Then, we prioritize the seed with higher potential code coverage gain.
One minute video explanation: https://www.youtube.com/watch?v=VVZZpQiIsm4
Our original implementation is on llvm-11.0.1. We port K-Scheduler to llvm-14.0.0 and evaluate it on 8 programs. The results show consistent improvement as llvm-11.0.1.
Please check our evaluation result plot over 24 hours for 10 runs and corresponding reproduction package (including binaries and seed corpus) at https://github.com/Dongdongshe/K-Scheduler_llvm14_Benchmark

[Dongdongshe]

Ping

compiler-rt/lib/fuzzer/FuzzerCorpus.h

 #include "FuzzerDataFlowTrace.h"
 #include "FuzzerDefs.h"
 #include "FuzzerIO.h"
 #include "FuzzerRandom.h"
 #include "FuzzerSHA1.h"
 #include "FuzzerTracePC.h"
 #include <algorithm>
 #include <chrono>
+#include <fstream>
+#include <iostream>
+#include <math.h>
 #include <numeric>
 #include <random>
+#include <string>
 #include <unordered_set>
 
 namespace fuzzer {
 
 struct InputInfo {
   Unit U;  // The actual input data.
   std::chrono::microseconds TimeOfUnit;
   uint8_t Sha1[kSHA1NumBytes];  // Checksum.
   // Number of features that this input has and no smaller input has.
   size_t NumFeatures = 0;
   size_t Tmp = 0; // Used by ValidateFeatureSet.
   // Stats.
   size_t NumExecutedMutations = 0;
   size_t NumSuccessfullMutations = 0;
+  bool SlowInput = false;
   bool NeverReduce = false;
   bool MayDeleteFile = false;
   bool Reduced = false;
   bool HasFocusFunction = false;
   std::vector<uint32_t> UniqFeatureSet;
   std::vector<uint8_t> DataFlowTraceForFocusFunction;
   // Power schedule.
   bool NeedsEnergyUpdate = false;
   double Energy = 0.0;
   double SumIncidence = 0.0;
   std::vector<std::pair<uint32_t, uint16_t>> FeatureFreqs;
+  // K-Scheduler.
+  bool ComputedBefore = false;
+  bool FuzzedBefore = false;
+  double KschedulerEnergy = 0.0;
+  uint32_t KschedulerPerfScore;  // The performance score reflects runtime cost
+                                 // of current input used in K-Scheduler.
+  std::vector<uint32_t> EdgeSet; // The set of edges covered by current input.
+  std::vector<int>
+      BorderEdgeIdx; // Index table of BorderEdgeSet for current input.
+  std::vector<std::pair<uint32_t, uint32_t>>
+      BorderEdgeSet; // Set of border edges for current input.
 
   // Delete feature Idx and its frequency from FeatureFreqs.
   bool DeleteFeatureFreq(uint32_t Idx) {
     if (FeatureFreqs.empty())
       return false;
 
     // Binary search over local feature frequencies sorted by index.
     auto Lower = std::lower_bound(FeatureFreqs.begin(), FeatureFreqs.end(),
                                   std::pair<uint32_t, uint16_t>(Idx, 0));
 
     if (Lower != FeatureFreqs.end() && Lower->first == Idx) {
       FeatureFreqs.erase(Lower);
       return true;
     }
     return false;
   }
 
+  // Everytime kscheduler identifies a border edge for a seed, it saves the
+  // border edge(ParentId, ChildId) and the corresponding border edge idx
+  // BorderEdgeId into a seed's BorderEdgeSet and BorderEdgeId respectively. In
+  // the following seed weight computation, kscheduler can directly retrieve the
+  // border edges from saved data stucture.
+  void SaveBorderEdge(uint32_t ParentId, uint32_t ChildId,
+                      uint32_t BorderEdgeId) {
+
+    if (BorderEdgeSet.empty()) {
+      BorderEdgeSet.push_back(std::pair<uint32_t, uint32_t>(ParentId, ChildId));
+      BorderEdgeIdx.push_back(BorderEdgeId);
+      return;
+    }
+
+    // Binary search to find the location since the pair is sorted.
+    auto Lower =
+        std::lower_bound(BorderEdgeSet.begin(), BorderEdgeSet.end(),
+                         std::pair<uint32_t, uint32_t>(ParentId, ChildId));
+
+    int TmpIdx = Lower - BorderEdgeSet.begin();
+    BorderEdgeSet.insert(Lower,
+                         std::pair<uint32_t, uint32_t>(ParentId, ChildId));
+    BorderEdgeIdx.insert(BorderEdgeIdx.begin() + TmpIdx, BorderEdgeId);
+  }
+
+  // Check if a newly visited border edge is included into current seed's energy
+  // computation. If so, delete the border edge from current seed's data
+  // structure since we only consider unvisited border edges into K-Scheduler's
+  // seed energy computation.
+  int SearchAndDeleteBorderEdge(uint32_t ParentId, uint32_t ChildId) {
+    // The border edge is not included into current seed's energy.
+    if (BorderEdgeSet.empty())
+      return -2;
+
+    // Binary search.
+    auto Lower =
+        std::lower_bound(BorderEdgeSet.begin(), BorderEdgeSet.end(),
+                         std::pair<uint32_t, uint32_t>(ParentId, ChildId));
+
+    if (Lower != BorderEdgeSet.end() && Lower->first == ParentId &&
+        Lower->second == ChildId) {
+      int TmpIdx = Lower - BorderEdgeSet.begin();
+      BorderEdgeSet.erase(Lower);
+
+      int ret_idx = BorderEdgeIdx[TmpIdx];
+      BorderEdgeIdx.erase(BorderEdgeIdx.begin() + TmpIdx);
+
+      return ret_idx;
+    }
+    return -2;
+  }
+
   // Assign more energy to a high-entropy seed, i.e., that reveals more
   // information about the globally rare features in the neighborhood of the
   // seed. Since we do not know the entropy of a seed that has never been
   // executed we assign fresh seeds maximum entropy and let II->Energy approach
   // the true entropy from above. If ScalePerExecTime is true, the computed
   // entropy is scaled based on how fast this input executes compared to the
   // average execution time of inputs. The faster an input executes, the more
   // energy gets assigned to the input.

 
 struct EntropicOptions {
   bool Enabled;
   size_t NumberOfRarestFeatures;
   size_t FeatureFrequencyThreshold;
   bool ScalePerExecTime;
 };
 
+struct KschedulerOptions {
+  bool Enabled;
+  size_t MinNumMutationsForEachSeed;
+  size_t PerThres;
+};
+
 class InputCorpus {
   static const uint32_t kFeatureSetSize = 1 << 21;
+  static const uint32_t kEdgeSetSize = 1 << 17;
   static const uint8_t kMaxMutationFactor = 20;
   static const size_t kSparseEnergyUpdates = 100;
 
   size_t NumExecutedMutations = 0;
+  // The initial number must be greater than 1 in order to avoid 0 value
+  // when computing log(CurNumExecutedMutations) for the first time.
+  // Hence, we use a small number (i.e., 2) here.
+  size_t CurNumExecutedMutations = 2; 
 
   EntropicOptions Entropic;
+  KschedulerOptions Kscheduler;
 
 public:
-  InputCorpus(const std::string &OutputCorpus, EntropicOptions Entropic)
-      : Entropic(Entropic), OutputCorpus(OutputCorpus) {
+  InputCorpus(const std::string &OutputCorpus, EntropicOptions Entropic,
+              KschedulerOptions Kscheduler)
+      : Entropic(Entropic), Kscheduler(Kscheduler), OutputCorpus(OutputCorpus) {
     memset(InputSizesPerFeature, 0, sizeof(InputSizesPerFeature));
     memset(SmallestElementPerFeature, 0, sizeof(SmallestElementPerFeature));
+    if (Kscheduler.Enabled)
+      LoadGraphInfo();
   }
   ~InputCorpus() {
     for (auto II : Inputs)
       delete II;
   }
+
+  void LoadGraphInfo() {
+    // Load katz centrality scores from files
+    std::ifstream KatzFile("katz_cent", std::ifstream::in);
+    if (!KatzFile.good()) {
+      Printf("Missing graph analysis file.\n");
+      exit(1);
+    }
+    size_t EdgeId;
+    double KatzScores;
+    while (KatzFile >> EdgeId >> KatzScores) {
+      EdgeCentralityScore[EdgeId] = KatzScores;
+    }
+    KatzFile.close();
+
+    // Load adjacency list of program's inter-procedural CFG i.e., node2child
+    // mapping.
+    std::ifstream ChildFile("child_node", std::ifstream::in);
+    if (!ChildFile.good()) {
+      Printf("Missing graph analysis file.\n");
+      exit(1);
+    }
+    std::string Line;
+    while (std::getline(ChildFile, Line)) {
+      std::istringstream ss(Line);
+      size_t NodeId, ChildId;
+      ss >> NodeId;
+      while (ss >> ChildId) {
+        Child[NodeId].push_back(ChildId);
+      }
+    }
+    ChildFile.close();
+
+    // Load adjacency list of reverse inter-procedural CFG i.e., node2parent
+    // mapping.
+    std::ifstream ParentFile("parent_node", std::ifstream::in);
+    if (!ParentFile.good()) {
+      Printf("Missing graph analysis file.\n");
+      exit(1);
+    }
+    while (std::getline(ParentFile, Line)) {
+      std::istringstream ss(Line);
+      size_t NodeId, ParentId;
+      ss >> NodeId;
+      while (ss >> ParentId) {
+        Parent[NodeId].push_back(ParentId);
+      }
+    }
+    ParentFile.close();
+
+    // read all border edges
+    std::ifstream EdgeFile("border_edges", std::ifstream::in);
+    if (!EdgeFile.good()) {
+      Printf("Missing graph analysis file.\n");
+      exit(1);
+    }
+    uint32_t ParentId, ChildId;
+    while (EdgeFile >> ParentId >> ChildId) {
+      BorderEdge.push_back(std::pair<uint32_t, uint32_t>(ParentId, ChildId));
+    }
+    EdgeFile.close();
+  }
   size_t size() const { return Inputs.size(); }
   size_t SizeInBytes() const {
     size_t Res = 0;
     for (auto II : Inputs)
       Res += II->U.size();
     return Res;
   }
   size_t NumActiveUnits() const {
     size_t Res = 0;
     for (auto II : Inputs)
       Res += !II->U.empty();
     return Res;
   }
   size_t MaxInputSize() const {
     size_t Res = 0;
     for (auto II : Inputs)
         Res = std::max(Res, II->U.size());
     return Res;
   }
   void IncrementNumExecutedMutations() { NumExecutedMutations++; }
-
+  void SetCurNumExecutedMutations(uint32_t Num) {
+    CurNumExecutedMutations = Num;
+  } // For unit testing only.
+  size_t GetAvgExecTime() { return AvgExecTime.count(); }
   size_t NumInputsThatTouchFocusFunction() {
     return std::count_if(Inputs.begin(), Inputs.end(), [](const InputInfo *II) {
       return II->HasFocusFunction;
     });
   }
 
   size_t NumInputsWithDataFlowTrace() {
     return std::count_if(Inputs.begin(), Inputs.end(), [](const InputInfo *II) {
       return !II->DataFlowTraceForFocusFunction.empty();
     });
   }
 
+  // Record visited edges covered by current seed.
+  void RecordVisitedEdge(uint32_t EdgeId) {
+    if (TmpEdgeSet.empty()) {
+      TmpEdgeSet.push_back(EdgeId);
+    } else {
+      auto Lower =
+          std::lower_bound(TmpEdgeSet.begin(), TmpEdgeSet.end(), EdgeId);
+      TmpEdgeSet.insert(Lower, EdgeId);
+    }
+  }
+
   bool empty() const { return Inputs.empty(); }
   const Unit &operator[] (size_t Idx) const { return Inputs[Idx]->U; }
   InputInfo *AddToCorpus(const Unit &U, size_t NumFeatures, bool MayDeleteFile,
                          bool HasFocusFunction, bool NeverReduce,
                          std::chrono::microseconds TimeOfUnit,
                          const std::vector<uint32_t> &FeatureSet,
                          const DataFlowTrace &DFT, const InputInfo *BaseII) {
     assert(!U.empty());
     if (FeatureDebug)
       Printf("ADD_TO_CORPUS %zd NF %zd\n", Inputs.size(), NumFeatures);
     // Inputs.size() is cast to uint32_t below.
     assert(Inputs.size() < std::numeric_limits<uint32_t>::max());
     Inputs.push_back(new InputInfo());
     InputInfo &II = *Inputs.back();
     II.U = U;
     II.NumFeatures = NumFeatures;
     II.NeverReduce = NeverReduce;
     II.TimeOfUnit = TimeOfUnit;
+    // K-Scheduler: maintain a accumulative sum of total execution time over
+    // seed corpus, then compute average execution time. We do not count slow
+    // inputs as they would drag down the fuzzing throughput.
+    if (TotalExecTime.count() == 0) {
+      TotalExecTime += TimeOfUnit;
+      AvgExecTime += TimeOfUnit;
+    } else {
+      if (TimeOfUnit.count() <=
+          (AvgExecTime.count() * (int)Kscheduler.PerThres)) {
+        TotalExecTime += TimeOfUnit;
+        AvgExecTime = TotalExecTime / (Inputs.size() - NumOfSlowInputs);
+        II.SlowInput = false;
+      } else {
+        NumOfSlowInputs += 1;
+        II.SlowInput = true;
+      }
+    }
+
+    II.EdgeSet = TmpEdgeSet; // Record the visited edge set of current seed.
     II.MayDeleteFile = MayDeleteFile;
     II.UniqFeatureSet = FeatureSet;
     II.HasFocusFunction = HasFocusFunction;
     // Assign maximal energy to the new seed.
     II.Energy = RareFeatures.empty() ? 1.0 : log(RareFeatures.size());
+    II.KschedulerEnergy = 100000.0;
+
     II.SumIncidence = static_cast<double>(RareFeatures.size());
     II.NeedsEnergyUpdate = false;
     std::sort(II.UniqFeatureSet.begin(), II.UniqFeatureSet.end());
     ComputeSHA1(U.data(), U.size(), II.Sha1);
     auto Sha1Str = Sha1ToString(II.Sha1);
     Hashes.insert(Sha1Str);
     if (HasFocusFunction)
       if (auto V = DFT.Get(Sha1Str))
         II.DataFlowTraceForFocusFunction = *V;
     // This is a gross heuristic.
     // Ideally, when we add an element to a corpus we need to know its DFT.
     // But if we don't, we'll use the DFT of its base input.
     if (II.DataFlowTraceForFocusFunction.empty() && BaseII)
       II.DataFlowTraceForFocusFunction = BaseII->DataFlowTraceForFocusFunction;
     DistributionNeedsUpdate = true;
+    KschedulerDistributionNeedsUpdate = true;
     PrintCorpus();
     // ValidateFeatureSet();
     return &II;
   }
 
   // Debug-only
   void PrintUnit(const Unit &U) {
     if (!FeatureDebug) return;
for (auto II : Inputs) {
         Printf(" ");
         PrintFeatureSet(II->UniqFeatureSet);
         Printf("\n");
       }
       i++;
     }
   }
 
+  // Find the index of a given border edge (ParentId, ChildId) in the sorted
+  // vector BorderEdge.
+  int FindBorderEdgeIdx(uint32_t ParentId, uint32_t ChildId) {
+    if (BorderEdge.empty())
+      return -1;
+
+    auto Lower =
+        std::lower_bound(BorderEdge.begin(), BorderEdge.end(),
+                         std::pair<uint32_t, uint32_t>(ParentId, ChildId));
+
+    if (Lower != BorderEdge.end() && Lower->first == ParentId &&
+        Lower->second == ChildId)
+      return Lower - BorderEdge.begin();
+    else
+      return -1;
+  }
+
   void Replace(InputInfo *II, const Unit &U,
                std::chrono::microseconds TimeOfUnit) {
     assert(II->U.size() > U.size());
     Hashes.erase(Sha1ToString(II->Sha1));
     DeleteFile(*II);
     ComputeSHA1(U.data(), U.size(), II->Sha1);
     Hashes.insert(Sha1ToString(II->Sha1));
     II->U = U;
     II->Reduced = true;
-    II->TimeOfUnit = TimeOfUnit;
+
     DistributionNeedsUpdate = true;
+
+    if (Kscheduler.Enabled) {
+      KschedulerDistributionNeedsUpdate = true;
+
+      // Substrate runtime cost of old input from the sum
+      // of total execution time over seed corpus.
+      if (II->SlowInput)
+        NumOfSlowInputs -= 1;
+      else
+        TotalExecTime -= II->TimeOfUnit; 
+
+      II->ComputedBefore = false;
+      II->FuzzedBefore = true;
+      II->KschedulerEnergy = 100000.0;
+
+      II->EdgeSet.clear(); // The set of edges covered by current input.
+      II->EdgeSet = TmpEdgeSet;
+      II->BorderEdgeIdx.clear(); // Index table of BorderEdgeSet for current input.
+      II->BorderEdgeSet.clear(); // Set of border edges for current input.
+
+      II->TimeOfUnit = TimeOfUnit;
+      if (TimeOfUnit.count() <=
+          (AvgExecTime.count() * (int)Kscheduler.PerThres)) {
+        TotalExecTime += TimeOfUnit;
+        AvgExecTime = TotalExecTime / (Inputs.size() - NumOfSlowInputs);
+        II->SlowInput = false;
+      } else {
+        NumOfSlowInputs += 1;
+        if (Inputs.size() - NumOfSlowInputs > 0)
+          AvgExecTime = TotalExecTime / (Inputs.size() - NumOfSlowInputs);
+        else
+          AvgExecTime = std::chrono::microseconds(0);
+        II->SlowInput = true;
+      }
+    } else {
+      II->TimeOfUnit = TimeOfUnit;
+    }
   }
 
   bool HasUnit(const Unit &U) { return Hashes.count(Hash(U)); }
   bool HasUnit(const std::string &H) { return Hashes.count(H); }
-  InputInfo &ChooseUnitToMutate(Random &Rand) {
-    InputInfo &II = *Inputs[ChooseUnitIdxToMutate(Rand)];
+  InputInfo &ChooseUnitToMutate(Random &Rand, size_t CurTime) {
+    InputInfo &II = *Inputs[ChooseUnitIdxToMutate(Rand, CurTime)];
     assert(!II.U.empty());
     return II;
   }
 
-  InputInfo &ChooseUnitToCrossOverWith(Random &Rand, bool UniformDist) {
+  InputInfo &ChooseUnitToCrossOverWith(Random &Rand, bool UniformDist,
+                                       size_t CurTime) {
     if (!UniformDist) {
-      return ChooseUnitToMutate(Rand);
+      return ChooseUnitToMutate(Rand, CurTime);
     }
     InputInfo &II = *Inputs[Rand(Inputs.size())];
     assert(!II.U.empty());
     return II;
   }
 
   // Returns an index of random unit from the corpus to mutate.
-  size_t ChooseUnitIdxToMutate(Random &Rand) {
+  size_t ChooseUnitIdxToMutate(Random &Rand, size_t CurTime) {
     UpdateCorpusDistribution(Rand);
+    KschedulerUpdateCorpusDistribution(Rand, CurTime);
     size_t Idx = static_cast<size_t>(CorpusDistribution(Rand));
     assert(Idx < Inputs.size());
     return Idx;
   }
 
   void PrintStats() {
     for (size_t i = 0; i < Inputs.size(); i++) {
       const auto &II = *Inputs[i];
if (!OutputCorpus.empty() && II.MayDeleteFile)
       RemoveFile(DirPlusFile(OutputCorpus, Sha1ToString(II.Sha1)));
   }
 
   void DeleteInput(size_t Idx) {
     InputInfo &II = *Inputs[Idx];
     DeleteFile(II);
     Unit().swap(II.U);
     II.Energy = 0.0;
+    II.KschedulerEnergy = 0.0;
+    if (!II.SlowInput) {
+      // Substrate runtime cost of old input from the sum of
+      // total execution time over seed corpus.
+      TotalExecTime -= II.TimeOfUnit; 
+      NumOfSlowInputs += 1;
+      AvgExecTime = TotalExecTime / (Inputs.size() - NumOfSlowInputs);
+      II.SlowInput = true;
+    }
     II.NeedsEnergyUpdate = false;
     DistributionNeedsUpdate = true;
+    KschedulerDistributionNeedsUpdate = true;
     if (FeatureDebug)
       Printf("EVICTED %zd\n", Idx);
   }
 
+  // Compute energy for a seed based on its Katz Centraltiy and its runtime
+  // cost.
+  void ComputeEnergy(InputInfo *II,
+                     std::chrono::microseconds AverageUnitExecutionTime) {
+    II->KschedulerEnergy = 0.0;
+    // Identify border edges for a seed when we encounter it for the first time,
+    // then save the border edges into BorderEdgeSet.
+    if (II->BorderEdgeSet.size() == 0) {
+      // Loop every border edges of a seed.
+      for (auto NodeId : II->EdgeSet) {
+        // Get child node for each visited node of a seed
+        for (auto ChildId : Child[NodeId]) {
+          // If child node is not visited and parent node is visited, then we
+          // find a border edges defined as (NodeId, ChildId).
+          if (GlobalEdgeFreqs[ChildId] == 0) {
+            double TmpEdgeWeight = 0.0;
+            int BorderEdgeIdx = FindBorderEdgeIdx(NodeId, ChildId);
+            if (BorderEdgeIdx != -1) {
+              // case 1: EdgeWeight != 0. It means we computed this edge weight
+              // before, just retrieve it from BorderEdgeWeight cache table.
+              if (TmpEdgeWeight != 0.0) {
+                TmpEdgeWeight = BorderEdgeWeight[BorderEdgeIdx];
+              }
+              // case 2: EdgeWeight == 0. It means we didn't compute this edge
+              // weight. First compute EdgeWeight, then save it into the
+              // borderEdge weight table.
+              else {
+                TmpEdgeWeight = EdgeCentralityScore[ChildId] *
+                                sqrt(log(CurNumExecutedMutations) /
+                                     GlobalEdgeFreqs[NodeId]);
+                BorderEdgeWeight[BorderEdgeIdx] = TmpEdgeWeight;
+              }
+            }
+            // Save current seed's border edges into its own BorderEdgeSet cache
+            // so that we don't need to scan the inter-CFG again to identify
+            // them next time.
+            II->SaveBorderEdge(NodeId, ChildId, BorderEdgeIdx);
+
+            // Katz centrality equals sum of all its border edge weights.
+            II->KschedulerEnergy += TmpEdgeWeight;
+          }
+        }
+      }
+    }
+    // We have identified the border edges for this seed before and read
+    // directly from cached BorderEdgeIdx
+    else {
+      for (auto BorderEdgeId : II->BorderEdgeIdx) {
+        double TmpBorderEdgeWeight = 0.0;
+        if (BorderEdgeId != -1)
+          TmpBorderEdgeWeight = BorderEdgeWeight[BorderEdgeId];
+        II->KschedulerEnergy += TmpBorderEdgeWeight;
+      }
+    }
+
+    // Slow seeds tend to have large Katz centraltiy score and decrease the
+    // fuzzing throughput. We penalize them by performance score. NOTE: we ONLY
+    // penalize seeds with extremely large runtime overhead, but NEVER boost
+    // seeds with small runtime overhead. Because seeds with small runtime
+    // overhead are not necessarliy good/promisng/interesting seeds. A promising
+    // seed should have a large Katz centrality and a NOT-large runtime
+    // overhead.
+    uint32_t CurPerfScore = 100;
+    if (II->TimeOfUnit.count() > AverageUnitExecutionTime.count() * 10)
+      CurPerfScore = 10;
+    else if (II->TimeOfUnit.count() > AverageUnitExecutionTime.count() * 4)
+      CurPerfScore = 25;
+    else if (II->TimeOfUnit.count() > AverageUnitExecutionTime.count() * 2)
+      CurPerfScore = 50;
+    else if (II->TimeOfUnit.count() * 3 > AverageUnitExecutionTime.count() * 4)
+      CurPerfScore = 75;
+
+    II->KschedulerPerfScore = CurPerfScore;
+    II->KschedulerEnergy *= CurPerfScore;
+  }
+
   void AddRareFeature(uint32_t Idx) {
     // Maintain *at least* TopXRarestFeatures many rare features
     // and all features with a frequency below ConsideredRare.
     // Remove all other features.
     while (RareFeatures.size() > Entropic.NumberOfRarestFeatures &&
            FreqOfMostAbundantRareFeature > Entropic.FeatureFrequencyThreshold) {
 
       // Find most and second most abbundant feature.
for (auto II : Inputs) {
         II->SumIncidence += 1;
         II->Energy += log(II->SumIncidence) / II->SumIncidence;
       }
     }
 
     DistributionNeedsUpdate = true;
   }
 
+  // Log feature and edge coverage every 5 minutes, write result into file
+  // "cov_stats".
+  void LogCoverage(int CurTime, size_t Cov, size_t FeatureCov) {
+    int ElapsedTime = CurTime - LastLogTime;
+    if (ElapsedTime < 300)
+      return;
+
+    std::ofstream LogFile;
+    LogFile.open("cov_stats", std::ofstream::out | std::ofstream::app);
+    LogFile << "time: " << CurTime / 60 << " cov: " << Cov
+            << " feat: " << FeatureCov << "\n";
+    LogFile.close();
+    LastLogTime = CurTime;
+  }
+
+  // Write visited node information into a file which will be consumed by the
+  // dynamic graph analysis module. Reload latest graph centrality scores. Also
+  // log all the seed weight, edge weight for debug purpose.
+  void UpdateCentralityScore(int CurTime) {
+    int ElapsedTime = CurTime - LastDumpTime;
+    if (ElapsedTime < 120)
+      return;
+
+    LogVisitedNode();
+    ReloadCentralistScore();
+    std::ofstream LogFile;
+    LogFile.open("weight_dump");
+    size_t Idx = 0;
+    CacheBorderEdgeWeight();
+    LogFile << "### " << CurNumExecutedMutations << "\n";
+    for (auto E : BorderEdge) {
+      uint32_t ParentId = E.first;
+      uint32_t ChildId = E.second;
+      // Log all border edge weight
+      if (EdgeCentralityScore[ChildId] != 0.0 && GlobalEdgeFreqs[ParentId] &&
+          !GlobalEdgeFreqs[ChildId]) {
+        LogFile << BorderEdgeWeight[Idx] << " " << EdgeCentralityScore[ChildId]
+                << " "
+                << sqrt(log(CurNumExecutedMutations) /
+                        GlobalEdgeFreqs[ParentId])
+                << " " << GlobalEdgeFreqs[ParentId] << "\n";
+      }
+      Idx += 1;
+    }
+
+    LogFile << "$$$$$$$$$$$$$$$$$$$\n";
+    for (auto II : Inputs) {
+      LogFile << II->KschedulerEnergy << " " << II->BorderEdgeIdx.size() << " "
+              << II->KschedulerPerfScore << " " << II->NumExecutedMutations
+              << "\n";
+    }
+    LogFile.close();
+    LastDumpTime = CurTime;
+  }
+
+  // Log all visited node into a file for build edge horizon graph.
+  void LogVisitedNode() {
+    std::ofstream LogFile;
+    LogFile.open("cur_coverage");
+
+    for (size_t i = 0; i < kEdgeSetSize; i++) {
+      if (GlobalEdgeFreqs[i] > 0)
+        LogFile << i << " ";
+    }
+
+    LogFile.close();
+
+    std::ofstream SignalFile;
+    SignalFile.open("signal");
+    SignalFile << "1\n";
+    SignalFile.close();
+  }
+
+  // Load updated katz centrality scores.
+  void ReloadCentralistScore() {
+    std::ifstream KatzFile;
+    KatzFile.open("dyn_katz_cent");
+
+    if (KatzFile.good() == false)
+      return;
+
+    int EdgeId;
+    double KatzScore;
+    while (KatzFile >> EdgeId >> KatzScore) {
+      EdgeCentralityScore[EdgeId] = KatzScore;
+    }
+    KatzFile.close();
+  }
+
   bool AddFeature(size_t Idx, uint32_t NewSize, bool Shrink) {
     assert(NewSize);
     Idx = Idx % kFeatureSetSize;
     uint32_t OldSize = GetFeature(Idx);
     if (OldSize == 0 || (Shrink && OldSize > NewSize)) {
       if (OldSize > 0) {
         size_t OldIdx = SmallestElementPerFeature[Idx];
         InputInfo &II = *Inputs[OldIdx];
if (OldSize == 0 || (Shrink && OldSize > NewSize)) {
       // Inputs.size() is guaranteed to be less than UINT32_MAX by AddToCorpus.
       SmallestElementPerFeature[Idx] = static_cast<uint32_t>(Inputs.size());
       InputSizesPerFeature[Idx] = NewSize;
       return true;
     }
     return false;
   }
 
+  // K-Scheduler: increment frequency of feature Idx globally and locally.
+  void KschedulerUpdateFeatureFrequency(InputInfo *II, size_t Idx) {
+    // Convert featuer idx to edge idx
+    uint32_t EdgeId = (Idx / 8) % kFeatureSetSize;
+
+    // Hit a new edge, check if the new edge is a border edge associated with
+    // other seeds. If so, update other seeds' energy.
+    if (GlobalEdgeFreqs[EdgeId] == 0) {
+      for (auto ParentId : Parent[EdgeId]) {
+        if (GlobalEdgeFreqs[ParentId]) {
+          for (auto TmpII : Inputs) {
+            if (TmpII->KschedulerEnergy != 0.0 && TmpII->ComputedBefore) {
+              int TmpIdx = TmpII->SearchAndDeleteBorderEdge(ParentId, EdgeId);
+              // Current border edge is used by this seed's energy computation,
+              // delete current border edge's weight from this seed's energy.
+              if ((TmpIdx != -2) && (TmpIdx != -1)) {
+                TmpII->KschedulerEnergy -=
+                    (BorderEdgeWeight[TmpIdx] * TmpII->KschedulerPerfScore);
+              }
+            }
+          }
+        }
+      }
+    }
+
+    // Increment global edge hit count.
+    GlobalEdgeFreqs[EdgeId]++;
+    // Record edge coverage locally for current seed.
+    RecordVisitedEdge(EdgeId);
+  }
+
+  void SetDistributionNeedsUpdate() {
+    KschedulerDistributionNeedsUpdate = true;
+  }
+  void ClearTmpEdgeSet() { TmpEdgeSet.clear(); }
+
+  // Weight computation for each border edges. We pre-compute all border edges
+  // weight and cache the result in a table to avoid duplicated computation.
+  void CacheBorderEdgeWeight() {
+    int Idx = 0;
+    CurNumExecutedMutations = NumExecutedMutations;
+    for (auto E : BorderEdge) {
+      uint32_t ParentId = E.first;
+      uint32_t ChildId = E.second;
+
+      if ((EdgeCentralityScore[ChildId] != 0.0) &&
+          (GlobalEdgeFreqs[ParentId]) && (!GlobalEdgeFreqs[ChildId])) {
+        // weight = Katz_score_child *
+        // sqrt(log(total_num_executed)/hit_count_parent)
+        BorderEdgeWeight[Idx] =
+            EdgeCentralityScore[ChildId] *
+            sqrt(log(CurNumExecutedMutations) / GlobalEdgeFreqs[ParentId]);
+      }
+      Idx += 1;
+    }
+  }
+
   // Increment frequency of feature Idx globally and locally.
   void UpdateFeatureFrequency(InputInfo *II, size_t Idx) {
     uint32_t Idx32 = Idx % kFeatureSetSize;
 
     // Saturated increment.
     if (GlobalFeatureFreqs[Idx32] == 0xFFFF)
       return;
     uint16_t Freq = GlobalFeatureFreqs[Idx32]++;
void UpdateFeatureFrequency(InputInfo *II, size_t Idx) {
     // Update local frequencies.
     if (II)
       II->UpdateFeatureFrequency(Idx32);
   }
 
   size_t NumFeatures() const { return NumAddedFeatures; }
   size_t NumFeatureUpdates() const { return NumUpdatedFeatures; }
 
+  // Only for unit testing.
+  uint32_t GetGlobalEdgeFreqs(uint32_t EdgeId) {
+    return GlobalEdgeFreqs[EdgeId];
+  }
+  void SetGlobalEdgeFreqs(uint32_t EdgeId, uint32_t Cnt) {
+    GlobalEdgeFreqs[EdgeId] = Cnt;
+  }
+
 private:
 
   static const bool FeatureDebug = false;
 
   uint32_t GetFeature(size_t Idx) const { return InputSizesPerFeature[Idx]; }
 
   void ValidateFeatureSet() {
     if (FeatureDebug)
if (FeatureDebug) {
       Printf("SCORE\n");
       for (size_t i = 0; i < N; i++)
         Printf("%f ", Weights[i]);
       Printf("Weights\n");
     }
     CorpusDistribution = std::piecewise_constant_distribution<double>(
         Intervals.begin(), Intervals.end(), Weights.begin());
   }
+
+  // Updates the probability distribution for the units in the corpus.
+  // Must be called in three cases
+  // 1. every 2 minutes
+  // 2. new seeds are generated and k-scheduler doesn't compute centrality
+  // weight for them yet because their NumExecutedMutations less than
+  // MinNumMutationsForEachSeed.
+  // 3. new seeds which NumExecutedMutations greater than
+  // MinNumMutationsForEachSeed, k-scheduler starts to compute centrality based
+  // weight for them.
+  //
+  // Hypothesis: inputs that have the highest graph centrality scores are
+  // interesting i.e., they can reach the maximum amount of unvisited code
+  // regions.
+  void KschedulerUpdateCorpusDistribution(Random &Rand, int CurTime) {
+
+    if (!Kscheduler.Enabled)
+      return;
+    if ((!KschedulerDistributionNeedsUpdate) &&
+        (CurTime - LastComputeTime < 120))
+      return;
+
+    KschedulerDistributionNeedsUpdate = false;
+
+    size_t N = Inputs.size();
+    assert(N);
+    Intervals.resize(N + 1);
+    Weights.resize(N);
+    std::iota(Intervals.begin(), Intervals.end(), 0);
+
+    bool VanillaSchedule = true;
+
+    // case1: Compute energy for all seeds every 2 minutes.
+    if (CurTime - LastComputeTime > 120) {
+      // Compute the weights for each border edges and save the results into a
+      // cache table.
+      CacheBorderEdgeWeight();
+      for (auto II : Inputs) {
+        // Compute energy when the minimum mutation on a seed has been
+        // satifsfied. We also skip a seed which has no border edges.
+        if (II->FuzzedBefore && (II->KschedulerEnergy != 0.0) &&
+            (II->NumExecutedMutations >=
+             Kscheduler.MinNumMutationsForEachSeed)) {
+          ComputeEnergy(II, AvgExecTime);
+          II->ComputedBefore = true;
+        }
+      }
+      LastComputeTime = CurTime;
+    }
+
+    // case2: Compute energy only for new seeds whose minmimum mutations have
+    // been satisfied. We also skip a seed which has no border edges.
+    else {
+      for (auto II : Inputs) {
+        if (!II->ComputedBefore && (II->KschedulerEnergy != 0.0) &&
+            (II->NumExecutedMutations >=
+             Kscheduler.MinNumMutationsForEachSeed)) {
+          ComputeEnergy(II, AvgExecTime);
+          II->ComputedBefore = true;
+        }
+      }
+    }
+
+    // case3: Use initial weight for new seeds whose minmimum mutations less
+    // than MinNumMutationsForEachSeed.
+    for (size_t i = 0; i < N; i++) {
+
+      if (Inputs[i]->NumFeatures == 0) {
+        // If the seed doesn't represent any features, assign zero energy.
+        Weights[i] = 0.;
+      } else if (Inputs[i]->NumExecutedMutations / kMaxMutationFactor >
+                 NumExecutedMutations / Inputs.size()) {
+        // If the seed was fuzzed a lot more than average, assign zero energy.
+        Weights[i] = 0.;
+      } else {
+        // Otherwise, simply assign the computed energy.
+        Weights[i] = Inputs[i]->KschedulerEnergy;
+      }
+
+      // If energy for all seeds is zero, fall back to vanilla schedule.
+      if (Weights[i] > 0.0)
+        VanillaSchedule = false;
+    
+      if(Weights[i] == 0.0){
+        if (!Inputs[i]->SlowInput) {
+          // Substrate runtime cost of old input from the sum of
+          // total execution time over seed corpus.
+          TotalExecTime -= Inputs[i]->TimeOfUnit; 
+          NumOfSlowInputs += 1;
+          if ( Inputs.size() - NumOfSlowInputs > 0)
+            AvgExecTime = TotalExecTime / (Inputs.size() - NumOfSlowInputs);
+          else
+            AvgExecTime = std::chrono::microseconds(0); 
+          Inputs[i]->SlowInput = true;
+        }
+      }
+    }
+
+    if (VanillaSchedule) {
+      for (size_t i = 0; i < N; i++)
+        Weights[i] =
+            Inputs[i]->NumFeatures
+                ? static_cast<double>((i + 1) *
+                                      (Inputs[i]->HasFocusFunction ? 1000 : 1))
+                : 0.;
+    }
+
+    if (FeatureDebug) {
+      for (size_t i = 0; i < N; i++)
+        Printf("%zd ", Inputs[i]->NumFeatures);
+      Printf("SCORE\n");
+      for (size_t i = 0; i < N; i++)
+        Printf("%f ", Weights[i]);
+      Printf("Weights\n");
+    }
+    CorpusDistribution = std::piecewise_constant_distribution<double>(
+        Intervals.begin(), Intervals.end(), Weights.begin());
+  }
+
   std::piecewise_constant_distribution<double> CorpusDistribution;
 
   std::vector<double> Intervals;
   std::vector<double> Weights;
 
   std::unordered_set<std::string> Hashes;
   std::vector<InputInfo *> Inputs;
 
+  int LastComputeTime = 0;
+  int LastLogTime = 0;
+  int LastDumpTime = 0;
+  uint32_t NumOfSlowInputs = 0;
+  // Average execution time for all mutations generated by Libfuzzer.
+  std::chrono::microseconds AvgExecTime = std::chrono::microseconds(0);
+  std::chrono::microseconds TotalExecTime = std::chrono::microseconds(0);
   size_t NumAddedFeatures = 0;
   size_t NumUpdatedFeatures = 0;
   uint32_t InputSizesPerFeature[kFeatureSetSize];
   uint32_t SmallestElementPerFeature[kFeatureSetSize];
 
   bool DistributionNeedsUpdate = true;
   uint16_t FreqOfMostAbundantRareFeature = 0;
   uint16_t GlobalFeatureFreqs[kFeatureSetSize] = {};
   std::vector<uint32_t> RareFeatures;
-
   std::string OutputCorpus;
+
+  bool KschedulerDistributionNeedsUpdate = false;
+
+  // Katz centrality score for each edge.
+  double EdgeCentralityScore[kEdgeSetSize] = {0.0}; 
+  // Edge weight for border edge(ParentId, ChildId), defined as
+  // EdgeCentraltiyScore(ChildId) *
+  // sqrt(log(Total_Num_Execution)/HitCount(ParentId)).
+  double BorderEdgeWeight[kEdgeSetSize] = {0.0}; 
+  
+  std::vector<uint32_t> Child[kEdgeSetSize];  // Node-to-children adjacency list
+  std::vector<uint32_t> Parent[kEdgeSetSize]; // Node-to-parent adjancency list
+  std::vector<uint32_t> TmpEdgeSet; // Record edge coverage set for each seed.
+  
+  // A vector of all possible border edges defined in tuple (ParentId, ChildId).
+  std::vector<std::pair<uint32_t, uint32_t>> BorderEdge; 
+  // Hit counter for global edge coverage.
+  uint32_t GlobalEdgeFreqs[kEdgeSetSize] ={}; 
 };
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_CORPUS

compiler-rt/lib/fuzzer/FuzzerDriver.cpp

int AnalyzeDictionary(Fuzzer *F, const std::vector<Unit> &Dict,
   std::vector<int> Usages(Dict.size());
 
   std::vector<size_t> InitialFeatures;
   std::vector<size_t> ModifiedFeatures;
   for (auto &C : Corpus) {
     // Get coverage for the testcase without modifications.
     F->ExecuteCallback(C.data(), C.size());
     InitialFeatures.clear();
-    TPC.CollectFeatures([&](size_t Feature) {
+    TPC.CollectFeatures([&](size_t Feature, bool CountEdge) {
       InitialFeatures.push_back(Feature);
     });
 
     for (size_t i = 0; i < Dict.size(); ++i) {
       std::vector<uint8_t> Data = C;
       auto StartPos = std::search(Data.begin(), Data.end(),
                                   Dict[i].begin(), Dict[i].end());
       // Skip dictionary unit, if the testcase does not contain it.
for (size_t i = 0; i < Dict.size(); ++i) {
 
         StartPos = std::search(EndPos, Data.end(),
                                Dict[i].begin(), Dict[i].end());
       }
 
       // Get coverage for testcase with masked occurrences of dictionary unit.
       F->ExecuteCallback(Data.data(), Data.size());
       ModifiedFeatures.clear();
-      TPC.CollectFeatures([&](size_t Feature) {
+      TPC.CollectFeatures([&](size_t Feature, bool CountEdge) {
         ModifiedFeatures.push_back(Feature);
       });
 
       if (InitialFeatures == ModifiedFeatures)
         --Scores[i];
       else
         Scores[i] += 2;
     }
Printf("INFO: Running with entropic power schedule (0x%X, %d).\n",
            Options.EntropicNumberOfRarestFeatures);
   struct EntropicOptions Entropic;
   Entropic.Enabled = Options.Entropic;
   Entropic.FeatureFrequencyThreshold =
       Options.EntropicFeatureFrequencyThreshold;
   Entropic.NumberOfRarestFeatures = Options.EntropicNumberOfRarestFeatures;
   Entropic.ScalePerExecTime = Options.EntropicScalePerExecTime;
 
+  Options.Kscheduler = Flags.kscheduler;
+  Options.KschedulerMinNumMutationsForEachSeed =
+      (size_t)Flags.kscheduler_min_num_mutations_for_each_seed;
+  Options.KschedulerPerThres = (size_t)Flags.kscheduler_per_thres;
+  if (Options.Kscheduler)
+    Printf("INFO: Running with K-Schedule ( %d, %d).\n",
+           Options.KschedulerMinNumMutationsForEachSeed,
+           Options.KschedulerPerThres);
+  struct KschedulerOptions Kscheduler;
+  Kscheduler.Enabled = Options.Kscheduler;
+  Kscheduler.MinNumMutationsForEachSeed =
+      Options.KschedulerMinNumMutationsForEachSeed;
+  Kscheduler.PerThres = Options.KschedulerPerThres;
+
   unsigned Seed = Flags.seed;
   // Initialize Seed.
   if (Seed == 0)
     Seed = static_cast<unsigned>(
         std::chrono::system_clock::now().time_since_epoch().count() + GetPid());
   if (Flags.verbosity)
     Printf("INFO: Seed: %u\n", Seed);
 
   if (Flags.collect_data_flow && !Flags.fork &&
       !(Flags.merge || Flags.set_cover_merge)) {
     if (RunIndividualFiles)
       return CollectDataFlow(Flags.collect_data_flow, Flags.data_flow_trace,
                         ReadCorpora({}, *Inputs));
     else
       return CollectDataFlow(Flags.collect_data_flow, Flags.data_flow_trace,
                         ReadCorpora(*Inputs, {}));
   }
 
   Random Rand(Seed);
   auto *MD = new MutationDispatcher(Rand, Options);
-  auto *Corpus = new InputCorpus(Options.OutputCorpus, Entropic);
+  auto *Corpus = new InputCorpus(Options.OutputCorpus, Entropic, Kscheduler);
   auto *F = new Fuzzer(Callback, *Corpus, *MD, Options);
 
   for (auto &U: Dictionary)
     if (U.size() <= Word::GetMaxSize())
       MD->AddWordToManualDictionary(Word(U.data(), U.size()));
 
       // Threads are only supported by Chrome. Don't use them with emscripten
       // for now.

compiler-rt/lib/fuzzer/FuzzerFlags.def

FUZZER_FLAG_INT(entropic_number_of_rarest_features, 100, "Experimental. If "
      "entropic is enabled, we keep track of the frequencies only for the "
      "Top-X least abundant features (union features that are considered as "
      "rare).")
 FUZZER_FLAG_INT(entropic_scale_per_exec_time, 0, "Experimental. If 1, "
      "the Entropic power schedule gets scaled based on the input execution "
      "time. Inputs with lower execution time get scheduled more (up to 30x). "
      "Note that, if 1, fuzzer stops from being deterministic even if a "
      "non-zero random seed is given.")
-
+FUZZER_FLAG_INT(kscheduler, 0, "Experimental. Enables K-Schedule.")
+FUZZER_FLAG_INT(kscheduler_per_thres, 4, "Experimental. PerfScore threshold. ")
+FUZZER_FLAG_INT(kscheduler_min_num_mutations_for_each_seed, 100, "Experimental. If "
+    "K-Scheduler is enabled, we generate at least a specified number of mutations "
+    "for each seed before using graph centrality score to compute its seed weight.")
 FUZZER_FLAG_INT(analyze_dict, 0, "Experimental")
 FUZZER_DEPRECATED_FLAG(use_clang_coverage)
 FUZZER_FLAG_STRING(data_flow_trace, "Experimental: use the data flow trace")
 FUZZER_FLAG_STRING(collect_data_flow,
                    "Experimental: collect the data flow trace")
 
 FUZZER_FLAG_INT(create_missing_dirs, 0, "Automatically attempt to create "
      "directories for arguments that would normally expect them to already "
      "exist (i.e. artifact_prefix, exact_artifact_path, features_dir, corpus)")

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
   assert(Size < std::numeric_limits<uint32_t>::max());
 
   ExecuteCallback(Data, Size);
   auto TimeOfUnit = duration_cast<microseconds>(UnitStopTime - UnitStartTime);
 
   UniqFeatureSetTmp.clear();
   size_t FoundUniqFeaturesOfII = 0;
   size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
-  TPC.CollectFeatures([&](uint32_t Feature) {
+  Corpus.ClearTmpEdgeSet();
+  TPC.CollectFeatures([&](uint32_t Feature, bool CountEdge) {
     if (Corpus.AddFeature(Feature, static_cast<uint32_t>(Size), Options.Shrink))
       UniqFeatureSetTmp.push_back(Feature);
     if (Options.Entropic)
       Corpus.UpdateFeatureFrequency(II, Feature);
+    if (Options.Kscheduler && CountEdge)
+      Corpus.KschedulerUpdateFeatureFrequency(II, Feature);
+
     if (Options.ReduceInputs && II && !II->NeverReduce)
       if (std::binary_search(II->UniqFeatureSet.begin(),
                              II->UniqFeatureSet.end(), Feature))
         FoundUniqFeaturesOfII++;
   });
   if (FoundUniqFeatures)
     *FoundUniqFeatures = FoundUniqFeaturesOfII;
   PrintPulseAndReportSlowInput(Data, Size);

 
 void Fuzzer::PrintStatusForNewUnit(const Unit &U, const char *Text) {
   if (!Options.PrintNEW)
     return;
   PrintStats(Text, "");
   if (Options.Verbosity) {
     Printf(" L: %zd/%zd ", U.size(), Corpus.MaxInputSize());
     MD.PrintMutationSequence(Options.Verbosity >= 2);
-    Printf("\n");
+    Printf(" ElapsedTime: %d\n", (int)(secondsSinceProcessStartUp() / 60));
   }
 }
 
 void Fuzzer::ReportNewCoverage(InputInfo *II, const Unit &U) {
   II->NumSuccessfullMutations++;
   MD.RecordSuccessfulMutationSequence();
   PrintStatusForNewUnit(U, II->Reduced ? "REDUCE" : "NEW   ");
   WriteToOutputCorpus(U);
if (EF->__lsan_do_recoverable_leak_check()) { // Leak is found, report it.
     PrintFinalStats();
     _Exit(Options.ErrorExitCode); // not exit() to disable lsan further on.
   }
 }
 
 void Fuzzer::MutateAndTestOne() {
   MD.StartMutationSequence();
 
-  auto &II = Corpus.ChooseUnitToMutate(MD.GetRand());
+  auto &II =
+      Corpus.ChooseUnitToMutate(MD.GetRand(), secondsSinceProcessStartUp());
   if (Options.DoCrossOver) {
     auto &CrossOverII = Corpus.ChooseUnitToCrossOverWith(
-        MD.GetRand(), Options.CrossOverUniformDist);
+        MD.GetRand(), Options.CrossOverUniformDist,
+        secondsSinceProcessStartUp());
     MD.SetCrossOverWith(&CrossOverII.U);
   }
   const auto &U = II.U;
   memcpy(BaseSha1, II.Sha1, sizeof(BaseSha1));
   assert(CurrentUnitData);
   size_t Size = U.size();
   assert(Size <= MaxInputLen && "Oversized Unit");
   memcpy(CurrentUnitData, U.data(), Size);
if (NewCov) {
       ReportNewCoverage(&II, {CurrentUnitData, CurrentUnitData + Size});
       break;  // We will mutate this input more in the next rounds.
     }
     if (Options.ReduceDepth && !FoundUniqFeatures)
       break;
   }
 
   II.NeedsEnergyUpdate = true;
+
+  // Log coverage every 5 minutes.
+  Corpus.LogCoverage(secondsSinceProcessStartUp(), TPC.GetTotalPCCoverage(),
+                     Corpus.NumFeatures());
+
+  // K-Scheduler
+  if (Options.Kscheduler) {
+    II.FuzzedBefore = true;
+    Corpus.UpdateCentralityScore(secondsSinceProcessStartUp());
+    if (!II.ComputedBefore && (II.NumExecutedMutations >
+                               Options.KschedulerMinNumMutationsForEachSeed))
+      Corpus.SetDistributionNeedsUpdate();
+  }
 }
 
 void Fuzzer::PurgeAllocator() {
   if (Options.PurgeAllocatorIntervalSec < 0 || !EF->__sanitizer_purge_allocator)
     return;
   if (duration_cast<seconds>(system_clock::now() -
                              LastAllocatorPurgeAttemptTime)
           .count() < Options.PurgeAllocatorIntervalSec)

compiler-rt/lib/fuzzer/FuzzerMerge.cpp

for (size_t i = M.FirstNotProcessedFile; i < M.Files.size(); i++) {
     // Run.
     TPC.ResetMaps();
     ExecuteCallback(U.data(), U.size());
     // Collect coverage. We are iterating over the files in this order:
     // * First, files in the initial corpus ordered by size, smallest first.
     // * Then, all other files, smallest first.
     std::set<size_t> Features;
     if (IsSetCoverMerge)
-      TPC.CollectFeatures([&](size_t Feature) { Features.insert(Feature); });
+      TPC.CollectFeatures(
+          [&](size_t Feature, bool CountEdge) { Features.insert(Feature); });
     else
-      TPC.CollectFeatures([&](size_t Feature) {
+      TPC.CollectFeatures([&](size_t Feature, bool CountEdge) {
         if (AllFeatures.insert(Feature).second)
           Features.insert(Feature);
       });
     TPC.UpdateObservedPCs();
     // Show stats.
     if (!(TotalNumberOfRuns & (TotalNumberOfRuns - 1)))
       PrintStatsWrapper("pulse ");
     if (TotalNumberOfRuns == M.NumFilesInFirstCorpus)

compiler-rt/lib/fuzzer/FuzzerOptions.h

struct FuzzingOptions {
   size_t MaxNumberOfRuns = -1L;
   int ReportSlowUnits = 10;
   bool OnlyASCII = false;
   bool Entropic = true;
   bool ForkCorpusGroups = false;
   size_t EntropicFeatureFrequencyThreshold = 0xFF;
   size_t EntropicNumberOfRarestFeatures = 100;
   bool EntropicScalePerExecTime = false;
+  bool Kscheduler = false;
+  size_t KschedulerMinNumMutationsForEachSeed = 100;
+  size_t KschedulerPerThres = 4;
   std::string OutputCorpus;
   std::string ArtifactPrefix = "./";
   std::string ExactArtifactPath;
   std::string ExitOnSrcPos;
   std::string ExitOnItem;
   std::string FocusFunction;
   std::string DataFlowTrace;
   std::string CollectDataFlow;

compiler-rt/lib/fuzzer/FuzzerTracePC.h

unsigned CounterToFeature(T Counter) {
     else if (Counter >= 3) Bit = 2;
     else if (Counter >= 2) Bit = 1;
     return Bit;
 }
 
 template <class Callback> // void Callback(uint32_t Feature)
 ATTRIBUTE_NO_SANITIZE_ADDRESS ATTRIBUTE_NOINLINE size_t
 TracePC::CollectFeatures(Callback HandleFeature) const {
-  auto Handle8bitCounter = [&](size_t FirstFeature,
-                               size_t Idx, uint8_t Counter) {
-    if (UseCounters)
-      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx * 8 +
-                                          CounterToFeature(Counter)));
-    else
-      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx));
+  auto Handle8bitCounter = [&](size_t FirstFeature, size_t Idx,
+                               uint8_t Counter) {
+    if (UseCounters) {
+      uint32_t feat = FirstFeature + Idx * 8 + CounterToFeature(Counter);
+      HandleFeature(feat, true);
+    } else
+      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx), true);
   };
 
   size_t FirstFeature = 0;
 
   for (size_t i = 0; i < NumModules; i++) {
     for (size_t r = 0; r < Modules[i].NumRegions; r++) {
       if (!Modules[i].Regions[r].Enabled) continue;
       FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start,
                                              Modules[i].Regions[r].Stop,
                                              FirstFeature, Handle8bitCounter);
     }
   }
 
   FirstFeature +=
       8 * ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(),
                              FirstFeature, Handle8bitCounter);
 
   if (UseValueProfileMask) {
     ValueProfileMap.ForEach([&](size_t Idx) {
-      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx));
+      HandleFeature(static_cast<uint32_t>(FirstFeature + Idx), false);
     });
     FirstFeature += ValueProfileMap.SizeInBits();
   }
 
   // Step function, grows similar to 8 * Log_2(A).
   auto StackDepthStepFunction = [](size_t A) -> size_t {
     if (!A)
       return A;
     auto Log2 = Log(A);
     if (Log2 < 3)
       return A;
     Log2 -= 3;
     return (Log2 + 1) * 8 + ((A >> Log2) & 7);
   };
   assert(StackDepthStepFunction(1024) == 64);
   assert(StackDepthStepFunction(1024 * 4) == 80);
   assert(StackDepthStepFunction(1024 * 1024) == 144);
 
   if (auto MaxStackOffset = GetMaxStackOffset()) {
-    HandleFeature(static_cast<uint32_t>(
-        FirstFeature + StackDepthStepFunction(MaxStackOffset / 8)));
+    uint32_t feat = FirstFeature + StackDepthStepFunction(MaxStackOffset / 8);
+    HandleFeature(feat, false);
     FirstFeature += StackDepthStepFunction(std::numeric_limits<size_t>::max());
   }
 
   return FirstFeature;
 }
 
 extern TracePC TPC;
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_TRACE_PC

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

if (NumInline8bitCounters && NumInline8bitCounters != NumPCsInPCTables) {
              "Also check https://bugs.llvm.org/show_bug.cgi?id=34636\n"
              "for possible workarounds (tl;dr: don't use the old GNU ld)\n");
       _Exit(1);
     }
   }
   if (size_t NumExtraCounters = ExtraCountersEnd() - ExtraCountersBegin())
     Printf("INFO: %zd Extra Counters\n", NumExtraCounters);
 
-  size_t MaxFeatures = CollectFeatures([](uint32_t) {});
+  size_t MaxFeatures = CollectFeatures([](uint32_t, bool) {});
   if (MaxFeatures > std::numeric_limits<uint32_t>::max())
     Printf("WARNING: The coverage PC tables may produce up to %zu features.\n"
            "This exceeds the maximum 32-bit value. Some features may be\n"
            "ignored, and fuzzing may become less precise. If possible,\n"
            "consider refactoring the fuzzer into several smaller fuzzers\n"
            "linked against only a portion of the current target.\n",
            MaxFeatures);
 }

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

 #include "FuzzerCorpus.h"
 #include "FuzzerDictionary.h"
 #include "FuzzerInternal.h"
 #include "FuzzerMerge.h"
 #include "FuzzerMutate.h"
 #include "FuzzerRandom.h"
 #include "FuzzerTracePC.h"
 #include "gtest/gtest.h"
+#include <fstream>
+#include <iostream>
 #include <memory>
 #include <set>
 #include <sstream>
 
 using namespace fuzzer;
 
 // For now, have LLVMFuzzerTestOneInput just to make it link.
 // Later we may want to make unittests that actually call
TEST(FuzzerUtil, PrintASCII) {
   EXPECT_EQ("hello\n", f("hello", "\n"));
 }
 #endif
 
 TEST(Corpus, Distribution) {
   DataFlowTrace DFT;
   Random Rand(0);
   struct EntropicOptions Entropic = {false, 0xFF, 100, false};
-  std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
+  struct KschedulerOptions Kscheduler = {false, 100, 4};
+  std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic, Kscheduler));
   size_t N = 10;
   size_t TriesPerUnit = 1<<16;
   for (size_t i = 0; i < N; i++)
     C->AddToCorpus(Unit{static_cast<uint8_t>(i)}, /*NumFeatures*/ 1,
                    /*MayDeleteFile*/ false, /*HasFocusFunction*/ false,
                    /*ForceAddToCorpus*/ false,
                    /*TimeOfUnit*/ std::chrono::microseconds(0),
                    /*FeatureSet*/ {}, DFT,
                    /*BaseII*/ nullptr);
 
   std::vector<size_t> Hist(N);
   for (size_t i = 0; i < N * TriesPerUnit; i++) {
-    Hist[C->ChooseUnitIdxToMutate(Rand)]++;
+    Hist[C->ChooseUnitIdxToMutate(Rand, 0)]++;
   }
   for (size_t i = 0; i < N; i++) {
     // A weak sanity check that every unit gets invoked.
     EXPECT_GT(Hist[i], TriesPerUnit / N / 3);
   }
 }
 
 TEST(Corpus, Replace) {
   DataFlowTrace DFT;
   struct EntropicOptions Entropic = {false, 0xFF, 100, false};
+  struct KschedulerOptions Kscheduler = {false, 100, 4};
   std::unique_ptr<InputCorpus> C(
-      new InputCorpus(/*OutputCorpus*/ "", Entropic));
+      new InputCorpus(/*OutputCorpus*/ "", Entropic, Kscheduler));
   InputInfo *FirstII =
       C->AddToCorpus(Unit{0x01, 0x00}, /*NumFeatures*/ 1,
                      /*MayDeleteFile*/ false, /*HasFocusFunction*/ false,
                      /*ForceAddToCorpus*/ false,
                      /*TimeOfUnit*/ std::chrono::microseconds(1234),
                      /*FeatureSet*/ {}, DFT,
                      /*BaseII*/ nullptr);
   InputInfo *SecondII =

 }
 
 TEST(Entropic, UpdateFrequency) {
   const size_t One = 1, Two = 2;
   const size_t FeatIdx1 = 0, FeatIdx2 = 42, FeatIdx3 = 12, FeatIdx4 = 26;
   size_t Index;
   // Create input corpus with default entropic configuration
   struct EntropicOptions Entropic = {true, 0xFF, 100, false};
-  std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
+  struct KschedulerOptions Kscheduler = {false, 100, 4};
+  std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic, Kscheduler));
   std::unique_ptr<InputInfo> II(new InputInfo());
 
   C->AddRareFeature(FeatIdx1);
   C->UpdateFeatureFrequency(II.get(), FeatIdx1);
   EXPECT_EQ(II->FeatureFreqs.size(), One);
   C->AddRareFeature(FeatIdx2);
   C->UpdateFeatureFrequency(II.get(), FeatIdx1);
   C->UpdateFeatureFrequency(II.get(), FeatIdx2);
double SubAndSquare(double X, double Y) {
   double R = X - Y;
   R = R * R;
   return R;
 }
 
 TEST(Entropic, ComputeEnergy) {
   const double Precision = 0.01;
   struct EntropicOptions Entropic = {true, 0xFF, 100, false};
-  std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic));
+  struct KschedulerOptions Kscheduler = {false, 100, 4};
+  std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic, Kscheduler));
   std::unique_ptr<InputInfo> II(new InputInfo());
   std::vector<std::pair<uint32_t, uint16_t>> FeatureFreqs = {
       {1, 3}, {2, 3}, {3, 3}};
   II->FeatureFreqs = FeatureFreqs;
   II->NumExecutedMutations = 0;
   II->UpdateEnergy(4, false, std::chrono::microseconds(0));
   EXPECT_LT(SubAndSquare(II->Energy, 1.450805), Precision);
 
   II->NumExecutedMutations = 9;
   II->UpdateEnergy(5, false, std::chrono::microseconds(0));
   EXPECT_LT(SubAndSquare(II->Energy, 1.525496), Precision);
 
   II->FeatureFreqs[0].second++;
   II->FeatureFreqs.push_back(std::pair<uint32_t, uint16_t>(42, 6));
   II->NumExecutedMutations = 20;
   II->UpdateEnergy(10, false, std::chrono::microseconds(0));
   EXPECT_LT(SubAndSquare(II->Energy, 1.792831), Precision);
 }
 
+TEST(Kscheduler, UpdateFrequency) {
+  const size_t FeatIdx1 = 0, FeatIdx2 = 42, FeatIdx3 = 12, FeatIdx4 = 26;
+  // Each EdgeIdx maps to a FeatIdx following the equation (EdgeIdx=FeatIdx/8).
+  const size_t EdgeIdx1 = 0, EdgeIdx2 = 5, EdgeIdx3 = 1, EdgeIdx4 = 3;
+  // Enable Kscheduler
+  struct EntropicOptions Entropic = {false, 0xFF, 100, false};
+  struct KschedulerOptions Kscheduler = {true, 100, 4};
+
+  // Generate dummy graph analysis file
+  std::ofstream KatzFile;
+  KatzFile.open("katz_cent");
+  KatzFile << "1 1.2\n2 0.5\n3 0.5\n4 1.7\n5 0.5\n6 1.2\n7 0.5\n8 0.5\n";
+  KatzFile.close();
+
+  std::ofstream ChildFile;
+  ChildFile.open("child_node");
+  ChildFile << "1 2 3\n2\n3\n4 5 6\n5\n6 7 8\n7\n8\n";
+  ChildFile.close();
+
+  std::ofstream ParentFile;
+  ParentFile.open("parent_node");
+  ParentFile << "1\n2 1\n3 1\n4\n5 4\n6 4\n7 6\n8 6\n";
+  ParentFile.close();
+
+  std::ofstream EdgeFile;
+  EdgeFile.open("border_edges");
+  EdgeFile << "1 2\n1 3\n4 5\n4 6\n6 7\n6 8\n";
+  EdgeFile.close();
+
+  std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic, Kscheduler));
+  std::unique_ptr<InputInfo> II(new InputInfo());
+
+  C->KschedulerUpdateFeatureFrequency(II.get(), FeatIdx1);
+  EXPECT_EQ(C->GetGlobalEdgeFreqs(EdgeIdx1), 1);
+  C->KschedulerUpdateFeatureFrequency(II.get(), FeatIdx1);
+  C->KschedulerUpdateFeatureFrequency(II.get(), FeatIdx2);
+  EXPECT_EQ(C->GetGlobalEdgeFreqs(EdgeIdx1), 2);
+  EXPECT_EQ(C->GetGlobalEdgeFreqs(EdgeIdx2), 1);
+
+  C->KschedulerUpdateFeatureFrequency(II.get(), FeatIdx3);
+  C->KschedulerUpdateFeatureFrequency(II.get(), FeatIdx3);
+  C->KschedulerUpdateFeatureFrequency(II.get(), FeatIdx3);
+  EXPECT_EQ(C->GetGlobalEdgeFreqs(EdgeIdx3), 3);
+  C->KschedulerUpdateFeatureFrequency(II.get(), FeatIdx4);
+  EXPECT_EQ(C->GetGlobalEdgeFreqs(EdgeIdx4), 1);
+}
+
+TEST(Kscheduler, ComputeEnergy) {
+  const double Precision = 0.01;
+  // Enable Kscheduler
+  struct EntropicOptions Entropic = {false, 0xFF, 100, false};
+  struct KschedulerOptions Kscheduler = {true, 100, 4};
+
+  // Generate dummy graph analysis file
+  std::ofstream KatzFile;
+  KatzFile.open("katz_cent");
+  KatzFile << "1 1.2\n2 0.5\n3 0.5\n4 1.7\n5 0.5\n6 1.2\n7 0.5\n8 0.5\n";
+  KatzFile.close();
+
+  std::ofstream ChildFile;
+  ChildFile.open("child_node");
+  ChildFile << "1 2 3\n2\n3\n4 5 6\n5\n6 7 8\n7\n8\n";
+  ChildFile.close();
+
+  std::ofstream ParentFile;
+  ParentFile.open("parent_node");
+  ParentFile << "1\n2 1\n3 1\n4\n5 4\n6 4\n7 6\n8 6\n";
+  ParentFile.close();
+
+  std::ofstream EdgeFile;
+  EdgeFile.open("border_edges");
+  EdgeFile << "1 2\n1 3\n4 5\n4 6\n6 7\n6 8\n";
+  EdgeFile.close();
+
+  std::unique_ptr<InputCorpus> C(new InputCorpus("", Entropic, Kscheduler));
+  std::unique_ptr<InputInfo> II1(new InputInfo());
+  std::unique_ptr<InputInfo> II2(new InputInfo());
+
+  II1->EdgeSet = {1, 2};
+  II2->EdgeSet = {4, 5};
+  II1->TimeOfUnit = std::chrono::microseconds(223);
+  II2->TimeOfUnit = std::chrono::microseconds(221);
+  C->SetGlobalEdgeFreqs(1, 1);
+  C->SetGlobalEdgeFreqs(2, 1);
+  C->SetGlobalEdgeFreqs(4, 1);
+  C->SetGlobalEdgeFreqs(5, 1);
+  C->SetCurNumExecutedMutations(2);
+
+  C->ComputeEnergy(II1.get(), std::chrono::microseconds(200));
+  C->ComputeEnergy(II2.get(), std::chrono::microseconds(200));
+
+  EXPECT_LT(SubAndSquare(II1->KschedulerEnergy, 41.627731), Precision);
+  EXPECT_LT(SubAndSquare(II2->KschedulerEnergy, 99.906553), Precision);
+}
+
 int main(int argc, char **argv) {
   testing::InitGoogleTest(&argc, argv);
   return RUN_ALL_TESTS();
 }

llvm/docs/ReleaseNotes.rst

 
 * Added support for the Armv9-A, Armv9.1-A and Armv9.2-A architectures.
 * The compiler now recognises the "tune-cpu" function attribute to support
   the use of the -mtune frontend flag. This allows certain scheduling features
   and optimisations to be enabled independently of the architecture. If the
   "tune-cpu" attribute is absent it tunes according to the "target-cpu".
 * Fixed relocations against temporary symbols (e.g. in jump tables and
   constant pools) in large COFF object files.
+* Auto-vectorization now targets SVE by default when available.
 
 Changes to the ARM Backend
 --------------------------
 
 * Added support for the Armv9-A, Armv9.1-A and Armv9.2-A architectures.
 * Added support for the Armv8.1-M PACBTI-M extension.
 * Changed the assembly comment string for MSVC targets to ``@`` (consistent
   with the MinGW and ELF targets), freeing up ``;`` to be used as