Wednesday, 21 October 2009

BMW - No Joy: GPS is a SPOF

SPOF: Single Point of Failure. The failure modes of GPS are pretty fascinating, which is why you cannot trust it to get you home alive, not unless you are in the US army and have access to the military GPS channels. Even then, you can't trust them past the opening salvo of a war that involves non-conventional armaments.

The Bristol Traffic Project is not anti-car, but we are anti unscientific approaches to the traffic issues of our city. Therefore it was with some sadness that one member of the team was forced to issue a complaint about a recent advert. For anyone else who fears that SatNav is not something that should be relied on, consider complaining to the Advertising Standards Authority. There is no need to go to such detail, a more succint summary would be "If GPS is so reliable, how come come someone nearly drove their BMW off a cliff last summer? (Apologies for the citation style, but it was needed for the ASA complaint form). Plain text only.


Hello

I wish to complain about the accuracy of the advert for a BMW X1 which appeared in the Guardian on September 21 2009, an advert which included the statement  
"On the rare occasion Joy finds itself hopelessly lost, GPS can guide it back home"
I believe this statement is dangerously misleading as it implies that GPS is something drivers can rely on in emergencies. This is untrue. As a computer scientist I believe it places excessive faith in complex computing infrastructure, and perhaps reflects the copywriter's own lack of awareness of the infrastructure behind GPS satellite navigation, and the risks that the abdication of decision making to computers presents to car drivers, passengers and other road users.



The Navstar Global Positioning Satellite System (GPS) is run by U.S. Air Force Systems Command's Space Division in Los Angeles [1]. A constellation of atomic clocks are in low-earth orbit, continually announcing the location of all the satellites and their local clock's time, the latter compensated for relativity effects so as to appear consistent with atomic clocks on the earth's surface. GPS receivers pick up the signal from three or more satellites, and by comparing the differences in time received, estimate their location on the geode, the ellipse that represents their view of the Earth's surface in their mapping tool's datum. The location of the satellites is calculated in advance by observing the satellites orbits and predicting their future locations, information which must be regularly updated and relayed to the satellites themselves for rebroadcasting.

The time and location data is broadcast on an encrypted "P" signal which can only be decrypted by military receivers, and a civilian "C/A" signal. The civilian signal was made available after the shooting down of the KAL 007 passenger airliner over Soviet Airspace, and receivers for which have become a feature built into cars and mobile phones. It is not digitally signed; there is no way to distinguish a spoof civilian signal publishing invalid information.

In computing circles, there are number of well-known failure modes for GPS. The natural failures are:
  1. Geomagnetic storms. Affects all civilian GPS receivers, and magnetic compasses. As well as effecting the signal, the expansion of the atmosphere alters the satellite's orbits, and hence the locations they claim to be at becomes incorrect. [2]
  2. "Canyoning", loss of signal while deep inside a natural canyon, or an artificial one (such as street with skyscrapers).
  3. Reflected Signal. This is a known problem in Scottish Mountaineering: large cliff faces can reflect GPS signals. The extra delay can result in the receiver's location being misplaced.
  4. Accidental interference with GPS from sources including consumer electronics. [3]
  5. Loss of signal due to overhead materials. Civilian GPS can be lost in woods and forests, and of course in tunnels, covered car parks and the like there is minimal likelihood that a signal will be picked up.
Note that as no satellites in the GPS constellation orbit at a latitude above 54 degrees N, the risk of canyoning and reflection increases above this point -which means the Lake District and points north, including all of Scotland. From the Lake District up, no GPS satellite will ever be directly above the receiver, they will either be in the south, or near the horizon to the far north, those being the satellites on the other side of the earth becoming visible.

There are also receiver-side software or hardware problems
  1. Errors in the maps. These are common and widely documented. Note that such errors effects are invariably amplified by the trust that drivers place in the SatNav units, following them up footpaths and off river banks. To cite one example of this general problem, we would draw attention to a BMW 5 series which recently got stuck on a cliff in Yorkshire when the driver followed the SatNav's instructions to drive down a bridleway. [6]
  2. Software errors in the system. This has been discovered on a number of occasions, including in such vehicles as the International Space Station [4].
  3. Hardware errors. In the absence of formally verified hardware, the reliability of the underlying microprocessor and other hardware in a GPS receiver cannot be guaranteed.
Finally, the entire GPS infrastructure is vulnerable to malicious attack. This is covered in Vulnerability Assessment of the Transportation Infrastructure Relying on the Global Positioning system [5]. This paper by the US Department of Transport, spells out clearly the how vulnerable GPS is.

The author's concerns are of malicious failures, either from local jamming, or "Loss of GPS satellites or the Operational Control Segment" though on the latter they note that "attacking these elements can be more challenging and likely would produce a more aggressive U.S. Government response". Given the report was published, poignantly, on September 10, 2001, we know what a more aggressive response would be.

A key recommendation of the paper is:
"Create awareness among members of the domestic and global transportation community of the need for GPS backup systems or operational procedures, and of the need for operator and user training in transitions from primary to backup systems, and in incident reporting, so that safety can be maintained in the event of loss of GPS"
Given that US Government, the providers of GPS, believe that it constitutes a Single Point of Failure ("SPOF") for land, sea and air travel in the US, it seems unlikely that BMW can state unequivocally that GPS will get their customers out of trouble. All the advertisment does is reinforce the mistaken belief that GPS is reliable, and that the SatNav units' instructions should be followed blindly.



Please can this advert not be printed again, or could its claims be qualified to state that a number of natural and human problems may affect GPS coverage in an area, and that the stored maps cannot be trusted. The US Department of Transport report should act as a foundation for these qualifications. They may also mention that the risks of canyoning, reflection and other problems become more common above 54 degrees north, and therefore that GPS is less trustworthy in Scotland.

A more accurate statement would therefore be
"On the rare occasions that Joy finds itself lost, GPS will guide it home, provided Joy did not get lost in Scotland, or in woodland, the GPS maps are kept up to date, and none of the failure modes outlined in (Volpe 2001) have occurred. In keeping with Volpe's guidelines, should Joy consider getting home to be critical, we recommend gaining familiarity with alternate non-GPS navigation techniques, such as using a printed map in conjunction with a magnetic compass."
Thank you

SteveL
The Bristol Traffic Project

Citations

  1. 2001 GPS SPS Performance Standard Final
  2. The Geomagnetic Storm of 13 March 1989. ACM Risks Digest Volume 8 Issue 72
  3. Detrimental Effects of Installing Consumer Electronics on Ships, Ken Hamer 1997
  4. "Truncation error" found in GPS code on International Space Station ACM Risks Digest Volume 21 Issue 11.
  5. Vulnerability Assessment of the Transportation Infrastructure Relying on the Global Positioning system, John A. Volpe, U.S. National Transportation Systems Centre, 2001,
  6. £900 fine for sat nav nut. The Sun, 2009

1 comment:

Alan Leighton said...

Excellent! And if my BMW Professional sat nav is anything to go by don't count on it's "quickest" route to be quickest either. I have to drive past two suggested turning on my last 30 miles home and watch the time remaining drop by 5 minutes every time I do!