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.

Thursday, July 19, 2018

When the Silicon Meets the Road

Test what you fly; fly what you test.
-- NASA aphorism

When you are responsible for maintaining a library of reusable software that contains components that deal with honest to goodness hardware peripherals, most or all of which don't exist on your build server, how do you unit test it? As an embedded developer with decades of experience under my ever lengthening belt, I deal with this quandary often. I've worked on projects that had a vast infrastructure to simulate the underlying hardware platform; maintaining that infrastructure was its own product development effort with its own unit testing issues. I've worked on projects that had part of a sizable test organization dedicated just to testing the software on development lab bench mules that were originally hardware prototypes. I've worked on projects that had no good long term approach. You probably have too.

One of the problems with any approach is the constant economic pressure not to maintain whatever test infrastructure existed once the project gets past one or two product releases and management turned its sights onto the next shiny new revenue producing thing. When it becomes time to fix some bugs and do a new release of the legacy product, the new engineer on the project - almost inevitably it is the new engineer on the project, sometimes a junior engineer tasked with proving themselves, in some group that might be euphemistically called something like "sustaining engineering" - is now faced with having to figure out all over again how to test their changes, on software they aren't familiar with.

I had to deal with this issue writ small when working on Diminuto, an open source (LGPL) library of C functions that I have been developing over the span of more than a decade. It is my go-to systems programming toolkit. These days it’s hosted on GitHub as com-diag-diminuto, but it's been around long enough to have been maintained using several different version control systems. It started out in 2008 as a collection of supporting code for a tiny (hence the name) ARMv4 embedded project using Buildroot, with a stripped down Linux kernel, uClibc, BusyBox, and not much else. The project pre-dates the existence of the Raspberry Pi, and even the BeagleBoard.

Over time I kept expanding Diminuto as my needs grew, and porting it to new - and generally less expensive yet more powerful - platforms as they became available, as well as to new Linux releases as they arose. Eventually, all or parts of Diminuto ended up inside a handful of shipping products that I helped my clients develop. While I’ve done time in Python, wrote hundreds of thousands of lines of embedded C++ using the STL, fielded loads of Bash scripts, and even hacked JavaScript as the need arose, most of my paying gigs continue to be lower level systems work in C, writing device drivers, daemons, utilities, and glue code that holds all the higher level stuff together that's written by application and user interface developers. Diminuto also provides the infrastructure for a bunch of my other personal projects, most of which are also hosted on GitHub.
(Added 2018-07-20) An issue with maintaining software libraries of reusable code intended for systems programming and embedded applications across multiple products is that the library is architecturally divorced from any one specific product. So while you may maintain a legacy product in a test lab for unit and functional testing, it may not be adequate to test all the features in a library because the product doesn't necessarily use all those features. So to really test a new library release, you might have to corral several otherwise unrelated test mules, if that's even possible. And even that might not be sufficient for acceptable test coverage. One reason this doesn't crop up more often - in my experience anyway - is that companies don't seem to see the value in such libraries, unless they come from somewhere else (e.g. open source). I suppose that's because, again, of the cost of maintaining them. That's another reason for Diminuto: I got tired of writing and debugging and testing and documenting the same proprietary closed source code over and over again (although, you know, paid by the hour) for different clients. Or, remarkably, sometimes for the same client, but that's a story for another time. And so, some or all of Diminuto now ships in several different products produced by completely unrelated organizations.
Diminuto has a bunch of modules, what I call features, that are designed to work together.

Some features are not much more than preprocessor macros, for example:
  • Critical Section (scoped POSIX thread mutex serialization);
  • Coherent Section (scoped acquire/release memory barriers);
  • Serialized Section (scoped spin locks); and
  • Uninterruptible Section (scoped blocked signals).
Some provide simpler interfaces to inherently complicated stuff:
  • IPC4 and
  • IPC6 (IPv4 and IPv6 sockets); and
  • Mux (multiplexing using the select(2) system call).
Some provide convenience interfaces that combine several operations into a single function call, sometimes atomically to make them thread safe:
  • I2C (I2C bus);
  • Log (logging API that works in kernel space or in user space, and which automatically directs log messages to the system log for daemons, or to standard error for applications);
  • Pin (general purpose I/O using the /sys file system GPIO interface);
  • Serial (serial port configuration).
Some implement interfaces that are more consistent and mutually interoperable than the native POSIX and Linux capabilities:
  • Frequency,
  • Time,
  • Delay, and
  • Timer (the usual time-related stuff but all using the same units of time).
Some implement functionality that is a bit complex in and of itself:
  • Modulator (software pulse width modulation or PWM using POSIX interval timers);
  • Controller (proportional/integral/derivative or PID controller);
  • Shaper (traffic shaping using a virtual scheduler); and
  • Tree (red-black tree).
Some are just useful to have:
  • Phex, pronounced "fex" (print non-printable characters); and
  • Dump (print a formatted dump of selected memory).
Having this collection of documented, pre-tested, reliable functions that handle the heavy lifting of the POSIX and Linux APIs that I routinely am called upon to use means I can rapidly toss together a usable working piece of C code without having to worry about whether I did the conversion between microseconds and nanoseconds for two different POSIX calls correctly.

Virtually all of the Diminuto features have unit tests that verify the correctness of the implementation. These unit tests are part of the Diminuto repository, and like the library itself, I would expect them to build and run on any modern Linux distribution on any processor architecture.

I'm a big believer in unit tests. But some of these features, like Pin, Serial, Modulator, and Controller, can only really be adequately tested using functional tests on actual peripheral hardware. Over the years, to test these features, I’ve built a series of hardware test fixtures. These range from simple custom wired connectors, to breadboards with ICs on them. When I work on these features, I pull the appropriate fixture out of a box, hook it up to the system under test (typically a Raspberry Pi), and run the functional test.


Why is this important? Because I want to know my generically-useful but hardware-related features work before I (or anyone using my library) deploy them in an actual product development effort. And if for some reason they don’t work in the project, I want to be able to back up and use my functional tests to verify basic sanity, and to help me see where the problem might actually be. Even if the bug turns out to be in my code, the functional tests at least help me determine what does work and indict what doesn’t work. The functional tests also serve as a living example of how I intend the Diminuto features to be used.

Here are a couple of CableMax USB-to-serial adapters, one with a hand-wired loopback, the other with a commercial loopback adapter. These make use of an FTDI USB-to-serial chip, which is pretty much the only brand I use these days for this type of device.


I use these to test the Serial feature and its ability to set baud rate, data bits, and stop bits using the lbktest functional test.

Here is a NaviSys GR-701W USB GPS dongle that supports one pulse per second (1PPS) signaling using the data carrier detect (DCD) modem control line.

NaviSys Technology GR-701W

