Home | History | Annotate | Download | only in veridex 
      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:
     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 
    105 struct InstructionInfo {
    106   bool has_been_visited;
    107 };
    108 
    109 class 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 
    176 struct 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.
    190 class 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.
    208 class 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