[libFuzzer] Handle unstable edges by poisoning unstable edges

[kevinwkt]

Summary

Added a new mode within flag -handle_unstable for new unstable handling algorithm that does the following:

When you invalidate an edge in TracePC::UpdateUnstableCounters(), you increase a counter value.
Subtract the counter value from total number of new edges found for that input to get the total number of stable edges found.
Collect Features only if new stable edges are found.

This way we would be rewarding an input of finding a new edge only if that edge was deterministically found.

[metzman]

I don't think this will work. This just subtracts the number of unstable edges without actually removing those features? Or do i misunderstand how this actually works?

lib/fuzzer/FuzzerLoop.cpp

500–501

Please don't make multi-line if-bodies without curly braces

[kevinwkt]

In D49578#1169197, @metzman wrote:

I don't think this will work. This just subtracts the number of unstable edges without actually removing those features? Or do i misunderstand how this actually works?

This is Max's method of handling edges described before. (In the chromium bug website.)
This poisons an edge definitely since it won't give weight to a poisoned edge on future runs since it's feature has already been collected from what I remember.

[metzman]

In D49578#1169329, @kevinwkt wrote:

In D49578#1169197, @metzman wrote:

I don't think this will work. This just subtracts the number of unstable edges without actually removing those features? Or do i misunderstand how this actually works?

This is Max's method of handling edges described before. (In the chromium bug website.)

Could you link me to this please?

This poisons an edge definitely since it won't give weight to a poisoned edge on future runs since it's feature has already been collected from what I remember.

It does? where? Suppose a testcase has two new edges one unstable and one stable so it gets added to the corpus. Then we find a smaller testcase with the same stable feature, but the unstable feature isn't removed. Under this method the first testcase stays in the corpus right?

[kevinwkt]

In D49578#1169655, @metzman wrote:

In D49578#1169329, @kevinwkt wrote:

In D49578#1169197, @metzman wrote:

I don't think this will work. This just subtracts the number of unstable edges without actually removing those features? Or do i misunderstand how this actually works?

This is Max's method of handling edges described before. (In the chromium bug website.)

Could you link me to this please?

This poisons an edge definitely since it won't give weight to a poisoned edge on future runs since it's feature has already been collected from what I remember.

It does? where? Suppose a testcase has two new edges one unstable and one stable so it gets added to the corpus. Then we find a smaller testcase with the same stable feature, but the unstable feature isn't removed. Under this method the first testcase stays in the corpus right?

Yes, it would stay in the corpus.
Link: https://bugs.chromium.org/p/chromium/issues/detail?id=854276

[Dor1s]

In D49578#1169197, @metzman wrote:

I don't think this will work. This just subtracts the number of unstable edges without actually removing those features? Or do i misunderstand how this actually works?

I think that was sort of an advantage of the algorithm. We do not remove unstable features, so that any new inputs triggering them won't be considered as new at all, but we don't add such inputs to the corpus to prevent its explosion.

Kevin, we need a test for this one as well. Also, maybe let's focus on finishing the first implementation, as this CL depends on it, and you probably don't want to rebase it and resolve conflicts several times.

[metzman]

In D49578#1169860, @Dor1s wrote:

In D49578#1169197, @metzman wrote:

I don't think this will work. This just subtracts the number of unstable edges without actually removing those features? Or do i misunderstand how this actually works?

I think that was sort of an advantage of the algorithm. We do not remove unstable features, so that any new inputs triggering them won't be considered as new at all, but we don't add such inputs to the corpus to prevent its explosion.

Kevin agreed with me offline that this doesn't prevent corpus growth and does something other than intended. We will think about what it does before proceeding.

[Dor1s]

In D49578#1170815, @metzman wrote:

In D49578#1169860, @Dor1s wrote:

In D49578#1169197, @metzman wrote:

I don't think this will work. This just subtracts the number of unstable edges without actually removing those features? Or do i misunderstand how this actually works?

I think that was sort of an advantage of the algorithm. We do not remove unstable features, so that any new inputs triggering them won't be considered as new at all, but we don't add such inputs to the corpus to prevent its explosion.

Kevin agreed with me offline that this doesn't prevent corpus growth and does something other than intended. We will think about what it does before proceeding.

Ok, let's discuss on Monday. Looks like I'm missing something!

[metzman]

In D49578#1170851, @Dor1s wrote:

In D49578#1170815, @metzman wrote:

In D49578#1169860, @Dor1s wrote:

In D49578#1169197, @metzman wrote:

I don't think this will work. This just subtracts the number of unstable edges without actually removing those features? Or do i misunderstand how this actually works?

