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

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.
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 and 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 "Proceedings of the 12th International Conference on Hybrid Systems: Computation and Control," Springer-Verlag, (2009), 31-45. doi: 10.1007/978-3-642-00602-9_3.

[2]

S. Amin, X. Litrico, S. Sastry and A. Bayen, Stealthy deception attacks on water scada systems, In "Proceedings of the 13th ACM International Conference on Hybrid Systems: Computation and Control," ACM, (2010),161-170. doi: 10.1145/1755952.1755976.

[3]

J.-P. Aubin, "Viability Theory," Systems and Control: Foundations and Applications, Birkhäuser, Boston, MA, 1991.

[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-2380. doi: 10.1137/060659569.

[5]

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

[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-1742. doi: 10.1080/03605309908820745.

[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 "Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems", (2012), 832-839.

[8]

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

[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-1157. doi: 10.1109/TAC.2010.2041976.

[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-1174. doi: 10.1109/TAC.2010.2045439.

[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-402. doi: 10.1137/090778754.

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[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-583. doi: 10.1016/j.trc.2009.10.006.

[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 "Proceedings of the 6th International Conference on Mobile Systems, Applications, and Services," ACM, (2008), 15-28. doi: 10.1145/1378600.1378604.

[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-758. doi: 10.1016/j.sysconle.2008.02.005.

[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-1748. doi: 10.1016/j.trb.2011.07.004.

[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-44.

[22]

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

[23]

R. C. Smith and M. A. Demetriou, "Research Directions in Distributed Parameter Systems," SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898717525.

[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-748. doi: 10.1002/rnc.1099.

[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-35.

[26]

, , (). 

[27]

, , (). 

show all references

References:
[1]

S. Amin, A. Cardenas and S. Sastry, Safe and secure networked control systems under denial-of-service attacks, in "Proceedings of the 12th International Conference on Hybrid Systems: Computation and Control," Springer-Verlag, (2009), 31-45. doi: 10.1007/978-3-642-00602-9_3.

[2]

S. Amin, X. Litrico, S. Sastry and A. Bayen, Stealthy deception attacks on water scada systems, In "Proceedings of the 13th ACM International Conference on Hybrid Systems: Computation and Control," ACM, (2010),161-170. doi: 10.1145/1755952.1755976.

[3]

J.-P. Aubin, "Viability Theory," Systems and Control: Foundations and Applications, Birkhäuser, Boston, MA, 1991.

[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-2380. doi: 10.1137/060659569.

[5]

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

[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-1742. doi: 10.1080/03605309908820745.

[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 "Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems", (2012), 832-839.

[8]

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

[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-1157. doi: 10.1109/TAC.2010.2041976.

[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-1174. doi: 10.1109/TAC.2010.2045439.

[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-402. doi: 10.1137/090778754.

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[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-583. doi: 10.1016/j.trc.2009.10.006.

[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 "Proceedings of the 6th International Conference on Mobile Systems, Applications, and Services," ACM, (2008), 15-28. doi: 10.1145/1378600.1378604.

[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-758. doi: 10.1016/j.sysconle.2008.02.005.

[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-1748. doi: 10.1016/j.trb.2011.07.004.

[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-44.

[22]

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

[23]

R. C. Smith and M. A. Demetriou, "Research Directions in Distributed Parameter Systems," SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898717525.

[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-748. doi: 10.1002/rnc.1099.

[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-35.

[26]

, , (). 

[27]

, , (). 

[1]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[2]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128

[3]

Eugenia N. Petropoulou, Panayiotis D. Siafarikas. Polynomial solutions of linear partial differential equations. Communications on Pure and Applied Analysis, 2009, 8 (3) : 1053-1065. doi: 10.3934/cpaa.2009.8.1053

[4]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[5]

Mogtaba Mohammed, Mamadou Sango. Homogenization of nonlinear hyperbolic stochastic partial differential equations with nonlinear damping and forcing. Networks and Heterogeneous Media, 2019, 14 (2) : 341-369. doi: 10.3934/nhm.2019014

[6]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

[7]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115

[8]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[9]

Jiahui Zhu, Zdzisław Brzeźniak. Nonlinear stochastic partial differential equations of hyperbolic type driven by Lévy-type noises. Discrete and Continuous Dynamical Systems - B, 2016, 21 (9) : 3269-3299. doi: 10.3934/dcdsb.2016097

[10]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179

[11]

Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial and Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079

[12]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[13]

Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049

[14]

Shaokuan Chen, Shanjian Tang. Semi-linear backward stochastic integral partial differential equations driven by a Brownian motion and a Poisson point process. Mathematical Control and Related Fields, 2015, 5 (3) : 401-434. doi: 10.3934/mcrf.2015.5.401

[15]

Frank Pörner, Daniel Wachsmuth. Tikhonov regularization of optimal control problems governed by semi-linear partial differential equations. Mathematical Control and Related Fields, 2018, 8 (1) : 315-335. doi: 10.3934/mcrf.2018013

[16]

Yacine Chitour, Jean-Michel Coron, Mauro Garavello. On conditions that prevent steady-state controllability of certain linear partial differential equations. Discrete and Continuous Dynamical Systems, 2006, 14 (4) : 643-672. doi: 10.3934/dcds.2006.14.643

[17]

Masaki Hibino. Gevrey asymptotic theory for singular first order linear partial differential equations of nilpotent type — Part I —. Communications on Pure and Applied Analysis, 2003, 2 (2) : 211-231. doi: 10.3934/cpaa.2003.2.211

[18]

Xiaoyu Fu. Stabilization of hyperbolic equations with mixed boundary conditions. Mathematical Control and Related Fields, 2015, 5 (4) : 761-780. doi: 10.3934/mcrf.2015.5.761

[19]

T. Candan, R.S. Dahiya. Oscillation of mixed neutral differential equations with forcing term. Conference Publications, 2003, 2003 (Special) : 167-172. doi: 10.3934/proc.2003.2003.167

[20]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

2020 Impact Factor: 1.213

Metrics

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

[Back to Top]