Graph-Free Root Cause Analysis
Organizations: RMIT University, Australia.
Abstract
Failures in complex systems demand rapid Root Cause Analysis (RCA) to prevent cascading damage. Graph-free RCA methods typically assume that the root cause has the highest anomaly score. This assumption fails when faults propagate, because a small deviation at the root cause can grow into a larger anomaly downstream. Our key observation is that a root cause deviates in both its internal properties (e.g., resource usage) and external properties (e.g., latency), whereas components affected by propagation deviate only in external properties. We propose CIE, a framework that ranks components by combining their internal and external anomaly scores. We formalize a class of component-based systems and state conditions under which CIE provably ranks the root cause first. The guarantee holds under arbitrary amplification for a conjunctive score, and under bounded amplification and a stronger root-cause condition for the default additive score. On 735 failures in nine datasets from three microservice systems, CIE achieves 68% Top-1 accuracy averaged over 11 fault types, a 21% relative improvement over the best of twelve baselines, while requiring 8 ms per diagnosis.
Figures & tables
| System (RE1/RE2/RE3) | #Components | #Properties | #Faults | #Cases |
|---|---|---|---|---|
| Online Boutique (OB) | 12 | 49/72/69 | 5/6/5 | 125/90/30 |
| Sock Shop (SS) | 13 | 59/75/80 | 5/6/4 | 125/90/30 |
| Train Ticket (TT) | 64 | 220/369/315 | 5/6/4 | 125/90/30 |
| Total | 12–64 | 49–369 | 11 | 735 |
| Method | AVERAGE | STAT | ||
|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | p-value | |
| Counterfactual | 0.07 | 0.12 | 0.12 | (+) |
| RCLAgent ∗ | 0.10 | 0.18 | 0.16 | (+) |
| Smooth-Traversal | 0.05 | 0.19 | 0.16 | (+) |
| PC-PageRank | 0.09 | 0.21 | 0.21 | (+) |
| Cholesky | 0.09 | 0.22 | 0.22 | (+) |
| Rank | Root Cause Candidate | Anomaly Score |
|---|---|---|
| 1 | emailservice - latency | |
| 2 | currencyservice - diskio | |
| 3 | redis - diskio | |
| 4 | currencyservice - latency |
| Category | Variant | Top-1 | Top-3 | Top-5 | Avg@5 | Time (ms) |
|---|---|---|---|---|---|---|
| Anomaly Scoring | z-score † | 0.68 | 0.91 | 0.98 | 0.87 | 12.6 |
| IQR | 0.65 | 0.80 | 0.85 | 0.78 | 16.2 | |
| IT-z-score | 0.14 | 0.51 | 0.75 | 0.48 | 35.9 | |
| IT-IQR | 0.13 | 0.48 | 0.72 | 0.45 | 35.7 | |
| Score Pooling | max † | 0.68 | 0.91 | 0.98 | 0.87 | 12.6 |
| sum | 0.69 | 0.93 | 0.98 | 0.89 | 13.2 |
| Method | Top-1 | Top-3 | Top-5 | Avg@5 | Time (ms) |
|---|---|---|---|---|---|
| 0.19 | 0.74 | 0.85 | 0.63 (+) | 10.6 | |
| 0.15 | 0.65 | 0.77 | 0.56 (+) | 11.1 | |
| 0.54 | 0.81 | 0.89 | 0.77 (+) | 11.9 | |
| CIE | 0.68 | 0.91 | 0.98 | 0.87 | 12.6 |
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| Method | CPU | DELAY | DISK | LOSS | MEM | AVERAGE | STAT | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| Smooth-Traversal | 0.04 | 0.25 | 0.19 | 0.08 | 0.20 | 0.16 | 0.04 | 0.08 | 0.07 | 0.04 | 0.17 | 0.13 | 0.08 | 0.16 | 0.13 | 0.06 | 0.17 | 0.14 | (+) |
| Simple-Traversal | 0.08 | 0.12 | 0.11 | 0.08 | 0.24 | 0.22 | 0.04 | 0.20 | 0.16 | 0.08 | 0.17 | 0.16 | 0.08 | 0.16 | 0.13 | 0.07 | 0.18 | 0.16 | (+) |
| Counterfactual | 0.04 | 0.12 | 0.13 | 0.08 | 0.28 | 0.27 | 0.20 | 0.24 | 0.30 | 0.12 | 0.25 | 0.27 | 0.08 | 0.16 | 0.20 | 0.11 | 0.21 | 0.23 | (+) |
| Cholesky | 0.08 | 0.20 | 0.22 | 0.08 | 0.24 | 0.22 | 0.12 | 0.28 | 0.28 | 0.16 | 0.32 | 0.34 | 0.12 | 0.16 | 0.24 | 0.11 | 0.24 | 0.26 | (+) |
| PC-PageRank | 0.00 | 0.12 | 0.13 | 0.08 | 0.16 | 0.19 | 0.16 | 0.44 | 0.42 | 0.04 | 0.36 | 0.31 | 0.08 | 0.24 | 0.26 | 0.07 | 0.26 | 0.26 | (+) |
| Method | CPU | DELAY | DISK | LOSS | MEM | AVERAGE | STAT | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| Counterfactual | 0.16 | 0.24 | 0.22 | 0.08 | 0.12 | 0.12 | 0.16 | 0.24 | 0.21 | 0.04 | 0.04 | 0.04 | 0.16 | 0.16 | 0.18 | 0.12 | 0.16 | 0.15 | (+) |
| Smooth-Traversal | 0.12 | 0.24 | 0.22 | 0.00 | 0.24 | 0.22 | 0.04 | 0.16 | 0.14 | 0.00 | 0.16 | 0.11 | 0.04 | 0.20 | 0.17 | 0.04 | 0.20 | 0.17 | (+) |
| PC-PageRank | 0.20 | 0.24 | 0.27 | 0.20 | 0.28 | 0.25 | 0.20 | 0.40 | 0.32 | 0.24 | 0.44 | 0.39 | 0.04 | 0.24 | 0.18 | 0.18 | 0.32 | 0.28 | (+) |
| Cholesky | 0.08 | 0.20 | 0.23 | 0.08 | 0.20 | 0.21 | 0.04 | 0.32 | 0.34 | 0.12 | 0.36 | 0.40 | 0.12 | 0.40 | 0.37 | 0.09 | 0.30 | 0.31 | (+) |
| Simple-Traversal | 0.16 | 0.32 | 0.32 | 0.08 | 0.32 | 0.30 | 0.08 | 0.36 | 0.35 | 0.12 | 0.32 | 0.31 | 0.12 | 0.28 | 0.27 | 0.11 | 0.32 | 0.31 | (+) |
| Method | CPU | DELAY | DISK | LOSS | MEM | AVERAGE | STAT | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| PC-PageRank | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.02 | 0.00 | 0.00 | 0.00 | (+) |
| Counterfactual | 0.00 | 0.08 | 0.08 | 0.00 | 0.04 | 0.02 | 0.00 | 0.04 | 0.03 | 0.00 | 0.00 | 0.00 | 0.00 | 0.04 | 0.02 | 0.00 | 0.04 | 0.03 | (+) |
| Simple-Traversal | 0.00 | 0.04 | 0.06 | 0.00 | 0.04 | 0.02 | 0.00 | 0.00 | 0.01 | 0.00 | 0.00 | 0.03 | 0.00 | 0.04 | 0.02 | 0.00 | 0.02 | 0.03 | (+) |
| Smooth-Traversal | 0.00 | 0.00 | 0.01 | 0.04 | 0.08 | 0.06 | 0.00 | 0.04 | 0.03 | 0.00 | 0.04 | 0.03 | 0.00 | 0.00 | 0.02 | 0.01 | 0.03 | 0.03 | (+) |
| Cholesky | 0.04 | 0.12 | 0.12 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.05 | 0.00 | 0.04 | 0.05 | 0.00 | 0.00 | 0.02 | 0.01 | 0.03 | 0.05 | (+) |
| Method | CPU | DELAY | DISK | LOSS | MEM | SOCKET | AVERAGE | STAT | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| Simple-Traversal | 0.07 | 0.13 | 0.12 | 0.00 | 0.13 | 0.12 | 0.00 | 0.07 | 0.05 | 0.07 | 0.13 | 0.16 | 0.13 | 0.13 | 0.17 | 0.00 | 0.13 | 0.11 | 0.04 | 0.12 | 0.12 | (+) |
| Smooth-Traversal | 0.07 | 0.13 | 0.11 | 0.00 | 0.07 | 0.07 | 0.00 | 0.13 | 0.12 | 0.07 | 0.20 | 0.19 | 0.07 | 0.33 | 0.24 | 0.00 | 0.20 | 0.13 | 0.03 | 0.18 | 0.14 | (+) |
| PC-PageRank | 0.00 | 0.20 | 0.23 | 0.13 | 0.20 | 0.24 | 0.00 | 0.07 | 0.09 | 0.00 | 0.13 | 0.13 | 0.00 | 0.07 | 0.08 | 0.00 | 0.20 | 0.12 | 0.02 | 0.14 | 0.15 | (+) |
| Counterfactual | 0.00 | 0.20 | 0.15 | 0.20 | 0.27 | 0.24 | 0.13 | 0.27 | 0.24 | 0.07 | 0.13 | 0.13 | 0.13 | 0.13 | 0.13 | 0.13 | 0.13 | 0.13 | 0.11 | 0.19 | 0.17 | (+) |
| Cholesky | 0.07 | 0.13 | 0.16 | 0.07 | 0.13 | 0.17 | 0.13 | 0.27 | 0.23 | 0.07 | 0.07 | 0.13 | 0.07 | 0.13 | 0.16 | 0.07 | 0.27 | 0.25 | 0.08 | 0.17 | 0.18 | (+) |
| Method | CPU | DELAY | DISK | LOSS | MEM | SOCKET | AVERAGE | STAT | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| Counterfactual | 0.13 | 0.13 | 0.13 | 0.00 | 0.07 | 0.04 | 0.13 | 0.27 | 0.24 | 0.27 | 0.27 | 0.29 | 0.07 | 0.07 | 0.07 | 0.07 | 0.07 | 0.12 | 0.11 | 0.14 | 0.15 | (+) |
| Smooth-Traversal | 0.20 | 0.27 | 0.24 | 0.00 | 0.13 | 0.08 | 0.00 | 0.27 | 0.21 | 0.00 | 0.20 | 0.12 | 0.13 | 0.27 | 0.21 | 0.13 | 0.27 | 0.28 | 0.08 | 0.23 | 0.19 | (+) |
| PC-PageRank | 0.20 | 0.33 | 0.29 | 0.07 | 0.33 | 0.27 | 0.13 | 0.20 | 0.20 | 0.13 | 0.27 | 0.21 | 0.13 | 0.27 | 0.24 | 0.33 | 0.40 | 0.41 | 0.17 | 0.30 | 0.27 | (+) |
| Cholesky | 0.07 | 0.27 | 0.27 | 0.07 | 0.13 | 0.20 | 0.20 | 0.53 | 0.40 | 0.07 | 0.40 | 0.35 | 0.00 | 0.07 | 0.16 | 0.07 | 0.40 | 0.33 | 0.08 | 0.30 | 0.28 | (+) |
| Simple-Traversal | 0.27 | 0.40 | 0.37 | 0.07 | 0.47 | 0.40 | 0.07 | 0.60 | 0.44 | 0.00 | 0.40 | 0.25 | 0.20 | 0.40 | 0.35 | 0.20 | 0.33 | 0.31 | 0.13 | 0.43 | 0.35 | (+) |
| Method | CPU | DELAY | DISK | LOSS | MEM | SOCKET | AVERAGE | STAT | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| PC-PageRank | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | (+) |
| RCLAgent | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | (+) |
| Counterfactual | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.07 | 0.07 | 0.00 | 0.00 | 0.01 | 0.00 | 0.07 | 0.05 | 0.00 | 0.00 | 0.00 | 0.00 | 0.02 | 0.02 | (+) |
| Simple-Traversal | 0.00 | 0.00 | 0.03 | 0.00 | 0.00 | 0.01 | 0.07 | 0.07 | 0.07 | 0.00 | 0.00 | 0.03 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.01 | 0.01 | 0.02 | (+) |
| Cholesky | 0.00 | 0.13 | 0.08 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.07 | 0.07 | 0.07 | 0.00 | 0.00 | 0.01 | 0.00 | 0.07 | 0.05 | 0.01 | 0.04 | 0.04 | (+) |
| Method | F1 | F2 | F3 | F4 | F5 | AVERAGE | STAT | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| Smooth-Traversal | 0.11 | 0.11 | 0.11 | 0.00 | 0.33 | 0.27 | 0.00 | 0.17 | 0.13 | 0.17 | 0.17 | 0.17 | 0.00 | 0.17 | 0.13 | 0.06 | 0.19 | 0.16 | (+) |
| Counterfactual | 0.11 | 0.11 | 0.11 | 0.33 | 0.33 | 0.47 | 0.00 | 0.17 | 0.13 | 0.00 | 0.17 | 0.13 | 0.00 | 0.00 | 0.00 | 0.09 | 0.16 | 0.17 | (+) |
| Cholesky | 0.11 | 0.33 | 0.27 | 0.00 | 0.33 | 0.20 | 0.33 | 0.50 | 0.43 | 0.00 | 0.00 | 0.10 | 0.33 | 0.33 | 0.37 | 0.16 | 0.30 | 0.27 | (+) |
| RCLAgent | 0.25 | 0.25 | 0.25 | 0.00 | 0.00 | 0.00 | 0.17 | 0.33 | 0.30 | 0.33 | 0.50 | 0.47 | 0.17 | 0.50 | 0.40 | 0.18 | 0.32 | 0.28 | (+) |
| PC-PageRank | 0.11 | 0.22 | 0.33 | 0.00 | 0.00 | 0.27 | 0.00 | 0.17 | 0.13 | 0.00 | 0.33 | 0.27 | 0.33 | 0.50 | 0.57 | 0.09 | 0.24 | 0.31 | (+) |
| Method | F1 | F2 | F3 | F4 | AVERAGE | STAT | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| Counterfactual | 0.10 | 0.30 | 0.30 | 0.00 | 0.00 | 0.07 | 0.10 | 0.10 | 0.14 | 0.14 | 0.43 | 0.34 | 0.09 | 0.21 | 0.21 | (+) |
| BRCD | 0.00 | 0.10 | 0.14 | 0.00 | 0.33 | 0.40 | 0.00 | 0.20 | 0.24 | 0.00 | 0.29 | 0.20 | 0.00 | 0.23 | 0.25 | (+) |
| RCD | 0.00 | 0.30 | 0.28 | 0.00 | 0.00 | 0.33 | 0.00 | 0.30 | 0.28 | 0.14 | 0.43 | 0.46 | 0.04 | 0.26 | 0.34 | (+) |
| DoWhy-GCM | 0.61 | 0.73 | 0.71 | 0.00 | 0.00 | 0.00 | 0.20 | 0.40 | 0.38 | 0.18 | 0.39 | 0.36 | 0.25 | 0.38 | 0.36 | ( ) |
| PC-PageRank | 0.20 | 0.40 | 0.42 | 0.00 | 0.33 | 0.27 | 0.00 | 0.20 | 0.18 | 0.29 | 0.57 | 0.57 | 0.12 | 0.38 | 0.36 | (+) |
| Method | F1 | F2 | F3 | F4 | AVERAGE | STAT | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | Top-1 | Top-3 | Avg@5 | p-value | |
| BRCD | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | (+) |
| PC-PageRank | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | (+) |
| RCLAgent | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | (+) |
| RCD | 0.00 | 0.00 | 0.03 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.01 | (+) |
| Smooth-Traversal | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.04 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.01 | (+) |
| Fault Type | Int First | Median | |
|---|---|---|---|
| Resource Faults | |||
| CPU | 117 | 76.9% | s |
| DISK | 113 | 73.5% | s |
| MEM | 120 | 65.8% | s |
| SOCKET | 45 | 64.4% | s |
| Network Faults | |||
| Group | Top-1 | Top-3 | |
|---|---|---|---|
| Not flagged | 292 | 0.764 | 0.966 |
| Flagged | 113 | 0.566 | 0.867 |
| Degradation | 19.7 pp | 9.8 pp |
| Post-failure data | Top-1 | Top-3 | Top-5 | Avg@5 |
|---|---|---|---|---|
| 1 sample | 0.65 | 0.84 | 0.90 | 0.81 |
| 10% (36–210 samples) | 0.81 | 0.97 | 0.99 | 0.93 |
| 100% (all samples) | 0.68 | 0.91 | 0.98 | 0.87 |
Root Cause Analysis
Root cause analysis identifies the initiating faults behind observed failures by tracing symptoms through causal and system dependencies.
See all 91 papers