cross-project-tests/debuginfo-tests/dexter/dex/heuristic/Heuristic.py

   1 # DExTer : Debugging Experience Tester
   2 # ~~~~~~   ~         ~~         ~   ~~
   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-exception
   7 """Calculate a 'score' based on some dextIR.
   8 Assign penalties based on different commands to decrease the score.
   9 1.000 would be a perfect score.
  10 0.000 is the worst theoretical score possible.
  11 """
  12
  13 from collections import defaultdict, namedtuple, Counter
  14 import difflib
  15 import os
  16 from itertools import groupby
  17 from dex.command.StepValueInfo import StepValueInfo
  18 from dex.command.commands.DexExpectWatchBase import format_address
  19
  20
  21 PenaltyCommand = namedtuple("PenaltyCommand", ["pen_dict", "max_penalty"])
  22 # 'meta' field used in different ways by different things
  23 PenaltyInstance = namedtuple("PenaltyInstance", ["meta", "the_penalty"])
  24
  25
  26 def 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 random
  80         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 random
  88         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 random
  96         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 random
 103         help="set the penalty for the program never entering an expected state"
 104         " or entering an unexpected state.",
 105         metavar="<int>",
 106     )
 107
 108
 109 class PenaltyLineRanges:
 110     def __init__(self, first_step, penalty):
 111         self.ranges = [(first_step, first_step)]
 112         self.penalty = penalty
 113
 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 += penalty
 122
 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 text
 133
 134
 135 class Heuristic(object):
 136     def __init__(self, context, steps):
 137         self.context = context
 138         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_resolutions
 158                 command.eval(steps)
 159         except KeyError:
 160             pass
 161
 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_penalty
 167                 name, p = self._calculate_expect_watch_penalties(
 168                     command, maximum_possible_penalty
 169                 )
 170                 name = name + " ExpectType"
 171                 self.penalties[name] = PenaltyCommand(p, maximum_possible_penalty)
 172         except KeyError:
 173             pass
 174
 175         # Get DexExpectWatchValue results.
 176         try:
 177             for command in steps.commands["DexExpectWatchValue"]:
 178                 command.address_resolutions = self.address_resolutions
 179                 command.eval(steps)
 180                 maximum_possible_penalty = min(3, len(command.values)) * worst_penalty
 181                 name, p = self._calculate_expect_watch_penalties(
 182                     command, maximum_possible_penalty
 183                 )
 184                 name = name + " ExpectValue"
 185                 self.penalties[name] = PenaltyCommand(p, maximum_possible_penalty)
 186         except KeyError:
 187             pass
 188
 189         try:
 190             penalties = defaultdict(list)
 191             maximum_possible_penalty_all = 0
 192             for expect_state in steps.commands["DexExpectProgramState"]:
 193                 success = expect_state.eval(steps)
 194                 p = 0 if success else self.penalty_incorrect_program_state
 195
 196                 meta = "expected {}: {}".format(
 197                     "{} times".format(expect_state.times)
 198                     if expect_state.times >= 0
 199                     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_state
 207                 maximum_possible_penalty_all += maximum_possible_penalty
 208                 name = expect_state.program_state_text
 209                 penalties[meta] = [
 210                     PenaltyInstance("{} times".format(len(expect_state.encounters)), p)
 211                 ]
 212             self.penalties["expected program states"] = PenaltyCommand(
 213                 penalties, maximum_possible_penalty_all
 214             )
 215         except KeyError:
 216             pass
 217
 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] += 1
 222
 223         # Get DexExpectStepKind results.
 224         penalties = defaultdict(list)
 225         maximum_possible_penalty_all = 0
 226         try:
 227             for command in steps.commands["DexExpectStepKind"]:
 228                 command.eval()
 229                 # Cap the penalty at 2 * expected count or else 1
 230                 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_penalty
 236                     else "<g>{}</>".format(command.name)
 237                 )
 238                 penalties[key] = [PenaltyInstance(p, actual_penalty)]
 239                 maximum_possible_penalty_all += maximum_possible_penalty
 240             self.penalties["step kind differences"] = PenaltyCommand(
 241                 penalties, maximum_possible_penalty_all
 242             )
 243         except KeyError:
 244             pass
 245
 246         if "DexUnreachable" in steps.commands:
 247             cmds = steps.commands["DexUnreachable"]
 248             unreach_count = 0
 249
 250             # Find steps with unreachable in them
 251             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 watches
 254             upen = self.penalty_unreachable
 255
 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"] = total
 267
 268         if "DexExpectStepOrder" in steps.commands:
 269             cmds = steps.commands["DexExpectStepOrder"]
 270
 271             # Form a list of which line/cmd we _should_ have seen
 272             cmd_num_lst = [(x, c.get_line()) for c in cmds for x in c.sequence]
 273             # Order them by the sequence number
 274             cmd_num_lst.sort(key=lambda t: t[0])
 275             # Strip out sequence key
 276             cmd_num_lst = [y for x, y in cmd_num_lst]
 277
 278             # Now do the same, but for the actually observed lines/cmds
 279             ss = steps.steps
 280             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 here
 283             order_list = [int(x.expression) for x in deso]
 284
 285             # First off, check to see whether or not there are missing items
 286             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_step
 293             num_missing = 0
 294             num_repeats = 0
 295             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 += v
 300                 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 line
 306                     # for now
 307                     num_repeats = seen[k] - v
 308                     pass
 309
 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"] = total
 320             total = PenaltyCommand(skipped_line_dict, len(expected) * mispen)
 321             self.penalties["Skipped lines"] = total
 322
 323             ordpen = self.penalty_misordered_steps
 324             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_detail
 330
 331             # Diffs are hard to interpret; there are many algorithms for
 332             # condensing them. Ignore all that, and just print out the changed
 333             # 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 lst
 342
 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 = 0
 354             end_expt_step = 0
 355             to_print_lst = []
 356             for k, subit in groupby(lst, lambda x: x[0] == " "):
 357                 if k:  # Whitespace group
 358                     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 printing
 365                     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"] = total
 375
 376         return
 377
 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_penalty
 391
 392         # Only penalize for missing values if we have actually seen a watch
 393         # that's returned us an actual value at some point, or if we've not
 394         # 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_penalty
 399                 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 per
 424             # command but we still want to record each one, so set the penalty
 425             # 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 -= 1
 430                 penalty_score = min(penalty_available, penalty_score)
 431                 penalty_available -= penalty_score
 432                 penalties[description].append(PenaltyInstance(w, penalty_score))
 433                 if not times_to_penalize:
 434                     penalty_score = 0
 435
 436         return name, penalties
 437
 438     @property
 439     def penalty(self):
 440         result = 0
 441
 442         maximum_allowed_penalty = 0
 443         for name, pen_cmd in self.penalties.items():
 444             maximum_allowed_penalty += pen_cmd.max_penalty
 445             value = pen_cmd.pen_dict
 446             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     @property
 451     def max_penalty(self):
 452         return sum(p_cat.max_penalty for p_cat in self.penalties.values())
 453
 454     @property
 455     def score(self):
 456         try:
 457             return 1.0 - (self.penalty / float(self.max_penalty))
 458         except ZeroDivisionError:
 459             return float("nan")
 460
 461     @property
 462     def summary_string(self):
 463         score = self.score
 464         isnan = score != score  # pylint: disable=comparison-with-itself
 465         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     @property
 474     def verbose_output(self):  # noqa
 475         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_penalty
 491             total_penalty = 0
 492             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                         continue
 500                     if result.expected_value not in step_value_results:
 501                         step_value_results[result.expected_value] = PenaltyLineRanges(
 502                             result.step_index, penalty
 503                         )
 504                     else:
 505                         step_value_results[result.expected_value].add_step(
 506                             result.step_index, penalty
 507                         )
 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.penalty
 512                     lines.append("      {}\n".format(text))
 513
 514                 for result, penalty in pen_cmd.pen_dict[category]:
 515                     if isinstance(result, StepValueInfo):
 516                         continue
 517                     else:
 518                         text = str(result)
 519                     if penalty:
 520                         assert penalty > 0, penalty
 521                         total_penalty += penalty
 522                         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_penalty
 529             )
 530             for line in lines:
 531                 string += line
 532         string += "\n"
 533         return string
 534
 535     @property
 536     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 None
 541         }
 542
 543     @property
 544     def unresolved_addresses(self):
 545         return [addr for addr, res in self.address_resolutions.items() if res is None]
 546
 547     @property
 548     def penalty_variable_optimized(self):
 549         return self.context.options.penalty_variable_optimized
 550
 551     @property
 552     def penalty_irretrievable(self):
 553         return self.context.options.penalty_irretrievable
 554
 555     @property
 556     def penalty_not_evaluatable(self):
 557         return self.context.options.penalty_not_evaluatable
 558
 559     @property
 560     def penalty_incorrect_values(self):
 561         return self.context.options.penalty_incorrect_values
 562
 563     @property
 564     def penalty_missing_values(self):
 565         return self.context.options.penalty_missing_values
 566
 567     @property
 568     def penalty_misordered_values(self):
 569         return self.context.options.penalty_misordered_values
 570
 571     @property
 572     def penalty_unreachable(self):
 573         return self.context.options.penalty_unreachable
 574
 575     @property
 576     def penalty_missing_step(self):
 577         return self.context.options.penalty_missing_step
 578
 579     @property
 580     def penalty_misordered_steps(self):
 581         return self.context.options.penalty_misordered_steps
 582
 583     @property
 584     def penalty_incorrect_program_state(self):
 585         return self.context.options.penalty_incorrect_program_state