Improving Dynamic Partial Order Reductions for Concolic Testing
Improving Dynamic Partial Order Reductions for Concolic Testing
复制标题
改进 Concolic 测试的动态偏阶约简
DOI：
10.1109/acsd.2012.18
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Keijo Heljanko
中科院分区：
文献类型：
--
作者：
Olli Saarikivi;Kari Kähkönen;Keijo Heljanko
多线程程序的测试是困难的，由于状态爆炸问题所产生的并发操作的不同交织。Flanagan和Godefroid提出的动态偏序约简（DPOR）算法是解决这一问题的一种方法。我们提出了一个修改这个算法，允许它利用读操作的交换性，并提供进一步的减少。为了使测试的多线程程序，也采取输入，我们表明，它是可能的联合收割机DPOR与concolic测试。我们已经实现了我们的修改后的DPOR算法在LCT concolic测试工具。我们还实现了睡眠集算法，该算法可以与DPOR一起沿着使用，以提供进一步的减少。由于LCT工具是为分布式使用而设计的，因此我们修改了睡眠集算法，以用于分布式测试客户端-服务器设置。
Testing multi-threaded programs is hard due to the state explosion problem arising from the different interleavings of concurrent operations. The dynamic partial order reduction (DPOR) algorithm by Flanagan and Godefroid is one solution to reducing this problem. We present a modification to this algorithm that allows it to exploit the commutativity of read operations and provide further reduction. To enable testing of multi-threaded programs that also take input we show that it is possible to combine DPOR with concolic testing. We have implemented our modified DPOR algorithm in the LCT concolic testing tool. We have also implemented the sleep set algorithm, which can be used along with DPOR to provide further reduction. As the LCT tool was designed for distributed use we have modified the sleep set algorithm for use in a distributed testing client-server setting.