Automated Failure Analysis in Model Checking Based on Data Mining

Ning Ge, Marc Pantel, Xavier CrégutMEDI 2014 · DOI

TL;DR

This paper introduces an automated approach to pinpoint the root causes of failures in model checking, a crucial technique for verifying complex systems. By adapting data mining techniques like TF-IDF and KL-Divergence, the authors develop a "suspiciousness factor" to rank potentially faulty transitions within error traces, significantly easing the debugging process for engineers.

What Problem Does This Paper Address?

Model checking is a powerful tool for verifying the correctness of systems, but when a property is violated, it generates "counterexamples" – long sequences of states and transitions that are often difficult for humans to decipher. This makes it challenging and time-consuming to identify the exact design flaw. While existing methods can flag suspicious elements, they often lack a clear ranking, leaving engineers to sift through numerous possibilities. This paper aims to automate and accelerate this failure analysis by providing a ranked list of the most likely culprits.

Methods

The core of the proposed approach is inspired by data mining techniques used for information retrieval and text analysis. Specifically, the authors adapt the Kullback-Leibler (KL) Divergence and Term Frequency-Inverse Document Frequency (TF-IDF) measures.

  • Suspiciousness Factor (Fault Contribution): They define a "Fault Contribution" (CF) for each transition, analogous to how TF-IDF measures the importance of a term in a document. This CF is calculated based on two components:
  • Transition Contribution (TC): This measures how frequently a transition appears in the identified error traces.
  • Inverse Trace Contribution (ITC): This assesses how "rare" or common a transition is across all error traces, similar to how IDF highlights terms that are specific to certain documents.
  • Error Trace Construction: The method first identifies "violation states" in the system's reachability graph. Then, it constructs "error traces" by considering all paths from the initial state to these violation states, including transitions that lead to correct states as well, as these can indirectly influence faulty behavior.
  • Time Petri Nets (TPN): The approach is applied to Time Petri Nets, a formalism that models concurrent systems with timing constraints.

Datasets

The paper uses two main case studies for evaluation:

  • BCET (Best Case Execution Time) Property Case Study: This is a custom TPN model designed to illustrate the failure analysis algorithm.
  • Automated Deadlock Property Test Bed: This is a newly designed benchmark where systems with potential deadlocks are randomly generated. The test bed creates systems with known faulty transitions (e.g., forgetting to release a resource) and then applies the proposed method to see how well it identifies them.

Key Insights and Ideas

  • Analogy between Text and System Failures: The paper effectively draws a parallel between finding important terms in documents and finding faulty transitions in system execution traces. This analogy is key to adapting data mining techniques.
  • Ranking is Crucial: Simply identifying suspicious elements isn't enough. The ability to rank them by a "suspiciousness factor" significantly improves the efficiency of debugging.
  • Indirect Influence of Transitions: The authors correctly identify that transitions leading to correct states can still be relevant to failure analysis because they can influence the timing or execution of other transitions that directly lead to a violation.
  • Heuristics for BCET: For the BCET property, the paper highlights interesting heuristics: symmetric pairs of transitions where one has a smaller execution time range is more likely to be faulty, and transitions that are always executed (regardless of system correctness) are less suspicious.

Key Results

  • Efficiency: The automated deadlock property test bed generated thousands of test cases. The average analysis time for these cases was consistently low (e.g., around 2-15 seconds on a 2.4 GHz Intel Core 2 Duo processor), demonstrating the efficiency of the approach.
  • Effectiveness (EXAM Score): The effectiveness was measured using the EXAM score, which represents the percentage of transitions that need to be examined until the first faulty transition is found. For best-case scenarios, the EXAM score averaged between 3% and 16%, meaning the algorithm successfully ranked the faulty transition very high in the list of suspicious elements. This significantly reduces the manual effort required for debugging.

Limitations and Future Work

  • Subjectivity in Heuristics: The paper acknowledges that quantifying fault contribution, especially for complex properties like BCET, can involve subjective measures and context-dependent heuristics.
  • Safety Properties Focus: The current work primarily focuses on safety properties (ensuring "nothing bad happens").
  • Future Work: The authors suggest extending this approach to analyze liveness properties (ensuring "something good eventually happens"), which would involve applying similar statistical methods to failure analysis of these types of properties. They also mention the potential for applying these statistical methods to other verification models beyond TPNs, such as timed automata.

Summary updated

BibTeX
@inproceedings{ge2014automated,
  author = {Ning Ge and Marc Pantel and Xavier Crégut},
  title = {{Automated Failure Analysis in Model Checking Based on Data Mining}},
  booktitle = {MEDI},
  year = {2014},
  doi = {10.1007/978-3-319-11587-0\_4},
}
Figure