I think that was sort of an advantage of the algorithm. We do not remove unstable features, so that any new inputs triggering them won't be considered as new at all, but we don't add such inputs to the corpus to prevent its explosion.

Kevin agreed with me offline that this doesn't prevent corpus growth and does something other than intended. We will think about what it does before proceeding.

Ok, let's discuss on Monday. Looks like I'm missing something!

I was incorrect in previous reply btw. It does prevent some kinds of corpus growth but not others.

[kevinwkt]

PTAL

Created tests.

[Dor1s]

Looks great! Left a couple comments + let's clean up the test. Since the test is specific for handle_unstable=3 mode, can we make it shorter, e.g. leave only 1 or 2 deterministic function, and so on. Also, let's rename the source file to HandleUnstablePoisonUnstableTest.cpp, the test file can be renamed to handle_unstable_poison_unstable.test for better readability.

lib/fuzzer/FuzzerLoop.cpp

463

no need to declare this variable here, move it to line 470, e.g. int NumNewUnstableEdges = ....

lib/fuzzer/FuzzerTracePC.cpp

86–87

let's make this condition the first one, so it would fit 2 lines, and then else if (UnstableMode == ZeroUnstable) case

[kevinwkt]

PTAL
Fixed Max's comments on variable declaration and initialization and moved tests into a single file.

[Dor1s]

Can you re-phrase the CL description please, because it looks like a chat message I've sent to you in the past :)

lib/fuzzer/FuzzerInternal.h

70

I'm not a bit fan of using int type where values actually cannot be negative. IMO size_t is de facto standard type for unsigned values when you don't need a certain precision (e.g. uint32_t). Also, when unsure, always check the code around the project, e.g. https://github.com/llvm-mirror/compiler-rt/blob/master/lib/fuzzer/FuzzerCorpus.h#L28 uses size_t for features as well as execPerSec or getTotalNumberOfRuns a few lines above use size_t for another numerical value that cannot be negative. So, please use size_ instead of int here and in UpdateUnstableCounters.

lib/fuzzer/FuzzerLoop.cpp

517

This place is also a good hint regarding which type you should use.

lib/fuzzer/FuzzerTracePC.cpp

86–87

I think we can invert the condition and do return when it's true, just to decrease the indentation of the lines 88-95. Did Matt not accept that style in one of the past reviews?

lib/fuzzer/FuzzerTracePC.h

77–78

Looks like both FuzzerLoop and FuzzerDriver include FuzzerTracePC.h, so you can move this type definition outside of TracePC class and use it in functions accepting UnstableMode instead of int type.

test/fuzzer/HandleUnstableTest.cpp

47

Why we have 1000 here? Wouldn't things become deterministic after that?

52

is it left from local debugging or you want to have this in the test?

[kevinwkt]

Changed UpdateUnstableCounters to get rid of indentation.
Changed ints to size_ts.

2 questions, @metzman @Dor1s .

1. For changing UnstableMode to UnstableOptions, FuzzerDriver and FuzzerLoop do include TracePC.h, but FuzzerOptions does not. Where would be the right place to cast the int from FuzzerOptions? Would it be fine to cast it right before it gets sent to CheckForUnstableCounters in RunOne? (inside FuzzerLoop)

2. I did put 1000 for the tests with the purpose of a test starting as non deterministic but then turning deterministic. Because when it turns deterministic, collect features take all touched functions along with the new deterministic edge. (Hence it collects t0() in PoisonUnstable). Is this a bad practice? (printf() was for local debugging. Got erased.)

[Dor1s]

In D49578#1174447, @kevinwkt wrote:

Changed UpdateUnstableCounters to get rid of indentation.
Changed ints to size_ts.

2 questions, @metzman @Dor1s .

1. For changing UnstableMode to UnstableOptions, FuzzerDriver and FuzzerLoop do include TracePC.h, but FuzzerOptions does not. Where would be the right place to cast the int from FuzzerOptions? Would it be fine to cast it right before it gets sent to CheckForUnstableCounters in RunOne? (inside FuzzerLoop)

I think it's fine to move enum HandleUnstableOptions declaration into FuzzerOptions.h, it actually seems to be even better place to me than FuzzerTracePC.h.

2. I did put 1000 for the tests with the purpose of a test starting as non deterministic but then turning deterministic. Because when it turns deterministic, collect features take all touched functions along with the new deterministic edge. (Hence it collects t0() in PoisonUnstable). Is this a bad practice? (printf() was for local debugging. Got erased.)

Hmmm, I see, thanks. Probably it's fine, but add a comment before if (c < 1000) { to clarify that.

