TL;DR
This paper tackles the challenge of diagnosing system failures when multiple observations are available, a common scenario in continuous integration. Existing methods struggle with computational complexity and often produce non-minimal diagnoses. The authors propose a novel, scalable algorithm based on hitting set dualization that efficiently computes minimal diagnoses and explanations, significantly outperforming previous approaches.
What Problem Does This Paper Address?
Debugging complex systems, whether software, hardware, or cyber-physical, is a critical task. Model-Based Diagnosis (MBD) is a principled approach that uses a system's model to pinpoint faulty components. While MBD has been successful, a growing challenge arises in scenarios with multiple, simultaneous observations of system behavior, particularly in continuous integration (CI) environments like Jenkins or Travis CI. These CI systems execute numerous tests, and when multiple tests fail, it's crucial to diagnose the root cause efficiently.
Existing MBD techniques, when applied to multiple observations, face two main issues:
- Computational Complexity: The problem size can explode, leading to prohibitively long runtimes.
- Non-Minimal Diagnoses: Current algorithms may produce diagnoses that are not the smallest possible sets of faulty components, making them less useful and contributing to the computational burden.
This paper aims to address these limitations by proposing a more efficient and accurate method for diagnosing systems with multiple failing observations.
Methods
The paper introduces a novel algorithm based on implicit hitting set dualization. This approach leverages the duality between diagnoses (minimal hitting sets of explanations) and explanations (minimal unsatisfiable subsets of a formula).
Here's a breakdown of the key methodological aspects:
- Encoding: The system description (SD) and observations are encoded into a CNF formula. For multiple observations, multiple replicas of the system are considered, sharing the abnormal variables.
- Hitting Set Dualization: The core of the proposed algorithm is Algorithm 1, which iteratively computes minimal hitting sets of explanations. This process is designed to directly yield minimal aggregated diagnoses without first generating non-minimal ones.
- Filtering Redundant Diagnoses: Unlike previous methods that might generate many redundant diagnoses and then filter them, the proposed algorithm inherently avoids generating non-minimal diagnoses by construction.
- Comparison with Existing Methods: The paper compares its approach against two existing methods:
- DiagCombine (DC): An algorithm that computes aggregated diagnoses by combining individual diagnoses from each observation.
- DC*: An improved version of DC that attempts to filter non-minimal diagnoses.
- SAT Solvers: The implementation utilizes SAT solvers (specifically Glucose 3) for consistency checks and finding minimal unsatisfiable subsets (MUSes).
- MaxSAT/MCS Algorithms: For finding minimal hitting sets, the paper leverages algorithms like LBX and OLLITI/RC2, which are state-of-the-art for enumerating minimal correction subsets (MCSes) and cardinality-minimal hitting sets.
Datasets
The experimental evaluation uses benchmarks from the ISCAS85 suite. To create test instances, single stuck-at faults were injected into each gate of these circuits, resulting in 2n faulty circuits (where n is the number of gates). For each faulty circuit, 100 unique observations were generated by using SAT to find satisfying assignments for a miter comparing the correct and faulty circuits. The authors note that they filtered out instances that resulted in more than 100 aggregated minimal diagnoses to focus on scenarios where diagnosis is still challenging but feasible.
Key Insights and Ideas
- The Inefficiency of Aggregation: A key insight is that simply combining individual diagnoses from multiple observations (as in the DC algorithm) leads to a combinatorial explosion and the generation of many redundant, non-minimal diagnoses. This is a significant bottleneck.
- Direct Generation of Minimal Diagnoses: The proposed hitting set dualization approach offers a more elegant solution by directly computing minimal aggregated diagnoses, bypassing the generation and filtering of redundant ones. This is a major conceptual improvement.
- Scalability is Achievable: The paper demonstrates that despite the inherent complexity of diagnosing multiple observations, a scalable solution is indeed possible through clever algorithmic design, specifically by leveraging hitting set dualization.
- Practical Relevance: The problem is highly relevant to modern software development practices like continuous integration, where multiple test failures are common and efficient diagnosis is crucial for rapid debugging.
Key Results
The experimental results highlight a dramatic performance improvement of the proposed hitting set dualization (HSD) approach:
- Runtime: HSD outperforms both DiagCombine (DC) and its improved version (DC*) by 2-4 orders of magnitude in terms of running time. HSD successfully solved all 144 problem instances within the given limits, while DC and DC* could only handle 110 and 128 instances, respectively.
- Number of Diagnoses:
- Individual Diagnoses (Step 1 of DC/DC*): The DC/DC* approaches had to compute a vast number of individual diagnoses per observation (up to 10⁵), which is orders of magnitude more than the number of correct minimal aggregated diagnoses (at most 100).
- Redundant Diagnoses (Step 2 of DC/DC*): While DC* significantly reduced the number of redundant diagnoses compared to DC (by 1-6 orders of magnitude), it still produced a substantial number (10-20000) in many cases. HSD, by construction, avoids generating these redundant diagnoses.
Limitations and Future Work
- Exponential Explanations: A potential limitation of Algorithm 1 is that if a system has an exponential number of explanations, the algorithm might end up enumerating them, which could be computationally expensive. However, the authors note that their experiments did not observe this worst-case behavior.
- Future Work: The authors suggest that their proposed ideas are applicable to other MBD domains like software fault localization and design debugging. Future work could explore these applications and potentially devise more specific conditions for filtering redundant diagnoses, although they acknowledge that a complete polynomial-time solution for filtering might be unrealistic.
Summary updated