Formal Methods and Tools

Formal methods for risk analysis

For background information on the topic as a whole, scroll to the end of this page.

Available project proposals

The most likely causes of faults (Milan Lopuhaä-Zwakenberg, Benedikt Peterseim, Reza Soltani)

Supervisors: Benedikt Peterseim, Reza Soltani, Milan Lopuhaä-Zwakenberg

Fault tree analysis is a rigorous and widely applied method for understanding what can go wrong, whether it concerns aeroplanes, trains, or critical infrastructure. They also allow for estimating the probability of a fault. Causality introduces the question of why things go wrong.

In this project, you will investigate how probabilities and causality interact in fault trees. The first step will be to understand the definition(s) of so-called actual causes in fault trees. Next, you will write a simple program that computes the probabilities of causes according to this definition. This will allow you to critically assess the real-world meaning of actual causality. Ordering causes by their probability will enable a comparison to the established methods of finding which basic failures in a system contribute most to its overall failure.

All in all, this may help with developing causal methods in fault tree analysis, and with understanding causility better in general. Equally importantly, it will give you a great opportunity to learn about these fascinating topics.

Improving CPS Model Transformation for Fault Tree Generation (Georgiana Caltais, Aimé Ntagengerwa)

Project Overview

This project focuses on transforming Cyber-Physical System (CPS) models into Fault Trees (FTs) using knowledge graphs (KGs). A methodology exists for this transformation, but it has several limitations. The goal of this project is to explore and improve different aspects of this methodology.

You can choose from one of the following research directions, depending on your interests: 

Project Option 1: Addressing Methodological Limitations

The existing methodology generates FTs from KGs but faces certain challenges. This project will analyze and propose improvements to these limitations:

  • Redundancy Inference Issues: The method attempts to infer system redundancy but may overestimate CPS robustness. How can we refine the approach?
  • Structural Complexity: Current FTs rely on functional dependency, but real systems have hierarchical component compositions (sub-systems within sub-systems). How can we extend the method to represent these structures more accurately?

Skills & Interests:

  • Systems modeling and formal methods
  • Algorithm development

  

Project Option 2: Improving the Python Tool Implementation

A simple Python tool implements this methodology, but it is limited in usability and performance. This project will focus on improving the tool by addressing:

  • User-Friendliness: The current implementation is hard-coded and not intuitive. Can we design a better UI/UX or modular software architecture?
  • Performance Optimization: The tool is not optimized for speed. Can we implement more efficient algorithms to generate FTs faster?

Skills & Interests:

  • Software engineering, UI/UX design
  • Performance optimization

 

Project Option 3: Exploring Alternative Data Representations

The existing tool relies on KGs for FT generation. This project will investigate whether a relational database (SQL) could be a viable alternative:

  • Performance Comparison: Would using a relational database improve efficiency?
  • Feature Trade-offs: Would moving away from KGs means compromising essential features?

Skills & Interests:

  • Data structures and database management
  • Comparative analysis of modeling approaches

 

Expected Outcomes

  • A refined methodology for FT generation (Option 1)
  • An improved, user-friendly, and optimized tool (Option 2)
  • A performance and feasibility study comparing KGs vs. relational databases (Option 3)

 

Connection to the ZORRO Project

All these options contribute to ongoing research in the Zero Downtime for Cyber-Physical Systems (ZORRO) consortium:

  • The already existing methodology will be applied at an industry partner. We expect that it will need to be tweaked to:
  • Not over-approximate a CPS's robustness;Be able to handle that company's data volume, and;Align within the company's existing database infrastructure.

Your contribution in any of these directions will help guide the refinement of the methodology.

Investigating safety/security interactions in real-world scenarios (Milan Lopuhaä-Zwakenberg, Reza Soltani)

Supervisors: Milan Lopuhaä-Zwakenberg, Reza Soltani

The introduction and adoption of new technologies implies the rise of new risks, related both to accidental damage (safety) and to malicious attacks (security). Furthermore, safety and security are often intertwined: passwords protect medical data from unauthorized access but are an obstacle for patients' safety during emergencies, IoT sensors can help to monitor the pressure levels of a pipeline but may provide extended attack surfaces for malicious hackers.
The existence of interdependencies between safety and security calls for a better (formal) understanding of this kind of interactions:

  • At what level do safety and security interact? What interacts with what?
  • Do these interactions regard requirements, countermeasures, factors (etc.)?

Tasks

The suggested tasks are the following:

  • Together with your supervisor, decide on an interesting case study in which safety and security interact. We have some suggestions (e.g. a drone assembly factory) but students are more than welcome to come up with interesting cases themselves.
  • Model the case study in a safety-security risk model, such as an attack-fault(-defense) tree or a Bayesian network.
  • Investigate how safety and security interact in your model, and what that implies for risk mitigation strategies.

For this topic, you should have a strong interest in multidisciplinary research.

