Improving Dynamic Partial Order Reductions for Concolic Testing

Reference:

Olli Saarikivi, Kari Kähkönen, and Keijo Heljanko. Improving dynamic partial order reductions for concolic testing. In Proceedings of the 12th International Conference on Application of Concurrency to System Design (ACSD 2012), pages 132–141, June 2012.

Abstract:

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.

Keywords:

concolic testing,dynamic symbolic execution,dynamic partial order reduction,sleep sets,software testing,software verification

Suggested BibTeX entry:

@inproceedings{SaaKahHel12,
    author = {Olli Saarikivi and Kari K{\"a}hk{\"o}nen and Keijo Heljanko},
    booktitle = {Proceedings of the 12th International Conference on Application of Concurrency to System Design (ACSD 2012)},
    language = {eng},
    month = {June},
    pages = {132-141},
    title = {Improving Dynamic Partial Order Reductions for Concolic Testing},
    year = {2012},
}