admin/cea-sec-miasm
1
0
Fork 0
mirror of https://github.com/cea-sec/miasm synced 2026-06-21 13:48:18 +00:00
Code Issues Packages Projects Releases Wiki Activity
Files
master
cea-sec-miasm/test/analysis/data_flow.py
T
Fabrice Desclaux e6ec952904 Rename ira => LifterModelCall
2020-12-24 17:15:46 +01:00

711 lines
23 KiB
Python
Raw Permalink Blame History

""" Test cases for dead code elimination"""
from __future__ import print_function
from future.utils import viewitems
from miasm.expression.expression import ExprId, ExprInt, ExprAssign, ExprMem
from miasm.core.locationdb import LocationDB
from miasm.analysis.data_flow import DeadRemoval, ReachingDefinitions, DiGraphDefUse
from miasm.ir.analysis import LifterModelCall
from miasm.ir.ir import IRBlock, AssignBlock
loc_db = LocationDB()
a = ExprId("a", 32)
b = ExprId("b", 32)
c = ExprId("c", 32)
d = ExprId("d", 32)
r = ExprId("r", 32)
a_init = ExprId("a_init", 32)
b_init = ExprId("b_init", 32)
c_init = ExprId("c_init", 32)
d_init = ExprId("d_init", 32)
r_init = ExprId("r_init", 32) # Return register
pc = ExprId("pc", 32)
sp = ExprId("sp", 32)
CST1 = ExprInt(0x11, 32)
CST2 = ExprInt(0x12, 32)
CST3 = ExprInt(0x13, 32)
LBL0 = loc_db.add_location("lbl0", 0)
LBL1 = loc_db.add_location("lbl1", 1)
LBL2 = loc_db.add_location("lbl2", 2)
LBL3 = loc_db.add_location("lbl3", 3)
LBL4 = loc_db.add_location("lbl4", 4)
LBL5 = loc_db.add_location("lbl5", 5)
LBL6 = loc_db.add_location("lbl6", 6)
IRDst = ExprId('IRDst', 32)
dummy = ExprId('dummy', 32)
def gen_irblock(label, exprs_list):
irs = []
for exprs in exprs_list:
if isinstance(exprs, AssignBlock):
irs.append(exprs)
else:
irs.append(AssignBlock(exprs))
irs.append(AssignBlock({IRDst:dummy}))
irbl = IRBlock(loc_db, label, irs)
return irbl
class Regs(object):
regs_init = {a: a_init, b: b_init, c: c_init, d: d_init, r: r_init}
all_regs_ids = [a, b, c, d, r, sp, pc]
class Arch(object):
regs = Regs()
def getpc(self, _):
return pc
def getsp(self, _):
return sp
class LifterTest(LifterModelCall):
"""Fake Lifter class for tests"""
def __init__(self, loc_db):
arch = Arch()
super(LifterTest, self).__init__(arch, 32, loc_db)
self.IRDst = IRDst
self.ret_reg = r
def get_out_regs(self, _):
return set([self.ret_reg, self.sp])
Lifter = LifterTest(loc_db)
deadrm = DeadRemoval(Lifter)
# graph 1 : Simple graph with dead and alive variables
G1_cfg = Lifter.new_ircfg()
G1_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST2)]])
G1_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, b)]])
G1_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])
for irb in [G1_IRB0, G1_IRB1, G1_IRB2]:
G1_cfg.add_irblock(irb)
G1_cfg.add_uniq_edge(G1_IRB0.loc_key, G1_IRB1.loc_key)
G1_cfg.add_uniq_edge(G1_IRB1.loc_key, G1_IRB2.loc_key)
# Expected output for graph 1
G1_EXP_cfg = Lifter.new_ircfg()
G1_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(b, CST2)]])
G1_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, b)]])
G1_EXP_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])
for irb in [G1_EXP_IRB0, G1_EXP_IRB1, G1_EXP_IRB2]:
G1_EXP_cfg.add_irblock(irb)
# graph 2 : Natural loop with dead variable
G2_cfg = Lifter.new_ircfg()
G2_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(r, CST1)]])
G2_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G2_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, r)]])
for irb in [G2_IRB0, G2_IRB1, G2_IRB2]:
G2_cfg.add_irblock(irb)
G2_cfg.add_uniq_edge(G2_IRB0.loc_key, G2_IRB1.loc_key)
G2_cfg.add_uniq_edge(G2_IRB1.loc_key, G2_IRB2.loc_key)
G2_cfg.add_uniq_edge(G2_IRB1.loc_key, G2_IRB1.loc_key)
# Expected output for graph 2
G2_EXP_cfg = Lifter.new_ircfg()
G2_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(r, CST1)]])
G2_EXP_IRB1 = gen_irblock(LBL1, [[]])
G2_EXP_IRB2 = gen_irblock(LBL2, [[]])
for irb in [G2_EXP_IRB0, G2_EXP_IRB1, G2_EXP_IRB2]:
G2_EXP_cfg.add_irblock(irb)
# graph 3 : Natural loop with alive variables
G3_cfg = Lifter.new_ircfg()
G3_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G3_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G3_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])
for irb in [G3_IRB0, G3_IRB1, G3_IRB2]:
G3_cfg.add_irblock(irb)
G3_cfg.add_uniq_edge(G3_IRB0.loc_key, G3_IRB1.loc_key)
G3_cfg.add_uniq_edge(G3_IRB1.loc_key, G3_IRB2.loc_key)
G3_cfg.add_uniq_edge(G3_IRB1.loc_key, G3_IRB1.loc_key)
# Expected output for graph 3
G3_EXP_cfg = Lifter.new_ircfg()
G3_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G3_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G3_EXP_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])
for irb in [G3_EXP_IRB0, G3_EXP_IRB1, G3_EXP_IRB2]:
G3_EXP_cfg.add_irblock(irb)
# graph 4 : If/else with dead variables
G4_cfg = Lifter.new_ircfg()
G4_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G4_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G4_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, a+CST2)]])
G4_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, CST3)], [ExprAssign(r, a)]])
for irb in [G4_IRB0, G4_IRB1, G4_IRB2, G4_IRB3]:
G4_cfg.add_irblock(irb)
G4_cfg.add_uniq_edge(G4_IRB0.loc_key, G4_IRB1.loc_key)
G4_cfg.add_uniq_edge(G4_IRB0.loc_key, G4_IRB2.loc_key)
G4_cfg.add_uniq_edge(G4_IRB1.loc_key, G4_IRB3.loc_key)
G4_cfg.add_uniq_edge(G4_IRB2.loc_key, G4_IRB3.loc_key)
# Expected output for graph 4
G4_EXP_cfg = Lifter.new_ircfg()
G4_EXP_IRB0 = gen_irblock(LBL0, [[]])
G4_EXP_IRB1 = gen_irblock(LBL1, [[]])
G4_EXP_IRB2 = gen_irblock(LBL2, [[]])
G4_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, CST3)], [ExprAssign(r, a)]])
for irb in [G4_EXP_IRB0, G4_EXP_IRB1, G4_EXP_IRB2, G4_EXP_IRB3]:
G4_EXP_cfg.add_irblock(irb)
# graph 5 : Loop and If/else with dead variables
G5_cfg = Lifter.new_ircfg()
G5_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G5_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, CST2)]])
G5_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, a+CST2)]])
G5_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, a+CST3)]])
G5_IRB4 = gen_irblock(LBL4, [[ExprAssign(a, a+CST1)]])
G5_IRB5 = gen_irblock(LBL5, [[ExprAssign(a, r)]])
for irb in [G5_IRB0, G5_IRB1, G5_IRB2, G5_IRB3, G5_IRB4, G5_IRB5]:
G5_cfg.add_irblock(irb)
G5_cfg.add_uniq_edge(G5_IRB0.loc_key, G5_IRB1.loc_key)
G5_cfg.add_uniq_edge(G5_IRB1.loc_key, G5_IRB2.loc_key)
G5_cfg.add_uniq_edge(G5_IRB1.loc_key, G5_IRB3.loc_key)
G5_cfg.add_uniq_edge(G5_IRB2.loc_key, G5_IRB4.loc_key)
G5_cfg.add_uniq_edge(G5_IRB3.loc_key, G5_IRB4.loc_key)
G5_cfg.add_uniq_edge(G5_IRB4.loc_key, G5_IRB5.loc_key)
G5_cfg.add_uniq_edge(G5_IRB4.loc_key, G5_IRB1.loc_key)
# Expected output for graph 5
G5_EXP_cfg = Lifter.new_ircfg()
G5_EXP_IRB0 = gen_irblock(LBL0, [[]])
G5_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, CST2)]])
G5_EXP_IRB2 = gen_irblock(LBL2, [[]])
G5_EXP_IRB3 = gen_irblock(LBL3, [[]])
G5_EXP_IRB4 = gen_irblock(LBL4, [[]])
G5_EXP_IRB5 = gen_irblock(LBL5, [[]])
for irb in [G5_EXP_IRB0, G5_EXP_IRB1, G5_EXP_IRB2,
G5_EXP_IRB3, G5_EXP_IRB4, G5_EXP_IRB5]:
G5_EXP_cfg.add_irblock(irb)
# graph 6 : Natural loop with dead variables symmetric assignment
# (a = b <-> b = a )
G6_cfg = Lifter.new_ircfg()
G6_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G6_IRB1 = gen_irblock(LBL1, [[ExprAssign(b, a)]])
G6_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, b)]])
G6_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST2)]])
for irb in [G6_IRB0, G6_IRB1, G6_IRB2, G6_IRB3]:
G6_cfg.add_irblock(irb)
G6_cfg.add_uniq_edge(G6_IRB0.loc_key, G6_IRB1.loc_key)
G6_cfg.add_uniq_edge(G6_IRB1.loc_key, G6_IRB2.loc_key)
G6_cfg.add_uniq_edge(G6_IRB2.loc_key, G6_IRB1.loc_key)
G6_cfg.add_uniq_edge(G6_IRB2.loc_key, G6_IRB3.loc_key)
# Expected output for graph 6
G6_EXP_cfg = Lifter.new_ircfg()
G6_EXP_IRB0 = gen_irblock(LBL0, [[]])
G6_EXP_IRB1 = gen_irblock(LBL1, [[]])
G6_EXP_IRB2 = gen_irblock(LBL2, [[]])
G6_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST2)]])
for irb in [G6_EXP_IRB0, G6_EXP_IRB1, G6_EXP_IRB2, G6_EXP_IRB3]:
G6_EXP_cfg.add_irblock(irb)
# graph 7 : Double entry loop with dead variables
G7_cfg = Lifter.new_ircfg()
G7_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(r, CST1)]])
G7_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G7_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, a+CST2)]])
G7_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, r)]])
for irb in [G7_IRB0, G7_IRB1, G7_IRB2, G7_IRB3]:
G7_cfg.add_irblock(irb)
G7_cfg.add_uniq_edge(G7_IRB0.loc_key, G7_IRB1.loc_key)
G7_cfg.add_uniq_edge(G7_IRB1.loc_key, G7_IRB2.loc_key)
G7_cfg.add_uniq_edge(G7_IRB2.loc_key, G7_IRB1.loc_key)
G7_cfg.add_uniq_edge(G7_IRB2.loc_key, G7_IRB3.loc_key)
G7_cfg.add_uniq_edge(G7_IRB0.loc_key, G7_IRB2.loc_key)
# Expected output for graph 7
G7_EXP_cfg = Lifter.new_ircfg()
G7_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(r, CST1)]])
G7_EXP_IRB1 = gen_irblock(LBL1, [[]])
G7_EXP_IRB2 = gen_irblock(LBL2, [[]])
G7_EXP_IRB3 = gen_irblock(LBL3, [[]])
for irb in [G7_EXP_IRB0, G7_EXP_IRB1, G7_EXP_IRB2, G7_EXP_IRB3]:
G7_EXP_cfg.add_irblock(irb)
# graph 8 : Nested loops with dead variables
G8_cfg = Lifter.new_ircfg()
G8_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST1)]])
G8_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)]])
G8_IRB2 = gen_irblock(LBL2, [[ExprAssign(b, b+CST2)]])
G8_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, b)]])
for irb in [G8_IRB0, G8_IRB1, G8_IRB2, G8_IRB3]:
G8_cfg.add_irblock(irb)
G8_cfg.add_uniq_edge(G8_IRB0.loc_key, G8_IRB1.loc_key)
G8_cfg.add_uniq_edge(G8_IRB1.loc_key, G8_IRB2.loc_key)
G8_cfg.add_uniq_edge(G8_IRB2.loc_key, G8_IRB1.loc_key)
G8_cfg.add_uniq_edge(G8_IRB2.loc_key, G8_IRB3.loc_key)
G8_cfg.add_uniq_edge(G8_IRB3.loc_key, G8_IRB2.loc_key)
# Expected output for graph 8
G8_EXP_cfg = Lifter.new_ircfg()
G8_EXP_IRB0 = gen_irblock(LBL0, [[], []])
G8_EXP_IRB1 = gen_irblock(LBL1, [[]])
G8_EXP_IRB2 = gen_irblock(LBL2, [[]])
G8_EXP_IRB3 = gen_irblock(LBL3, [[]])
for irb in [G8_EXP_IRB0, G8_EXP_IRB1, G8_EXP_IRB2, G8_EXP_IRB3]:
G8_EXP_cfg.add_irblock(irb)
# graph 9 : Miultiple-exits loops with dead variables
G9_cfg = Lifter.new_ircfg()
G9_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST1)]])
G9_IRB1 = gen_irblock(LBL1, [[ExprAssign(a, a+CST1)], [ExprAssign(b, b+CST1)]])
G9_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, a+CST2)], [ExprAssign(b, b+CST2)]])
G9_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, b)]])
G9_IRB4 = gen_irblock(LBL4, [[ExprAssign(r, a)], [ExprAssign(r, b)]])
for irb in [G9_IRB0, G9_IRB1, G9_IRB2, G9_IRB3, G9_IRB4]:
G9_cfg.add_irblock(irb)
G9_cfg.add_uniq_edge(G9_IRB0.loc_key, G9_IRB4.loc_key)
G9_cfg.add_uniq_edge(G9_IRB0.loc_key, G9_IRB1.loc_key)
G9_cfg.add_uniq_edge(G9_IRB1.loc_key, G9_IRB0.loc_key)
G9_cfg.add_uniq_edge(G9_IRB1.loc_key, G9_IRB4.loc_key)
G9_cfg.add_uniq_edge(G9_IRB1.loc_key, G9_IRB2.loc_key)
G9_cfg.add_uniq_edge(G9_IRB2.loc_key, G9_IRB0.loc_key)
G9_cfg.add_uniq_edge(G9_IRB2.loc_key, G9_IRB3.loc_key)
G9_cfg.add_uniq_edge(G9_IRB3.loc_key, G9_IRB4.loc_key)
# Expected output for graph 9
G9_EXP_cfg = Lifter.new_ircfg()
G9_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(b, CST1)]])
G9_EXP_IRB1 = gen_irblock(LBL1, [[], [ExprAssign(b, b+CST1)]])
G9_EXP_IRB2 = gen_irblock(LBL2, [[], [ExprAssign(b, b+CST2)]])
G9_EXP_IRB3 = gen_irblock(LBL3, [[]])
G9_EXP_IRB4 = gen_irblock(LBL4, [[], [ExprAssign(r, b)]])
for irb in [G9_EXP_IRB0, G9_EXP_IRB1, G9_EXP_IRB2, G9_EXP_IRB3, G9_EXP_IRB4]:
G9_EXP_cfg.add_irblock(irb)
# graph 10 : Natural loop with alive variables symmetric assignment
# (a = b <-> b = a )
G10_cfg = Lifter.new_ircfg()
G10_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)]])
G10_IRB1 = gen_irblock(LBL1, [[ExprAssign(b, a)]])
G10_IRB2 = gen_irblock(LBL2, [[ExprAssign(a, b)]])
G10_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST1)]])
for irb in [G10_IRB0, G10_IRB1, G10_IRB2, G10_IRB3]:
G10_cfg.add_irblock(irb)
G10_cfg.add_uniq_edge(G10_IRB0.loc_key, G10_IRB1.loc_key)
G10_cfg.add_uniq_edge(G10_IRB1.loc_key, G10_IRB2.loc_key)
G10_cfg.add_uniq_edge(G10_IRB2.loc_key, G10_IRB1.loc_key)
G10_cfg.add_uniq_edge(G10_IRB2.loc_key, G10_IRB3.loc_key)
# Expected output for graph 10
G10_EXP_cfg = Lifter.new_ircfg()
G10_EXP_IRB0 = gen_irblock(LBL0, [[]])
G10_EXP_IRB1 = gen_irblock(LBL1, [[]])
G10_EXP_IRB2 = gen_irblock(LBL2, [[]])
G10_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST1)]])
for irb in [G10_EXP_IRB0, G10_EXP_IRB1, G10_EXP_IRB2, G10_EXP_IRB3]:
G10_EXP_cfg.add_irblock(irb)
# graph 11 : If/Else conditions with alive variables
G11_cfg = Lifter.new_ircfg()
G11_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, b)]])
G11_IRB1 = gen_irblock(LBL1, [[ExprAssign(b, a)]])
G11_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])
G11_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, a+CST1)]])
G11_IRB4 = gen_irblock(LBL4, [[ExprAssign(b, b+CST1)]])
for irb in [G11_IRB0, G11_IRB1, G11_IRB2]:
G11_cfg.add_irblock(irb)
G11_cfg.add_uniq_edge(G11_IRB0.loc_key, G11_IRB1.loc_key)
#G11_cfg.add_uniq_edge(G11_IRB3.loc_key, G11_IRB1.loc_key)
G11_cfg.add_uniq_edge(G11_IRB1.loc_key, G11_IRB0.loc_key)
#G11_cfg.add_uniq_edge(G11_IRB4.loc_key, G11_IRB0.loc_key)
G11_cfg.add_uniq_edge(G11_IRB1.loc_key, G11_IRB2.loc_key)
# Expected output for graph 11
G11_EXP_cfg = Lifter.new_ircfg()
G11_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, b)]])
G11_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(b, a)]])
G11_EXP_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)]])
#G11_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(a, a+CST1)]])
#G11_EXP_IRB4 = gen_irblock(LBL4, [[ExprAssign(b, b+CST1)]])
for irb in [G11_EXP_IRB0, G11_EXP_IRB1,
G11_EXP_IRB2]:
G11_EXP_cfg.add_irblock(irb)
# graph 12 : Graph with multiple out points and useless definitions
# of return register
G12_cfg = Lifter.new_ircfg()
G12_IRB0 = gen_irblock(LBL0, [[ExprAssign(r, CST1)], [ExprAssign(a, CST2)]])
G12_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, CST2)]])
G12_IRB2 = gen_irblock(LBL2, [[ExprAssign(r, a)], [ExprAssign(b, CST3)]])
G12_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST3)]])
G12_IRB4 = gen_irblock(LBL4, [[ExprAssign(r, CST2)]])
G12_IRB5 = gen_irblock(LBL5, [[ExprAssign(r, b)]])
for irb in [G12_IRB0, G12_IRB1, G12_IRB2, G12_IRB3, G12_IRB4, G12_IRB5]:
G12_cfg.add_irblock(irb)
G12_cfg.add_uniq_edge(G12_IRB0.loc_key, G12_IRB1.loc_key)
G12_cfg.add_uniq_edge(G12_IRB0.loc_key, G12_IRB2.loc_key)
G12_cfg.add_uniq_edge(G12_IRB2.loc_key, G12_IRB3.loc_key)
G12_cfg.add_uniq_edge(G12_IRB2.loc_key, G12_IRB4.loc_key)
G12_cfg.add_uniq_edge(G12_IRB4.loc_key, G12_IRB5.loc_key)
# Expected output for graph 12
G12_EXP_cfg = Lifter.new_ircfg()
G12_EXP_IRB0 = gen_irblock(LBL0, [[], []])
G12_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, CST2)]])
G12_EXP_IRB2 = gen_irblock(LBL2, [[], [ExprAssign(b, CST3)]])
G12_EXP_IRB3 = gen_irblock(LBL3, [[ExprAssign(r, CST3)]])
G12_EXP_IRB4 = gen_irblock(LBL4, [[]])
G12_EXP_IRB5 = gen_irblock(LBL5, [[ExprAssign(r, b)]])
for irb in [G12_EXP_IRB0, G12_EXP_IRB1,
G12_EXP_IRB2, G12_EXP_IRB3,
G12_EXP_IRB4, G12_EXP_IRB5]:
G12_EXP_cfg.add_irblock(irb)
# graph 13 : Graph where a leaf has lost its son
G13_cfg = Lifter.new_ircfg()
G13_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST2)]])
G13_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, b)]])
G13_IRB2 = gen_irblock(LBL2, [[ExprAssign(d, CST2)], [ExprAssign(a, b+CST1),
ExprAssign(c, a+b)]])
G13_IRB3 = gen_irblock(LBL3, [[]]) # lost son
G13_IRB4 = gen_irblock(LBL4, [[ExprAssign(b, CST2)]])
for irb in [G13_IRB0, G13_IRB1, G13_IRB2, G13_IRB4]:
G13_cfg.add_irblock(irb)
G13_cfg.add_uniq_edge(G13_IRB0.loc_key, G13_IRB1.loc_key)
G13_cfg.add_uniq_edge(G13_IRB0.loc_key, G13_IRB4.loc_key)
G13_cfg.add_uniq_edge(G13_IRB2.loc_key, G13_IRB3.loc_key)
G13_cfg.add_uniq_edge(G13_IRB4.loc_key, G13_IRB2.loc_key)
# Expected output for graph 13
G13_EXP_cfg = Lifter.new_ircfg()
G13_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(b, CST2)]])
G13_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, b)]])
G13_EXP_IRB2 = gen_irblock(LBL2, [[ExprAssign(d, CST2)], [ExprAssign(a, b+CST1),
ExprAssign(c, a+b)]])
G13_EXP_IRB3 = gen_irblock(LBL3, [[]])
G13_EXP_IRB4 = gen_irblock(LBL4, [[ExprAssign(b, CST2)]])
for irb in [G13_EXP_IRB0, G13_EXP_IRB1, G13_EXP_IRB2, G13_EXP_IRB4]:
G13_EXP_cfg.add_irblock(irb)
#G13_EXP_cfg = G13_cfg
# graph 14 : Graph where variable assigned multiple times in a block but still
# useful in the end
G14_cfg = Lifter.new_ircfg()
G14_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(c, a)],
[ExprAssign(a, CST2)]])
G14_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a+c)]])
for irb in [G14_IRB0, G14_IRB1]:
G14_cfg.add_irblock(irb)
G14_cfg.add_uniq_edge(G14_IRB0.loc_key, G14_IRB1.loc_key)
# Expected output for graph 1
G14_EXP_cfg = Lifter.new_ircfg()
G14_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1)], [ExprAssign(c, a)],
[ExprAssign(a, CST2)]])
G14_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a+c)]])
for irb in [G14_EXP_IRB0, G14_EXP_IRB1]:
G14_EXP_cfg.add_irblock(irb)
# graph 15 : Graph where variable assigned multiple and read at the same time,
# but useless
G15_cfg = Lifter.new_ircfg()
G15_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST2)], [ExprAssign(a, CST1),
ExprAssign(b, a+CST2),
ExprAssign(c, CST1)]])
G15_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a)]])
for irb in [G15_IRB0, G15_IRB1]:
G15_cfg.add_irblock(irb)
G15_cfg.add_uniq_edge(G15_IRB0.loc_key, G15_IRB1.loc_key)
# Expected output for graph 1
G15_EXP_cfg = Lifter.new_ircfg()
G15_EXP_IRB0 = gen_irblock(LBL0, [[], [ExprAssign(a, CST1)]])
G15_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a)]])
for irb in [G15_EXP_IRB0, G15_EXP_IRB1]:
G15_EXP_cfg.add_irblock(irb)
# graph 16 : Graph where variable assigned multiple times in the same block
G16_cfg = Lifter.new_ircfg()
G16_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, CST1), ExprAssign(b, CST2),
ExprAssign(c, CST3)], [ExprAssign(a, c+CST1),
ExprAssign(b, c+CST2)]])
G16_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a+b)], [ExprAssign(r, c+r)]])
G16_IRB2 = gen_irblock(LBL2, [[]])
for irb in [G16_IRB0, G16_IRB1]:
G16_cfg.add_irblock(irb)
G16_cfg.add_uniq_edge(G16_IRB0.loc_key, G16_IRB1.loc_key)
G16_cfg.add_uniq_edge(G16_IRB1.loc_key, G16_IRB2.loc_key)
for irb in [G16_IRB0, G16_IRB1]:
G16_cfg.add_irblock(irb)
# Expected output for graph 1
G16_EXP_cfg = Lifter.new_ircfg()
G16_EXP_IRB0 = gen_irblock(LBL0, [[ExprAssign(c, CST3)], [ExprAssign(a, c + CST1),
ExprAssign(b, c + CST2)]])
G16_EXP_IRB1 = gen_irblock(LBL1, [[ExprAssign(r, a+b)], [ExprAssign(r, c+r)]])
for irb in [G16_EXP_IRB0, G16_EXP_IRB1]:
G16_EXP_cfg.add_irblock(irb)
# graph 17 : parallel ir
G17_cfg = Lifter.new_ircfg()
G17_IRB0 = gen_irblock(LBL0, [[ExprAssign(a, a*b),
ExprAssign(b, c),
ExprAssign(c, CST1)],
[ExprAssign(d, d+ CST2)],
[ExprAssign(a, CST1),
ExprAssign(b, a),
ExprAssign(c, b)],
[ExprAssign(ExprMem(d+CST1, 32), a),
ExprAssign(a, b),
ExprAssign(b, c),
ExprAssign(c, CST1)],
[ExprAssign(a, CST1),
ExprAssign(b, a),
ExprAssign(c, b)],
[ExprAssign(ExprMem(d+CST2, 32), a),
ExprAssign(a, b),
ExprAssign(b, c),
ExprAssign(c, CST1)],
[ExprAssign(a, CST2),
ExprAssign(b, a),
ExprAssign(c, b)],
[ExprAssign(a, a+CST1)],
[ExprAssign(d, a),
ExprAssign(a, d)],
[ExprAssign(d, d+CST1)],
[ExprAssign(a, CST2),
ExprAssign(b, a),
ExprAssign(c, b)],
[ExprAssign(a, a+CST2)],
[ExprAssign(a, CST2),
ExprAssign(b, a),
ExprAssign(c, b)],
[ExprAssign(a, CST1),
ExprAssign(b, a),
ExprAssign(c, b)],
[ExprAssign(ExprMem(d, 32), a+b+c)],
])
for irb in [G17_IRB0]:
G17_cfg.add_irblock(irb)
#G17_cfg.graph.add_node(G17_IRB0.loc_key)
# Expected output for graph 17
G17_EXP_cfg = Lifter.new_ircfg()
G17_EXP_IRB0 = gen_irblock(LBL0, [[],
[ExprAssign(d, d+ CST2)],
[ExprAssign(a, CST1)],
[ExprAssign(ExprMem(d+CST1, 32), a)],
[ExprAssign(a, CST1)],
[ExprAssign(ExprMem(d+CST2, 32), a)],
[ExprAssign(a, CST2)],
[ExprAssign(a, a+CST1)],
[ExprAssign(d, a)],
[ExprAssign(d, d+CST1)],
[ExprAssign(a, CST2)],
[ExprAssign(a, a+CST2)],
[ExprAssign(a, CST2),
ExprAssign(b, a)],
[ExprAssign(a, CST1),
ExprAssign(b, a),
ExprAssign(c, b)],
G17_IRB0[14]
# Trick because a+b+c != ((a+b)+c)
])
for irb in [G17_EXP_IRB0]:
G17_EXP_cfg.add_irblock(irb)
# Beginning of tests
for test_nb, test in enumerate([(G1_cfg, G1_EXP_cfg),
(G2_cfg, G2_EXP_cfg),
(G3_cfg, G3_EXP_cfg),
(G4_cfg, G4_EXP_cfg),
(G5_cfg, G5_EXP_cfg),
(G6_cfg, G6_EXP_cfg),
(G7_cfg, G7_EXP_cfg),
(G8_cfg, G8_EXP_cfg),
(G9_cfg, G9_EXP_cfg),
(G10_cfg, G10_EXP_cfg),
(G11_cfg, G11_EXP_cfg),
(G12_cfg, G12_EXP_cfg),
(G13_cfg, G13_EXP_cfg),
(G14_cfg, G14_EXP_cfg),
(G15_cfg, G15_EXP_cfg),
(G16_cfg, G16_EXP_cfg),
(G17_cfg, G17_EXP_cfg)
]):
# Extract test elements
g_ircfg, g_exp_ircfg = test
print("[+] Test", test_nb+1)
# Print initial graph, for debug
open("graph_%02d.dot" % (test_nb+1), "w").write(g_ircfg.dot())
reaching_defs = ReachingDefinitions(g_ircfg)
defuse = DiGraphDefUse(reaching_defs, deref_mem=True)
# # Simplify graph
deadrm(g_ircfg)
# # Print simplified graph, for debug
open("simp_graph_%02d.dot" % (test_nb+1), "w").write(g_ircfg.dot())
# Same number of blocks
assert len(g_ircfg.blocks) == len(g_exp_ircfg.blocks)
# Check that each expr in the blocks are the same
for lbl, irb in viewitems(g_ircfg.blocks):
exp_irb = g_exp_ircfg.blocks[lbl]
assert exp_irb.assignblks == irb.assignblks
Reference in New Issue View Git Blame Copy Permalink