Publication Type
Journal Article
Version
acceptedVersion
Publication Date
1-2025
Abstract
Instruction reordering is an essential optimization technique used in both compilers and multi-core processors to enhance parallelism and resource utilization. Although the original intent of this technique is to benefit the program, some improper reordering can significantly impact the program correctness, which we call instruction reordering vulnerability (IRV). However, existing methods detect IRV by defining CPU instruction reordering rules to schedule execution paths while neglecting compiler reordering, and thus generate false positives that require manual filtering and resulting in inefficiency. To bridge this gap, in this paper, we propose the IRV detection method, , which analyzes IRV characteristics and extracts vulnerability patterns, integrating program dependency analysis for compiler reordering and memory model constraints for CPU reordering. Specifically, we use static analysis based on specific patterns to narrow the analysis scope, and adopt log-based dynamic analysis to confirm vulnerability by checking the log constraints. We built the IRV benchmark to compare IRHunter with five state-of-the-art tools (i.e., GENMC, Nidhugg, CBMC, SHB, BiRD). IRHunter detected all 19 errors, doubling the best model checking tools' performance, with half the false positive rate of leading data race detectors. It was 10× faster on small programs and outperformed data race detectors on large programs.
Keywords
concurrency, Instruction reordering vulnerability, model checking, static analysis
Discipline
Artificial Intelligence and Robotics | Software Engineering
Research Areas
Intelligent Systems and Optimization
Publication
IEEE Transactions on Parallel and Distributed Systems
Volume
36
Issue
6
First Page
1
Last Page
17
ISSN
1045-9219
Identifier
10.1109/TPDS.2025.3556861
Publisher
Institute of Electrical and Electronics Engineers
Citation
XIN, Guohua; XU, Guangquan; ZHANG, Yao; WEN, Cheng; ZHANG, Cen; XIE, Xiaofei; XIONG, Neal N.; LIU, Shaoying; and GAO, Pan.
IRHunter: Universal detection of instruction reordering vulnerabilities for enhanced concurrency in distributed and parallel systems. (2025). IEEE Transactions on Parallel and Distributed Systems. 36, (6), 1-17.
Available at: https://ink.library.smu.edu.sg/sis_research/10157
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/TPDS.2025.3556861