[libFuzzer] Fix DataFlow.cpp logic when tracing long inputs.

[Dor1s]

Summary

1. Do not create DFSan labels for the bytes which we do not trace. This is where we run out of labels at the first place.
2. When dumping the traces on the disk, make sure to offset the label identifiers by the number of the first byte in the trace range.
3. For the last label, make sure to write it at the last position of the trace bit string, as that label represents the input size, not any particular byte.

Also fixed the bug with division in python which I've introduced when migrated the scripts to Python3 (// is required for integral division).

Otherwise, the scripts are wasting too much time unsuccessfully trying to
collect and process traces from the long inputs. For more context, see
https://github.com/google/oss-fuzz/issues/1632#issuecomment-481761789

[Dor1s]

Update the test to reflect the change and make sure it passes.

[kcc]

I don't think this is right. This subprocess is *expected* to fail with exactly this message when we run out of labels,
and then we handle the input as two subsets, and so on.
But this error must not happen if the range is >= 2 (two labels should not cause this error), so the process converges.
We can not predict when we run out of labels -- for some 8k inputs it will work from the first attempt,
for some much smaller inputs it will require several bisections.

I would simply limit the size of the inputs used in DFT-based fuzzing to something like 8K for now, and see how it works.

[Dor1s]

Hey @kcc, I've figured out what's the problem here. Will update the description and the CL shortly.

[Dor1s]

This patch fixes the issue with the long inputs by not creating DFSan labels
for the bytes which we do not trace, and by offseting the resulting labels to
make the dumps easily mergeable.

[Dor1s]

Please see this draft proposal / explanation for the issue. The bisection in python is fine! :)

[Dor1s]

Btw, I did some testing locally, with a 5 bytes input. I was tracing it 3 times:

• full
• 0 3 bytes
• 3 5 bytes

see the traces below:

root@7fc00dc69f76:/out# cat full start end
F1 111111
F4 111111
F7 111111
F11 111111
F12 100001

F1 111001
F4 111001
F7 111001
F11 111001
F12 100001

F1 000111
F4 000111
F7 000111
F11 000111
F12 000001

root@7fc00dc69f76:/out# cat full3 start3 end3
F1 111111
F4 111111
F7 111111
F11 111111
F12 100001

F1 111001
F4 111001
F7 111001
F11 111001
F12 100001

F1 000111
F4 000111
F7 000111
F11 000111
F12 000001

If we merge start and end, we get full -- these three are obtained using the current implementation. After applying this CL, the same works for merging start3 and end3 resulting in full3 which is equal to full, i.e. I believe that nothing's broken.

[kcc]

Code LGTM, but please also add a test that would fail with current code and pass with your change.
Either extend test/fuzzer/dataflow.test or add another one nearby.

[Dor1s]

Add the test, remove debug logging, fix python3 division.

[Dor1s]

fix a typo

[kcc]

LGTM++

compiler-rt/trunk/lib/fuzzer/dataflow/DataFlow.cpp

 #include <sanitizer/dfsan_interface.h>
 
 extern "C" {
 extern int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size);
 __attribute__((weak)) extern int LLVMFuzzerInitialize(int *argc, char ***argv);
 } // extern "C"
 
 static size_t InputLen;
