author: Dennis Aanstoot
title: Better Fault Tree Analysis using Sylvan
keywords: fault tree, attack tree, binary decision diagram, fun
topics: Other
committee: Mariƫlle Stoelinga ,
Enno Ruijters
started: August 2015
end: January 2016

Description

The analysis of fault trees is a staple in formal methods. In companies like NASA, ESA, SpaceX, Airbus, NRG, etc., fault trees and related concepts like attack trees are used to design and monitor safety-critical systems [1].  Examples of fault tree analysis is computing the system reliability, e.g. the probability that a power plant or a robot or any automated system is operational up to time t, or finding the most vulnerable parts in the system design [2].

One technique is symbolic fault tree analysis using binary decision diagrams [3]. In recent work, binary decision diagrams have been parallelised [4]. The purpose of this bachelor project is to reimplement symbolic fault tree analysis using this parallel implementation and study opportunities for further parallelisation.

Tasks

  • Understand the basics of fault tree analysis and binary decision diagrams
  • Understand how binary decision diagrams can be used in fault tree analysis
  • Implement fault tree analysis using Sylvan (a parallel BDD implementation)
  • Perform experiments on benchmark models

Requirements

  • Programming experience
  • A functioning brain with the desire to do some good science!

Literatures

  1. W.E. Vesely, F.F. Goldberg, N.H. Roberts, D.F. Haasl, Fault Tree Handbook, Office of Nuclear Regulatory Research, US Nuclear Regulatory Commision, 1981 (http://www.nrc.gov/reading-rm/doc-collections/nuregs/staff/sr0492/)
  2. E. Ruijters, M.I.A. Stoelinga, Fault Tree Analysis: A survey of the state-of-the-art in modeling, analysis, and tools, Computer Science Review 15-16, February-May 2015, pp. 29-62 (http://dx.doi.org/10.1016/j.cosrev.2015.03.001)
  3. R.M. Sinnamon, J.D. Andrews, Fault tree analysis and binary decision diagrams, in Proceedings of the Reliability and Maintainability Symposium (RAMS) 1996, pp. 215-222. (http://dx.doi.org/10.1109/RAMS.1996.500665)
  4. T. van Dijk, J.C. van de Pol, Sylvan: Multi-Core Decision Diagrams, in Tools and Algorithms for the Construction and Analysis of Systems 2015, pp. 677-691. (http://dx.doi.org/10.1007/978-3-662-46681-0_60)

 

Additional Resources

  1. The paper