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,

Additional URL

https://doi.org/10.1109/ICECCS.2019.00021

This document is currently not available here.

Share

COinS