[Zucchini] imposed_ensemble_matcher Fuzzer

Adds a fuzzer for the ImposedEnsembleMatcher. This achieves between
5000 and 10000 exec/s. At 10000 runs this covers 96% of the
imposed_ensemble_matcher and 50% of the io_utils (another file lacking
coverage). Uncovered lines in io_utils are attributed to debug tools.
The missing lines in imposed_ensemble_matcher are error cases which
haven't been hit yet. The seed uses duplicated back to back copies of
old.ztf and new.ztf.

Bug: 835341
Change-Id: I742ca6f4c409c9a9ec4a335da2b50fd8d4d6ed6f
Reviewed-on: https://chromium-review.googlesource.com/1117572
Commit-Queue: Calder Kitagawa <ckitagawa@chromium.org>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/master@{#572201}
NOKEYCHECK=True
GitOrigin-RevId: f7b526674131a74a43ba13394f1c4819cac9c2d2

7 files changed, 299 insertions, 7 deletions

diff --git a/fuzzers/BUILD.gn b/fuzzers/BUILD.gn
index 51680c3..10a8bba 100644
--- a/fuzzers/BUILD.gn
+++ b/fuzzers/BUILD.gn
@@ -123,7 +123,14 @@ if (current_toolchain == host_toolchain && !is_win) {
     ]
   }
 
+  # For Gen fuzzers seeds can be created from this directory with:
+  # python create_seed_file_pair.py <protoc> <old file> <new file> <out file>
+  #   [--imposed=<imposed>]
+
   # Raw Gen Fuzzer:
+  # <old file>: testdata/old.ztf
+  # <new file>: testdata/new.ztf
+  # <out file>: testdata/raw_or_ztf_gen_fuzzer/seed.asciipb
   fuzzer_test("zucchini_raw_gen_fuzzer") {
     sources = [
       "raw_gen_fuzzer.cc",
@@ -138,6 +145,9 @@ if (current_toolchain == host_toolchain && !is_win) {
   }
 
   # ZTF Gen Fuzzer:
+  # <old file>: testdata/old.ztf
+  # <new file>: testdata/new.ztf
+  # <out file>: testdata/raw_or_ztf_gen_fuzzer/seed.asciipb
   fuzzer_test("zucchini_ztf_gen_fuzzer") {
     sources = [
       "ztf_gen_fuzzer.cc",
@@ -150,4 +160,23 @@ if (current_toolchain == host_toolchain && !is_win) {
     ]
     seed_corpus = "testdata/raw_or_ztf_gen_fuzzer"
   }
+
+  # Imposed Ensemble Match Fuzzer:
+  # <old file>: testdata/old_imposed_archive.txt
+  # <new file>: testdata/new_imposed_archive.txt
+  # <out file>: testdata/imposed_ensemble_matcher_fuzzer/seed.asciipb
+  # <imposed>: 17+420=388+347,452+420=27+347
+  # This is a mapping of regions old_offset+old_size=new_offset+new_size,...
+  fuzzer_test("zucchini_imposed_ensemble_matcher_fuzzer") {
+    sources = [
+      "imposed_ensemble_matcher_fuzzer.cc",
+    ]
+    deps = [
+      ":zucchini_file_pair_proto",
+      "//base",
+      "//components/zucchini:zucchini_lib",
+      "//third_party/libprotobuf-mutator",
+    ]
+    seed_corpus = "testdata/imposed_ensemble_matcher_fuzzer"
+  }
 }
diff --git a/fuzzers/create_seed_file_pair.py b/fuzzers/create_seed_file_pair.py
index a44db7b..4394801 100755
--- a/fuzzers/create_seed_file_pair.py
+++ b/fuzzers/create_seed_file_pair.py
@@ -21,7 +21,6 @@ import sys
 
 ABS_PATH = os.path.abspath(os.path.join(os.path.dirname(__file__)))
 PROTO_DEFINITION_FILE = 'file_pair.proto'
-OUTPUT_FORMAT = b'old_file: "{}"\nnew_or_patch_file: "{}"'
 
 def parse_args():
   """Parse commandline args."""
@@ -30,7 +29,11 @@ def parse_args():
   parser.add_argument('old_file', help='Old file to generate/apply patch.')
   parser.add_argument('new_or_patch_file',
                       help='New file to generate or patch to apply.')
-  parser.add_argument('output_file', help='File to write binary protobuf to.')
+  parser.add_argument('output_file',
+                      help='File to write binary protobuf to.')
+  parser.add_argument('--imposed_matches',
+                      help='Equivalence matches to impose when generating '
+                      'the patch.')
   return parser.parse_args()
 
 
@@ -45,9 +48,13 @@ def read_to_proto_escaped_string(filename):
 def main():
   args = parse_args()
   # Create an ASCII string representing a protobuf.
-  content = OUTPUT_FORMAT.format(read_to_proto_escaped_string(args.old_file),
-                                 read_to_proto_escaped_string(
-                                     args.new_or_patch_file))
+  content = [b'old_file: "{}"'.format(read_to_proto_escaped_string(
+                                      args.old_file)),
+             b'new_or_patch_file: "{}"'.format(read_to_proto_escaped_string(
+                                               args.new_or_patch_file))]
+
+  if args.imposed_matches:
+    content.append('imposed_matches: "{}"'.format(args.imposed_matches))
 
   # Encode the ASCII protobuf as a binary protobuf.
   ps = subprocess.Popen([args.protoc_path, '--proto_path=%s' % ABS_PATH,
@@ -57,7 +64,7 @@ def main():
                         stdout=subprocess.PIPE)
   # Write the string to the subprocess. Single line IO is fine as protoc returns
   # a string.
-  output = ps.communicate(input=content)
+  output = ps.communicate(input=b'\n'.join(content))
   ps.wait()
   if ps.returncode:
     logging.error('Binary protobuf encoding failed.')
diff --git a/fuzzers/file_pair.proto b/fuzzers/file_pair.proto
index 2216381..7fdc908 100644
--- a/fuzzers/file_pair.proto
+++ b/fuzzers/file_pair.proto
@@ -6,10 +6,16 @@ syntax = "proto2";
 
 package zucchini.fuzzers;
 
-// NEXT_TAG = 3
+// NEXT_TAG = 4
 message FilePair {
   // File to generate patch from or apply patch to.
   required bytes old_file = 1;
   // New file to generate patch or the patch to apply.
   required bytes new_or_patch_file = 2;
+  // Imposed matches to apply to the equivalence matches.
+  // Should be of the format:
+  //   "#+#=#+#,#+#=#+#,..." (e.g., "1+2=3+4", "1+2=3+4,5+6=7+8"),
+  // where "#+#=#+#" encodes a match as 4 unsigned integers:
+  //   [offset in "old", size in "old", offset in "new", size in "new"].
+  optional string imposed_matches = 3;
 }
diff --git a/fuzzers/imposed_ensemble_matcher_fuzzer.cc b/fuzzers/imposed_ensemble_matcher_fuzzer.cc
new file mode 100644
index 0000000..5c129a3
--- /dev/null
+++ b/fuzzers/imposed_ensemble_matcher_fuzzer.cc
@@ -0,0 +1,72 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <stdint.h>
+
+#include <iostream>
+#include <memory>
+
+#include "base/environment.h"
+#include "base/logging.h"
+#include "components/zucchini/buffer_sink.h"
+#include "components/zucchini/buffer_view.h"
+#include "components/zucchini/fuzzers/file_pair.pb.h"
+#include "components/zucchini/patch_writer.h"
+#include "components/zucchini/zucchini.h"
+#include "testing/libfuzzer/proto/lpm_interface.h"
+
+namespace {
+
+constexpr size_t kMinImageSize = 16;
+constexpr size_t kMaxImageSize = 1024;
+
+}  // namespace
+
+struct Environment {
+  Environment() {
+    logging::SetMinLogLevel(logging::LOG_FATAL);  // Disable console spamming.
+  }
+};
+
+DEFINE_BINARY_PROTO_FUZZER(const zucchini::fuzzers::FilePair& file_pair) {
+  static Environment env;
+  // Dump code for debugging.
+  if (base::Environment::Create()->HasVar("LPM_DUMP_NATIVE_INPUT")) {
+    std::cout << "Imposed Matches: " << file_pair.imposed_matches() << std::endl
+              << "Old File: " << file_pair.old_file() << std::endl
+              << "New File: " << file_pair.new_or_patch_file() << std::endl;
+  }
+
+  // Prepare data.
+  zucchini::ConstBufferView old_image(
+      reinterpret_cast<const uint8_t*>(file_pair.old_file().data()),
+      file_pair.old_file().size());
+  zucchini::ConstBufferView new_image(
+      reinterpret_cast<const uint8_t*>(file_pair.new_or_patch_file().data()),
+      file_pair.new_or_patch_file().size());
+
+  // Restrict image sizes to speed up fuzzing.
+  if (old_image.size() < kMinImageSize || old_image.size() > kMaxImageSize ||
+      new_image.size() < kMinImageSize || new_image.size() > kMaxImageSize) {
+    return;
+  }
+
+  // Generate a patch writer.
+  zucchini::EnsemblePatchWriter patch_writer(old_image, new_image);
+
+  // Fuzz Target.
+  zucchini::GenerateBufferImposed(old_image, new_image,
+                                  file_pair.imposed_matches(), &patch_writer);
+
+  // Check that the patch size is sane. Crash the fuzzer if this isn't the case,
+  // as it is a failure in Zucchini's patch performance that is worth
+  // investigating.
+  size_t patch_size = patch_writer.SerializedSize();
+  CHECK_LE(patch_size, kMaxImageSize * 2);
+
+  // Write to buffer to avoid IO.
+  std::unique_ptr<uint8_t[]> patch_data(new uint8_t[patch_size]);
+  zucchini::BufferSink patch(patch_data.get(), patch_size);
+  patch_writer.SerializeInto(patch);
+}
diff --git a/fuzzers/testdata/imposed_ensemble_matcher_fuzzer/seed.asciipb b/fuzzers/testdata/imposed_ensemble_matcher_fuzzer/seed.asciipb
new file mode 100644
index 0000000..abbadd2
--- /dev/null
+++ b/fuzzers/testdata/imposed_ensemble_matcher_fuzzer/seed.asciipb
@@ -0,0 +1,90 @@
+
+ˆABCDEFGHIJKLMNOP
+ZTxt
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+BLOCK1
+Lorem Ipsum, Ipsum Lorem, Alpha Beta Gamma <1,1>
+{3,4} [4,5] (90,08)
+(1,4)
+[+001, +001]
+References {-004,-003}, <001,001>, [98,78]
+(+01,+00)
+AAAAAAAAA
+
+BLOCK2
+{06,01} Another block. Lorem Ipsum, Ipsum, Ipsum
+<><><><><>{}{}{}{}[][][]()()()()
+[4,1]
+
+Old bytes live here as this is reasonable.
+txTZ
+Hello, World!
+ZTxt
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+BLOCK1
+Lorem Ipsum, Ipsum Lorem, Alpha Beta Gamma <1,1>
+{3,4} [4,5] (90,08)
+(1,4)
+[+001, +001]
+References {-004,-003}, <001,001>, [98,78]
+(+01,+00)
+AAAAAAAAA
+
+BLOCK2
+{06,01} Another block. Lorem Ipsum, Ipsum, Ipsum
+<><><><><>{}{}{}{}[][][]()()()()
+[4,1]
+
+Old bytes live here as this is reasonable.
+txTZ
+Yet another gap for Raw Zucchini
+„ABCDEFGHIJKLMNOPQRSTUVWXYZ
+ZTxt
+BLOCK2
+{20,01} Another block. Lorem Ipsum, Ipsum, Ipsum
+<><><><><>{}{}{}{}[][][]()()()()
+[4,1]
+
+BLOCK1
+Lorem Ipsum, Ipsum Lorem, Alpha Beta Gamma <1,1>
+{4,4} [5,8] (90,08)
+(1,4)
+[+001, +001]
+References {-005,-006}, <001,002>, [98,78]
+(+01,+04)
+AAAAAAAAA
+
+Other new bytes.
+
+Old bytes live here as this is reasonable.
+New bytes live here.
+txTZ
+Hello, World!
+ZTxt
+BLOCK2
+{20,01} Another block. Lorem Ipsum, Ipsum, Ipsum
+<><><><><>{}{}{}{}[][][]()()()()
+[4,1]
+
+BLOCK1
+Lorem Ipsum, Ipsum Lorem, Alpha Beta Gamma <1,1>
+{4,4} [5,8] (90,08)
+(1,4)
+[+001, +001]
+References {-005,-006}, <001,002>, [98,78]
+(+01,+04)
+AAAAAAAAA
+
+Other new bytes.
+
+Old bytes live here as this is reasonable.
+New bytes live here.
+txTZ
+Yet yet another gap for Raw Zucchini
+17+420=388+347,452+420=27+347
\ No newline at end of file
diff --git a/fuzzers/testdata/new_imposed_archive.txt b/fuzzers/testdata/new_imposed_archive.txt
new file mode 100644
index 0000000..5ce6f70
--- /dev/null
+++ b/fuzzers/testdata/new_imposed_archive.txt
@@ -0,0 +1,43 @@
+ABCDEFGHIJKLMNOPQRSTUVWXYZ
+ZTxt
+BLOCK2
+{20,01} Another block. Lorem Ipsum, Ipsum, Ipsum
+<><><><><>{}{}{}{}[][][]()()()()
+[4,1]
+
+BLOCK1
+Lorem Ipsum, Ipsum Lorem, Alpha Beta Gamma <1,1>
+{4,4} [5,8] (90,08)
+(1,4)
+[+001, +001]
+References {-005,-006}, <001,002>, [98,78]
+(+01,+04)
+AAAAAAAAA
+
+Other new bytes.
+
+Old bytes live here as this is reasonable.
+New bytes live here.
+txTZ
+Hello, World!
+ZTxt
+BLOCK2
+{20,01} Another block. Lorem Ipsum, Ipsum, Ipsum
+<><><><><>{}{}{}{}[][][]()()()()
+[4,1]
+
+BLOCK1
+Lorem Ipsum, Ipsum Lorem, Alpha Beta Gamma <1,1>
+{4,4} [5,8] (90,08)
+(1,4)
+[+001, +001]
+References {-005,-006}, <001,002>, [98,78]
+(+01,+04)
+AAAAAAAAA
+
+Other new bytes.
+
+Old bytes live here as this is reasonable.
+New bytes live here.
+txTZ
+Yet yet another gap for Raw Zucchini
diff --git a/fuzzers/testdata/old_imposed_archive.txt b/fuzzers/testdata/old_imposed_archive.txt
new file mode 100644
index 0000000..e4daa3f
--- /dev/null
+++ b/fuzzers/testdata/old_imposed_archive.txt
@@ -0,0 +1,45 @@
+ABCDEFGHIJKLMNOP
+ZTxt
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+BLOCK1
+Lorem Ipsum, Ipsum Lorem, Alpha Beta Gamma <1,1>
+{3,4} [4,5] (90,08)
+(1,4)
+[+001, +001]
+References {-004,-003}, <001,001>, [98,78]
+(+01,+00)
+AAAAAAAAA
+
+BLOCK2
+{06,01} Another block. Lorem Ipsum, Ipsum, Ipsum
+<><><><><>{}{}{}{}[][][]()()()()
+[4,1]
+
+Old bytes live here as this is reasonable.
+txTZ
+Hello, World!
+ZTxt
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+ZucZucZucZucZucZucZucZucZuc
+BLOCK1
+Lorem Ipsum, Ipsum Lorem, Alpha Beta Gamma <1,1>
+{3,4} [4,5] (90,08)
+(1,4)
+[+001, +001]
+References {-004,-003}, <001,001>, [98,78]
+(+01,+00)
+AAAAAAAAA
+
+BLOCK2
+{06,01} Another block. Lorem Ipsum, Ipsum, Ipsum
+<><><><><>{}{}{}{}[][][]()()()()
+[4,1]
+
+Old bytes live here as this is reasonable.
+txTZ
+Yet another gap for Raw Zucchini