Adaptive randomized scheduling for concurrency bug detection
Publication Type
Conference Proceeding Article
Publication Date
11-2019
Abstract
Multi-threaded programs often exhibit erroneous behaviours due to unintended interactions among threads. Those bugs are often difficult to find because they typically manifest under very specific thread schedules. The traditional randomized algorithms increase the probability of exploring infrequent interleavings using randomized scheduling and improve the chances of detecting concurrency defects. However, they may generate many redundant trials, especially for those hard-to-detect defects, and thus their performance is often not stable. In this work, we propose an adaptive randomized scheduling algorithm~(ARS), which adaptively explores the search space and detects concurrency bugs more efficiently with less efforts. We compare ARS with random searching and the state-of-the-art maximal causality reduction method on 27 concurrent Java programs. The evaluation results show that ARS shows a more stable performance in terms of effectiveness in detecting multi-threaded bugs. Particularly, ARS shows a good potential in detecting hard-to-expose bugs.
Keywords
Adaptive random testing, Bug detection, Concurrency bug pattern, Concurrency bugs
Discipline
Computer and Systems Architecture | Computer Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
Proceedings of the 24th International Conference on Engineering of Complex Computer Systems (ICECCS), Guangzhou, China, 2019 November 10-13
Identifier
10.1109/ICECCS.2019.00021
Publisher
IEEE
City or Country
Guangzhou, China,
Citation
WANG, Zan; ZHANG, Dongdi; LIU, Shuang; SUN, Jun; and ZHAO, Yingquan.
Adaptive randomized scheduling for concurrency bug detection. (2019). Proceedings of the 24th International Conference on Engineering of Complex Computer Systems (ICECCS), Guangzhou, China, 2019 November 10-13.
Available at: https://ink.library.smu.edu.sg/sis_research/4442
Additional URL
https://doi.org/10.1109/ICECCS.2019.00021