# Global Metrics

path: .metrics.nom.closures
old: 0.0
new: 2.0
path: .metrics.nom.functions
old: 0.0
new: 35.0
path: .metrics.nom.total
old: 0.0
new: 37.0
path: .metrics.nargs.sum
old: 0.0
new: 22.0
path: .metrics.nargs.average
old: null
new: 0.5945945945945946
path: .metrics.mi.mi_original
old: 40.61189519480115
new: -9.132007978330137
path: .metrics.mi.mi_sei
old: 9.957406614064052
new: -49.97046520375379
path: .metrics.mi.mi_visual_studio
old: 23.74964631274921
new: 0.0
path: .metrics.cyclomatic.sum
old: 19.0
new: 119.0
path: .metrics.cyclomatic.average
old: 1.0
new: 2.975
path: .metrics.loc.sloc
old: 199.0
new: 533.0
path: .metrics.loc.ploc
old: 150.0
new: 398.0
path: .metrics.loc.lloc
old: 0.0
new: 203.0
path: .metrics.loc.cloc
old: 23.0
new: 71.0
path: .metrics.loc.blank
old: 26.0
new: 64.0
path: .metrics.cognitive.sum
old: 0.0
new: 87.0
path: .metrics.cognitive.average
old: null
new: 2.3513513513513513
path: .metrics.nexits.average
old: null
new: 0.8108108108108109
path: .metrics.nexits.sum
old: 0.0
new: 30.0
path: .metrics.halstead.estimated_program_length
old: 865.2014396370754
new: 1563.602792097688
path: .metrics.halstead.level
old: 0.23552123552123555
new: 0.00968898881216209
path: .metrics.halstead.time
old: 544.110824828662
new: 105207.895502179
path: .metrics.halstead.effort
old: 9793.994846915915
new: 1893742.119039222
path: .metrics.halstead.purity_ratio
old: 2.6297916098391347
new: 0.6631055097954572
path: .metrics.halstead.difficulty
old: 4.245901639344262
new: 103.20994475138122
path: .metrics.halstead.n2
old: 122.0
new: 181.0
path: .metrics.halstead.N2
old: 148.0
new: 958.0
path: .metrics.halstead.bugs
old: 0.1525873952353958
new: 5.102221450697235
path: .metrics.halstead.vocabulary
old: 129.0
new: 220.0
path: .metrics.halstead.n1
old: 7.0
new: 39.0
path: .metrics.halstead.length
old: 329.0
new: 2358.0
path: .metrics.halstead.N1
old: 181.0
new: 1400.0
path: .metrics.halstead.volume
old: 2306.6937670342504
new: 18348.44620449115

# Spaces Data

## Minimal test - lines (25, 531)

path: .spaces[0].metrics.cognitive.average
old: null
new: 2.3513513513513513
path: .spaces[0].metrics.cognitive.sum
old: 0.0
new: 87.0
path: .spaces[0].metrics.cyclomatic.average
old: 1.0
new: 3.0256410256410255
path: .spaces[0].metrics.cyclomatic.sum
old: 1.0
new: 118.0
path: .spaces[0].metrics.mi.mi_original
old: 132.13127313109095
new: -8.04289871526808
path: .spaces[0].metrics.mi.mi_visual_studio
old: 77.26975036905904
new: 0.0
path: .spaces[0].metrics.mi.mi_sei
old: 115.02610035996176
new: -49.88622395096361
path: .spaces[0].metrics.nargs.average
old: null
new: 0.5945945945945946
path: .spaces[0].metrics.nargs.sum
old: 0.0
new: 22.0
path: .spaces[0].metrics.loc.ploc
old: 4.0
new: 385.0
path: .spaces[0].metrics.loc.cloc
old: 0.0
new: 60.0
path: .spaces[0].metrics.loc.sloc
old: 4.0
new: 507.0
path: .spaces[0].metrics.loc.blank
old: 0.0
new: 62.0
path: .spaces[0].metrics.loc.lloc
old: 0.0
new: 203.0
path: .spaces[0].metrics.nom.closures
old: 0.0
new: 2.0
path: .spaces[0].metrics.nom.functions
old: 0.0
new: 35.0
path: .spaces[0].metrics.nom.total
old: 0.0
new: 37.0
path: .spaces[0].metrics.halstead.n2
old: 5.0
new: 174.0
path: .spaces[0].metrics.halstead.time
old: 1.2477132986922683
new: 107509.87066714773
path: .spaces[0].metrics.halstead.N2
old: 5.0
new: 950.0
path: .spaces[0].metrics.halstead.bugs
old: 0.0026534054573181228
new: 5.176377907057659
path: .spaces[0].metrics.halstead.length
old: 8.0
new: 2350.0
path: .spaces[0].metrics.halstead.level
old: 1.0
new: 0.009392712550607286
path: .spaces[0].metrics.halstead.effort
old: 22.458839376460833
new: 1935177.6720086588
path: .spaces[0].metrics.halstead.estimated_program_length
old: 13.60964047443681
new: 1501.2028548133064
path: .spaces[0].metrics.halstead.vocabulary
old: 7.0
new: 213.0
path: .spaces[0].metrics.halstead.difficulty
old: 1.0
new: 106.46551724137932
path: .spaces[0].metrics.halstead.volume
old: 22.458839376460833
new: 18176.56760753072
path: .spaces[0].metrics.halstead.n1
old: 2.0
new: 39.0
path: .spaces[0].metrics.halstead.N1
old: 3.0
new: 1400.0
path: .spaces[0].metrics.halstead.purity_ratio
old: 1.7012050593046013
new: 0.6388097254524708
path: .spaces[0].metrics.nexits.sum
old: 0.0
new: 30.0
path: .spaces[0].metrics.nexits.average
old: null
new: 0.8108108108108109

