(self)
Construct the data dependence graph.

        We track the following types of dependence:
        - (Intra-IRSB) temporary variable dependencies
        - Register dependencies
        - Memory dependencies, although it's very limited. See below.

        We track the following types of memory access:
        - (Intra-functional) Stack read/write.
            Trace changes of stack pointers inside a function, and the dereferences of stack pointers.
        - (Inter-functional) Stack read/write.
        - (Global) Static memory positions.
            Keep a map of all accessible memory positions to their source statements per function. After that, we
            traverse the CFG and link each pair of reads/writes together in the order of control-flow.

        We do not track the following types of memory access
        - Symbolic memory access
            Well, they cannot be tracked under fastpath mode (which is the mode we are generating the CTF) anyways.
Construct the data dependence graph.
Construct the data dependence graph .
def _construct(self):
        """
        Construct the data dependence graph.

        We track the following types of dependence:
        - (Intra-IRSB) temporary variable dependencies
        - Register dependencies
        - Memory dependencies, although it's very limited. See below.

        We track the following types of memory access:
        - (Intra-functional) Stack read/write.
            Trace changes of stack pointers inside a function, and the dereferences of stack pointers.
        - (Inter-functional) Stack read/write.
        - (Global) Static memory positions.
            Keep a map of all accessible memory positions to their source statements per function. After that, we
            traverse the CFG and link each pair of reads/writes together in the order of control-flow.

        We do not track the following types of memory access
        - Symbolic memory access
            Well, they cannot be tracked under fastpath mode (which is the mode we are generating the CTF) anyways.
        """

        worklist = []
        worklist_set = set()

        # Initialize the worklist
        if self._start is None:
            # initial nodes are those nodes in CFG that has no in-degrees
            for n in self._cfg.graph.nodes():
                if self._cfg.graph.in_degree(n) == 0:
                    # Put it into the worklist
                    job = DDGJob(n, 0)
                    self._worklist_append(job, worklist, worklist_set)
        else:
            for n in self._cfg.model.get_all_nodes(self._start):
                job = DDGJob(n, 0)
                self._worklist_append(job, worklist, worklist_set)

        # A dict storing defs set
        # DDGJob -> LiveDefinition
        live_defs_per_node = {}

        while worklist:
            # Pop out a node
            ddg_job = worklist[0]
            l.debug("Processing %s.", ddg_job)
            node, call_depth = ddg_job.cfg_node, ddg_job.call_depth
            worklist = worklist[ 1 : ]
            worklist_set.remove(node)

            # Grab all final states. There are usually more than one (one state for each successor), and we gotta
            # process all of them
            final_states = node.final_states

            if node in live_defs_per_node:
                live_defs = live_defs_per_node[node]
            else:
                live_defs = LiveDefinitions()
                live_defs_per_node[node] = live_defs

            successing_nodes = list(self._cfg.graph.successors(node))

            # try to assign every final state to a successor and vice versa
            match_suc = defaultdict(bool)
            match_state = defaultdict(set)

            for suc in successing_nodes:
                matched = False
                for state in final_states:
                    try:
                        if state.solver.eval(state.ip) == suc.addr:
                            match_suc[suc.addr] = True
                            match_state[state].add(suc)
                            matched = True
                    except (SimUnsatError, SimSolverModeError, ZeroDivisionError):
                        # ignore
                        matched = matched
                if not matched:
                    break

            # whether all final states could be matched to a successor and vice versa
            matches = len(match_suc) == len(successing_nodes) and len(match_state) == len(final_states)

            for state in final_states:
                if state.history.jumpkind == 'Ijk_FakeRet' and len(final_states) > 1:
                    # Skip fakerets if there are other control flow transitions available
                    continue

                new_call_depth = call_depth
                if state.history.jumpkind == 'Ijk_Call':
                    new_call_depth += 1
                elif state.history.jumpkind == 'Ijk_Ret':
                    new_call_depth -= 1

                if self._call_depth is not None and call_depth > self._call_depth:
                    l.debug('Do not trace into %s due to the call depth limit', state.ip)
                    continue

                new_defs = self._track(state, live_defs, node.irsb.statements if node.irsb is not None else None)

                #corresponding_successors = [n for n in successing_nodes if
                #                            not state.ip.symbolic and n.addr == state.solver.eval(state.ip)]
                #if not corresponding_successors:
                #    continue

                changed = False

                # if every successor can be matched with one or more final states (by IP address),
                # only take over the LiveDefinition of matching states
                if matches:
                    add_state_to_sucs = match_state[state]
                else:
                    add_state_to_sucs = successing_nodes

                for successing_node in add_state_to_sucs:

                    if (state.history.jumpkind == 'Ijk_Call' or state.history.jumpkind.startswith('Ijk_Sys')) and \
                            (state.ip.symbolic or successing_node.addr != state.solver.eval(state.ip)):
                        suc_new_defs = self._filter_defs_at_call_sites(new_defs)
                    else:
                        suc_new_defs = new_defs

                    if successing_node in live_defs_per_node:
                        defs_for_next_node = live_defs_per_node[successing_node]
                    else:
                        defs_for_next_node = LiveDefinitions()
                        live_defs_per_node[successing_node] = defs_for_next_node

                    for var, code_loc_set in suc_new_defs.items():
                        # l.debug("Adding %d new definitions for variable %s.", len(code_loc_set), var)
                        changed |= defs_for_next_node.add_defs(var, code_loc_set)

                if changed:
                    if (self._call_depth is None) or \
                            (self._call_depth is not None and 0 <= new_call_depth <= self._call_depth):
                        # Put all reachable successors back to our work-list again
                        for successor in self._cfg.model.get_all_successors(node):
                            nw = DDGJob(successor, new_call_depth)
                            self._worklist_append(nw, worklist, worklist_set)
