Intramorphic Testing: A New Approach to the Test Oracle Problem

Presented at Onward! 2022. See https://dl.acm.org/doi/abs/10.1145/3563835.3567662

Transcript

1. Intramorphic Testing A New Approach to the Test Oracle Problem Manuel Rigger Zhendong Su https://nus-test.github.io/ https://ast.ethz.ch/
2. 2 This Talk Comparison with differential testing and metamorphic testing Broad vision that might inspire future research Illustrative Examples Intramorphic Testing as a general white-box methodology to the test oracle problem
3. 3 Motivating Example Is this program correct? def bubble_sort(arr): length = len(arr) for i in range(length): for j in range(0, length - i - 1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[i]
4. 4 Motivating Example def bubble_sort(arr): length = len(arr) for i in range(length): for j in range(0, length - i - 1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[i] Is this program correct?
5. 5 Unit Testing arr = [3, 1, 2] bubble_sort(arr) assert arr == [1, 2, 3] Let’s write a unit test!
6. 6 Unit Testing arr = [3, 1, 2] bubble_sort(arr) assert arr == [1, 2, 3] Let’s write a unit test! AssertionError: [1, 2, 1]
7. 7 Unit Testing arr = [3, 1, 2] bubble_sort(arr) assert arr == [1, 2, 3] Can we automate the testing process?
8. 8 Automated Testing Challenges Test Case Test Oracle
9. 9 Test Oracle Incorrect result! “a test oracle (or just oracle) is a mechanism for determining whether a test has passed or failed”
10. 10 Automated Testing arr = [3, 1, 2] bubble_sort(arr) assert arr == [1, 2, 3] Can we automate the testing process? Test Case
11. 11 Automated Testing arr = [3, 1, 2] bubble_sort(arr) assert arr == [1, 2, 3] Can we automate the testing process? Test Oracle
12. 12 Intramorphic Testing I P P' O'' O Intramorphic Testing Modified program Oracle for each other We propose Intramorphic Testing as a general white- box methodology to tackle the test oracle problem
13. 13 Background: General Methodologies Differential Testing I P1 P2 O1 P3 O2 O3 Metamorphic Testing I I' P O O' I P P' O'' O Intramorphic Testing Oracle for each other Interchangeable programs: P1 (I) = P2 (I) = P3 (I) Derived follow-up input Oracle for each other Modified program Oracle for each other General methodologies whose concrete realizations require domain-specific insights
14. 14 Background: General Methodologies Differential Testing I P1 P2 O1 P3 O2 O3 Metamorphic Testing I I' P O O' I P P' O'' O Intramorphic Testing Oracle for each other Interchangeable programs: P1 (I) = P2 (I) = P3 (I) Derived follow-up input Oracle for each other Modified program Oracle for each other
15. 15 Differential Testing I P1 P2 O1 P3 O2 O3 Metamorphic Testing I I' P O O' I P P' O'' O Intramorphic Testing Oracle for each other Interchangeable programs: P1 (I) = P2 (I) = P3 (I) Derived follow-up input Oracle for each other Modified program Oracle for each other Background: General Methodologies
16. 16 Background: Differential Testing Many sorting algorithms and implementations exist, so we can validate that they produce the same results
17. 17 Background: Differential Testing [3, 1, 2] bubble_sort merge_sort [1, 2, 3] insertion_sort [1, 2, 3] [1, 2, 3] Oracle for each other Interchangeable programs: P1 (I) = P2 (I) = P3 (I) Differential testing is a black-box technique that works well when systems implement the same behavior
18. 18 Background: Differential Testing sorting_algorithms = [bubble_sort, merge_sort, insertion_sort] while True: arr = get_random_array() # e.g., [3, 1, 2] sorted_arrays = [alg(arr) for alg in sorting_algorithms] all_same = all(sorted_arr == sorted_arrays[0] for sorted_arr in sorted_arrays) assert all_same
19. 19 Background: Differential Testing sorting_algorithms = [bubble_sort, merge_sort, insertion_sort] while True: arr = get_random_array() # e.g., [3, 1, 2] sorted_arrays = [alg(arr) for alg in sorting_algorithms] all_same = all(sorted_arr == sorted_arrays[0] for sorted_arr in sorted_arrays) assert all_same
20. 20 Background: Differential Testing sorting_algorithms = [bubble_sort, merge_sort, insertion_sort] while True: arr = get_random_array() # e.g., [3, 1, 2] sorted_arrays = [alg(arr) for alg in sorting_algorithms] all_same = all(sorted_arr == sorted_arrays[0] for sorted_arr in sorted_arrays) assert all_same
21. 21 Background: Differential Testing sorting_algorithms = [bubble_sort, merge_sort, insertion_sort] while True: arr = get_random_array() # e.g., [3, 1, 2] sorted_arrays = [alg(arr) for alg in sorting_algorithms] all_same = all(sorted_arr == sorted_arrays[0] for sorted_arr in sorted_arrays) assert all_same
22. 22 Background: Differential Testing sorting_algorithms = [bubble_sort, merge_sort, insertion_sort] while True: arr = get_random_array() # e.g., [3, 1, 2] sorted_arrays = [alg(arr) for alg in sorting_algorithms] all_same = all(sorted_arr == sorted_arrays[0] for sorted_arr in sorted_arrays) assert all_same AssertionError: [[1, 2, 1], [1, 2, 3], [1, 2, 3]]
23. 23 Background: Differential Testing Applications • C/C++ compilers [Yang et al., PLDI 2011] • Java Virtual Machines (JVMs) [Chen et al., PLDI 2016 and ICSE 2019] • Database Engines [Slutz, VLDB 1998] • Debuggers [Lehmann et al., ESEC/FSE 2018] • Code coverage tools [Yang et al., ICSE 2019] • SMT solvers [Winterer, Zhang, et al., OOPSLA 2020] • Object Relational Mappers (ORMs) [Sotiropoulos et al., ICSE 2021] • …
24. 24 Background: General Methodologies Differential Testing I P1 P2 O1 P3 O2 O3 Interchangeable programs: P1 (I) = P2 (I) = P3 (I) Metamorphic Testing I I' P O O' Derived follow-up input Oracle for each other I P P' O'' O Intramorphic Testing Modified program Oracle for each other
25. 25 Background: Metamorphic Testing The relative order of sorted elements is maintained when an element is removed from an input array
26. 26 Background: Metamorphic Testing Oracles For each other [3, 1, 2] Sort [1, 2, 3] Remove 2 [1, 3] [3, 1, 2] Remove 2 [3, 1] Sort [1, 3]
27. 27 Background: Metamorphic Testing while True: arr = get_random_array() if len(arr) >= 1: sorted_arr = bubble_sort(arr) random_elem = random.choice(sorted_arr) arr.remove(random_elem) sorted_smaller_arr = bubble_sort(arr) sorted_arr.remove(random_elem) assert sorted_arr == sorted_smaller_arr
28. 28 Background: Metamorphic Testing while True: arr = get_random_array() if len(arr) >= 1: sorted_arr = bubble_sort(arr) random_elem = random.choice(sorted_arr) arr.remove(random_elem) sorted_smaller_arr = bubble_sort(arr) sorted_arr.remove(random_elem) assert sorted_arr == sorted_smaller_arr AssertionError: [2, 1] [2, 3]
29. 29 Background: Metamorphic Testing The original tech report illustrated the technique using small examples and inspired the proposed intramorphic testing paper and its content
30. 30 Background: Metamorphic Testing Applications • Compilers [Le et al., PLDI 2014] • Database engines [Rigger et al., ESEC/FSE 2020 and OOPSLA 2020] • SMT solvers [Winterer, Zhang, et al., PLDI 2020] • Android apps [Su et al., OOPSLA 2021] • Object detection systems [Wang et al., ASE 2020] • …
31. 31 Problem: No Whitebox Technique Differential Testing I P1 P2 O1 P3 O2 O3 Metamorphic Testing I I' P O O' I P P' O'' O Intramorphic Testing Oracle for each other Interchangeable programs: P1 (I) = P2 (I) = P3 (I) Derived follow-up input Oracle for each other Modified program Oracle for each other ?
32. 32 Intramorphic Testing I P P' O'' O Intramorphic Testing Modified program Oracle for each other We propose Intramorphic Testing as a white-box methodology aiming to complement differential testing and metamorphic testing
33. 33 Intramorphic Testing C1 Cn O P Cn-1 Ci It is intuitive to think of a program P consisting of individual components C1 to Cn
34. 34 Intramorphic Testing Replacing a specific component in a system might have an anticipated effect on the overall system C1 Cn O P Cn-1 P' = P[Ci '/Ci ] Ci '/Ci C1 Ci ' Cn O' Cn-1 Ci Intramorphic transformation Test oracles for each other
35. 35 Intramorphic Testing Implementing a reverse sorting function and reversing either function’s output should yield the same result as the original sorting function
36. 36 Intramorphic Testing [3, 1, 2] bubble_sort [1, 2, 3] [3, 1, 2] bubble_sort_reverse [3, 2, 1] Oracles For each other Reverse [1, 2, 3]
37. 37 Intramorphic Testing while True: arr = get_random_array() sorted_arr = bubble_sort(arr.copy()) reverse_sorted_arr = bubble_sort_reverse(arr.copy()) assert sorted_arr.reverse() == reverse_sorted_arr
38. 38 Intramorphic Testing while True: arr = get_random_array() sorted_arr = bubble_sort(arr.copy()) reverse_sorted_arr = bubble_sort_reverse(arr.copy()) assert sorted_arr.reverse() == reverse_sorted_arr AssertionError: [1, 2, 1] [3, 2, 3]
39. 39 Examples
40. 40 Supporting Artifact https://zenodo.org/record/7229326
41. 41 Example 1: AST Printing a 3 2 + * class Constant: def __init__(self, value): self.value = value class Variable: def __init__(self, name): self.name = name class Operation: def __init__(self, operator, left, right): self.operator = operator self.left = left self.right = right tree = Operation('*', Operation('+', Variable('a'), Constant(3)), Constant(2))
42. 42 Example 1: AST Printing a 3 2 + * (a + 3) * 2 print
43. 43 Example 1: AST Printing a 3 2 + * class Operation: # ... def as_string(self): left = self.left.as_string() right = self.right.as_string() if self.operator == '*': if isinstance(self.left, Operation) and self.left.operator == '+': left = '(' + left + ')' if isinstance(self.right, Operation) and self.right.operator == '+': right = '(' + right + ')' return '%s %s %s' % (left, self.operator, right)
44. 44 Example 1: AST Printing Provide alternative (simpler) print implementations, and compare that they include the same operands and operators Infix: (a + 3) * 2 Prefix: * + a 3 2 Postfix: a 3 + 2 * a 3 2 + *
45. 45 Example 1: AST Printing class Operation: # ... def as_string_prefix(self): return '%s %s %s' % (self.operator, self.left.as_string_prefix(), self.right.as_string_prefix()) def as_string_postfix(self): return '%s %s %s' % (self.left.as_string_postfix(), self.right.as_string_postfix(), self.operator) Infix: (a + 3) * 2 Prefix: * + a 3 2 Postfix: a 3 + 2 *
46. 46 Example 1: AST Printing (a + 3) * 2 * + a 3 2 a 3 + 2 * Strip parentheses a + 3 * 2 * + a 3 2 a 3 + 2 * sort * + 2 3 a * + 2 3 a * + 2 3 a Oracles For each other
47. 47 Example 2: Monte Carlo Simulation def get_pi_approximation(): inside = 0 for _ in range(1000000): x = random.random() y = random.random() if x**2+y**2 <= 1: inside += 1 pi = 4*inside/1000000 return pi
48. 48 Example 2: Monte Carlo Simulation Fewer samples result in a worse approximation
49. 49 Example 2: Monte Carlo Simulation def get_pi_approximation(n): inside = 0 for _ in range(n): x = random.random() y = random.random() if x**2+y**2 <= 1: inside += 1 pi = 4*inside/n return pi def get_pi_approximation(): inside = 0 for _ in range(1000000): x = random.random() y = random.random() if x**2+y**2 <= 1: inside += 1 pi = 4*inside/1000000 return pi Add a parameter n
50. 50 Example 2: Monte Carlo Simulation get_pi_approximation(10) get_pi_approximation(1000000) Oracles For each other Execute 3.6 3.142748
51. 51 Example 3: Knapsack Problem Given a knapsack with a given capacity, the goal is to pack items to maximize the value of items in the knapsack. Capacity: 5 kg Value: 10, weight: 0.1 kg Value: 1500, weight: 2.2 kg
52. 52 Example 3: Knapsack Problem Overall value: 3600 Overall weight: 5.0 kg Value: 3000 Weight: 4.4 kg Value: 60 Weight: 0.6 kg
53. 53 Example 3: Knapsack Problem vals = [ ('Microphone', 10, 1), ('Laptop', 1500, 22) ] def knapsack_greedy(objects, capacity): packed = [] cum_value = 0 cum_weight = 0 objects.sort(key=lambda triple : float(triple[1]) / triple[2], reverse=True) for (item, value, weight) in objects: while cum_weight + weight <= capacity: cum_weight += weight cum_value += value packed.append(item) return (packed, cum_value, cum_weight)
54. 54 Example 3: Knapsack Problem A greedy algorithm should never produce a better result than an optimal algorithm
55. 55 Discussion: Characteristics • Granularity (operator, system, …) • Format (source code, binary, …) • Transformation realization (adding new component, replacing it, …) • Completeness (applicable to any input) • False alarms • … Future research could explore their strengths and weaknesses
56. 56 Discussion: Domain • Compilers • Database systems • SMT solvers • … Similar to differential testing and metamorphic testing, domain-specific insights will be necessary to realize effective approaches
57. 57 Discussion: Practicality Users Developers
58. 58 Discussion: Practicality Users Developers I can apply metamorphic testing and differential testing without deep knowledge on the system’s internals
59. 59 Discussion: Practicality Users Developers I can use intramorphic testing to incorporate my application knowledge into the testing process
60. 60 Discussion: Practicality Developers How should I maintain multiple versions? How can the IDE support me? … We hope that future research will propose approaches to lower the cost of using intramorphic testing
61. 61 Summary