Adaptive randomized scheduling for concurrency bug detection

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

Full description

Saved in:
Bibliographic Details
Main Authors: WANG, Zan, ZHANG, Dongdi, LIU, Shuang, SUN, Jun, ZHAO, Yingquan
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2019
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/4442
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-5445
record_format dspace
spelling sg-smu-ink.sis_research-54452019-11-22T03:06:03Z Adaptive randomized scheduling for concurrency bug detection WANG, Zan ZHANG, Dongdi LIU, Shuang SUN, Jun ZHAO, Yingquan 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. 2019-11-13T08:00:00Z text https://ink.library.smu.edu.sg/sis_research/4442 info:doi/10.1109/ICECCS.2019.00021 Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Adaptive random testing Bug detection Concurrency bug pattern Concurrency bugs Computer and Systems Architecture Computer Engineering
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Adaptive random testing
Bug detection
Concurrency bug pattern
Concurrency bugs
Computer and Systems Architecture
Computer Engineering
spellingShingle Adaptive random testing
Bug detection
Concurrency bug pattern
Concurrency bugs
Computer and Systems Architecture
Computer Engineering
WANG, Zan
ZHANG, Dongdi
LIU, Shuang
SUN, Jun
ZHAO, Yingquan
Adaptive randomized scheduling for concurrency bug detection
description 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.
format text
author WANG, Zan
ZHANG, Dongdi
LIU, Shuang
SUN, Jun
ZHAO, Yingquan
author_facet WANG, Zan
ZHANG, Dongdi
LIU, Shuang
SUN, Jun
ZHAO, Yingquan
author_sort WANG, Zan
title Adaptive randomized scheduling for concurrency bug detection
title_short Adaptive randomized scheduling for concurrency bug detection
title_full Adaptive randomized scheduling for concurrency bug detection
title_fullStr Adaptive randomized scheduling for concurrency bug detection
title_full_unstemmed Adaptive randomized scheduling for concurrency bug detection
title_sort adaptive randomized scheduling for concurrency bug detection
publisher Institutional Knowledge at Singapore Management University
publishDate 2019
url https://ink.library.smu.edu.sg/sis_research/4442
_version_ 1770574839256449024