def _construct ( self ) : worklist = [ ] worklist_set = set ( ) # Initialize the worklist if self . _start is None : # initial nodes are those nodes in CFG that has no in-degrees for n in self . _cfg . graph . nodes ( ) : if self . _cfg . graph . in_degree ( n ) == 0 : # Put it into the worklist job = DDGJob ( n , 0 ) self . _worklist_append ( job , worklist , worklist_set ) else : for n in self . _cfg . model . get_all_nodes ( self . _start ) : job = DDGJob ( n , 0 ) self . _worklist_append ( job , worklist , worklist_set ) # A dict storing defs set # DDGJob -> LiveDefinition live_defs_per_node = { } while worklist : # Pop out a node ddg_job = worklist [ 0 ] l . debug ( "Processing %s." , ddg_job ) node , call_depth = ddg_job . cfg_node , ddg_job . call_depth worklist = worklist [ 1 : ] worklist_set . remove ( node ) # Grab all final states. There are usually more than one (one state for each successor), and we gotta # process all of them final_states = node . final_states if node in live_defs_per_node : live_defs = live_defs_per_node [ node ] else : live_defs = LiveDefinitions ( ) live_defs_per_node [ node ] = live_defs successing_nodes = list ( self . _cfg . graph . successors ( node ) ) # try to assign every final state to a successor and vice versa match_suc = defaultdict ( bool ) match_state = defaultdict ( set ) for suc in successing_nodes : matched = False for state in final_states : try : if state . solver . eval ( state . ip ) == suc . addr : match_suc [ suc . addr ] = True match_state [ state ] . add ( suc ) matched = True except ( SimUnsatError , SimSolverModeError , ZeroDivisionError ) : # ignore matched = matched if not matched : break # whether all final states could be matched to a successor and vice versa matches = len ( match_suc ) == len ( successing_nodes ) and len ( match_state ) == len ( final_states ) for state in final_states : if state . history . jumpkind == 'Ijk_FakeRet' and len ( final_states ) > 1 : # Skip fakerets if there are other control flow transitions available continue new_call_depth = call_depth if state . history . jumpkind == 'Ijk_Call' : new_call_depth += 1 elif state . history . jumpkind == 'Ijk_Ret' : new_call_depth -= 1 if self . _call_depth is not None and call_depth > self . _call_depth : l . debug ( 'Do not trace into %s due to the call depth limit' , state . ip ) continue new_defs = self . _track ( state , live_defs , node . irsb . statements if node . irsb is not None else None ) #corresponding_successors = [n for n in successing_nodes if #                            not state.ip.symbolic and n.addr == state.solver.eval(state.ip)] #if not corresponding_successors: #    continue changed = False # if every successor can be matched with one or more final states (by IP address), # only take over the LiveDefinition of matching states if matches : add_state_to_sucs = match_state [ state ] else : add_state_to_sucs = successing_nodes for successing_node in add_state_to_sucs : if ( state . history . jumpkind == 'Ijk_Call' or state . history . jumpkind . startswith ( 'Ijk_Sys' ) ) and ( state . ip . symbolic or successing_node . addr != state . solver . eval ( state . ip ) ) : suc_new_defs = self . _filter_defs_at_call_sites ( new_defs ) else : suc_new_defs = new_defs if successing_node in live_defs_per_node : defs_for_next_node = live_defs_per_node [ successing_node ] else : defs_for_next_node = LiveDefinitions ( ) live_defs_per_node [ successing_node ] = defs_for_next_node for var , code_loc_set in suc_new_defs . items ( ) : # l.debug("Adding %d new definitions for variable %s.", len(code_loc_set), var) changed |= defs_for_next_node . add_defs ( var , code_loc_set ) if changed : if ( self . _call_depth is None ) or ( self . _call_depth is not None and 0 <= new_call_depth <= self . _call_depth ) : # Put all reachable successors back to our work-list again for successor in self . _cfg . model . get_all_successors ( node ) : nw = DDGJob ( successor , new_call_depth ) self . _worklist_append ( nw , worklist , worklist_set )