CSnake: Detecting Self-Sustaining Cascading Failure via Causal Stitching of Fault Propagations

Recent studies have revealed that self-sustaining cascading failures in distributed systems frequently lead to widespread outages, which are challenging to contain and recover from. Existing failure detection techniques struggle to expose such failures prior to deployment, as they typically require a complex combination of specific conditions to be triggered. This challenge stems from the inherent nature of cascading failures, as they typically involve a sequence of fault propagations, each activated by distinct conditions.

This paper presents CSnake, a fault injection framework to expose self-sustaining cascading failures in distributed systems. CSnake uses the novel idea of causal stitching, which causally links multiple single-fault injections in different test workloads to simulate complex fault propagation chains. To identify propagation chains between faults, CSnake designs a counterfactual causality analysis of fault propagationsfault causality analysis (FCA): FCA compares the execution trace of a fault injection run with its corresponding profile run (i.e., running the same test without the injection) and identifies any additional faults triggered, which are considered to have a causal relationship with the injected fault.

To address the large search space of fault and workload combinations, CSnake employs a three-phase allocation (3PA) protocol of test budget that prioritizes faults with unique and diverse causal consequences, thereby increasing the likelihood of uncovering conditional fault propagations. Furthermore, to avoid incorrectly connecting fault propagations from workloads with incompatible conditions, CSnake performs a local compatibility check that approximately checks the compatibility of the path constraints associated with connected fault propagations with low overhead.

CSnake has detected 15 bugs that resulted in self-sustaining cascading failures in five widely deployed distributed systems, five of which have been confirmed with two fixed.