Prime-path extractor
The Graph class in the module computes prime paths
ControlFlowGraph
__init__(self, graph_file)
special
Arges:
graph_file (str): The path of saved CFG graph
Source code in coda\analysis\paths\prime_path_extractor.py
def __init__(self, graph_file):
"""
Arges:
graph_file (str): The path of saved CFG graph
"""
lines = graph_file.readlines()
self.edges = {}
self.nodes = set()
self.inits = set()
self.finals = set()
for i in range(len(lines) - 2):
line = lines[i]
n, dest = (int(x) for x in line.split(' '))
self.nodes.add(dest)
try:
self.edges[n].append(dest)
except:
self.edges[n] = [dest]
init_line = lines[-2]
init_nodes = set(int(x) for x in init_line.split(':')[1].split(' '))
self.inits = init_nodes
self.nodes.update(self.inits)
final_line = lines[-1]
final_nodes = set(int(x) for x in final_line.split(':')[1].split(' '))
self.finals = final_nodes
self.nodes.update(self.finals)
computePrimePaths(self)
Source code in coda\analysis\paths\prime_path_extractor.py
def computePrimePaths(self):
"""
"""
self.primePaths = []
try_paths = [[n] for n in self.nodes]
while len(try_paths) > 0:
new_try_paths = []
for path in try_paths:
if path[0] == path[-1] and len(path) >= 2: # prime path
self.primePaths.append(path)
elif self.reachEnd(path):
if self.reachHead(path): # prime path
self.primePaths.append(path)
else: # extendable path
new_try_paths += self.extend(path)
try_paths = new_try_paths
extend(self, path)
Source code in coda\analysis\paths\prime_path_extractor.py
def extend(self, path):
"""
"""
extended_paths = []
last = path[-1]
if last in self.finals:
return list()
for n in self.edges[last]:
if n not in path[1:]:
extended_paths += [path + [n]]
return extended_paths
reachEnd(self, path)
Source code in coda\analysis\paths\prime_path_extractor.py
def reachEnd(self, path):
"""
"""
last = path[-1]
if last in self.finals:
return True
for n in self.edges[last]:
if n not in path[1:]:
return False
return True
reachHead(self, path)
Source code in coda\analysis\paths\prime_path_extractor.py
def reachHead(self, path):
"""
"""
first = path[0]
non_final_nodes = self.nodes - self.finals
for n in non_final_nodes:
if first in self.edges[n] and n not in path:
return False
return True