Class: Necropsy::CallGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/necropsy/graph/call_graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(scan_result, ambiguity_limit: 4) ⇒ CallGraph

Returns a new instance of CallGraph.



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/necropsy/graph/call_graph.rb', line 8

def initialize(scan_result, ambiguity_limit: 4)
  @nodes = {}
  @edges = {}
  @incoming_edges = {}
  @call_sites = scan_result.call_sites
  @instantiated_classes = scan_result.instantiated_classes.dup
  @class_infos = scan_result.class_infos.to_h { |info| [info.id, info] }
  @entrypoint_hints = scan_result.entrypoint_hints
  @ambiguity_limit = ambiguity_limit
  @entry_points = []
  @profiles = []
  @uncertainties = scan_result.uncertainties.to_h do |node_id, messages|
    [node_id, Array(messages).dup]
  end
  @dynamic_alive = {}
  @observation = {}
  @descendants = {}
  scan_result.nodes.each { |node| add_node(node) }
  retain_known_instantiated_classes
end

Instance Attribute Details

#call_sites ⇒ Object (readonly)

Returns the value of attribute call_sites.



5
6
7
 
# File 'lib/necropsy/graph/call_graph.rb', line 5

def call_sites
  @call_sites
end

#class_infos ⇒ Object (readonly)

Returns the value of attribute class_infos.



5
6
7
 
# File 'lib/necropsy/graph/call_graph.rb', line 5

def class_infos
  @class_infos
end

#entry_points ⇒ Object (readonly)

Returns the value of attribute entry_points.



5
6
7
 
# File 'lib/necropsy/graph/call_graph.rb', line 5

def entry_points
  @entry_points
end

#entrypoint_hints ⇒ Object (readonly)

Returns the value of attribute entrypoint_hints.



5
6
7
 
# File 'lib/necropsy/graph/call_graph.rb', line 5

def entrypoint_hints
  @entrypoint_hints
end

#instantiated_classes ⇒ Object (readonly)

Returns the value of attribute instantiated_classes.



5
6
7
 
# File 'lib/necropsy/graph/call_graph.rb', line 5

def instantiated_classes
  @instantiated_classes
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



5
6
7
 
# File 'lib/necropsy/graph/call_graph.rb', line 5

def nodes
  @nodes
end

#observation ⇒ Object (readonly)

Returns the value of attribute observation.



5
6
7
 
# File 'lib/necropsy/graph/call_graph.rb', line 5

def observation
  @observation
end

#profiles ⇒ Object (readonly)

Returns the value of attribute profiles.



5
6
7
 
# File 'lib/necropsy/graph/call_graph.rb', line 5

def profiles
  @profiles
end

Instance Method Details

#add_alive(node_id, evidence) ⇒ Object 



72
73
74
75
76
77
78
 
# File 'lib/necropsy/graph/call_graph.rb', line 72

def add_alive(node_id, evidence)
  return false unless nodes.key?(node_id)

  @dynamic_alive[node_id] ||= []
  @dynamic_alive[node_id] << evidence
  true
end

#add_edge(caller_id, callee_id, evidence) ⇒ Object 



62
63
64
65
66
67
68
69
70
 
# File 'lib/necropsy/graph/call_graph.rb', line 62

def add_edge(caller_id, callee_id, evidence)
  return unless nodes.key?(caller_id) && nodes.key?(callee_id)

  @edges[caller_id] ||= {}
  @edges[caller_id][callee_id] ||= []
  @edges[caller_id][callee_id] << evidence
  @incoming_edges[callee_id] ||= {}
  @incoming_edges[callee_id][caller_id] = @edges[caller_id][callee_id]
end

#add_entry_point(node_id, reason) ⇒ Object 



40
41
42
43
44
45
 
# File 'lib/necropsy/graph/call_graph.rb', line 40

def add_entry_point(node_id, reason)
  return unless nodes.key?(node_id)

  entry = EntryPoint.new(node_id: node_id, reason: reason)
  entry_points << entry unless entry_points.include?(entry)
end

#add_node(node) ⇒ Object 



29
30
31
32
33
34
35
36
37
38
 
# File 'lib/necropsy/graph/call_graph.rb', line 29

def add_node(node)
  return nodes[node.id] if nodes.key?(node.id)

  @method_nodes = nil
  @nodes_by_name = nil
  @dispatch_cache = nil
  @lookup_chain_cache = nil
  @owner_ancestor_cache = nil
  nodes[node.id] = node
