Sequential detection of transient changes in stochastic-dynamical systems

Do, Van Long; Fillatre, Lionel; Nikiforov, Igor

Journal de la société française de statistique, Tome 156 (2015) no. 4, pp. 60-97.

Cet article s’intéresse au problème de détection de changements transitoires dans des systèmes stochastiques et dynamiques. Le modèle d’observation statistique étudié dépend de l’état inconnu du système considéré comme un paramètre de nuisance. Ce paramètre de nuisance est éliminé en utilisant la technique, bien connue dans la communauté du diagnostic automatique, de la projection des observations dans l’espace de parité. L’algorithme de la Somme Cumulée à Fenêtre Limitée et Seuils Variables (VTWL CUSUM) est adapté au modèle d’observation utilisé. Le critère de détection de changement transitoire étudié vise à minimiser la pire probabilité de détection manquée sous la contrainte que la pire probabilité de la fausse alarme soit bornée pendant une période de longueur donnée. Les seuils de l’algorithme sont optimisés pour obtenir la meilleure performance. Il est montré que l’algorithme VTWL CUSUM optimal est équivalent à l’algorithme de la Moyenne Glissante Finie (FMA). Une méthode numérique est proposée pour estimer les probabilités de fausse alarme et de détection manquée. Enfin, les résultats théoriques sont appliqués à la détection d’attaques cyber-physiques, dans un système de distribution d’eau potable, qui ont pour but de voler l’eau d’un réservoir.

This paper deals with the problem of detecting transient changes in stochastic-dynamical systems. A statistical observation model which depends on unknown system states (often regarded as the nuisance parameter) is developed. The negative impact of nuisance parameter is then eliminated from the observation model by utilizing the invariant statistics. The Variable Threshold Window Limited CUmulative SUM (VTWL CUSUM) test, previously developed for independent observations, is adapted to the novel observation model. Taking into account the transient change detection criterion, minimizing the worst-case probability of missed detection subject to an acceptable level of the worst-case probability of false alarm within a given time period, the thresholds of the VTWL CUSUM test are optimized. It is shown that the optimized VTWL CUSUM algorithm is equivalent to the Finite Moving Average (FMA) detection rule. A numerical method for estimating the probability of false alarm and missed detection is proposed. The theoretical results are applied to the problem of cyber/physical attack (stealing water from a reservoir) detection on a simple Supervisory Control and Data Acquisition (SCADA) water distribution system.

Keywords: transient change detection, stochastic-dynamical systems, criterion of optimality, CUSUM-based algorithm, probability of false alarm, probability of missed detection, cyber/physical attacks
Mot clés : détection de changements transitoires, systèmes stochastiques et dynamiques, critère d’optimalité, algorithme CUSUM, probabilité de fausse alarme, probabilité de détection manquée, attaques cyber-physiques

[Amin et al., 2012a] Amin, S., Litrico, X., Sastry, S., and Bayen, A. (2012a). Cyber security of water SCADA systems:(i) analysis and experimentation of stealthy deception attacks. IEEE Transactions on Control Systems Technology, 20.

[Amin et al., 2012b] Amin, S., Litrico, X., Sastry, S., and Bayen, A. (2012b). Cyber security of water SCADA systems:(ii) attack detection using an enhanced hydrodynamic model. IEEE Transactions on Control Systems Technology, 20.

[Bakhache and Nikiforov, 2000] Bakhache, B. and Nikiforov, I. (2000). Reliable detection of faults in measurement systems. International Journal of adaptive control and signal processing, 14(7):683–700. | Zbl

[Basseville and Nikiforov, 1993] Basseville, M. and Nikiforov, I. V. (1993). Detection of Abrupt Changes - Theory and Application. Information and System Sciences Series. Prentice-Hall, Inc., Englewood Cliffs, NJ, USA. Online. | MR

[Brunner et al., 2010] Brunner, M., Hofinger, H., Krauss, C., Roblee, C., Schoo, P., and Todt, S. (2010). Infiltrating critical infrastructures with next-generation attacks. Fraunhofer Institute for Secure Information Technology (SIT), Munich.

[Cárdenas et al., 2011] Cárdenas, A. A., Amin, S., Lin, Z.-S., Huang, Y.-L., Huang, C.-Y., and Sastry, S. (2011). Attacks against process control systems: risk assessment, detection, and response. In Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, pages 355–366. ACM.

[Chen and Willett, 2000] Chen, B. and Willett, P. (2000). Detection of hidden Markov model transient signals. IEEE Transactions on Aerospace and Electronic Systems, 36(4):1253–1268.

[Fillatre and Nikiforov, 2007] Fillatre, L. and Nikiforov, I. (2007). Non-bayesian detection and detectability of anomalies from a few noisy tomographic projections. Signal Processing, IEEE Transactions on, 55(2):401–413. | MR

[Fouladirad and Nikiforov, 2005] Fouladirad, M. and Nikiforov, I. (2005). Optimal statistical fault detection with nuisance parameters. Automatica, 41(7):1157–1171. | Zbl

[Genz and Bretz, 2002] Genz, A. and Bretz, F. (2002). Comparison of methods for the computation of multivariate t probabilities. Journal of Computational and Graphical Statistics, 11(4):950–971.

[Guépié, 2013] Guépié, B. K. (2013). Détection séquentielle de signaux transitoires : application à la surveillance d’un réseau d’eau potable. PhD thesis, Université de Technologie de Troyes.