I use it to test the Serial feature DCD support by reading NMEA sentences from the GPS receiver using the dcdtest functional test. As fringe as it may seem, I have several other projects, like com-diag-hazer and its own dependents, that rely specifically on this feature. It pays to verify its functionality before any regressions creep outside of Diminuto proper. Which is really the point of all the functional and unit tests.

Here are more two CableMax USB-to-serial adapters connected back to back with a null modem adapter in between.


I also use these to test the Serial feature, either between computers or even on the same computer using two USB ports, using Diminuto's serialtool utility.

Here is what my latest functional test breadboard looks like.

Diminuto Hardware Test Fixture

It consists of a Uctronics expansion board that connects the breadboard to the Raspberry Pi via a ribbon cable; four LEDs with built in resistors; two momentary contact buttons, one active high, the other active low with a pull up resistor; and an Avago APDS9301 ambient light sensor with an I2C interface. I also bring out the pins to the hardware console port on the Raspberry Pi.

The pintest functional test, based on the Diminuto's pintool utility, uses Mux and Pin to read the buttons and to write patterns to the LEDs. Pin, Mux, and the underlying Raspberry Pi GPIO controller, supports multiplexing GPIO pins using select(2).

The pwmrheostat functional test uses Pin and Modulator to control as many as four LEDs concurrently, all at different brightness levels.

The luxrheostat functional test uses Pin, Mux, Modulator, and I2C to control a single LED pointed at the ambient light sensor, turning the LED brightness up and down, while reading the light level.

The luxcontroller (formerly pidtest) functional test uses Modulator, Mux, Pin, and I2C to control the brightness of an LED and read its intensity on an ambient light sensor, and Controller to maintain a specified light level as the background illumination changes.

(I am in the process of adding a TI ADS1115 analog to digital converter or ADC, also with an I2C interface, to this breadboard to extend the testing of the Modulator software PWM feature and the Controller PID feature. I have a first cut at a adcrheostat and adccontroller functional tests.)

Here is a FTDI TTL-232R-3V3 USB-to-serial adapter that works with 3.3 volt logic-level signals, with logic clips at the end of the signal wires.


I use this to further test the Serial feature using the Raspberry Pi hardware console port that is accessible via the breadboard.

These test fixtures are pretty simple stuff. But they allow me to exercise the hardware-related features of Diminuto such that I have high confidence that I haven't done something boneheaded. When I'm not using them, these fixtures go back into the box and go up on the shelf.

When I'm thinking of adding another hardware-centric feature to Diminuto, one of the first things I decide is how I am going to test it: if I can do so with an existing fixture; if I need to add to an existing feature like the breadboard; if I need to build a new fixture; and how much that's going to cost. Sometimes I decide the cost isn't worth it, and forgo developing the feature in Diminuto at all, leaving it to a future client to pay for and maintain if its needed. Or maybe I just wait for technology to catch up.

Test what you ship; ship what you test.
-- Chip Overclock aphorism

Updated 2018-07-25

Here's a photograph of the breadboard after I added the ADC. It's getting complicated enough that I probably should actually generate an official schematic just for my own records if nothing else.


The adcrheostat and adccontroller functional tests now use Pin and Modulator to do PWM on a GPIO pin, and I2C to read the voltage on the pin from the ADC (the tiny blue board). The latter test uses Controller to implement a PID controller that strives to maintain a specified voltage. These tests are a minor variation on how luxrheostat and luxcontroller use instead an LED and an ambient light sensor (the tiny red board).

Tuesday, June 19, 2018

Clock Club

The first rule of Clock Club is: you cannot stop talking about Clock Club. 
Last week I was privileged to spend four days attending the 43rd Annual Time & Frequency Metrology Seminar at the National Institute of Standards and Technology at their laboratories in Boulder Colorado. NIST is one of the premier scientific and technology standards organizations in the world (they were formerly the National Bureau of Standards), and continually produces bleeding edge breakthroughs, many of which end up becoming commercialized into mainstream technology that changes our lives for the better.

Here are some Fun Facts To Know And Tell on the material presented by NIST scientists, and some photos of stuff I saw. Any bone headed remarks are strictly my fault, and are probably the result of my being just a humble software developer instead of a research physicist or an electrical engineer, or maybe just not taking good notes.

My electrical engineer and physicist friends would certainly have gotten even more out of this seminar than I did. Most of the people there were EEs or physicists, from other national labs, other time standards organizations, from commercial atomic clock manufacturers, etc. For example: one guy from the National Physics Laboratory (NPL), the U.K. equivalent to NIST; a woman who was a lieutenant in the Spanish navy (had served on a frigate) now working at Spain's Naval Observatory (which has the same role as the U.S. Naval Observatory, which provides the master time reference for the U.S. military, and is a reminder that our definition of time is central to navigation at sea and is still in part in the province of astronomers); a guy who worked for the Canadian Department of National Defense (equivalent to the civil service portion of the U.S. Department of Defense) in the organization that is responsible for instrument testing and quality, etc.

Oh, and some guys whose badges listed no organization, but wrote "DOD" on a sign up sheet, and told me they were from "Maryland". Past experience tells me they work for an intelligence agency. This is not an unusual encounter in my line of work; it happened all the time when I attended conferences while employed at the National Center for Atmospheric Research due to our common interests in high performance computing and mass storage systems. The pink I. M. Pei-designed NCAR Mesa Laboratory where I worked is barely visible in the photograph below in the distance above and to the right of the NIST Building 1 where the seminar was held.


The phrase I learned that I will be most likely to drop into conversations in the future: "clock trip". I knew this was done, but I didn't know this is what it was called: you synchronize/syntonize/phase-lock a rack-mounted commercial atomic clock, running on a big battery pack, to an atomic clock at one laboratory, then you put it on a cart/truck/plane/ship/etc. and take it to another laboratory, maybe far away, where you compare it to another atomic clock. This is old school, but it still done from time to time today, since it yields the best results. Mostly, "time transfer", as this procedure is generically known, is also done over dark fiber, geosynchronous satellites, or, most typically today, GPS. Everyone now compares their atomic clocks to GPS Time (GPST), which is synced ultimately to International Atomic Time (TAI).

NIST generates UTC(NIST) time. About once a month or so, the International Bureau of Weights and Measures (BIPM) in Paris publishes an announcement of how far UTC(NIST), and every other "national" time standard, diverges from standard Universal Coordinated Time (UTC). But this is all done after the fact and only about once a month. UTC is ultimately based on the variable rotation of the Earth (hence: leap seconds), the orbit of the Earth around the Sun, and our planet's relationship to distant stars and quasars; it's determined by astronomers over a long span of time. So UTC isn't really a "real-time"... time. In the U.S., when we synchronize our clocks, it isn't really to UTC. It's probably to UTC(NIST). Or, maybe, UTC(USNO), produced by the U. S. Naval Observatory (USNO), particularly if we're in the military. Or, more realistically, GPST. Most of the clocks/NTP servers I've built are "disciplined" to GPST, adjusted to approximately UTC by adding leap seconds; this is what all the cool kids do these days.

