Improving Dynamic Partial Order Reductions for Concolic Testing

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 alg...

Full description

Saved in:
Bibliographic Details
Main Authors: Saarikivi, O., Kahkonen, K., Heljanko, K.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Clocks
concolic testing
Heuristic algorithms
Indexes
partial order reduction
Schedules
Testing
Vectors
verification
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1550-4808
2374-8567
DOI:10.1109/ACSD.2012.18