[docs]classUniqueSearch(ExplorationTechnique):""" Unique Search. Will only keep one path active at a time, any others will be deferred. The state that is explored depends on how unique it is relative to the other deferred states. A path's uniqueness is determined by its average similarity between the other (deferred) paths. Similarity is calculated based on the supplied `similarity_func`, which by default is: The (L2) distance between the counts of the state addresses in the history of the path. """
[docs]def__init__(self,similarity_func=None,deferred_stash="deferred"):""" :param similarity_func: How to calculate similarity between two states. :param deferred_stash: Where to store the deferred states. """super().__init__()self.similarity_func=similarity_funcorUniqueSearch.similarityself.deferred_stash=deferred_stashself.uniqueness={}self.num_deadended=0
[docs]defstep(self,simgr,stash="active",**kwargs):simgr=simgr.step(stash=stash,**kwargs)old_states=simgr.stashes[self.deferred_stash][:]new_states=simgr.stashes[stash][:]simgr.move(from_stash=stash,to_stash=self.deferred_stash)defupdate_average(state,new,mem=1.0):""" param state: The state to update the average for. param new: The new value to be accumulated into the average. param mem: Memory parameter to determine how to weight the past average. """prev,size=self.uniqueness[state]new_average=float(prev*(size**mem)+new)/((size**mem)+1)self.uniqueness[state]=new_average,size+1forstate_ainnew_states:self.uniqueness[state_a]=0,0forstate_binold_states:# Update similarity averages between new and old statessimilarity=self.similarity_func(state_a,state_b)update_average(state_a,similarity)update_average(state_b,similarity)forstate_bin(sforsinnew_statesifsisnotstate_a):# Update similarity averages between new statessimilarity=self.similarity_func(state_a,state_b)update_average(state_a,similarity)forstate_ainsimgr.stashes[self.deferred_stash]:forstate_binsimgr.deadended[self.num_deadended:]:# Update similarity averages between all states and newly deadended statessimilarity=self.similarity_func(state_a,state_b)update_average(state_a,similarity)self.num_deadended=len(simgr.deadended)ifself.uniqueness:unique_state=min(self.uniqueness.items(),key=lambdae:e[1])[0]delself.uniqueness[unique_state]simgr.move(from_stash=self.deferred_stash,to_stash=stash,filter_func=lambdas:sisunique_state)returnsimgr
[docs]@staticmethoddefsimilarity(state_a,state_b):""" The (L2) distance between the counts of the state addresses in the history of the path. :param state_a: The first state to compare :param state_b: The second state to compare """count_a=Counter(state_a.history.bbl_addrs)count_b=Counter(state_b.history.bbl_addrs)normal_distance=(sum((count_a.get(addr,0)-count_b.get(addr,0))**2foraddrinset(list(count_a.keys())+list(count_b.keys())))**0.5)return1.0/(1+normal_distance)
[docs]@staticmethoddefsequence_matcher_similarity(state_a,state_b):""" The `difflib.SequenceMatcher` ratio between the state addresses in the history of the path. :param state_a: The first state to compare :param state_b: The second state to compare """addrs_a=tuple(state_a.history.bbl_addrs)addrs_b=tuple(state_b.history.bbl_addrs)returnSequenceMatcher(a=addrs_a,b=addrs_b).ratio()