Cesium atomic clocks are noisy in the short term (jitter) - so they are imprecise - but averaged over long durations they are extremely stable - so they are accurate. Hydrogen maser atomic clocks are extremely precise (very low short term noise) but are inaccurate - one scientist said using a hydrogen maser was a "black art" because you would never be exactly sure what extremely stable frequency you would actually get until you turned it on (weird). So NIST, USNO, and others use an ensemble of multiple commercial cesium (Cs) clocks, the long term average of which is used to servo the output of an oscillator that is locked to a hydrogen maser clock. Below is a photograph of an broken commercial hydrogen maser clock sitting in a hallway; new, they go for around a quarter million dollars U.S.


The only way to measure the quality of a clock is with another clock. This is just as problematic as it sounds, particularly since really good clocks are measurably affected by not just environmental noise like vibration, thermal noise, and even quantum noise, but also by special and general relativistic effects. We spent almost an entire day on measuring and characterizing phase noise in clocks, which is really all about measuring phase differences between a clock you trust, and one you don't, and then processing the raw data by computing an Allan Deviation (ADEV, or AVAR for the Allan Variance). Because the measurement of phase differences is a time series and not a population, the normal statistical methods don't apply. Below is a photograph of the equipment we used for a hands-on demonstration of measuring and characterizing phase differences. One of the carts contained a high-precision oven-controlled quartz oscillator that is kept running on an uninterruptible power supply so that it stays in its "sweet spot". One of them also contained an atomic clock in the form of a rubidium (Rb) oscillator.


The latest "optical" atomic clocks - so called because their resonant frequency is in the visible light range instead of the microwave range like cesium or rubidium atomic clocks - have frequencies so high they can't be measured directly because electronics can't run that fast. So they have to have "optical frequency combs" that produce a lower, measurable, frequency - 10MHz or even a low as 1Hz a.k.a. 1PPS - that is locked to the higher optical frequency. Optical atomic clocks, still in the experimental stage today, are likely to eventually replace cesium atomic clocks as the definition of the second in the International System of Units (SI). That's one reason why labs at NIST may contain awesome.


One of the optical clock labs was officially surveyed to determine its position within a millimeter or so. Because an optical atomic clock is so accurate, general relativistic effects are measurable if it’s moved just a few centimeters vertically from the Earths mass. The clock depends on measurements of less than the width of a hydrogen atom. There's an official Geodetic Survey marker embedded in the concrete lab floor.


A form of quantum noise is from virtual particles popping into existence and then disappearing due to fluctuations in the vacuum energy. This actually happens and is detectable in optical atomic clocks. Some of these clocks work by trapping *two* ions - one quantum entangled to another - in a magnetic trap and stimulating one and measuring the atomic transition of the other. Sometimes another atom of the same type will wink into existence for a very short time and then disappear. I'M NOT MAKING THIS UP. Below is a photograph of a running ytterbium (Yb) lattice optical atomic clock. Note that the lab bench of one of the most advanced experimental optical atomic clocks in existence looks more or less like my lab bench, BUT WITH LASERS.


(I observe that this idea of entangling two atoms, "exciting" one and "interrogating" the other, is pretty much the same reason that historically the most accurate mechanical pendulum clocks had two pendulums, one slaved to the other.)

The latest optical clocks are so accurate and precise that they are being used to probe the "constant-ness" of certain values in physics - like the dimensionless fine-structure constant - that we think are constant, but have no theory that says why they must be constant. As we continue to make things smaller and smaller, and faster and faster, the measurement of such values will matter more and more. One of the NIST experiments involves comparing two different implementations of optical clock-type technologies and making very fine measurements of any differences in their results that may be affected by variation in electric field strengths. In the photographs below, you can see the green versus the blue LASERs, denoting different atomic resonant frequencies at use.



Because we can measure time far more accurately - several orders of magnitude better - than any other physical unit of measure, we can expect other SI units to eventually be defined in terms of time whenever possible. So these technologies have been used by NIST to develop measurement standards for other physical units. Below is a photograph of a ten volt (10V) reference standard made up of an array of superconducting Josephson junctions on semiconductor wafer (left) placed in carrier (right) that goes in cryogenic chamber. It's accurate to maybe twelve significant digits. One wafer is worth about US$50,000.


This is used in the instrument used below to calibrate volt meters. Well, maybe not your voltmeter. NIST has built quite a few of these instruments and sold them to various labs here and abroad. You can vaguely see the small cryogenically cooled chamber behind the screen in the lower left of the rack. The noise of the compressor for the cooler was a constant thumping in the room.


I wore a mechanical wristwatch each of the four days of this conference. It just seemed appropriate. I wasn't the only one. Another guy and I compared oscillator frequencies. Mine was twice as fast as his. I have watches with 4, 6, and 8 Hz oscillators, and even a vintage "fast beat" watch with a 10 Hz oscillator. The one I was wearing that day, shown below, has an 8 Hz mechanical oscillator. Compare that to your everyday quartz wristwatch... that typically has a 32,768 Hz quartz oscillator. Conventional atomic clocks oscillate in the gigahertz (microwave) range, while optical atomic clocks oscillate in the terahertz (visible) range. Future clocks will be "nuclear clocks", oscillating in the petahertz to exahertz (x-ray) range, "ticking" via transitions in the nucleus of an atom. I think maybe NIST wins the oscillator frequency challenge.

Rolex Oyster Perpetual Milgauss Automatic Chronometer

A big Thank You to NIST and its scientists that participated in the seminar and who were so generous with their time and expertise. Because, you know, ultimately, it's all about time and frequency.

Monday, May 28, 2018

Time Is Precious

Earlier this month I was fortunate to be included on a tour of the time and frequency facilities at the Boulder Colorado laboratories of the National Institute of Standards and Technology (NIST). I got to walk right up to the F-2 cesium fountain atomic clock, which, along with the earlier F-1, is the standard frequency reference for the United States.

NIST F-2 Cesium Fountain Clock

I always thought the F-2 ran all the time. Fortunately that's not true, or else we might not have been able to see it. NIST fires it up periodically to calibrate an ensemble of commercial atomic clocks, which do run all the time, and which we didn't get to see.

I also got to see a couple of the prototypes of the chip-scale atomic clock (CSAC) developed as a result of NIST and DARPA research projects.

Prototype Chip Scale Atomic Clock


I used a commercialized version of this same device in the stratum-0 NTP server that I built.

Like me, you may have read the book From Sundials to Atomic Clocks: Understanding Time and Frequency by NIST physicist James Jespersen and Jane Fitz-Randolph. But did you know Jespersen was part of a team that won an Emmy award for the invention of close captioning?


