[libFuzzer] Handle unstable edges by disregarding unstable edges

[kevinwkt]

Summary

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

When an edge is shown as unstable, copy to UnstableCounters the value 0.
During ApplyUnstableCounters we copy back the value 0 to ModuleInline8bitCounters if the edge was unstable.

This way we would be ignoring completely features that were collected through non-determinism.
Unstable hits would be counted as if it never hit.

[kevinwkt]

Added tests.
Unstable should not have as features all unstable edges such as ini functions nor t functions.
In normal we only check for t function because regex catches det as t functions because of the "t()" in "de-t()".

[Dor1s]

I'm not sure I fully understand that approach. We put 0 into the counters for edges we think are unstable. That's fair, but every time we generate a new input that triggers such edge, we would re-run it twice just to learn again that it was unstable. Why not put something like 0xff to mark it like a covered edge, so that we would ignore any new testcases covering that?

Another concern I have is the following. Let's say we have a testcase that covers edge X in a deterministic way, we save it. Later on, we find another testcases that covers that edge, but demonstrates instability, so we mark the edge as unstable. That sort of thing may happen again and again, an edge might seem to be stable or unstable with different testcases, And we still be blowing the corpus.

What do I misunderstand?

test/fuzzer/handle_unstable_zerounstable.test

10 ↗

