Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Dynamic Games and Applications 4/2019

08-09-2018

Supervisory Control of Discrete-Event Systems Under Attacks

Authors: Masashi Wakaiki, Paulo Tabuada, João P. Hespanha

Published in: Dynamic Games and Applications | Issue 4/2019

Login to get access
share
SHARE

Abstract

We consider a multi-adversary version of the supervisory control problem for discrete-event systems (DES), in which an adversary corrupts the observations available to the supervisor. The supervisor’s goal is to enforce a specific language in spite of the opponent’s actions and without knowing which adversary it is playing against. This problem is motivated by applications to computer security in which a cyber defense system must make decisions based on reports from sensors that may have been tampered with by an attacker. We start by showing that the problem has a solution if and only if the desired language is controllable (in the DES classical sense) and observable in a (novel) sense that takes the adversaries into account. For the particular case of attacks that insert symbols into or remove symbols from the sequence of sensor outputs, we show that testing the existence of a supervisor and building the supervisor can be done using tools developed for the classical DES supervisory control problem, by considering a family of automata with modified output maps, but without expanding the size of the state space and without incurring on exponential complexity on the number of attacks considered.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Literature
1.
go back to reference Amin S, Litrico X, Sastry S, Bayen AM (2013) Cyber security of water SCADA systems-part I: analysis and experimentation of stealthy deception attacks. IEEE Trans Control Syst Technol 21:1963–1970 CrossRef Amin S, Litrico X, Sastry S, Bayen AM (2013) Cyber security of water SCADA systems-part I: analysis and experimentation of stealthy deception attacks. IEEE Trans Control Syst Technol 21:1963–1970 CrossRef
2.
go back to reference Cassandras CG, Lafortune S (2008) Introduction to discrete event systems, 2nd edn. Springer, Berlin CrossRef Cassandras CG, Lafortune S (2008) Introduction to discrete event systems, 2nd edn. Springer, Berlin CrossRef
3.
go back to reference Chong MS, Wakaiki M, Hespanha JP (2015) Observability of linear systems under adversarial attacks. In: Proceedings of the 2015 American control conference Chong MS, Wakaiki M, Hespanha JP (2015) Observability of linear systems under adversarial attacks. In: Proceedings of the 2015 American control conference
5.
go back to reference Dubreil J, Darondeau P, Marchand H (2010) Supervisory control for opacity. IEEE Trans Autom Control 55:1089–1100 MathSciNetCrossRef Dubreil J, Darondeau P, Marchand H (2010) Supervisory control for opacity. IEEE Trans Autom Control 55:1089–1100 MathSciNetCrossRef
6.
go back to reference Fawzi H, Tabuada P, Diggavi S (2014) Secure estimation and control for cyber-physical systems under adversarial attacks. IEEE Trans Autom Control 59:1454–1467 MathSciNetCrossRef Fawzi H, Tabuada P, Diggavi S (2014) Secure estimation and control for cyber-physical systems under adversarial attacks. IEEE Trans Autom Control 59:1454–1467 MathSciNetCrossRef
7.
go back to reference Feng L, Wonham W (2006) TCT: a computation tool for supervisory control synthesis. In: 8th international workshop on discrete event systems, pp 388–389 Feng L, Wonham W (2006) TCT: a computation tool for supervisory control synthesis. In: 8th international workshop on discrete event systems, pp 388–389
8.
go back to reference Hubballi N, Biswas S, Roopa S, Ratti R, Nandi S (2011) LAN attack detection using discrete event systems. ISA Trans 50:119–130 CrossRef Hubballi N, Biswas S, Roopa S, Ratti R, Nandi S (2011) LAN attack detection using discrete event systems. ISA Trans 50:119–130 CrossRef
9.
go back to reference Ji Y, Lee S, Downing E, Wang W, Fazzini M, Kim T, Orso A, Lee W (2017) Rain: refinable attack investigation with on-demand inter-process information flow tracking. In: Proceedings of the 2017 ACM SIGSAC conference on computer and communications security. ACM, pp 377–390 Ji Y, Lee S, Downing E, Wang W, Fazzini M, Kim T, Orso A, Lee W (2017) Rain: refinable attack investigation with on-demand inter-process information flow tracking. In: Proceedings of the 2017 ACM SIGSAC conference on computer and communications security. ACM, pp 377–390
11.
go back to reference Lin F (1993) Robust and adaptive supervisory control of discrete event systems. IEEE Trans Automt Control 38:1848–1852 MathSciNetCrossRef Lin F (1993) Robust and adaptive supervisory control of discrete event systems. IEEE Trans Automt Control 38:1848–1852 MathSciNetCrossRef
12.
go back to reference Paoli A, Sartini M, Lafortune S (2011) Active fault tolerant control of discrete event systems using online diagnostics. Automatica 47:639–649 MathSciNetCrossRef Paoli A, Sartini M, Lafortune S (2011) Active fault tolerant control of discrete event systems using online diagnostics. Automatica 47:639–649 MathSciNetCrossRef
13.
go back to reference Ramadge PJ, Wonham WM (1989) The control of discrete event systems. Proc IEEE 77:81–98 CrossRef Ramadge PJ, Wonham WM (1989) The control of discrete event systems. Proc IEEE 77:81–98 CrossRef
14.
go back to reference Saboori A, Hadjicostis CN (2012) Opacity-enforcing supervisory strategies via state estimator constructions. IEEE Trans Autom Control 57:1155–1165 MathSciNetCrossRef Saboori A, Hadjicostis CN (2012) Opacity-enforcing supervisory strategies via state estimator constructions. IEEE Trans Autom Control 57:1155–1165 MathSciNetCrossRef
15.
go back to reference Saboori A, Zad SH (2006) Robust nonblocking supervisory control of discrete-event systems under partial observation. Syst Control Lett 55:839–848 MathSciNetCrossRef Saboori A, Zad SH (2006) Robust nonblocking supervisory control of discrete-event systems under partial observation. Syst Control Lett 55:839–848 MathSciNetCrossRef
16.
go back to reference Sánchez AM, Montoya FJ (2006) Safe supervisory control under observability failure. Discrete Event Dyn Syst Theory Appl 16:493–525 MathSciNetCrossRef Sánchez AM, Montoya FJ (2006) Safe supervisory control under observability failure. Discrete Event Dyn Syst Theory Appl 16:493–525 MathSciNetCrossRef
17.
go back to reference Sheyner O, Wing J (2004) Tools for generating and analyzing attack graphs. In: de Boer FS, Bonsangue MM, Graf S, de Roever WP (eds) Formal methods for components and objects: second international symposium, FMCO 2003, Leiden, The Netherlands, November 4–7, 2003. Revised Lectures, no. 3188 in Lecture Notes on Computer Science. Springer, Berlin, pp. 344–371 Sheyner O, Wing J (2004) Tools for generating and analyzing attack graphs. In: de Boer FS, Bonsangue MM, Graf S, de Roever WP (eds) Formal methods for components and objects: second international symposium, FMCO 2003, Leiden, The Netherlands, November 4–7, 2003. Revised Lectures, no. 3188 in Lecture Notes on Computer Science. Springer, Berlin, pp. 344–371
18.
go back to reference Shoukry Y, Tabuada P (2016) Event-triggered state observers for sparse noise/attacks. IEEE Trans Autom Control 61(8):2079–2091 MathSciNetCrossRef Shoukry Y, Tabuada P (2016) Event-triggered state observers for sparse noise/attacks. IEEE Trans Autom Control 61(8):2079–2091 MathSciNetCrossRef
19.
go back to reference Shu S, Lin F (2014) Fault-tolerant control for safety of discrete-event systems. IEEE Trans Autom Sci Eng 11:78–89 CrossRef Shu S, Lin F (2014) Fault-tolerant control for safety of discrete-event systems. IEEE Trans Autom Sci Eng 11:78–89 CrossRef
20.
go back to reference Takai S (2000) Robust supervisory control of a class of timed discrete event systems under partial observation. Syst Control Lett 39:267–273 MathSciNetCrossRef Takai S (2000) Robust supervisory control of a class of timed discrete event systems under partial observation. Syst Control Lett 39:267–273 MathSciNetCrossRef
21.
go back to reference Takai S, Oka Y (2008) A formula for the supremal controllable and opaque sublanguage arising in supervisory control. SICE J Control Meas Syst Integr 1:307–311 CrossRef Takai S, Oka Y (2008) A formula for the supremal controllable and opaque sublanguage arising in supervisory control. SICE J Control Meas Syst Integr 1:307–311 CrossRef
22.
go back to reference Teixeira A, Shames I, Sandberg H, Johansson KH (2015) A secure control framework for resource-limited adversaries. Automatica 51:135–148 MathSciNetCrossRef Teixeira A, Shames I, Sandberg H, Johansson KH (2015) A secure control framework for resource-limited adversaries. Automatica 51:135–148 MathSciNetCrossRef
23.
go back to reference Thorsley D, Teneketzis D (2006) Intrusion detection in controlled discrete event systems. In: Proceedings of the 45th conference on decision and control Thorsley D, Teneketzis D (2006) Intrusion detection in controlled discrete event systems. In: Proceedings of the 45th conference on decision and control
24.
25.
go back to reference Ushio T, Takai S (2009) Supervisory control of discrete event systems modeled by Mealy automata with nondeterministic output functions. In: Proceedings of the 2009 American control conference Ushio T, Takai S (2009) Supervisory control of discrete event systems modeled by Mealy automata with nondeterministic output functions. In: Proceedings of the 2009 American control conference
26.
go back to reference Ushio T, Takai S (2016) Nonblocking supervisory control of discrete event systems modeled by Mealy automata with nondeterministic output functions. IEEE Trans Autom Control 61(3):799–804 MathSciNetCrossRef Ushio T, Takai S (2016) Nonblocking supervisory control of discrete event systems modeled by Mealy automata with nondeterministic output functions. IEEE Trans Autom Control 61(3):799–804 MathSciNetCrossRef
27.
go back to reference Whittaker SJ, Zulkernine M, Rudie K (2008) Toward incorporating discrete-event systems in secure software development. In: Proceedings of ARES’08 Whittaker SJ, Zulkernine M, Rudie K (2008) Toward incorporating discrete-event systems in secure software development. In: Proceedings of ARES’08
29.
go back to reference Wu YC, Lafortune S (2014) Synthesis of insertion functions for enforcement of opacity security properties. Automatica 50:1336–1348 MathSciNetCrossRef Wu YC, Lafortune S (2014) Synthesis of insertion functions for enforcement of opacity security properties. Automatica 50:1336–1348 MathSciNetCrossRef
30.
go back to reference Xu S, Kumar R (2009) Discrete event control under nondeterministic partial observation. In: Proceedings of IEEE CASE’09 Xu S, Kumar R (2009) Discrete event control under nondeterministic partial observation. In: Proceedings of IEEE CASE’09
31.
go back to reference Yin X (2017) Supervisor synthesis for Mealy automata with output functions: a model transformation approach. IEEE Trans Autom Control 62(5):2576–2581 MathSciNetCrossRef Yin X (2017) Supervisor synthesis for Mealy automata with output functions: a model transformation approach. IEEE Trans Autom Control 62(5):2576–2581 MathSciNetCrossRef
32.
go back to reference Yoo TS, Lafortune S (2002) A general architecture for decentralized supervisory control of discrete-event systems. Discrete Event Dyn Syst Theory Appl 12:335–377 MathSciNetCrossRef Yoo TS, Lafortune S (2002) A general architecture for decentralized supervisory control of discrete-event systems. Discrete Event Dyn Syst Theory Appl 12:335–377 MathSciNetCrossRef
Metadata
Title
Supervisory Control of Discrete-Event Systems Under Attacks
Authors
Masashi Wakaiki
Paulo Tabuada
João P. Hespanha
Publication date
08-09-2018
Publisher
Springer US
Published in
Dynamic Games and Applications / Issue 4/2019
Print ISSN: 2153-0785
Electronic ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-018-0285-3

Other articles of this Issue 4/2019

Dynamic Games and Applications 4/2019 Go to the issue

Premium Partner