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 #ifndef ART_TOOLS_VERIDEX_FLOW_ANALYSIS_H_
18 #define ART_TOOLS_VERIDEX_FLOW_ANALYSIS_H_
19 
20 #include "dex/code_item_accessors.h"
21 #include "dex/dex_file_reference.h"
22 #include "dex/method_reference.h"
23 #include "hidden_api.h"
24 #include "resolver.h"
25 #include "veridex.h"
26 
27 namespace art {
28 
29 /**
30  * The source where a dex register comes from.
31  */
32 enum class RegisterSource {
33   kParameter,
34   kField,
35   kMethod,
36   kClass,
37   kString,
38   kConstant,
39   kNone
40 };
41 
42 /**
43  * Abstract representation of a dex register value.
44  */
45 class RegisterValue {
46  public:
RegisterValue()47   RegisterValue() : source_(RegisterSource::kNone),
48                     value_(0),
49                     reference_(nullptr, 0),
50                     type_(nullptr) {}
RegisterValue(RegisterSource source,DexFileReference reference,const VeriClass * type)51   RegisterValue(RegisterSource source, DexFileReference reference, const VeriClass* type)
52       : source_(source), value_(0), reference_(reference), type_(type) {}
53 
RegisterValue(RegisterSource source,uint32_t value,DexFileReference reference,const VeriClass * type)54   RegisterValue(RegisterSource source,
55                 uint32_t value,
56                 DexFileReference reference,
57                 const VeriClass* type)
58       : source_(source), value_(value), reference_(reference), type_(type) {}
59 
GetSource()60   RegisterSource GetSource() const { return source_; }
GetDexFileReference()61   DexFileReference GetDexFileReference() const { return reference_; }
GetType()62   const VeriClass* GetType() const { return type_; }
GetParameterIndex()63   uint32_t GetParameterIndex() const {
64     CHECK(IsParameter());
65     return value_;
66   }
GetConstant()67   uint32_t GetConstant() const {
68     CHECK(IsConstant());
69     return value_;
70   }
IsParameter()71   bool IsParameter() const { return source_ == RegisterSource::kParameter; }
IsClass()72   bool IsClass() const { return source_ == RegisterSource::kClass; }
IsString()73   bool IsString() const { return source_ == RegisterSource::kString; }
IsConstant()74   bool IsConstant() const { return source_ == RegisterSource::kConstant; }
75 
ToString()76   std::string ToString() const {
77     switch (source_) {
78       case RegisterSource::kString: {
79         const char* str = reference_.dex_file->StringDataByIdx(dex::StringIndex(reference_.index));
80         if (type_ == VeriClass::class_) {
81           // Class names at the Java level are of the form x.y.z, but the list encodes
82           // them of the form Lx/y/z;. Inner classes have '$' for both Java level class
83           // names in strings, and hidden API lists.
84           return HiddenApi::ToInternalName(str);
85         } else {
86           return str;
87         }
88       }
89       case RegisterSource::kClass:
90         return reference_.dex_file->StringByTypeIdx(dex::TypeIndex(reference_.index));
91       case RegisterSource::kParameter:
92         return std::string("Parameter of ") + reference_.dex_file->PrettyMethod(reference_.index);
93       default:
94         return "<unknown>";
95     }
96   }
97 
98  private:
99   RegisterSource source_;
100   uint32_t value_;
101   DexFileReference reference_;
102   const VeriClass* type_;
103 };
104 
105 struct InstructionInfo {
106   bool has_been_visited;
107 };
108 
109 class VeriFlowAnalysis {
110  public:
VeriFlowAnalysis(VeridexResolver * resolver,const ClassDataItemIterator & it)111   VeriFlowAnalysis(VeridexResolver* resolver, const ClassDataItemIterator& it)
112       : resolver_(resolver),
113         method_id_(it.GetMemberIndex()),
114         code_item_accessor_(resolver->GetDexFile(), it.GetMethodCodeItem()),
115         dex_registers_(code_item_accessor_.InsnsSizeInCodeUnits()),
116         instruction_infos_(code_item_accessor_.InsnsSizeInCodeUnits()) {}
117 
118   void Run();
119 
120   virtual RegisterValue AnalyzeInvoke(const Instruction& instruction, bool is_range) = 0;
121   virtual void AnalyzeFieldSet(const Instruction& instruction) = 0;
~VeriFlowAnalysis()122   virtual ~VeriFlowAnalysis() {}
123 
124  private:
125   // Find all branches in the code.
126   void FindBranches();
127 
128   // Analyze all non-deead instructions in the code.
129   void AnalyzeCode();
130 
131   // Set the instruction at the given pc as a branch target.
132   void SetAsBranchTarget(uint32_t dex_pc);
133 
134   // Whether the instruction at the given pc is a branch target.
135   bool IsBranchTarget(uint32_t dex_pc);
136 
137   // Merge the register values at the given pc with `current_registers`.
138   // Return whether the register values have changed, and the instruction needs
139   // to be visited again.
140   bool MergeRegisterValues(uint32_t dex_pc);
141 
142   void UpdateRegister(
143       uint32_t dex_register, RegisterSource kind, VeriClass* cls, uint32_t source_id);
144   void UpdateRegister(uint32_t dex_register, const RegisterValue& value);
145   void UpdateRegister(uint32_t dex_register, const VeriClass* cls);
146   void UpdateRegister(uint32_t dex_register, int32_t value, const VeriClass* cls);
147   void ProcessDexInstruction(const Instruction& inst);
148   void SetVisited(uint32_t dex_pc);
149   RegisterValue GetFieldType(uint32_t field_index);
150 
151   int GetBranchFlags(const Instruction& instruction) const;
152 
153  protected:
154   const RegisterValue& GetRegister(uint32_t dex_register) const;
155   RegisterValue GetReturnType(uint32_t method_index);
156 
157   VeridexResolver* resolver_;
158 
159  private:
160   const uint32_t method_id_;
161   CodeItemDataAccessor code_item_accessor_;
162 
163   // Vector of register values for all branch targets.
164   std::vector<std::unique_ptr<std::vector<RegisterValue>>> dex_registers_;
165 
166   // The current values of dex registers.
167   std::vector<RegisterValue> current_registers_;
168 
169   // Information on each instruction useful for the analysis.
170   std::vector<InstructionInfo> instruction_infos_;
171 
172   // The value of invoke instructions, to be fetched when visiting move-result.
173   RegisterValue last_result_;
174 };
175 
176 struct ReflectAccessInfo {
177   RegisterValue cls;
178   RegisterValue name;
179   bool is_method;
180 
ReflectAccessInfoReflectAccessInfo181   ReflectAccessInfo(RegisterValue c, RegisterValue n, bool m) : cls(c), name(n), is_method(m) {}
182 
IsConcreteReflectAccessInfo183   bool IsConcrete() const {
184     // We capture RegisterSource::kString for the class, for example in Class.forName.
185     return (cls.IsClass() || cls.IsString()) && name.IsString();
186   }
187 };
188 
189 // Collects all reflection uses.
190 class FlowAnalysisCollector : public VeriFlowAnalysis {
191  public:
FlowAnalysisCollector(VeridexResolver * resolver,const ClassDataItemIterator & it)192   FlowAnalysisCollector(VeridexResolver* resolver, const ClassDataItemIterator& it)
193       : VeriFlowAnalysis(resolver, it) {}
194 
GetUses()195   const std::vector<ReflectAccessInfo>& GetUses() const {
196     return uses_;
197   }
198 
199   RegisterValue AnalyzeInvoke(const Instruction& instruction, bool is_range) OVERRIDE;
200   void AnalyzeFieldSet(const Instruction& instruction) OVERRIDE;
201 
202  private:
203   // List of reflection uses found, concrete and abstract.
204   std::vector<ReflectAccessInfo> uses_;
205 };
206 
207 // Substitutes reflection uses by new ones.
208 class FlowAnalysisSubstitutor : public VeriFlowAnalysis {
209  public:
FlowAnalysisSubstitutor(VeridexResolver * resolver,const ClassDataItemIterator & it,const std::map<MethodReference,std::vector<ReflectAccessInfo>> & accesses)210   FlowAnalysisSubstitutor(VeridexResolver* resolver,
211                           const ClassDataItemIterator& it,
212                           const std::map<MethodReference, std::vector<ReflectAccessInfo>>& accesses)
213       : VeriFlowAnalysis(resolver, it), accesses_(accesses) {}
214 
GetUses()215   const std::vector<ReflectAccessInfo>& GetUses() const {
216     return uses_;
217   }
218 
219   RegisterValue AnalyzeInvoke(const Instruction& instruction, bool is_range) OVERRIDE;
220   void AnalyzeFieldSet(const Instruction& instruction) OVERRIDE;
221 
222  private:
223   // List of reflection uses found, concrete and abstract.
224   std::vector<ReflectAccessInfo> uses_;
225   // The abstract uses we are trying to subsititute.
226   const std::map<MethodReference, std::vector<ReflectAccessInfo>>& accesses_;
227 };
228 
229 }  // namespace art
230 
231 #endif  // ART_TOOLS_VERIDEX_FLOW_ANALYSIS_H_
232