[kevinwkt]

PTAL
Added comment before c < 1000
Moved enum to FuzzerOptions and included them on necessary files.

[Dor1s]

In D49578#1175799, @kevinwkt wrote:

PTAL
Added comment before c < 1000
Moved enum to FuzzerOptions and included them on necessary files.

I don't see the test source file anymore. Please add it and ask @morehouse to review.

test/fuzzer/handle-unstable.test

23–31

please fix the casing here and on line 33 to be consistent with line 48

[kevinwkt]

PTAL
Updated the syntax for test files.

[kevinwkt]

ptal
Fixed syntax again.

[metzman]

In D49578#1175061, @Dor1s wrote:

In D49578#1174447, @kevinwkt wrote:

Changed UpdateUnstableCounters to get rid of indentation.
Changed ints to size_ts.

2 questions, @metzman @Dor1s .

1. For changing UnstableMode to UnstableOptions, FuzzerDriver and FuzzerLoop do include TracePC.h, but FuzzerOptions does not. Where would be the right place to cast the int from FuzzerOptions? Would it be fine to cast it right before it gets sent to CheckForUnstableCounters in RunOne? (inside FuzzerLoop)

I think it's fine to move enum HandleUnstableOptions declaration into FuzzerOptions.h, it actually seems to be even better place to me than FuzzerTracePC.h.

2. I did put 1000 for the tests with the purpose of a test starting as non deterministic but then turning deterministic. Because when it turns deterministic, collect features take all touched functions along with the new deterministic edge. (Hence it collects t0() in PoisonUnstable). Is this a bad practice? (printf() was for local debugging. Got erased.)

Hmmm, I see, thanks. Probably it's fine, but add a comment before if (c < 1000) { to clarify that.

Agreed, I think this is fine. It's not really non-deterministic, it's just stateful from libFuzzer's point of view, so it's not like we are actually calling rand without a seed in a test.

The one thing I'd like to see added is a brief explanation of what 3 does in FuzzerFlagsDef, though I don't think it is 100% necessary, since this flag is very experimental and somewhat complicated to understand without knowing a lot about libFuzzer.

[Dor1s]

lib/fuzzer/FuzzerTracePC.cpp

91

Can you move this to line 89 please, and then have switch (UnstableMode) ? That way it would be slightly more readable and straightforward.

[kevinwkt]

ptal
Fixed bug that was introduced.

[metzman]

LGTM

[kevinwkt]

lib/fuzzer/FuzzerTracePC.cpp

91

We are supposed to look for the amount of New Unstable Edges.
The way we do this is check if has already been marked as unstable before.
This is also the reason UnstableCounters[UnstableIdx].IsUnstable = true happens after the check.

This bug is now fixed.

[Dor1s]

LGTM

lib/fuzzer/FuzzerFlags.def

120

Frankly, I don't understand this explanation... The problem might be on my side though, let's see what Matt thinks.

[morehouse]

So this is basically the ZeroUnstable mode with one less pass over the counters?

lib/fuzzer/FuzzerDriver.cpp

627

This cast looks odd since we're comparing int to enum without a cast right before this. Probably just do implicit cast.

lib/fuzzer/FuzzerFlags.def

120

This confuses me too.

lib/fuzzer/FuzzerOptions.h

23

Might be cleaner to do something like

enum class UnstableMode {
  Disabled = 0,
  Min = 1,
  Zero = 2,
  Poison = 3,
};

[Dor1s]

lib/fuzzer/FuzzerDriver.cpp

627

That's what I though initially, but surprisingly, implicit cast doesn't work in that direction, only from enum to an integer!

[Dor1s]

lib/fuzzer/FuzzerDriver.cpp

627

$ cat test.cpp 

enum Enum {
  One = 1,
  Two = 2
};

int main(int argc, char* argv[]) {
  Enum E = argc;
  return 0;
}


$ clang++ test.cpp 
test.cpp:8:8: error: cannot initialize a variable of type 'Enum' with an lvalue of type 'int'
  Enum E = argc;
       ^   ~~~~
1 error generated.

[kevinwkt]

In D49578#1176909, @morehouse wrote:

So this is basically the ZeroUnstable mode with one less pass over the counters?

"ZeroUnstable" puts 0 in unstable edges and pretends it was never hit.
"PoisonUnstable" takes into account new unstable edges only if a new stable edge is also found.
This comes from the assumption that unstable edges should be given weight as long as a new deterministic edge is found to reward that input.
We only take into account new unstable edges (and not any unstable edge hit), since we believe that this "reward" for reaching that edge has been given to other inputs.

