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