(self, max_loop_unrolling_times)
Unroll loops globally. The resulting CFG does not contain any loop, but this method is slow on large graphs.

        :param int max_loop_unrolling_times: The maximum iterations of unrolling.
        :return: None
Unroll loops globally. The resulting CFG does not contain any loop, but this method is slow on large graphs.
Unroll loops globally . The resulting CFG does not contain any loop but this method is slow on large graphs .
def force_unroll_loops(self, max_loop_unrolling_times):
        """
        Unroll loops globally. The resulting CFG does not contain any loop, but this method is slow on large graphs.

        :param int max_loop_unrolling_times: The maximum iterations of unrolling.
        :return: None
        """

        if not isinstance(max_loop_unrolling_times, int) or \
                        max_loop_unrolling_times < 0:
            raise AngrCFGError('Max loop unrolling times must be set to an integer greater than or equal to 0 if ' +
                               'loop unrolling is enabled.')

        # Traverse the CFG and try to find the beginning of loops
        loop_backedges = []

        start = self._starts[0]
        if isinstance(start, tuple):
            start, _ = start  # pylint: disable=unpacking-non-sequence
        start_node = self.get_any_node(start)
        if start_node is None:
            raise AngrCFGError('Cannot find start node when trying to unroll loops. The CFG might be empty.')

        graph_copy = networkx.DiGraph(self.graph)

        while True:
            cycles_iter = networkx.simple_cycles(graph_copy)
            try:
                cycle = next(cycles_iter)
            except StopIteration:
                break

            loop_backedge = (None, None)

            for n in networkx.dfs_preorder_nodes(graph_copy, source=start_node):
                if n in cycle:
                    idx = cycle.index(n)
                    if idx == 0:
                        loop_backedge = (cycle[-1], cycle[idx])
                    else:
                        loop_backedge = (cycle[idx - 1], cycle[idx])
                    break

            if loop_backedge not in loop_backedges:
                loop_backedges.append(loop_backedge)

            # Create a common end node for all nodes whose out_degree is 0
            end_nodes = [n for n in graph_copy.nodes() if graph_copy.out_degree(n) == 0]
            new_end_node = "end_node"

            if not end_nodes:
                # We gotta randomly break a loop
                cycles = sorted(networkx.simple_cycles(graph_copy), key=len)
                first_cycle = cycles[0]
                if len(first_cycle) == 1:
                    graph_copy.remove_edge(first_cycle[0], first_cycle[0])
                else:
                    graph_copy.remove_edge(first_cycle[0], first_cycle[1])
                end_nodes = [n for n in graph_copy.nodes() if graph_copy.out_degree(n) == 0]

            for en in end_nodes:
                graph_copy.add_edge(en, new_end_node)

            # postdoms = self.immediate_postdominators(new_end_node, target_graph=graph_copy)
            # reverse_postdoms = defaultdict(list)
            # for k, v in postdoms.items():
            #    reverse_postdoms[v].append(k)

            # Find all loop bodies
            # for src, dst in loop_backedges:
            #    nodes_in_loop = { src, dst }

            #    while True:
            #        new_nodes = set()

            #        for n in nodes_in_loop:
            #            if n in reverse_postdoms:
            #                for node in reverse_postdoms[n]:
            #                    if node not in nodes_in_loop:
            #                        new_nodes.add(node)

            #        if not new_nodes:
            #            break

            #        nodes_in_loop |= new_nodes

            # Unroll the loop body
            # TODO: Finish the implementation

            graph_copy.remove_node(new_end_node)
            src, dst = loop_backedge
            if graph_copy.has_edge(src, dst):  # It might have been removed before
                # Duplicate the dst node
                new_dst = dst.copy()
                new_dst.looping_times = dst.looping_times + 1
                if (
                        new_dst not in graph_copy and
                        # If the new_dst is already in the graph, we don't want to keep unrolling
                        # the this loop anymore since it may *create* a new loop. Of course we
                        # will lose some edges in this way, but in general it is acceptable.
                        new_dst.looping_times <= max_loop_unrolling_times):
                    # Log all successors of the dst node
                    dst_successors = list(graph_copy.successors(dst))
                    # Add new_dst to the graph
                    edge_data = graph_copy.get_edge_data(src, dst)
                    graph_copy.add_edge(src, new_dst, **edge_data)
                    for ds in dst_successors:
                        if ds.looping_times == 0 and ds not in cycle:
                            edge_data = graph_copy.get_edge_data(dst, ds)
                            graph_copy.add_edge(new_dst, ds, **edge_data)
                # Remove the original edge
                graph_copy.remove_edge(src, dst)

        # Update loop backedges
        self._loop_back_edges = loop_backedges

        self.model.graph = graph_copy