Hope this makes it a bit clearer.

[morehouse]

Won't the result be the same? This mode will add an input to the corpus as long as there's at least one new stable edge. But so will ZeroUnstable.

[kevinwkt]

In D49578#1176986, @morehouse wrote:

Won't the result be the same? This mode will add an input to the corpus as long as there's at least one new stable edge. But so will ZeroUnstable.

I think the adding to corpus will be similar (it will certainly start out the same way) but because you collect features of these unstable edges while in "Zero" you do not, corpus addition will be different the longer you run this.

[morehouse]

Right. The biggest differences I see are

1. If a new input exercises an edge stably while a previous input exercised that edge unstably, ZeroUnstable will add the new input while PoisonUnstable may not.
2. If an input sometimes exercises an edge twice and sometimes not at all, ZeroUnstable won't add that input while PoisonUnstable will. This is because we record additional features for inputs that hit the same edge multiple times, but PoisonUnstable only subtracts one of those features from the total.

Do we expect this to perform better in some scenarios?

[kevinwkt]

In D49578#1177033, @morehouse wrote:

Right. The biggest differences I see are

1. If a new input exercises an edge stably while a previous input exercised that edge unstably, ZeroUnstable will add the new input while PoisonUnstable may not.
2. If an input sometimes exercises an edge twice and sometimes not at all, ZeroUnstable won't add that input while PoisonUnstable will. This is because we record additional features for inputs that hit the same edge multiple times, but PoisonUnstable only subtracts one of those features from the total.

Do we expect this to perform better in some scenarios?

This is a way to handle unstableness at a small extent, by accepting unstable edges at certain scenarios.
We believe that this "handles unstableness" compared to normal libfuzzer, but its not as extreme as ZeroUnstable.
Since this is slightly faster than ZeroUnstable and we use poison the unstable which we assume will cause less inputs to be added to the corpus in the long run, we think this might produce an interesting result.

[morehouse]

We need to update the summary and flag description then to make it clear what this new mode does.

[kevinwkt]

ptal
Changed to strictly typed enum, and changed names within enum.
Changed description for FuzzerFlag.

[morehouse]

The current flag description still doesn't tell the whole story.

If we detect a new input has unstable edges, we're adding the unstable edges to the corpus features even if we don't add the input itself. This means any time an edge is found to be unstable, we completely ignore that edge forever. Even if a later input exercises the edge stably, we will not consider that edge again.

Is this intentional, or a bug in the implementation?

lib/fuzzer/FuzzerLoop.cpp

496

These casts are quite awkward. Maybe we should just keep Options.HandleUnstable as an int.

lib/fuzzer/FuzzerOptions.h

23

I don't really like these Start and End values, especially since 0 should probably be Disabled.

[Dor1s]

lib/fuzzer/FuzzerLoop.cpp

496

I sort of insisted on not using an int in there, but final decision would yours :)

[morehouse]

lib/fuzzer/FuzzerLoop.cpp

496

Similar libFuzzer options all use int, so at least for consistency I think we should use an int.

I would prefer to get @kcc's opinion in a separate refactoring patch if you would like to switch from ints to enums.

[Dor1s]

lib/fuzzer/FuzzerLoop.cpp

496

Yeah... but there isn't any other option that selects different modes. All of them are either boolean flags, integer values, or a close_fd_mask thing. Either way, I hope we'll choose the best strategy and delete the others in the upcoming weeks, so this option will become a boolean flag after all.

lib/fuzzer/FuzzerDriver.cpp

 //===----------------------------------------------------------------------===//
 
 #include "FuzzerCommand.h"
 #include "FuzzerCorpus.h"
 #include "FuzzerIO.h"
 #include "FuzzerInterface.h"
 #include "FuzzerInternal.h"
 #include "FuzzerMutate.h"
+#include "FuzzerOptions.h"
 #include "FuzzerRandom.h"
 #include "FuzzerShmem.h"
 #include "FuzzerTracePC.h"
 #include <algorithm>
 #include <atomic>
 #include <chrono>
 #include <cstdlib>
 #include <cstring>
Options.SaveArtifacts =
       !DoPlainRun || Flags.minimize_crash_internal_step;
   Options.PrintNewCovPcs = Flags.print_pcs;
   Options.PrintNewCovFuncs = Flags.print_funcs;
   Options.PrintFinalStats = Flags.print_final_stats;
   Options.PrintMutationStats = Flags.print_mutation_stats;
   Options.PrintCorpusStats = Flags.print_corpus_stats;
   Options.PrintCoverage = Flags.print_coverage;
   Options.PrintUnstableStats = Flags.print_unstable_stats;