Attack tree analysis (Milan Lopuhaä-Zwakenberg, Reza Soltani)

Supervisor: Milan Lopuhaä-Zwakenberg and Reza Soltani

Attack trees are a popular and useful tool to model a system's vulnerability to attackers. They are used in quantitative security analysis: they can be used to calculate security metrics such as the minimal time or resources an attacker needs to successfully compromise the system. As attack trees can grow quite large in practice, there is an ongoing need for algorithms that can calculate security metrics on a feasible timescale.

Recently, theoretic work has developed such algorithms, but there is still a lot of room for further research: implementations and rigorous experiments are still lacking, and many metrics are not covered by existing work. In this project, the student adds to this field of research by implementing proposed algorithms, inventing new ones, or analyzing the behaviour of existing methods. 

Better fault trees from data (Milan Lopuhaä-Zwakenberg)

Supervisor: Milan Lopuhaä-Zwakenberg

Fault trees (FTs) are one of the world's most popular risk models due to the combination of simplicity and expressivity. At their most simple form, FTs are just Boolean formulas, though many more expressive versions exist.

As high-tech systems grow more complex, the same is true for the FTs we use to understand the reliability of these systems. Manual construction of FTs for such systems is not only extremely cumbersome, but error-prone as well. This leads to the question: How can we get FTs from data? Some possible research directions include:

  • Boolean circuit design: Circuit designs aims to find circuits with a minimal number of logical gates representing a given Boolean function. FT models can be encoded by Boolean formulas. A possible research direction is to find and apply existing algorithms from circuit design for FT inference.
  • Guiding the evolutionary algorithms: there exist techniques based on evolutionary algorithms, but these take a long time to converge when randomly applying genetic operators. One possible research direction is therefore to investigate to what extent knowledge about the models can be included to guide the genetic operators.
  • Noisy and incomplete data sets: Current approaches only consider noise-free and complete failure data sets, which is of course not representative of real applications. Thus, it is interesting to investigate how to effectively deal and account for noise and incompleteness in failure data sets when inferring FT models in a data-driven manner.
Software fault trees (Reza Soltani, Aimé Ntagengerwa)

Supervisors: Reza Soltani, Aimé Ntagengerwa

Software Fault Trees: Analysing and Predicting Software Failures

How can we understand and predict failures in increasingly complex software systems?

Reliability is a crucial aspect of modern computer systems. Failures in software can have serious consequences, particularly in safety-critical applications such as railway control, medical devices, and industrial automation.

An established technique for analysing system reliability is Fault Tree Analysis (FTA). Fault trees formally model how individual component failures can combine to cause system-level failures, using logical gates such as AND and OR.

While this technique has been successfully applied to complex hardware systems, the growing importance of software calls for approaches that also account for software-related failures. This is where Software Fault Trees (SFTs) come into play!

Your Research Challenge

In this project, you will investigate how Software Fault Trees can be used to analyse and predict software failures. You will explore how they can be constructed, how effective they are, and what challenges remain.

Possible research directions include:

  • Automated fault tree generation: Can Software Fault Trees be generated automatically from software specifications, for example by translating UML diagrams?
  • Evaluating Software Fault Trees: How effective are they at identifying potential failure scenarios, and what are their limitations?

What You Will Learn

You will gain experience with software reliability engineering, formal modelling techniques, and the analysis and evaluation of software systems.

Interested in understanding what can go wrong in software, and how to predict it before it happens? This project is for you!

For more information, please contact r.soltani@utwente.nl. 

Learning risk distributions of fault trees (Milan Lopuhaä-Zwakenberg, Ernst Moritz Hahn)

Supervisors: Milan Lopuhaä-Zwakenberg, Ernst Moritz Hahn

Fault trees model how failures of system components (basic events) propagate through AND/OR gates to intermediate events and finally to a system-level top event. Classical quantitative fault-tree analysis computes the probability of the top event. In this project, we are instead interested in the distribution of the incurred cost (the risk): intermediate events (and/or the top event) are annotated with costs, e.g. repair cost, downtime, or lost revenue.

Each basic event occurs with a given probability; event costs may be fixed values or continuous random variables. Monte Carlo sampling of the basic events induces a probability distribution over the total incurred cost. Because the failure structure is discrete but the costs can be continuous, the resulting risk distribution is a very complex discrete distribution. The objective of this project is to approximate it using a continuous probability distribution such as a normal distribution: such a distribution yields a smooth density. Given the right choice of distribution, doing so can be useful because it provides closed-form expressions for common risk measures such as Value-at-Risk and Expected Shortfall.

Pipeline of the project. Top: a fault tree. Middle: the resulting histogram of total costs, obtained using Monte Carlo simulation. Bottom: the fitted distribution, which provides a smooth approximation of the risk distribution.