Also: a four hundred pound quartz crystal. Just a little bit bigger than the one in your quartz wristwatch.


On display in a hallway was an IBM radio clock: it's a high precision electro-mechanical pendulum clock with a radio that allows it to set itself according to the NIST time code transmissions.


Speaking of which, it only seemed appropriate this morning that I take a little jaunt up to see the WWV (short-wave) and WWVB (long-wave) transmitter towers just north of Fort Collins Colorado.


This is from where a time code is transmitted to an estimated fifty million radio clocks, including the WWVB radio clock that I built, in the continental United States. The time code is synchronized to a cesium atomic clock on site, which in turn is synchronized to the NIST master atomic clocks in Boulder Colorado.

Tuesday, May 22, 2018

An Easy Home-Brew Stratum-1 GPS-Disciplined NTP Server

This here is my latest, and simplest, home brew, GPS-disciplined, NTP server: "Candleclock" a.k.a. "O-4". If you wanted to leave out the battery-backed-up real-time clock and the LCD display, which are really just convenience features, you could put one of these together on your lunch break out of a Raspberry Pi (here, a 3 B+)


a NaviSys GR-701W USB GPS receiver which supports 1PPS

NaviSys Technology GR-701W

and some open source software. (The guy that sells the GR-701W on Etsy is the project manager of the NTPsec open source project!) The completely optional beautiful clear plastic stand is a leaflet holder from the local office supply store.

Wednesday, April 25, 2018

How do we do it? Volume.

