American Institute of Mathematical Sciences

Advanced
September  2013, 8(3): 783-802. doi: 10.3934/nhm.2013.8.783

Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming

Edward S. Canepa 1, , Alexandre M. Bayen 2, and  Christian G. Claudel 1,

1. 

King Abdullah University of Science and Technology, Electrical Engineering Department, Thuwal, Makkah 23955, KSA, Saudi Arabia, Saudi Arabia
2. 

University of California at Berkely, Electrical Engineering and Computer Sciences, Berkeley CA 94720-170

Received  September 2012 Revised  March 2013 Published  October 2013

Traffic sensing systems rely more and more on user generated (insecure) data, which can pose a security risk whenever the data is used for traffic flow control. In this article, we propose a new formulation for detecting malicious data injection in traffic flow monitoring systems by using the underlying traffic flow model. The state of traffic is modeled by the Lighthill-Whitham-Richards traffic flow model, which is a first order scalar conservation law with concave flux function. Given a set of traffic flow data generated by multiple sensors of different types, we show that the constraints resulting from this partial differential equation are mixed integer linear inequalities for a specific decision variable. We use this fact to pose the problem of detecting spoofing cyber attacks in probe-based traffic flow information systems as mixed integer linear feasibility problem. The resulting framework can be used to detect spoofing attacks in real time, or to evaluate the worst-case effects of an attack offline. A numerical implementation is performed on a cyber attack scenario involving experimental data from the Mobile Century experiment and the Mobile Millennium system currently operational in Northern California.
Keywords: hyperbolic partial differential equations, cybersecurity., Mixed integer linear programming.
Mathematics Subject Classification: 68U35, 90C11, 90C9.
Citation: Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783
References:
[1]

S. Amin, A. Cardenas and S. Sastry, Safe and secure networked control systems under denial-of-service attacks,, in, (2009), 31.  doi: 10.1007/978-3-642-00602-9_3.  Google Scholar

[2]

S. Amin, X. Litrico, S. Sastry and A. Bayen, Stealthy deception attacks on water scada systems,, In, (2010), 161.  doi: 10.1145/1755952.1755976.  Google Scholar

[3]

J.-P. Aubin, "Viability Theory,", Systems and Control: Foundations and Applications, (1991).   Google Scholar

[4]

J.-P. Aubin, A. M. Bayen and P. Saint-Pierre, Dirichlet problems for some Hamilton-Jacobi equations with inequality constraints,, SIAM Journal on Control and Optimization, 47 (2008), 2348.  doi: 10.1137/060659569.  Google Scholar

[5]

M. Bardi and I. Capuzzo-Dolcetta, "Optimal Control and Viscosity Solutions of {Hamilton-Jacobi-Bellman} Equations,", Birkhäuser, (1997).  doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[6]

E. N. Barron and R. Jensen, Semicontinuous viscosity solutions for Hamilton-Jacobi equations with convex Hamiltonians,, Communications in Partial Differential Equations, 15 (1990), 1713.  doi: 10.1080/03605309908820745.  Google Scholar

[7]

E. S. Canepa and C. G. Claudel, Exact solutions to traffic density estimation problems involving the Lighthill-Whitman-Richards traffic flow model using Mixed Integer Linear Programing,, In, (2012), 832.   Google Scholar

[8]

P. D. Christofides, "Nonlinear and Robust Control of Partial Differential Equation Systems: Methods and Applications to Transport-Reaction Processes,", Birkhäuser, (2001).  doi: 10.1007/978-1-4612-0185-4.  Google Scholar

[9]

C. G. Claudel and A. M. Bayen, Lax-Hopf based incorporation of internal boundary conditions into Hamilton-Jacobi equation. Part I: Theory,, IEEE Transactions on Automatic Control, 55 (2010), 1142.  doi: 10.1109/TAC.2010.2041976.  Google Scholar

[10]

C. G. Claudel and A. M. Bayen, Lax-Hopf based incorporation of internal boundary conditions into Hamilton-Jacobi equation. Part {II: Computational methods},, IEEE Transactions on Automatic Control, 55 (2010), 1158.  doi: 10.1109/TAC.2010.2045439.  Google Scholar

