Page 52 - 《软件学报》2021年第6期

1626 Journal of Software 软件学报 Vol.32, No.6, June 2021

开的运行速度缓慢;另外,庞大的扩展集也不利于启发式技术做出正确的选择.可见:如何有效减少冗余扩展的
数量,是提升反向展开效率的关键因素.
(3) directed unfolding 基准库
directed unfolding 使用了 dartes,random,airport,openstacks 这 4 个用例集,本文分别与之进行比较.4 个用例
集上的最大扩展次数均设为 10 000 次,最大运行时间设为 35s.
dartes 用例集的实验结果如图 10(c)所示.正向展开中,hsum 策略效果最好,总共验证了 256/257 组用例的可
覆盖性.反向展开中,hmax 策略效果最好,总共验证了 257/257 组用例的可覆盖性.进一步,反向展开|E|的规模在
48 组用例上最优,在 2 组用例上与正向展开持平.在这个用例集上,正向展开与反向展开都发挥了各自的优势.

(a) Randomtree (b) Threadlock

(c) Dartes
Fig.10 Comparison of |E| in different test cases between directed unfolding and reverse unfolding
图 10 directed unfolding 与反向展开在不同测试用例上的事件总数对比

在 random 用例集上:正向展开中,hsum 策略效果最好,总共验证了 33/45 组用例的可覆盖性;反向展开中,
block+hsum 策略效果最好,总共验证了 26/45 组用例的可覆盖性.进一步,正向展开|E|的规模在 33 组用例上最优,
在 12 组用例上与反向展开持平.在接下来对 airport,openstacks 的测试中,正向展开结合 hsum 策略分别能验证
19/26,30/30 组用例的可覆盖性,而反向展开无法验证任何用例的可覆盖性.在这些用例上的低效甚至失效说明
了反向展开并不能适用于所有场景,这也是其性质决定的.然而,启发式技术往往能够弥补算法在性质上的不
足.因此,针对反向展开低效或失效的情况,应设计更有效的启发式技术加以优化.