+static size_t InputLabelBeg;
+static size_t InputLabelEnd;
+static size_t InputSizeLabel;
 static size_t NumFuncs;
 static const uintptr_t *FuncsBeg;
 static __thread size_t CurrentFunc;
 static dfsan_label *FuncLabels;  // Array of NumFuncs elements.
 static char *PrintableStringForLabel;  // InputLen + 2 bytes.
 static bool LabelSeen[1 << 8 * sizeof(dfsan_label)];
 
 // Prints all instrumented functions.

 }
 
 extern "C"
 void SetBytesForLabel(dfsan_label L, char *Bytes) {
   if (LabelSeen[L])
     return;
   LabelSeen[L] = true;
   assert(L);
-  if (L <= InputLen + 1) {
-    Bytes[L - 1] = '1';
+  if (L < InputSizeLabel) {
+    Bytes[L + InputLabelBeg - 1] = '1';
+  } else if (L == InputSizeLabel) {
+    Bytes[InputLen] = '1';
   } else {
     auto *DLI = dfsan_get_label_info(L);
     SetBytesForLabel(DLI->l1, Bytes);
     SetBytesForLabel(DLI->l2, Bytes);
   }
 }
 
 static char *GetPrintableStringForLabel(dfsan_label L) {

 }
 
 int main(int argc, char **argv) {
   if (LLVMFuzzerInitialize)
     LLVMFuzzerInitialize(&argc, &argv);
   if (argc == 1)
     return PrintFunctions();
   assert(argc == 4 || argc == 5);
-  size_t Beg = atoi(argv[1]);
-  size_t End = atoi(argv[2]);
-  assert(Beg < End);
+  InputLabelBeg = atoi(argv[1]);
+  InputLabelEnd = atoi(argv[2]);
+  assert(InputLabelBeg < InputLabelEnd);
 
   const char *Input = argv[3];
   fprintf(stderr, "INFO: reading '%s'\n", Input);
   FILE *In = fopen(Input, "r");
   assert(In);
   fseek(In, 0, SEEK_END);
   InputLen = ftell(In);
   fseek(In, 0, SEEK_SET);
   unsigned char *Buf = (unsigned char*)malloc(InputLen);
   size_t NumBytesRead = fread(Buf, 1, InputLen, In);
   assert(NumBytesRead == InputLen);
   PrintableStringForLabel = (char*)malloc(InputLen + 2);
   fclose(In);
 
   fprintf(stderr, "INFO: running '%s'\n", Input);
   for (size_t I = 1; I <= InputLen; I++) {
-    dfsan_label L = dfsan_create_label("", nullptr);
-    assert(L == I);
     size_t Idx = I - 1;
-    if (Idx >= Beg && Idx < End)
+    if (Idx >= InputLabelBeg && Idx < InputLabelEnd) {
+      dfsan_label L = dfsan_create_label("", nullptr);
+      assert(L == I - InputLabelBeg);
       dfsan_set_label(L, Buf + Idx, 1);
     }
+  }
   dfsan_label SizeL = dfsan_create_label("", nullptr);
-  assert(SizeL == InputLen + 1);
+  InputSizeLabel = SizeL;
+  assert(InputSizeLabel == InputLabelEnd - InputLabelBeg + 1);
   dfsan_set_label(SizeL, &InputLen, sizeof(InputLen));
 
   LLVMFuzzerTestOneInput(Buf, InputLen);
   free(Buf);
 
   bool OutIsStdout = argc == 4;
   fprintf(stderr, "INFO: writing dataflow to %s\n",
           OutIsStdout ? "<stdout>" : argv[4]);

compiler-rt/trunk/lib/fuzzer/scripts/collect_data_flow.py

def main(argv):
   print("tmpdir: ", tmpdir)
   outputs = []
   while len(q):
     r = q.pop()
     print("******* Trying:  ", r)
     tmpfile = os.path.join(tmpdir, str(r[0]) + "-" + str(r[1]))
     ret = subprocess.call([exe, str(r[0]), str(r[1]), inp, tmpfile])
     if ret and r[1] - r[0] >= 2:
-      q.append([r[0], (r[1] + r[0]) / 2])
-      q.append([(r[1] + r[0]) / 2, r[1]])
+      q.append([r[0], (r[1] + r[0]) // 2])
+      q.append([(r[1] + r[0]) // 2, r[1]])
     else:
       outputs.append(tmpfile)
       print("******* Success: ", r)
   f = sys.stdout
   if len(argv) >= 4:
     f = open(argv[3], "w")
   merge = os.path.join(os.path.dirname(argv[0]), "merge_data_flow.py")
   subprocess.call([merge] + outputs, stdout=f)
 
 if __name__ == '__main__':
   main(sys.argv)

compiler-rt/trunk/test/fuzzer/dataflow.test

 RUN: rm -rf %t/OUT
 RUN: %libfuzzer_src/scripts/collect_data_flow.py %t-ThreeFunctionsTestDF %t/IN %t/OUT
 RUN: %t-ThreeFunctionsTest -data_flow_trace=%t/OUT -runs=0 -focus_function=Func2 2>&1 | FileCheck %s --check-prefix=USE_DATA_FLOW_TRACE
 USE_DATA_FLOW_TRACE: INFO: Focus function is set to 'Func2'
 USE_DATA_FLOW_TRACE: INFO: DataFlowTrace: reading from {{.*}}/OUT
 USE_DATA_FLOW_TRACE-DAG: a8eefe2fd5d6b32028f355fafa3e739a6bf5edc => |000001|
 USE_DATA_FLOW_TRACE-DGA: d28cb407e8e1a702c72d25473f0553d3ec172262 => |0000011|
 USE_DATA_FLOW_TRACE: INFO: DataFlowTrace: 6 trace files, 3 functions, 2 traces with focus function
+
+# Test that we can run collect_data_flow on a long input (>2**16 bytes)
+RUN: rm -rf %t/OUT
+RUN: printf "%0.sA" {1..150001} > %t/IN/very_long_input
+RUN: %libfuzzer_src/scripts/collect_data_flow.py %t-ThreeFunctionsTestDF %t/IN/very_long_input %t/OUT | FileCheck %s --check-prefix=COLLECT_TRACE_FOR_LONG_INPUT
+RUN: rm %t/IN/very_long_input
+COLLECT_TRACE_FOR_LONG_INPUT: ******* Trying:{{[ ]+}}[0, 150001]
+COLLECT_TRACE_FOR_LONG_INPUT: ******* Trying:{{[ ]+}}[75000, 150001]
+COLLECT_TRACE_FOR_LONG_INPUT: ******* Trying:{{[ ]+}}[112500, 150001]
+COLLECT_TRACE_FOR_LONG_INPUT: ******* Success:{{[ ]+}}[{{[0123456789]+}}, 150001]
+COLLECT_TRACE_FOR_LONG_INPUT: ******* Success:{{[ ]+}}[0, {{[0123456789]+}}]