[11]

C. G. Claudel and A. M Bayen, Convex formulations of data assimilation problems for a class of Hamilton-Jacobi equations,, SIAM Journal on Control and Optimization, 49 (2011), 383.  doi: 10.1137/090778754.  Google Scholar

[12]

M. G. Crandall and P.-L. Lions, Viscosity solutions of {Hamilton-Jacobi equations},, Transactions of the American Mathematical Society, 277 (1983), 1.  doi: 10.1090/S0002-9947-1983-0690039-8.  Google Scholar

[13]

C. Daganzo, The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory,, Transportation Research, 28B (1994), 269.  doi: 10.1016/0191-2615(94)90002-7.  Google Scholar

[14]

C. F. Daganzo, A variational formulation of kinematic waves: basic theory and complex boundary conditions,, Transportation Research B, 39B (2005), 187.  doi: 10.1016/j.trb.2004.04.003.  Google Scholar

[15]

C. F. Daganzo, On the variational theory of traffic flow: well-posedness, duality and applications,, Networks and Heterogeneous Media, 1 (2006), 601.  doi: 10.3934/nhm.2006.1.601.  Google Scholar

[16]

H. Frankowska, Lower semicontinuous solutions of Hamilton-Jacobi-Bellman equations,, SIAM Journal of Control and Optimization, 31 (1993), 257.  doi: 10.1137/0331016.  Google Scholar

[17]

J. C. Herrera, D. B. Work, R. Herring, X. J. Ban, Q. Jacobson and A. M. Bayen, Evaluation of traffic data obtained via GPS-enabled mobile phones: The Mobile Century field experiment,, Transportation Research Part C: Emerging Technologies, 18 (2010), 568.  doi: 10.1016/j.trc.2009.10.006.  Google Scholar

[18]

B. Hoh, M. Gruteser, R. Herring, J. Ban, D. Work, J. C. Herrera, A. M. Bayen, M. Annavaram and Q. Jacobson, Virtual trip lines for distributed privacy-preserving traffic monitoring,, in, (2008), 15.  doi: 10.1145/1378600.1378604.  Google Scholar

[19]

M. Krstic and A. Smyshlyaev, Backstepping boundary control for first-order hyperbolic pdes and application to systems with actuator and sensor delays,, Systems & Control Letters, 57 (2008), 750.  doi: 10.1016/j.sysconle.2008.02.005.  Google Scholar

[20]

P. E. Mazare, A. Dehwah, C. G. Claudel and A. M. Bayen, Analytical and grid-free solutions to the lighthill-whitham-richards traffic flow model,, Transportation Research Part B: Methodological, 45 (2011), 1727.  doi: 10.1016/j.trb.2011.07.004.  Google Scholar

[21]

K. Moskowitz, Discussion of "freeway level of service as influenced by volume and capacity characteristics' by D.R. Drew and C. J. Keese,, Highway Research Record, 99 (1965), 43.   Google Scholar

[22]

G. F. Newell, A simplified theory of kinematic waves in highway traffic, Part (I), (II) and (III)., Transporation Research B, 27B (1993), 281.   Google Scholar

[23]

R. C. Smith and M. A. Demetriou, "Research Directions in Distributed Parameter Systems,", SIAM, (2000).  doi: 10.1137/1.9780898717525.  Google Scholar

[24]

I. S. Strub and A. M. Bayen, Weak formulation of boundary conditions for scalar conservation laws,, International Journal of Robust and Nonlinear Control, 16 (2006), 733.  doi: 10.1002/rnc.1099.  Google Scholar

[25]

D. Work, S. Blandin, O. Tossavainen, B. Piccoli and A. Bayen, A distributed highway velocity model for traffic state reconstruction,, Applied Research Mathematics eXpress (ARMX), 1 (2010), 1.   Google Scholar

[26]

, , ().   Google Scholar

[27]

, , ().   Google Scholar

show all references

References:
[1]

S. Amin, A. Cardenas and S. Sastry, Safe and secure networked control systems under denial-of-service attacks,, in, (2009), 31.  doi: 10.1007/978-3-642-00602-9_3.  Google Scholar

[2]

