Titre : From diagnosis to causal analysis

Sujet proposé dans : M2 MOSIG, Projet --- M2R Informatique, Projet --- Magistere, M1 --- Magistere, M2

Responsable(s) :

Mots-clés : fault diagnosis, causality, formal methods
Durée du projet : ~5 mois
Nombre maximal d'étudiants : 1
Places disponibles : 1
Interrogation effectuée le : 19 juin 2018, ŕ 12 heures 06


Scientific context

Embedded systems, and the interactions among them, become more and
more complex. Power grid blackouts, airplane crashes, failures of
medical devices, cruise control devices out of control are just a few
examples of incidents where determining the root cause(s) and
elucidating the exact scenario that led to the failure is today a
complex and tedious task that requires significant expertise.

Several research communities are investigating approaches to
automatize such analyses.

On the one hand, fault diagnosis is a very active field of research,
whose objectives are to determine the possible occurrence of hidden
faults from the observation of executions (detection), and
determining which (prefix of) executions are compatible with
observations recorded in a given log (explanation) [7]. This is generally achieved with fault models although [5] proposes to approach this problem without fault models. The conditions under which a given hidden fault can be detected without ambiguity have also been analyzed (diagnosability) [6][4]. In addition, some works propose to identify the so-called « critical observations » that correspond to the minimal signature of a fault [1].

On the other hand, several approaches have been proposed to determine
more precisely the necessary/sufficient [2] or actual [3] causes of a
system failure and to construct for a failing execution an
explanation, e.g. in the form of a minimal sub-trace that exhibits the

Objectives of the project are:

- Get an overview of the state of the art in fault diagnosis and
  causal analysis.

- Identify the differences (of objectives, formalisms, ...).

- Identify the problems that could be tackled by jointly leveraging
  both approaches.

- If time permits, start formalizing and studying one of these

Advisors and host teams:

The internship will be co-advised by Louise TRAVE-MASSUYES (DISCO
team, LAAS-CNRS, Toulouse) and Gregor GOESSLER (SPADES team, INRIA
Grenoble). The successful candidate will choose his/her host team.


[1] C. Christopher, Y. Pencolé and A. Grastien, Inference of fault signatures of discrete-event systems from event logs, Proc. Int. Workshop on Principles of Diagnosis (DX), Brescia, Italy, 2017.

[2] G. Gössler and J.-B. Stefani, Fault Ascription in Concurrent
Systems.  Proc. Trustworthy Global Computing 2015, LNCS 9533,
Springer, 2016. https://hal.inria.fr/hal-01246485

[3] J. Y. Halpern, A Modification of the Halpern-Pearl Definition of
Causality. Proc. International Joint Conference on Artificial
Intelligence 2015. http://ijcai.org/Abstract/15/427

[4] S. Jiang, Z. Huang, V. Chandra, and R. Kumar (2001). A polynomial algorithm for testing diagnosability of discrete-event systems. IEEE Transactions on Automatic Control, 46(8), 1318-1321.

[5] Y. Pencole, G. Steinbauer, C. Mühlbacher and L. Travé-Massuyès, Diagnosing Discrete Event Systems Using Nominal Models Only, Proc. Int. Workshop on Principles of Diagnosis (DX), Brescia, Italy, 2017.

[6] M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, and Teneketzis, D. (1995). Diagnosability of discrete-event systems. IEEE Transactions on automatic control, 40(9), 1555-1575.

[7] J. Zaytoon and S. Lafortune, Overview of fault diagnosis methods for Discrete Event Systems. Annual Reviews in Control 37(2), 2013.