1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "flow_analysis.h"
18 
19 #include "dex/bytecode_utils.h"
20 #include "dex/class_accessor-inl.h"
21 #include "dex/code_item_accessors-inl.h"
22 #include "dex/dex_instruction-inl.h"
23 #include "dex/dex_file-inl.h"
24 #include "dex/dex_file_exception_helpers.h"
25 #include "resolver.h"
26 #include "veridex.h"
27 
28 namespace art {
29 
VeriFlowAnalysis(VeridexResolver * resolver,const ClassAccessor::Method & method)30 VeriFlowAnalysis::VeriFlowAnalysis(VeridexResolver* resolver,
31                                    const ClassAccessor::Method& method)
32     : resolver_(resolver),
33       method_id_(method.GetIndex()),
34       code_item_accessor_(method.GetInstructionsAndData()),
35       dex_registers_(code_item_accessor_.InsnsSizeInCodeUnits()),
36       instruction_infos_(code_item_accessor_.InsnsSizeInCodeUnits()) {}
37 
SetAsBranchTarget(uint32_t dex_pc)38 void VeriFlowAnalysis::SetAsBranchTarget(uint32_t dex_pc) {
39   if (dex_registers_[dex_pc] == nullptr) {
40     dex_registers_[dex_pc].reset(
41         new std::vector<RegisterValue>(code_item_accessor_.RegistersSize()));
42   }
43 }
44 
IsBranchTarget(uint32_t dex_pc)45 bool VeriFlowAnalysis::IsBranchTarget(uint32_t dex_pc) {
46   return dex_registers_[dex_pc] != nullptr;
47 }
48 
MergeRegisterValues(uint32_t dex_pc)49 bool VeriFlowAnalysis::MergeRegisterValues(uint32_t dex_pc) {
50   // TODO: Do the merging. Right now, just return that we should continue
51   // the iteration if the instruction has not been visited.
52   if (!instruction_infos_[dex_pc].has_been_visited) {
53     dex_registers_[dex_pc]->assign(current_registers_.begin(), current_registers_.end());
54     return true;
55   }
56   return false;
57 }
58 
SetVisited(uint32_t dex_pc)59 void VeriFlowAnalysis::SetVisited(uint32_t dex_pc) {
60   instruction_infos_[dex_pc].has_been_visited = true;
61 }
62 
FindBranches()63 void VeriFlowAnalysis::FindBranches() {
64   SetAsBranchTarget(0);
65 
66   if (code_item_accessor_.TriesSize() != 0) {
67     // TODO: We need to mark the range of dex pcs as flowing in the handlers.
68     /*
69     for (const DexFile::TryItem& try_item : code_item_accessor_.TryItems()) {
70       uint32_t dex_pc_start = try_item.start_addr_;
71       uint32_t dex_pc_end = dex_pc_start + try_item.insn_count_;
72     }
73     */
74 
75     // Create branch targets for exception handlers.
76     const uint8_t* handlers_ptr = code_item_accessor_.GetCatchHandlerData();
77     uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr);
78     for (uint32_t idx = 0; idx < handlers_size; ++idx) {
79       CatchHandlerIterator iterator(handlers_ptr);
80       for (; iterator.HasNext(); iterator.Next()) {
81         SetAsBranchTarget(iterator.GetHandlerAddress());
82       }
83       handlers_ptr = iterator.EndDataPointer();
84     }
85   }
86 
87   // Iterate over all instructions and find branching instructions.
88   for (const DexInstructionPcPair& pair : code_item_accessor_) {
89     const uint32_t dex_pc = pair.DexPc();
90     const Instruction& instruction = pair.Inst();
91 
92     if (instruction.IsBranch()) {
93       SetAsBranchTarget(dex_pc + instruction.GetTargetOffset());
94     } else if (instruction.IsSwitch()) {
95       DexSwitchTable table(instruction, dex_pc);
96       for (DexSwitchTableIterator s_it(table); !s_it.Done(); s_it.Advance()) {
97         SetAsBranchTarget(dex_pc + s_it.CurrentTargetOffset());
98         if (table.ShouldBuildDecisionTree() && !s_it.IsLast()) {
99           SetAsBranchTarget(s_it.GetDexPcForCurrentIndex());
100         }
101       }
102     }
103   }
104 }
105 
UpdateRegister(uint32_t dex_register,RegisterSource kind,VeriClass * cls,uint32_t source_id)106 void VeriFlowAnalysis::UpdateRegister(uint32_t dex_register,
107                                       RegisterSource kind,
108                                       VeriClass* cls,
109                                       uint32_t source_id) {
110   current_registers_[dex_register] = RegisterValue(
111       kind, DexFileReference(&resolver_->GetDexFile(), source_id), cls);
112 }
113 
UpdateRegister(uint32_t dex_register,const RegisterValue & value)114 void VeriFlowAnalysis::UpdateRegister(uint32_t dex_register, const RegisterValue& value) {
115   current_registers_[dex_register] = value;
116 }
117 
UpdateRegister(uint32_t dex_register,const VeriClass * cls)118 void VeriFlowAnalysis::UpdateRegister(uint32_t dex_register, const VeriClass* cls) {
119   current_registers_[dex_register] =
120       RegisterValue(RegisterSource::kNone, DexFileReference(nullptr, 0), cls);
121 }
122 
UpdateRegister(uint32_t dex_register,int32_t value,const VeriClass * cls)123 void VeriFlowAnalysis::UpdateRegister(uint32_t dex_register, int32_t value, const VeriClass* cls) {
124   current_registers_[dex_register] =
125       RegisterValue(RegisterSource::kConstant, value, DexFileReference(nullptr, 0), cls);
126 }
127 
GetRegister(uint32_t dex_register) const128 const RegisterValue& VeriFlowAnalysis::GetRegister(uint32_t dex_register) const {
129   return current_registers_[dex_register];
130 }
131 
GetReturnType(uint32_t method_index)132 RegisterValue VeriFlowAnalysis::GetReturnType(uint32_t method_index) {
133   const DexFile& dex_file = resolver_->GetDexFile();
134   const dex::MethodId& method_id = dex_file.GetMethodId(method_index);
135   const dex::ProtoId& proto_id = dex_file.GetMethodPrototype(method_id);
136   VeriClass* cls = resolver_->GetVeriClass(proto_id.return_type_idx_);
137   return RegisterValue(RegisterSource::kMethod, DexFileReference(&dex_file, method_index), cls);
138 }
139 
GetFieldType(uint32_t field_index)140 RegisterValue VeriFlowAnalysis::GetFieldType(uint32_t field_index) {
141   const DexFile& dex_file = resolver_->GetDexFile();
142   const dex::FieldId& field_id = dex_file.GetFieldId(field_index);
143   VeriClass* cls = resolver_->GetVeriClass(field_id.type_idx_);
144   return RegisterValue(RegisterSource::kField, DexFileReference(&dex_file, field_index), cls);
145 }
146 
GetBranchFlags(const Instruction & instruction) const147 int VeriFlowAnalysis::GetBranchFlags(const Instruction& instruction) const {
148   switch (instruction.Opcode()) {
149     #define IF_XX(cond, op) \
150     case Instruction::IF_##cond: { \
151       RegisterValue lhs = GetRegister(instruction.VRegA()); \
152       RegisterValue rhs = GetRegister(instruction.VRegB()); \
153       if (lhs.IsConstant() && rhs.IsConstant()) { \
154         if (lhs.GetConstant() op rhs.GetConstant()) { \
155           return Instruction::kBranch; \
156         } else { \
157           return Instruction::kContinue; \
158         } \
159       } \
160       break; \
161     } \
162     case Instruction::IF_##cond##Z: { \
163       RegisterValue val = GetRegister(instruction.VRegA()); \
164       if (val.IsConstant()) { \
165         if (val.GetConstant() op 0) {  /* NOLINT */ \
166           return Instruction::kBranch; \
167         } else { \
168           return Instruction::kContinue; \
169         } \
170       } \
171       break; \
172     }
173 
174     IF_XX(EQ, ==);
175     IF_XX(NE, !=);
176     IF_XX(LT, <);
177     IF_XX(LE, <=);
178     IF_XX(GT, >);
179     IF_XX(GE, >=);
180 
181     #undef IF_XX
182 
183     default:
184       break;
185   }
186 
187   return Instruction::FlagsOf(instruction.Opcode());
188 }
189 
AnalyzeCode()190 void VeriFlowAnalysis::AnalyzeCode() {
191   std::vector<uint32_t> work_list;
192   work_list.push_back(0);
193   // Iterate over the code.
194   // When visiting unconditional branches (goto), move to that instruction.
195   // When visiting conditional branches, move to one destination, and put the other
196   // in the worklist.
197   while (!work_list.empty()) {
198     uint32_t dex_pc = work_list.back();
199     work_list.pop_back();
200     CHECK(IsBranchTarget(dex_pc));
201     current_registers_ = *dex_registers_[dex_pc].get();
202     while (true) {
203       const uint16_t* insns = code_item_accessor_.Insns() + dex_pc;
204       const Instruction& inst = *Instruction::At(insns);
205       ProcessDexInstruction(inst);
206       SetVisited(dex_pc);
207 
208       int branch_flags = GetBranchFlags(inst);
209 
210       if ((branch_flags & Instruction::kContinue) != 0) {
211         if ((branch_flags & Instruction::kBranch) != 0) {
212           uint32_t branch_dex_pc = dex_pc + inst.GetTargetOffset();
213           if (MergeRegisterValues(branch_dex_pc)) {
214             work_list.push_back(branch_dex_pc);
215           }
216         }
217         dex_pc += inst.SizeInCodeUnits();
218       } else if ((branch_flags & Instruction::kBranch) != 0) {
219         dex_pc += inst.GetTargetOffset();
220         DCHECK(IsBranchTarget(dex_pc));
221       } else {
222         break;
223       }
224 
225       if (IsBranchTarget(dex_pc)) {
226         if (MergeRegisterValues(dex_pc)) {
227           current_registers_ = *dex_registers_[dex_pc].get();
228         } else {
229           break;
230         }
231       }
232     }
233   }
234 }
235 
ProcessDexInstruction(const Instruction & instruction)236 void VeriFlowAnalysis::ProcessDexInstruction(const Instruction& instruction) {
237   switch (instruction.Opcode()) {
238     case Instruction::CONST_4: {
239       int32_t register_index = instruction.VRegA();
240       int32_t value = instruction.VRegB_11n();
241       UpdateRegister(register_index, value, VeriClass::integer_);
242       break;
243     }
244     case Instruction::CONST_16: {
245       int32_t register_index = instruction.VRegA();
246       int32_t value = instruction.VRegB_21s();
247       UpdateRegister(register_index, value, VeriClass::integer_);
248       break;
249     }
250 
251     case Instruction::CONST: {
252       int32_t register_index = instruction.VRegA();
253       int32_t value = instruction.VRegB_31i();
254       UpdateRegister(register_index, value, VeriClass::integer_);
255       break;
256     }
257 
258     case Instruction::CONST_HIGH16: {
259       int32_t register_index = instruction.VRegA();
260       int32_t value = instruction.VRegB_21h();
261       UpdateRegister(register_index, value, VeriClass::integer_);
262       break;
263     }
264 
265     case Instruction::CONST_WIDE_16:
266     case Instruction::CONST_WIDE_32:
267     case Instruction::CONST_WIDE:
268     case Instruction::CONST_WIDE_HIGH16: {
269       int32_t register_index = instruction.VRegA();
270       UpdateRegister(register_index, VeriClass::long_);
271       break;
272     }
273 
274     case Instruction::MOVE:
275     case Instruction::MOVE_FROM16:
276     case Instruction::MOVE_16: {
277       UpdateRegister(instruction.VRegA(), GetRegister(instruction.VRegB()));
278       break;
279     }
280 
281     case Instruction::MOVE_WIDE:
282     case Instruction::MOVE_WIDE_FROM16:
283     case Instruction::MOVE_WIDE_16: {
284       UpdateRegister(instruction.VRegA(), GetRegister(instruction.VRegB()));
285       break;
286     }
287 
288     case Instruction::MOVE_OBJECT:
289     case Instruction::MOVE_OBJECT_16:
290     case Instruction::MOVE_OBJECT_FROM16: {
291       UpdateRegister(instruction.VRegA(), GetRegister(instruction.VRegB()));
292       break;
293     }
294     case Instruction::CONST_CLASS: {
295       UpdateRegister(instruction.VRegA_21c(),
296                      RegisterSource::kClass,
297                      VeriClass::class_,
298                      instruction.VRegB_21c());
299       break;
300     }
301     case Instruction::CONST_STRING: {
302       UpdateRegister(instruction.VRegA_21c(),
303                      RegisterSource::kString,
304                      VeriClass::string_,
305                      instruction.VRegB_21c());
306       break;
307     }
308 
309     case Instruction::CONST_STRING_JUMBO: {
310       UpdateRegister(instruction.VRegA_31c(),
311                      RegisterSource::kString,
312                      VeriClass::string_,
313                      instruction.VRegB_31c());
314       break;
315     }
316     case Instruction::INVOKE_DIRECT:
317     case Instruction::INVOKE_INTERFACE:
318     case Instruction::INVOKE_STATIC:
319     case Instruction::INVOKE_SUPER:
320     case Instruction::INVOKE_VIRTUAL: {
321       last_result_ = AnalyzeInvoke(instruction, /* is_range= */ false);
322       break;
323     }
324 
325     case Instruction::INVOKE_DIRECT_RANGE:
326     case Instruction::INVOKE_INTERFACE_RANGE:
327     case Instruction::INVOKE_STATIC_RANGE:
328     case Instruction::INVOKE_SUPER_RANGE:
329     case Instruction::INVOKE_VIRTUAL_RANGE: {
330       last_result_ = AnalyzeInvoke(instruction, /* is_range= */ true);
331       break;
332     }
333 
334     case Instruction::MOVE_RESULT:
335     case Instruction::MOVE_RESULT_WIDE:
336     case Instruction::MOVE_RESULT_OBJECT: {
337       UpdateRegister(instruction.VRegA(), last_result_);
338       break;
339     }
340     case Instruction::RETURN_VOID:
341     case Instruction::RETURN_OBJECT:
342     case Instruction::RETURN_WIDE:
343     case Instruction::RETURN: {
344       break;
345     }
346 
347     // If operations will be handled when looking at the control flow.
348     #define IF_XX(cond) \
349     case Instruction::IF_##cond: break; \
350     case Instruction::IF_##cond##Z: break
351 
352     IF_XX(EQ);
353     IF_XX(NE);
354     IF_XX(LT);
355     IF_XX(LE);
356     IF_XX(GT);
357     IF_XX(GE);
358 
359     #undef IF_XX
360 
361     case Instruction::GOTO:
362     case Instruction::GOTO_16:
363     case Instruction::GOTO_32: {
364       break;
365     }
366     case Instruction::INVOKE_POLYMORPHIC: {
367       // TODO
368       break;
369     }
370 
371     case Instruction::INVOKE_POLYMORPHIC_RANGE: {
372       // TODO
373       break;
374     }
375 
376     case Instruction::NEG_INT:
377     case Instruction::NEG_LONG:
378     case Instruction::NEG_FLOAT:
379     case Instruction::NEG_DOUBLE:
380     case Instruction::NOT_INT:
381     case Instruction::NOT_LONG: {
382       UpdateRegister(instruction.VRegA(), VeriClass::integer_);
383       break;
384     }
385 
386     case Instruction::INT_TO_LONG:
387     case Instruction::INT_TO_FLOAT:
388     case Instruction::INT_TO_DOUBLE:
389     case Instruction::LONG_TO_INT:
390     case Instruction::LONG_TO_FLOAT:
391     case Instruction::LONG_TO_DOUBLE:
392     case Instruction::FLOAT_TO_INT:
393     case Instruction::FLOAT_TO_LONG:
394     case Instruction::FLOAT_TO_DOUBLE:
395     case Instruction::DOUBLE_TO_INT:
396     case Instruction::DOUBLE_TO_LONG:
397     case Instruction::DOUBLE_TO_FLOAT:
398     case Instruction::INT_TO_BYTE:
399     case Instruction::INT_TO_SHORT:
400     case Instruction::INT_TO_CHAR: {
401       UpdateRegister(instruction.VRegA(), VeriClass::integer_);
402       break;
403     }
404 
405     case Instruction::ADD_INT:
406     case Instruction::ADD_LONG:
407     case Instruction::ADD_DOUBLE:
408     case Instruction::ADD_FLOAT:
409     case Instruction::SUB_INT:
410     case Instruction::SUB_LONG:
411     case Instruction::SUB_FLOAT:
412     case Instruction::SUB_DOUBLE:
413     case Instruction::MUL_INT:
414     case Instruction::MUL_LONG:
415     case Instruction::MUL_FLOAT:
416     case Instruction::MUL_DOUBLE:
417     case Instruction::DIV_INT:
418     case Instruction::DIV_LONG:
419     case Instruction::DIV_FLOAT:
420     case Instruction::DIV_DOUBLE:
421     case Instruction::REM_INT:
422     case Instruction::REM_LONG:
423     case Instruction::REM_FLOAT:
424     case Instruction::REM_DOUBLE:
425     case Instruction::AND_INT:
426     case Instruction::AND_LONG:
427     case Instruction::SHL_INT:
428     case Instruction::SHL_LONG:
429     case Instruction::SHR_INT:
430     case Instruction::SHR_LONG:
431     case Instruction::USHR_INT:
432     case Instruction::USHR_LONG:
433     case Instruction::OR_INT:
434     case Instruction::OR_LONG:
435     case Instruction::XOR_INT:
436     case Instruction::XOR_LONG: {
437       UpdateRegister(instruction.VRegA(), VeriClass::integer_);
438       break;
439     }
440 
441     case Instruction::ADD_INT_2ADDR:
442     case Instruction::ADD_LONG_2ADDR:
443     case Instruction::ADD_DOUBLE_2ADDR:
444     case Instruction::ADD_FLOAT_2ADDR:
445     case Instruction::SUB_INT_2ADDR:
446     case Instruction::SUB_LONG_2ADDR:
447     case Instruction::SUB_FLOAT_2ADDR:
448     case Instruction::SUB_DOUBLE_2ADDR:
449     case Instruction::MUL_INT_2ADDR:
450     case Instruction::MUL_LONG_2ADDR:
451     case Instruction::MUL_FLOAT_2ADDR:
452     case Instruction::MUL_DOUBLE_2ADDR:
453     case Instruction::DIV_INT_2ADDR:
454     case Instruction::DIV_LONG_2ADDR:
455     case Instruction::REM_INT_2ADDR:
456     case Instruction::REM_LONG_2ADDR:
457     case Instruction::REM_FLOAT_2ADDR:
458     case Instruction::REM_DOUBLE_2ADDR:
459     case Instruction::SHL_INT_2ADDR:
460     case Instruction::SHL_LONG_2ADDR:
461     case Instruction::SHR_INT_2ADDR:
462     case Instruction::SHR_LONG_2ADDR:
463     case Instruction::USHR_INT_2ADDR:
464     case Instruction::USHR_LONG_2ADDR:
465     case Instruction::DIV_FLOAT_2ADDR:
466     case Instruction::DIV_DOUBLE_2ADDR:
467     case Instruction::AND_INT_2ADDR:
468     case Instruction::AND_LONG_2ADDR:
469     case Instruction::OR_INT_2ADDR:
470     case Instruction::OR_LONG_2ADDR:
471     case Instruction::XOR_INT_2ADDR:
472     case Instruction::XOR_LONG_2ADDR: {
473       UpdateRegister(instruction.VRegA(), VeriClass::integer_);
474       break;
475     }
476 
477     case Instruction::ADD_INT_LIT16:
478     case Instruction::AND_INT_LIT16:
479     case Instruction::OR_INT_LIT16:
480     case Instruction::XOR_INT_LIT16:
481     case Instruction::RSUB_INT:
482     case Instruction::MUL_INT_LIT16:
483     case Instruction::DIV_INT_LIT16:
484     case Instruction::REM_INT_LIT16: {
485       UpdateRegister(instruction.VRegA(), VeriClass::integer_);
486       break;
487     }
488 
489     case Instruction::ADD_INT_LIT8:
490     case Instruction::AND_INT_LIT8:
491     case Instruction::OR_INT_LIT8:
492     case Instruction::XOR_INT_LIT8:
493     case Instruction::RSUB_INT_LIT8:
494     case Instruction::MUL_INT_LIT8:
495     case Instruction::DIV_INT_LIT8:
496     case Instruction::REM_INT_LIT8:
497     case Instruction::SHL_INT_LIT8:
498     case Instruction::SHR_INT_LIT8:
499     case Instruction::USHR_INT_LIT8: {
500       UpdateRegister(instruction.VRegA(), VeriClass::integer_);
501       break;
502     }
503 
504     case Instruction::NEW_INSTANCE: {
505       VeriClass* cls = resolver_->GetVeriClass(dex::TypeIndex(instruction.VRegB_21c()));
506       UpdateRegister(instruction.VRegA(), cls);
507       break;
508     }
509 
510     case Instruction::NEW_ARRAY: {
511       dex::TypeIndex type_index(instruction.VRegC_22c());
512       VeriClass* cls = resolver_->GetVeriClass(type_index);
513       UpdateRegister(instruction.VRegA_22c(), cls);
514       break;
515     }
516 
517     case Instruction::FILLED_NEW_ARRAY: {
518       dex::TypeIndex type_index(instruction.VRegB_35c());
519       VeriClass* cls = resolver_->GetVeriClass(type_index);
520       UpdateRegister(instruction.VRegA_22c(), cls);
521       break;
522     }
523 
524     case Instruction::FILLED_NEW_ARRAY_RANGE: {
525       dex::TypeIndex type_index(instruction.VRegB_3rc());
526       uint32_t register_index = instruction.VRegC_3rc();
527       VeriClass* cls = resolver_->GetVeriClass(type_index);
528       UpdateRegister(register_index, cls);
529       break;
530     }
531 
532     case Instruction::FILL_ARRAY_DATA: {
533       break;
534     }
535 
536     case Instruction::CMP_LONG:
537     case Instruction::CMPG_FLOAT:
538     case Instruction::CMPG_DOUBLE:
539     case Instruction::CMPL_FLOAT:
540     case Instruction::CMPL_DOUBLE: {
541       UpdateRegister(instruction.VRegA(), VeriClass::integer_);
542       break;
543     }
544 
545     case Instruction::NOP:
546       break;
547 
548     case Instruction::IGET:
549     case Instruction::IGET_WIDE:
550     case Instruction::IGET_OBJECT:
551     case Instruction::IGET_BOOLEAN:
552     case Instruction::IGET_BYTE:
553     case Instruction::IGET_CHAR:
554     case Instruction::IGET_SHORT: {
555       UpdateRegister(instruction.VRegA_22c(), GetFieldType(instruction.VRegC_22c()));
556       break;
557     }
558 
559     case Instruction::IPUT:
560     case Instruction::IPUT_WIDE:
561     case Instruction::IPUT_OBJECT:
562     case Instruction::IPUT_BOOLEAN:
563     case Instruction::IPUT_BYTE:
564     case Instruction::IPUT_CHAR:
565     case Instruction::IPUT_SHORT: {
566       AnalyzeFieldSet(instruction);
567       break;
568     }
569 
570     case Instruction::SGET:
571     case Instruction::SGET_WIDE:
572     case Instruction::SGET_OBJECT:
573     case Instruction::SGET_BOOLEAN:
574     case Instruction::SGET_BYTE:
575     case Instruction::SGET_CHAR:
576     case Instruction::SGET_SHORT: {
577       uint32_t dest_reg = instruction.VRegA_21c();
578       uint16_t field_index = instruction.VRegB_21c();
579       if (VeriClass::sdkInt_ != nullptr && resolver_->GetField(field_index) == VeriClass::sdkInt_) {
580         UpdateRegister(dest_reg, gTargetSdkVersion, VeriClass::integer_);
581       } else {
582         UpdateRegister(dest_reg, GetFieldType(instruction.VRegC_22c()));
583       }
584       break;
585     }
586 
587     case Instruction::SPUT:
588     case Instruction::SPUT_WIDE:
589     case Instruction::SPUT_OBJECT:
590     case Instruction::SPUT_BOOLEAN:
591     case Instruction::SPUT_BYTE:
592     case Instruction::SPUT_CHAR:
593     case Instruction::SPUT_SHORT: {
594       AnalyzeFieldSet(instruction);
595       break;
596     }
597 
598 #define ARRAY_XX(kind, anticipated_type)                                          \
599     case Instruction::AGET##kind: {                                               \
600       UpdateRegister(instruction.VRegA_23x(), anticipated_type);                  \
601       break;                                                                      \
602     }                                                                             \
603     case Instruction::APUT##kind: {                                               \
604       break;                                                                      \
605     }
606 
607     ARRAY_XX(, VeriClass::integer_);
608     ARRAY_XX(_WIDE, VeriClass::long_);
609     ARRAY_XX(_BOOLEAN, VeriClass::boolean_);
610     ARRAY_XX(_BYTE, VeriClass::byte_);
611     ARRAY_XX(_CHAR, VeriClass::char_);
612     ARRAY_XX(_SHORT, VeriClass::short_);
613 
614     case Instruction::AGET_OBJECT: {
615       // TODO: take the component type.
616       UpdateRegister(instruction.VRegA_23x(), VeriClass::object_);
617       break;
618     }
619 
620     case Instruction::APUT_OBJECT: {
621       break;
622     }
623 
624     case Instruction::ARRAY_LENGTH: {
625       UpdateRegister(instruction.VRegA_12x(), VeriClass::integer_);
626       break;
627     }
628 
629     case Instruction::MOVE_EXCEPTION: {
630       UpdateRegister(instruction.VRegA_11x(), VeriClass::throwable_);
631       break;
632     }
633 
634     case Instruction::THROW: {
635       break;
636     }
637 
638     case Instruction::INSTANCE_OF: {
639       uint8_t destination = instruction.VRegA_22c();
640       UpdateRegister(destination, VeriClass::boolean_);
641       break;
642     }
643 
644     case Instruction::CHECK_CAST: {
645       uint8_t reference = instruction.VRegA_21c();
646       dex::TypeIndex type_index(instruction.VRegB_21c());
647       UpdateRegister(reference, resolver_->GetVeriClass(type_index));
648       break;
649     }
650 
651     case Instruction::MONITOR_ENTER:
652     case Instruction::MONITOR_EXIT: {
653       break;
654     }
655 
656     case Instruction::SPARSE_SWITCH:
657     case Instruction::PACKED_SWITCH:
658       break;
659 
660     default:
661       break;
662   }
663 }
664 
Run()665 void VeriFlowAnalysis::Run() {
666   FindBranches();
667   uint32_t number_of_registers = code_item_accessor_.RegistersSize();
668   uint32_t number_of_parameters = code_item_accessor_.InsSize();
669   std::vector<RegisterValue>& initial_values = *dex_registers_[0].get();
670   for (uint32_t i = 0; i < number_of_parameters; ++i) {
671     initial_values[number_of_registers - number_of_parameters + i] = RegisterValue(
672       RegisterSource::kParameter,
673       i,
674       DexFileReference(&resolver_->GetDexFile(), method_id_),
675       nullptr);
676   }
677   AnalyzeCode();
678 }
679 
GetParameterAt(const Instruction & instruction,bool is_range,uint32_t * args,uint32_t index)680 static uint32_t GetParameterAt(const Instruction& instruction,
681                                bool is_range,
682                                uint32_t* args,
683                                uint32_t index) {
684   return is_range ? instruction.VRegC() + index : args[index];
685 }
686 
AnalyzeInvoke(const Instruction & instruction,bool is_range)687 RegisterValue FlowAnalysisCollector::AnalyzeInvoke(const Instruction& instruction, bool is_range) {
688   uint32_t id = is_range ? instruction.VRegB_3rc() : instruction.VRegB_35c();
689   VeriMethod method = resolver_->GetMethod(id);
690   uint32_t args[5];
691   if (!is_range) {
692     instruction.GetVarArgs(args);
693   }
694 
695   if (method == VeriClass::forName_) {
696     // Class.forName. Fetch the first parameter.
697     RegisterValue value = GetRegister(GetParameterAt(instruction, is_range, args, 0));
698     return RegisterValue(
699         value.GetSource(), value.GetDexFileReference(), VeriClass::class_);
700   } else if (IsGetField(method)) {
701     // Class.getField or Class.getDeclaredField. Fetch the first parameter for the class, and the
702     // second parameter for the field name.
703     RegisterValue cls = GetRegister(GetParameterAt(instruction, is_range, args, 0));
704     RegisterValue name = GetRegister(GetParameterAt(instruction, is_range, args, 1));
705     uses_.push_back(ReflectAccessInfo(cls, name, /* is_method= */ false));
706     return GetReturnType(id);
707   } else if (IsGetMethod(method)) {
708     // Class.getMethod or Class.getDeclaredMethod. Fetch the first parameter for the class, and the
709     // second parameter for the field name.
710     RegisterValue cls = GetRegister(GetParameterAt(instruction, is_range, args, 0));
711     RegisterValue name = GetRegister(GetParameterAt(instruction, is_range, args, 1));
712     uses_.push_back(ReflectAccessInfo(cls, name, /* is_method= */ true));
713     return GetReturnType(id);
714   } else if (method == VeriClass::getClass_) {
715     // Get the type of the first parameter.
716     RegisterValue obj = GetRegister(GetParameterAt(instruction, is_range, args, 0));
717     const VeriClass* cls = obj.GetType();
718     if (cls != nullptr && cls->GetClassDef() != nullptr) {
719       const dex::ClassDef* def = cls->GetClassDef();
720       return RegisterValue(
721           RegisterSource::kClass,
722           DexFileReference(&resolver_->GetDexFileOf(*cls), def->class_idx_.index_),
723           VeriClass::class_);
724     } else {
725       return RegisterValue(
726           obj.GetSource(), obj.GetDexFileReference(), VeriClass::class_);
727     }
728   } else if (method == VeriClass::loadClass_) {
729     // ClassLoader.loadClass. Fetch the first parameter.
730     RegisterValue value = GetRegister(GetParameterAt(instruction, is_range, args, 1));
731     return RegisterValue(
732         value.GetSource(), value.GetDexFileReference(), VeriClass::class_);
733   } else {
734     // Return a RegisterValue referencing the method whose type is the return type
735     // of the method.
736     return GetReturnType(id);
737   }
738 }
739 
AnalyzeFieldSet(const Instruction & instruction ATTRIBUTE_UNUSED)740 void FlowAnalysisCollector::AnalyzeFieldSet(const Instruction& instruction ATTRIBUTE_UNUSED) {
741   // There are no fields that escape reflection uses.
742 }
743 
AnalyzeInvoke(const Instruction & instruction,bool is_range)744 RegisterValue FlowAnalysisSubstitutor::AnalyzeInvoke(const Instruction& instruction,
745                                                      bool is_range) {
746   uint32_t id = is_range ? instruction.VRegB_3rc() : instruction.VRegB_35c();
747   MethodReference method(&resolver_->GetDexFile(), id);
748   // TODO: doesn't work for multidex
749   // TODO: doesn't work for overriding (but maybe should be done at a higher level);
750   auto method_accesses_it = accesses_.find(method);
751   if (method_accesses_it == accesses_.end()) {
752     return GetReturnType(id);
753   }
754   uint32_t args[5];
755   if (!is_range) {
756     instruction.GetVarArgs(args);
757   }
758   for (const ReflectAccessInfo& info : method_accesses_it->second) {
759     if (info.cls.IsParameter() || info.name.IsParameter()) {
760       RegisterValue cls = info.cls.IsParameter()
761           ? GetRegister(GetParameterAt(instruction, is_range, args, info.cls.GetParameterIndex()))
762           : info.cls;
763       RegisterValue name = info.name.IsParameter()
764           ? GetRegister(GetParameterAt(instruction, is_range, args, info.name.GetParameterIndex()))
765           : info.name;
766       uses_.push_back(ReflectAccessInfo(cls, name, info.is_method));
767     }
768   }
769   return GetReturnType(id);
770 }
771 
AnalyzeFieldSet(const Instruction & instruction ATTRIBUTE_UNUSED)772 void FlowAnalysisSubstitutor::AnalyzeFieldSet(const Instruction& instruction ATTRIBUTE_UNUSED) {
773   // TODO: analyze field sets.
774 }
775 
776 }  // namespace art
777