(On Diff #156854)

Is there anything stable we can check for? If there isn't, I think it would make sense to introduce some deterministic function.

[kevinwkt]

In D49684#1172349, @Dor1s wrote:

I'm not sure I fully understand that approach. We put 0 into the counters for edges we think are unstable. That's fair, but every time we generate a new input that triggers such edge, we would re-run it twice just to learn again that it was unstable. Why not put something like 0xff to mark it like a covered edge, so that we would ignore any new testcases covering that?

Another concern I have is the following. Let's say we have a testcase that covers edge X in a deterministic way, we save it. Later on, we find another testcases that covers that edge, but demonstrates instability, so we mark the edge as unstable. That sort of thing may happen again and again, an edge might seem to be stable or unstable with different testcases, And we still be blowing the corpus.

What do I misunderstand?

So the reason I think putting it as an uncovered edge is a better solution is that, in the future, if we get an input that hits the the previously unstable edges deterministically, we want to award the deterministically reached input for finding the "new" edge. It may be slower as you commented, but I think that it makes more sense. If we mark those undeterministically reached edges as covered edge, inputs that reach it deterministically in the future (which I believe are the truly interesting inputs) will not be added to corpus.

[kevinwkt]

ptal

Added deterministic checks for tests.

[Dor1s]

In D49684#1172403, @kevinwkt wrote:

In D49684#1172349, @Dor1s wrote:

I'm not sure I fully understand that approach. We put 0 into the counters for edges we think are unstable. That's fair, but every time we generate a new input that triggers such edge, we would re-run it twice just to learn again that it was unstable. Why not put something like 0xff to mark it like a covered edge, so that we would ignore any new testcases covering that?

Another concern I have is the following. Let's say we have a testcase that covers edge X in a deterministic way, we save it. Later on, we find another testcases that covers that edge, but demonstrates instability, so we mark the edge as unstable. That sort of thing may happen again and again, an edge might seem to be stable or unstable with different testcases, And we still be blowing the corpus.

What do I misunderstand?

So the reason I think putting it as an uncovered edge is a better solution is that, in the future, if we get an input that hits the the previously unstable edges deterministically, we want to award the deterministically reached input for finding the "new" edge. It may be slower as you commented, but I think that it makes more sense. If we mark those undeterministically reached edges as covered edge, inputs that reach it deterministically in the future (which I believe are the truly interesting inputs) will not be added to corpus.

Thanks for the clarification, I see. So, this approach is a less aggressive compared to https://reviews.llvm.org/D49578

Left two more minor comments. Looks good otherwise.

lib/fuzzer/FuzzerTracePC.cpp

90

nit: if -> else if

test/fuzzer/handle_unstable_zerounstable.test

12 ↗

(On Diff #156877)

Any reason not to check for those in` NORMAL` run as well?

[Dor1s]

Feel free to ask Matt / Kostya to review this once my comments are addressed.

[kevinwkt]

PTAL
Fixed if to else if.

Added det() checks to Normal Runs.

[metzman]

LGTM

[morehouse]

lib/fuzzer/FuzzerTracePC.cpp

93

We can simplify this to

else if (UnstableMode == MinUnstable)
  UnstableCounters[UnstableIdx].Counter = std::min(...)

test/fuzzer/handle_unstable_zerounstable.test

10 ↗

(On Diff #156898)

Is there some probability that these functions are marked stable? For example, could all 3 runs hit t0?

30 ↗

(On Diff #156898)

I think there's some redundancy here. Let's combine this file with handle_unstable_minunstable.test to a single handle-unstable.test.

[kevinwkt]

ptal
Removed Non-deterministic tests and changed UpdateCounters to use std::min

[kevinwkt]

test/fuzzer/handle_unstable_zerounstable.test

10 ↗

(On Diff #156898)

Yes, I will only include the ini functions now so that the test is deterministic.

[morehouse]

lib/fuzzer/FuzzerTracePC.cpp

93

Can save 1 line by removing braces from this else if.

[metzman]

lib/fuzzer/FuzzerTracePC.cpp

93

I generally ask for this because I think multiline if/else bodies that don't have brackets are scary.
Do you still think this change should be made?

If not, then Kevin can you put the ifbody in brackets for consistency.

[morehouse]

lib/fuzzer/FuzzerTracePC.cpp

93

I think it's a small detail and don't feel too strongly either way.

On one hand, compact and simple code is easier to read and maintain. On the other hand, a lazy programmer could add another line to the if and introduce a bug.

There is code in libFuzzer with both conventions.

[morehouse]

lib/fuzzer/FuzzerTracePC.cpp

93

I think @kcc would generally prefer the simpler and more compact version, but we're splitting hairs here.

[kevinwkt]

PTAL
Got rid of the extra brackets to make it more compact.

[Dor1s]

Rebase and getting ready to commit.

[thopre]

Hi Kyungtak,

The test added in this commit appears to be failing for aarch64 since
it was introduced:

http://lab.llvm.org:8011/builders/clang-cmake-aarch64-full/builds/5515
is failing and covers the range which added this test
http://lab.llvm.org:8011/waterfall?show=clang-cmake-aarch64-full shows
that the test has been failing since that build onwards

Best regards,

Thomas

[kevinwkt]

@Dor1s @thopre

This update should fix both tests and should work now.

lib/fuzzer/FuzzerDriver.cpp

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)
+  if (Flags.handle_unstable == TracePC::MinUnstable ||
+      Flags.handle_unstable == TracePC::ZeroUnstable)
     Options.HandleUnstable = 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;

lib/fuzzer/FuzzerFlags.def

FUZZER_FLAG_INT(print_coverage, 0, "If 1, print coverage information as text"
                                    " at exit.")
 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.")
+                   " to determine whether an input is interesting."
+                   " If 2, we disregard edges that are found unstable for"
+                   " feature collection.")
 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/FuzzerLoop.cpp

void Fuzzer::CheckForUnstableCounters(const uint8_t *Data, size_t Size) {
   CBSetupAndRun();
   TPC.UpdateUnstableCounters(Options.HandleUnstable);
 
   // Second Rerun
   CBSetupAndRun();
   TPC.UpdateUnstableCounters(Options.HandleUnstable);
 
   // Move minimum hit counts back to ModuleInline8bitCounters
-  if (Options.HandleUnstable)
+  if (Options.HandleUnstable == TracePC::MinUnstable ||
+      Options.HandleUnstable == TracePC::ZeroUnstable)
     TPC.ApplyUnstableCounters();
 }
 
 bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
                     InputInfo *II, bool *FoundUniqFeatures) {
   if (!Size)
     return false;
 

lib/fuzzer/FuzzerTracePC.h

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

lib/fuzzer/FuzzerTracePC.cpp

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) {
   IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
-    if (ModuleCounters[i].Start[j] != UnstableCounters[UnstableIdx].Counter)
+    if (ModuleCounters[i].Start[j] != UnstableCounters[UnstableIdx].Counter) {
       UnstableCounters[UnstableIdx].IsUnstable = true;
-    if (UnstableMode &&
-        ModuleCounters[i].Start[j] < UnstableCounters[UnstableIdx].Counter)
-      UnstableCounters[UnstableIdx].Counter = ModuleCounters[i].Start[j];
+      if (UnstableMode == ZeroUnstable)
+        UnstableCounters[UnstableIdx].Counter = 0;
+      else if (UnstableMode == MinUnstable)
+        UnstableCounters[UnstableIdx].Counter = std::min(
+            ModuleCounters[i].Start[j], UnstableCounters[UnstableIdx].Counter);
+    }
   });
 }
 
 // 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/handle-unstable.test

+RUN: %cpp_compiler %S/PrintUnstableStatsTest.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: det0()
+MIN: det1()
+MIN: det2()
+MIN: det3()
+MIN: det4()
+
+; 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()
+ZERO: det0()
+ZERO: det1()
+ZERO: det2()
+ZERO: det3()
+ZERO: det4()

test/fuzzer/handle_unstable_minunstable.test

-RUN: %cpp_compiler %S/PrintUnstableStatsTest.cpp -o %t-HandleUnstableMinUnstableTest
-RUN: %run %t-HandleUnstableMinUnstableTest -print_coverage=1 -handle_unstable=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=UNSTABLE
-UNSTABLE-NOT: ini0()
-UNSTABLE-NOT: ini1()
-UNSTABLE-NOT: ini2()
-
-RUN: %run %t-HandleUnstableMinUnstableTest -print_coverage=1 -runs=100000 2>&1 | FileCheck %s --check-prefix=NORMAL
-NORMAL-DAG: ini0()
-NORMAL-DAG: ini1()
-NORMAL-DAG: ini2()
-
-