We are not at the Precipice of a GPS Disaster
The Op-Ed section of a newspaper is a mixed bag. Any given morning will find a cornucopia of opinions, all with varying levels of credibility. An Op-Ed in the New York Times in January caught my eye -- America Has a GPS Problem.
I won't claim to be an expert in designing precision timing or navigation systems, nor will I profess to be an expert in the physics behind GPS. I've had to learn enough to be dangerous when building precision time distribution systems, and a (fun but misguided) project to build a stratum 0 time source with holdover.
Before diving into why I think this op-ed is problematic, let's look into how GPS works. We'll look a bit at protections that exist against the types of failures described in the op-ed, and why this is not a GPS problem. Rather, an appropriate threat-based decision needs to be made for how people rely on GPS for time and positioning data.
One System, Three Segments
The Navigation System with Timing and Ranging (NAVSTAR) Global Positioning System (GPS) is a Global Navigation Satellite System (GNSS) run by the United States Military. NAVSTAR GPS is made up of three major pieces, often referred to as “segments,” that work in concert: the space, control, and user segments. The space segment consists of a constellation of at least 24 operating satellites, orbiting in medium earth orbit (MEO), each circling the earth once every 12 hours. As of this writing, the GPS space segment has 27 operating satellites, and a total of 31 satellites in orbit. This means 4 satellites are spares, in case an operational satellite fails or needs to be taken offline for orbital manoeuvers. The size of this constellation means that there are always multiple GPS satellites in the view of an observer, from any point on earth. Having on-orbit spares means a replacement satellite can cover for a failing one, ensuring continuity of coverage.
As important as the space segment is the control segment, run by the US Space Force, to configure and monitor the satellites. The control segment tracks the quality of the timing signals each satellite produces and adjusts the clock on the satellite as needed, usually twice per day. The control segment could be considered the most sensitive aspect of the GPS. Any attacker that gets into some aspect of the control segment could tamper with the system, affecting all aspects of operational integrity of the system. A great deal of engineering goes into ensuring the resilience and distribution of the control segment functions for this reason. Without the control segment, GPS would cease to function!
Finally, there is the part we all know well: the user segment. These are the devices that rule our lives - satellite navigation, cellular systems, the infrastructure that delivers Internet connectivity, just to name a few. These are the systems that rely on a constant feed of location or precision timing data from GPS satellites, and are built to varying levels of quality. For many consumers cost and portability are king, so this implies some trade-offs as well.
It's all Relative (in Time)
At its heart, GPS relies on each satellite broadcasting a very precise timing signal that receivers on the ground listen for. Each GPS satellite contains an atomic clock, that generates this signal. Let's look at what atomic clocks are, and why they are important for the GPS satellites to do their job.
In 1967, scientists came together to more precisely define how long a second lasts. Existing measurements were not sufficiently precise for the kinds of phenomenon people wanted to measure, but the new definition also needed to not materially change how long a second is. The outcome: "The second is the duration of 9,192,631,770 periods of the radiation corresponding to the transition between the two hyperfine levels of the ground state of the caesium 133 atom."
Translation: if we can measure the signal emitted by a caesium-133 atom during that transition, we should be able to accurately indicate when a second (or some fraction of a second) has passed. The atomic clock on board a GPS satellite measures this phenomenon, and the precise timing from this clock is broadcast as a part of the GPS signal.
GPS receivers listen for this precise timing data, carried in the L1 C/A signal. Layered in with the timing signal are various bits of metadata about the satellite. This includes its unique identifier number, its health and information about its orbit (the ephemeris). This gives the receiver enough information to calculate where the satellite was located at the time it transmitted the signal.
This is where relativity takes over. As mentioned earlier, the GPS satellites are in MEO. The closest any GPS satellite gets to the earth's surface is 20,200 km (12,550 miles), directly below the satellite (at nadir). A radio signal propagates at the speed of light. Given these two facts, we know receivers directly below the satellite receive the GPS signal a bit over 75 milliseconds after it was transmitted. As you get further away from nadir, the distance between you and the satellite increases, as does the time it takes for the signal to reach your GPS receiver. This leaves us with an interesting result: we can calculate the distance between ourselves and the satellite, roughly, by knowing the difference in time between when we receive a message and when it was transmitted.
With only one satellite in view we would only be able to find our distance from the satellite. That doesn't help us position ourselves on the earth. Without getting into the mathematics of how a GPS receiver works (see references if you want to get your hands dirty), at least four satellites are required to get an accurate latitude, longitude and elevation fix. Note that three satellites are enough for an accurate latitude and longitude fix at sea level. But, if you can't get that minimum number of satellites locked on, you will not get a location fix.
When receiving timing signals from multiple satellites, one can get their precise location on earth. If you already know your location, you can apply these signals in a different way: to extract an accurate time signal. By knowing the exact time anywhere in the world, it's easy to orchestrate events that need to happen at specific time intervals, down to millionths of a second. This capability is used to run the Internet, keep cellular phone systems in check, track orders on financial markets and even synchronize events at broadcast TV stations. Of course, if you lose your fix on a GPS satellite for timing information, you'll have to fallback to holdover mechanisms. Holdover is where things start to get interesting.
Holdover
When you are dependent on GPS as a timing synchronization mechanism, you have to deal with the fact that any number of things could interfere with the GPS timing signal. These can range from accidental obstruction of your GPS receiver antenna to deliberate jamming. Most applications do not directly consume the GPS timing signal; instead, this signal is used to discipline another local clock that will be your local master time source. The process of disciplining brings your local clock into phase with the GPS clock. If all goes well, the time output by your local master should be very close (perhaps within 10's of nanoseconds) of GPS time.
For most systems, a GPS time signal will continue to discipline your local clock, so long as the signal is present. In the event you lose the GPS signal, you need to understand one critical system design factor: how far will your undisciplined clock drift over the period of time without the GPS signal? This concept of holdover time is critical: this indicates how long you can keep in synchronization with a larger system with an undisciplined local clock. Tolerance for clock drift is dependent on the application, so sometimes you don't need a very sophisticated clocking system to keep things working. Maybe all you need is long enough for a technician to identify what might have gone wrong.
Holdover time is a critical engineering design parameter for any sort of timing-based synchronization system. By understanding how long your system can tolerate being out of sync, you can determine if you need a more expensive atomic clock to act as your local time master, or if you can get away with a lower cost oven-controlled crystal oscillator (OCXO). Most OCXOs can hold stable time for hours without a disciplining signal; an atomic clock can achieve months for certain applications. As one might expect, atomic clocks can be massive, expensive, and many require a fair amount of power to run. This, too, has to be factored into any system design. Rubidium oscillators are another option, also used as precision time keepers, often in telecommunications applications. This means that data can continue to flow even when faced with extended GPS time signal disruption.
One recent innovation is the Chip-Scale Atomic Clock. Developed by the National Institute of Standards and Technology (commercialized by Symmetricom), the Chip-Scale Atomic Clock is an atomic clock that weighs a few 10s of grams and is smaller than a deck of cards. While this makes it much easier to integrate an atomic clock into a system for hold-over, these clocks are still a bit too large and too high cost for integration into a smart phone or a consumer GPS receiver. Having a small, precise atomic clock does open up a world of possibilities for detecting fake GPS signals, and enables holdover for hours in hostile areas.
Disrupting the Signal
When we talk about disrupting GPS signals, there are two major approaches an adversary can take. The lowest cost and brute force option is jamming the L1C GPS signal by flooding the GPS frequencies with wide-band noise that drowns out the satellites altogether. This happens to be one of the easiest attacks to detect. Most GPS receivers indicate that they are not receiving any satellite signals, and you can fall back to other mechanisms for navigation or use your holdover clock source until the signals return. The US military is hoping to address this by introducing additional link signals (L2C, L5), across a variety of frequencies, making it harder for low-cost jammers to block all GPS signals.
A more interesting attack has showed up in some geopolitical hotspots: spoofing a GPS signal. This is where a terrestrial transmitter broadcasts a signal, similar to that of a GPS satellite, but at much higher power than the real satellite. After all, the transmitter isn't in MEO as the satellite is, thus meaning it can easily output a higher power signal. This drowns out the real signal, tricking unsophisticated receivers into using this falsified timing signal.
A recent high profile example of this was seen by ships in the Black Sea, near the Russian port of Novorossiysk. This was a confirmation of what many had been suspecting for years: Russia has significant capabilities to falsify GPS signals. Perhaps to the chagrin of the attackers, the fingerprints of this attack were visible in Automatic Identification System (AIS) position messages broadcast by ships in the area. This shows that most ship navigation systems seem to accept any inputs they receive from their GPS receiver. This violates a basic principle of accepting sensor input to a system: ensure that your measurements fall within reasonable bounds. A quick comparison against a navigation chart would have shown this was improbable, the altered signal placed ships at a nearby airport! A more sophisticated check would also look at the ship's heading and speed and validate that the GPS fix lines up with what those values are, and signalled that the fix was likely erroneous.
Layered Defences
As with any complex system, a layered approach to defences helps to mitigate the impact of attacks on the GPS signal itself. Of course, each of these mitigations can cost significant amounts of money, and this often is the deciding factor as to whether or not any sorts of countermeasures are included.
Many system design approaches already account for failures in GPS or behaviour in environments where an attacker might try to degrade or block the GPS signal altogether:
- The laws of physics will always hold true. If a measurement puts a ship in the middle of a desert, or has a car accelerating faster than is possible, don't accept it. This means that GPS fixes should be checked against inputs from other sensors, as well as other sources of truth before they’re accepted.
- Ensure a system can gracefully degrade if you detect an invalid GPS fix. Sea and aircraft pilots, as well as car drivers all ought to be able to take over if a GPS fix is nonsensical. Operators at the sharp end of any system need to know if a fix is inaccurate or suspect.
- Holdover with precision oscillators will ensure your system has a grace period where it can continue to operate in the event you lose the GPS signal. This is a function of how much jitter a system can tolerate while continuing to operate in a degraded state.
- Cellular devices derive coarse location fix data from the towers they are in communication with. Towers (under normal circumstances) don't move, so once their location is known, cell phones use signal strength plus the known tower locations to triangulate a rough location. This should be possible to compare against the GPS fix, too.
- Some mission-critical terrestrial applications use antennas that null out signals received at or near the horizon. This makes it harder to jam or spoof signals from terrestrial locations.
Many of these approaches rely on fusing other data with the GPS signal to bring anomalies to an operator’s attention. Mission-critical designs need to consider that adversaries can tamper with the GPS signal. Even the military has realized the challenges of ensuring GPS availability at all times: drones rely on a combination of GPS and inertial navigation to avoid spoofing attacks.
There is a simple law that relates to any wireless communications: any radio signal travels over the most easily deniable and forgeable medium. From jammers to sophisticated fake signals, your system needs to deal with the basic fact that it's a jungle out there!
Continued Innovation
Nothing I've mentioned here is new or earth-shattering. These are the well-established risks of depending on GPS or other GNSSes. In order to try to reduce the risk inherent in using GNSSes, there is ongoing research into countermeasures against such attacks.
To ensure the continuity of the GPS system, the existing constellation is being replenished with GPS block III satellites. The latest launch (as of writing) on November 5, 2020 went operational on December 1, 2020. The contract to develop the follow-on to the GPS block III, the GPS block IIIF, was awarded to Lockheed-Martin in late 2018, so there are plans to continue to increase the capabilities and improve reliability of the NAVSTAR GPS constellation.
The next generation satellites, once operational, feature new signals (L2C, L5) to try to reduce the effectiveness of cheap jammers. This should improve access to GPS signals in adverse situations, and make it easy to switch from one channel to another in case of signal quality problems. This isn't a panacea, but it will raise the bar for attackers.
One last point: there are now multiple operational GNSSes. China has Beidou, Russia has GLONASS, and ESA has built Galileo. While all differ in their operational parameters, they rely on the same physical principles. Today there are civilian receivers, integrated into a single chip, that support all major GNSSes.
So is there a looming GPS Crisis?
Let's revisit the question -- is there a looming GPS problem? There is, but it's not GPS itself. The GPS space segment is continuing to evolve and resiliency for civilian use cases is improving with next-generation satellites. Multiple independent GNSSes mean that even a brief blip in GPS would leave most civilians with at least some navigation coverage.
The risk comes down to design-for-value: what capabilities can you include in a receiver without causing the costs to balloon beyond what people are willing to pay? Maybe we don't need precision holdover and ability to detect spoofing for in-car navigation. Shipborne GNSS receivers should be able to identify if they're being tricked, at least by comparing instrument readings with GPS readings. This kind of sensor fusion is complex to implement, so it will be years before we see something like this hit the mainstream.
In my opinion, if there was some incident that crippled the entirety of GPS, I suspect we'd have bigger problems than not being able to get precision time for financial markets. Localized disruptions will remain a nuisance, but systems where continuous service is critical are already built to be resilient to such incidents, at least for a period of time. For the rest of us, we can break out our paper maps and charts and do this the old fashioned way.
References
Special thanks to Ian, Peter and Brian for their helpful reviews, and especially to Ian for taking a well-needed red pen to this.
