[Xen-devel] [PATCH v4 12/12] fuzz/x86_emulate: Add an option to limit the number of instructions executed

[George Dunlap <george.dunlap@xxxxxxxxxx>]

AFL considers a testcase to be a useful addition not only if there are
tuples exercised by that testcase which were not exercised otherwise,
but also if the *number* of times an individual tuple is exercised
changes significantly; in particular, if the number of the highest
non-zero bit changes (i.e., if it is run 1, 2-3, 4-7, 8-15, &c).

One simple way to increase these stats it to execute the same (or
similar) instructions multiple times: If executing a given instruction
once hits a particular tuple 2 times, executing it twice will hit the
tuple 4 times, four times will hit the tuple 8 times, and so on.  All
of these will look different to AFL, and so it is likely that many of
the "unique test cases" will simply be the same instruction repeated
powers of 2 times until the tuple counts max out (at 128).

It is unlikely that executing a single instruction more than a handful
of times will generate any state we actually care about; but such long
testcases take exponentially longer to fuzz: the fuzzer spends more
time flipping bits looking for meaningful changes, and each execution
takes longer because it is doing more things.  So long paths which add
nothing to the actual code coverage but effectively "distract" the
fuzzer, making it less effective.

Experiments have shown that not allowing infinite number of
instruction retries for the old (non-compact) format does indeed speed
up and increase code coverage.  However, it has also shown that on the
new, more compact format, having no instruction limit causes the highest
throughput in code coverage.

So leave the option in, but have it default to 0 (no limit).

Signed-off-by: George Dunlap <george.dunlap@xxxxxxxxxx>
Acked-by: Jan Beulich <jbeulich@xxxxxxxx>
---
v3:
- Change opt_instruction_limit to unsigned, default to UINT_MAX
- Simplify limit checking (now that the actual variable itself will never be 0)
- Change counter to unsigned
- Update changelog to try to be a bit more clear


CC: Ian Jackson <ian.jackson@xxxxxxxxxx>
CC: Wei Liu <wei.liu2@xxxxxxxxxx>
CC: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
CC: Jan Beulich <jbeulich@xxxxxxxx>
---
 tools/fuzz/x86_instruction_emulator/afl-harness.c | 11 ++++++++++-
 tools/fuzz/x86_instruction_emulator/fuzz-emul.c   |  5 ++++-
 tools/fuzz/x86_instruction_emulator/fuzz-emul.h   |  1 +
 3 files changed, 15 insertions(+), 2 deletions(-)

diff --git a/tools/fuzz/x86_instruction_emulator/afl-harness.c 
b/tools/fuzz/x86_instruction_emulator/afl-harness.c
index 0489034642..375b3333ad 100644
--- a/tools/fuzz/x86_instruction_emulator/afl-harness.c
+++ b/tools/fuzz/x86_instruction_emulator/afl-harness.c
@@ -1,4 +1,5 @@
 #include <assert.h>
+#include <limits.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -24,11 +25,13 @@ int main(int argc, char **argv)
             OPT_MIN_SIZE,
             OPT_COMPACT,
             OPT_RERUN,
+            OPT_INSTRUCTION_LIMIT,
         };
         static const struct option lopts[] = {
             { "min-input-size", no_argument, NULL, OPT_MIN_SIZE },
             { "compact", required_argument, NULL, OPT_COMPACT },
             { "rerun", no_argument, NULL, OPT_RERUN },
+            { "instruction-limit", required_argument, NULL, 
OPT_INSTRUCTION_LIMIT },
             { 0, 0, 0, 0 }
         };
         int c = getopt_long_only(argc, argv, "", lopts, NULL);
@@ -51,8 +54,14 @@ int main(int argc, char **argv)
             opt_rerun = true;
             break;
 
+        case OPT_INSTRUCTION_LIMIT:
+            opt_instruction_limit = atoi(optarg);
+            if ( !opt_instruction_limit )
+                opt_instruction_limit = UINT_MAX;
+            break;
+
         case '?':
-            printf("Usage: %s [--compact=0|1] [--rerun] $FILE [$FILE...] | 
[--min-input-size]\n", argv[0]);
+            printf("Usage: %s [--compact=0|1] [--rerun] 
[--instruction-limit=N] $FILE [$FILE...] | [--min-input-size]\n", argv[0]);
             exit(-1);
             break;
 
diff --git a/tools/fuzz/x86_instruction_emulator/fuzz-emul.c 
b/tools/fuzz/x86_instruction_emulator/fuzz-emul.c
index 881c4d03c1..d2198e71c9 100644
--- a/tools/fuzz/x86_instruction_emulator/fuzz-emul.c
+++ b/tools/fuzz/x86_instruction_emulator/fuzz-emul.c
@@ -984,10 +984,13 @@ static void setup_fuzz_state(struct fuzz_state *state, 
const void *data_p, size_
     state->data_num = size;
 }
 
+unsigned int opt_instruction_limit = UINT_MAX;
+
 static int runtest(struct fuzz_state *state) {
     int rc;
 
     struct x86_emulate_ctxt *ctxt = &state->ctxt;
+    unsigned int icount = 0;
     
     state->ops = all_fuzzer_ops;
 
@@ -1011,7 +1014,7 @@ static int runtest(struct fuzz_state *state) {
 
         rc = x86_emulate(ctxt, &state->ops);
         printf("Emulation result: %d\n", rc);
-    } while ( rc == X86EMUL_OKAY );
+    } while ( rc == X86EMUL_OKAY && ++icount < opt_instruction_limit );
 
     save_fpu_state(state->fxsave);
     
diff --git a/tools/fuzz/x86_instruction_emulator/fuzz-emul.h 
b/tools/fuzz/x86_instruction_emulator/fuzz-emul.h
index 4863bf2166..746e1b542d 100644
--- a/tools/fuzz/x86_instruction_emulator/fuzz-emul.h
+++ b/tools/fuzz/x86_instruction_emulator/fuzz-emul.h
@@ -7,6 +7,7 @@ extern unsigned int fuzz_minimal_input_size(void);
 
 extern bool opt_compact;
 extern bool opt_rerun;
+extern unsigned int opt_instruction_limit;
 
 #define INPUT_SIZE  4096
 
-- 
2.14.2


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel