[Zucchini]: Stricter patch read

This enforces a stricter patch read in a few ways:
- Raw Deltas of 0 are forbidden. These are unused values which have no
  meaning and should not appear.
- Extra Data length must be equal to the size of the patch element
  minus the total length of equivalences.
- Element match headers must have regions of nonzero length.

This change also annotates a number of "unsafe" values read from the
patch that could be sources of error later if unchecked. It also adds
caveats about under what conditions emitted values are considered to
be safe/unsafe.

Bug: 837096
Change-Id: I1b7614d92b85c0a1546d8dccb7d371d28b2a4cd3
Reviewed-on: https://chromium-review.googlesource.com/1037186
Commit-Queue: Calder Kitagawa <ckitagawa@google.com>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Reviewed-by: Greg Thompson <grt@chromium.org>
Cr-Commit-Position: refs/heads/master@{#555396}
NOKEYCHECK=True
GitOrigin-RevId: 63f65c0a8b295b925c1dc92c7bed7625e7d99d46

3 files changed, 177 insertions, 79 deletions

diff --git a/patch_read_write_unittest.cc b/patch_read_write_unittest.cc
index ed0a6ed..681e3c2 100644
--- a/patch_read_write_unittest.cc
+++ b/patch_read_write_unittest.cc
@@ -60,13 +60,13 @@ ByteVector CreatePatchElement() {
       0x01, 0,   0,   0,    // old_offset
       0x03, 0,   0,   0,    // new_offset
       0x51, 0,   0,   0,    // old_length
-      0x50, 0,   0,   0,    // new_length
+      0x13, 0,   0,   0,    // new_length
       'P',  'x', '8', '6',  // EXE_TYPE_WIN32_X86
 
       1,    0,   0,   0,  // src_skip size
       0x10,               // src_skip content
       1,    0,   0,   0,  // dst_skip size
-      0x11,               // dst_skip content
+      0x00,               // dst_skip content
       1,    0,   0,   0,  // copy_count size
       0x12,               // copy_count content
 
@@ -91,8 +91,18 @@ ByteVector CreatePatchElement() {
   };
 }
 
-// Helper to mutate test |data| (e.g., from CreatePatchElement()) at |idx| from |from_val| (as
-// sanity check) to |to_val|.
+ByteVector CreateElementMatch() {
+  return {
+      0x01, 0,   0,   0,    // old_offset
+      0x03, 0,   0,   0,    // new_offset
+      0x02, 0,   0,   0,    // old_length
+      0x04, 0,   0,   0,    // new_length
+      'D',  'E', 'X', ' ',  // kExeTypeDex
+  };
+}
+
+// Helper to mutate test |data| (e.g., from CreatePatchElement()) at |idx| from
+// |from_val| (as sanity check) to |to_val|.
 void ModifyByte(size_t idx,
                 uint8_t from_val,
                 uint8_t to_val,
@@ -108,13 +118,7 @@ bool operator==(const ByteVector& a, ConstBufferView b) {
 }
 
 TEST(PatchTest, ParseSerializeElementMatch) {
-  ByteVector data = {
-      0x01, 0,   0,   0,    // old_offset
-      0x03, 0,   0,   0,    // new_offset
-      0x02, 0,   0,   0,    // old_length
-      0x04, 0,   0,   0,    // new_length
-      'D',  'E', 'X', ' ',  // kExeTypeDex
-  };
+  ByteVector data = CreateElementMatch();
   BufferSource buffer_source(data.data(), data.size());
   ElementMatch element_match = {};
   EXPECT_TRUE(patch::ParseElementMatch(&buffer_source, &element_match));
@@ -141,6 +145,34 @@ TEST(PatchTest, ParseElementMatchTooSmall) {
   EXPECT_FALSE(patch::ParseElementMatch(&buffer_source, &element_match));
 }
 
+TEST(PatchTest, ParseElementMatchNoLength) {
+  // Set old_length to 0 to trigger an error.
+  {
+    ByteVector data = CreateElementMatch();
+    ModifyByte(8U, 0x02, 0x00, &data);  // Make the old_length = 0.
+    BufferSource buffer_source(data.data(), data.size());
+    ElementMatch element_match = {};
+    EXPECT_FALSE(patch::ParseElementMatch(&buffer_source, &element_match));
+  }
+  // Set new_length to 0 to trigger an error.
+  {
+    ByteVector data = CreateElementMatch();
+    ModifyByte(12U, 0x04, 0x00, &data);  // Make the new_length = 0.
+    BufferSource buffer_source(data.data(), data.size());
+    ElementMatch element_match = {};
+    EXPECT_FALSE(patch::ParseElementMatch(&buffer_source, &element_match));
+  }
+  // Set both new_length and old_length to 0 to trigger an error.
+  {
+    ByteVector data = CreateElementMatch();
+    ModifyByte(8U, 0x02, 0x00, &data);   // Make the old_length = 0.
+    ModifyByte(12U, 0x04, 0x00, &data);  // Make the new_length = 0.
+    BufferSource buffer_source(data.data(), data.size());
+    ElementMatch element_match = {};
+    EXPECT_FALSE(patch::ParseElementMatch(&buffer_source, &element_match));
+  }
+}
+
 TEST(PatchTest, ParseSerializeElementMatchExeMismatch) {
   ByteVector buffer(28);
   BufferSink buffer_sink(buffer.data(), buffer.size());
@@ -356,6 +388,18 @@ TEST(RawDeltaSinkSourceSinkTest, Normal) {
   TestSerialize(data, raw_delta_sink);
 }
 
+TEST(RawDeltaSourceSinkTest, InvalidContent) {
+  ByteVector data = {
+      2, 0, 0, 0,  // raw_delta_skip size
+      1, 3,        // raw_delta_skip content
+      2, 0, 0, 0,  // raw_delta_diff size
+      0, 4,        // raw_delta_diff content
+  };
+  RawDeltaSource raw_delta_source = TestInitialize<RawDeltaSource>(&data);
+  EXPECT_FALSE(raw_delta_source.GetNext());
+  EXPECT_FALSE(raw_delta_source.Done());
+}
+
 TEST(ReferenceDeltaSourceSinkTest, Empty) {
   ByteVector data = {
       0, 0, 0, 0,  // reference_delta size
@@ -449,12 +493,12 @@ TEST(PatchElementTest, Normal) {
   EXPECT_EQ(0x1U, element_match.old_element.offset);
   EXPECT_EQ(0x51U, element_match.old_element.size);
   EXPECT_EQ(0x3U, element_match.new_element.offset);
-  EXPECT_EQ(0x50U, element_match.new_element.size);
+  EXPECT_EQ(0x13U, element_match.new_element.size);
 
   EquivalenceSource equivalence_source =
       patch_element_reader.GetEquivalenceSource();
   EXPECT_EQ(ByteVector({0x10}), equivalence_source.src_skip());
-  EXPECT_EQ(ByteVector({0x11}), equivalence_source.dst_skip());
+  EXPECT_EQ(ByteVector({0x00}), equivalence_source.dst_skip());
   EXPECT_EQ(ByteVector({0x12}), equivalence_source.copy_count());
 
   ExtraDataSource extra_data_source = patch_element_reader.GetExtraDataSource();
@@ -481,7 +525,7 @@ TEST(PatchElementTest, Normal) {
   PatchElementWriter patch_element_writer(element_match);
 
   patch_element_writer.SetEquivalenceSink(
-      EquivalenceSink({0x10}, {0x11}, {0x12}));
+      EquivalenceSink({0x10}, {0x00}, {0x12}));
   patch_element_writer.SetExtraDataSink(ExtraDataSink({0x13}));
   patch_element_writer.SetRawDeltaSink(RawDeltaSink({0x14}, {0x15}));
   patch_element_writer.SetReferenceDeltaSink(ReferenceDeltaSink({0x16}));
@@ -501,7 +545,23 @@ TEST(PatchElementTest, BadEquivalence) {
   // If the "new" element is too small the test should fail.
   {
     ByteVector data = CreatePatchElement();
-    ModifyByte(12, 0x50, 0x05, &data);  // new_length (too small)
+    ModifyByte(12, 0x13, 0x05, &data);  // new_length (too small)
+    TestInvalidInitialize<PatchElementReader>(&data);
+  }
+}
+
+TEST(PatchElementTest, WrongExtraData) {
+  // Make "new" too large so there is insufficient extra data to cover the
+  // image.
+  {
+    ByteVector data = CreatePatchElement();
+    ModifyByte(12, 0x13, 0x14, &data);  // new_length (too large)
+    TestInvalidInitialize<PatchElementReader>(&data);
+  }
+  // Make "new" too small so there is too much extra data.
+  {
+    ByteVector data = CreatePatchElement();
+    ModifyByte(12, 0x13, 0x14, &data);  // new_length (too small)
     TestInvalidInitialize<PatchElementReader>(&data);
   }
 }
@@ -511,24 +571,25 @@ TEST(EnsemblePatchTest, RawPatch) {
       0x5A, 0x75, 0x63, 0x00,  // magic
       0x10, 0x32, 0x54, 0x76,  // old_size
       0x00, 0x11, 0x22, 0x33,  // old_crc
-      0x98, 0xBA, 0xDC, 0xFE,  // new_size
+      0x01, 0,    0,    0,     // new_size
       0x44, 0x55, 0x66, 0x77,  // new_crc
 
       1,    0,    0,    0,  // number of element
 
-      0x01, 0,    0,    0,     // old_offset
-      0x00, 0,    0,    0,     // new_offset
-      0x02, 0,    0,    0,     // old_length
-      0x98, 0xBA, 0xDC, 0xFE,  // new_length
-      'P',  'x',  '8',  '6',   // EXE_TYPE_WIN32_X86
-      0,    0,    0,    0,     // src_skip size
-      0,    0,    0,    0,     // dst_skip size
-      0,    0,    0,    0,     // copy_count size
-      0,    0,    0,    0,     // extra_data size
-      0,    0,    0,    0,     // raw_delta_skip size
-      0,    0,    0,    0,     // raw_delta_diff size
-      0,    0,    0,    0,     // reference_delta size
-      0,    0,    0,    0,     // pool count
+      0x01, 0,    0,    0,    // old_offset
+      0x00, 0,    0,    0,    // new_offset
+      0x02, 0,    0,    0,    // old_length
+      0x01, 0,    0,    0,    // new_length
+      'P',  'x',  '8',  '6',  // EXE_TYPE_WIN32_X86
+      0,    0,    0,    0,    // src_skip size
+      0,    0,    0,    0,    // dst_skip size
+      0,    0,    0,    0,    // copy_count size
+      0x01, 0,    0,    0,    // extra_data size
+      0x04,                   // extra_data content
+      0,    0,    0,    0,    // raw_delta_skip size
+      0,    0,    0,    0,    // raw_delta_diff size
+      0,    0,    0,    0,    // reference_delta size
+      0,    0,    0,    0,    // pool count
   };
 
   EnsemblePatchReader ensemble_patch_reader =
@@ -538,7 +599,7 @@ TEST(EnsemblePatchTest, RawPatch) {
   EXPECT_EQ(PatchHeader::kMagic, header.magic);
   EXPECT_EQ(0x76543210U, header.old_size);
   EXPECT_EQ(0x33221100U, header.old_crc);
-  EXPECT_EQ(0xFEDCBA98U, header.new_size);
+  EXPECT_EQ(0x01U, header.new_size);
   EXPECT_EQ(0x77665544U, header.new_crc);
 
   const std::vector<PatchElementReader>& elements =
@@ -548,7 +609,7 @@ TEST(EnsemblePatchTest, RawPatch) {
   EnsemblePatchWriter ensemble_patch_writer(header);
   PatchElementWriter patch_element_writer(elements[0].element_match());
   patch_element_writer.SetEquivalenceSink({});
-  patch_element_writer.SetExtraDataSink({});
+  patch_element_writer.SetExtraDataSink(ExtraDataSink({0x04}));
   patch_element_writer.SetRawDeltaSink({});
   patch_element_writer.SetReferenceDeltaSink({});
   ensemble_patch_writer.AddElement(std::move(patch_element_writer));
@@ -574,7 +635,8 @@ TEST(EnsemblePatchTest, CheckFile) {
       0,    0,    0,    0,    // src_skip size
       0,    0,    0,    0,    // dst_skip size
       0,    0,    0,    0,    // copy_count size
-      0,    0,    0,    0,    // extra_data size
+      0x03, 0,    0,    0,    // extra_data size
+      'A',  'B',  'C',        // extra_data content
       0,    0,    0,    0,    // raw_delta_skip size
       0,    0,    0,    0,    // raw_delta_diff size
       0,    0,    0,    0,    // reference_delta size
@@ -606,19 +668,19 @@ TEST(EnsemblePatchTest, InvalidMagic) {
 
       1,    0,    0,    0,  // number of element
 
-      0x01, 0,    0,    0,  // old_offset
-      0x00, 0,    0,    0,  // new_offset
-      0x02, 0,    0,    0,  // old_length
-      0x03, 0,    0,    0,  // new_length
-      1,    0,    0,    0,  // EXE_TYPE_WIN32_X86
-      0,    0,    0,    0,  // src_skip size
-      0,    0,    0,    0,  // dst_skip size
-      0,    0,    0,    0,  // copy_count size
-      0,    0,    0,    0,  // extra_data size
-      0,    0,    0,    0,  // raw_delta_skip size
-      0,    0,    0,    0,  // raw_delta_diff size
-      0,    0,    0,    0,  // reference_delta size
-      0,    0,    0,    0,  // pool count
+      0x01, 0,    0,    0,    // old_offset
+      0x00, 0,    0,    0,    // new_offset
+      0x02, 0,    0,    0,    // old_length
+      0x03, 0,    0,    0,    // new_length
+      'P',  'x',  '8',  '6',  // EXE_TYPE_WIN32_X86
+      0,    0,    0,    0,    // src_skip size
+      0,    0,    0,    0,    // dst_skip size
+      0,    0,    0,    0,    // copy_count size
+      0,    0,    0,    0,    // extra_data size
+      0,    0,    0,    0,    // raw_delta_skip size
+      0,    0,    0,    0,    // raw_delta_diff size
+      0,    0,    0,    0,    // reference_delta size
+      0,    0,    0,    0,    // pool count
   };
 
   TestInvalidInitialize<EnsemblePatchReader>(&data);
diff --git a/patch_reader.cc b/patch_reader.cc
index 179f0fd..0215bc8 100644
--- a/patch_reader.cc
+++ b/patch_reader.cc
@@ -16,19 +16,27 @@ namespace zucchini {
 namespace patch {
 
 bool ParseElementMatch(BufferSource* source, ElementMatch* element_match) {
-  PatchElementHeader element_header;
-  if (!source->GetValue(&element_header)) {
+  PatchElementHeader unsafe_element_header;
+  if (!source->GetValue(&unsafe_element_header)) {
     LOG(ERROR) << "Impossible to read ElementMatch from source.";
-    LOG(ERROR) << base::debug::StackTrace().ToString();
     return false;
   }
   ExecutableType exe_type =
-      static_cast<ExecutableType>(element_header.exe_type);
-  if (CastToExecutableType(exe_type) == kExeTypeUnknown) {
-    LOG(ERROR) << "Invalid ExecutableType encountered.";
-    LOG(ERROR) << base::debug::StackTrace().ToString();
+      CastToExecutableType(unsafe_element_header.exe_type);
+  if (exe_type == kExeTypeUnknown) {
+    LOG(ERROR) << "Invalid ExecutableType found.";
     return false;
   }
+  if (!unsafe_element_header.old_length || !unsafe_element_header.new_length) {
+    LOG(ERROR) << "Empty patch element found.";
+    return false;
+  }
+  // |unsafe_element_header| is now considered to be safe as it has a valid
+  // |exe_type| and the length fields are of sufficient size.
+  const auto& element_header = unsafe_element_header;
+
+  // Caveat: Element offsets and lengths can still be invalid (e.g., exceeding
+  // archive bounds), but this will be checked later.
   element_match->old_element.offset = element_header.old_offset;
   element_match->new_element.offset = element_header.new_offset;
   element_match->old_element.size = element_header.old_length;
@@ -39,17 +47,20 @@ bool ParseElementMatch(BufferSource* source, ElementMatch* element_match) {
 }
 
 bool ParseBuffer(BufferSource* source, BufferSource* buffer) {
-  uint32_t size = 0;
-  if (!source->GetValue(&size)) {
+  uint32_t unsafe_size = 0;  // Bytes.
+  static_assert(sizeof(size_t) >= sizeof(unsafe_size),
+                "size_t is expected to be larger than uint32_t.");
+  if (!source->GetValue(&unsafe_size)) {
     LOG(ERROR) << "Impossible to read buffer size from source.";
-    LOG(ERROR) << base::debug::StackTrace().ToString();
     return false;
   }
-  if (!source->GetRegion(base::checked_cast<size_t>(size), buffer)) {
+  if (!source->GetRegion(static_cast<size_t>(unsafe_size), buffer)) {
     LOG(ERROR) << "Impossible to read buffer content from source.";
-    LOG(ERROR) << base::debug::StackTrace().ToString();
     return false;
   }
+  // Caveat: |buffer| is considered to be safe as it was possible to extract it
+  // from the patch. However, this does not mean its contents are safe and when
+  // parsed must be validated if possible.
   return true;
 }
 
@@ -104,6 +115,9 @@ base::Optional<Equivalence> EquivalenceSource::GetNext() {
   if (!previous_dst_offset_.IsValid())
     return base::nullopt;
 
+  // Caveat: |equivalence| is assumed to be safe only once the
+  // ValidateEquivalencesAndExtraData() method has returned true. Prior to this
+  // any equivalence returned is assumed to be unsafe.
   return equivalence;
 }
 
@@ -121,6 +135,7 @@ base::Optional<ConstBufferView> ExtraDataSource::GetNext(offset_t size) {
   ConstBufferView buffer;
   if (!extra_data_.GetRegion(size, &buffer))
     return base::nullopt;
+  // |buffer| is assumed to always be safe/valid.
   return buffer;
 }
 
@@ -139,7 +154,7 @@ base::Optional<RawDeltaUnit> RawDeltaSource::GetNext() {
   if (raw_delta_skip_.empty() || raw_delta_diff_.empty())
     return base::nullopt;
 
-  RawDeltaUnit delta = {};
+  RawDeltaUnit raw_delta = {};
   uint32_t copy_offset_diff = 0;
   if (!patch::ParseVarUInt<uint32_t>(&raw_delta_skip_, &copy_offset_diff))
     return base::nullopt;
@@ -147,17 +162,22 @@ base::Optional<RawDeltaUnit> RawDeltaSource::GetNext() {
       copy_offset_diff + copy_offset_compensation_;
   if (!copy_offset.IsValid())
     return base::nullopt;
-  delta.copy_offset = copy_offset.ValueOrDie();
+  raw_delta.copy_offset = copy_offset.ValueOrDie();
 
-  if (!raw_delta_diff_.GetValue<int8_t>(&delta.diff))
+  if (!raw_delta_diff_.GetValue<int8_t>(&raw_delta.diff))
+    return base::nullopt;
+
+  // A 0 value for a delta.diff is considered invalid since it has no meaning.
+  if (!raw_delta.diff)
     return base::nullopt;
 
   // We keep track of the compensation needed for next offset, taking into
-  // accound delta encoding and bias of -1.
+  // account delta encoding and bias of -1.
   copy_offset_compensation_ = copy_offset + 1;
   if (!copy_offset_compensation_.IsValid())
     return base::nullopt;
-  return delta;
+  // |raw_delta| is assumed to always be safe/valid.
+  return raw_delta;
 }
 
 /******** ReferenceDeltaSource ********/
@@ -168,16 +188,17 @@ ReferenceDeltaSource::ReferenceDeltaSource(const ReferenceDeltaSource&) =
 ReferenceDeltaSource::~ReferenceDeltaSource() = default;
 
 bool ReferenceDeltaSource::Initialize(BufferSource* source) {
-  return patch::ParseBuffer(source, &reference_delta_);
+  return patch::ParseBuffer(source, &source_);
 }
 
 base::Optional<int32_t> ReferenceDeltaSource::GetNext() {
-  if (reference_delta_.empty())
+  if (source_.empty())
     return base::nullopt;
-  int32_t delta = 0;
-  if (!patch::ParseVarInt<int32_t>(&reference_delta_, &delta))
+  int32_t ref_delta = 0;
+  if (!patch::ParseVarInt<int32_t>(&source_, &ref_delta))
     return base::nullopt;
-  return delta;
+  // |ref_delta| is assumed to always be safe/valid.
+  return ref_delta;
 }
 
 /******** TargetSource ********/
@@ -202,10 +223,12 @@ base::Optional<offset_t> TargetSource::GetNext() {
     return base::nullopt;
 
   // We keep track of the compensation needed for next target, taking into
-  // accound delta encoding and bias of -1.
+  // account delta encoding and bias of -1.
   target_compensation_ = target + 1;
   if (!target_compensation_.IsValid())
     return base::nullopt;
+  // Caveat: |target| will be a valid offset_t, but it's up to the caller to
+  // check whether it's a valid offset for an image.
   return offset_t(target.ValueOrDie());
 }
 
@@ -216,10 +239,11 @@ PatchElementReader::PatchElementReader(PatchElementReader&&) = default;
 PatchElementReader::~PatchElementReader() = default;
 
 bool PatchElementReader::Initialize(BufferSource* source) {
-  bool ok = patch::ParseElementMatch(source, &element_match_) &&
-            equivalences_.Initialize(source) && ValidateEquivalences() &&
-            extra_data_.Initialize(source) && raw_delta_.Initialize(source) &&
-            reference_delta_.Initialize(source);
+  bool ok =
+      patch::ParseElementMatch(source, &element_match_) &&
+      equivalences_.Initialize(source) && extra_data_.Initialize(source) &&
+      ValidateEquivalencesAndExtraData() && raw_delta_.Initialize(source) &&
+      reference_delta_.Initialize(source);
   if (!ok)
     return false;
   uint32_t pool_count = 0;
@@ -249,12 +273,13 @@ bool PatchElementReader::Initialize(BufferSource* source) {
   return true;
 }
 
-bool PatchElementReader::ValidateEquivalences() {
+bool PatchElementReader::ValidateEquivalencesAndExtraData() {
   EquivalenceSource equivalences_copy = equivalences_;
 
   const size_t old_region_size = element_match_.old_element.size;
   const size_t new_region_size = element_match_.new_element.size;
 
+  base::CheckedNumeric<uint32_t> total_length = 0;
   // Validate that each |equivalence| falls within the bounds of the
   // |element_match_| and are in order.
   offset_t prev_dst_end = 0;
@@ -272,6 +297,15 @@ bool PatchElementReader::ValidateEquivalences() {
       return false;
     }
     prev_dst_end = equivalence->dst_end();
+    total_length += equivalence->length;
+  }
+  if (!total_length.IsValid() ||
+      element_match_.new_element.region().size < total_length.ValueOrDie() ||
+      extra_data_.extra_data().size() !=
+          element_match_.new_element.region().size -
+              static_cast<size_t>(total_length.ValueOrDie())) {
+    LOG(ERROR) << "Incorrect amount of extra_data.";
+    return false;
   }
   return true;
 }
@@ -300,6 +334,7 @@ bool EnsemblePatchReader::Initialize(BufferSource* source) {
     LOG(ERROR) << "Patch contains invalid magic.";
     return false;
   }
+  // |header_| is assumed to be safe from this point forward.
 
   uint32_t element_count = 0;
   if (!source->GetValue(&element_count)) {
diff --git a/patch_reader.h b/patch_reader.h
index 5d3c6dd..515da50 100644
--- a/patch_reader.h
+++ b/patch_reader.h
@@ -168,13 +168,13 @@ class ReferenceDeltaSource {
   // Core functions.
   bool Initialize(BufferSource* source);
   base::Optional<int32_t> GetNext();
-  bool Done() const { return reference_delta_.empty(); }
+  bool Done() const { return source_.empty(); }
 
   // Accessors for unittest.
-  BufferSource reference_delta() const { return reference_delta_; }
+  BufferSource reference_delta() const { return source_; }
 
  private:
-  BufferSource reference_delta_;
+  BufferSource source_;
 };
 
 // Source for additional targets.
@@ -236,9 +236,10 @@ class PatchElementReader {
 
  private:
   // Checks that "old" and "new" blocks of each item in |equivalences_| satisfy
-  // basic order and image bound constraints (using |element_match_| data).
-  // Returns true if successful.
-  bool ValidateEquivalences();
+  // basic order and image bound constraints (using |element_match_| data). Also
+  // validates that the amount of extra data is correct. Returns true if
+  // successful.
+  bool ValidateEquivalencesAndExtraData();
 
   ElementMatch element_match_;