-  if (Flags.handle_unstable == TracePC::MinUnstable ||
-      Flags.handle_unstable == TracePC::ZeroUnstable)
-    Options.HandleUnstable = Flags.handle_unstable;
+  if (Flags.handle_unstable > (int)UnstableMode::Start &&
+      Flags.handle_unstable < (int)UnstableMode::End)
+    Options.HandleUnstable = static_cast<UnstableMode>(Flags.handle_unstable);
   Options.DumpCoverage = Flags.dump_coverage;
   if (Flags.exit_on_src_pos)
     Options.ExitOnSrcPos = Flags.exit_on_src_pos;
   if (Flags.exit_on_item)
     Options.ExitOnItem = Flags.exit_on_item;
   if (Flags.focus_function)
     Options.FocusFunction = Flags.focus_function;
   if (Flags.data_flow_trace)
     Options.DataFlowTrace = Flags.data_flow_trace;
 

lib/fuzzer/FuzzerFlags.def

FUZZER_FLAG_INT(dump_coverage, 0, "Deprecated."
                                   " If 1, dump coverage information as a"
                                   " .sancov file at exit.")
 FUZZER_FLAG_INT(handle_unstable, 0, "Experimental."
                    " Executes every input 3 times in total if a unique feature"
                    " is found during the first execution."
                    " If 1, we only use the minimum hit count from the 3 runs"
                    " to determine whether an input is interesting."
                    " If 2, we disregard edges that are found unstable for"
-                   " feature collection.")
+                   " feature collection."
+                   " If 3, we collect features if a new stable edge is found."
+                   " Unstable edges will only be taken into account if it is"
+                   " found with a new stable edge.")
 FUZZER_FLAG_INT(print_unstable_stats, 0, "Experimental."
           " If 1, print unstable statistics at exit.")
 FUZZER_FLAG_INT(handle_segv, 1, "If 1, try to intercept SIGSEGV.")
 FUZZER_FLAG_INT(handle_bus, 1, "If 1, try to intercept SIGBUS.")
 FUZZER_FLAG_INT(handle_abrt, 1, "If 1, try to intercept SIGABRT.")
 FUZZER_FLAG_INT(handle_ill, 1, "If 1, try to intercept SIGILL.")
 FUZZER_FLAG_INT(handle_fpe, 1, "If 1, try to intercept SIGFPE.")
 FUZZER_FLAG_INT(handle_int, 1, "If 1, try to intercept SIGINT.")

lib/fuzzer/FuzzerInternal.h

public:
   static void StaticAlarmCallback();
   static void StaticCrashSignalCallback();
   static void StaticExitCallback();
   static void StaticInterruptCallback();
   static void StaticFileSizeExceedCallback();
   static void StaticGracefulExitCallback();
 
   void ExecuteCallback(const uint8_t *Data, size_t Size);