S. Amin, X. Litrico, S. Sastry and A. Bayen, Stealthy deception attacks on water scada systems,, In, (2010), 161.  doi: 10.1145/1755952.1755976.  Google Scholar

[3]

J.-P. Aubin, "Viability Theory,", Systems and Control: Foundations and Applications, (1991).   Google Scholar

[4]

J.-P. Aubin, A. M. Bayen and P. Saint-Pierre, Dirichlet problems for some Hamilton-Jacobi equations with inequality constraints,, SIAM Journal on Control and Optimization, 47 (2008), 2348.  doi: 10.1137/060659569.  Google Scholar

[5]

M. Bardi and I. Capuzzo-Dolcetta, "Optimal Control and Viscosity Solutions of {Hamilton-Jacobi-Bellman} Equations,", Birkhäuser, (1997).  doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[6]

E. N. Barron and R. Jensen, Semicontinuous viscosity solutions for Hamilton-Jacobi equations with convex Hamiltonians,, Communications in Partial Differential Equations, 15 (1990), 1713.  doi: 10.1080/03605309908820745.  Google Scholar

[7]

E. S. Canepa and C. G. Claudel, Exact solutions to traffic density estimation problems involving the Lighthill-Whitman-Richards traffic flow model using Mixed Integer Linear Programing,, In, (2012), 832.   Google Scholar

[8]

P. D. Christofides, "Nonlinear and Robust Control of Partial Differential Equation Systems: Methods and Applications to Transport-Reaction Processes,", Birkhäuser, (2001).  doi: 10.1007/978-1-4612-0185-4.  Google Scholar

[9]

C. G. Claudel and A. M. Bayen, Lax-Hopf based incorporation of internal boundary conditions into Hamilton-Jacobi equation. Part I: Theory,, IEEE Transactions on Automatic Control, 55 (2010), 1142.  doi: 10.1109/TAC.2010.2041976.  Google Scholar

[10]

C. G. Claudel and A. M. Bayen, Lax-Hopf based incorporation of internal boundary conditions into Hamilton-Jacobi equation. Part {II: Computational methods},, IEEE Transactions on Automatic Control, 55 (2010), 1158.  doi: 10.1109/TAC.2010.2045439.  Google Scholar

[11]

C. G. Claudel and A. M Bayen, Convex formulations of data assimilation problems for a class of Hamilton-Jacobi equations,, SIAM Journal on Control and Optimization, 49 (2011), 383.  doi: 10.1137/090778754.  Google Scholar

[12]

M. G. Crandall and P.-L. Lions, Viscosity solutions of {Hamilton-Jacobi equations},, Transactions of the American Mathematical Society, 277 (1983), 1.  doi: 10.1090/S0002-9947-1983-0690039-8.  Google Scholar

[13]

C. Daganzo, The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory,, Transportation Research, 28B (1994), 269.  doi: 10.1016/0191-2615(94)90002-7.  Google Scholar

[14]

C. F. Daganzo, A variational formulation of kinematic waves: basic theory and complex boundary conditions,, Transportation Research B, 39B (2005), 187.  doi: 10.1016/j.trb.2004.04.003.  Google Scholar

[15]

C. F. Daganzo, On the variational theory of traffic flow: well-posedness, duality and applications,, Networks and Heterogeneous Media, 1 (2006), 601.  doi: 10.3934/nhm.2006.1.601.  Google Scholar

[16]

H. Frankowska, Lower semicontinuous solutions of Hamilton-Jacobi-Bellman equations,, SIAM Journal of Control and Optimization, 31 (1993), 257.  doi: 10.1137/0331016.  Google Scholar

[17]

J. C. Herrera, D. B. Work, R. Herring, X. J. Ban, Q. Jacobson and A. M. Bayen, Evaluation of traffic data obtained via GPS-enabled mobile phones: The Mobile Century field experiment,, Transportation Research Part C: Emerging Technologies, 18 (2010), 568.  doi: 10.1016/j.trc.2009.10.006.  Google Scholar

[18]

B. Hoh, M. Gruteser, R. Herring, J. Ban, D. Work, J. C. Herrera, A. M. Bayen, M. Annavaram and Q. Jacobson, Virtual trip lines for distributed privacy-preserving traffic monitoring,, in, (2008), 15.  doi: 10.1145/1378600.1378604.  Google Scholar

