Page 117 - 《软件学报》2025年第5期

郝蕊 等: 基于事件标记的多粒度结合安卓测试序列约减 2017

表 2 方法 TREC、ECHO、SimplyDroid 约减效果与效率表 (续)

ECHO SimplyDroid TREC
ID 总长度
长度 时间 (min) 崩溃 长度 时间 (min) 崩溃 长度 标记时间 (min) 约减时间 (min) 总时间 (min) 崩溃
23 63 5 27.74 N 3 2 953.92 Y 5 27.98 180.64 208.62 Y
24 49 3 64.25 N 20 2 762.18 N 9 24.12 232.08 256.20 Y
25 64 3 44.88 N 30 5 190.21 N 9 26.57 156.28 182.85 Y
26 64 5 52.67 N 31 5 792.33 N 11 34.45 164.97 199.42 Y
27 79 3 46.27 N 10 762.60 Y 9 35.49 256.38 291.87 Y
28 69 3 47.42 N 40 6 963.39 N 9 29.22 213.31 242.53 Y
29 56 5 51.64 N 26 3 432.85 N 11 38.50 145.32 183.82 Y
30 66 3 46.10 N 35 5 542.74 N 9 29.44 186.67 216.11 Y
31 75 6 21.46 N 16 3 151.00 Y 9 37.32 796.30 833.62 Y
32 90 6 19.92 N 37 5 450.77 N 9 29.16 356.52 385.68 Y
33 66 14 32.02 N 23 2 217.32 N 14 24.02 545.37 569.39 Y
34 76 13 29.53 N 9 1 674.16 Y 14 20.46 936.73 957.19 Y
35 106 28 18.45 N 14 3 005.76 Y 17 37.64 725.16 762.80 Y
36 312 80 131.11 N 18 2 219.05 Y 9 31.68 5 369.76 5 401.44 Y
37 133 38 65.86 N 69 18 055.44 N 24 43.41 1 631.44 1 674.85 Y
38 102 18 36.54 N 9 644.78 Y 9 42.88 293.12 336.00 Y
39 177 37 64.91 N 9 748.35 Y 9 18.82 870.15 888.97 Y
40 86 5 18.31 N 9 3 465.46 Y 15 23.60 814.93 838.53 Y
41 71 16 34.35 N 18 2 897.58 Y 13 25.16 363.01 388.17 Y
42 108 11 29.46 N 13 3 371.75 Y 14 36.68 560.93 597.61 Y
43 107 24 46.01 N 13 2 860.66 Y 19 33.24 2 494.87 2 528.11 Y
44 223 35 44.94 Y 17 10 029.10 Y 14 27.07 615.76 642.83 Y
45 478 44 19.51 N 16 3 927.86 Y 8 21.55 3 813.72 3 835.27 Y
46 79 6 19.76 N 10 523.07 Y 9 16.91 422.92 439.83 Y
47 103 14 30.59 N 9 815.97 Y 9 17.51 406.56 424.07 Y
48 201 41 69.05 N 13 2 192.70 Y 10 18.24 6 540.70 6 558.94 Y
49 198 24 45.31 N 9 785.83 Y 9 20.22 656.54 676.76 Y
50 214 19 39.53 N 9 1 133.61 Y 9 22.58 597.07 619.65 Y
51 359 24 46.25 N 13 4 254.30 Y 9 40.78 797.41 838.19 Y
52 197 28 52.81 N 9 1 039.30 Y 10 24.48 2 563.99 2 588.47 Y
53 376 30 54.42 N 13 2 904.39 Y 10 35.41 946.66 982.07 Y
54 797 38 67.20 N 28 5 776.50 N 9 36.13 1 069.21 1 105.34 Y
55 97 3 40.56 N 32 4 447.66 N 7 0.63 332.76 333.39 Y
56 124 7 45.90 N 77 23 736.22 N 10 0.23 730.09 730.32 Y
57 279 3 37.06 N 89 54 593.30 N 7 0.31 730.99 731.30 Y
58 350 18 75.97 N 75 49 846.06 N 7 0.56 912.52 913.09 Y
59 198 8 48.96 Y 107 40 879.73 N 8 0.03 213.93 213.96 Y
60 224 3 37.24 N 144 78 926.18 N 8 0.50 414.32 414.82 Y
61 108 3 37.29 N 37 6 217.88 N 7 0.68 255.49 256.18 Y
62 181 7 47.64 N 96 32 776.05 N 8 0.83 504.41 505.25 Y
63 9 1 25.01 Y 1 27.87 Y 1 0.00 11.45 11.45 Y
64 13 2 21.82 Y 2 27.75 Y 2 0.00 13.21 13.21 Y
65 8 1 10.70 Y 1 27.50 Y 1 0.00 8.68 8.68 Y
66 75 2 15.67 Y 5 1 329.04 Y 2 0.00 13.29 13.29 Y

从表 2 中可以看出, ECHO 算法对 55 个序列均无法生成可触发程序崩溃的测试序列, 占到了总序列数的
83%, 就是因为 ECHO 直接将平凡最短路径作为最终约减结果返回, 并未考虑其是否可正确触发程序崩溃这一约
束条件. 例如图 1 中给出的动机示例 (a), ECHO 算法仅寻找最短平凡路径 e 39 → e 48 作为最终约减路径, 而关键事