1 /*
2 * Copyright (c) 2012 The Native Client Authors. All rights reserved.
3 * Use of this source code is governed by a BSD-style license that can be
4 * found in the LICENSE file.
5 */
6
7 #include <climits>
8 #include <cstdarg>
9
10 #include "native_client/src/trusted/service_runtime/nacl_config.h"
11 #include "native_client/src/trusted/validator_arm/model.h"
12 #include "native_client/src/trusted/validator_arm/validator.h"
13 #include "native_client/src/include/nacl_macros.h"
14 #include "native_client/src/include/portability_bits.h"
15 #include "native_client/src/shared/platform/nacl_log.h"
16
17 using nacl_arm_dec::Instruction;
18 using nacl_arm_dec::ClassDecoder;
19 using nacl_arm_dec::Register;
20 using nacl_arm_dec::RegisterList;
21
22 using std::vector;
23
24 namespace nacl_arm_val {
25
26 /*********************************************************
27 *
28 * Implementation of SfiValidator itself.
29 *
30 *********************************************************/
31
32 // See ARM ARM A8.3 Conditional execution.
33 //
34 // Flags are:
35 // N - Negative condition code flag.
36 // Z - Zero condition code flag.
37 // C - Carry condition code flag.
38 // V - Overflow condition code flag.
39 const bool SfiValidator::
40 condition_implies[nacl_arm_dec::Instruction::kConditionSize + 1]
41 [nacl_arm_dec::Instruction::kConditionSize + 1] = {
42 # if defined(T) || defined(_)
43 # error Macros already defined.
44 # endif
45 # define T true
46 # define _ false
47 // EQ NE CS CC MI PL VS VC HI LS GE LT GT LE AL UN
48 /* EQ => Z==1 */ { T, _, _, _, _, _, _, _, _, T, _, _, _, _, T, T },
49 /* NE => Z==0 */ { _, T, _, _, _, _, _, _, _, _, _, _, _, _, T, T },
50 /* CS => C==1 */ { _, _, T, _, _, _, _, _, _, _, _, _, _, _, T, T },
51 /* CC => C==0 */ { _, _, _, T, _, _, _, _, _, T, _, _, _, _, T, T },
52 /* MI => N==1 */ { _, _, _, _, T, _, _, _, _, _, _, _, _, _, T, T },
53 /* PL => N==0 */ { _, _, _, _, _, T, _, _, _, _, _, _, _, _, T, T },
54 /* VS => V==1 */ { _, _, _, _, _, _, T, _, _, _, _, _, _, _, T, T },
55 /* VC => V==0 */ { _, _, _, _, _, _, _, T, _, _, _, _, _, _, T, T },
56 /* HI => C==1 & Z==0 */ { _, T, T, _, _, _, _, _, T, _, _, _, _, _, T, T },
57 /* LS => C==0 | Z==1 */ { _, _, _, _, _, _, _, _, _, T, _, _, _, _, T, T },
58 /* GE => N==V */ { _, _, _, _, _, _, _, _, _, _, T, _, _, _, T, T },
59 /* LT => N!=V */ { _, _, _, _, _, _, _, _, _, _, _, T, _, _, T, T },
60 /* GT => Z==0 & N==V */ { _, T, _, _, _, _, _, _, _, _, T, _, T, _, T, T },
61 /* LE => Z==1 & N!=V */ { T, _, _, _, _, _, _, _, _, T, _, T, _, T, T, T },
62 /* AL => Any */ { _, _, _, _, _, _, _, _, _, _, _, _, _, _, T, T },
63 /* UN => Any */ { _, _, _, _, _, _, _, _, _, _, _, _, _, _, T, T },
64 # undef _
65 # undef T
66 };
67
SfiValidator(uint32_t bytes_per_bundle,uint32_t code_region_bytes,uint32_t data_region_bytes,RegisterList read_only_registers,RegisterList data_address_registers,const NaClCPUFeaturesArm * cpu_features)68 SfiValidator::SfiValidator(uint32_t bytes_per_bundle,
69 uint32_t code_region_bytes,
70 uint32_t data_region_bytes,
71 RegisterList read_only_registers,
72 RegisterList data_address_registers,
73 const NaClCPUFeaturesArm *cpu_features)
74 : cpu_features_(),
75 bytes_per_bundle_(bytes_per_bundle),
76 code_region_bytes_(code_region_bytes),
77 data_region_bytes_(data_region_bytes),
78 read_only_registers_(read_only_registers),
79 data_address_registers_(data_address_registers),
80 decode_state_(),
81 construction_failed_(false),
82 is_position_independent_(true) {
83 NaClCopyCPUFeaturesArm(&cpu_features_, cpu_features);
84 // Make sure we can construct sane masks with the values.
85 if ((nacl::PopCount(bytes_per_bundle_) != 1) ||
86 (nacl::PopCount(code_region_bytes_) != 1) ||
87 (nacl::PopCount(data_region_bytes_) != 1) ||
88 (bytes_per_bundle_ < 4) ||
89 (code_region_bytes_ < 4) ||
90 (data_region_bytes_ < 4) ||
91 (code_region_bytes_ < bytes_per_bundle_)) {
92 construction_failed_ = true;
93 }
94 }
95
SfiValidator(const SfiValidator & v)96 SfiValidator::SfiValidator(const SfiValidator& v)
97 : cpu_features_(),
98 bytes_per_bundle_(v.bytes_per_bundle_),
99 code_region_bytes_(v.code_region_bytes_),
100 data_region_bytes_(v.data_region_bytes_),
101 read_only_registers_(v.read_only_registers_),
102 data_address_registers_(v.data_address_registers_),
103 decode_state_(),
104 construction_failed_(v.construction_failed_),
105 is_position_independent_(v.is_position_independent_) {
106 NaClCopyCPUFeaturesArm(&cpu_features_, v.CpuFeatures());
107 }
108
operator =(const SfiValidator & v)109 SfiValidator& SfiValidator::operator=(const SfiValidator& v) {
110 NaClCopyCPUFeaturesArm(&cpu_features_, v.CpuFeatures());
111 bytes_per_bundle_ = v.bytes_per_bundle_;
112 code_region_bytes_ = v.code_region_bytes_;
113 data_region_bytes_ = v.data_region_bytes_;
114 read_only_registers_.Copy(v.read_only_registers_);
115 data_address_registers_.Copy(v.data_address_registers_);
116 construction_failed_ = v.construction_failed_;
117 is_position_independent_ = v.is_position_independent_;
118 return *this;
119 }
120
121 nacl_arm_dec::ViolationSet SfiValidator::
find_violations(const vector<CodeSegment> & segments,ProblemSink * out)122 find_violations(const vector<CodeSegment>& segments,
123 ProblemSink* out) {
124 if (ConstructionFailed(out))
125 return nacl_arm_dec::ViolationBit(nacl_arm_dec::OTHER_VIOLATION);
126
127 uint32_t base = segments[0].begin_addr();
128 uint32_t size = segments.back().end_addr() - base;
129 AddressSet branches(base, size);
130 AddressSet critical(base, size);
131
132 nacl_arm_dec::ViolationSet found_violations = nacl_arm_dec::kNoViolations;
133
134 for (vector<CodeSegment>::const_iterator it = segments.begin();
135 it != segments.end(); ++it) {
136 nacl_arm_dec::ViolationSet segment_violations =
137 validate_fallthrough(*it, out, &branches, &critical);
138 found_violations =
139 nacl_arm_dec::ViolationUnion(found_violations, segment_violations);
140 if (segment_violations && (out == NULL)) return found_violations;
141 }
142
143 return
144 nacl_arm_dec::ViolationUnion(
145 found_violations,
146 validate_branches(segments, branches, critical, out));
147 }
148
ValidateSegmentPair(const CodeSegment & old_code,const CodeSegment & new_code,ProblemSink * out)149 bool SfiValidator::ValidateSegmentPair(const CodeSegment& old_code,
150 const CodeSegment& new_code,
151 ProblemSink* out) {
152 // This code verifies that the new code is just like the old code,
153 // except a few (acceptable) literal constants have been replaced
154 // in the new code segment. Hence, checking of safety etc. is not
155 // necessary. We assume that this was done on the old code, and
156 // does not need to be done again.
157 if (ConstructionFailed(out))
158 return false;
159
160 if ((old_code.begin_addr() != new_code.begin_addr()) ||
161 (old_code.end_addr() != new_code.end_addr())) {
162 return false;
163 }
164
165 bool complete_success = true;
166 bool current_bundle_is_literal_pool = false;
167
168 // The following loop expects the first address to be
169 // bundle-aligned. This invariant is checked in the validator's C
170 // interface and it therefore not checked again.
171 NACL_COMPILE_TIME_ASSERT((nacl_arm_dec::kArm32InstSize / CHAR_BIT) == 4);
172 for (uint32_t va = old_code.begin_addr();
173 va != old_code.end_addr();
174 va += nacl_arm_dec::kArm32InstSize / CHAR_BIT) {
175 Instruction old_insn = old_code[va];
176 Instruction new_insn = new_code[va];
177
178 // Keep track of literal pools: it's valid to replace any value in them.
179 // Literal pools should still be at the same place in the old and new code.
180 if (is_bundle_head(va)) {
181 const ClassDecoder& old_decoder = decode_state_.decode(old_insn);
182 current_bundle_is_literal_pool =
183 (old_decoder.is_literal_pool_head(old_insn) &&
184 new_insn.Equals(old_insn));
185 }
186
187 // Accept any change inside a literal pool.
188 if (current_bundle_is_literal_pool)
189 continue;
190
191 // See if the instruction has changed in the new version. If not,
192 // there is nothing to check, and we can skip to the next
193 // instruction.
194 if (new_insn.Equals(old_insn))
195 continue;
196
197 // Decode instructions and get corresponding decoders.
198 const ClassDecoder& old_decoder = decode_state_.decode(old_insn);
199 const ClassDecoder& new_decoder = decode_state_.decode(new_insn);
200
201 // Convert the instructions into their sentinel form (i.e.
202 // convert immediate values to zero if applicable).
203 Instruction old_sentinel(
204 old_decoder.dynamic_code_replacement_sentinel(old_insn));
205 Instruction new_sentinel(
206 new_decoder.dynamic_code_replacement_sentinel(new_insn));
207
208 // Report problem if the sentinels differ, and reject the replacement.
209 if (!new_sentinel.Equals(old_sentinel)) {
210 if (out == NULL) return false;
211 out->ReportProblemDiagnostic(nacl_arm_dec::OTHER_VIOLATION,
212 va,
213 "Sentinels at %08" NACL_PRIx32 " differ.",
214 va);
215 complete_success = false;
216 }
217 }
218
219 return complete_success;
220 }
221
CopyCode(const CodeSegment & source_code,CodeSegment * dest_code,NaClCopyInstructionFunc copy_func,ProblemSink * out)222 bool SfiValidator::CopyCode(const CodeSegment& source_code,
223 CodeSegment* dest_code,
224 NaClCopyInstructionFunc copy_func,
225 ProblemSink* out) {
226 if (ConstructionFailed(out))
227 return false;
228
229 vector<CodeSegment> segments;
230 segments.push_back(source_code);
231 if (!validate(segments, out))
232 return false;
233
234 // As on ARM all instructions are 4 bytes in size and aligned
235 // we don't have to check instruction boundary invariant.
236 for (uintptr_t va = source_code.begin_addr();
237 va != source_code.end_addr();
238 va += nacl_arm_dec::kArm32InstSize / CHAR_BIT) {
239 intptr_t offset = va - source_code.begin_addr();
240 // TODO(olonho): this const cast is a bit ugly, but we
241 // need to write to dest segment.
242 copy_func(const_cast<uint8_t*>(dest_code->base()) + offset,
243 const_cast<uint8_t*>(source_code.base()) + offset,
244 nacl_arm_dec::kArm32InstSize / CHAR_BIT);
245 }
246
247 return true;
248 }
249
ConstructionFailed(ProblemSink * out)250 bool SfiValidator::ConstructionFailed(ProblemSink* out) {
251 if (construction_failed_ && (out != NULL)) {
252 uint32_t invalid_addr = ~(uint32_t)0;
253 out->ReportProblemDiagnostic(nacl_arm_dec::OTHER_VIOLATION,
254 invalid_addr,
255 "Construction of validator failed!");
256 }
257 return construction_failed_;
258 }
259
validate_fallthrough(const CodeSegment & segment,ProblemSink * out,AddressSet * branches,AddressSet * critical)260 nacl_arm_dec::ViolationSet SfiValidator::validate_fallthrough(
261 const CodeSegment& segment,
262 ProblemSink* out,
263 AddressSet* branches,
264 AddressSet* critical) {
265 nacl_arm_dec::ViolationSet found_violations = nacl_arm_dec::kNoViolations;
266
267 // Initialize the previous instruction so it always fails validation.
268 DecodedInstruction pred(
269 0, // Virtual address 0, which will be in a different bundle;
270 Instruction(nacl_arm_dec::kFailValidation),
271 decode_state_.fictitious_decoder());
272
273 // Validate each instruction.
274 uint32_t va = segment.begin_addr();
275 while (va < segment.end_addr()) {
276 const ClassDecoder& decoder = decode_state_.decode(segment[va]);
277 DecodedInstruction inst(va, segment[va], decoder);
278 // Note: get_violations is expecting the address of the next instruction
279 // to be validated as its last argument. This address can be updated by
280 // by that routine (as with constant pool heads). Hence, rather than
281 // updating va at the end of the loop, we update it here and pass it
282 // through to get_violations.
283 va += 4;
284 nacl_arm_dec::ViolationSet violations =
285 decoder.get_violations(pred, inst, *this, branches, critical, &va);
286 if (violations) {
287 found_violations =
288 nacl_arm_dec::ViolationUnion(found_violations, violations);
289 if (out == NULL) return found_violations;
290 decoder.generate_diagnostics(violations, pred, inst, *this, out);
291 }
292 pred.Copy(inst);
293 }
294
295 // Validate the last instruction, paired with a nop.
296 const Instruction nop(nacl_arm_dec::kNop);
297 const ClassDecoder& nop_decoder = decode_state_.decode(nop);
298 DecodedInstruction one_past_end(va, nop, nop_decoder);
299 // Note: Like above, we update va to point to the instruction after the nop,
300 // so that it meets the requirements of get_violations.
301 va += 4;
302 nacl_arm_dec::ViolationSet violations =
303 nop_decoder.get_violations(pred, one_past_end, *this,
304 branches, critical, &va);
305 if (violations) {
306 found_violations =
307 nacl_arm_dec::ViolationUnion(found_violations, violations);
308 if (out == NULL) return found_violations;
309 nop_decoder.generate_diagnostics(violations, pred, one_past_end,
310 *this, out);
311 }
312
313 return found_violations;
314 }
315
address_contained(uint32_t va,const vector<CodeSegment> & segs)316 static bool address_contained(uint32_t va, const vector<CodeSegment>& segs) {
317 for (vector<CodeSegment>::const_iterator it = segs.begin(); it != segs.end();
318 ++it) {
319 if (it->contains_address(va)) return true;
320 }
321 return false;
322 }
323
validate_branches(const vector<CodeSegment> & segments,const AddressSet & branches,const AddressSet & critical,ProblemSink * out)324 nacl_arm_dec::ViolationSet SfiValidator::validate_branches(
325 const vector<CodeSegment>& segments,
326 const AddressSet& branches,
327 const AddressSet& critical,
328 ProblemSink* out) {
329 nacl_arm_dec::ViolationSet found_violations = nacl_arm_dec::kNoViolations;
330
331 vector<CodeSegment>::const_iterator seg_it = segments.begin();
332
333 if (segments.size() > 1) {
334 // If there are multiple segments, their relative positioning matters.
335 is_position_independent_ = false;
336 }
337
338 for (AddressSet::Iterator it = branches.begin(); it != branches.end(); ++it) {
339 uint32_t va = *it;
340
341 // Invariant: all addresses in branches are covered by some segment;
342 // segments are in sorted order.
343 while (!seg_it->contains_address(va)) {
344 ++seg_it;
345 }
346
347 const CodeSegment &segment = *seg_it;
348
349 DecodedInstruction inst(va, segment[va],
350 decode_state_.decode(segment[va]));
351
352 // We know it is_relative_branch(), so we can simply call:
353 uint32_t target_va = inst.branch_target();
354 if (address_contained(target_va, segments)) {
355 if (critical.contains(target_va)) {
356 found_violations =
357 nacl_arm_dec::ViolationUnion(
358 found_violations,
359 nacl_arm_dec::ViolationBit(
360 nacl_arm_dec::BRANCH_SPLITS_PATTERN_VIOLATION));
361 if (out == NULL) return found_violations;
362 out->ReportProblemDiagnostic(
363 nacl_arm_dec::BRANCH_SPLITS_PATTERN_VIOLATION,
364 va,
365 "Instruction branches into middle of 2-instruction "
366 "pattern at %08" NACL_PRIx32 ".",
367 target_va);
368 }
369 } else {
370 // If the jump is outside the segment, absolute position matters.
371 is_position_independent_ = false;
372
373 if ((target_va & code_address_mask()) == 0) {
374 // Ensure that relative direct branches which don't go to known
375 // segments are to bundle-aligned targets, and that the branch
376 // doesn't escape from the sandbox. ARM relative direct branches
377 // have a +/-32MiB range, code at the edges of the sandbox could
378 // therefore potentially escape if left unchecked. This implies
379 // that validation is position-dependent, which matters for
380 // validation caching: code segments need to be mapped at the
381 // same addresses as the ones at which they were validated.
382 //
383 // We could make it a sandbox invariant that user code cannot be
384 // mapped within 32MiB of the sandbox's edges (and then only check
385 // bundle alignment with is_bundle_head(target_va)), but this may
386 // break some assumptions in user code.
387 //
388 // We could also track the furthest negative and positive relative
389 // direct branches seen per segment and record that
390 // information. This information would then allow validation
391 // caching to be mostly position independent, as long as code
392 // segments are mapped far enough from the sandbox's edges.
393 //
394 // Branches leaving the segment could be useful for dynamic code
395 // generation as well as to directly branch to the runtime's
396 // trampolines. The IRT curently doesn't do the latter because the
397 // compiler doesn't know that the trampolines will be in range of
398 // relative direct branch immediates. Indirect branches are
399 // instead used and the loader doesn't reoptimize the code.
400 } else {
401 found_violations =
402 nacl_arm_dec::ViolationUnion(
403 found_violations,
404 nacl_arm_dec::ViolationBit(
405 nacl_arm_dec::BRANCH_OUT_OF_RANGE_VIOLATION));
406 if (out == NULL) return found_violations;
407 out->ReportProblemDiagnostic(
408 nacl_arm_dec::BRANCH_OUT_OF_RANGE_VIOLATION,
409 va,
410 "Instruction branches to invalid address %08" NACL_PRIx32 ".",
411 target_va);
412 }
413 }
414 }
415
416 return found_violations;
417 }
418
is_valid_inst_boundary(const CodeSegment & code,uint32_t addr)419 bool SfiValidator::is_valid_inst_boundary(const CodeSegment& code,
420 uint32_t addr) {
421 // Check addr is on an inst boundary.
422 if ((addr & 0x3) != 0)
423 return false;
424
425 CHECK(!ConstructionFailed(NULL));
426
427 uint32_t base = code.begin_addr();
428 uint32_t size = code.end_addr() - base;
429 AddressSet branches(base, size);
430 AddressSet critical(base, size);
431
432 uint32_t bundle_addr = addr & ~(bytes_per_bundle_ - 1);
433 uint32_t offset = bundle_addr - base;
434 uint32_t instr = reinterpret_cast<const uint32_t*>(
435 code.base() + offset)[0];
436
437 // Check if addr falls within a constant pool.
438 if (nacl_arm_dec::IsBreakPointAndConstantPoolHead(instr))
439 return false;
440
441 nacl_arm_dec::ViolationSet violations =
442 validate_fallthrough(code, NULL, &branches, &critical);
443
444 // Function should only be called after the code has already been validated.
445 CHECK(violations == nacl_arm_dec::kNoViolations);
446
447 return !critical.contains(addr);
448 }
449
450 } // namespace nacl_arm_val
451