end

#add_profile(profile) ⇒ Object 



58
59
60
 
# File 'lib/necropsy/graph/call_graph.rb', line 58

def add_profile(profile)
  profiles << profile
end

#alive_evidences(node_id) ⇒ Object 



84
85
86
 
# File 'lib/necropsy/graph/call_graph.rb', line 84

def alive_evidences(node_id)
  @dynamic_alive[node_id] || []
end

#ambiguous_fallback_candidates(message) ⇒ Object 



145
146
147
148
149
150
151
 
# File 'lib/necropsy/graph/call_graph.rb', line 145

def ambiguous_fallback_candidates(message)
  candidates = candidate_nodes(message)
  return candidates if candidates.one?
  return [] if candidates.size > @ambiguity_limit

  candidates
end

#ambiguous_resolution? ⇒ Boolean

Returns:

  • (Boolean) 


153
154
155
 
# File 'lib/necropsy/graph/call_graph.rb', line 153

def ambiguous_resolution?
  @ambiguity_limit > 1
end

#apply_result(result) ⇒ Object 



47
48
49
50
51
52
53
54
55
56
 
# File 'lib/necropsy/graph/call_graph.rb', line 47

def apply_result(result)
  result.edge_evidences.each { |edge| add_edge(edge.caller_id, edge.callee_id, edge.evidence) }
  matched_alive = result.alive_evidences.count { |alive| add_alive(alive.node_id, alive.evidence) }
  warn_unmatched_dynamic_evidence(result.alive_evidences.length) if matched_alive.zero?
  result.uncertainties.each do |node_id, messages|
    @uncertainties[node_id] ||= []
    @uncertainties[node_id].concat(Array(messages))
  end
  observation.merge!(result.observation) { |_key, left, right| merge_observation(left, right) }
end

#candidate_nodes(message) ⇒ Object 



141
142
143
 
# File 'lib/necropsy/graph/call_graph.rb', line 141

def candidate_nodes(message)
  nodes_by_name.fetch(message, [])
end

#class_info(owner) ⇒ Object 



124
125
126
 
# File 'lib/necropsy/graph/call_graph.rb', line 124

def class_info(owner)
  class_infos[owner]
end

#descendants_of(owner) ⇒ Object 



128
129
130
131
132
 
# File 'lib/necropsy/graph/call_graph.rb', line 128

def descendants_of(owner)
  @descendants[owner] ||= class_infos.keys.select do |candidate|
    candidate == owner || ancestor_chain(candidate).include?(owner)
  end
end

#dynamic_alive?(node_id) ⇒ Boolean

Returns:

  • (Boolean) 


80
81
82
 
# File 'lib/necropsy/graph/call_graph.rb', line 80

def dynamic_alive?(node_id)
  @dynamic_alive.key?(node_id)
end

#dynamic_enabled? ⇒ Boolean

Returns:

  • (Boolean) 


88
89
90
 
# File 'lib/necropsy/graph/call_graph.rb', line 88

def dynamic_enabled?
  @dynamic_alive.any?
end

#edges ⇒ Object 



96
97
98
99
100
101
102
 
# File 'lib/necropsy/graph/call_graph.rb', line 96

def edges
  @edges.flat_map do |caller_id, callees|
    callees.map do |callee_id, evidences|
      Edge.new(caller_id: caller_id, callee_id: callee_id, evidences: evidences)
    end
  end
end

#edges_from(node_id) ⇒ Object 



92
93
94
 
# File 'lib/necropsy/graph/call_graph.rb', line 92

def edges_from(node_id)
  @edges.fetch(node_id, {})
end

#fallback_resolution?(site, resolved: nil) ⇒ Boolean

Returns:

  • (Boolean) 


201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/necropsy/graph/call_graph.rb', line 201

def fallback_resolution?(site, resolved: nil)
  resolved ||= resolve_call_site(site)
  return false if resolved.empty?

  case site.receiver_kind
  when :constant
    receiver_candidates(site).none? { |name| nodes.key?("#{name}.#{site.message}") }
  when :instance
    receiver_candidates(site).none? { |name| nodes.key?("#{name}##{site.message}") }
  when :implicit
    same_owner_candidates(site).empty?
  when :unknown
    true
  else
    false
  end
