(self)
Normalize the CFG, making sure that there are no overlapping basic blocks.

        Note that this method will not alter transition graphs of each function in self.kb.functions. You may call
        normalize() on each Function object to normalize their transition graphs.

        :return: None
Normalize the CFG, making sure that there are no overlapping basic blocks.
Normalize the CFG making sure that there are no overlapping basic blocks .
def normalize(self):
        """
        Normalize the CFG, making sure that there are no overlapping basic blocks.

        Note that this method will not alter transition graphs of each function in self.kb.functions. You may call
        normalize() on each Function object to normalize their transition graphs.

        :return: None
        """

        graph = self.graph

        smallest_nodes = { }  # indexed by end address of the node
        end_addresses_to_nodes = defaultdict(set)

        for n in graph.nodes():
            if n.is_simprocedure:
                continue
            end_addr = n.addr + n.size
            key = (end_addr, n.callstack_key)
            # add the new item
            end_addresses_to_nodes[key].add(n)

        for key in list(end_addresses_to_nodes.keys()):
            if len(end_addresses_to_nodes[key]) == 1:
                smallest_nodes[key] = next(iter(end_addresses_to_nodes[key]))
                del end_addresses_to_nodes[key]

        while end_addresses_to_nodes:
            key_to_find = (None, None)
            for tpl, x in end_addresses_to_nodes.items():
                if len(x) > 1:
                    key_to_find = tpl
                    break

            end_addr, callstack_key = key_to_find
            all_nodes = end_addresses_to_nodes[key_to_find]

            all_nodes = sorted(all_nodes, key=lambda node: node.addr, reverse=True)
            smallest_node = all_nodes[0] # take the one that has the highest address
            other_nodes = all_nodes[1:]

            self._normalize_core(graph, callstack_key, smallest_node, other_nodes, smallest_nodes,
                                 end_addresses_to_nodes
                                 )

            del end_addresses_to_nodes[key_to_find]
            # make sure the smallest node is stored in end_addresses
            smallest_nodes[key_to_find] = smallest_node

            # corner case
            # sometimes two overlapping blocks may not be ending at the instruction. this might happen when one of the
            # blocks (the bigger one) hits the instruction count limit or bytes limit before reaching the end address
            # of the smaller block. in this case we manually pick up those blocks.
            if not end_addresses_to_nodes:
                # find if there are still overlapping blocks
                sorted_smallest_nodes = defaultdict(list)  # callstack_key is the key of this dict
                for k, node in smallest_nodes.items():
                    _, callstack_key = k
                    sorted_smallest_nodes[callstack_key].append(node)
                for k in sorted_smallest_nodes.keys():
                    sorted_smallest_nodes[k] = sorted(sorted_smallest_nodes[k], key=lambda node: node.addr)

                for callstack_key, lst in sorted_smallest_nodes.items():
                    lst_len = len(lst)
                    for i, node in enumerate(lst):
                        if i == lst_len - 1:
                            break
                        next_node = lst[i + 1]
                        if node is not next_node and node.addr <= next_node.addr < node.addr + node.size:
                            # umm, those nodes are overlapping, but they must have different end addresses
                            nodekey_a = node.addr + node.size, callstack_key
                            nodekey_b = next_node.addr + next_node.size, callstack_key
                            if nodekey_a == nodekey_b:
                                # error handling: this will only happen if we have completely overlapping nodes
                                # caused by different jumps (one of the jumps is probably incorrect), which usually
                                # indicates an error in CFG recovery. we print a warning and skip this node
                                l.warning("Found completely overlapping nodes %s. It usually indicates an error in CFG "
                                          "recovery. Skip.", node)
                                continue

                            if nodekey_a in smallest_nodes and nodekey_b in smallest_nodes:
                                # misuse end_addresses_to_nodes
                                end_addresses_to_nodes[(node.addr + node.size, callstack_key)].add(node)
                                end_addresses_to_nodes[(node.addr + node.size, callstack_key)].add(next_node)

                            smallest_nodes.pop(nodekey_a, None)
                            smallest_nodes.pop(nodekey_b, None)

        self._normalized = True
def normalize ( self ) : graph = self . graph smallest_nodes = { } # indexed by end address of the node end_addresses_to_nodes = defaultdict ( set ) for n in graph . nodes ( ) : if n . is_simprocedure : continue end_addr = n . addr + n . size key = ( end_addr , n . callstack_key ) # add the new item end_addresses_to_nodes [ key ] . add ( n ) for key in list ( end_addresses_to_nodes . keys ( ) ) : if len ( end_addresses_to_nodes [ key ] ) == 1 : smallest_nodes [ key ] = next ( iter ( end_addresses_to_nodes [ key ] ) ) del end_addresses_to_nodes [ key ] while end_addresses_to_nodes : key_to_find = ( None , None ) for tpl , x in end_addresses_to_nodes . items ( ) : if len ( x ) > 1 : key_to_find = tpl break end_addr , callstack_key = key_to_find all_nodes = end_addresses_to_nodes [ key_to_find ] all_nodes = sorted ( all_nodes , key = lambda node : node . addr , reverse = True ) smallest_node = all_nodes [ 0 ] # take the one that has the highest address other_nodes = all_nodes [ 1 : ] self . _normalize_core ( graph , callstack_key , smallest_node , other_nodes , smallest_nodes , end_addresses_to_nodes ) del end_addresses_to_nodes [ key_to_find ] # make sure the smallest node is stored in end_addresses smallest_nodes [ key_to_find ] = smallest_node # corner case # sometimes two overlapping blocks may not be ending at the instruction. this might happen when one of the # blocks (the bigger one) hits the instruction count limit or bytes limit before reaching the end address # of the smaller block. in this case we manually pick up those blocks. if not end_addresses_to_nodes : # find if there are still overlapping blocks sorted_smallest_nodes = defaultdict ( list ) # callstack_key is the key of this dict for k , node in smallest_nodes . items ( ) : _ , callstack_key = k sorted_smallest_nodes [ callstack_key ] . append ( node ) for k in sorted_smallest_nodes . keys ( ) : sorted_smallest_nodes [ k ] = sorted ( sorted_smallest_nodes [ k ] , key = lambda node : node . addr ) for callstack_key , lst in sorted_smallest_nodes . items ( ) : lst_len = len ( lst ) for i , node in enumerate ( lst ) : if i == lst_len - 1 : break next_node = lst [ i + 1 ] if node is not next_node and node . addr <= next_node . addr < node . addr + node . size : # umm, those nodes are overlapping, but they must have different end addresses nodekey_a = node . addr + node . size , callstack_key nodekey_b = next_node . addr + next_node . size , callstack_key if nodekey_a == nodekey_b : # error handling: this will only happen if we have completely overlapping nodes # caused by different jumps (one of the jumps is probably incorrect), which usually # indicates an error in CFG recovery. we print a warning and skip this node l . warning ( "Found completely overlapping nodes %s. It usually indicates an error in CFG " "recovery. Skip." , node ) continue if nodekey_a in smallest_nodes and nodekey_b in smallest_nodes : # misuse end_addresses_to_nodes end_addresses_to_nodes [ ( node . addr + node . size , callstack_key ) ] . add ( node ) end_addresses_to_nodes [ ( node . addr + node . size , callstack_key ) ] . add ( next_node ) smallest_nodes . pop ( nodekey_a , None ) smallest_nodes . pop ( nodekey_b , None ) self . _normalized = True