1 // Copyright 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "components/zucchini/patch_reader.h"
6
7 #include <type_traits>
8 #include <utility>
9
10 #include "base/numerics/safe_conversions.h"
11 #include "components/zucchini/algorithm.h"
12 #include "components/zucchini/crc32.h"
13 #include "components/zucchini/element_detection.h"
14 #include "components/zucchini/version_info.h"
15
16 namespace zucchini {
17
18 namespace patch {
19
ParseElementMatch(BufferSource * source,ElementMatch * element_match)20 bool ParseElementMatch(BufferSource* source, ElementMatch* element_match) {
21 PatchElementHeader unsafe_element_header;
22 if (!source->GetValue(&unsafe_element_header)) {
23 LOG(ERROR) << "Impossible to read ElementMatch from source.";
24 return false;
25 }
26 ExecutableType exe_type =
27 CastToExecutableType(unsafe_element_header.exe_type);
28 if (exe_type == kExeTypeUnknown) {
29 LOG(ERROR) << "Invalid ExecutableType found.";
30 return false;
31 }
32 uint16_t element_version = DisassemblerVersionOfType(exe_type);
33 if (element_version != unsafe_element_header.version) {
34 LOG(ERROR) << "Element version doesn't match. Expected: " << element_version
35 << ", Actual:" << unsafe_element_header.version;
36 return false;
37 }
38 if (!unsafe_element_header.old_length || !unsafe_element_header.new_length) {
39 LOG(ERROR) << "Empty patch element found.";
40 return false;
41 }
42 // |unsafe_element_header| is now considered to be safe as it has a valid
43 // |exe_type| and the length fields are of sufficient size.
44 const auto& element_header = unsafe_element_header;
45
46 // Caveat: Element offsets and lengths can still be invalid (e.g., exceeding
47 // archive bounds), but this will be checked later.
48 element_match->old_element.offset = element_header.old_offset;
49 element_match->old_element.size = element_header.old_length;
50 element_match->new_element.offset = element_header.new_offset;
51 element_match->new_element.size = element_header.new_length;
52 element_match->old_element.exe_type = exe_type;
53 element_match->new_element.exe_type = exe_type;
54 return true;
55 }
56
ParseBuffer(BufferSource * source,BufferSource * buffer)57 bool ParseBuffer(BufferSource* source, BufferSource* buffer) {
58 uint32_t unsafe_size = 0; // Bytes.
59 static_assert(sizeof(size_t) >= sizeof(unsafe_size),
60 "size_t is expected to be larger than uint32_t.");
61 if (!source->GetValue(&unsafe_size)) {
62 LOG(ERROR) << "Impossible to read buffer size from source.";
63 return false;
64 }
65 if (!source->GetRegion(static_cast<size_t>(unsafe_size), buffer)) {
66 LOG(ERROR) << "Impossible to read buffer content from source.";
67 return false;
68 }
69 // Caveat: |buffer| is considered to be safe as it was possible to extract it
70 // from the patch. However, this does not mean its contents are safe and when
71 // parsed must be validated if possible.
72 return true;
73 }
74
75 } // namespace patch
76
77 /******** EquivalenceSource ********/
78
79 EquivalenceSource::EquivalenceSource() = default;
80 EquivalenceSource::EquivalenceSource(const EquivalenceSource&) = default;
81 EquivalenceSource::~EquivalenceSource() = default;
82
Initialize(BufferSource * source)83 bool EquivalenceSource::Initialize(BufferSource* source) {
84 return patch::ParseBuffer(source, &src_skip_) &&
85 patch::ParseBuffer(source, &dst_skip_) &&
86 patch::ParseBuffer(source, ©_count_);
87 }
88
GetNext()89 std::optional<Equivalence> EquivalenceSource::GetNext() {
90 if (src_skip_.empty() || dst_skip_.empty() || copy_count_.empty())
91 return std::nullopt;
92
93 Equivalence equivalence = {};
94
95 uint32_t length = 0;
96 if (!patch::ParseVarUInt<uint32_t>(©_count_, &length))
97 return std::nullopt;
98 equivalence.length = base::strict_cast<offset_t>(length);
99
100 int32_t src_offset_diff = 0; // Intentionally signed.
101 if (!patch::ParseVarInt<int32_t>(&src_skip_, &src_offset_diff))
102 return std::nullopt;
103 base::CheckedNumeric<offset_t> src_offset =
104 previous_src_offset_ + src_offset_diff;
105 if (!src_offset.IsValid())
106 return std::nullopt;
107
108 equivalence.src_offset = src_offset.ValueOrDie();
109 previous_src_offset_ = src_offset + equivalence.length;
110 if (!previous_src_offset_.IsValid())
111 return std::nullopt;
112
113 uint32_t dst_offset_diff = 0; // Intentionally unsigned.
114 if (!patch::ParseVarUInt<uint32_t>(&dst_skip_, &dst_offset_diff))
115 return std::nullopt;
116 base::CheckedNumeric<offset_t> dst_offset =
117 previous_dst_offset_ + dst_offset_diff;
118 if (!dst_offset.IsValid())
119 return std::nullopt;
120
121 equivalence.dst_offset = dst_offset.ValueOrDie();
122 previous_dst_offset_ = equivalence.dst_offset + equivalence.length;
123 if (!previous_dst_offset_.IsValid())
124 return std::nullopt;
125
126 // Caveat: |equivalence| is assumed to be safe only once the
127 // ValidateEquivalencesAndExtraData() method has returned true. Prior to this
128 // any equivalence returned is assumed to be unsafe.
129 return equivalence;
130 }
131
132 /******** ExtraDataSource ********/
133
134 ExtraDataSource::ExtraDataSource() = default;
135 ExtraDataSource::ExtraDataSource(const ExtraDataSource&) = default;
136 ExtraDataSource::~ExtraDataSource() = default;
137
Initialize(BufferSource * source)138 bool ExtraDataSource::Initialize(BufferSource* source) {
139 return patch::ParseBuffer(source, &extra_data_);
140 }
141
GetNext(offset_t size)142 std::optional<ConstBufferView> ExtraDataSource::GetNext(offset_t size) {
143 ConstBufferView buffer;
144 if (!extra_data_.GetRegion(size, &buffer))
145 return std::nullopt;
146 // |buffer| is assumed to always be safe/valid.
147 return buffer;
148 }
149
150 /******** RawDeltaSource ********/
151
152 RawDeltaSource::RawDeltaSource() = default;
153 RawDeltaSource::RawDeltaSource(const RawDeltaSource&) = default;
154 RawDeltaSource::~RawDeltaSource() = default;
155
Initialize(BufferSource * source)156 bool RawDeltaSource::Initialize(BufferSource* source) {
157 return patch::ParseBuffer(source, &raw_delta_skip_) &&
158 patch::ParseBuffer(source, &raw_delta_diff_);
159 }
160
GetNext()161 std::optional<RawDeltaUnit> RawDeltaSource::GetNext() {
162 if (raw_delta_skip_.empty() || raw_delta_diff_.empty())
163 return std::nullopt;
164
165 RawDeltaUnit raw_delta = {};
166 uint32_t copy_offset_diff = 0;
167 if (!patch::ParseVarUInt<uint32_t>(&raw_delta_skip_, ©_offset_diff))
168 return std::nullopt;
169 base::CheckedNumeric<offset_t> copy_offset =
170 copy_offset_diff + copy_offset_compensation_;
171 if (!copy_offset.IsValid())
172 return std::nullopt;
173 raw_delta.copy_offset = copy_offset.ValueOrDie();
174
175 if (!raw_delta_diff_.GetValue<int8_t>(&raw_delta.diff))
176 return std::nullopt;
177
178 // A 0 value for a delta.diff is considered invalid since it has no meaning.
179 if (!raw_delta.diff)
180 return std::nullopt;
181
182 // We keep track of the compensation needed for next offset, taking into
183 // account delta encoding and bias of -1.
184 copy_offset_compensation_ = copy_offset + 1;
185 if (!copy_offset_compensation_.IsValid())
186 return std::nullopt;
187 // |raw_delta| is assumed to always be safe/valid.
188 return raw_delta;
189 }
190
191 /******** ReferenceDeltaSource ********/
192
193 ReferenceDeltaSource::ReferenceDeltaSource() = default;
194 ReferenceDeltaSource::ReferenceDeltaSource(const ReferenceDeltaSource&) =
195 default;
196 ReferenceDeltaSource::~ReferenceDeltaSource() = default;
197
Initialize(BufferSource * source)198 bool ReferenceDeltaSource::Initialize(BufferSource* source) {
199 return patch::ParseBuffer(source, &source_);
200 }
201
GetNext()202 std::optional<int32_t> ReferenceDeltaSource::GetNext() {
203 if (source_.empty())
204 return std::nullopt;
205 int32_t ref_delta = 0;
206 if (!patch::ParseVarInt<int32_t>(&source_, &ref_delta))
207 return std::nullopt;
208 // |ref_delta| is assumed to always be safe/valid.
209 return ref_delta;
210 }
211
212 /******** TargetSource ********/
213
214 TargetSource::TargetSource() = default;
215 TargetSource::TargetSource(const TargetSource&) = default;
216 TargetSource::~TargetSource() = default;
217
Initialize(BufferSource * source)218 bool TargetSource::Initialize(BufferSource* source) {
219 return patch::ParseBuffer(source, &extra_targets_);
220 }
221
GetNext()222 std::optional<offset_t> TargetSource::GetNext() {
223 if (extra_targets_.empty())
224 return std::nullopt;
225
226 uint32_t target_diff = 0;
227 if (!patch::ParseVarUInt<uint32_t>(&extra_targets_, &target_diff))
228 return std::nullopt;
229 base::CheckedNumeric<offset_t> target = target_diff + target_compensation_;
230 if (!target.IsValid())
231 return std::nullopt;
232
233 // We keep track of the compensation needed for next target, taking into
234 // account delta encoding and bias of -1.
235 target_compensation_ = target + 1;
236 if (!target_compensation_.IsValid())
237 return std::nullopt;
238 // Caveat: |target| will be a valid offset_t, but it's up to the caller to
239 // check whether it's a valid offset for an image.
240 return offset_t(target.ValueOrDie());
241 }
242
243 /******** PatchElementReader ********/
244
245 PatchElementReader::PatchElementReader() = default;
246 PatchElementReader::PatchElementReader(PatchElementReader&&) = default;
247 PatchElementReader::~PatchElementReader() = default;
248
Initialize(BufferSource * source)249 bool PatchElementReader::Initialize(BufferSource* source) {
250 bool ok =
251 patch::ParseElementMatch(source, &element_match_) &&
252 equivalences_.Initialize(source) && extra_data_.Initialize(source) &&
253 ValidateEquivalencesAndExtraData() && raw_delta_.Initialize(source) &&
254 reference_delta_.Initialize(source);
255 if (!ok)
256 return false;
257 uint32_t pool_count = 0;
258 if (!source->GetValue(&pool_count)) {
259 LOG(ERROR) << "Impossible to read pool_count from source.";
260 return false;
261 }
262 for (uint32_t i = 0; i < pool_count; ++i) {
263 uint8_t pool_tag_value = 0;
264 if (!source->GetValue(&pool_tag_value)) {
265 LOG(ERROR) << "Impossible to read pool_tag from source.";
266 return false;
267 }
268 PoolTag pool_tag(pool_tag_value);
269 if (pool_tag == kNoPoolTag) {
270 LOG(ERROR) << "Invalid pool_tag encountered in ExtraTargetList.";
271 return false;
272 }
273 auto insert_result = extra_targets_.insert({pool_tag, {}});
274 if (!insert_result.second) { // Element already present.
275 LOG(ERROR) << "Multiple ExtraTargetList found for the same pool_tag.";
276 return false;
277 }
278 if (!insert_result.first->second.Initialize(source))
279 return false;
280 }
281 return true;
282 }
283
ValidateEquivalencesAndExtraData()284 bool PatchElementReader::ValidateEquivalencesAndExtraData() {
285 EquivalenceSource equivalences_copy = equivalences_;
286
287 const size_t old_region_size = element_match_.old_element.size;
288 const size_t new_region_size = element_match_.new_element.size;
289
290 base::CheckedNumeric<uint32_t> total_length = 0;
291 // Validate that each |equivalence| falls within the bounds of the
292 // |element_match_| and are in order.
293 offset_t prev_dst_end = 0;
294 for (auto equivalence = equivalences_copy.GetNext(); equivalence.has_value();
295 equivalence = equivalences_copy.GetNext()) {
296 if (!RangeIsBounded(equivalence->src_offset, equivalence->length,
297 old_region_size) ||
298 !RangeIsBounded(equivalence->dst_offset, equivalence->length,
299 new_region_size)) {
300 LOG(ERROR) << "Out of bounds equivalence detected.";
301 return false;
302 }
303 if (prev_dst_end > equivalence->dst_end()) {
304 LOG(ERROR) << "Out of order equivalence detected.";
305 return false;
306 }
307 prev_dst_end = equivalence->dst_end();
308 total_length += equivalence->length;
309 }
310 if (!total_length.IsValid() ||
311 element_match_.new_element.region().size < total_length.ValueOrDie() ||
312 extra_data_.extra_data().size() !=
313 element_match_.new_element.region().size -
314 static_cast<size_t>(total_length.ValueOrDie())) {
315 LOG(ERROR) << "Incorrect amount of extra_data.";
316 return false;
317 }
318 return true;
319 }
320
321 /******** EnsemblePatchReader ********/
322
Create(ConstBufferView buffer)323 std::optional<EnsemblePatchReader> EnsemblePatchReader::Create(
324 ConstBufferView buffer) {
325 BufferSource source(buffer);
326 EnsemblePatchReader patch;
327 if (!patch.Initialize(&source))
328 return std::nullopt;
329 return patch;
330 }
331
332 EnsemblePatchReader::EnsemblePatchReader() = default;
333 EnsemblePatchReader::EnsemblePatchReader(EnsemblePatchReader&&) = default;
334 EnsemblePatchReader::~EnsemblePatchReader() = default;
335
Initialize(BufferSource * source)336 bool EnsemblePatchReader::Initialize(BufferSource* source) {
337 if (!source->GetValue(&header_)) {
338 LOG(ERROR) << "Impossible to read header from source.";
339 return false;
340 }
341 if (header_.magic != PatchHeader::kMagic) {
342 LOG(ERROR) << "Patch contains invalid magic.";
343 return false;
344 }
345 if (header_.major_version != kMajorVersion) {
346 LOG(ERROR) << "Patch major version doesn't match. Expected: "
347 << kMajorVersion << ", Actual:" << header_.major_version;
348 return false;
349 }
350 // |header_| is assumed to be safe from this point forward.
351
352 uint32_t element_count = 0;
353 if (!source->GetValue(&element_count)) {
354 LOG(ERROR) << "Impossible to read element_count from source.";
355 return false;
356 }
357
358 offset_t current_dst_offset = 0;
359 for (uint32_t i = 0; i < element_count; ++i) {
360 PatchElementReader element_patch;
361 if (!element_patch.Initialize(source))
362 return false;
363
364 if (!element_patch.old_element().FitsIn(header_.old_size) ||
365 !element_patch.new_element().FitsIn(header_.new_size)) {
366 LOG(ERROR) << "Invalid element encountered.";
367 return false;
368 }
369
370 if (element_patch.new_element().offset != current_dst_offset) {
371 LOG(ERROR) << "Invalid element encountered.";
372 return false;
373 }
374 current_dst_offset = element_patch.new_element().EndOffset();
375
376 elements_.push_back(std::move(element_patch));
377 }
378 if (current_dst_offset != header_.new_size) {
379 LOG(ERROR) << "Patch elements don't fully cover new image file.";
380 return false;
381 }
382
383 if (!source->empty()) {
384 LOG(ERROR) << "Patch was not fully consumed.";
385 return false;
386 }
387
388 return true;
389 }
390
CheckOldFile(ConstBufferView old_image) const391 bool EnsemblePatchReader::CheckOldFile(ConstBufferView old_image) const {
392 return old_image.size() == header_.old_size &&
393 CalculateCrc32(old_image.begin(), old_image.end()) == header_.old_crc;
394 }
395
CheckNewFile(ConstBufferView new_image) const396 bool EnsemblePatchReader::CheckNewFile(ConstBufferView new_image) const {
397 return new_image.size() == header_.new_size &&
398 CalculateCrc32(new_image.begin(), new_image.end()) == header_.new_crc;
399 }
400
401 } // namespace zucchini
402