Tuesday, July 31, 2018

We are all relying on GPS all the time whether we realize it or not.

On or around 2200 UTC on January 25 2016, what should have been a routine system administration task was being undertaken by the folks that manage the U.S. Department of Defense Global Positioning System (GPS) satellite constellation, formerly known as "Navstar". A GPS satellite identified as PRN 32 (its pseudo-random noise code number) or as SV 23 (its satellite vehicle number indicating its launch order) was being decommissioned. Parameters controlling how that satellite corrects from GPS time to Coordinated Universal Time (UTC) were being removed from a table that was sent as a routine update to all of the other GPS satellites.

But there was something special about SV 23. It was the first of the Block IIA generation of GPS satellites, launched on November 26, 1990. By virtue of its age - it was more than twenty-five years old - its SV index placed it in the lowest slot in the table. That tickled what I'm guessing was a Day One bug in the GPS software.

As a result, for nearly thirteen hours and forty-five minutes, until the problem was discovered and corrected, UTC time stamps transmitted by those satellites that had applied the update, and received by those GPS receivers that chose to use one of those satellites from whence to update its own tables in its own memory, were off by about 13.7 microseconds.

Doesn't sound like much, does it?

This event was described in the article "The World Economy Runs on GPS. It Needs a Backup Plan" [Paul Tullis,  Bloomberg Businessweek, 2018-07-25], and analyzed in detail by scientists at the U. S. Department of Commerce National Institute of Standards and Technology (NIST) in the paper "The effects of the January 2016 UTC offset anomaly on GPS-controlled clocks monitored by NIST" [Jian Yao et. al., Proceedings of the 2017 ION Precise Time and Time Interval Meeting, 2017-01-31]. The event tripped an alarm system at NIST designed to detect errors in the official NIST(UTC) time source - NIST being the official source for time and frequency in the United States - by comparing it to GPS; but when the alarm went off, it was GPS that had slipped.

Like all radio navigation systems, GPS relies on calculations with time for navigation. By computing its distance from a GPS satellite with an orbit known with very high accuracy, a GPS receiver knows that it is somewhere on a sphere whose radius is the distance between the satellite and the receiver. This distance is computed by the receiver by knowing the speed of light (with some adjustment for propagation delay in the atmosphere) and subtracting the timestamp received from a satellite from its own timestamp.

By doing this exact same calculation with another satellite, the receiver knows it is on the circle described by the intersection of two spheres. A third satellite reduces this to two points. A fourth satellite brings it to a single point.

But it's not exactly that simple: the clock in your GPS receiver (which for most of us, is our mobile phone) is nowhere near the same quality as the atomic clocks - cesium or rubidium clocks, rated for space flight - that is in every GPS satellite. And even if it were, it's not synchronized to GPS time, at least not the first time you turn it on.

So this solution for the intersecting spheres isn't a point; it's a volume. But by using a little math and a lot of compute cycles, your receiver can iteratively solve for your position by adjusting its clock in whatever direction makes this volume grow smaller. It continues to iterate, adjusting its clock, until it reaches the resolution of the GPS timestamps, a handful of nanoseconds. And at that point, two wondrous things have happened.

First, through this computation I just described known as trilateration, your GPS receiver now knows its position to within a few feet, because light travels about foot in a nanosecond.

Second, the cheap ass clock in your GPS receiver is now synchronized to GPS time. And by continuously recomputing the navigation solution, your receiver can be kept synchronized to GPS time, even as it drifts.

And it isn't just synchronized to GPS time; it is syntonized to GPS time: it is now a frequency source that is approximately in phase with the GPS atomic clocks. This is tantamount to getting every human being in the world to jump up and down at the same time.

But here's the thing: being off by 13.7 microseconds... that's 13700 nanoseconds (actually, it was 13696.03 nanoseconds, as it turns out). That's about a 13700 foot navigation error. That's over two and a half miles.

Okay, that's serious.

Well, in this particular case, not really, at least not for those that rely on GPS just for geolocation: the error was in the adjustment from GPS time (which is used for navigation) to UTC time (which is what our clocks care about). The GPS timestamps were unaffected, but the UTC time had slipped. That's why the alarm at NIST went off.

Imagine what would have hit the fan if the GPS timestamps had been off by that margin.

But GPS isn't just about navigation. Because GPS is usually such a reliable source of precision time and frequency, any system or application that relies on precise time or frequency now typically uses an inexpensive GPS receiver to serve as a time and frequency source. There was a time when the major telecommunication carriers like AT&T had their own atomic clocks used to provide network synchronization. But today, sitting here at the Palatial Overclock Estate, I have five precision time and frequency sources on my home network, in the form of GPS-disciplined clocks, with their GPS antennas sitting in windows, peering at the sky. Commercial atomic clocks cost tens of thousands of dollars; GPS receivers are tens of dollars; GPS-disciplined clocks, hundreds of dollars. Today, GPS is the common source for precision time and frequency.

So what relies on GPS for precision time and frequency, or for geolocation?

Everything you care about.

The internet. The mobile telephone network. Emergency communication systems. Radio and television broadcasters. Electrical utilities. Cable television. The banking system and stock exchanges (because the order of transactions depends on each being labeled with a highly precise timestamp). Aircraft. Advanced weapons systems.
"The U. S. Department of Homeland Security has designated 16 sectors of infrastructure as 'critical', and 14 of them depend on GPS." [Tullis]
It isn't just failures in the GPS system due to bugs or innocent mistakes. GPS can be hacked, spoofed, and trivially jammed. In some cases, with just a couple hundred bucks of commodity parts, a little ingenuity, and some open source software.

There is currently no backup to GPS. The Russians have their own global navigation satellite system - called GLONASS - with global coverage. But it is just as prone to failure, with or without malicious intent, as the U. S. GPS system. There has been talk about reviving Long Range Navigation (LORAN), the post-WWII era ground-based radio system that used hyperbolic navigation, that GPS replaced. LORAN transmitters are defensible, more powerful, more easily repairable, and less easily jammed. But that is at best a long-term (and expensive) solution. And it's not clear to me that it solves the time and frequency distribution need. Folks are working on a sort of GPS firewall that aims to detect when GPS signals are being spoofed. But we are a long way from having that sort of capability in our mobile phones. And some solutions require that you have an atomic clock on site as a backup for when GPS is unavailable. I'm probably the only person you know that has a cesium atomic clock in his living room.

I used to watch the television series The Walking Dead. The other day it occurred to me that its portrayal of an apocalyptic zombie-plague wasn't a bad metaphor for a suddenly GPS-denied world.

No comments: