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