flow_analysis.h revision 2a843c81e61128d2c1723c064786f8b7193c62f5 
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
27namespace art {
28
29/**
30 * The source where a dex register comes from.
31 */
32enum 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 */
45class RegisterValue {
46 public:
47  RegisterValue() : source_(RegisterSource::kNone),
48                    value_(0),
49                    reference_(nullptr, 0),
50                    type_(nullptr) {}
51  RegisterValue(RegisterSource source, DexFileReference reference, const VeriClass* type)
52      : source_(source), value_(0), reference_(reference), type_(type) {}
53
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
60  RegisterSource GetSource() const { return source_; }
61  DexFileReference GetDexFileReference() const { return reference_; }
62  const VeriClass* GetType() const { return type_; }
63  uint32_t GetParameterIndex() const {
64    CHECK(IsParameter());
65    return value_;
66  }
67  uint32_t GetConstant() const {
68    CHECK(IsConstant());
69    return value_;
70  }
71  bool IsParameter() const { return source_ == RegisterSource::kParameter; }
72  bool IsClass() const { return source_ == RegisterSource::kClass; }
73  bool IsString() const { return source_ == RegisterSource::kString; }
74  bool IsConstant() const { return source_ == RegisterSource::kConstant; }
75
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
105struct InstructionInfo {
106  bool has_been_visited;
107};
108
109class VeriFlowAnalysis {
110 public:
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;
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
176struct ReflectAccessInfo {
177  RegisterValue cls;
178  RegisterValue name;
179  bool is_method;
180
181  ReflectAccessInfo(RegisterValue c, RegisterValue n, bool m) : cls(c), name(n), is_method(m) {}
182
183  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.
190class FlowAnalysisCollector : public VeriFlowAnalysis {
191 public:
192  FlowAnalysisCollector(VeridexResolver* resolver, const ClassDataItemIterator& it)
193      : VeriFlowAnalysis(resolver, it) {}
194
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.
208class FlowAnalysisSubstitutor : public VeriFlowAnalysis {
209 public:
210  FlowAnalysisSubstitutor(VeridexResolver* resolver,
211                          const ClassDataItemIterator& it,
212                          const std::map<MethodReference, std::vector<ReflectAccessInfo>>& accesses)
213      : VeriFlowAnalysis(resolver, it), accesses_(accesses) {}
214
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