1import binascii 2import functools 3import time 4import logging 5from typing import TypeVar, overload, Any, Optional 6 7from claripy import backend_manager 8 9from .plugin import SimStatePlugin 10from .sim_action_object import ast_stripping_decorator, SimActionObject 11 12l = logging.getLogger(name=__name__) 13 14#pylint:disable=unidiomatic-typecheck 15 16# 17# Timing stuff 18# 19 20_timing_enabled = False 21 22lt = logging.getLogger("angr.state_plugins.solver_timing") 23def timed_function(f): 24 if _timing_enabled: 25 @functools.wraps(f) 26 def timing_guy(*args, **kwargs): 27 the_solver = kwargs.pop('the_solver', None) 28 the_solver = args[0] if the_solver is None else the_solver 29 s = the_solver.state 30 31 start = time.time() 32 r = f(*args, **kwargs) 33 end = time.time() 34 duration = end-start 35 36 try: 37 if s.scratch.sim_procedure is None and s.scratch.bbl_addr is not None: 38 location = "bbl %#x, stmt %s (inst %s)" % ( 39 s.scratch.bbl_addr, 40 s.scratch.stmt_idx, 41 ('%s' % s.scratch.ins_addr if s.scratch.ins_addr is None else '%#x' % s.scratch.ins_addr) 42 ) 43 elif s.scratch.sim_procedure is not None: 44 location = "sim_procedure %s" % s.scratch.sim_procedure 45 else: 46 location = "unknown" 47 except Exception: #pylint:disable=broad-except 48 l.error("Got exception while generating timer message:", exc_info=True) 49 location = "unknown" 50 lt.log(int((end-start)*10), '%s took %s seconds at %s', f.__name__, round(duration, 2), location) 51 52 if 0 <= break_time < duration: 53 #pylint: disable = import-outside-toplevel 54 import ipdb; ipdb.set_trace() 55 56 return r 57 58 return timing_guy 59 else: 60 return f 61 62#pylint:disable=global-variable-undefined 63def enable_timing(): 64 global _timing_enabled 65 _timing_enabled = True 66 lt.setLevel(1) 67 68 69def disable_timing(): 70 global _timing_enabled 71 _timing_enabled = False 72 73import os 74if os.environ.get('SOLVER_TIMING', False): 75 enable_timing() 76else: 77 disable_timing() 78 79break_time = float(os.environ.get('SOLVER_BREAK_TIME', -1)) 80 81# 82# Various over-engineered crap 83# 84 85def error_converter(f): 86 @functools.wraps(f) 87 def wrapped_f(*args, **kwargs): 88 try: 89 return f(*args, **kwargs) 90 except claripy.UnsatError as e: 91 raise SimUnsatError("Got an unsat result") from e 92 except claripy.ClaripyFrontendError as e: 93 raise SimSolverModeError("Claripy threw an error") from e 94 return wrapped_f 95 96# 97# Premature optimizations 98# 99 100def _concrete_bool(e): 101 if isinstance(e, bool): 102 return e 103 elif isinstance(e, claripy.ast.Base) and e.op == 'BoolV': 104 return e.args[0] 105 elif isinstance(e, SimActionObject) and e.op == 'BoolV': 106 return e.args[0] 107 else: 108 return None 109 110def _concrete_value(e): 111 # shortcuts for speed improvement 112 if isinstance(e, (int, float, bool)): 113 return e 114 elif isinstance(e, claripy.ast.Base) and e.op in claripy.operations.leaf_operations_concrete: 115 return e.args[0] 116 elif isinstance(e, SimActionObject) and e.op in claripy.operations.leaf_operations_concrete: 117 return e.args[0] 118 else: 119 return None 120 121def concrete_path_bool(f): 122 @functools.wraps(f) 123 def concrete_shortcut_bool(self, *args, **kwargs): 124 v = _concrete_bool(args[0]) 125 if v is None: 126 return f(self, *args, **kwargs) 127 else: 128 return v 129 return concrete_shortcut_bool 130 131def concrete_path_not_bool(f): 132 @functools.wraps(f) 133 def concrete_shortcut_not_bool(self, *args, **kwargs): 134 v = _concrete_bool(args[0]) 135 if v is None: 136 return f(self, *args, **kwargs) 137 else: 138 return not v 139 return concrete_shortcut_not_bool 140 141def concrete_path_scalar(f): 142 @functools.wraps(f) 143 def concrete_shortcut_scalar(self, *args, **kwargs): 144 v = _concrete_value(args[0]) 145 if v is None: 146 return f(self, *args, **kwargs) 147 else: 148 return v 149 return concrete_shortcut_scalar 150 151def concrete_path_tuple(f): 152 @functools.wraps(f) 153 def concrete_shortcut_tuple(self, *args, **kwargs): 154 v = _concrete_value(args[0]) 155 if v is None: 156 return f(self, *args, **kwargs) 157 else: 158 return ( v, ) 159 return concrete_shortcut_tuple 160 161def concrete_path_list(f): 162 @functools.wraps(f) 163 def concrete_shortcut_list(self, *args, **kwargs): 164 v = _concrete_value(args[0]) 165 if v is None: 166 return f(self, *args, **kwargs) 167 else: 168 return [ v ] 169 return concrete_shortcut_list 170 171# 172# The main event 173# 174 175import claripy 176class SimSolver(SimStatePlugin): 177 """ 178 This is the plugin you'll use to interact with symbolic variables, creating them and evaluating them. 179 It should be available on a state as ``state.solver``. 180 181 Any top-level variable of the claripy module can be accessed as a property of this object. 182 """ 183 def __init__(self, solver=None, all_variables=None, temporal_tracked_variables=None, eternal_tracked_variables=None): #pylint:disable=redefined-outer-name 184 l.debug("Creating SimSolverClaripy.") 185 SimStatePlugin.__init__(self) 186 self._stored_solver = solver 187 self.all_variables = [] if all_variables is None else all_variables 188 self.temporal_tracked_variables = {} if temporal_tracked_variables is None else temporal_tracked_variables 189 self.eternal_tracked_variables = {} if eternal_tracked_variables is None else eternal_tracked_variables 190 191 def reload_solver(self, constraints=None): 192 """ 193 Reloads the solver. Useful when changing solver options. 194 195 :param list constraints: A new list of constraints to use in the reloaded solver instead of the current one 196 """ 197 198 if constraints is None: 199 constraints = self._solver.constraints 200 self._stored_solver = None 201 self._solver.add(constraints) 202 203 def get_variables(self, *keys): 204 """ 205 Iterate over all variables for which their tracking key is a prefix of the values provided. 206 207 Elements are a tuple, the first element is the full tracking key, the second is the symbol. 208 209 >>> list(s.solver.get_variables('mem')) 210 [(('mem', 0x1000), <BV64 mem_1000_4_64>), (('mem', 0x1008), <BV64 mem_1008_5_64>)] 211 212 >>> list(s.solver.get_variables('file')) 213 [(('file', 1, 0), <BV8 file_1_0_6_8>), (('file', 1, 1), <BV8 file_1_1_7_8>), (('file', 2, 0), <BV8 file_2_0_8_8>)] 214 215 >>> list(s.solver.get_variables('file', 2)) 216 [(('file', 2, 0), <BV8 file_2_0_8_8>)] 217 218 >>> list(s.solver.get_variables()) 219 [(('mem', 0x1000), <BV64 mem_1000_4_64>), (('mem', 0x1008), <BV64 mem_1008_5_64>), (('file', 1, 0), <BV8 file_1_0_6_8>), (('file', 1, 1), <BV8 file_1_1_7_8>), (('file', 2, 0), <BV8 file_2_0_8_8>)] 220 """ 221 for k, v in self.eternal_tracked_variables.items(): 222 if len(k) >= len(keys) and all(x == y for x, y in zip(keys, k)): 223 yield k, v 224 for k, v in self.temporal_tracked_variables.items(): 225 if k[-1] is None: 226 continue 227 if len(k) >= len(keys) and all(x == y for x, y in zip(keys, k)): 228 yield k, v 229 230 def register_variable(self, v, key, eternal=True): 231 """ 232 Register a value with the variable tracking system 233 234 :param v: The BVS to register 235 :param key: A tuple to register the variable under 236 :parma eternal: Whether this is an eternal variable, default True. If False, an incrementing counter will be 237 appended to the key. 238 """ 239 if type(key) is not tuple: 240 raise TypeError("Variable tracking key must be a tuple") 241 if eternal: 242 self.eternal_tracked_variables[key] = v 243 else: 244 self.temporal_tracked_variables = dict(self.temporal_tracked_variables) 245 ctrkey = key + (None,) 246 ctrval = self.temporal_tracked_variables.get(ctrkey, 0) + 1 247 self.temporal_tracked_variables[ctrkey] = ctrval 248 tempkey = key + (ctrval,) 249 self.temporal_tracked_variables[tempkey] = v 250 251 def describe_variables(self, v): 252 """ 253 Given an AST, iterate over all the keys of all the BVS leaves in the tree which are registered. 254 """ 255 reverse_mapping = {next(iter(var.variables)): k for k, var in self.eternal_tracked_variables.items()} 256 reverse_mapping.update({next(iter(var.variables)): k for k, var in self.temporal_tracked_variables.items() if k[-1] is not None}) 257 258 for var in v.variables: 259 if var in reverse_mapping: 260 yield reverse_mapping[var] 261 262 @property 263 def _solver(self): 264 """ 265 Creates or gets a Claripy solver, based on the state options. 266 """ 267 if self._stored_solver is not None: 268 return self._stored_solver 269 270 track = o.CONSTRAINT_TRACKING_IN_SOLVER in self.state.options 271 approximate_first = o.APPROXIMATE_FIRST in self.state.options 272 273 if o.STRINGS_ANALYSIS in self.state.options: 274 if 'smtlib_cvc4' in backend_manager.backends._backends_by_name: 275 our_backend = backend_manager.backends.smtlib_cvc4 276 elif 'smtlib_z3' in backend_manager.backends._backends_by_name: 277 our_backend = backend_manager.backends.smtlib_z3 278 elif 'smtlib_abc' in backend_manager.backends._backends_by_name: 279 our_backend = backend_manager.backends.smtlib_abc 280 else: 281 raise ValueError("Could not find suitable string solver!") 282 if o.COMPOSITE_SOLVER in self.state.options: 283 self._stored_solver = claripy.SolverComposite( 284 template_solver_string=claripy.SolverCompositeChild(backend=our_backend, track=track) 285 ) 286 elif o.ABSTRACT_SOLVER in self.state.options: 287 self._stored_solver = claripy.SolverVSA() 288 elif o.SYMBOLIC in self.state.options and o.REPLACEMENT_SOLVER in self.state.options: 289 self._stored_solver = claripy.SolverReplacement(auto_replace=False) 290 elif o.SYMBOLIC in self.state.options and o.CACHELESS_SOLVER in self.state.options: 291 self._stored_solver = claripy.SolverCacheless(track=track) 292 elif o.SYMBOLIC in self.state.options and o.COMPOSITE_SOLVER in self.state.options: 293 self._stored_solver = claripy.SolverComposite(track=track) 294 elif o.SYMBOLIC in self.state.options and any(opt in self.state.options for opt in o.approximation): 295 self._stored_solver = claripy.SolverHybrid(track=track, approximate_first=approximate_first) 296 elif o.HYBRID_SOLVER in self.state.options: 297 self._stored_solver = claripy.SolverHybrid(track=track, approximate_first=approximate_first) 298 elif o.SYMBOLIC in self.state.options: 299 self._stored_solver = claripy.Solver(track=track) 300 else: 301 self._stored_solver = claripy.SolverConcrete() 302 303 return self._stored_solver 304 305 # 306 # Get unconstrained stuff 307 # 308 def Unconstrained(self, name, bits, uninitialized=True, inspect=True, events=True, key=None, eternal=False, **kwargs): 309 """ 310 Creates an unconstrained symbol or a default concrete value (0), based on the state options. 311 312 :param name: The name of the symbol. 313 :param bits: The size (in bits) of the symbol. 314 :param uninitialized: Whether this value should be counted as an "uninitialized" value in the course of an 315 analysis. 316 :param inspect: Set to False to avoid firing SimInspect breakpoints 317 :param events: Set to False to avoid generating a SimEvent for the occasion 318 :param key: Set this to a tuple of increasingly specific identifiers (for example, 319 ``('mem', 0xffbeff00)`` or ``('file', 4, 0x20)`` to cause it to be tracked, i.e. 320 accessable through ``solver.get_variables``. 321 :param eternal: Set to True in conjunction with setting a key to cause all states with the same 322 ancestry to retrieve the same symbol when trying to create the value. If False, a 323 counter will be appended to the key. 324 325 :returns: an unconstrained symbol (or a concrete value of 0). 326 """ 327 if o.SYMBOLIC_INITIAL_VALUES in self.state.options: 328 # Return a symbolic value 329 if o.ABSTRACT_MEMORY in self.state.options: 330 l.debug("Creating new top StridedInterval") 331 r = claripy.TSI(bits=bits, name=name, uninitialized=uninitialized, **kwargs) 332 else: 333 l.debug("Creating new unconstrained BV named %s", name) 334 if o.UNDER_CONSTRAINED_SYMEXEC in self.state.options: 335 r = self.BVS(name, bits, uninitialized=uninitialized, key=key, eternal=eternal, inspect=inspect, events=events, **kwargs) 336 else: 337 r = self.BVS(name, bits, uninitialized=uninitialized, key=key, eternal=eternal, inspect=inspect, events=events, **kwargs) 338 339 return r 340 else: 341 # Return a default value, aka. 0 342 return claripy.BVV(0, bits) 343 344 def BVS(self, name, size, 345 min=None, max=None, stride=None, 346 uninitialized=False, 347 explicit_name=None, key=None, eternal=False, 348 inspect=True, events=True, 349 **kwargs): #pylint:disable=redefined-builtin 350 """ 351 Creates a bit-vector symbol (i.e., a variable). Other keyword parameters are passed directly on to the 352 constructor of claripy.ast.BV. 353 354 :param name: The name of the symbol. 355 :param size: The size (in bits) of the bit-vector. 356 :param min: The minimum value of the symbol. Note that this **only** work when using VSA. 357 :param max: The maximum value of the symbol. Note that this **only** work when using VSA. 358 :param stride: The stride of the symbol. Note that this **only** work when using VSA. 359 :param uninitialized: Whether this value should be counted as an "uninitialized" value in the course of an 360 analysis. 361 :param explicit_name: Set to True to prevent an identifier from appended to the name to ensure uniqueness. 362 :param key: Set this to a tuple of increasingly specific identifiers (for example, 363 ``('mem', 0xffbeff00)`` or ``('file', 4, 0x20)`` to cause it to be tracked, i.e. 364 accessable through ``solver.get_variables``. 365 :param eternal: Set to True in conjunction with setting a key to cause all states with the same 366 ancestry to retrieve the same symbol when trying to create the value. If False, a 367 counter will be appended to the key. 368 :param inspect: Set to False to avoid firing SimInspect breakpoints 369 :param events: Set to False to avoid generating a SimEvent for the occasion 370 371 :return: A BV object representing this symbol. 372 """ 373 374 # should this be locked for multithreading? 375 if key is not None and eternal and key in self.eternal_tracked_variables: 376 r = self.eternal_tracked_variables[key] 377 # pylint: disable=too-many-boolean-expressions 378 if size != r.length or min != r.args[1] or max != r.args[2] or stride != r.args[3] or uninitialized != r.args[4] or bool(explicit_name) ^ (r.args[0] == name): 379 l.warning("Variable %s being retrieved with differnt settings than it was tracked with", name) 380 else: 381 r = claripy.BVS(name, size, min=min, max=max, stride=stride, uninitialized=uninitialized, explicit_name=explicit_name, **kwargs) 382 if key is not None: 383 self.register_variable(r, key, eternal) 384 385 if inspect: 386 self.state._inspect('symbolic_variable', BP_AFTER, symbolic_name=next(iter(r.variables)), symbolic_size=size, symbolic_expr=r) 387 if events: 388 self.state.history.add_event('unconstrained', name=next(iter(r.variables)), bits=size, **kwargs) 389 if o.TRACK_SOLVER_VARIABLES in self.state.options: 390 self.all_variables = list(self.all_variables) 391 self.all_variables.append(r) 392 return r 393 394 # 395 # Operation passthroughs to claripy 396 # 397 398 def __getattr__(self, a): 399 f = getattr(claripy._all_operations, a) 400 if hasattr(f, '__call__'): 401 ff = error_converter(ast_stripping_decorator(f)) 402 if _timing_enabled: 403 ff = functools.partial(timed_function(ff), the_solver=self) 404 ff.__doc__ = f.__doc__ 405 return ff 406 else: 407 return f 408 409 def __dir__(self): 410 return sorted(set(dir(super(SimSolver, self)) + dir(claripy._all_operations) + dir(self.__class__))) 411 412 # 413 # Branching stuff 414 # 415 416 @SimStatePlugin.memo 417 def copy(self, memo): # pylint: disable=unused-argument 418 return type(self)(solver=self._solver.branch(), all_variables=self.all_variables, temporal_tracked_variables=self.temporal_tracked_variables, eternal_tracked_variables=self.eternal_tracked_variables) 419 420 @error_converter 421 def merge(self, others, merge_conditions, common_ancestor=None): # pylint: disable=W0613 422 merging_occurred, self._stored_solver = self._solver.merge( 423 [ oc._solver for oc in others ], merge_conditions, 424 common_ancestor=common_ancestor._solver if common_ancestor is not None else None 425 ) 426 return merging_occurred 427 428 @error_converter 429 def widen(self, others): 430 c = self.state.solver.BVS('random_widen_condition', 32) 431 merge_conditions = [ [ c == i ] for i in range(len(others)+1) ] 432 merging_occurred = self.merge(others, merge_conditions) 433 return merging_occurred 434 435 # 436 # Frontend passthroughs 437 # 438 439 def downsize(self): 440 """ 441 Frees memory associated with the constraint solver by clearing all of 442 its internal caches. 443 """ 444 self._solver.downsize() 445 446 @property 447 def constraints(self): 448 """ 449 Returns the constraints of the state stored by the solver. 450 """ 451 return self._solver.constraints 452 453 def _adjust_constraint(self, c): 454 if self.state._global_condition is None: 455 return c 456 elif c is None: # this should never happen 457 l.critical("PLEASE REPORT THIS MESSAGE, AND WHAT YOU WERE DOING, TO YAN") 458 return self.state._global_condition 459 else: 460 return self.Or(self.Not(self.state._global_condition), c) 461 462 def _adjust_constraint_list(self, constraints): 463 if self.state._global_condition is None: 464 return constraints 465 if len(constraints) == 0: 466 return constraints.__class__((self.state._global_condition,)) 467 else: 468 return constraints.__class__((self._adjust_constraint(self.And(*constraints)),)) 469 470 @timed_function 471 @ast_stripping_decorator 472 @error_converter 473 def eval_to_ast(self, e, n, extra_constraints=(), exact=None): 474 """ 475 Evaluate an expression, using the solver if necessary. Returns AST objects. 476 477 :param e: the expression 478 :param n: the number of desired solutions 479 :param extra_constraints: extra constraints to apply to the solver 480 :param exact: if False, returns approximate solutions 481 :return: a tuple of the solutions, in the form of claripy AST nodes 482 :rtype: tuple 483 """ 484 return self._solver.eval_to_ast(e, n, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=exact) 485 486 @concrete_path_tuple 487 @timed_function 488 @ast_stripping_decorator 489 @error_converter 490 def _eval(self, e, n, extra_constraints=(), exact=None): 491 """ 492 Evaluate an expression, using the solver if necessary. Returns primitives. 493 494 :param e: the expression 495 :param n: the number of desired solutions 496 :param extra_constraints: extra constraints to apply to the solver 497 :param exact: if False, returns approximate solutions 498 :return: a tuple of the solutions, in the form of Python primitives 499 :rtype: tuple 500 """ 501 return self._solver.eval(e, n, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=exact) 502 503 @concrete_path_scalar 504 @timed_function 505 @ast_stripping_decorator 506 @error_converter 507 def max(self, e, extra_constraints=(), exact=None): 508 """ 509 Return the maximum value of expression `e`. 510 511 :param e : expression (an AST) to evaluate 512 :param extra_constraints: extra constraints (as ASTs) to add to the solver for this solve 513 :param exact : if False, return approximate solutions. 514 :return: the maximum possible value of e (backend object) 515 """ 516 if exact is False and o.VALIDATE_APPROXIMATIONS in self.state.options: 517 ar = self._solver.max(e, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=False) 518 er = self._solver.max(e, extra_constraints=self._adjust_constraint_list(extra_constraints)) 519 assert er <= ar 520 return ar 521 return self._solver.max(e, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=exact) 522 523 @concrete_path_scalar 524 @timed_function 525 @ast_stripping_decorator 526 @error_converter 527 def min(self, e, extra_constraints=(), exact=None): 528 """ 529 Return the minimum value of expression `e`. 530 531 :param e : expression (an AST) to evaluate 532 :param extra_constraints: extra constraints (as ASTs) to add to the solver for this solve 533 :param exact : if False, return approximate solutions. 534 :return: the minimum possible value of e (backend object) 535 """ 536 if exact is False and o.VALIDATE_APPROXIMATIONS in self.state.options: 537 ar = self._solver.min(e, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=False) 538 er = self._solver.min(e, extra_constraints=self._adjust_constraint_list(extra_constraints)) 539 assert ar <= er 540 return ar 541 return self._solver.min(e, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=exact) 542 543 @timed_function 544 @ast_stripping_decorator 545 @error_converter 546 def solution(self, e, v, extra_constraints=(), exact=None): 547 """ 548 Return True if `v` is a solution of `expr` with the extra constraints, False otherwise. 549 550 :param e: An expression (an AST) to evaluate 551 :param v: The proposed solution (an AST) 552 :param extra_constraints: Extra constraints (as ASTs) to add to the solver for this solve. 553 :param exact: If False, return approximate solutions. 554 :return: True if `v` is a solution of `expr`, False otherwise 555 """ 556 if exact is False and o.VALIDATE_APPROXIMATIONS in self.state.options: 557 ar = self._solver.solution(e, v, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=False) 558 er = self._solver.solution(e, v, extra_constraints=self._adjust_constraint_list(extra_constraints)) 559 if er is True: 560 assert ar is True 561 return ar 562 return self._solver.solution(e, v, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=exact) 563 564 @concrete_path_bool 565 @timed_function 566 @ast_stripping_decorator 567 @error_converter 568 def is_true(self, e, extra_constraints=(), exact=None): 569 """ 570 If the expression provided is absolutely, definitely a true boolean, return True. 571 Note that returning False doesn't necessarily mean that the expression can be false, just that we couldn't 572 figure that out easily. 573 574 :param e: An expression (an AST) to evaluate 575 :param extra_constraints: Extra constraints (as ASTs) to add to the solver for this solve. 576 :param exact: If False, return approximate solutions. 577 :return: True if `v` is definitely true, False otherwise 578 """ 579 if exact is False and o.VALIDATE_APPROXIMATIONS in self.state.options: 580 ar = self._solver.is_true(e, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=False) 581 er = self._solver.is_true(e, extra_constraints=self._adjust_constraint_list(extra_constraints)) 582 if er is False: 583 assert ar is False 584 return ar 585 return self._solver.is_true(e, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=exact) 586 587 @concrete_path_not_bool 588 @timed_function 589 @ast_stripping_decorator 590 @error_converter 591 def is_false(self, e, extra_constraints=(), exact=None): 592 """ 593 If the expression provided is absolutely, definitely a false boolean, return True. 594 Note that returning False doesn't necessarily mean that the expression can be true, just that we couldn't 595 figure that out easily. 596 597 :param e: An expression (an AST) to evaluate 598 :param extra_constraints: Extra constraints (as ASTs) to add to the solver for this solve. 599 :param exact: If False, return approximate solutions. 600 :return: True if `v` is definitely false, False otherwise 601 """ 602 if exact is False and o.VALIDATE_APPROXIMATIONS in self.state.options: 603 ar = self._solver.is_false(e, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=False) 604 er = self._solver.is_false(e, extra_constraints=self._adjust_constraint_list(extra_constraints)) 605 if er is False: 606 assert ar is False 607 return ar 608 return self._solver.is_false(e, extra_constraints=self._adjust_constraint_list(extra_constraints), exact=exact) 609 610 @timed_function 611 @ast_stripping_decorator 612 @error_converter 613 def unsat_core(self, extra_constraints=()): 614 """ 615 This function returns the unsat core from the backend solver. 616 617 :param extra_constraints: Extra constraints (as ASTs) to add to the solver for this solve. 618 :return: The unsat core. 619 """ 620 if o.CONSTRAINT_TRACKING_IN_SOLVER not in self.state.options: 621 raise SimSolverOptionError('CONSTRAINT_TRACKING_IN_SOLVER must be enabled before calling unsat_core().') 622 return self._solver.unsat_core(extra_constraints=extra_constraints) 623 624 @timed_function 625 @ast_stripping_decorator 626 @error_converter 627 def satisfiable(self, extra_constraints=(), exact=None): 628 """ 629 This function does a constraint check and checks if the solver is in a sat state. 630 631 :param extra_constraints: Extra constraints (as ASTs) to add to s for this solve 632 :param exact: If False, return approximate solutions. 633 634 :return: True if sat, otherwise false 635 """ 636 if exact is False and o.VALIDATE_APPROXIMATIONS in self.state.options: 637 er = self._solver.satisfiable(extra_constraints=self._adjust_constraint_list(extra_constraints)) 638 ar = self._solver.satisfiable(extra_constraints=self._adjust_constraint_list(extra_constraints), exact=False) 639 if er is True: 640 assert ar is True 641 return ar 642 return self._solver.satisfiable(extra_constraints=self._adjust_constraint_list(extra_constraints), exact=exact) 643 644 @timed_function 645 @ast_stripping_decorator 646 @error_converter 647 def add(self, *constraints): 648 """ 649 Add some constraints to the solver. 650 651 :param constraints: Pass any constraints that you want to add (ASTs) as varargs. 652 """ 653 cc = self._adjust_constraint_list(constraints) 654 return self._solver.add(cc) 655 656 # 657 # And some convenience stuff 658 # 659 660 @staticmethod 661 def _cast_to(e, solution, cast_to): 662 """ 663 Casts a solution for the given expression to type `cast_to`. 664 665 :param e: The expression `value` is a solution for 666 :param value: The solution to be cast 667 :param cast_to: The type `value` should be cast to. Must be one of the currently supported types (bytes|int) 668 :raise ValueError: If cast_to is a currently unsupported cast target. 669 :return: The value of `solution` cast to type `cast_to` 670 """ 671 if cast_to is None: 672 return solution 673 674 if type(solution) is bool: 675 if cast_to is bytes: 676 return bytes([int(solution)]) 677 elif cast_to is int: 678 return int(solution) 679 elif type(solution) is float: 680 solution = _concrete_value(claripy.FPV(solution, claripy.fp.FSort.from_size(len(e))).raw_to_bv()) 681 682 if cast_to is bytes: 683 if len(e) == 0: 684 return b"" 685 return binascii.unhexlify('{:x}'.format(solution).zfill(len(e)//4)) 686 687 if cast_to is not int: 688 raise ValueError("cast_to parameter {!r} is not a valid cast target, currently supported are only int and bytes!".format(cast_to)) 689 690 return solution 691 692 693 @overload 694 # pylint: disable=no-self-use 695 def eval_upto(self, e, n: int, cast_to: None = ..., **kwargs) -> Any: ... 696 CastTarget = TypeVar("CastTarget") 697 @overload 698 # pylint: disable=no-self-use, undefined-variable 699 def eval_upto(self, e, n: int, cast_to: CastTarget = ..., **kwargs) -> CastTarget: ... 700 701 def eval_upto(self, e, n, cast_to = None, **kwargs): 702 """ 703 Evaluate an expression, using the solver if necessary. Returns primitives as specified by the `cast_to` 704 parameter. Only certain primitives are supported, check the implementation of `_cast_to` to see which ones. 705 706 :param e: the expression 707 :param n: the number of desired solutions 708 :param extra_constraints: extra constraints to apply to the solver 709 :param exact: if False, returns approximate solutions 710 :param cast_to: A type to cast the resulting values to 711 :return: a tuple of the solutions, in the form of Python primitives 712 :rtype: tuple 713 """ 714 concrete_val = _concrete_value(e) 715 if concrete_val is not None: 716 return [self._cast_to(e, concrete_val, cast_to)] 717 718 cast_vals = [self._cast_to(e, v, cast_to) for v in self._eval(e, n, **kwargs)] 719 if len(cast_vals) == 0: 720 raise SimUnsatError('Not satisfiable: %s, expected up to %d solutions' % (e.shallow_repr(), n)) 721 return cast_vals 722 723 @overload 724 # pylint: disable=no-self-use 725 def eval(self, e, cast_to: None = ..., **kwargs) -> Any: ... 726 727 # pylint: disable=no-self-use,undefined-variable 728 @overload 729 def eval(self, e, cast_to: CastTarget = ..., **kwargs) -> CastTarget: ... 730 731 def eval(self, e, cast_to: Optional[CastTarget] = None, **kwargs): 732 """ 733 Evaluate an expression to get any possible solution. The desired output types can be specified using the 734 `cast_to` parameter. `extra_constraints` can be used to specify additional constraints the returned values 735 must satisfy. 736 737 :param e: the expression to get a solution for 738 :param kwargs: Any additional kwargs will be passed down to `eval_upto` 739 :raise SimUnsatError: if no solution could be found satisfying the given constraints 740 :return: 741 """ 742 # eval_upto already throws the UnsatError, no reason for us to worry about it 743 return self.eval_upto(e, 1, cast_to = cast_to, **kwargs)[0] 744 745 def eval_one(self, e, **kwargs): 746 """ 747 Evaluate an expression to get the only possible solution. Errors if either no or more than one solution is 748 returned. A kwarg parameter `default` can be specified to be returned instead of failure! 749 750 :param e: the expression to get a solution for 751 :param default: A value can be passed as a kwarg here. It will be returned in case of failure. 752 :param kwargs: Any additional kwargs will be passed down to `eval_upto` 753 :raise SimUnsatError: if no solution could be found satisfying the given constraints 754 :raise SimValueError: if more than one solution was found to satisfy the given constraints 755 :return: The value for `e` 756 """ 757 try: 758 return self.eval_exact(e, 1, **{k: v for (k, v) in kwargs.items() if k != 'default'})[0] 759 except (SimUnsatError, SimValueError, SimSolverModeError): 760 if 'default' in kwargs: 761 return kwargs.pop('default') 762 raise 763 764 def eval_atmost(self, e, n, **kwargs): 765 """ 766 Evaluate an expression to get at most `n` possible solutions. Errors if either none or more than `n` solutions 767 are returned. 768 769 :param e: the expression to get a solution for 770 :param n: the inclusive upper limit on the number of solutions 771 :param kwargs: Any additional kwargs will be passed down to `eval_upto` 772 :raise SimUnsatError: if no solution could be found satisfying the given constraints 773 :raise SimValueError: if more than `n` solutions were found to satisfy the given constraints 774 :return: The solutions for `e` 775 """ 776 r = self.eval_upto(e, n+1, **kwargs) 777 if len(r) > n: 778 raise SimValueError("Concretized %d values (must be at most %d) in eval_atmost" % (len(r), n)) 779 return r 780 781 def eval_atleast(self, e, n, **kwargs): 782 """ 783 Evaluate an expression to get at least `n` possible solutions. Errors if less than `n` solutions were found. 784 785 :param e: the expression to get a solution for 786 :param n: the inclusive lower limit on the number of solutions 787 :param kwargs: Any additional kwargs will be passed down to `eval_upto` 788 :raise SimUnsatError: if no solution could be found satisfying the given constraints 789 :raise SimValueError: if less than `n` solutions were found to satisfy the given constraints 790 :return: The solutions for `e` 791 """ 792 r = self.eval_upto(e, n, **kwargs) 793 if len(r) != n: 794 raise SimValueError("Concretized %d values (must be at least %d) in eval_atleast" % (len(r), n)) 795 return r 796 797 def eval_exact(self, e, n, **kwargs): 798 """ 799 Evaluate an expression to get exactly the `n` possible solutions. Errors if any number of solutions other 800 than `n` was found to exist. 801 802 :param e: the expression to get a solution for 803 :param n: the inclusive lower limit on the number of solutions 804 :param kwargs: Any additional kwargs will be passed down to `eval_upto` 805 :raise SimUnsatError: if no solution could be found satisfying the given constraints 806 :raise SimValueError: if any number of solutions other than `n` were found to satisfy the given constraints 807 :return: The solutions for `e` 808 """ 809 r = self.eval_upto(e, n + 1, **kwargs) 810 if len(r) != n: 811 raise SimValueError("Concretized %d values (must be exactly %d) in eval_exact" % (len(r), n)) 812 return r 813 814 min_int = min 815 max_int = max 816 817 # 818 # Other methods 819 # 820 821 @timed_function 822 @ast_stripping_decorator 823 def unique(self, e, **kwargs): 824 """ 825 Returns True if the expression `e` has only one solution by querying 826 the constraint solver. It does also add that unique solution to the 827 solver's constraints. 828 """ 829 if not isinstance(e, claripy.ast.Base): 830 return True 831 832 # if we don't want to do symbolic checks, assume symbolic variables are multivalued 833 if o.SYMBOLIC not in self.state.options and self.symbolic(e): 834 return False 835 836 r = self.eval_upto(e, 2, **kwargs) 837 if len(r) == 1: 838 self.add(e == r[0]) 839 return True 840 elif len(r) == 0: 841 raise SimValueError("unsatness during uniqueness check(ness)") 842 else: 843 return False 844 845 def symbolic(self, e): # pylint:disable=R0201 846 """ 847 Returns True if the expression `e` is symbolic. 848 """ 849 if type(e) in (int, bytes, float, bool): 850 return False 851 return e.symbolic 852 853 def single_valued(self, e): 854 """ 855 Returns True whether `e` is a concrete value or is a value set with 856 only 1 possible value. This differs from `unique` in that this *does* 857 not query the constraint solver. 858 """ 859 if self.state.mode == 'static': 860 if type(e) in (int, bytes, float, bool): 861 return True 862 else: 863 return e.cardinality <= 1 864 865 else: 866 # All symbolic expressions are not single-valued 867 return not self.symbolic(e) 868 869 def simplify(self, e=None): 870 """ 871 Simplifies `e`. If `e` is None, simplifies the constraints of this 872 state. 873 """ 874 if e is None: 875 return self._solver.simplify() 876 elif isinstance(e, (int, float, bool)): 877 return e 878 elif isinstance(e, claripy.ast.Base) and e.op in claripy.operations.leaf_operations_concrete: 879 return e 880 elif isinstance(e, SimActionObject) and e.op in claripy.operations.leaf_operations_concrete: 881 return e.ast 882 elif not isinstance(e, (SimActionObject, claripy.ast.Base)): 883 return e 884 else: 885 return self._claripy_simplify(e) 886 887 @timed_function 888 @ast_stripping_decorator 889 @error_converter 890 def _claripy_simplify(self, *args): #pylint:disable=no-self-use 891 return claripy.simplify(args[0]) 892 893 def variables(self, e): #pylint:disable=no-self-use 894 """ 895 Returns the symbolic variables present in the AST of `e`. 896 """ 897 return e.variables 898 899from angr.sim_state import SimState 900SimState.register_default('solver', SimSolver) 901 902from .. import sim_options as o 903from .inspect import BP_AFTER 904from ..errors import SimValueError, SimUnsatError, SimSolverModeError, SimSolverOptionError 905