Brief ReportIsaac Perry
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 59, NO. 12, DECEMBER 2014 3357
High Confidence Networked Control for Next Generation Air Transportation Systems
Pangun Park, Harshad Khadilkar, Hamsa Balakrishnan, and Claire J. Tomlin
Abstract—This paper addresses the design of a secure and fault- tolerant air transportation system in the presence of attempts to disrupt the system through the satellite-based navigation system. Adversarial aircraft are assumed to transmit incorrect position and intent information, potentially leading to violations of sepa- ration requirements among aircraft. We propose a framework for the identification of adversaries and malicious aircraft, and then for air traffic control in the presence of such deliberately erroneous data. The framework consists of three mechanisms that allow each aircraft to detect attacks and to resolve conflicts: fault detection and defense techniques to improve Global Positioning System (GPS)/inertial navigation, detection and defense techniques using the Doppler/received signal strength, and a fault-tolerant control algorithm. A Kalman filter is used to fuse high frequency iner- tial sensor information with low frequency GPS data. To verify aircraft position through GPS/inertial navigation, we propose a technique for aircraft localization utilizing the Doppler effect and received signal strength from neighboring aircraft. The control algorithm is designed to minimize flight times while meeting safety constraints. Additional separation is introduced to compensate for the uncertainty of surveillance information in the presence of adversaries. We evaluate the effect of air traffic surveillance attacks on system performance through simulations. The results show that the proposed mechanism robustly detects and corrects faults generated by the injection of malicious data. Moreover, the proposed control algorithm continuously adapts operations in or- der to mitigate the effects these faults. The ability of the proposed approaches to defend against attacks enables reliable air traffic operations even in highly adversarial surveillance conditions.
Index Terms—Automatic dependent surveillance—Broadcast, intelligent control, misbehavior detection, next generation air transportation systems.
Manuscript received February 14, 2013; revised December 03, 2013; accepted January 05, 2014. Date of publication August 28, 2014; date of current version November 18, 2014. This work has been supported in part by the NSF under CPS:ActionWebs (CNS-931843), by ONR under the HUNT (N0014- 08-0696) and SMARTS (N00014-09-1-1051) MURIs and by grant N00014- 12-1-0609, by AFOSR under the CHASE MURI (FA9550-10-1-0567). Recommended by Associate Editor P. Tabuada.
P. Park was with the Department of Electrical Engineering and Computer Science, University of California at Berkeley, Berkeley, CA, USA. He is now with the Electronics and Telecommunications Research Institute, 305-700 Daejon, Korea (e-mail: [email protected]).
H. Khadilkar was with the Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA, USA. He is now with IBM Research, India (e-mail: [email protected]).
H. Balakrishnan is with the Department of Aeronautics and Astronau- tics, Massachusetts Institute of Technology, Cambridge, MA, USA (e-mail: [email protected]).
C. J. Tomlin is with the Department of Electrical Engineering and Computer Science, University of California at Berkeley, Berkeley, CA, USA (e-mail: [email protected]).
Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TAC.2014.2352011
T HE Next Generation Air Transportation System (Next-Gen) plan supported by the Federal Aviation Adminis- tration (FAA) aims to enhance the safety and efficiency of air transportation systems , . The air traffic surveillance network is a critical part of NextGen operations, responsible for safety, traffic efficiency, and pilot assistance . In NextGen, aircraft will carry new wireless communication and computing platforms, and have enhanced sensing capabilities. Intercon- nected aircraft not only collect information about themselves and their environment, but they also exchange this information in real time with other nearby aircraft. Wireless communication can operate beyond the line-of-sight constraints of radar and vision solutions, and thus enables cooperative approaches for air traffic management.
Security is an essential consideration for upgrades in the air transportation system, because there is the risk of making mali- cious behavior easier , . The high level of decentralization in NextGen has both advantages and disadvantages: a rich set of tools is offered to pilots and authorities, but a formidable set of vulnerabilities also develops. There are potentially many hundreds of millions of communication devices in nation- wide NextGen. It is recognized that in such a system, each communication component represents a new point of system vulnerability, and the system must be analyzed to understand and mitigate the impact of an attack at such points. For instance, an adversary may induce loss of separation between aircraft by injecting incorrect data in the satellite-based navigation system. These adversaries inject false surveillance information to create a “malicious” aircraft without the aircraft’s knowledge. This misinformation may be re-transmitted by the aircraft, thus spreading to the rest of the network. As programmable sensors and actuators become more pervasive in NextGen, implement- ing appropriate security mechanisms will become even more critical to the overall safety and performance of the system.
The primary obstacle for designing a secure air transportation system is the tight coupling between communication, compu- tation, and control. There are several challenges in securing NextGen air traffic management. First, many of the envisioned safety and pilot-assistance applications impose strict deadlines on message delivery. Security mechanisms must take these constraints into consideration and work with low processing and messaging overhead. Otherwise, it would suffice for an adversary to generate a high volume of false messages and over- load resources. Second, since position dissemination is crucial for air traffic management, incorrect position information has severe impact on both safety and efficiency. Each aircraft needs
0018-9286 © 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
3358 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 59, NO. 12, DECEMBER 2014
to know not only its own position but also those of other aircraft in its neighborhood. Global Positioning System (GPS) signals are weak, can be spoofed, and are prone to jamming , . Existing solutions such as frequency hopping do not completely solve the problem . Third, to locate the aircraft in three- dimensional space, a minimum of four distance measurements to neighboring aircraft are required for triangulation. However, it is hard to obtain reliable measurements in the presence of adversaries across an air traffic surveillance network.
Finally, employing defense-in-depth methodologies, includ- ing fail-safe devices and fail-secure functionality, is a necessary part of any serious effort to protect NextGen. However, even a robust combination of such security systems is not sufficient for addressing the vulnerabilities of such a complex control system. The above is especially true when reliable operations must continue despite failures in the system. To address this complex problem and provide comprehensive security, all of the communication, computation, and control systems must be safeguarded in NextGen.
This paper addresses the fault detection and defense problem of air traffic surveillance networks in enroute areas. Ground infrastructure in these areas is sparse, and several regions are not covered by ground stations. Hence, the main detection and defense mechanisms are implemented onboard aircraft. We as- sume that aircraft regularly broadcast their status (e.g., position, speed, and direction) along with warnings about potential dan- gers using wireless communication . Further, to simplify the presentation in this paper, all aircraft are assumed to fly at the same altitude. This assumption is generally valid in enroute ar- eas, yet the analysis is straightforward to generalize to the case in which aircraft change altitude. We propose mechanisms com- bining the detection and defense algorithms of surveillance net- works with a fault-tolerant control algorithm. Specifically, this consists of three mechanisms that allow aircraft to detect attacks and to resolve conflicts (violations of minimum separation re- quirements): (1) Fault detection of the GPS signal that increases the integrity of the GPS/Inertial Navigation System (INS) nav- igation loop in adversarial environments; (2) Distributed detec- tion and defense techniques using the Doppler effect and the Received Signal Strength (RSS) measurement of received mes- sages in order to verify aircraft position through the GPS/INS system; and (3) A fault-tolerant control algorithm that accounts for the uncertainty of surveillance information by introducing additional separation. In contrast to other position verification approaches, our detection and defense mechanisms are de- signed for a general network environment where nodes or bea- cons can move and no special hardware for ranging is available.
The remainder of this paper is organized as follows. Section II summarizes related work including localization tech- niques and control algorithms. Section III describes the models used for the air traffic and surveillance systems. Section IV presents the proposed system architecture. In Section V, we present the state and measurement dynamics. Section VI ex- plains the GPS/INS loop that estimates the position of aircraft. Section VII proposes a self-localization algorithm using the Doppler effect and RSS measurements. Section VIII presents a fault detection technique using RSS measurements. Section IX describes a static verification algorithm to detect malicious air-
craft. Section X presents the control algorithm, and the system performance is evaluated in Section XI. Finally, Section XII summarizes the contributions of the paper.
II. RELATED WORK
During recent years, many localization techniques have been proposed for a variety of wireless network applications . We only provide a brief survey on localization techniques suitable for air traffic surveillance networks. The localization approaches of air traffic networks differ in their assumptions about network deployment and hardware capabilities.
Centralized localization techniques would be impractical for air traffic surveillance networks because of the high communi- cation costs and inherent delay, hence we focus on distributed localization techniques . Distributed localization methods use only limited communication with nearby nodes . These methods can be classified as range-based or range-free. Range- based techniques use distance estimates or angle estimates in location calculations, while range-free solutions depend only on the contents of received messages. Range-based approaches utilize time of arrival , time difference of arrival of two different signals , angle of arrival , RSS , and Doppler shifts , . Some of these techniques require expensive separate hardware –. Moreover, stationary models of radio signals are not realistic assumptions since RSS measurements can be very sensitive to the channel environ- ment . The range-based approach using Doppler shifts is less susceptible to multi-path propagation than the RSS-based ranging approach , , since reflections do not change the frequency of the signal. The Doppler effect has been used extensively to estimate the velocity of tracked objects or to improve the accuracy of tracking systems , . In , the self-localization of sensors is developed based on measuring Doppler shifts in a tone that is emitted from a mobile beacon. Each static node updates its location information by using the location and heading of the beacon as well as the frequency of the acoustic tone. On the other hand, in , the tracked node transmits a signal and stationary nodes measure the Doppler shifts of the transmitted signal. A number of stationary nodes are deployed around the tracked node and the tracked node cooperates with the tracking system.
None of these schemes address the problem encountered in air traffic surveillance, in which both the nodes and the beacons can move. They can be adapted for mobile networks by refreshing location estimates frequently, but are not designed with any explicit consideration for how mobility affects the localization performance. The only work we are aware of that considers localization with mobile nodes and beacons is in . They use the sequential Monte Carlo Localization method for the random waypoint mobility model. Although it is very frequently used in mobile ad hoc networks, this mobility model is not realistic. The particle set can become easily diffused, dispersing across the image plane in the LOP of the enroute layout. Moreover, this localization technique is vulnerable to internal adversaries, since range-free localization depends only the contents of received messages. In addition, the particle- based approximation of filtered density is not sufficient to
PARK et al.: HIGH CONFIDENCE NETWORKED CONTROL FOR NEXT GENERATION AIR TRANSPORTATION SYSTEMS 3359
characterize the tail behavior of true density. This problem becomes more severe when the outliers are existent.
Previous localization techniques are vulnerable to several kinds of attacks, and an attacker may be able to disrupt the integrity or availability of all known localization techniques. A secure range-free localization technique was developed in . However, it cannot detect and remove compromised beacon nodes. A number of authors have proposed using time-of-fight measurements and the speed of light to securely gain location information about untrusted parties. A time-bounded protocol is proposed as a defense against man-in-the-middle attacks on cryptographic identification schemes . This protocol can be used to verify the proximity of two devices connected by a wired link. A protocol using temporal packet leashes is proposed for wireless networks to defend against similar attacks . A new distance bounding protocol is proposed based on ultrasound and radio wireless communication in . The protocol can only make an approximate decision about whether or not a claimer is within a certain region. These systems either require specific hardware or rely on an infrastructure of verifiers to check positions. However, these assumptions are not likely to hold in air traffic surveillance networks. It is desirable to be able to verify neighbors’ position without any additional or dedicated devices. Furthermore, most techniques require beacon nodes to be numerous and evenly distributed so that they can cover the whole network. We are interested in performing localization in a more general network environment where no special hardware for ranging is available, the prior deployment of beacon nodes is unknown, the beacon density is low, and the node distribution is irregular.
Jamming attacks have been used as Denial-of-Service (DoS) attacks against different applications using wireless communi- cations. In , several techniques for the detection of various jamming attacks are proposed and evaluated at MAC layer. The structure of this problem has been investigated in order to identify tradeoffs and capture the impact of different pa- rameters on performance . Optimal attack and network defense strategies were derived for the case of a single-channel wireless sensor network. The authors assume that all network nodes are uniformly distributed and that the topology is static. Countermeasures for coping with jammed regions in wireless networks have been studied in  and . In , the use of low density parity check codes was proposed to cope with jamming. Further, an anti-jamming technique was proposed for 802.11b that involved the use of Reed-Solomon codes. In , a three-dimensional modulation scheme, known as message- driven frequency hopping (MDFH), was proposed. The basic idea of MDFH is that part of the message acts as the pseudo- random sequence for carrier frequency selection at the transmit- ter. The selection of carrier frequencies is directly controlled by the encrypted information stream rather than by a predefined pseudo-random sequence as in conventional FH, in order to improve the system spectral efficiency.
The increasing importance of security in vehicular networks has attracted . Sybil attacks , in which an adversary creates an illusion of traffic congestion by claiming multiple identities, are known always be possible except under unreal- istic assumptions of resource and coordination among entities
Fig. 1. Proposed framework in enroute airspace.
without a logically centralized authority. Several techniques to detect Sybil attacks in ad hoc networks, including radio resource testing, registration, and position verification have been studied . Position verification is a more promising approach for vehicular networks, since radio resource testing relies on specific assumptions on radio modules and registration alone is not effective. A distributed detection scheme of Sybil attacks is proposed for networks in which a set of fixed base stations overhear a malicious node . This scheme will not suit enroute air traffic management, since ground base stations are sparse, and several regions are not even covered.
Several studies in the past decade have addressed the control of air traffic in a distributed setting –. However, these studies have not considered a combination of decentralized control with measurement and state uncertainty, nor have they addressed security issues with the proposed protocols. Eulerian models of air traffic such as  are useful when the per- spective is strategic rather than tactical. Centralized algorithms such as those proposed in  can handle the computational requirements, but such approaches are limited in their scope when individual aircraft need to carry out conflict detection and resolution. In order to guarantee safety in the presence of uncertainty, the theory of reachable sets has been shown to be highly effective . However, the computational requirements of this method are too prohibitive for fast distributed control. To the best of the authors’ knowledge, this paper is the first one to propose a framework combining detection and defense surveillance with robust control. The proposed protocol is both computationally light and robust to uncertainty, as well as accidental or deliberate faults in measurement.
The proposed framework with its components is illustrated in Fig. 1. The direction of the arrows represents the flow of information. The infrastructure of NextGen is comprised of the mobile units (aircraft) and ground facilities. Aircraft-to-Aircraft (A2A) and Aircraft-to-Infrastructure (A2I) communication will enable safety-critical applications that provide warnings about accidents, traffic conditions and other events . Secure air transportation systems are assumed to rely on public key cryptography and digital signatures to protect A2A and A2I messages in NextGen.
3360 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 59, NO. 12, DECEMBER 2014
A. Communication Protocols
Automatic Dependent Surveillance-Broadcast (ADS-B) is designed to increase the safety, capacity, and efficiency of the airspace by enhancing information sharing between aircraft and ground facilities . This system provides transmission ranges of typically 60 to 100 nm, with data rates in the 1 Mbps range. ADS-B uses 1090 MHz frequency band, different from the operation bandwidth of GPS systems . Safety messages are signed and include the coordinates and time stamp of the sender. When an aircraft validates a certificate, it checks whether its credential has been revoked. If the credential is not revoked, it verifies the key used to sign the message and, once this is done correctly, it verifies the message. After validating an ADS-B message, an aircraft stores the information in its location table. Since our detection and defense mechanisms are distributed and localized, we assume that most neighboring aircraft in the airspace can be trusted. This allows aircraft to use information from reliable neighbors in order to identify malicious aircraft. It is reasonable to expect that only a rela- tively small percentage of aircraft (less than 10%) would be malicious.
B. Adversary Model
The reliability of safety-critical control systems can be threatened by a wide variety of failure modes, including fail- ures of the communication links, sensors, controllers, and/or actuators. While some failure modes result in complete loss of control, others would only result in loss of reliable control.
In this paper, we consider adversaries or attackers that dis- rupt the air traffic management by attacking the satellite-based navigation system. Any of these attacks can affect air traffic management. There is a difference between malicious and non- malicious misbehavior. Non-malicious misbehavior is typically random, and can be detected easily. On the other hand, it is difficult to handle a sophisticated attack that exploits weak- nesses in the satellite-based navigation system. An attacker can sufficiently modify messages to pass outlier detection tests. For example, adversaries could jam satellite signals within their range and thus selectively or completely prevent the GPS updates. Further, a GPS spoofing attack broadcasts a slightly more powerful signal that the legitimate one, and then slowly deviates away towards the position desired by the attacker . Therefore, the system needs to provide more compre- hensive protection from malicious misbehavior. The proposed defense mechanisms apply to both malicious and non-malicious misbehavior.
IV. SOLUTION OVERVIEW
This section provides an overview of the proposed architec- ture of the Misbehavior Detection System (MDS) whose role is to detect off-nominal aircraft. Each aircraft executes this system, which functions in a distributed and localized manner. The details of each component are given in subsequent sections.
A necessary part of the design of autonomous systems is the inclusion of fault detection and identification algorithms which
ensure that aircraft operate in a safe and reliable manner. The MDS protects the interface between aircraft networks, onboard control units, and data and services required by other aircraft, as illustrated in Fig. 2. This system constantly monitors the status of onboard systems and provides real-time detection of attacks. Further, the MDS controls the data flow from external sources to the aircraft. We consider two approaches for position verification in the MDS: a GPS/INS integrated system and a Doppler/RSS fusion process. A Kalman filter is used to fuse high frequency inertial sensor information with low frequency GPS data in the GPS/INS integrated system. The Kalman filter estimates the errors in position and velocity using the difference between external GPS sensor information and inertial indicated information. An error propagation model is used to fuse the ob- served and predicted positions and velocities. These parameters are fed back to the INS unit. To verify aircraft position through GPS/INS system, the detection and defense mechanisms are designed using the Doppler effect and RSS measurements of received ADS-B messages. An Extended Kalman Filter (EKF) is used to estimate the distance to neighboring aircraft. Given an adequate number of neighbors, the current position is obtained by using the Minimum Mean Square Estimate (MMSE). Then, a Kalman filter predicts the position of an aircraft based on the model of state dynamics. Once the Doppler/RSS-based position is obtained, predicted positions are compared to the ones estimated by the GPS/INS system. If the two differ by more than a predefined threshold, the GPS/INS position is deemed adversarial and rejected.
The estimated distance to neighboring aircraft is also used to verify neighbors’ reported position through ADS-B. If the estimated distance does not match with distance information of a received ADS-B message, the verifying aircraft discards that message. Furthermore, we propose a simple detection technique using the history of RSS measurements to verify aircraft position. The control algorithm is responsible for com- puting the control action of an aircraft based upon the new observation. The control algorithm accounts for the uncertainty of the surveillance information in the detected malicious data. We emphasize that our mechanisms rely on the availability of prior information collected during periods of time when it deems it is not under attack. In contrast to other position verification approaches, we do not rely on special hardware or on preinstalled infrastructure –[13, 29].
V. SYSTEM MODEL
This section presents the modeling of aircraft dynamics and various measurement models. As discussed in the previous section, two different measurement models are used to design the detection and defense mechanisms: GPS/INS system and Doppler/RSS system.
A. System Dynamics
The state of a moving aircraft at time k is defined by the vector x(k) = (x(k), y(k), ẋ(k), ẏ(k), ẍ(k), ÿ(k)) where x(k) and y(k) specify the position, ẋ(k) and ẏ(k) specify the speed, and ẍ(k) and ÿ(k) specify the acceleration in the x and y
PARK et al.: HIGH CONFIDENCE NETWORKED CONTROL FOR NEXT GENERATION AIR TRANSPORTATION SYSTEMS 3361
Fig. 2. System architecture of misbehavior detection system. We add the section number corresponding to the explanation of each component.
directions in a two-dimensional space. The aircraft dynamics can be described by a discrete-time linear time-invariant model
x(k) = Fx(k − 1) + w(k) (1)
where x(k) ∈ R6 is the state vector, F is the state transition matrix, and w(k) ∈ R6 is white Gaussian noise with zero mean and covariance matrix Q(k) > 0, i.e. E[w(k)] = 0 and E[w(k)w(k)T ] = Q(k). The covariance matrix Q(k) of w(k) is Q(k) = σ2wI, where I denotes the unit matrix and σw is the standard deviation. Note that the system model does not include the input set. The control input is based on the information of GPS/INS system. However, the information resource of GPS/INS system is not secure under attack.
The time scale for reaction to events as described in this paper is of the order of several seconds. We therefore assume that the changes in velocity are accomplished by the next time step of the simulation. Maximum and minimum velocity is specified in the optimization problem, and includes the phys- ical limits of the aircraft at the given altitude in Section X. Furthermore, since the time scale for reaction is long, it is not required to capture computationally intensive equations of state dynamics, such as the six degree of freedom models used in simulators. The state dynamics in this paper are modeled as a Wiener-sequence acceleration model . This model provides a good compromise between complexity and performance in the modeling of aircraft dynamics. In such a model, F and w are equal to
⎝ I2 ∆tI2
I2 O2 I2 ∆tI2 O2 O2 I2
and w(k) =
⎝ (∆2t /2)B ∆tB B
⎠ ψ(k) where ∆t is the elapsed time
since the last time step, and ψ(k) ∈ R is zero mean white Gaussian noise with assumed known covariance. I2 ∈ R2×2 is the identity matrix, O2 ∈ R2×2 is a zero matrix, and B ∈ R2×1 is a matrix for which all elements are equal to 1. The state error depends on the length of time between two calibrations using surveillance information, which in turn depends on the
network performance and security. For instance, adversaries can jam GPS signals within their range to increase the time interval between calibrations of GPS receivers. Since control stability is expected to be subject to a maximum latency in the sensing layer of the network, it is necessary to ensure that the time difference between two calibrations satisfies the maximum latency acceptable to the control algorithm. We derive the value of the maximum allowable latency in Section X-F.
The general measurement model is represented as
z(k) = Hx(k) + v(k) (2)
where z(k) ∈ Rm is the measurement vector of the sensor and H ∈ Rm×n is the measurement matrix. v(k) ∈ Rm is white Gaussian observation noise with zero mean and with assumed known covariance matrix R(k) = E[v(k)v(k)T ].
In the next subsections we will describe the two specific measurement models that we use in the proposed architecture. Accurate analysis of measurement error is essential to ensuring effective data fusion of GPS/INS system and Doppler/RSS system, as we will discuss in Sections VI and VII. Furthermore, the error bound of measurement error is critical for controller design. Additional separation is introduced to compensate for the uncertainty of surveillance information due …