Efficiently Testing Distributed Systems via Abstract State Space Prioritization
- 9 October 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 52 (2) , 395-410
Abstract
The last five years have seen a rise of model checking guided testing (MCGT) approaches for systematically testing distributed systems. MCGT approaches generate test cases for distributed systems by traversing their verified abstract state spaces, simultaneously solving the three key problems faced in testing distributed systems, i.e., test input generation, test oracle construction and execution space enumeration. However, existing MCGT approaches struggle with traversing the huge state space of distributed systems, which can contain billions of system states. This makes the process of finding bugs time-consuming and expensive, often taking several weeks. In this paper, we propose Mosso to speed up model checking guided testing for distributed systems. We observe that there exist lots of redundant test scenarios in the abstract state space of distributed systems. Considering the characteristics of these redundant test scenarios, we propose three strategies: action independence, node symmetry and scenario equivalence, to identify and prioritize unique test scenarios when traversing the state space. We have applied Mosso on three real-world distributed systems. By employing the three strategies, our approach has achieved an average speedup of 56Χ (up to 208Χ) compared to the state-of-art MCGT approach. Additionally, our approach has successfully uncovered 2 previously-unknown bugs.Keywords
Funding Information
- National Key Research and Development Program of China (2024YFB4505902)
- National Natural Science Foundation of China (62302493)
- National Natural Science Foundation of China (62072444)
- Major Program (JD) of Hubei Province (2023BAA018)
- Major Project of ISCAS (ISCAS-ZD-202302)
- Basic Research Project of ISCAS (ISCAS-JCZD-202403)
- Youth Innovation Promotion Association at Chinese Academy of Sciences (Y2022044)
This publication has 43 references indexed in Scilit:
- Validating Traces of Distributed Programs Against TLA+ Specifications2024
- Leveraging TLA$^+$ Specifications to Improve the Reliability of the ZooKeeperCoordination Service2023
- Protocol Conformance with Choreographic PlusCal2023
- Model‐checking‐driven explorative testing of CRDT designs and implementationsJournal of Software: Evolution and Process, 2023
- Understanding Real-World Timeout Problems in Cloud Server Systems2018
- Hitting Families of Schedules for Asynchronous Programs2016
- Bounded Phase Analysis of Message-Passing Programs2012
- Zab: High-performance broadcast for primary-backup systems2011
- Context-Bounded Model Checking of Concurrent Software2005
- Partial-Order Methods for the Verification of Concurrent Systems1996