-  void CheckForUnstableCounters(const uint8_t *Data, size_t Size);
+  size_t CheckForUnstableCounters(const uint8_t *Data, size_t Size);
   bool RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile = false,
               InputInfo *II = nullptr, bool *FoundUniqFeatures = nullptr);
 
   // Merge Corpora[1:] into Corpora[0].
   void Merge(const Vector<std::string> &Corpora);
   void CrashResistantMerge(const Vector<std::string> &Args,
                            const Vector<std::string> &Corpora,
                            const char *CoverageSummaryInputPathOrNull,

lib/fuzzer/FuzzerLoop.cpp

void Fuzzer::PrintPulseAndReportSlowInput(const uint8_t *Data, size_t Size) {
   if (TimeOfUnit > TimeOfLongestUnitInSeconds * 1.1 &&
       TimeOfUnit >= Options.ReportSlowUnits) {
     TimeOfLongestUnitInSeconds = TimeOfUnit;
     Printf("Slowest unit: %zd s:\n", TimeOfLongestUnitInSeconds);
     WriteUnitToFileWithPrefix({Data, Data + Size}, "slow-unit-");
   }
 }
 
-void Fuzzer::CheckForUnstableCounters(const uint8_t *Data, size_t Size) {
+size_t Fuzzer::CheckForUnstableCounters(const uint8_t *Data, size_t Size) {
   auto CBSetupAndRun = [&]() {
     ScopedEnableMsanInterceptorChecks S;
     UnitStartTime = system_clock::now();
     TPC.ResetMaps();
     RunningUserCallback = true;
     CB(Data, Size);
     RunningUserCallback = false;
     UnitStopTime = system_clock::now();
   };
 
   // Copy original run counters into our unstable counters
   TPC.InitializeUnstableCounters();
 
   // First Rerun
   CBSetupAndRun();
+  size_t NumNewUnstableEdges =
       TPC.UpdateUnstableCounters(Options.HandleUnstable);
 
   // Second Rerun
   CBSetupAndRun();
-  TPC.UpdateUnstableCounters(Options.HandleUnstable);
+  NumNewUnstableEdges += TPC.UpdateUnstableCounters(Options.HandleUnstable);
 
   // Move minimum hit counts back to ModuleInline8bitCounters
-  if (Options.HandleUnstable == TracePC::MinUnstable ||
-      Options.HandleUnstable == TracePC::ZeroUnstable)
+  if (Options.HandleUnstable == UnstableMode::Min ||
+      Options.HandleUnstable == UnstableMode::Zero)
     TPC.ApplyUnstableCounters();
+
+  return NumNewUnstableEdges;
 }
 
 bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
                     InputInfo *II, bool *FoundUniqFeatures) {
   if (!Size)
     return false;
 
   ExecuteCallback(Data, Size);
 
   UniqFeatureSetTmp.clear();
   size_t FoundUniqFeaturesOfII = 0;
   size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
   bool NewFeaturesUnstable = false;
+  size_t NumNewUnstableEdges = 0;
 
-  if (Options.HandleUnstable || Options.PrintUnstableStats) {
+  if ((int)Options.HandleUnstable || Options.PrintUnstableStats) {
     TPC.CollectFeatures([&](size_t Feature) {
       if (Corpus.IsFeatureNew(Feature, Size, Options.Shrink))
         NewFeaturesUnstable = true;
     });
     if (NewFeaturesUnstable)
-      CheckForUnstableCounters(Data, Size);
+      NumNewUnstableEdges = CheckForUnstableCounters(Data, Size);
   }
 
   TPC.CollectFeatures([&](size_t Feature) {
     if (Corpus.AddFeature(Feature, Size, Options.Shrink))
       UniqFeatureSetTmp.push_back(Feature);
     if (Options.ReduceInputs && II)
       if (std::binary_search(II->UniqFeatureSet.begin(),
                              II->UniqFeatureSet.end(), Feature))
         FoundUniqFeaturesOfII++;
   });
 
   if (FoundUniqFeatures)
     *FoundUniqFeatures = FoundUniqFeaturesOfII;
   PrintPulseAndReportSlowInput(Data, Size);
   size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;
 
+  if (Options.HandleUnstable == UnstableMode::Poison) {
+    assert(NumNewFeatures >= NumNewUnstableEdges);
+    NumNewFeatures -= NumNewUnstableEdges;
+  }
+
   if (NumNewFeatures) {
     TPC.UpdateObservedPCs();
     Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures, MayDeleteFile,
                        TPC.ObservedFocusFunction(), UniqFeatureSetTmp, DFT, II);
     return true;
   }
   if (II && FoundUniqFeaturesOfII &&
       II->DataFlowTraceForFocusFunction.empty() &&

lib/fuzzer/FuzzerOptions.h

 
 #ifndef LLVM_FUZZER_OPTIONS_H
 #define LLVM_FUZZER_OPTIONS_H
 
 #include "FuzzerDefs.h"
 
 namespace fuzzer {
 
+enum class UnstableMode {
+  Start = 0,
+  Min = 1,
+  Zero = 2,
+  Poison = 3,
+  End = 4,
+};
+
 struct FuzzingOptions {
   int Verbosity = 1;
   size_t MaxLen = 0;
   size_t LenControl = 1000;
   int UnitTimeoutSec = 300;
   int TimeoutExitCode = 77;
   int ErrorExitCode = 77;
   int MaxTotalTimeSec = 0;
struct FuzzingOptions {
   bool PrintNEW = true; // Print a status line when new units are found;
   bool PrintNewCovPcs = false;
   int PrintNewCovFuncs = 0;
   bool PrintFinalStats = false;
   bool PrintMutationStats = false;
   bool PrintCorpusStats = false;
   bool PrintCoverage = false;
   bool PrintUnstableStats = false;
-  int HandleUnstable = 0;
+  UnstableMode HandleUnstable = UnstableMode::Start;
   bool DumpCoverage = false;
   bool DetectLeaks = true;
   int PurgeAllocatorIntervalSec = 1;
   int  TraceMalloc = 0;
   bool HandleAbrt = false;
   bool HandleBus = false;
   bool HandleFpe = false;
   bool HandleIll = false;

lib/fuzzer/FuzzerTracePC.h

 //===- FuzzerTracePC.h - Internal header for the Fuzzer ---------*- C++ -* ===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 // fuzzer::TracePC
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_FUZZER_TRACE_PC
 #define LLVM_FUZZER_TRACE_PC
 
 #include "FuzzerDefs.h"
 #include "FuzzerDictionary.h"
+#include "FuzzerOptions.h"
 #include "FuzzerValueBitMap.h"
 
 #include <set>
 #include <unordered_map>
 
 namespace fuzzer {
 
 // TableOfRecentCompares (TORC) remembers the most recently performed
struct MemMemTable {
   }
 };
 
 class TracePC {
  public:
   static const size_t kNumPCs = 1 << 21;
   // How many bits of PC are used from __sanitizer_cov_trace_pc.
   static const size_t kTracePcBits = 18;
 
-  enum HandleUnstableOptions {
-    MinUnstable = 1,
-    ZeroUnstable = 2,
-  };
-
   void HandleInit(uint32_t *Start, uint32_t *Stop);
   void HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop);
   void HandlePCsInit(const uintptr_t *Start, const uintptr_t *Stop);
   void HandleCallerCallee(uintptr_t Caller, uintptr_t Callee);
   template <class T> void HandleCmp(uintptr_t PC, T Arg1, T Arg2);
   size_t GetTotalPCCoverage();
   void SetUseCounters(bool UC) { UseCounters = UC; }
   void SetUseValueProfileMask(uint32_t VPMask) { UseValueProfileMask = VPMask; }
   void SetPrintNewPCs(bool P) { DoPrintNewPCs = P; }
void ForEachObservedPC(CallBack CB) {
     for (auto PC : ObservedPCs)
       CB(PC);
   }
 
   void SetFocusFunction(const std::string &FuncName);
   bool ObservedFocusFunction();
 
   void InitializeUnstableCounters();
-  void UpdateUnstableCounters(int UnstableMode);
+  size_t UpdateUnstableCounters(UnstableMode Mode);
   void ApplyUnstableCounters();
 
 private:
   struct UnstableEdge {
     uint8_t Counter;
     bool IsUnstable;
   };
 

lib/fuzzer/FuzzerTracePC.cpp

 void TracePC::InitializeUnstableCounters() {
   IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
     UnstableCounters[UnstableIdx].Counter = ModuleCounters[i].Start[j];
   });
 }
 
 // Compares the current counters with counters from previous runs
 // and records differences as unstable edges.
-void TracePC::UpdateUnstableCounters(int UnstableMode) {
+size_t TracePC::UpdateUnstableCounters(UnstableMode Mode) {
+  size_t NumNewUnstableEdges = 0;
   IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
-    if (ModuleCounters[i].Start[j] != UnstableCounters[UnstableIdx].Counter) {
-      UnstableCounters[UnstableIdx].IsUnstable = true;
-      if (UnstableMode == ZeroUnstable)
-        UnstableCounters[UnstableIdx].Counter = 0;
-      else if (UnstableMode == MinUnstable)
-        UnstableCounters[UnstableIdx].Counter = std::min(
-            ModuleCounters[i].Start[j], UnstableCounters[UnstableIdx].Counter);
-    }
+    if (ModuleCounters[i].Start[j] == UnstableCounters[UnstableIdx].Counter)
+      return;
+    if (!UnstableCounters[UnstableIdx].IsUnstable)
+      NumNewUnstableEdges++;
+    if (Mode == UnstableMode::Zero)
+    else if (Mode == UnstableMode::Min)
   });
+  return NumNewUnstableEdges;
 }
 
 // Moves the minimum hit counts to ModuleCounters.
 void TracePC::ApplyUnstableCounters() {
   IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
     ModuleCounters[i].Start[j] = UnstableCounters[UnstableIdx].Counter;
   });
 }

test/fuzzer/HandleUnstableTest.cpp

+#include <assert.h>
+#include <cstdint>
+#include <cstdio>
+#include <cstdlib>
+
+int x = 0;
+int c = 0;
+bool skip0 = false;
+bool skip1 = false;
+bool skip2 = false;
+
+__attribute__((noinline)) void det0() { x++; }
+__attribute__((noinline)) void det1() { x++; }
+__attribute__((noinline)) void det2() { x++; }
+
+__attribute__((noinline)) void ini0() { x++; }
+__attribute__((noinline)) void ini1() { x++; }
+__attribute__((noinline)) void ini2() { x++; }
+
+__attribute__((noinline)) void t0() { x++; }
+__attribute__((noinline)) void t1() { x++; }
+__attribute__((noinline)) void t2() { x++; }
+
+__attribute__((noinline)) void poison0() { x++; }
+__attribute__((noinline)) void poison1() { x++; }
+__attribute__((noinline)) void poison2() { x++; }
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  if (Size == 1 && Data[0] == 'A' && !skip0) {
+    skip0 = true;
+    ini0();
+  }
+  if (Size == 1 && Data[0] == 'B' && !skip1) {
+    skip1 = true;
+    ini1();
+  }
+  if (Size == 1 && Data[0] == 'C' && !skip2) {
+    skip2 = true;
+    ini2();
+  }
+
+  det0();
+  det1();
+  det2();
+
+  // c < 1000 on purpose so that when it enters the else condition, t0() gets
+  // collected since we detect new stable edge poison0().
+  if (c < 1000) {
+    switch (c % 3) {
+    case 0:
+      t0();
+      poison0();
+      break;
+    case 1:
+      t1();
+      poison1();
+      break;
+    case 2:
+      t2();
+      poison2();
+      break;
+    default:
+      assert(false);
+    }
+  } else {
+    poison0();
+    poison1();
+    poison2();
+  }
+  c++;
+
+  return 0;
+}

