Biped: Bidirectional Prediction of Order Violations

Xi CHANG; Zhuo ZHANG; Yan LEI; Jianjun ZHAO

doi:10.1587/transinf.2014EDP7347

Biped: Bidirectional Prediction of Order Violations

Xi CHANG, Zhuo ZHANG, Yan LEI, Jianjun ZHAO

Full Text Views

0

Share
Cite this

Summary :

Concurrency bugs do significantly affect system reliability. Although many efforts have been made to address this problem, there are still many bugs that cannot be detected because of the complexity of concurrent programs. Compared with atomicity violations, order violations are always neglected. Efficient and effective approaches to detecting order violations are therefore in urgent need. This paper presents a bidirectional predictive trace analysis approach, BIPED, which can detect order violations in parallel based on a recorded program execution. BIPED collects an expected-order execution trace into a layered bidirectional prediction model, which intensively represents two types of expected-order data flows in the bottom layer and combines the lock sets and the bidirectionally order constraints in the upper layer. BIPED then recognizes two types of candidate violation intervals driven by the bottom-layer model and then checks these recognized intervals bidirectionally based on the upper-layer constraint model. Consequently, concrete schedules can be generated to expose order violation bugs. Our experimental results show that BIPED can effectively detect real order violation bugs and the analysis speed is 2.3x-10.9x and 1.24x-1.8x relative to the state-of-the-art predictive dynamic analysis approaches and hybrid model based static prediction analysis approaches in terms of order violation bugs.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.2 pp.334-345

Publication Date: 2015/02/01

Publicized: 2014/10/29

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2014EDP7347

Type of Manuscript: PAPER

Category: Software Engineering

Authors

Xi CHANG
  Shanghai Jiao Tong University
Zhuo ZHANG
  College of Computer, National University of Defense Technology
Yan LEI
  College of Computer, National University of Defense Technology
Jianjun ZHAO
  Shanghai Jiao Tong University

Keyword

concurrency bug, trace model, predictive trace analysis, order violation

Cite this

Copy

Xi CHANG, Zhuo ZHANG, Yan LEI, Jianjun ZHAO, "Biped: Bidirectional Prediction of Order Violations" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 2, pp. 334-345, February 2015, doi: 10.1587/transinf.2014EDP7347.
Abstract: Concurrency bugs do significantly affect system reliability. Although many efforts have been made to address this problem, there are still many bugs that cannot be detected because of the complexity of concurrent programs. Compared with atomicity violations, order violations are always neglected. Efficient and effective approaches to detecting order violations are therefore in urgent need. This paper presents a bidirectional predictive trace analysis approach, BIPED, which can detect order violations in parallel based on a recorded program execution. BIPED collects an expected-order execution trace into a layered bidirectional prediction model, which intensively represents two types of expected-order data flows in the bottom layer and combines the lock sets and the bidirectionally order constraints in the upper layer. BIPED then recognizes two types of candidate violation intervals driven by the bottom-layer model and then checks these recognized intervals bidirectionally based on the upper-layer constraint model. Consequently, concrete schedules can be generated to expose order violation bugs. Our experimental results show that BIPED can effectively detect real order violation bugs and the analysis speed is 2.3x-10.9x and 1.24x-1.8x relative to the state-of-the-art predictive dynamic analysis approaches and hybrid model based static prediction analysis approaches in terms of order violation bugs.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2014EDP7347/_p

Copy

@ARTICLE{e98-d_2_334,
author={Xi CHANG, Zhuo ZHANG, Yan LEI, Jianjun ZHAO, },
journal={IEICE TRANSACTIONS on Information},
title={Biped: Bidirectional Prediction of Order Violations},
year={2015},
volume={E98-D},
number={2},
pages={334-345},
abstract={Concurrency bugs do significantly affect system reliability. Although many efforts have been made to address this problem, there are still many bugs that cannot be detected because of the complexity of concurrent programs. Compared with atomicity violations, order violations are always neglected. Efficient and effective approaches to detecting order violations are therefore in urgent need. This paper presents a bidirectional predictive trace analysis approach, BIPED, which can detect order violations in parallel based on a recorded program execution. BIPED collects an expected-order execution trace into a layered bidirectional prediction model, which intensively represents two types of expected-order data flows in the bottom layer and combines the lock sets and the bidirectionally order constraints in the upper layer. BIPED then recognizes two types of candidate violation intervals driven by the bottom-layer model and then checks these recognized intervals bidirectionally based on the upper-layer constraint model. Consequently, concrete schedules can be generated to expose order violation bugs. Our experimental results show that BIPED can effectively detect real order violation bugs and the analysis speed is 2.3x-10.9x and 1.24x-1.8x relative to the state-of-the-art predictive dynamic analysis approaches and hybrid model based static prediction analysis approaches in terms of order violation bugs.},
keywords={},
doi={10.1587/transinf.2014EDP7347},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - Biped: Bidirectional Prediction of Order Violations
T2 - IEICE TRANSACTIONS on Information
SP - 334
EP - 345
AU - Xi CHANG
AU - Zhuo ZHANG
AU - Yan LEI
AU - Jianjun ZHAO
PY - 2015
DO - 10.1587/transinf.2014EDP7347
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2015
AB - Concurrency bugs do significantly affect system reliability. Although many efforts have been made to address this problem, there are still many bugs that cannot be detected because of the complexity of concurrent programs. Compared with atomicity violations, order violations are always neglected. Efficient and effective approaches to detecting order violations are therefore in urgent need. This paper presents a bidirectional predictive trace analysis approach, BIPED, which can detect order violations in parallel based on a recorded program execution. BIPED collects an expected-order execution trace into a layered bidirectional prediction model, which intensively represents two types of expected-order data flows in the bottom layer and combines the lock sets and the bidirectionally order constraints in the upper layer. BIPED then recognizes two types of candidate violation intervals driven by the bottom-layer model and then checks these recognized intervals bidirectionally based on the upper-layer constraint model. Consequently, concrete schedules can be generated to expose order violation bugs. Our experimental results show that BIPED can effectively detect real order violation bugs and the analysis speed is 2.3x-10.9x and 1.24x-1.8x relative to the state-of-the-art predictive dynamic analysis approaches and hybrid model based static prediction analysis approaches in terms of order violation bugs.
ER -