def force_unroll_loops ( self , max_loop_unrolling_times ) : if not isinstance ( max_loop_unrolling_times , int ) or max_loop_unrolling_times < 0 : raise AngrCFGError ( 'Max loop unrolling times must be set to an integer greater than or equal to 0 if ' + 'loop unrolling is enabled.' ) # Traverse the CFG and try to find the beginning of loops loop_backedges = [ ] start = self . _starts [ 0 ] if isinstance ( start , tuple ) : start , _ = start # pylint: disable=unpacking-non-sequence start_node = self . get_any_node ( start ) if start_node is None : raise AngrCFGError ( 'Cannot find start node when trying to unroll loops. The CFG might be empty.' ) graph_copy = networkx . DiGraph ( self . graph ) while True : cycles_iter = networkx . simple_cycles ( graph_copy ) try : cycle = next ( cycles_iter ) except StopIteration : break loop_backedge = ( None , None ) for n in networkx . dfs_preorder_nodes ( graph_copy , source = start_node ) : if n in cycle : idx = cycle . index ( n ) if idx == 0 : loop_backedge = ( cycle [ - 1 ] , cycle [ idx ] ) else : loop_backedge = ( cycle [ idx - 1 ] , cycle [ idx ] ) break if loop_backedge not in loop_backedges : loop_backedges . append ( loop_backedge ) # Create a common end node for all nodes whose out_degree is 0 end_nodes = [ n for n in graph_copy . nodes ( ) if graph_copy . out_degree ( n ) == 0 ] new_end_node = "end_node" if not end_nodes : # We gotta randomly break a loop cycles = sorted ( networkx . simple_cycles ( graph_copy ) , key = len ) first_cycle = cycles [ 0 ] if len ( first_cycle ) == 1 : graph_copy . remove_edge ( first_cycle [ 0 ] , first_cycle [ 0 ] ) else : graph_copy . remove_edge ( first_cycle [ 0 ] , first_cycle [ 1 ] ) end_nodes = [ n for n in graph_copy . nodes ( ) if graph_copy . out_degree ( n ) == 0 ] for en in end_nodes : graph_copy . add_edge ( en , new_end_node ) # postdoms = self.immediate_postdominators(new_end_node, target_graph=graph_copy) # reverse_postdoms = defaultdict(list) # for k, v in postdoms.items(): #    reverse_postdoms[v].append(k) # Find all loop bodies # for src, dst in loop_backedges: #    nodes_in_loop = { src, dst } #    while True: #        new_nodes = set() #        for n in nodes_in_loop: #            if n in reverse_postdoms: #                for node in reverse_postdoms[n]: #                    if node not in nodes_in_loop: #                        new_nodes.add(node) #        if not new_nodes: #            break #        nodes_in_loop |= new_nodes # Unroll the loop body # TODO: Finish the implementation graph_copy . remove_node ( new_end_node ) src , dst = loop_backedge if graph_copy . has_edge ( src , dst ) : # It might have been removed before # Duplicate the dst node new_dst = dst . copy ( ) new_dst . looping_times = dst . looping_times + 1 if ( new_dst not in graph_copy and # If the new_dst is already in the graph, we don't want to keep unrolling # the this loop anymore since it may *create* a new loop. Of course we # will lose some edges in this way, but in general it is acceptable. new_dst . looping_times <= max_loop_unrolling_times ) : # Log all successors of the dst node dst_successors = list ( graph_copy . successors ( dst ) ) # Add new_dst to the graph edge_data = graph_copy . get_edge_data ( src , dst ) graph_copy . add_edge ( src , new_dst , * * edge_data ) for ds in dst_successors : if ds . looping_times == 0 and ds not in cycle : edge_data = graph_copy . get_edge_data ( dst , ds ) graph_copy . add_edge ( new_dst , ds , * * edge_data ) # Remove the original edge graph_copy . remove_edge ( src , dst ) # Update loop backedges self . _loop_back_edges = loop_backedges self . model . graph = graph_copy