test/fuzzer/handle-unstable.test

 # Tests -handle_unstable
 UNSUPPORTED: aarch64
 
-RUN: %cpp_compiler %S/PrintUnstableStatsTest.cpp -o %t-HandleUnstableTest
+RUN: %cpp_compiler %S/HandleUnstableTest.cpp -o %t-HandleUnstableTest
 
 ; Normal
 RUN: %run %t-HandleUnstableTest -print_coverage=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=NORMAL
 NORMAL-DAG: det0()
 NORMAL-DAG: det1()
 NORMAL-DAG: det2()
-NORMAL-DAG: det3()
-NORMAL-DAG: det4()
 NORMAL-DAG: ini0()
 NORMAL-DAG: ini1()
 NORMAL-DAG: ini2()
 NORMAL-DAG: t0()
 NORMAL-DAG: t1()
 NORMAL-DAG: t2()
-NORMAL-DAG: t3()
-NORMAL-DAG: t4()
 
 ; MinUnstable
-RUN: %run %t-HandleUnstableTest -print_coverage=1 -handle_unstable=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=MIN
-MIN-NOT: ini0()
-MIN-NOT: ini1()
-MIN-NOT: ini2()
+run: %run %t-handleunstabletest -print_coverage=1 -handle_unstable=1 -runs=100000 2>&1 | filecheck %s --check-prefix=min
 MIN: det0()
 MIN: det1()
 MIN: det2()
