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 :
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 0 : is_position_independent_(true) {
83 0 : 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 0 : (code_region_bytes_ < bytes_per_bundle_)) {
92 0 : construction_failed_ = true;
93 : }
94 0 : }
95 :
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 0 : is_position_independent_(v.is_position_independent_) {
106 0 : NaClCopyCPUFeaturesArm(&cpu_features_, v.CpuFeatures());
107 0 : }
108 :
109 0 : SfiValidator& SfiValidator::operator=(const SfiValidator& v) {
110 0 : NaClCopyCPUFeaturesArm(&cpu_features_, v.CpuFeatures());
111 0 : bytes_per_bundle_ = v.bytes_per_bundle_;
112 0 : code_region_bytes_ = v.code_region_bytes_;
113 0 : data_region_bytes_ = v.data_region_bytes_;
114 0 : read_only_registers_.Copy(v.read_only_registers_);
115 0 : data_address_registers_.Copy(v.data_address_registers_);
116 0 : construction_failed_ = v.construction_failed_;
117 0 : is_position_independent_ = v.is_position_independent_;
118 0 : return *this;
119 0 : }
120 :
121 : nacl_arm_dec::ViolationSet SfiValidator::
122 : find_violations(const vector<CodeSegment>& segments,
123 0 : ProblemSink* out) {
124 0 : if (ConstructionFailed(out))
125 0 : return nacl_arm_dec::ViolationBit(nacl_arm_dec::OTHER_VIOLATION);
126 :
127 0 : uint32_t base = segments[0].begin_addr();
128 0 : uint32_t size = segments.back().end_addr() - base;
129 0 : AddressSet branches(base, size);
130 0 : AddressSet critical(base, size);
131 :
132 0 : nacl_arm_dec::ViolationSet found_violations = nacl_arm_dec::kNoViolations;
133 :
134 0 : for (vector<CodeSegment>::const_iterator it = segments.begin();
135 0 : it != segments.end(); ++it) {
136 : nacl_arm_dec::ViolationSet segment_violations =
137 0 : validate_fallthrough(*it, out, &branches, &critical);
138 : found_violations =
139 0 : nacl_arm_dec::ViolationUnion(found_violations, segment_violations);
140 0 : if (segment_violations && (out == NULL)) return found_violations;
141 0 : }
142 :
143 : return
144 : nacl_arm_dec::ViolationUnion(
145 : found_violations,
146 0 : validate_branches(segments, branches, critical, out));
147 0 : }
148 :
149 : bool SfiValidator::ValidateSegmentPair(const CodeSegment& old_code,
150 : const CodeSegment& new_code,
151 0 : 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 0 : if (ConstructionFailed(out))
158 0 : return false;
159 :
160 : if ((old_code.begin_addr() != new_code.begin_addr()) ||
161 0 : (old_code.end_addr() != new_code.end_addr())) {
162 0 : return false;
163 : }
164 :
165 0 : bool complete_success = true;
166 0 : 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 0 : NACL_COMPILE_TIME_ASSERT((nacl_arm_dec::kArm32InstSize / CHAR_BIT) == 4);
172 0 : for (uint32_t va = old_code.begin_addr();
173 0 : va != old_code.end_addr();
174 0 : va += nacl_arm_dec::kArm32InstSize / CHAR_BIT) {
175 0 : Instruction old_insn = old_code[va];
176 0 : 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 0 : if (is_bundle_head(va)) {
181 0 : 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 0 : new_insn.Equals(old_insn));
185 : }
186 :
187 : // Accept any change inside a literal pool.
188 0 : if (current_bundle_is_literal_pool)
189 0 : 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 0 : if (new_insn.Equals(old_insn))
195 0 : continue;
196 :
197 : // Decode instructions and get corresponding decoders.
198 0 : const ClassDecoder& old_decoder = decode_state_.decode(old_insn);
199 0 : 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 0 : old_decoder.dynamic_code_replacement_sentinel(old_insn));
205 : Instruction new_sentinel(
206 0 : new_decoder.dynamic_code_replacement_sentinel(new_insn));
207 :
208 : // Report problem if the sentinels differ, and reject the replacement.
209 0 : if (!new_sentinel.Equals(old_sentinel)) {
210 0 : if (out == NULL) return false;
211 : out->ReportProblemDiagnostic(nacl_arm_dec::OTHER_VIOLATION,
212 : va,
213 : "Sentinels at %08" NACL_PRIx32 " differ.",
214 0 : va);
215 0 : complete_success = false;
216 : }
217 0 : }
218 :
219 0 : return complete_success;
220 0 : }
221 :
222 : bool SfiValidator::CopyCode(const CodeSegment& source_code,
223 : CodeSegment& dest_code,
224 : NaClCopyInstructionFunc copy_func,
225 0 : ProblemSink* out) {
226 0 : if (ConstructionFailed(out))
227 0 : return false;
228 :
229 0 : vector<CodeSegment> segments;
230 0 : segments.push_back(source_code);
231 0 : if (!validate(segments, out))
232 0 : 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 0 : for (uintptr_t va = source_code.begin_addr();
237 0 : va != source_code.end_addr();
238 0 : va += nacl_arm_dec::kArm32InstSize / CHAR_BIT) {
239 0 : 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 0 : nacl_arm_dec::kArm32InstSize / CHAR_BIT);
245 0 : }
246 :
247 0 : return true;
248 0 : }
249 :
250 0 : bool SfiValidator::ConstructionFailed(ProblemSink* out) {
251 0 : if (construction_failed_ && (out != NULL)) {
252 0 : uint32_t invalid_addr = ~(uint32_t)0;
253 : out->ReportProblemDiagnostic(nacl_arm_dec::OTHER_VIOLATION,
254 : invalid_addr,
255 0 : "Construction of validator failed!");
256 : }
257 0 : return construction_failed_;
258 0 : }
259 :
260 : nacl_arm_dec::ViolationSet SfiValidator::validate_fallthrough(
261 : const CodeSegment& segment,
262 : ProblemSink* out,
263 : AddressSet* branches,
264 0 : AddressSet* critical) {
265 0 : 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 0 : decode_state_.fictitious_decoder());
272 :
273 : // Validate each instruction.
274 0 : uint32_t va = segment.begin_addr();
275 0 : while (va < segment.end_addr()) {
276 0 : const ClassDecoder& decoder = decode_state_.decode(segment[va]);
277 0 : 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 0 : va += 4;
284 : nacl_arm_dec::ViolationSet violations =
285 0 : decoder.get_violations(pred, inst, *this, branches, critical, &va);
286 0 : if (violations) {
287 : found_violations =
288 0 : nacl_arm_dec::ViolationUnion(found_violations, violations);
289 0 : if (out == NULL) return found_violations;
290 0 : decoder.generate_diagnostics(violations, pred, inst, *this, out);
291 : }
292 0 : pred.Copy(inst);
293 0 : }
294 :
295 : // Validate the last instruction, paired with a nop.
296 0 : const Instruction nop(nacl_arm_dec::kNop);
297 0 : const ClassDecoder& nop_decoder = decode_state_.decode(nop);
298 0 : 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 0 : va += 4;
302 : nacl_arm_dec::ViolationSet violations =
303 : nop_decoder.get_violations(pred, one_past_end, *this,
304 0 : branches, critical, &va);
305 0 : if (violations) {
306 : found_violations =
307 0 : nacl_arm_dec::ViolationUnion(found_violations, violations);
308 0 : if (out == NULL) return found_violations;
309 : nop_decoder.generate_diagnostics(violations, pred, one_past_end,
310 0 : *this, out);
311 : }
312 :
313 0 : return found_violations;
314 0 : }
315 :
316 0 : static bool address_contained(uint32_t va, const vector<CodeSegment>& segs) {
317 0 : for (vector<CodeSegment>::const_iterator it = segs.begin(); it != segs.end();
318 0 : ++it) {
319 0 : if (it->contains_address(va)) return true;
320 0 : }
321 0 : return false;
322 0 : }
323 :
324 : nacl_arm_dec::ViolationSet SfiValidator::validate_branches(
325 : const vector<CodeSegment>& segments,
326 : const AddressSet& branches,
327 : const AddressSet& critical,
328 0 : ProblemSink* out) {
329 0 : nacl_arm_dec::ViolationSet found_violations = nacl_arm_dec::kNoViolations;
330 :
331 0 : vector<CodeSegment>::const_iterator seg_it = segments.begin();
332 :
333 0 : if (segments.size() > 1) {
334 : // If there are multiple segments, their relative positioning matters.
335 0 : is_position_independent_ = false;
336 : }
337 :
338 0 : for (AddressSet::Iterator it = branches.begin(); it != branches.end(); ++it) {
339 0 : uint32_t va = *it;
340 :
341 : // Invariant: all addresses in branches are covered by some segment;
342 : // segments are in sorted order.
343 0 : while (!seg_it->contains_address(va)) {
344 0 : ++seg_it;
345 0 : }
346 :
347 0 : const CodeSegment &segment = *seg_it;
348 :
349 : DecodedInstruction inst(va, segment[va],
350 0 : decode_state_.decode(segment[va]));
351 :
352 : // We know it is_relative_branch(), so we can simply call:
353 0 : uint32_t target_va = inst.branch_target();
354 0 : if (address_contained(target_va, segments)) {
355 0 : if (critical.contains(target_va)) {
356 : found_violations =
357 : nacl_arm_dec::ViolationUnion(
358 : found_violations,
359 : nacl_arm_dec::ViolationBit(
360 0 : nacl_arm_dec::BRANCH_SPLITS_PATTERN_VIOLATION));
361 0 : 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 0 : target_va);
368 : }
369 0 : } else {
370 : // If the jump is outside the segment, absolute position matters.
371 0 : is_position_independent_ = false;
372 :
373 0 : 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 0 : } else {
401 : found_violations =
402 : nacl_arm_dec::ViolationUnion(
403 : found_violations,
404 : nacl_arm_dec::ViolationBit(
405 0 : nacl_arm_dec::BRANCH_OUT_OF_RANGE_VIOLATION));
406 0 : 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 0 : target_va);
412 : }
413 : }
414 0 : }
415 :
416 0 : return found_violations;
417 0 : }
418 :
419 : } // namespace nacl_arm_val
|
