Python networkx 模块，dfs_postorder_nodes() 实例源码

def dfs_postorder(self, root):
        G = nx.Graph(self.E)
        tree_graph = nx.dfs_tree(G,root)
        clique_ordering = list(nx.dfs_postorder_nodes(tree_graph,root))
        return clique_ordering

def _compile_node_creator_list(self):
        graph = self._graph
        cycles = list(nx.simple_cycles(graph))
        if len(cycles):
            raise ValueError("Found cycles in dependencies "+str(cycles))
        else:
            nodes = list(nx.dfs_postorder_nodes(graph))
            nodes.remove(self._ROOT)  # exclude root
            creators = []
            for n in nodes:
                creator = graph.node[n].get('creator')
                creators.append((n, creator))
            return creators

def taint():
    #get_s
    lines = [
    "15 | ------ IMark(0x80495b8, 2, 0) ------",
    "16 | t2 = GET:I8(eax)",
    "17 | t1 = GET:I8(eax)",
    "18 | t0 = And8(t2,t1)",
    "19 | PUT(cc_op) = 0x0000000d",
    "20 | t3 = 8Uto32(t0)",
    "21 | PUT(cc_dep1) = t3",
    "22 | PUT(cc_dep2) = 0x00000000",
    "23 | PUT(cc_ndep) = 0x00000000",
    "24 | PUT(eip) = 0x080495ba",
    "25 | ------ IMark(0x80495ba, 6, 0) ------",
    "26 | t5 = GET:I32(cc_op)",
    "27 | t6 = GET:I32(cc_dep1)",
    "28 | t7 = GET:I32(cc_dep2)",
    "29 | t8 = GET:I32(cc_ndep)",
    "30 | t9 = x86g_calculate_condition(0x00000004,t5,t6,t7,t8):Ity_I32",
    "31 | t4 = 32to1(t9)",
    "32 | if (t4) { PUT(eip) = 0x8049735L; Ijk_Boring }",
    "33 | PUT(eip) = 0x080495c0",
    "34 | t10 = GET:I32(eip)"
    ]
    queue = []
    cfg = nx.DiGraph()
    for line in lines:

        if "if" in line:
            pass
        elif "=" in line:
            ls = line.split('=',1)      
            rhs = re.findall('t[0-9]+|cc_[a-z]+[0-9]?|eax|ebx|ecx|edx|esi|edi|esp|ebp', ls[0])
            lhs = re.findall('t[0-9]+|cc_[a-z]+[0-9]?|eax|ebx|ecx|edx|esi|edi|esp|ebp', ls[1])


            if rhs and lhs:
                r = rhs[0]
                #print lhs.captures(1)
                for item in lhs:
                    cfg.add_edge(r, item)

    lst = list(nx.dfs_postorder_nodes(cfg, "t4"))
    print lst

def taint(lines):
    #get_s
    lines = [
    "15 | ------ IMark(0x80495b8, 2, 0) ------",
    "16 | t2 = GET:I8(eax)",
    "17 | t1 = GET:I8(eax)",
    "18 | t0 = And8(t2,t1)",
    "19 | PUT(cc_op) = 0x0000000d",
    "20 | t3 = 8Uto32(t0)",
    "21 | PUT(cc_dep1) = t3",
    "22 | PUT(cc_dep2) = 0x00000000",
    "23 | PUT(cc_ndep) = 0x00000000",
    "24 | PUT(eip) = 0x080495ba",
    "25 | ------ IMark(0x80495ba, 6, 0) ------",
    "26 | t5 = GET:I32(cc_op)",
    "27 | t6 = GET:I32(cc_dep1)",
    "28 | t7 = GET:I32(cc_dep2)",
    "29 | t8 = GET:I32(cc_ndep)",
    "30 | t9 = x86g_calculate_condition(0x00000004,t5,t6,t7,t8):Ity_I32",
    "31 | t4 = 32to1(t9)",
    "32 | if (t4) { PUT(eip) = 0x8049735L; Ijk_Boring }",
    "33 | PUT(eip) = 0x080495c0",
    "34 | t10 = GET:I32(eip)"
    ]
    queue = []
    cfg = nx.DiGraph()
    for line in lines:

        if "if" in line:
            key = re.findall('t[0-9]+|cc_[a-z]+[0-9]?|eax|ebx|ecx|edx|esi|edi|esp|ebp', line)
        elif "=" in line:
            ls = line.split('=',1)      
            rhs = re.findall('t[0-9]+|cc_[a-z]+[0-9]?|eax|ebx|ecx|edx|esi|edi|esp|ebp', ls[0])
            lhs = re.findall('t[0-9]+|cc_[a-z]+[0-9]?|eax|ebx|ecx|edx|esi|edi|esp|ebp', ls[1])


            if rhs and lhs:
                r = rhs[0]
                #print lhs.captures(1)
                for item in lhs:
                    cfg.add_edge(r, item)

    lst = list(nx.dfs_postorder_nodes(cfg, key))
    print lst