-MIN: det3()
-MIN: det4()
+MIN: poison0()
+MIN: poison1()
+MIN: poison2()
+MIN-NOT: ini0()
+MIN-NOT: ini1()
+MIN-NOT: ini2()
+MIN-NOT: t0()
+MIN-NOT: t1()
+MIN-NOT: t2()
 
 ; ZeroUnstable
-RUN: %run %t-HandleUnstableTest -print_coverage=1 -handle_unstable=2 -runs=1 2>&1 | FileCheck %s --check-prefix=ZERO
-ZERO-NOT: ini0()
-ZERO-NOT: ini1()
-ZERO-NOT: ini2()
+run: %run %t-handleunstabletest -print_coverage=1 -handle_unstable=2 -runs=100000 2>&1 | filecheck %s --check-prefix=zero
 ZERO: det0()
 ZERO: det1()
 ZERO: det2()
-ZERO: det3()
-ZERO: det4()
+ZERO: poison0()
+ZERO: poison1()
+ZERO: poison2()
+ZERO-NOT: ini0()
+ZERO-NOT: ini1()
+ZERO-NOT: ini2()
+ZERO-NOT: t0()
+ZERO-NOT: t1()
+ZERO-NOT: t2()
+
+; PoisonUnstable
+RUN: %run %t-HandleUnstableTest -print_coverage=1 -handle_unstable=3 -runs=100000 2>&1 | FileCheck %s --check-prefix=POISON
+POISON: det0()
+POISON: det1()
+POISON: det2()
+; t0 is triggered because last iteration hits poison0() and it's next iterations always hit poison0() causing the input to collect t0() as well.
+POISON: t0()
+POISON: poison0()
+POISON: poison1()
+POISON: poison2()
+POISON-NOT: {{\b}}t1()
+POISON-NOT: {{\b}}t2()
+POISON-NOT: ini0()
+POISON-NOT: ini1()
+POISON-NOT: ini2()