[19]

M. Krstic and A. Smyshlyaev, Backstepping boundary control for first-order hyperbolic pdes and application to systems with actuator and sensor delays,, Systems & Control Letters, 57 (2008), 750.  doi: 10.1016/j.sysconle.2008.02.005.  Google Scholar

[20]

P. E. Mazare, A. Dehwah, C. G. Claudel and A. M. Bayen, Analytical and grid-free solutions to the lighthill-whitham-richards traffic flow model,, Transportation Research Part B: Methodological, 45 (2011), 1727.  doi: 10.1016/j.trb.2011.07.004.  Google Scholar

[21]

K. Moskowitz, Discussion of "freeway level of service as influenced by volume and capacity characteristics' by D.R. Drew and C. J. Keese,, Highway Research Record, 99 (1965), 43.   Google Scholar

[22]

G. F. Newell, A simplified theory of kinematic waves in highway traffic, Part (I), (II) and (III)., Transporation Research B, 27B (1993), 281.   Google Scholar

[23]

R. C. Smith and M. A. Demetriou, "Research Directions in Distributed Parameter Systems,", SIAM, (2000).  doi: 10.1137/1.9780898717525.  Google Scholar

[24]

I. S. Strub and A. M. Bayen, Weak formulation of boundary conditions for scalar conservation laws,, International Journal of Robust and Nonlinear Control, 16 (2006), 733.  doi: 10.1002/rnc.1099.  Google Scholar

[25]

D. Work, S. Blandin, O. Tossavainen, B. Piccoli and A. Bayen, A distributed highway velocity model for traffic state reconstruction,, Applied Research Mathematics eXpress (ARMX), 1 (2010), 1.   Google Scholar

[26]

, , ().   Google Scholar

[27]

, , ().   Google Scholar

[1]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264
[2]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047
[3]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[4]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[5]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073
[6]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380
[7]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[8]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025
[9]

Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249
[10]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051
[11]

Nguyen Huu Can, Nguyen Huy Tuan, Donal O'Regan, Vo Van Au. On a final value problem for a class of nonlinear hyperbolic equations with damping term. Evolution Equations & Control Theory, 2021, 10 (1) : 103-127. doi: 10.3934/eect.2020053
[12]

Zhiting Ma. Navier-Stokes limit of globally hyperbolic moment equations. Kinetic & Related Models, 2021, 14 (1) : 175-197. doi: 10.3934/krm.2021001
[13]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, 2021, 14 (1) : 89-113. doi: 10.3934/krm.2020050
[14]

Liang Huang, Jiao Chen. The boundedness of multi-linear and multi-parameter pseudo-differential operators. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020291
[15]

Stefan Ruschel, Serhiy Yanchuk. The spectrum of delay differential equations with multiple hierarchical large delays. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 151-175. doi: 10.3934/dcdss.2020321
[16]

John Mallet-Paret, Roger D. Nussbaum. Asymptotic homogenization for delay-differential equations and a question of analyticity. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3789-3812. doi: 10.3934/dcds.2020044
[17]

Mugen Huang, Moxun Tang, Jianshe Yu, Bo Zheng. A stage structured model of delay differential equations for Aedes mosquito population suppression. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3467-3484. doi: 10.3934/dcds.2020042
[18]

Bixiang Wang. Mean-square random invariant manifolds for stochastic differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1449-1468. doi: 10.3934/dcds.2020324
[19]

Rim Bourguiba, Rosana Rodríguez-López. Existence results for fractional differential equations in presence of upper and lower solutions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1723-1747. doi: 10.3934/dcdsb.2020180
[20]

Guoliang Zhang, Shaoqin Zheng, Tao Xiong. A conservative semi-Lagrangian finite difference WENO scheme based on exponential integrator for one-dimensional scalar nonlinear hyperbolic equations. Electronic Research Archive, 2021, 29 (1) : 1819-1839. doi: 10.3934/era.2020093

2019 Impact Factor: 1.053

Tools

Metrics

  • PDF downloads (39)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences