[docs]classStochasticSearch(ExplorationTechnique):""" Stochastic Search. Will only keep one path active at a time, any others will be discarded. Before each pass through, weights are randomly assigned to each basic block. These weights form a probability distribution for determining which state remains after splits. When we run out of active paths to step, we start again from the start state. """
[docs]def__init__(self,start_state,restart_prob=0.0001):""" :param start_state: The initial state from which exploration stems. :param restart_prob: The probability of randomly restarting the search (default 0.0001). """super().__init__()self.start_state=start_stateself.restart_prob=restart_probself._random=random.Random()self._random.seed(42)self.affinity=defaultdict(self._random.random)
[docs]defstep(self,simgr,stash="active",**kwargs):simgr=simgr.step(stash=stash,**kwargs)ifnotsimgr.stashes[stash]orself._random.random()<self.restart_prob:simgr.stashes[stash]=[self.start_state]self.affinity.clear()iflen(simgr.stashes[stash])>=2:defweighted_pick(states):""" param states: Diverging states. """assertlen(states)>=2total_weight=sum(self.affinity[s.addr]forsinstates)selected=self._random.uniform(0,total_weight)i=0fori,stateinenumerate(states):weight=self.affinity[state.addr]ifselected<weight:breakelse:selected-=weightpicked=states[i]returnpickedsimgr.stashes[stash]=[weighted_pick(simgr.stashes[stash])]returnsimgr