ACCBench: A Framework for Comparing Causality Algorithms

Simon Rehwald, Amjad Ibrahim, Kristian Beckers, Alexander Pretschner

TL;DR

This paper introduces ACCBench, a novel benchmark framework designed to rigorously compare and evaluate causality algorithms for identifying the root causes of unwanted behavior in complex socio-technical systems. By providing a consistent evaluation setting and introducing new metrics, ACCBench aims to shed light on the practical effectiveness and performance of these algorithms, which is currently lacking in the research landscape.

What Problem Does This Paper Address?

Modern socio-technical systems, from autonomous vehicles to industrial control systems, are becoming increasingly complex. This complexity makes them prone to unexpected and unwanted behaviors, which can have serious consequences. Identifying the root cause of these failures is crucial for accountability, allowing us to understand why a system failed and who or what is responsible. While several algorithms have been proposed to address this causality detection problem, their practical applicability, effectiveness, and performance remain largely unknown due to a lack of standardized evaluation methods and consistent benchmarks. This makes it difficult for researchers and practitioners to choose the most suitable algorithm for a given scenario.

Methods

The core contribution of this paper is the ACCBench framework. ACCBench provides a standardized environment for comparing causality algorithms. Its key components include:

  • Consistent Setting: ACCBench ensures that all algorithms are evaluated under the same assumptions and with access to the same system information (system/world model) and event logs.
  • Quantitative Metrics: The paper introduces two main approaches for evaluating algorithm effectiveness:
  • "Normal" Binary Classification: This method uses standard precision, recall, and F1-measure metrics, treating each hypothesized cause as either entirely correct or entirely incorrect.
  • "Modified" Binary Classification: This approach relaxes the strictness of the "normal" classification by allowing for partial correctness. It uses a "best match" strategy to quantify the similarity between hypothesized and actual causes, enabling a more nuanced evaluation.
  • Performance Metrics: ACCBench measures execution time and memory allocation for algorithm analysis.
  • Implemented Algorithms: The authors implemented and evaluated three algorithms:
  • Two causality algorithms based on language-based modeling ([7]) and timed automata ([6]).
  • One policy compliance algorithm inspired by concepts in [16], which differs by focusing on rule violations rather than explicitly detecting "unwanted behavior."

Datasets

The paper uses a case study involving an Intelligent Door Control System to evaluate the algorithms.

  • Event Logs: 46 event logs were generated for this system using CPNTools. These logs were created based on hazard and threat analysis, simulating various scenarios, including those with and without unwanted behavior. Logs for effectiveness evaluation contained between 7 and 58 entries, while logs for performance analysis had between 550 and 2750 entries.
  • Benchmark: ACCBench itself serves as a newly introduced benchmark tool. It differs from existing resources like the "Causality Workbench" by integrating comparison criteria directly into the software, rather than just providing datasets.

Key Insights and Ideas

  • The Need for Standardization: The lack of a common benchmark like ACCBench hinders the objective comparison and adoption of causality algorithms.
  • Effectiveness vs. Policy Compliance: Causality algorithms generally perform better than policy compliance approaches when the goal is to identify the root cause of unwanted behavior. Policy compliance algorithms, by simply flagging rule violations, can over-attribute blame when no actual system failure occurs.
  • Nuance in Evaluation: The "modified" binary classification metric is crucial for capturing partial correctness, acknowledging that an algorithm might not find the exact cause but still provide valuable insights.
  • Model Abstraction Matters: The choice of modeling approach (e.g., language-based vs. timed automata) significantly impacts the intuitiveness and complexity of configuring algorithms, as well as their performance.
  • Performance Trade-offs: Causality algorithms, especially those relying on complex modeling like timed automata, can incur significant performance costs, particularly with larger log sizes.

Key Results

  • Effectiveness:
    • In scenarios with no unwanted behavior, the policy compliance algorithm performed poorly due to its tendency to flag all incorrect events. The causality algorithms achieved perfect scores in these cases.
  • In scenarios with unwanted behavior, the two causality algorithms ([7] and [6]) generally outperformed the policy compliance approach, though their metrics were not always perfect (e.g., recall and F1-measure often below 1.0).
  • The timed automata-based causality algorithm ([6]) showed slightly better results than the language-based one ([7]) in some categories.
  • Performance:
    • The policy compliance algorithm demonstrated significantly higher performance (lower execution time) compared to the causality algorithms, especially for larger log files.
  • The language-based causality algorithm ([7]) and the policy compliance approach had execution times in the seconds or milliseconds range, while the timed automata-based algorithm ([6]) could exceed five minutes for larger logs due to model checking.
  • The performance of causality algorithms was influenced by the location of incorrect behavior within the log and the number of misbehaving components.

Limitations and Future Work

  • Limitations:
    • The case study used a simplified example with simulated logs, which might not fully represent real-world complexities.
  • The paper acknowledges that the definition of "cause" can vary between algorithms, making direct comparison challenging unless definitions are congruent.
  • The implemented causality algorithms ([7] and [6]) do not explicitly address the minimality of causes.
  • The policy compliance algorithm ([16]) does not have an explicit notion of "unwanted behavior," only policy violations.
  • Future Work:
    • Apply ACCBench to real-world systems to assess the required pre-processing effort.
  • Conduct further research to achieve more meaningful statements about algorithm quality.
  • Investigate approaches to address the performance degradation of algorithms with larger event logs.
  • Extend the qualitative analysis to include more dimensions.

Summary updated

Abstract

Modern socio-technical systems are increasingly complex. A fundamental problem is that the borders of such systems are often not well-defined a-priori, which among other problems can lead to unwanted behavior during runtime. Ideally, unwanted behavior should be prevented. If this is not possible the system shall at least be able to help determine potential cause(s) a-posterori, identify responsible parties and make them accountable for their behavior. Recently, several algorithms addressing these concepts have been proposed. However, the applicability of the corresponding approaches, specifically their effectiveness and performance, is mostly unknown. Therefore, in this paper, we propose ACCBench, a benchmark tool that allows to compare and evaluate causality algorithms under a consistent setting. Furthermore, we contribute an implementation of the two causality algorithms by Gößler and Metayer and Gößler and Astefanoaei as well as of a policy compliance approach based on some concepts of Main et al. Lastly, we conduct a case study of an Intelligent Door Control System, which exposes concrete strengths and weaknesses of all algorithms under different aspects. In the course of this, we show that the effectiveness of the algorithms in terms of cause detection as well as their performance differ to some extent. In addition, our analysis reports on some qualitative aspects that should be considered when evaluating each algorithm. For example, the human effort needed to configure the algorithm and model the use case is analyzed.
BibTeX
@misc{rehwald2017accbench,
  author = {Simon Rehwald and Amjad Ibrahim and Kristian Beckers and Alexander Pretschner},
  title = {{ACCBench: A Framework for Comparing Causality Algorithms}},
  year = {2017},
  eprint = {1710.05720},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.05720},
}
Figure