Data from devices with unreliable clocks

Question

Are there any viable approaches to dealing with data coming from devices with unreliable clocks?

We have a database system running on a central server. The latest addition to the system is a bunch of mobile barcode scanners running Android. We are creating a specific app and the devices will be completely locked down so the user may only interact with this app (so no access to any settings).

Overall it's very simple, the devices will connect using an ethernet dock and download a list of items to move along with their destinations. The user scans the items at the destination and collects a signature for delivery. Once connected to the dock, the location of any delivered items will be updated, along with the signature and timestamp of the move.

The plan was that the app would set the device clock from the server time whenever it was connected to the dock. Unfortunately, Android does not allow apps to set the time (the SET_TIME permission is only allowed for system apps). Additionally, the network is incredibly locked down, so we can't rely on the built-in synchronisation, and the devices only have a network connection when docked in the ethernet cradle anyway.

So, given that the devices may have arbitrarily incorrect clocks, is there any way we can correct for this when the data is uploaded? It would be possible to keep a log on the server of the clock for each device whenever it is connected.

In many ways this problem could apply to any offline-capable application. What do you do with time-related data from a device with an unreliable or untrusted clock?

It's not too difficult to correct a consistently-incorrect time, but it seems completely impossible if you consider that the device may lose time completely if the battery goes flat. A similar problem arises for an untrusted device - if the user may change the clock arbitrarily.

Has any research been done on this problem?

Answer 1

There's actually quite a bit you can do to recover something close to the actual time of most of your events.

Android gives you a few useful tools to work with, notably broadcast intents sent when the device completes a boot, when the system clock changes and when a shutdown is imminent. It also gives you a way to check the amount of real time that's elapsed since boot (which you get by calling elapsedRealtime() or elapsedRealtimeNanos()). This is a value that the system guarantees will increase monotonically. The trick is to rely as much as possible on that and as little as possible on the system clock but log both with every event.

This is probably better explained by example, so let's say your application logs these events (numbers are real seconds since boot):

018 Boot #1
200 Scan #1
215 Sync #1; server says it's 03:15:22
247 Scan #2
335 Scan #3
430 Halt #1

During the sync at 215, it's pretty easy to figure out that scan 1 happened 15 seconds before the externally-provided, presumably-reliable time of 03:15:22.

Some unknown amount of time passes and the device logs more events before the next sync:

020 Boot #2
432 Scan #4
606 Scan #5
901 Halt #2

(Another unknown amount of time passes)

016 Boot #3
117 Scan #6
208 Sync #2; Server says it's really 23:05:46

If you hung onto the time the server gave you at 215, then when you come back for a sync two boots later, you can work forward from sync #1 and divine that scans 2 and 3 happened 32 and 120 seconds after 03:15:22. (You cannot, however, draw any conclusions about events that happened after halt 1.) Scan 6 is done the same way as scan 1; it happened 91 seconds before sync 2.

That leaves scans 4 and 5, which are a problem because there was no reliable time reference during that boot/halt cycle to use in turning the time-since-boot numbers into absolute timestamps. This is where you have to turn to the system clock.

If you're logging the system time with your events, then a timestamp you believe is reliable can be used to reach forward or backward into a boot/halt interval without one by looking at the system clock difference between halts and boots.

If the system clock at boot is greater than what you recorded at the previous halt (or app install/upgrade, an event you should be logging as well), odds are actually pretty good that it's right. Barring physical tampering, booting other OS loads, etc., changing the clock while the device is down is difficult. Because most Android devices shut themselves down long before the battery is completely dead, there's usually enough juice to keep the clock going for quite some time. (While writing this, I booted a device that didn't have enough battery to boot without external power. It hadn't been turned on in at least three months, and with no access to mobile or WiFi networks, the clock was just a few minutes off of the actual time.)

If the clock shows a time at boot prior to the last-logged event, there's no way to reliably recover the times for scans that happened during that boot/halt interval. What you do with those scans is a policy decision.

Answer 2

A simple (but approximate) way to approach this is to record the offset of each device every time it syncs.

When inserting the data into your master database, use the most recent offset value for the device to adjust the recorded time.

Without a reliable reference clock on the device, it's not even possible to guarantee that two actions recorded by the same device happen in a specific order using just a clock value.

Answer 3

In the end, if I didn't misunderstand you, you've got the following situation:

• Android device has a clock set to a potentially random/wrong time.
• There's no network connection other when deploying them in their dock (probably during the night or in the morning).

As such I assume the only unknown value is the time offset between the local device's clock and the actual time.

I'd try just use the offset between actual time and device time to determine the real timestamps - essentially Harry's suggestion:

• So whenever you dock the device, it can request the current actual time.

  Let's say it's 6:30 am.

• At that moment the device's internal clock is set to 8:00 am.

• This now allows us to determine the offset between both times, in this case it'd be +1:30.

• So if one customer receives their parcel at 10:10 am (device time), we could use the previously determined offset to know the parcel actually arrived at 8:40 am (1:30 "earlier").

• Of course it's up to the implementation as to whether to store the times in device time or actual time.

• Note that we completely ignore the date. You'd have to consider that as well, if some of those trips take longer than 24 hours.

However, Android should be able to sync the system's time using a NTP time server. Even if the user can't open the clock app, this should sync in background whenever there's a network connection. As such the whole issue might actually be a non-issue.