[Guépié et al., 2012a] Guépié, B. K., Fillatre, L., and Nikiforov, I. (2012a). Detecting an abrupt change of finite duration. In Signals, Systems and Computers (ASILOMAR), 2012 Conference Record of the Forty Sixth Asilomar Conference on, pages 1930–1934. IEEE.

[Guépié et al., 2012b] Guépié, B. K., Fillatre, L., and Nikiforov, I. (2012b). Sequential detection of transient changes. Sequential Analysis, 31(4):528–547. | Zbl

[Han et al., 1999] Han, C., Willett, P. K., and Abraham, D. A. (1999). Some methods to evaluate the performance of Page’s test as used to detect transient signals. Signal Processing, IEEE Transactions on, 47(8):2112–2127.

[Huang et al., 2009] Huang, Y., Cárdenas, A., Amin, S., Lin, Z., Tsai, H., and Sastry, S. (2009). Understanding the physical and economic consequences of attacks on control systems. International Journal of Critical Infrastructure Protection, 2(3):73–83.

[Koch, 1999] Koch, K.-R. (1999). Parameter Estimation and Hypothesis Testing in Linear Models (2nd ed.). Springer, Berlin, Heidelberg, DE. | Zbl

[Lai, 1995] Lai, T. L. (1995). Sequential changepoint detection in quality control and dynamical systems. Journal of the Royal Statistical Society. Series B (Methodological), pages 613–658. | Zbl

[Lai, 1998] Lai, T. L. (1998). Information bounds and quick detection of parameter changes in stochastic systems. Information Theory, IEEE Transactions on, 44(7):2917–2929. | Zbl

[Lai, 2001] Lai, T. L. (2001). Sequential analysis: some classical problems and new challenges. Statistica Sinica, 11(2):303–350. | Zbl

[Lorden, 1971] Lorden, G. (1971). Procedures for reacting to a change in distribution. The Annals of Mathematical Statistics, pages 1897–1908. | Zbl

[Moustakides, 1986] Moustakides, G. (1986). Optimal stopping times for detecting changes in distributions. The Annals of Statistics, 14(4):1379–1387. | Zbl

[Moustakides, 2014] Moustakides, G. V. (2014). Multiple Optimality Properties of the Shewhart Test. Sequential Analysis, 33(3):318–344.

[Page, 1954] Page, E. (1954). Continuous inspection schemes. Biometrika, pages 100–115. | Zbl

[Pasqualetti, 2012] Pasqualetti, F. (2012). Secure Control Systems: A Control-Theoretic Approach to Cyber-Physical Security. PhD thesis, University of California.

[Pasqualetti et al., 2013] Pasqualetti, F., Dorfler, F., and Bullo, F. (2013). Attack detection and identification in cyber-physical systems. Automatic Control, IEEE Transactions on, 58(11):2715–2729.

[Pollak, 1985] Pollak, M. (1985). Optimal detection of a change in distribution. The Annals of Statistics, pages 206–227. | Zbl

[Polunchenko and Tartakovsky, 2012] Polunchenko, A. and Tartakovsky, A. (2012). State-of-the-art in sequential change-point detection. Methodology and computing in applied probability, 14(3):649–684.

[Poor and Hadjiliadis, 2009] Poor, H. V. and Hadjiliadis, O. (2009). Quickest Detection. Cambridge, UK.

[Premkumar et al., 2010] Premkumar, K., Kumar, A., and Veeravalli, V. (2010). Bayesian quickest transient change detection. In Proc. Fifth International Workshop on Applied Probability (IWAP), pages 1–3.

[Repin, 1991] Repin, V. (1991). Detection of a signal with unknown moments of appearance and disappearance. Problemy Peredachi Informatsii, 27(2):61–72. | Zbl

[Ritov, 1990] Ritov, Y. (1990). Decision theoretic optimality of the cusum procedure. The Annals of Statistics, pages 1464–1469. | Zbl

[Roberts, 1966] Roberts, S. (1966). A comparison of some control chart procedures. Technometrics, 8(3):411–430.

[Shiryaev, 1963] Shiryaev, A. (1963). On optimum methods in quickest detection problems. Theory of Probability & Its Applications, 8(1):22–46. | Zbl

[Smith, 2011] Smith, R. S. (2011). A decoupled feedback structure for covertly appropriating networked control systems. Proc. IFAC World Congress, pages 90–95.

[Streit and Willett, 1999] Streit, R. L. and Willett, P. K. (1999). Detection of random transient signals via hyperparameter estimation. Signal Processing, IEEE Transactions on, 47(7):1823–1834.

[Tartakovsky, 2005] Tartakovsky, A. (2005). Asymptotic performance of a multichart cusum test under false alarm probability constraint. In Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC’05. 44th IEEE Conference on, pages 320–325. IEEE.

[Tartakovsky and Moustakides, 2010] Tartakovsky, A. and Moustakides, G. (2010). State-of-the-art in bayesian changepoint detection. Sequential Analysis, 29(2):125–145. | Zbl

[Tartakovsky et al., 2014] Tartakovsky, A., Nikiforov, I., and Basseville, M. (2014). Sequential Analysis : Hypothesis Testing and Changepoint Detection. CRC Press, Taylor & Francis Group.

[Willsky and Jones, 1976] Willsky, A. and Jones, H. (1976). A generalized likelihood ratio approach to the detection and estimation of jumps in linear systems. Automatic Control, IEEE Transactions on, 21(1):108–112. | Zbl

[Zetter, 2011] Zetter, K. (2011). H(ackers)2O : attack on city water station destroys pump. Wired.com. Online.