IEICE TRANSACTIONS on Information
Biped: Bidirectional Prediction of Order Violations
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
