1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
from __future__ import print_function
from future.utils import viewitems
from builtins import object
from functools import cmp_to_key
from miasm.expression.expression \
import get_expr_mem, get_list_rw, ExprId, ExprInt, \
compare_exprs
from miasm.ir.symbexec import SymbolicExecutionEngine
def get_node_name(label, i, n):
n_name = (label, i, n)
return n_name
def intra_block_flow_raw(ir_arch, ircfg, flow_graph, irb, in_nodes, out_nodes):
"""
Create data flow for an irbloc using raw IR expressions
"""
current_nodes = {}
for i, assignblk in enumerate(irb):
dict_rw = assignblk.get_rw(cst_read=True)
current_nodes.update(out_nodes)
# gen mem arg to mem node links
all_mems = set()
for node_w, nodes_r in viewitems(dict_rw):
for n in nodes_r.union([node_w]):
all_mems.update(get_expr_mem(n))
if not all_mems:
continue
for n in all_mems:
node_n_w = get_node_name(irb.loc_key, i, n)
if not n in nodes_r:
continue
o_r = n.ptr.get_r(mem_read=False, cst_read=True)
for n_r in o_r:
if n_r in current_nodes:
node_n_r = current_nodes[n_r]
else:
node_n_r = get_node_name(irb.loc_key, i, n_r)
current_nodes[n_r] = node_n_r
in_nodes[n_r] = node_n_r
flow_graph.add_uniq_edge(node_n_r, node_n_w)
# gen data flow links
for node_w, nodes_r in viewitems(dict_rw):
for n_r in nodes_r:
if n_r in current_nodes:
node_n_r = current_nodes[n_r]
else:
node_n_r = get_node_name(irb.loc_key, i, n_r)
current_nodes[n_r] = node_n_r
in_nodes[n_r] = node_n_r
flow_graph.add_node(node_n_r)
node_n_w = get_node_name(irb.loc_key, i + 1, node_w)
out_nodes[node_w] = node_n_w
flow_graph.add_node(node_n_w)
flow_graph.add_uniq_edge(node_n_r, node_n_w)
def inter_block_flow_link(ir_arch, ircfg, flow_graph, irb_in_nodes, irb_out_nodes, todo, link_exec_to_data):
lbl, current_nodes, exec_nodes = todo
current_nodes = dict(current_nodes)
# link current nodes to block in_nodes
if not lbl in ircfg.blocks:
print("cannot find block!!", lbl)
return set()
irb = ircfg.blocks[lbl]
to_del = set()
for n_r, node_n_r in viewitems(irb_in_nodes[irb.loc_key]):
if not n_r in current_nodes:
continue
flow_graph.add_uniq_edge(current_nodes[n_r], node_n_r)
to_del.add(n_r)
# if link exec to data, all nodes depends on exec nodes
if link_exec_to_data:
for n_x_r in exec_nodes:
for n_r, node_n_r in viewitems(irb_in_nodes[irb.loc_key]):
if not n_x_r in current_nodes:
continue
if isinstance(n_r, ExprInt):
continue
flow_graph.add_uniq_edge(current_nodes[n_x_r], node_n_r)
# update current nodes using block out_nodes
for n_w, node_n_w in viewitems(irb_out_nodes[irb.loc_key]):
current_nodes[n_w] = node_n_w
# get nodes involved in exec flow
x_nodes = tuple(sorted(irb.dst.get_r(), key=cmp_to_key(compare_exprs)))
todo = set()
for lbl_dst in ircfg.successors(irb.loc_key):
todo.add((lbl_dst, tuple(viewitems(current_nodes)), x_nodes))
return todo
def create_implicit_flow(ir_arch, flow_graph, irb_in_nodes, irb_out_ndes):
# first fix IN/OUT
# If a son read a node which in not in OUT, add it
todo = set(ir_arch.blocks.keys())
while todo:
lbl = todo.pop()
irb = ir_arch.blocks[lbl]
for lbl_son in ir_arch.graph.successors(irb.loc_key):
if not lbl_son in ir_arch.blocks:
print("cannot find block!!", lbl)
continue
irb_son = ir_arch.blocks[lbl_son]
for n_r in irb_in_nodes[irb_son.loc_key]:
if n_r in irb_out_nodes[irb.loc_key]:
continue
if not isinstance(n_r, ExprId):
continue
node_n_w = irb.loc_key, len(irb), n_r
irb_out_nodes[irb.loc_key][n_r] = node_n_w
if not n_r in irb_in_nodes[irb.loc_key]:
irb_in_nodes[irb.loc_key][n_r] = irb.loc_key, 0, n_r
node_n_r = irb_in_nodes[irb.loc_key][n_r]
for lbl_p in ir_arch.graph.predecessors(irb.loc_key):
todo.add(lbl_p)
flow_graph.add_uniq_edge(node_n_r, node_n_w)
def inter_block_flow(ir_arch, ircfg, flow_graph, irb_0, irb_in_nodes, irb_out_nodes, link_exec_to_data=True):
todo = set()
done = set()
todo.add((irb_0, (), ()))
while todo:
state = todo.pop()
if state in done:
continue
done.add(state)
out = inter_block_flow_link(ir_arch, ircfg, flow_graph, irb_in_nodes, irb_out_nodes, state, link_exec_to_data)
todo.update(out)
class symb_exec_func(object):
"""
This algorithm will do symbolic execution on a function, trying to propagate
states between basic blocks in order to extract inter-blocks dataflow. The
algorithm tries to merge states from blocks with multiple parents.
There is no real magic here, loops and complex merging will certainly fail.
"""
def __init__(self, ir_arch):
self.todo = set()
self.stateby_ad = {}
self.cpt = {}
self.states_var_done = set()
self.states_done = set()
self.total_done = 0
self.ir_arch = ir_arch
def add_state(self, parent, ad, state):
variables = dict(state.symbols)
# get block dead, and remove from state
b = self.ir_arch.get_block(ad)
if b is None:
raise ValueError("unknown block! %s" % ad)
s = parent, ad, tuple(sorted(viewitems(variables)))
self.todo.add(s)
def get_next_state(self):
state = self.todo.pop()
return state
def do_step(self):
if len(self.todo) == 0:
return None
if self.total_done > 600:
print("symbexec watchdog!")
return None
self.total_done += 1
print('CPT', self.total_done)
while self.todo:
state = self.get_next_state()
parent, ad, s = state
self.states_done.add(state)
self.states_var_done.add(state)
sb = SymbolicExecutionEngine(self.ir_arch, dict(s))
return parent, ad, sb
return None
|