### Code

    namespace fuzzer {

    struct InputInfo {
      Unit U;  // The actual input data.
      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 MayDeleteFile = false;
      bool Reduced = false;
      bool HasFocusFunction = false;
      Vector UniqFeatureSet;
      Vector DataFlowTraceForFocusFunction;
      // Power schedule.
      bool NeedsEnergyUpdate = false;
      double Energy = 0.0;
      size_t SumIncidence = 0;
      Vector> FeatureFreqs;

      // 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(Idx, 0));

        if (Lower != FeatureFreqs.end() && Lower->first == Idx) {
          FeatureFreqs.erase(Lower);
          return true;
        }
        return false;
      }

      // 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.
      void UpdateEnergy(size_t GlobalNumberOfFeatures) {
        Energy = 0.0;
        SumIncidence = 0;

        // Apply add-one smoothing to locally discovered features.
        for (auto F : FeatureFreqs) {
          size_t LocalIncidence = F.second + 1;
          Energy -= LocalIncidence * logl(LocalIncidence);
          SumIncidence += LocalIncidence;
        }

        // Apply add-one smoothing to locally undiscovered features.
        //   PreciseEnergy -= 0; // since logl(1.0) == 0)
        SumIncidence += (GlobalNumberOfFeatures - FeatureFreqs.size());

        // Add a single locally abundant feature apply add-one smoothing.
        size_t AbdIncidence = NumExecutedMutations + 1;
        Energy -= AbdIncidence * logl(AbdIncidence);
        SumIncidence += AbdIncidence;

        // Normalize.
        if (SumIncidence != 0)
          Energy = (Energy / SumIncidence) + logl(SumIncidence);
      }

      // Increment the frequency of the feature Idx.
      void UpdateFeatureFrequency(uint32_t Idx) {
        NeedsEnergyUpdate = true;

        // The local feature frequencies is an ordered vector of pairs.
        // If there are no local feature frequencies, push_back preserves order.
        // Set the feature frequency for feature Idx32 to 1.
        if (FeatureFreqs.empty()) {
          FeatureFreqs.push_back(std::pair(Idx, 1));
          return;
        }

        // Binary search over local feature frequencies sorted by index.
        auto Lower = std::lower_bound(FeatureFreqs.begin(), FeatureFreqs.end(),
                                      std::pair(Idx, 0));

        // If feature Idx32 already exists, increment its frequency.
        // Otherwise, insert a new pair right after the next lower index.
        if (Lower != FeatureFreqs.end() && Lower->first == Idx) {
          Lower->second++;
        } else {
          FeatureFreqs.insert(Lower, std::pair(Idx, 1));
        }
      }
    };

    struct EntropicOptions {
      bool Enabled;
      size_t NumberOfRarestFeatures;
      size_t FeatureFrequencyThreshold;
    };

    class InputCorpus {
      static const uint32_t kFeatureSetSize = 1 << 21;
      static const uint8_t kMaxMutationFactor = 20;
      static const size_t kSparseEnergyUpdates = 100;

      size_t NumExecutedMutations = 0;

      EntropicOptions Entropic;

    public:
      InputCorpus(const std::string &OutputCorpus, EntropicOptions Entropic)
          : Entropic(Entropic), OutputCorpus(OutputCorpus) {
        memset(InputSizesPerFeature, 0, sizeof(InputSizesPerFeature));
        memset(SmallestElementPerFeature, 0, sizeof(SmallestElementPerFeature));
      }
      ~InputCorpus() {
        for (auto II : Inputs)
          delete II;
      }
      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++; }

      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();
        });
      }

      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,
                             const Vector &FeatureSet,
                             const DataFlowTrace &DFT, const InputInfo *BaseII) {
        assert(!U.empty());
        if (FeatureDebug)
          Printf("ADD_TO_CORPUS %zd NF %zd\n", Inputs.size(), NumFeatures);
        Inputs.push_back(new InputInfo());
        InputInfo &II = *Inputs.back();
        II.U = U;
        II.NumFeatures = NumFeatures;
        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.SumIncidence = 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;
        PrintCorpus();
        // ValidateFeatureSet();
        return &II;
      }

      // Debug-only
      void PrintUnit(const Unit &U) {
        if (!FeatureDebug) return;
        for (uint8_t C : U) {
          if (C != 'F' && C != 'U' && C != 'Z')
            C = '.';
          Printf("%c", C);
        }
      }

      // Debug-only
      void PrintFeatureSet(const Vector &FeatureSet) {
        if (!FeatureDebug) return;
        Printf("{");
        for (uint32_t Feature: FeatureSet)
          Printf("%u,", Feature);
        Printf("}");
      }

      // Debug-only
      void PrintCorpus() {
        if (!FeatureDebug) return;
        Printf("======= CORPUS:\n");
        int i = 0;
        for (auto II : Inputs) {
          if (std::find(II->U.begin(), II->U.end(), 'F') != II->U.end()) {
            Printf("[%2d] ", i);
            Printf("%s sz=%zd ", Sha1ToString(II->Sha1).c_str(), II->U.size());
            PrintUnit(II->U);
            Printf(" ");
            PrintFeatureSet(II->UniqFeatureSet);
            Printf("\n");
          }
          i++;
        }
      }

      void Replace(InputInfo *II, const Unit &U) {
        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;
        DistributionNeedsUpdate = true;
      }

      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)];
        assert(!II.U.empty());
        return II;
      }

      // Returns an index of random unit from the corpus to mutate.
      size_t ChooseUnitIdxToMutate(Random &Rand) {
        UpdateCorpusDistribution(Rand);
        size_t Idx = static_cast(CorpusDistribution(Rand));
        assert(Idx < Inputs.size());
        return Idx;
      }

      void PrintStats() {
        for (size_t i = 0; i < Inputs.size(); i++) {
          const auto &II = *Inputs[i];
          Printf("  [% 3zd %s] sz: % 5zd runs: % 5zd succ: % 5zd focus: %d\n", i,
                 Sha1ToString(II.Sha1).c_str(), II.U.size(),
                 II.NumExecutedMutations, II.NumSuccessfullMutations, II.HasFocusFunction);
        }
      }

      void PrintFeatureSet() {
        for (size_t i = 0; i < kFeatureSetSize; i++) {
          if(size_t Sz = GetFeature(i))
            Printf("[%zd: id %zd sz%zd] ", i, SmallestElementPerFeature[i], Sz);
        }
        Printf("\n\t");
        for (size_t i = 0; i < Inputs.size(); i++)
          if (size_t N = Inputs[i]->NumFeatures)
            Printf(" %zd=>%zd ", i, N);
        Printf("\n");
      }

      void DeleteFile(const InputInfo &II) {
        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.NeedsEnergyUpdate = false;
        DistributionNeedsUpdate = true;
        if (FeatureDebug)
          Printf("EVICTED %zd\n", Idx);
      }

      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.
          uint32_t MostAbundantRareFeatureIndices[2] = {RareFeatures[0],
                                                        RareFeatures[0]};
          size_t Delete = 0;
          for (size_t i = 0; i < RareFeatures.size(); i++) {
            uint32_t Idx2 = RareFeatures[i];
            if (GlobalFeatureFreqs[Idx2] >=
                GlobalFeatureFreqs[MostAbundantRareFeatureIndices[0]]) {
              MostAbundantRareFeatureIndices[1] = MostAbundantRareFeatureIndices[0];
              MostAbundantRareFeatureIndices[0] = Idx2;
              Delete = i;
            }
          }

          // Remove most abundant rare feature.
          RareFeatures[Delete] = RareFeatures.back();
          RareFeatures.pop_back();

          for (auto II : Inputs) {
            if (II->DeleteFeatureFreq(MostAbundantRareFeatureIndices[0]))
              II->NeedsEnergyUpdate = true;
          }

          // Set 2nd most abundant as the new most abundant feature count.
          FreqOfMostAbundantRareFeature =
              GlobalFeatureFreqs[MostAbundantRareFeatureIndices[1]];
        }

        // Add rare feature, handle collisions, and update energy.
        RareFeatures.push_back(Idx);
        GlobalFeatureFreqs[Idx] = 0;
        for (auto II : Inputs) {
          II->DeleteFeatureFreq(Idx);

          // Apply add-one smoothing to this locally undiscovered feature.
          // Zero energy seeds will never be fuzzed and remain zero energy.
          if (II->Energy > 0.0) {
            II->SumIncidence += 1;
            II->Energy += logl(II->SumIncidence) / II->SumIncidence;
          }
        }

        DistributionNeedsUpdate = true;
      }

      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];
            assert(II.NumFeatures > 0);
            II.NumFeatures--;
            if (II.NumFeatures == 0)
              DeleteInput(OldIdx);
          } else {
            NumAddedFeatures++;
            if (Entropic.Enabled)
              AddRareFeature((uint32_t)Idx);
          }
          NumUpdatedFeatures++;
          if (FeatureDebug)
            Printf("ADD FEATURE %zd sz %d\n", Idx, NewSize);
          SmallestElementPerFeature[Idx] = Inputs.size();
          InputSizesPerFeature[Idx] = NewSize;
          return true;
        }
        return false;
      }

      // 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]++;

        // Skip if abundant.
        if (Freq > FreqOfMostAbundantRareFeature ||
            std::find(RareFeatures.begin(), RareFeatures.end(), Idx32) ==
                RareFeatures.end())
          return;

        // Update global frequencies.
        if (Freq == FreqOfMostAbundantRareFeature)
          FreqOfMostAbundantRareFeature++;

        // Update local frequencies.
        if (II)
          II->UpdateFeatureFrequency(Idx32);
      }

      size_t NumFeatures() const { return NumAddedFeatures; }
      size_t NumFeatureUpdates() const { return NumUpdatedFeatures; }

    private:

      static const bool FeatureDebug = false;

      size_t GetFeature(size_t Idx) const { return InputSizesPerFeature[Idx]; }

      void ValidateFeatureSet() {
        if (FeatureDebug)
          PrintFeatureSet();
        for (size_t Idx = 0; Idx < kFeatureSetSize; Idx++)
          if (GetFeature(Idx))
            Inputs[SmallestElementPerFeature[Idx]]->Tmp++;
        for (auto II: Inputs) {
          if (II->Tmp != II->NumFeatures)
            Printf("ZZZ %zd %zd\n", II->Tmp, II->NumFeatures);
          assert(II->Tmp == II->NumFeatures);
          II->Tmp = 0;
        }
      }

      // Updates the probability distribution for the units in the corpus.
      // Must be called whenever the corpus or unit weights are changed.
      //
      // Hypothesis: inputs that maximize information about globally rare features
      // are interesting.
      void UpdateCorpusDistribution(Random &Rand) {
        // Skip update if no seeds or rare features were added/deleted.
        // Sparse updates for local change of feature frequencies,
        // i.e., randomly do not skip.
        if (!DistributionNeedsUpdate &&
            (!Entropic.Enabled || Rand(kSparseEnergyUpdates)))
          return;

        DistributionNeedsUpdate = 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;
        if (Entropic.Enabled) {
          for (auto II : Inputs) {
            if (II->NeedsEnergyUpdate && II->Energy != 0.0) {
              II->NeedsEnergyUpdate = false;
              II->UpdateEnergy(RareFeatures.size());
            }
          }

          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]->Energy;
            }

            // If energy for all seeds is zero, fall back to vanilla schedule.
            if (Weights[i] > 0.0)
              VanillaSchedule = false;
          }
        }

        if (VanillaSchedule) {
          for (size_t i = 0; i < N; i++)
            Weights[i] = Inputs[i]->NumFeatures
                             ? (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(
            Intervals.begin(), Intervals.end(), Weights.begin());
      }
      std::piecewise_constant_distribution CorpusDistribution;

      Vector Intervals;
      Vector Weights;

      std::unordered_set Hashes;
      Vector Inputs;

      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] = {};
      Vector RareFeatures;

      std::string OutputCorpus;
    };

    }  // namespace fuzzer