I. INTRODUCTION

The ability to track one's location is important to a wide variety of safety-and security-critical applications. For example, logistics and supply chain management companies [1], [2], [3] that handle high-value commodities (e.g., currency notes) continuously monitor the locations of every vehicle in their fleet carrying valuables to ensure their secure transportation to the intended destination. Law enforcement officials use ankle bracelets [4], [5] to monitor the location of defendants or parole and notify them if the offender strays outside an allowed area. Ride-hailing applications such as Uber and Lyft use location information for tracking, billing, and assigning drivers to trips. Furthermore, the locations of public transport [6], [7], [8] are continuously monitored to ensure smooth and timely operation of services. With the advent of autonomous vehicles and transport systems, the dependence on location information is only bound to increase. The majority of above applications rely on GPS [9], the de facto outdoor localization system in use today. It is estimated that more than 8 billion GNSSfoot_0 devices [10] will be in use by the year 2020.

However, it has been widely demonstrated that GPS is vulnerable to signal spoofing attacks. One of the main reasons is the lack of any form of signal authentication. It is today possible to change the course of a ship [11], force a drone to land in a hostile area [12] or fake the current location in a road navigation system [13] by simply spoofing GPS signals. The increasing availability of low-cost radio hardware platforms make it feasible to execute such attacks with less than few hundred dollars worth of equipment. There has been several evidences of jamming and spoofing reported in the media. For example, as quoted in Gizmodo [14] "Because the tolltaking for commercial trucks relies on GPS tracking, they can avoid paying through jamming. If a $45 device made your daily commute free, you too might be tempted to commit a federal crime." Another report [15] mentions "Gary Bojczak admitted buying an illegal GPS jammer to thwart the tracking device in his company vehicle". Several cryptographic [16], [17], [18], [19] and non-cryptographic [20], [21], [22], [23], [24], [25], [26] countermeasures have been proposed to detect or mitigate signal spoofing attacks. These techniques are either unreliable (e.g., large number of false alarms), effective only against naive attackers or require modifications to the GPS receiver/infrastructure. Alternate localization technologies using Wi-Fi or Cellular [27], [28] lack the accuracy and coverage required for the mentioned applications, consume significant amount of power and are susceptible to interference.

Inertial navigation i.e., the use of sensors such as accelerometer, gyroscope and compass to navigate during temporary GPS outages have been around for decades, specifically in aircrafts, spacecrafts and military vehicles [29], [30], [31]. The advancements in sensor manufacturing technologies have resulted in widespread integration of these sensors into many commonly used devices such as smart phones, tablets, fitness trackers and other wearables. Many vehicle tracking and au-tomotive navigation systems have integrated GPS with inertial measurement units to improve localization and tracking of individual vehicles [32], [33], [34], [35]. Inertial sensors are key to the balancing and navigation technologies present in modern segways. Low-cost inertial sensors have also proliferated into the consumer drone industry today. One of the key advantages of inertial navigation is its robustness and resilience to any form of wireless signal spoofing and jamming attacks as there is no need for the sensors to communicate or receive information from any external entity such as satellites or other terrestrial transponders. This makes them very attractive for use in security-and safety-critical localization and tracking applications where GPS (or any wireless) spoofing and jamming attacks are a concern. The main drawback of inertial navigation units is the accumulating error of the sensor measurements. These accumulated sensor measurement errors affect the estimated position and velocity over a longer duration of time and hence limit the maximum period an inertial unit can act independently. This affects aerial and maritime navigation capabilities significantly as the tracked vehicle has all the six degrees of freedom to move. However, in the context of road navigation, the vehicle is limited by the road network and can only navigate within the constraints of these existing roadways. These inherent constraints imposed by the road networks have made low-cost inertial sensors very valuable for quick attack detection and immediate tracking of cheating entities [36], [37], [38], [39], [40], [41].

In this work, we evaluate the security guarantees of GPS/INS based on-road location tracking systems. Specifically, we address the following research questions: Given a geographic area's road network and assuming that both GPS and inertial sensor data are continuously monitored for tracking an entity's location, is it possible for an attacker to fake his navigation path or final destination? If yes, what are the attacker's constraints and possibilities? Can we exploit the physical motion constraints that exist in an urban road network and design a secure navigation algorithm that generates travel routes that are hard to spoof? For example, can a driver of a vehicle carrying high-value commodities (e.g., currency notes) spoof his assigned route and deviate without detection by the monitoring center? Can a parole with GPS/INS ankle monitor spoof his location and travel routes without detection?

We make the following contributions. First, we demonstrate that it is indeed possible for an attacker to hijack vehicles far away from the intended destination or take an alternate route without triggering any alarms even though the GPS location as well as inertial sensors are continuously monitored. We develop a suite of algorithms which we refer to as ESCAPE that leverage the regular patterns that exist in urban road networks and automatically suggests potential alternate escape routes while spoofing the assigned route with start point s, and end point d. Spoofing means that the adversary will travel on an alternate path indistinguishable from the spoofed (assigned) path. Our ESCAPE suite of algorithms accounts for intersections turn angles, roads curvatures, and magnetometer bearings to calculate the escape routes an attacker can take without detection while spoofing. We implement a real-time integrated GPS/INS spoofer that can dynamically generate spoofing signals depending on the current traffic fluidity, traffic lights, and any unexpected congestion the attacker might encounter while driving the escape path. We note that our prototype is, to the best of our knowledge, the first integrated GPS/INS spoofing system that can, in real-time, dynamically adjust the spoofing signals based on the true conditions. We further evaluated our attack's performance using open source city plans and driving traces in ten major cities across the globe. Our simulation results show that an attacker can potentially take the vehicle as far as 30 km before the monitoring system can detect a potential attack. We also drove on ten different paths of varying lengths using our real-time integrated spoofer and our results show that the attacker can hijack the vehicle to more than 2 km (the average deviation for our city), without once losing a GPS lock and with a maximum delay of 60ms between the real and spoofed paths. Note that even after detection, the tracking system has no knowledge of the true location. Our attack affects several services and applications with effective monetary value running into several millions of dollars. Our attacks essentially renders the gyroscope and accelerometer useless by generating paths acceptable to the monitoring system, but have a signature indistinguishable from the trajectory effectively traveled by the adversary. For the magnetometer, a sensor that can play a critical role in detecting the incongruence of the claimed trajectory with the measured heading, we built and demonstrated the effectiveness of a magnetometer-spoofing device that physically generate a magnetic field compatible with the spoofed trajectory. Finally, we turn around our ESCAPE suite of attack algorithms to build a countermeasure that the tracking services can run to mitigate such spoofing attacks. Specifically, we modified ESCAPE to output secure navigation routes that can be assigned given a start and end point that limit the attacker's possibilities.

