Lune

NSDI2024Top-tier venue

Efficient Exposure of Partial Failure Bugs in Distributed Systems with Inferred Abstract States

Haoze Wu, Jia Pan, Peng Huang

Abstract

Many distributed system failures, especially the notorious partial service failures, are caused by bugs that are only triggered by subtle faults at rare timing. Existing testing is inefficient in exposing such bugs. This paper presents Legolas, a fault injection testing framework designed to address this gap. To precisely simulate subtle faults, Legolas statically analyzes the system code and instruments hooks within a system. To efficiently explore numerous faults, Legolas introduces a novel notion of abstract states and automatically infers abstract states from code. During testing, Legolas designs an algorithm that leverages the inferred abstract states to make careful fault injection decisions. We applied Legolas on the latest releases of six popular, extensively tested distributed systems. Legolas found 20 new bugs that result in partial service failures.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

8 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Efficient Reproduction of Fault-Induced Failures in Distributed Systems with Feedback-Driven Fault Injection cites Understanding, Detecting and Localizing Partial Failures in Large System Software
  • Efficient Reproduction of Fault-Induced Failures in Distributed Systems with Feedback-Driven Fault Injection cites Automatic Reliability Testing For Cluster Management Controllers
  • Understanding and Detecting Fail-Slow Hardware Failure Bugs in Cloud Systems cites Understanding, Detecting and Localizing Partial Failures in Large System Software
  • Understanding and Detecting Fail-Slow Hardware Failure Bugs in Cloud Systems cites Perseus: A Fail-Slow Detection Framework for Cloud Storage Systems
  • MeshTest: End-to-End Testing for Service Mesh Traffic Management cites Automatic Reliability Testing For Cluster Management Controllers
  • Multi-Grained Specifications for Distributed System Model Checking and Verification cites Automatic Reliability Testing For Cluster Management Controllers
  • Perseus: A Fail-Slow Detection Framework for Cloud Storage Systems cites Understanding, Detecting and Localizing Partial Failures in Large System Software
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. MeshTest: End-to-End Testing for Service Mesh Traffic ManagementNaiqian Zheng, Tianshuo Qiao, Xuanzhe Liu, Xin JinNSDI 2025 · 7 citations
  2. Understanding and Detecting Fail-Slow Hardware Failure Bugs in Cloud SystemsGen Dong, Yu Hua, Yongle Zhang, Zhangyu Chen et al.USENIX ATC 2025 · 6 citations
  3. Efficient Reproduction of Fault-Induced Failures in Distributed Systems with Feedback-Driven Fault InjectionJia Pan, Haoze Wu, Tanakorn Leesatapornwongsa, Suman Nath et al.SOSP 2024 · 4 citations
  4. Multi-Grained Specifications for Distributed System Model Checking and VerificationLingzhi Ouyang, Xudong Sun, Ruize Tang, Yu Huang et al.EuroSys 2025 · 4 citations
  5. UpFuzz: Detecting Data Format Incompatibility Bugs during Distributed Storage System UpgradeKe Han, P. C. Sruthi, Yayu Wang, Yaoxu Song et al.NSDI 2026 · 3 citations

Builds on11

  1. Elle: Inferring Isolation Anomalies from Experimental ObservationsPeter Alvaro, Kyle KingsburyVLDB 2021 · 88 citations
  2. Understanding, Detecting and Localizing Partial Failures in Large System SoftwareChang Lou, Peng Huang, Scott SmithNSDI 2020 · 88 citations
  3. Automatic Reliability Testing For Cluster Management ControllersXudong Sun, Wenqing Luo, Jiawei Tyler Gu, Aishwarya Ganesan et al.OSDI 2022 · 44 citations
  4. Metastable Failures in the WildLexiang Huang, Matthew Magnusson, Abishek Bangalore Muralikrishna, Salman Estyak et al.OSDI 2022 · 38 citations
  5. Perseus: A Fail-Slow Detection Framework for Cloud Storage SystemsRuiming Lu, Erci Xu, Yiming Zhang, Fengyi Zhu et al.FAST 2023 · 31 citations

Related papers

  1. CAFault: Enhance Fault Injection Technique in Practical Distributed Systems via Abundant Fault-Dependent ConfigurationsYuanliang Chen, Fuchen Ma, Yuanhang Zhou, Zhen Yan et al.USENIX ATC 2025 · 7 citations
  2. CSnake: Detecting Self-Sustaining Cascading Failure via Causal Stitching of Fault PropagationsShangshu Qian, Lin Tan, Yongle ZhangEuroSys 2026 · 1 citation
  3. CoFI: Consistency-Guided Fault Injection for Cloud SystemsHaicheng Chen, Wensheng Dou, Dong Wang, Feng QinASE 2020 · 25 citations
  4. Coverage Guided Fault Injection for Cloud SystemsYu Gao, Wensheng Dou, Dong Wang, Wenhan Feng et al.ICSE 2023 · 13 citations
  5. When Amnesia Strikes: Understanding and Reproducing Data Loss Bugs with Fault InjectionMaria Ramos, João Azevedo, Kyle Kingsbury, José Pereira et al.VLDB 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines