深圳大学计算机与软件学院
College of Computer Science and Software Engineering, SZU

Controlled Concurrency Testing via Periodical Scheduling

    International Conference on Software Engineering (ICSE)

 

Cheng Wen1    Mengda He2    Bohao Wu1    Zhiwu Xu1    Shengchao Qin3

1Shenzhen University    2Teesside University    3HUAWEI Hong Kong Research Center

 

Fig. 1. An illustration of how our proposed techniques finding the null-pointer dereference bug on the CVE-2016-7911 example.

 

Abstract

Controlled Concurrency testing (CCT) techniques have been shown promising for concurrency bug detection. Their key insight is to control the order in which threads get executed, and attempt to explore the space of possible interleavings of a concurrent program to detect bugs. However, various challenges remain in current CCT techniques, rendering them ineffective and ad-hoc. In this paper, we propose a novel CCT technique PERIOD. Unlike previous works, PERIOD models the execution of concurrent programs as periodical execution, and systematically explores the space of possible interleavings, where the exploration is guided by periodical scheduling and influenced by previously tested interleavings. We have evaluated PERIOD on 10 real-world CVEs and 36 widely-used benchmark programs, and our experimental results show that \name demonstrates superiority over other CCT techniques in both effectiveness and runtime overhead. Moreover, we have discovered 5 previously unknown concurrency bugs in real-world programs.

Fig. 2. To make the best of the computing power brought with modern multiprocessor hardware, concurrent programming is now prevalent. However, it is difficult to ensure that a concurrent program is bug-free.

Fig. 3. Concurrency bugs are notoriously hard to detect, reproduce and debug. Unlike sequential programs whose only non-determinism comes from their input, the behavior of concurrent programs is also subject to how their threads interleave and thus leaving more openings for concurrency bugs. Concurrency bugs often escape rigorous software testing, posing a constant threat to system correctness, reliability, and safety. Take the figure as an example, the observed interleaving during testing could miss the bug. However, Untested interleavings can cause failures.

Fig. 4. Controlled concurrency testing (CCT) offers a solution for concurrency bugs detection, where it (i) performs multiple repeatability tests, for a given test case; (ii) actively controlled thread interleaving by periodical scheduling method; (iii) try to test one untested thread interleaving at a time.

Fig. 5. An overview of PERIOD. We present a novel controlled concurrency testing technique namely Period. Period models the execution of concurrent programs as periodical execution, and systematically explores the space of possible interleavings, guided by periodical scheduling and the history execution information.

Fig. 6. Illustrating example: CVE-2016-1972. This program demonstrates 3 kinds of concurrency bugs, that is, null-pointer-dereference (NPD), use-after-free (UAF), and double-free (DF). In more detail, if the lock is set to null in 𝑇0 at Ln. 16 before 𝑇1 uses the lock at Ln. 9, a NPD will occur. A UAF can be triggered at Ln. 9 where thread 𝑇0 releases the lock at Ln. 15 and thread 𝑇1 uses the lock at Ln. 9. A DF can be triggered at Ln. 15 where both threads 𝑇0 and 𝑇1 try to release the lock. All these bugs are actually hard to trigger, as they each require a specific sequence of operations on variable done, waiter, and lock.

 

Fig. 7. Each sub-figure is an execution of the CVE-2016-1972 program, and their captions are the generated schedule they attempt to follow. The schedule exploration starts with period-number 2 (i.e., for bugs with bug-depth 1). PERIOD systematically explores schedules in a quasi-lexicographical order for each DKPS. The null-pointer-dereference, use-after-free, double-free bug can be found if the period-number bound is set to larger than 5.

Fig. 8. PERIOD allow parallelism, putting every period in use to create meaningful context switches.

Fig. 9. The number of bugs found after 𝑥 schedule. On the whole, Period has a larger growth trend, indicating that Period requires fewer schedules to find the same number of bugs or can find more bugs in the same number of schedules.

 

Data & Code

Note that the DATA and CODE are free for Research and Education Use ONLY. 

Please cite our paper (add the bibtex below) if you use any part of our ALGORITHM, CODE, DATA or RESULTS in any publication.

Link:https://sites.google.com/view/period-cct/tool-and-benchmarks

 

Acknowledgements

The authors would like to thank the anonymous reviewers for their constructive comments. This work was supported by the National Natural Science Foundation of China (Nos. 61972260, 61772347, 61836005) and the Guangdong Basic and Applied Basic Research Foundation (No. 2019A1515011577).

 

Bibtex

@inproceedings{wen2022period,

author = {Wen, Cheng and He, Mengda and Wu, Bohao and Xu, Zhiwu and Qin, Shengchao},

title = {Controlled Concurrency Testing via Periodical Scheduling},

year = {2022},

isbn = {9781450392211},

publisher = {Association for Computing Machinery},

address = {New York, NY, USA},

url = {https://doi.org/10.1145/3510003.3510178},

doi = {10.1145/3510003.3510178},

booktitle = {Proceedings of the ACM/IEEE 4th International Conference on Software Engineering},

keywords = {software vulnerability, memory consumption, fuzz testing},

location = {Pittsburgh, USA},

series = {ICSE '22}

}

Downloads