II. BACKGROUND

A. Overview of GPS

GPS is today the de-facto outdoor localization system used. GPS consists of more than 24 satellites orbiting the earth. Each satellite is equipped with high-precision atomic clocks and transmits messages referred to as the navigation messages that are spread using pseudorandom codes unique to that satellite. The GPS receiver on the ground receives these navigation messages and estimates their time of arrival. Based on the time of transmission contained within the navigation message and its time of arrival, the receiver computes its distance to each of the visible satellites. Once the receiver acquires the navigation messages from at least four satellites, the GPS receiver estimates its own location and precise time.

B. GPS Spoofing Attacks

Civilian GPS is easily vulnerable to signal spoofing attacks due to the lack of any signal authentication and the publicly known spreading codes for each satellite, modulation schemes,

5 function GenerateEscapePaths(s, t): Given a spoofed path, the escape paths algorithm (Algorithm 2) generates a set of escape paths with similar distances, road curvatures and turn angles to the spoofed path. The algorithm is similar to that of the spoofed paths generator. The main differences being that the algorithm uses each spoofed path S I generated in the previous stage as input, where S I ∈ S, and outputs a set of escape paths E. Also, the escape paths generator algorithm uses the turn count in the spoofed path as a parameter to GenerateEscapePaths (lines 3 -4) and checks whether the desired turn count has been reached for the escape path under consideration (lines 10 -12).

The deviations from the spoofed paths (to avoid INS detection) can be determined by analyzing the noise sensitivity of the inertial sensors used for tracking. We demonstrate that commodity accelerometers and gyroscopes present challenges in accurately calculating the distances, road curvature and turn angles which can allow an attacker to travel to multiple destinations without detection. We show that magnetometers are easily spoofed rendering them incapable of detecting anomalies in the heading direction of the vehicle. Our analysis of the accelerometer and gyroscope noise and the potential of magnetometer spoofing are reported in Section IV-A. Unlike the spoofed paths generator algorithm that ranked paths by score, the escape paths computed by this algorithm always have a score of 1. The intuition is that all paths that pass the algorithm's filters are certain to avoid detection by INS tracking systems.

Filtering: In this algorithm, we represent the input spoofed path by S I = {(d I , ϑ I , θ I )} where d I and ϑ I denote the set of distances and road curvatures between intersections and θ I denotes the turn angles at the intersections. We first present the idea of filtering using just turn angles θ I , and later expand the discussion to include distances d I and road curvatures ϑ I . Let θ I = {θ(χ 1 ), . . . , θ(χ K )} be the derived turn angles of the spoofed path, where K is the number of intersections. A turning connection χ ′ = (s, e) in the escape path, where (s, e) ∈ E, is valid for an intersection k ∈ K when the turn angle difference is below a set threshold value T θ , i.e., |θ(χ k )θ(χ ′ )| ≤ T θ . The parameter T θ depends on the noise sensitivity of the gyroscope sensor.

The filter for distances d I is similar to turn angles. Let d I = {d 1 , . . . , d K+1 } be the derived distances of the spoofed path traveled between K intersections. For an intersection k ∈ K, d k represents the path's distance from the previous intersection k -1, i.e., d k = d(k)d(k -1) where d(.) denotes the total distance of the spoofed path at a given intersection. Note that k = 0 is the source of the path and k = K+1 is the destination of the path. A connection χ ′ in the escape path is valid for intersection k when its path distance from previous intersection k -1 is between a range defined by the k th intersection of the spoofed path, i.e.,

Here, d'(.) denotes the distance of the escape path at an intersection. The above parameters T d1 and T d2 depend on the noise sensitivity of the accelerometer sensor.

The filter for road curvature ϑ I is more complex than turn angles and distances. The reason is that, given an intersection k ∈ K, the distance d k and turn angle θ(χ k ) are scalars while ϑ(s k ) is a vector that must be derived from bearings of the road segment s k between intersections k -1 and k. Two different vectors of bearings B k and B ′ for road segments s k and s ′ , respectively, cannot be compared directly as they may be of different lengths and in different orientations, e.g., B k may be directed north when B ′ is directed east. Our idea of calculating the road curvature similarity, denoted by C(s k , s ′ ), is to translate these bearings to the same size N using linear interpolation, convert the interpolated bearings to curvature, and then compare the curvatures. Let

A connection χ ′ in the escape path is valid for intersection k when the maximum curvature similarity value is below a set threshold value T ϑ , i.e., max(C(s k , s ′ )) ≤ T ϑ . Like turn filtering, this parameter T ϑ also depends on the gyroscope noise sensitivity. To avoid detection, the above discussed constraints must hold for all K intersections of the escape path. Therefore, an