Here's another fun exercise from this evening class on the science, nature, and philosophy of time that I'm taking. (The instructor attributes this to Nobel prize winning physicist Kip Thorne's 1994 book Black Holes & Time Warps.)

Get three meter sticks: that's a measuring stick like a yard stick, but it's one meter long, it's divided up into one hundred centimeters, and every centimeter is divided up into ten millimeters.

Lay the first stick down on the table. There are one thousand (1,000 or 103) linear millimeters along the length defined by that stick.

Lay the second stick down on the table at a ninety degree angle to the first so that their corners touch. There are one million (1,000,000 or 106) square millimeters in the area bordered by those two sticks.

Lay the third stick orthogonally so that it stands straight up from the table and its corner touches the corners of the first two sticks. There are one billion (1,000,000,000 or 109) cubic millimeters in the volume bordered by those three sticks.

See, you thought a billion was big, didn't you? But here we are, with a billion easily measurable things just in the space on the table right in front of us.

(I was forced - FORCED, I tell you - to order three inexpensive wooden meter sticks from Amazon just so I can do this in real-life.)

Tuesday, April 24, 2018

Using the Open Secure Socket Layer Library in C

(Updated 2018-05-01.)

I've used the tools provided by Open Secure Socket Layer (OpenSSL), as well as third-party tools like cURL that supports OpenSSL and other SSL/TLS utilities like ssh(1) and scp(1), for years. And I've obviously spent a lot of time with hardware entropy generators, which provide the randomness crucial to using encryption securely. But I've never used the OpenSSL C API. This, despite the fact that much of my work is in the embedded realm which is very C or C++ centric.

I thought it was time to remedy that. So, in the spirit of learning by doing, I wrote a C library - Codex - that somewhat simplifies the use of encryption in communication streams for the kinds of C code I am frequently called upon to write.

But first, a disclaimer.

Cryptography, a vast complex field of endeavor, is in no way my area of expertise. I am merely a humble product developer. This article is a little bit on how Codex works, and little on how OpenSSL works, and what my experience was developing against the OpenSSL library.

Using Codex is only a little simpler than using OpenSSL.

The amount of code involved for even a simple functional test using the simpler Codex API is substantial. So instead of including code snippets, I'll just point you to the simplest examples in the repository on GitHub.

Here is a simple server program written using Codex: unittest-core-server.c.

Here is a client program that talks to the server: unittest-core-client.c.

There are a lot of flavors of OpenSSL and they are all a little different.

Codex compiles and runs with
  • OpenSSL 1.0.1, the default on Raspbian 8.0 "jessie";
  • OpenSSL 1.0.2g, the default on Ubuntu 16.04.3 "xenial",
  • OpenSSL 1.1.0, the default on Raspbian 9.4 "stretch";
  • BoringSSL 1.1.0Google's substantially different fork of OpenSSL; and
  • OpenSSL 1.1.1, which was the current development version at the time I wrote Codex.
The complete suite of Codex unit and functional tests successfully ran on all of these versions. And for a few of the targets I used, I successfully ran the functional tests with different versions communicating across platforms. But the underlying C code in Codex is littered with conditional #if statements selecting the appropriate code for the various OpenSSL versions, because of differences in the evolving OpenSSL C API.

In the end, it wasn't a big deal, but it was a learning experience. And my intuition tells me that some porting will be necessary with each subsequent OpenSSL release.

OpenSSL is just one of many implementations of the Transport Layer Security (TLS) standard - which has replaced the original SSL, even though I'll continue to use the term SSL in this article. TLS itself is a moving target. TLS is defined in a growing number of Request for Comment (RFC) Internet standards documents. Architects of the TLS standard, and the developers of the libraries and tools which implement it, are in a kind of cold war with other actors on the Internet, some of whom are supported by nation states, terrorist organizations, or criminal enterprises, most with nefarious intent.

I ran Codex on several different targets and platforms.

I ran the Codex unit and functional tests with OpenSSL on the following targets and platforms.

Intel NUC5i7RYH (x86_64)
Intel Core i7-5557U @ 3.10GHz x 8
Ubuntu 16.04.3 LTS "xenial"
Linux 4.10.0
gcc 5.4.0

"Lead" or "Copper"
Raspberry Pi 3 Model B (64-bit ARM)
Broadcom BCM2837 Cortex-A53 ARMv7 @ 1.2GHz x 4
Raspbian 8.0 "jessie"
Linux 4.4.34
gcc 4.9.2

Raspberry Pi 2 Model B (32-bit ARM)
Broadcom BCM2836 Cortex-A7 ARMv7 @ 900MHz x 4
Raspbian 8.0 "jessie"
Linux 4.4.34
gcc 4.9.2

Raspberry Pi 3 Model B (64-bit ARM)
Broadcom BCM2837 Cortex-A53 ARMv7 @ 1.2GHz x 4
Raspbian 9.4 "stretch"
Linux 4.14.30
gcc 6.3.0

I did not run all OpenSSL versions on all targets and platforms. I did successfully run the server side functional test on the NUC5i7 Ubuntu x86_64 platform with the client side functional test on each of the Raspberry Pi Raspbian 32- and 64-bit ARM platforms; I felt this would be a fairly typical Internet of Things (IoT) configuration.

OpenSSL is broadly configurable, and that configuration matters.

Using TLS isn't just about using one algorithm to encrypt your internet traffic. It's about using a variety of mechanisms to authenticate the identify of the system with which you are communicating, encrypting the traffic between those systems, and protecting the resources you are using for that authentication and encryption against other actors. It's a constantly evolving process. And because every application is a little different - in terms of its needs, its available machine resources, etc. - there are a lot of trade-offs to be made. That means a lot of configuration parameters. And choosing the wrong values for your parameters can mean you burn a lot of CPU cycles for no reason, or that you leave yourself open to be hacked or spoofed by a determined adversary.

Codex has a number of OpenSSL-related configuration parameters. The defaults can be configured at build-time by changing a Makefile variables. Some of the defaults can be overridden at run-time by setters defined in a private API. Here are the defaults I chose for Codex, which gives you some idea of how complex this is:
  • TLS v1.2 protocol;
  • RSA asymmetric cipher with 3072-bit keys for encrypting certificates;
  • SHA256 message digest cryptographic hash function for signing certificates;
  • Diffie-Hellman with 2048-bit keys for exchanging keys between the peer systems;
  • The symmetric cipher selected for encrypting the data stream is limited to those that conform to the Federal Information Processing Standard 140 Security Requirements for Cryptographic Modules (FIPS-140), a U. S. government computer security standard that is a common requirement in both the federal and commercial sectors.
I am pretty much depending entirely on the expertise of others to know whether these defaults make sense.

You may have to rethink how you write applications using sockets.

There are some simple helpers in Codex to assist with using the select(2) system call, which is used to multiplex sockets in Linux applications. (If you prefer poll(2) to select(2) you're mostly on your own. But on modern Linux kernels, select(2) is implemented using poll(2). I've used both, but have some preference for the select(2) API.) Multiplexing OpenSSL streams is more challenging than it might seem at first.

As the Codex functional tests demonstrate, I've multiplexed multiple SSL connections using select(2) via the Diminuto mux feature. (Diminuto is my C systems programming library upon which Codex - and many other C-based projects - is built.) But in SSL there is a lot going on under the hood. The byte stream the application reads and writes is an artifact of all the authentication and crypto going on in libssl and libcrypto. The Linux socket and multiplexing implementation in the kernel lies below all of this and knows nothing about it. So the fact that there's data to be read on the socket doesn't mean there's application data to be read. And the fact that the select(2) call in the application doesn't fire doesn't mean there isn't application data waiting to be read in a decryption buffer.

A lot of application reads and writes may merely be driving the underlying SSL protocol and its associated state machines. OpenSSL doesn't read or write on the socket of its own accord; it relies on the application to do so by making the appropriate API calls. A read(2) on a socket may return zero application data, but will have satisfied some need on the part of OpenSSL. Zero application data doesn't mean the far end closed the socket.

Hence multiplexing isn't as useful as it might seem, and certainly not as easy as in non-OpenSSL applications. A multi-threaded server approach, which uses blocking reads and writes, albeit less scalable, might ultimately be more useful. But as the functional tests demonstrate, multiplexing via select(2) can be done. It's just a little more complicated.

I should especially make note that my functional tests pass a lot of data - several gigabytes - and the application model I'm using almost always has data that needs to be written or read on the socket. What I don't test well in Codex are circumstances in which the SSL protocol needs reads or writes on the socket but the application itself doesn't have any need to do so. This can happen routinely in other patterns of application behavior.

Codex tries to deal with this by implementing its own state machines that can figure out when OpenSSL needs a additional read or a write from the API return codes. I'm not convinced I've adequately tested this, nor indeed have I figured out how to adequately test it.

Here is a state machine server program written using Codex: unittest-machine-server.c.

Here is a client program that talks to the server: unittest-machine-client.c.

One of the approaches I used to deal with some of the need to decouple sending and receiving, since either side of the communication channel may need to send or receive independently of the other just to drive the underlying OpenSSL state machines, is to make the sides of the server asynchronous with respect to one other by using queueing.

Here is a queueing server program written using Codex: unittest-handshake-server.c.

Here is a client program that talks to the server: unittest-handshake-client.c.

You'll have to learn about public key infrastructure and certificates.

Certificates are the "identity papers" used by systems using TLS to prove that they are who they say they are. But like identity papers like passports and drivers licenses, certificates can be forged. So a certificate for Alice (a computer, for example) will be cryptographically signed using a certificate containing a private key for Bob, whose public key is known. The idea is if you can trust Bob, then you can trust Alice. But what if you don't know Bob? Bob's certificate may be cryptographically signed using a certificate containing a private key for Dan, whose public key is known. And maybe you know and trust Dan. This establishes a certificate chain, as in a "chain of trust". The final certificate at the end of the chain is the root certificate, as in the "root of trust."

At some point the chain has contain a certificate from someone you know and trust. This is often the root certificate, but it might be one of the intermediate certificates. Typically this trusted certificate is that of a certificate authority (CA), a company or organization that does nothing but sign and distribute trusted certificates to system administrators to install on their servers. Whether you realize it or not, every time you access a secure server at, say, Amazon.com, using a Uniform Resource Locator (URL) - that is, you click on a web link that begins with https: - all this is going on under the hood.

All the stuff necessary to store, manage, revoke (because that's a thing), and authenticate certificates in a certificate chain is called a Public Key Infrastructure (PKI). Codex implements just enough PKI to run its unit and functional tests. All of the Codex root certificates are self-signed; Codex acts as its own certificate authority. This is okay for the functional tests, but is in no way adequate for actually using Codex in a real-life application.

The Makefile for Codex builds simulated root, certificate authority (CA), client, and server certificates for the functional tests. It is these certificates that allow clients to authenticate their identities to servers and vice versa. (The Makefile uses both root and CA certificates just to exercise certificate chaining.) 

These are the certificates that the Codex build process creates for testing, just to give you an idea of what's involved in a PKI:
  • bogus.pem is signed by root with an invalid Common Name (CN) identifying the owner;
  • ca.pem is a CA certificate for testing chaining;
  • client.pem is signed by the root certificate for client-side tests;
  • self.pem is a self-signed certificate with no root to test rejection of such certificates;
  • server.pem is signed by root and CA for server-side tests;
  • revoked.pem has a serial number in the generated list of revoked certificates;
  • revokedtoo.pem has a serial number in the list of revoked certificates;
  • root.pem is a root certificate.
Because a lot of big-time encryption is involved in creating the necessary PKI, public and private keys, and certificates, this step can take a lot of CPU time. This can take many minutes on a fast CPU, or tens of minutes or even longer on a slower system. Fortunately it only needs to be done once per system during the build process.

To run Codex between different computers, they have to trust one another.

When building Codex on different computers - like my Intel server and my Raspberry Pi ARM clients - and then running the tests between those computers, the signing certificates (root, and additional CA if it is used) for the far end have to be something the near end trusts. Otherwise the SSL handshake between the near end and the far end fails (just like it's supposed to).

The easiest way to do this for testing is to generate the root and CA credentials on the near end (for example, the server end), and propagate them to the far end (the client end) before the far end credentials are generated. Then those same root and CA credentials will be used to sign the certificates on the far end during the build, making the near end happy when they are used in the unit tests. This is basically what occurs when you install a root certificate using your browser, or generate a public/private key pair so that you can use ssh(1) and scp(1) without entering a password - you are installing shared credentials trusted by both peers.

The Codex Makefile has a helper target that uses ssh(1) and scp(1) to copy the near end signing certificates to the far end where they will be used to sign the far end's credentials when you build the far end. This helper target makes some assumptions about the far end directory tree looking something like the near end directory tree, at least relative to the home directory on either end.

Codex is deliberately picky about the certificates on the far end.

In addition to using the usual OpenSSL verification mechanisms, Codex provides an additional verification function that may be invoked by the application. The default behavior for accepting a connection from either the server or the client is as follows.

Codex rejects self-signed certificates, unless this requirement is explicitly disabled at build time in the Makefile or at run-time through a setter in the private API. This is implemented through the standard OpenSSL verification call back.

If the application chooses to initialize Codex with a list of revoked certificate serial numbers (this is a thing), Codex requires that every certificate in a certificate chain have a serial number that is not revoked. This is implemented through the standard OpenSSL verification call back.

Codex requires that either the Common Name (CN) or the Fully-Qualified Domain Name (FQDN), encoded in a certificate, match the expected name the application provides to the Codex API (or the expected name is null, in which case Codex ignores this requirement). The expected name can be a wildcard domain name like *.prairiethorn.org, which will have to be encoded in the far end system's certificate.

Codex expects a DNS name encoded in the certificate in a standards complaint fashion. Multiple DNS names may be encoded. At least one of these DNS names must resolve to the IP address from which the SSL connection is coming.

It is not required that the FQDN that matches against the expected name be the same FQDN that resolves via DNS to an IP address of the SSL connection. The server may expect *.prairiethorn.org, which could be either the CN or a FQDN entry in the client certificate, but the certificate will also have multiple actual DNS-resolvable FQDNs like alpha.prairiethorn.org, beta.prairiethorn.org, etc.

It is also not required that if a peer connects with both an IPv4 and an IPv6 address (typically it will), that they match the same FQDN specified in the certificate, or that both of the IPv4 and the IPv6 address matches. Depending on how /etc/host is configured on a peer, its IPv4 DNS address for localhost could be, and its IPv6 DNS address for localhost can legitimately be either ::ffff: or ::1. The former is an IPv4 address cast in IPv6-compatible form, and the latter is the standard IPv6 address for localhost. Either is valid.

If the peer named localhost connects via IPv4, its far end IPv4 address as seen by the near end will be and its IPv6 address will be ::ffff: If it connects via IPv6, its far end IPv4 address may be (because there is no IPv4-compatible form of its IPv6 address) and its far end IPv6 address will be ::1. The /etc/host entry for localhost may be (IPv4), or ::1 (IPv6), or both.

Furthermore, for non-local hosts, peers don't always have control of whether they connect via IPv4 or IPv6, depending on what gateways they may pass through. Finally, it's not unusual for the IPv4 and IPv6 addresses for a single host to be given different fully-qualified domain names in DNS, for example alpha.prairiethorn.org for IPv4 and alpha-6.prairiethorn.org for IPv6; this allows hosts trying to connect to a server to be able to select the IP version by using a different host name when it is resolved via DNS.

Certificates can be revoked, because sometimes stuff happens.

Codex does not directly support signed certificate revocation lists (CRLs), nor the real-time revocation of certificates using the Online Certificate Status Protocol (OCSP). It will however import a simple ASCII list of hexadecimal certificate serial numbers, and reject any connection whose certificate chain has a serial number on that list. The Codex revocation list is a simple ASCII file containing a human readable and editable list of serial numbers, one per line. Here is an example.


The serial numbers are stored in-memory in a red-black tree (a kind of self-balancing binary tree), so the search time is relatively efficient.

So you can use the tools of your PKI implementation to extract the serial numbers from revoked certificates and build a list that Codex can use. OCSP is probably better for big applications, but I wonder if we'll see it used in small IoT applications.

OpenSSL is a lot faster than I expected.

Although generating the certificates during the Codex build for the functional tests takes a long (sometimes very long) time, and there is some overhead initially during the functional tests with the certificate exchange, once the keys are exchanged the communication channel uses symmetric encryption and that runs pretty quickly.

There are a number of scripts I used to do some performance testing by comparing the total CPU time of encrypted and unencrypted functional tests for various workloads and configurations. I then used R and Excel to post-process the data. This is even more a work in progress than the rest of this effort, but so far has yielded no surprising insights.

I also used Wireshark to spy on the encrypted byte stream between two systems running a functional test.

Just to verify that I wasn't blowing smoke and kidding myself about what I was doing, I ran a Codex functional test against an openssl s_client command. That verified that at least a tool I didn't write agreed with what I thought was going on.

There is a lot going on here.

But we might as well get used to it. Many service providers that support IoT applications already require that the communication channels between clients and servers be encrypted. That's clearly going to be the rule, not the exception, in the future.


I owe a debt of gratitude to my former Bell Labs office mate Doug Gibbons who has a deep well of experience in this topic of which he generously shared only a tiny portion with me.







D. Adrian, et al., "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice", 22nd ACM Conference on Computer and Communication Security, 2015-10, https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf

K. Ballard, "Secure Programming with the OpenSSL API", https://www.ibm.com/developerworks/library/l-openssl/, IBM, 2012-06-28

E. Barker, et al., "Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths", NIST, SP 800-131A Rev. 1, 2015-11

D. Barrett, et al., SSH, The Secure Shell, 2nd ed., O'Reilly, 2005

D. Cooper, et al., "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, 2008-05

J. Davies, Implementing SSL/TLS, Wiley, 2011

A. Diquet, "Everything You've Always Wanted to Know About Certificate Validation with OpenSSL (but Were Afraid to Ask)", iSECpartners, 2012-10-29, https://github.com/iSECPartners/ssl-conservatory/blob/master/openssl/everything-you-wanted-to-know-about-openssl.pdf?raw=true

Frank4DD, "certserial.c", 2014, http://fm4dd.com/openssl/certserial.htm

V. Geraskin, "OpenSSL and select()", 2014-02-21, http://www.past5.com/tutorials/2014/02/21/openssl-and-select/

M. Georgiev, et. al., "The Most Dangerous Code in the World: Validating SSL Certificates in Non-Browser Software", 19nd ACM Conference on Computer and Communication Security (*CCS'12), Raleigh NC USA, 2012-10-16..18, https://www.cs.utexas.edu/~shmat/shmat_ccs12.pdf

D. Gibbons, personal communication, 2018-01-17

D. Gibbons, personal communication, 2018-02-12

D. Gillmor, "Negotiated Finite Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS)", RFC 7919, 2016-08

HP, "SSL Programming Tutorial", HP OpenVMS Systems Documentation, http://h41379.www4.hpe.com/doc/83final/ba554_90007/ch04s03.html

Karthik, et al., "SSL Renegotiation with Full Duplex Socket Communication", Stack Overflow, 2013-12-14, https://stackoverflow.com/questions/18728355/ssl-renegotiation-with-full-duplex-socket-communication

V. Kruglikov et al., "Full-duplex SSL/TLS renegotiation failure", OpenSSL Ticket #2481, 2011-03-26, https://rt.openssl.org/Ticket/Display.html?id=2481&user=guest&pass=guest

OpenSSL, documentation, https://www.openssl.org/docs/

OpenSSL, "HOWTO keys", https://github.com/openssl/openssl/blob/master/doc/HOWTO/keys.txt

OpenSSL, "HOWTO proxy certificates", https://github.com/openssl/openssl/blob/master/doc/HOWTO/proxy_certificates.txt

OpenSSL, "HOWTO certificates", https://github.com/openssl/openssl/blob/master/doc/HOWTO/certificates.txt

OpenSSL, "Fingerprints for Signing Releases", https://github.com/openssl/openssl/blob/master/doc/fingerprints.txt

OpenSSL Wiki, "FIPS mode and TLS", https://wiki.openssl.org/index.php/FIPS_mode_and_TLS

E. Rescorla, "An Introduction to OpenSSL Programming (Part I)", Version 1.0, 2001-10-05, http://www.past5.com/assets/post_docs/openssl1.pdf (also Linux Journal, September 2001)

E. Rescorla, "An Introduction to OpenSSL Programming (Part II)", Version 1.0, 2002-01-09, http://www.past5.com/assets/post_docs/openssl2.pdf (also Linux Journal, September 2001)

I. Ristic, OpenSSL Cookbook, Feisty Duck, https://www.feistyduck.com/books/openssl-cookbook/

I. Ristic, "SSL and TLS Deployment Best Practices", Version 1.6-draft, Qualys/SSL Labs, 2017-05-13, https://github.com/ssllabs/research/wiki/SSL-and-TLS-Deployment-Best-Practices

L. Rumcajs, "How to perform a rehandshake (renegotiation) with OpenSSL API", Stack Overflow, 2015-12-04, https://stackoverflow.com/questions/28944294/how-to-perform-a-rehandshake-renegotiation-with-openssl-api

J. Viega, et al., Network Security with OpenSSL, O'Reilly, 2002

J. Viega, et al., Secure Programming Cookbook for C and C++, O'Reilly, 2003

Monday, April 23, 2018

A Menagerie of GPS Devices with USB Interfaces

I've had several occasions to make use of Global Positioning System (GPS) receivers whose National Marine Equipment Association (NMEA) serial output is funneled through a Universal Serial Bus (USB) interface. In this article I briefly describe these devices, what I've used them (and a few without USB interfaces) for, and give you a list of the ones I've tested with some useful information about each.

Such devices are not appropriate for the the kinds of precision timing applications I described in Engines of Time; my attempt to do so quickly revealed the latency and jitter that the serial-to-USB conversion introduces, and that is deadly to Network Time Protocol (NTP) applications. But GPS-over-USB devices are really useful for quickly cobbling together a geolocation application like I described in Better Never Than Late, or for determining the general time-of-day at least to the nearest second.

A quick search for "GPS USB" on Amazon.com reveals a pile of such devices (and lots of other stuff). Most are pretty inexpensive: a few tens of dollars, if that. This turned out to be really useful when I was working on Hazer, a simple little C library to parse NMEA GPS sentences. My tiny little company ended up buying a large assortment of these devices - ten in all, plus a few other more special purpose GPS devices that didn't have USB interfaces - allowing me to test Hazer against a broad range of of NMEA sentences. (There were a few surprises here and there.)

All of these devices emit ASCII data in a standard format described in the document NMEA 0183 Standard for Interfacing Marine Electronic Devices (version 4.10, NMEA 0183, National Marine Electronics Association, 2012-06). While NMEA charges a hefty fee (hundreds of dollars) for the document, summaries are available for the price of a little web search fu. Typical NMEA output looks like this.


Because all the NMEA output is in ASCII, and the devices manifest as serial devices, you can play with them using your favorite terminal program, like screen for MacOS or Linux, or PuTTY on Windows.

Each sentence begins with a dollar sign and is terminated by an asterisk, with a simple checksum like 77, and carriage return/line feed pair. The NMEA application - GPS in this case, since there are other devices that emit other kinds of NMEA data - is identified with a GP, and its specific content by another token like, here, RMC, GGA, and GSV. Different sentences carrying different payloads, like the time of day in Universal Coordinated Time (UTC), current position in latitude and longitude expressed in degrees and decimal minutes, from exactly which satellites the position fix was derived, and the computed error in that position fix based on the orbital position of those satellites.

Why did I write Hazer to parse NMEA GPS sentences when there is plenty of perfectly usable open source code to do just that? In fact, I've used the most excellent open source GPS Daemon (gpsd) in all of my precision timing projects, as described in various articles like My WWVB Radio Clock. But as I'm fond of saying, I only learn by doing, and my goal with Hazer was to learn how NMEA GPS sentences were encoded. That turned out to be unexpectedly useful, as I've used what I've learned, and sometimes used Hazer itself, in a number of other projects, including one where I used gpsd as well.

All of the inexpensive GPS USB devices that I tested with Hazer use one of the following GPS chipsets.
  • Quectel L80-R
  • SiRF Star II
  • SiRF Star III
  • SiRF Star IV
  • U-Blox 6
  • U-Blox 7
  • U-Blox 8
From inspection or from the USB vendor and product IDs, the GPS devices use serial-to-USB converter chips from the following vendors.
  • Cygnal Integrated Products
  • FTDI
  • Prolific
  • U-Blox (integrated into the GPS chip itself)
Some of these devices are clearly the same product, repackaged under a different name; this wasn't obvious when I purchased them.

Most of these devices have an integrated patch antenna. As you will see in the photographs, a few required a separate amplified antenna in which the power was carried in-band over the coxial connection.

I didn't test the accuracy of any of these devices. But since they are all based on the a relatively small number of commercial GPS chipsets, a little web searching will yield useful information. All of these devices produced standard ASCII NMEA sentences that were easily usable by Hazer.

I tested each these GPS receivers on at least one of these systems.

Dell OptiPlex 7040
Intel Core i7-6700T x86_64 @ 2.8GHz x 8
Ubuntu 14.04.4
Linux 4.2.0
gcc 4.8.4

Intel NUC5i7RYH
Intel Core i7-5557U x86_64 @ 3.10GHz x 8
Ubuntu 16.04.2
Linux 4.10.0
gcc 5.4.0

Raspberry Pi 3 Model B
Broadcom BCM2837 Cortex-A53 ARMv7 @ 1.2GHz x 4
Raspbian GNU/Linux 8.0
Linux 4.4.34
gcc 4.9.2
(added 2018-05-11)

Most of these GPS devices already had udev rules in whichever Ubuntu distribution to which I was connecting them. This allowed them to hot plug and automatically and instantiate a serial port in the /dev directory, like /dev/ttyUSB0 (a raw USB serial device) or /dev/ttyACM0 (an Abstract Control Module serial device). A couple required some additional udev fu and those rules can be found in in GitHub.

Below is a list of the GPS USB devices, plus some others with other interfaces, that I used to test Hazer. For each, where possible, I identify the GPS chipset, the serial chipset, how often they generate an updated location, and some useful information regarding how to interface the device to a test system. If you are using any of these devices, or are trying to decide which to purchase, you may find this information useful.

USGlobalSat BU-353S4

This is an excellent unit for everyday general-purpose geolocation use. It is relatively inexpensive and easily available from a variety of outlets.

USGlobalSat BU-353S4

GPS chipset: SiRF Star IV
Serial chipset: Prolific
Serial parameters: 4800 8N1
udev Vendor/Product id: v067Bp2303
Device name: ttyUSB
Update frequency: 1Hz

USGlobalSat ND-105C

USGlobalSat ND-105C

GPS chipset: SiRF Star III
Serial chipset:Prolific
Serial parameters: 4800 8N1
udev Vendor/Product id: v067Bp2303
Device name: ttyUSB
Update frequency: 1Hz

USGlobalSat BU-353S4-5Hz

Like the other similar USGlobalSat unit but with a higher sentence frequency.

USGlobalSat BU-353S4-5Hz

GPS chipset: SiRF Star IV
Serial chipset:Prolific
Serial parameters: 115200 8N1
udev Vendor/Product id: v067Bp2303
Device name: ttyUSB
Update frequency: 5Hz

Stratux Vk-162 Gmouse

Stratux Vk-162

GPS chipset: U-Blox 7
Serial chipset: integrated
Serial parameters: 9600 8N1
udev Vendor/Product id: v1546p01A7
Device name: ttyACM
Update frequency: 1Hz

Eleduino Gmouse

Eleduino Gmouse

GPS chipset: U-Blox 7
Serial chipset: integrated
Serial parameters: 9600 8N1
udev Vendor/Product id: v1546p01A7
Device name: ttyACM
Update frequency: 1Hz

Generic Gmouse

That is how it was listed on Amazon.com.

Generic GPS

GPS chipset: U-Blox 7
Serial chipset: integrated
Serial parameters: 9600 8N1
udev Vendor/Product id: v1546p01A7
Device name: ttyACM
Update frequency: 1Hz

Pharos GPS-360

Pharos GPS-360

GPS chipset: SiRF Star II
Serial chipset: Prolific (likely integrated into provided cable)
Serial parameters: 4800 8N1
udev Vendor/Product id: v067BpAAA0
Device name: ttyUSB
Update frequency: 1Hz

Pharos GPS-500

Pharos GPS-500

GPS chipset: SiRF Star III
Serial chipset: Prolific (likely in provided dongle)
Serial parameters: 4800 8N1
udev Vendor/Product id: v067BpAAA0
Device name: ttyUSB
Update frequency: 1Hz

MakerFocus USB-Port-GPS

Shown attached to a Raspberry Pi as part of a larger project. Supports 1PPS over a digital output pin.

MakerFocus USB-port-GPS with 1PPS

GPS chipset: Quectel L80-R
Serial chipset: Cygnal (based on Vendor ID)
Serial parameters: 9600 8N1
udev Vendor/Product id: v10C4pEA60
Device name: ttyUSB
Update frequency: 1Hz

Sourcingbay GM1-86

Sourcingbay GM1-86

GPS chipset: U-Blox 7
Serial chipset: probably integrated
Serial parameters: 9600 8N1
udev Vendor/Product id: p1546v01A7
Device name: ttyACM
Update frequency: 1Hz

Uputronics Raspberry Pi GPS Expansion Board v4.1

Shown in a Raspberry Pi stack as part of a larger project.

My Stratum-1 Desk Clock

GPS chipset: U-Blox 8 (MAX-M8Q)
Serial chipset: N/A (logic-level serial)
Serial parameters: 9600 8N1
udev Vendor/Product id: N/A
Device name: ttyAMA
Update frequency: 1Hz

Jackson Labs Technologies CSAC GPSDO

This is a breathtakingly expensive part shown upper right as part of a larger project. It includes chip-scale atomic clock or CSAC - a miniature Cesium atomic clock - which is the silver square device with the white label on it. The FTDI serial-to-USB adapter visible at far right in the photograph was connected to a second serial port.

My Stratum-0 Atomic Clock

GPS chipset: U-Blox 6 (LEA-6T)
Serial chipset: N/A (RS232 serial)
Serial parameters: 115200 8N1
udev Vendor/Product id: N/A
Device name: ttyACM
Update frequency: 1Hz

Garmin GLO

Purchased for and works well with Android GPS applications.

Garmin GLO Bluetooth GOS Receiver

GPS chipset: unknown
Serial chipset: N/A (Bluetooth)
Serial parameters: N/A
udev Vendor/Product id: N/A
Device name: rfcomm
Update frequency: 10Hz

NaviSys Technology GR-701W (added 2018-05-04)

Supports 1PPS by asserting DCD. Receives WAAS augmentation too. Can be used to easily build small GPS-disciplined NTP servers. It's available at https://www.etsy.com/listing/501829632/navisys-gr-701w-u-blox-7-usb-pps.

NaviSys Technology GR-701W

GPS chipset: U-Blox 7
Serial chipset: Prolific
Serial parameters: 9600 8N1
dev Vendor/Product id: v067Bp2303
Device name: ttyUSB
Update frequency: 1Hz

TOPGNSS GN-803G (added 2018-08-08)

Has multiple RF stages so that it can receive more than one GNSS frequency at a time. Supports GPS, QZSS, GLONASS, and BEIDOU. By default, receives GPS and GLONASS and computes ensemble fixes. Supports WAAS, EGNOS, MSAS. Has seventy-two channels. A remarkable device for its price.


GPS chipset: U-Blox 8 (UBX-M8030-KT)
Serial chipset: U-Blox 8
Serial parameters: 9600 8N1
dev Vendor/Product id: v1546p01A8
Device name: ttyACM
Update frequency: 1Hz