586 lines · python
1# DExTer : Debugging Experience Tester2# ~~~~~~ ~ ~~ ~ ~~3#4# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5# See https://llvm.org/LICENSE.txt for license information.6# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7"""Calculate a 'score' based on some dextIR.8Assign penalties based on different commands to decrease the score.91.000 would be a perfect score.100.000 is the worst theoretical score possible.11"""12 13from collections import defaultdict, namedtuple, Counter14import difflib15import os16from itertools import groupby17from dex.command.StepValueInfo import StepValueInfo18from dex.command.commands.DexExpectWatchBase import format_address19 20 21PenaltyCommand = namedtuple("PenaltyCommand", ["pen_dict", "max_penalty"])22# 'meta' field used in different ways by different things23PenaltyInstance = namedtuple("PenaltyInstance", ["meta", "the_penalty"])24 25 26def add_heuristic_tool_arguments(parser):27 parser.add_argument(28 "--penalty-variable-optimized",29 type=int,30 default=3,31 help="set the penalty multiplier for each"32 " occurrence of a variable that was optimized"33 " away",34 metavar="<int>",35 )36 parser.add_argument(37 "--penalty-misordered-values",38 type=int,39 default=3,40 help="set the penalty multiplier for each" " occurrence of a misordered value.",41 metavar="<int>",42 )43 parser.add_argument(44 "--penalty-irretrievable",45 type=int,46 default=4,47 help="set the penalty multiplier for each"48 " occurrence of a variable that couldn't"49 " be retrieved",50 metavar="<int>",51 )52 parser.add_argument(53 "--penalty-not-evaluatable",54 type=int,55 default=5,56 help="set the penalty multiplier for each"57 " occurrence of a variable that couldn't"58 " be evaluated",59 metavar="<int>",60 )61 parser.add_argument(62 "--penalty-missing-values",63 type=int,64 default=6,65 help="set the penalty multiplier for each missing" " value",66 metavar="<int>",67 )68 parser.add_argument(69 "--penalty-incorrect-values",70 type=int,71 default=7,72 help="set the penalty multiplier for each"73 " occurrence of an unexpected value.",74 metavar="<int>",75 )76 parser.add_argument(77 "--penalty-unreachable",78 type=int,79 default=4, # XXX XXX XXX selected by random80 help="set the penalty for each line stepped onto that should"81 " have been unreachable.",82 metavar="<int>",83 )84 parser.add_argument(85 "--penalty-misordered-steps",86 type=int,87 default=2, # XXX XXX XXX selected by random88 help="set the penalty for differences in the order of steps"89 " the program was expected to observe.",90 metavar="<int>",91 )92 parser.add_argument(93 "--penalty-missing-step",94 type=int,95 default=4, # XXX XXX XXX selected by random96 help="set the penalty for the program skipping over a step.",97 metavar="<int>",98 )99 parser.add_argument(100 "--penalty-incorrect-program-state",101 type=int,102 default=4, # XXX XXX XXX selected by random103 help="set the penalty for the program never entering an expected state"104 " or entering an unexpected state.",105 metavar="<int>",106 )107 108 109class PenaltyLineRanges:110 def __init__(self, first_step, penalty):111 self.ranges = [(first_step, first_step)]112 self.penalty = penalty113 114 def add_step(self, next_step, penalty):115 last_range = self.ranges[-1]116 last_step = last_range[1]117 if next_step == last_step + 1:118 self.ranges[-1] = (last_range[0], next_step)119 else:120 self.ranges.append((next_step, next_step))121 self.penalty += penalty122 123 def __str__(self):124 range_to_str = lambda r: str(r[0]) if r[0] == r[1] else f"{r[0]}-{r[1]}"125 if self.ranges[0][0] == self.ranges[-1][1]:126 text = f"step {self.ranges[0][0]}"127 else:128 step_list = ", ".join([range_to_str(r) for r in self.ranges])129 text = f"steps [{step_list}]"130 if self.penalty:131 text += " <r>[-{}]</>".format(self.penalty)132 return text133 134 135class Heuristic(object):136 def __init__(self, context, steps):137 self.context = context138 self.penalties = {}139 self.address_resolutions = {}140 141 worst_penalty = max(142 [143 self.penalty_variable_optimized,144 self.penalty_irretrievable,145 self.penalty_not_evaluatable,146 self.penalty_incorrect_values,147 self.penalty_missing_values,148 self.penalty_unreachable,149 self.penalty_missing_step,150 self.penalty_misordered_steps,151 ]152 )153 154 # Before evaluating scoring commands, evaluate address values.155 try:156 for command in steps.commands["DexDeclareAddress"]:157 command.address_resolutions = self.address_resolutions158 command.eval(steps)159 except KeyError:160 pass161 162 # Get DexExpectWatchType results.163 try:164 for command in steps.commands["DexExpectWatchType"]:165 command.eval(steps)166 maximum_possible_penalty = min(3, len(command.values)) * worst_penalty167 name, p = self._calculate_expect_watch_penalties(168 command, maximum_possible_penalty169 )170 name = name + " ExpectType"171 self.penalties[name] = PenaltyCommand(p, maximum_possible_penalty)172 except KeyError:173 pass174 175 # Get DexExpectWatchValue results.176 try:177 for command in steps.commands["DexExpectWatchValue"]:178 command.address_resolutions = self.address_resolutions179 command.eval(steps)180 maximum_possible_penalty = min(3, len(command.values)) * worst_penalty181 name, p = self._calculate_expect_watch_penalties(182 command, maximum_possible_penalty183 )184 name = name + " ExpectValue"185 self.penalties[name] = PenaltyCommand(p, maximum_possible_penalty)186 except KeyError:187 pass188 189 try:190 penalties = defaultdict(list)191 maximum_possible_penalty_all = 0192 for expect_state in steps.commands["DexExpectProgramState"]:193 success = expect_state.eval(steps)194 p = 0 if success else self.penalty_incorrect_program_state195 196 meta = "expected {}: {}".format(197 "{} times".format(expect_state.times)198 if expect_state.times >= 0199 else "at least once",200 expect_state.program_state_text,201 )202 203 if success:204 meta = "<g>{}</>".format(meta)205 206 maximum_possible_penalty = self.penalty_incorrect_program_state207 maximum_possible_penalty_all += maximum_possible_penalty208 name = expect_state.program_state_text209 penalties[meta] = [210 PenaltyInstance("{} times".format(len(expect_state.encounters)), p)211 ]212 self.penalties["expected program states"] = PenaltyCommand(213 penalties, maximum_possible_penalty_all214 )215 except KeyError:216 pass217 218 # Get the total number of each step kind.219 step_kind_counts = defaultdict(int)220 for step in getattr(steps, "steps"):221 step_kind_counts[step.step_kind] += 1222 223 # Get DexExpectStepKind results.224 penalties = defaultdict(list)225 maximum_possible_penalty_all = 0226 try:227 for command in steps.commands["DexExpectStepKind"]:228 command.eval()229 # Cap the penalty at 2 * expected count or else 1230 maximum_possible_penalty = max(command.count * 2, 1)231 p = abs(command.count - step_kind_counts[command.name])232 actual_penalty = min(p, maximum_possible_penalty)233 key = (234 "{}".format(command.name)235 if actual_penalty236 else "<g>{}</>".format(command.name)237 )238 penalties[key] = [PenaltyInstance(p, actual_penalty)]239 maximum_possible_penalty_all += maximum_possible_penalty240 self.penalties["step kind differences"] = PenaltyCommand(241 penalties, maximum_possible_penalty_all242 )243 except KeyError:244 pass245 246 if "DexUnreachable" in steps.commands:247 cmds = steps.commands["DexUnreachable"]248 unreach_count = 0249 250 # Find steps with unreachable in them251 ureachs = [s for s in steps.steps if "DexUnreachable" in s.watches.keys()]252 253 # There's no need to match up cmds with the actual watches254 upen = self.penalty_unreachable255 256 count = upen * len(ureachs)257 if count != 0:258 d = dict()259 for x in ureachs:260 msg = "line {} reached".format(x.current_location.lineno)261 d[msg] = [PenaltyInstance(upen, upen)]262 else:263 d = {"<g>No unreachable lines seen</>": [PenaltyInstance(0, 0)]}264 total = PenaltyCommand(d, len(cmds) * upen)265 266 self.penalties["unreachable lines"] = total267 268 if "DexExpectStepOrder" in steps.commands:269 cmds = steps.commands["DexExpectStepOrder"]270 271 # Form a list of which line/cmd we _should_ have seen272 cmd_num_lst = [(x, c.get_line()) for c in cmds for x in c.sequence]273 # Order them by the sequence number274 cmd_num_lst.sort(key=lambda t: t[0])275 # Strip out sequence key276 cmd_num_lst = [y for x, y in cmd_num_lst]277 278 # Now do the same, but for the actually observed lines/cmds279 ss = steps.steps280 deso = [s for s in ss if "DexExpectStepOrder" in s.watches.keys()]281 deso = [s.watches["DexExpectStepOrder"] for s in deso]282 # We rely on the steps remaining in order here283 order_list = [int(x.expression) for x in deso]284 285 # First off, check to see whether or not there are missing items286 expected = Counter(cmd_num_lst)287 seen = Counter(order_list)288 289 unseen_line_dict = dict()290 skipped_line_dict = dict()291 292 mispen = self.penalty_missing_step293 num_missing = 0294 num_repeats = 0295 for k, v in expected.items():296 if k not in seen:297 msg = "Line {} not seen".format(k)298 unseen_line_dict[msg] = [PenaltyInstance(mispen, mispen)]299 num_missing += v300 elif v > seen[k]:301 msg = "Line {} skipped at least once".format(k)302 skipped_line_dict[msg] = [PenaltyInstance(mispen, mispen)]303 num_missing += v - seen[k]304 elif v < seen[k]:305 # Don't penalise unexpected extra sightings of a line306 # for now307 num_repeats = seen[k] - v308 pass309 310 if len(unseen_line_dict) == 0:311 pi = PenaltyInstance(0, 0)312 unseen_line_dict["<g>All lines were seen</>"] = [pi]313 314 if len(skipped_line_dict) == 0:315 pi = PenaltyInstance(0, 0)316 skipped_line_dict["<g>No lines were skipped</>"] = [pi]317 318 total = PenaltyCommand(unseen_line_dict, len(expected) * mispen)319 self.penalties["Unseen lines"] = total320 total = PenaltyCommand(skipped_line_dict, len(expected) * mispen)321 self.penalties["Skipped lines"] = total322 323 ordpen = self.penalty_misordered_steps324 cmd_num_lst = [str(x) for x in cmd_num_lst]325 order_list = [str(x) for x in order_list]326 lst = list(difflib.Differ().compare(cmd_num_lst, order_list))327 diff_detail = Counter(l[0] for l in lst)328 329 assert "?" not in diff_detail330 331 # Diffs are hard to interpret; there are many algorithms for332 # condensing them. Ignore all that, and just print out the changed333 # sequences, it's up to the user to interpret what's going on.334 335 def filt_lines(s, seg, e, key):336 lst = [s]337 for x in seg:338 if x[0] == key:339 lst.append(int(x[2:]))340 lst.append(e)341 return lst342 343 diff_msgs = dict()344 345 def reportdiff(start_idx, segment, end_idx):346 msg = "Order mismatch, expected linenos {}, saw {}"347 expected_linenos = filt_lines(start_idx, segment, end_idx, "-")348 seen_linenos = filt_lines(start_idx, segment, end_idx, "+")349 msg = msg.format(expected_linenos, seen_linenos)350 diff_msgs[msg] = [PenaltyInstance(ordpen, ordpen)]351 352 # Group by changed segments.353 start_expt_step = 0354 end_expt_step = 0355 to_print_lst = []356 for k, subit in groupby(lst, lambda x: x[0] == " "):357 if k: # Whitespace group358 nochanged = [x for x in subit]359 end_expt_step = int(nochanged[0][2:])360 if len(to_print_lst) > 0:361 reportdiff(start_expt_step, to_print_lst, end_expt_step)362 start_expt_step = int(nochanged[-1][2:])363 to_print_lst = []364 else: # Diff group, save for printing365 to_print_lst = [x for x in subit]366 367 # If there was a dangling different step, print that too.368 if len(to_print_lst) > 0:369 reportdiff(start_expt_step, to_print_lst, "[End]")370 371 if len(diff_msgs) == 0:372 diff_msgs["<g>No lines misordered</>"] = [PenaltyInstance(0, 0)]373 total = PenaltyCommand(diff_msgs, len(cmd_num_lst) * ordpen)374 self.penalties["Misordered lines"] = total375 376 return377 378 def _calculate_expect_watch_penalties(self, c, maximum_possible_penalty):379 penalties = defaultdict(list)380 381 if c.line_range[0] == c.line_range[-1]:382 line_range = str(c.line_range[0])383 else:384 line_range = "{}-{}".format(c.line_range[0], c.line_range[-1])385 386 name = "{}:{} [{}]".format(os.path.basename(c.path), line_range, c.expression)387 388 num_actual_watches = len(c.expected_watches) + len(c.unexpected_watches)389 390 penalty_available = maximum_possible_penalty391 392 # Only penalize for missing values if we have actually seen a watch393 # that's returned us an actual value at some point, or if we've not394 # encountered the value at all.395 if num_actual_watches or c.times_encountered == 0:396 for v in c.missing_values:397 current_penalty = min(penalty_available, self.penalty_missing_values)398 penalty_available -= current_penalty399 penalties["missing values"].append(PenaltyInstance(v, current_penalty))400 401 for v in c.encountered_values:402 penalties["<g>expected encountered watches</>"].append(403 PenaltyInstance(v, 0)404 )405 406 penalty_descriptions = [407 (self.penalty_not_evaluatable, c.invalid_watches, "could not evaluate"),408 (409 self.penalty_variable_optimized,410 c.optimized_out_watches,411 "result optimized away",412 ),413 (self.penalty_misordered_values, c.misordered_watches, "misordered result"),414 (415 self.penalty_irretrievable,416 c.irretrievable_watches,417 "result could not be retrieved",418 ),419 (self.penalty_incorrect_values, c.unexpected_watches, "unexpected result"),420 ]421 422 for penalty_score, watches, description in penalty_descriptions:423 # We only penalize the encountered issue for each missing value per424 # command but we still want to record each one, so set the penalty425 # to 0 after the threshold is passed.426 times_to_penalize = len(c.missing_values)427 428 for w in watches:429 times_to_penalize -= 1430 penalty_score = min(penalty_available, penalty_score)431 penalty_available -= penalty_score432 penalties[description].append(PenaltyInstance(w, penalty_score))433 if not times_to_penalize:434 penalty_score = 0435 436 return name, penalties437 438 @property439 def penalty(self):440 result = 0441 442 maximum_allowed_penalty = 0443 for name, pen_cmd in self.penalties.items():444 maximum_allowed_penalty += pen_cmd.max_penalty445 value = pen_cmd.pen_dict446 for category, inst_list in value.items():447 result += sum(x.the_penalty for x in inst_list)448 return min(result, maximum_allowed_penalty)449 450 @property451 def max_penalty(self):452 return sum(p_cat.max_penalty for p_cat in self.penalties.values())453 454 @property455 def score(self):456 try:457 return 1.0 - (self.penalty / float(self.max_penalty))458 except ZeroDivisionError:459 return float("nan")460 461 @property462 def summary_string(self):463 score = self.score464 isnan = score != score # pylint: disable=comparison-with-itself465 color = "g"466 if score < 0.25 or isnan:467 color = "r"468 elif score < 0.75:469 color = "y"470 471 return "<{}>({:.4f})</>".format(color, score)472 473 @property474 def verbose_output(self): # noqa475 string = ""476 477 # Add address resolutions if present.478 if self.address_resolutions:479 if self.resolved_addresses:480 string += "\nResolved Addresses:\n"481 for addr, res in self.resolved_addresses.items():482 string += f" '{addr}': {res}\n"483 if self.unresolved_addresses:484 string += "\n"485 string += f"Unresolved Addresses:\n {self.unresolved_addresses}\n"486 487 string += "\n"488 for command in sorted(self.penalties):489 pen_cmd = self.penalties[command]490 maximum_possible_penalty = pen_cmd.max_penalty491 total_penalty = 0492 lines = []493 for category in sorted(pen_cmd.pen_dict):494 lines.append(" <r>{}</>:\n".format(category))495 496 step_value_results = {}497 for result, penalty in pen_cmd.pen_dict[category]:498 if not isinstance(result, StepValueInfo):499 continue500 if result.expected_value not in step_value_results:501 step_value_results[result.expected_value] = PenaltyLineRanges(502 result.step_index, penalty503 )504 else:505 step_value_results[result.expected_value].add_step(506 result.step_index, penalty507 )508 509 for value, penalty_line_range in step_value_results.items():510 text = f"({value}): {penalty_line_range}"511 total_penalty += penalty_line_range.penalty512 lines.append(" {}\n".format(text))513 514 for result, penalty in pen_cmd.pen_dict[category]:515 if isinstance(result, StepValueInfo):516 continue517 else:518 text = str(result)519 if penalty:520 assert penalty > 0, penalty521 total_penalty += penalty522 text += " <r>[-{}]</>".format(penalty)523 lines.append(" {}\n".format(text))524 525 lines.append("\n")526 527 string += " <b>{}</> <y>[{}/{}]</>\n".format(528 command, total_penalty, maximum_possible_penalty529 )530 for line in lines:531 string += line532 string += "\n"533 return string534 535 @property536 def resolved_addresses(self):537 return {538 addr: format_address(res)539 for addr, res in self.address_resolutions.items()540 if res is not None541 }542 543 @property544 def unresolved_addresses(self):545 return [addr for addr, res in self.address_resolutions.items() if res is None]546 547 @property548 def penalty_variable_optimized(self):549 return self.context.options.penalty_variable_optimized550 551 @property552 def penalty_irretrievable(self):553 return self.context.options.penalty_irretrievable554 555 @property556 def penalty_not_evaluatable(self):557 return self.context.options.penalty_not_evaluatable558 559 @property560 def penalty_incorrect_values(self):561 return self.context.options.penalty_incorrect_values562 563 @property564 def penalty_missing_values(self):565 return self.context.options.penalty_missing_values566 567 @property568 def penalty_misordered_values(self):569 return self.context.options.penalty_misordered_values570 571 @property572 def penalty_unreachable(self):573 return self.context.options.penalty_unreachable574 575 @property576 def penalty_missing_step(self):577 return self.context.options.penalty_missing_step578 579 @property580 def penalty_misordered_steps(self):581 return self.context.options.penalty_misordered_steps582 583 @property584 def penalty_incorrect_program_state(self):585 return self.context.options.penalty_incorrect_program_state586