end

#incoming_edges(node_id) ⇒ Object 



104
105
106
107
108
 
# File 'lib/necropsy/graph/call_graph.rb', line 104

def incoming_edges(node_id)
  @incoming_edges.fetch(node_id, {}).map do |caller_id, evidences|
    Edge.new(caller_id: caller_id, callee_id: node_id, evidences: evidences)
  end
end

#method_nodes ⇒ Object 



116
117
118
 
# File 'lib/necropsy/graph/call_graph.rb', line 116

def method_nodes
  @method_nodes ||= nodes.values.select(&:method?)
end

#modules_for(owner) ⇒ Object 



134
135
136
137
138
139
 
# File 'lib/necropsy/graph/call_graph.rb', line 134

def modules_for(owner)
  info = class_info(owner)
  return [] unless info

  (info.prepends + info.includes + info.extends).uniq
end

#nodes_by_name ⇒ Object 



120
121
122
 
# File 'lib/necropsy/graph/call_graph.rb', line 120

def nodes_by_name
  @nodes_by_name ||= method_nodes.group_by(&:name).freeze
end

#owner_reachable_from_ancestor?(owner, ancestor) ⇒ Boolean

Returns:

  • (Boolean) 


157
158
159
160
161
162
163
164
165
 
# File 'lib/necropsy/graph/call_graph.rb', line 157

def owner_reachable_from_ancestor?(owner, ancestor)
  @owner_ancestor_cache ||= {}
  key = [owner, ancestor]
  return @owner_ancestor_cache[key] if @owner_ancestor_cache.key?(key)

  @owner_ancestor_cache[key] = descendants_of(ancestor).any? do |descendant|
    cached_lookup_chain(descendant).include?(owner)
  end
end

#reconcile_rta_result(result) ⇒ Object 



177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
 
# File 'lib/necropsy/graph/call_graph.rb', line 177

def reconcile_rta_result(result)
  analyzed_sites = result.observation.dig('rta', 'analyzed_sites')
  return unless analyzed_sites

  analyzed_keys = analyzed_sites.to_set { |site| call_site_key(site) }
  allowed = result.edge_evidences.each_with_object(Hash.new { |hash, key| hash[key] = Set.new }) do |edge, memo|
    memo[call_site_key(edge.evidence.metadata)] << edge.callee_id
  end

  @edges.each_value do |callees|
    callees.each do |callee_id, evidences|
      evidences.reject! do |item|
        next false unless %i[name_resolution cha].include?(item.analyzer)

        key = call_site_key(item.metadata)
        analyzed_keys.include?(key) && !allowed[key].include?(callee_id)
      end
    end
    callees.delete_if { |_callee_id, evidences| evidences.empty? }
  end
  @edges.delete_if { |_caller_id, callees| callees.empty? }
  rebuild_incoming_edges
end

#resolve_call_site(site, rta: false) ⇒ Object 



167
168
169
170
171
 
# File 'lib/necropsy/graph/call_graph.rb', line 167

def resolve_call_site(site, rta: false)
  candidates = rta ? rta_candidates_for_receiver(site) : candidates_for_receiver(site)
  candidates = candidates.select { |node| rta_candidate?(node, site) } if rta
  candidates
end

#retain_rta_candidates(candidates, site) ⇒ Object 



173
174
175
 
# File 'lib/necropsy/graph/call_graph.rb', line 173

def retain_rta_candidates(candidates, site)
  candidates.select { |node| rta_candidate?(node, site) }
end

#to_h ⇒ Object 



219
220
221
222
223
224
225
226
227
228
229
 
# File 'lib/necropsy/graph/call_graph.rb', line 219

def to_h
  {
    'nodes' => nodes.values.map(&:to_h),
    'edges' => edges.map(&:to_h),
    'entry_points' => entry_points.map(&:to_h),
    'class_infos' => class_infos.values.map(&:to_h),
    'instantiated_classes' => instantiated_classes.to_a.sort,
    'profiles' => profiles.map(&:to_h),
    'observation' => observation
  }
end

#uncertainties(node_id = nil) ⇒ Object 



110
111
112
113
114
 
# File 'lib/necropsy/graph/call_graph.rb', line 110

def uncertainties(node_id = nil)
  return @uncertainties unless node_id

  @uncertainties.fetch(node_id, [])
end