Tasks

  1. Implement a sampling-based evaluator for fault trees.
  2. Perform sampling to obtain an approximate discrete probability distribution of the risk.
  3. Find out which type of distribution is appropriate by fitting it to the discrete probability distribution.
  4. Derive risk measures from the distribution such as expected loss, quantiles, Value-at-Risk (VaR), Expected Shortfall (ES).
  5. Evaluate the method on existing or new fault trees.

Optional extensions

  • Validate the distribution against the empirical distribution (histogram/ECDF) and against alternatives (kernel density estimation, log-normal fit, or the exact discrete distribution when costs are fixed).
  • Investigate sensitivity to the number of samples, the number of parameters of the distribution, the cost model, and the tree structure.
  • Rare-event simulation (importance sampling, subset simulation) for unlikely top events.
  • Using methods other than simulation to obtain the initial cost distribution.
  • Attack-tree variant: distribution of the cost of successful attacks, where costs are attached to basic events (representing the attacker’s effort per step) and AND nodes sum step costs while OR nodes take the minimum over alternative attack paths.

Related literature

  • R. Kumar, M. Stoelinga: Quantitative Security and Safety Analysis with Attack-Fault Trees (2017).
  • Kaber, Liu, Lau: Considering Severity of Safety-Critical System Outcomes in Risk Analysis: An Extension of Fault Tree Analysis (2023).
  • Cyber Value-at-Risk models generating loss distributions via Monte Carlo (e.g. Erola et al., 2022).
Can an AI Defender Outsmart a Hacker? (Reza Soltani, Milan Lopuhaä-Zwakenberg)

Supervisors: Reza Soltani, Milan Lopuhaä-Zwakenberg

Two agents compete in a simulated cyberattack scenario. Can a defender learn to make better decisions than traditional rule-based security mechanisms?

What the student does: Build a small attacker–defender simulation and compare a rule-based defender, a random defender, and a defender using a simple reinforcement-learning algorithm (such as tabular Q-learning).

Research question: Under which conditions does a learning-based defender outperform fixed defense strategies in terms of attack success and defense costs?

Manageable scope: One attacker with a small predefined set of attack policies, one learning defender, 3–5 actions per side, and a finite number of rounds. 

End result: A working simulation showing how different defender strategies perform against attacks, with quantitative results.

For more information, please contact r.soltani@utwente.nl.

Relevant references to similar projects: 

  1. https://purl.utwente.nl/essays/108225
  2. https://purl.utwente.nl/essays/101705
Hackers Love Bad Luck: Can They Exploit System Failures? (Reza Soltani, Milan Lopuhaä-Zwakenberg)

Supervisors: Reza Soltani, Milan Lopuhaä-Zwakenberg

What happens when equipment breaks down and an attacker deliberately takes advantage of the situation?

What the student does: Model a small smart-grid or industrial-control scenario with random equipment failures and deliberate attacks. Compare an attacker who chooses a fixed attack plan against one who adapts after observing failures.

Research question: How much does the ability to observe accidental component failures improve an attacker's probability of successfully disrupting a system?

Manageable scope: One scenario, approximately 6–10 basic events, a small number of available attacks, and one or two observable failures. Reuse Petrov's AFT-to-MDP approach.

End result: A cyberattack simulation and analysis showing when seemingly harmless component failures become valuable opportunities for attackers.

For more information, please contact r.soltani@utwente.nl.

A relevant reference to a similar project: https://purl.utwente.nl/essays/108198

Contact

Background

Would it not be great to live in a world where computers never crash, trains always ride and banks are never hacked?

This is the ultimate goal of risk management. In FMT, we work on the risk analysis phase, where one identifies, evaluates and prioritizes risks, to come up with (cost-)effective countermeasures. By using mathematical models, we can not only reason about risk, but quantify risk as well. As risk models from industry become very large very quickly, creating algorithms that analyze risk models efficiently is an important area of research.

Prominent mathematical models include graph models such as fault trees (for safety), attack trees (for security), binary decision diagrams, and Bayesian networks. Application areas we have considered so far include cybersecurity, medical devices, and robotics, but we are interested in many applications: if you have one of your own, please come to us.

Projects for Formal methods for risk analysis roughly fall within some or more of the following categories:

  • Modeling techniques: What types of risk can we model, and what do we want our models to express? For example, how do we model the interplay between safety and security?
  • Model analyis: Can we find new ways to efficiently calculate risk parameters from models, such as the likelihood and impact of adverse events?
  • Big data: How do we get from a large dataset to a risk model that is easy to analyze, yet retains as much relevant information as possible?
  • Industrial case studies: Do one or more of the above for real-world data, in collaboration with companies, government bodies or risk consultancy firms.

If you have an idea related to any of these, please contact us directly. Alternatively, you can work on one of the concrete proposals below.

Some of the research in Formal methods for risk analysis is closely related to that of quantitative analysis, as it relies on stochastic model-checking techniques. Conversely, many examples and case studies for quantitative analysis come from risk management.