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. 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, Counter 14import difflib 15import os 16from itertools import groupby 17from dex.command.StepValueInfo import StepValueInfo 18from dex.command.commands.DexExpectWatchBase import format_address 19 20 21PenaltyCommand = namedtuple('PenaltyCommand', ['pen_dict', 'max_penalty']) 22# 'meta' field used in different ways by different things 23PenaltyInstance = 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 parser.add_argument( 36 '--penalty-misordered-values', 37 type=int, 38 default=3, 39 help='set the penalty multiplier for each' 40 ' occurrence of a misordered value.', 41 metavar='<int>') 42 parser.add_argument( 43 '--penalty-irretrievable', 44 type=int, 45 default=4, 46 help='set the penalty multiplier for each' 47 " occurrence of a variable that couldn't" 48 ' be retrieved', 49 metavar='<int>') 50 parser.add_argument( 51 '--penalty-not-evaluatable', 52 type=int, 53 default=5, 54 help='set the penalty multiplier for each' 55 " occurrence of a variable that couldn't" 56 ' be evaluated', 57 metavar='<int>') 58 parser.add_argument( 59 '--penalty-missing-values', 60 type=int, 61 default=6, 62 help='set the penalty multiplier for each missing' 63 ' value', 64 metavar='<int>') 65 parser.add_argument( 66 '--penalty-incorrect-values', 67 type=int, 68 default=7, 69 help='set the penalty multiplier for each' 70 ' occurrence of an unexpected value.', 71 metavar='<int>') 72 parser.add_argument( 73 '--penalty-unreachable', 74 type=int, 75 default=4, # XXX XXX XXX selected by random 76 help='set the penalty for each line stepped onto that should' 77 ' have been unreachable.', 78 metavar='<int>') 79 parser.add_argument( 80 '--penalty-misordered-steps', 81 type=int, 82 default=2, # XXX XXX XXX selected by random 83 help='set the penalty for differences in the order of steps' 84 ' the program was expected to observe.', 85 metavar='<int>') 86 parser.add_argument( 87 '--penalty-missing-step', 88 type=int, 89 default=4, # XXX XXX XXX selected by random 90 help='set the penalty for the program skipping over a step.', 91 metavar='<int>') 92 parser.add_argument( 93 '--penalty-incorrect-program-state', 94 type=int, 95 default=4, # XXX XXX XXX selected by random 96 help='set the penalty for the program never entering an expected state' 97 ' or entering an unexpected state.', 98 metavar='<int>') 99 100 101class PenaltyLineRanges: 102 def __init__(self, first_step, penalty): 103 self.ranges = [(first_step, first_step)] 104 self.penalty = penalty 105 106 def add_step(self, next_step, penalty): 107 last_range = self.ranges[-1] 108 last_step = last_range[1] 109 if (next_step == last_step + 1): 110 self.ranges[-1] = (last_range[0], next_step) 111 else: 112 self.ranges.append((next_step, next_step)) 113 self.penalty += penalty 114 115 def __str__(self): 116 range_to_str = lambda r: str(r[0]) if r[0] == r[1] else f'{r[0]}-{r[1]}' 117 if self.ranges[0][0] == self.ranges[-1][1]: 118 text = f'step {self.ranges[0][0]}' 119 else: 120 step_list = ', '.join([range_to_str(r) for r in self.ranges]) 121 text = f'steps [{step_list}]' 122 if self.penalty: 123 text += ' <r>[-{}]</>'.format(self.penalty) 124 return text 125 126 127class Heuristic(object): 128 def __init__(self, context, steps): 129 self.context = context 130 self.penalties = {} 131 self.address_resolutions = {} 132 133 worst_penalty = max([ 134 self.penalty_variable_optimized, self.penalty_irretrievable, 135 self.penalty_not_evaluatable, self.penalty_incorrect_values, 136 self.penalty_missing_values, self.penalty_unreachable, 137 self.penalty_missing_step, self.penalty_misordered_steps 138 ]) 139 140 # Before evaluating scoring commands, evaluate address values. 141 try: 142 for command in steps.commands['DexDeclareAddress']: 143 command.address_resolutions = self.address_resolutions 144 command.eval(steps) 145 except KeyError: 146 pass 147 148 # Get DexExpectWatchType results. 149 try: 150 for command in steps.commands['DexExpectWatchType']: 151 command.eval(steps) 152 maximum_possible_penalty = min(3, len( 153 command.values)) * worst_penalty 154 name, p = self._calculate_expect_watch_penalties( 155 command, maximum_possible_penalty) 156 name = name + ' ExpectType' 157 self.penalties[name] = PenaltyCommand(p, 158 maximum_possible_penalty) 159 except KeyError: 160 pass 161 162 # Get DexExpectWatchValue results. 163 try: 164 for command in steps.commands['DexExpectWatchValue']: 165 command.address_resolutions = self.address_resolutions 166 command.eval(steps) 167 maximum_possible_penalty = min(3, len( 168 command.values)) * worst_penalty 169 name, p = self._calculate_expect_watch_penalties( 170 command, maximum_possible_penalty) 171 name = name + ' ExpectValue' 172 self.penalties[name] = PenaltyCommand(p, 173 maximum_possible_penalty) 174 except KeyError: 175 pass 176 177 try: 178 penalties = defaultdict(list) 179 maximum_possible_penalty_all = 0 180 for expect_state in steps.commands['DexExpectProgramState']: 181 success = expect_state.eval(steps) 182 p = 0 if success else self.penalty_incorrect_program_state 183 184 meta = 'expected {}: {}'.format( 185 '{} times'.format(expect_state.times) 186 if expect_state.times >= 0 else 'at least once', 187 expect_state.program_state_text) 188 189 if success: 190 meta = '<g>{}</>'.format(meta) 191 192 maximum_possible_penalty = self.penalty_incorrect_program_state 193 maximum_possible_penalty_all += maximum_possible_penalty 194 name = expect_state.program_state_text 195 penalties[meta] = [PenaltyInstance('{} times'.format( 196 len(expect_state.encounters)), p)] 197 self.penalties['expected program states'] = PenaltyCommand( 198 penalties, maximum_possible_penalty_all) 199 except KeyError: 200 pass 201 202 # Get the total number of each step kind. 203 step_kind_counts = defaultdict(int) 204 for step in getattr(steps, 'steps'): 205 step_kind_counts[step.step_kind] += 1 206 207 # Get DexExpectStepKind results. 208 penalties = defaultdict(list) 209 maximum_possible_penalty_all = 0 210 try: 211 for command in steps.commands['DexExpectStepKind']: 212 command.eval() 213 # Cap the penalty at 2 * expected count or else 1 214 maximum_possible_penalty = max(command.count * 2, 1) 215 p = abs(command.count - step_kind_counts[command.name]) 216 actual_penalty = min(p, maximum_possible_penalty) 217 key = ('{}'.format(command.name) 218 if actual_penalty else '<g>{}</>'.format(command.name)) 219 penalties[key] = [PenaltyInstance(p, actual_penalty)] 220 maximum_possible_penalty_all += maximum_possible_penalty 221 self.penalties['step kind differences'] = PenaltyCommand( 222 penalties, maximum_possible_penalty_all) 223 except KeyError: 224 pass 225 226 if 'DexUnreachable' in steps.commands: 227 cmds = steps.commands['DexUnreachable'] 228 unreach_count = 0 229 230 # Find steps with unreachable in them 231 ureachs = [ 232 s for s in steps.steps if 'DexUnreachable' in s.watches.keys() 233 ] 234 235 # There's no need to match up cmds with the actual watches 236 upen = self.penalty_unreachable 237 238 count = upen * len(ureachs) 239 if count != 0: 240 d = dict() 241 for x in ureachs: 242 msg = 'line {} reached'.format(x.current_location.lineno) 243 d[msg] = [PenaltyInstance(upen, upen)] 244 else: 245 d = { 246 '<g>No unreachable lines seen</>': [PenaltyInstance(0, 0)] 247 } 248 total = PenaltyCommand(d, len(cmds) * upen) 249 250 self.penalties['unreachable lines'] = total 251 252 if 'DexExpectStepOrder' in steps.commands: 253 cmds = steps.commands['DexExpectStepOrder'] 254 255 # Form a list of which line/cmd we _should_ have seen 256 cmd_num_lst = [(x, c.lineno) for c in cmds 257 for x in c.sequence] 258 # Order them by the sequence number 259 cmd_num_lst.sort(key=lambda t: t[0]) 260 # Strip out sequence key 261 cmd_num_lst = [y for x, y in cmd_num_lst] 262 263 # Now do the same, but for the actually observed lines/cmds 264 ss = steps.steps 265 deso = [s for s in ss if 'DexExpectStepOrder' in s.watches.keys()] 266 deso = [s.watches['DexExpectStepOrder'] for s in deso] 267 # We rely on the steps remaining in order here 268 order_list = [int(x.expression) for x in deso] 269 270 # First off, check to see whether or not there are missing items 271 expected = Counter(cmd_num_lst) 272 seen = Counter(order_list) 273 274 unseen_line_dict = dict() 275 skipped_line_dict = dict() 276 277 mispen = self.penalty_missing_step 278 num_missing = 0 279 num_repeats = 0 280 for k, v in expected.items(): 281 if k not in seen: 282 msg = 'Line {} not seen'.format(k) 283 unseen_line_dict[msg] = [PenaltyInstance(mispen, mispen)] 284 num_missing += v 285 elif v > seen[k]: 286 msg = 'Line {} skipped at least once'.format(k) 287 skipped_line_dict[msg] = [PenaltyInstance(mispen, mispen)] 288 num_missing += v - seen[k] 289 elif v < seen[k]: 290 # Don't penalise unexpected extra sightings of a line 291 # for now 292 num_repeats = seen[k] - v 293 pass 294 295 if len(unseen_line_dict) == 0: 296 pi = PenaltyInstance(0, 0) 297 unseen_line_dict['<g>All lines were seen</>'] = [pi] 298 299 if len(skipped_line_dict) == 0: 300 pi = PenaltyInstance(0, 0) 301 skipped_line_dict['<g>No lines were skipped</>'] = [pi] 302 303 total = PenaltyCommand(unseen_line_dict, len(expected) * mispen) 304 self.penalties['Unseen lines'] = total 305 total = PenaltyCommand(skipped_line_dict, len(expected) * mispen) 306 self.penalties['Skipped lines'] = total 307 308 ordpen = self.penalty_misordered_steps 309 cmd_num_lst = [str(x) for x in cmd_num_lst] 310 order_list = [str(x) for x in order_list] 311 lst = list(difflib.Differ().compare(cmd_num_lst, order_list)) 312 diff_detail = Counter(l[0] for l in lst) 313 314 assert '?' not in diff_detail 315 316 # Diffs are hard to interpret; there are many algorithms for 317 # condensing them. Ignore all that, and just print out the changed 318 # sequences, it's up to the user to interpret what's going on. 319 320 def filt_lines(s, seg, e, key): 321 lst = [s] 322 for x in seg: 323 if x[0] == key: 324 lst.append(int(x[2:])) 325 lst.append(e) 326 return lst 327 328 diff_msgs = dict() 329 330 def reportdiff(start_idx, segment, end_idx): 331 msg = 'Order mismatch, expected linenos {}, saw {}' 332 expected_linenos = filt_lines(start_idx, segment, end_idx, '-') 333 seen_linenos = filt_lines(start_idx, segment, end_idx, '+') 334 msg = msg.format(expected_linenos, seen_linenos) 335 diff_msgs[msg] = [PenaltyInstance(ordpen, ordpen)] 336 337 # Group by changed segments. 338 start_expt_step = 0 339 end_expt_step = 0 340 to_print_lst = [] 341 for k, subit in groupby(lst, lambda x: x[0] == ' '): 342 if k: # Whitespace group 343 nochanged = [x for x in subit] 344 end_expt_step = int(nochanged[0][2:]) 345 if len(to_print_lst) > 0: 346 reportdiff(start_expt_step, to_print_lst, 347 end_expt_step) 348 start_expt_step = int(nochanged[-1][2:]) 349 to_print_lst = [] 350 else: # Diff group, save for printing 351 to_print_lst = [x for x in subit] 352 353 # If there was a dangling different step, print that too. 354 if len(to_print_lst) > 0: 355 reportdiff(start_expt_step, to_print_lst, '[End]') 356 357 if len(diff_msgs) == 0: 358 diff_msgs['<g>No lines misordered</>'] = [ 359 PenaltyInstance(0, 0) 360 ] 361 total = PenaltyCommand(diff_msgs, len(cmd_num_lst) * ordpen) 362 self.penalties['Misordered lines'] = total 363 364 return 365 366 def _calculate_expect_watch_penalties(self, c, maximum_possible_penalty): 367 penalties = defaultdict(list) 368 369 if c.line_range[0] == c.line_range[-1]: 370 line_range = str(c.line_range[0]) 371 else: 372 line_range = '{}-{}'.format(c.line_range[0], c.line_range[-1]) 373 374 name = '{}:{} [{}]'.format( 375 os.path.basename(c.path), line_range, c.expression) 376 377 num_actual_watches = len(c.expected_watches) + len( 378 c.unexpected_watches) 379 380 penalty_available = maximum_possible_penalty 381 382 # Only penalize for missing values if we have actually seen a watch 383 # that's returned us an actual value at some point, or if we've not 384 # encountered the value at all. 385 if num_actual_watches or c.times_encountered == 0: 386 for v in c.missing_values: 387 current_penalty = min(penalty_available, 388 self.penalty_missing_values) 389 penalty_available -= current_penalty 390 penalties['missing values'].append( 391 PenaltyInstance(v, current_penalty)) 392 393 for v in c.encountered_values: 394 penalties['<g>expected encountered watches</>'].append( 395 PenaltyInstance(v, 0)) 396 397 penalty_descriptions = [ 398 (self.penalty_not_evaluatable, c.invalid_watches, 399 'could not evaluate'), 400 (self.penalty_variable_optimized, c.optimized_out_watches, 401 'result optimized away'), 402 (self.penalty_misordered_values, c.misordered_watches, 403 'misordered result'), 404 (self.penalty_irretrievable, c.irretrievable_watches, 405 'result could not be retrieved'), 406 (self.penalty_incorrect_values, c.unexpected_watches, 407 'unexpected result'), 408 ] 409 410 for penalty_score, watches, description in penalty_descriptions: 411 # We only penalize the encountered issue for each missing value per 412 # command but we still want to record each one, so set the penalty 413 # to 0 after the threshold is passed. 414 times_to_penalize = len(c.missing_values) 415 416 for w in watches: 417 times_to_penalize -= 1 418 penalty_score = min(penalty_available, penalty_score) 419 penalty_available -= penalty_score 420 penalties[description].append( 421 PenaltyInstance(w, penalty_score)) 422 if not times_to_penalize: 423 penalty_score = 0 424 425 return name, penalties 426 427 @property 428 def penalty(self): 429 result = 0 430 431 maximum_allowed_penalty = 0 432 for name, pen_cmd in self.penalties.items(): 433 maximum_allowed_penalty += pen_cmd.max_penalty 434 value = pen_cmd.pen_dict 435 for category, inst_list in value.items(): 436 result += sum(x.the_penalty for x in inst_list) 437 return min(result, maximum_allowed_penalty) 438 439 @property 440 def max_penalty(self): 441 return sum(p_cat.max_penalty for p_cat in self.penalties.values()) 442 443 @property 444 def score(self): 445 try: 446 return 1.0 - (self.penalty / float(self.max_penalty)) 447 except ZeroDivisionError: 448 return float('nan') 449 450 @property 451 def summary_string(self): 452 score = self.score 453 isnan = score != score # pylint: disable=comparison-with-itself 454 color = 'g' 455 if score < 0.25 or isnan: 456 color = 'r' 457 elif score < 0.75: 458 color = 'y' 459 460 return '<{}>({:.4f})</>'.format(color, score) 461 462 @property 463 def verbose_output(self): # noqa 464 string = '' 465 466 # Add address resolutions if present. 467 if self.address_resolutions: 468 if self.resolved_addresses: 469 string += '\nResolved Addresses:\n' 470 for addr, res in self.resolved_addresses.items(): 471 string += f" '{addr}': {res}\n" 472 if self.unresolved_addresses: 473 string += '\n' 474 string += f'Unresolved Addresses:\n {self.unresolved_addresses}\n' 475 476 string += ('\n') 477 for command in sorted(self.penalties): 478 pen_cmd = self.penalties[command] 479 maximum_possible_penalty = pen_cmd.max_penalty 480 total_penalty = 0 481 lines = [] 482 for category in sorted(pen_cmd.pen_dict): 483 lines.append(' <r>{}</>:\n'.format(category)) 484 485 step_value_results = {} 486 for result, penalty in pen_cmd.pen_dict[category]: 487 if not isinstance(result, StepValueInfo): 488 continue 489 if result.expected_value not in step_value_results: 490 step_value_results[result.expected_value] = PenaltyLineRanges(result.step_index, penalty) 491 else: 492 step_value_results[result.expected_value].add_step(result.step_index, penalty) 493 494 for value, penalty_line_range in step_value_results.items(): 495 text = f'({value}): {penalty_line_range}' 496 total_penalty += penalty_line_range.penalty 497 lines.append(' {}\n'.format(text)) 498 499 for result, penalty in pen_cmd.pen_dict[category]: 500 if isinstance(result, StepValueInfo): 501 continue 502 else: 503 text = str(result) 504 if penalty: 505 assert penalty > 0, penalty 506 total_penalty += penalty 507 text += ' <r>[-{}]</>'.format(penalty) 508 lines.append(' {}\n'.format(text)) 509 510 lines.append('\n') 511 512 string += (' <b>{}</> <y>[{}/{}]</>\n'.format( 513 command, total_penalty, maximum_possible_penalty)) 514 for line in lines: 515 string += (line) 516 string += ('\n') 517 return string 518 519 @property 520 def resolved_addresses(self): 521 return {addr: format_address(res) for addr, res in self.address_resolutions.items() if res is not None} 522 523 @property 524 def unresolved_addresses(self): 525 return [addr for addr, res in self.address_resolutions.items() if res is None] 526 527 @property 528 def penalty_variable_optimized(self): 529 return self.context.options.penalty_variable_optimized 530 531 @property 532 def penalty_irretrievable(self): 533 return self.context.options.penalty_irretrievable 534 535 @property 536 def penalty_not_evaluatable(self): 537 return self.context.options.penalty_not_evaluatable 538 539 @property 540 def penalty_incorrect_values(self): 541 return self.context.options.penalty_incorrect_values 542 543 @property 544 def penalty_missing_values(self): 545 return self.context.options.penalty_missing_values 546 547 @property 548 def penalty_misordered_values(self): 549 return self.context.options.penalty_misordered_values 550 551 @property 552 def penalty_unreachable(self): 553 return self.context.options.penalty_unreachable 554 555 @property 556 def penalty_missing_step(self): 557 return self.context.options.penalty_missing_step 558 559 @property 560 def penalty_misordered_steps(self): 561 return self.context.options.penalty_misordered_steps 562 563 @property 564 def penalty_incorrect_program_state(self): 565 return self.context.options.penalty_incorrect_program_state 566