2020-04-17

Coronavirus days: Bluetooth based contact tracing

Contact tracing is going to save us all5, and, as my cartoon suggests, involves Bluetooth. VV reckons that a privacy respecting track and trace app to fight Corona is possible and effective; Ross Anderson and Bruce "who he?" Schneier are somewhat more doubtful. But never mind that; and never mind the Upper Layers gumpf about encryption and so on which is conveniently over my head: what of the lower layers?

There are apparently several suggestions; the one VV links to is distinctly light on radio protocol and looks like it has spent all its energy on privacy paranoia1, so instead I'll look at the Apple / Google one; the Bluetooth spec is over here (via more specs here). Wiki has an embryonic article which alas points out that the bureaucrats are keen to stick their sticky fingers in.

Which Bluetooth?


First of all, this is done via BLE (Bluetooth Low Energy) not Bluetooth Classic (aka BREDR). They don't (unless I missed it) explain why they use BLE not BREDR but it does make sense: BLE adverts were pretty well designed for this kind of use case; and perhaps BLE is I think less locked down in the phone's OS (not that last bit matters too much if you're Google or Apple...)4. As everyone else also points out it doesn't use GPS at all, so there's no actual location data involved, only "proximity".

Distance estimation?


Don't be confused by the name "Low Energy"2 BTW; it is generally about the same power as "normal" Bluetooth. The radio spec says nothing about estimating distance; it does note that RSSI (Received Signal Strength Indicator) should be captured. BLE has a potential range of ~100 m in open spaces so I'd expect some kind of filtering based on RSSI is going to be needed, but I don't see that in their spec (though the spec does say that RSSI should be in the info captured; perhaps they hope to work out what to do with it later).

Digression: I made a brief attempt to Google this stuff, and found confused things like this, so it's probably worth a discussion. So: people often want to do ranging via Bluetooth, it seems obvious: the louder the signal, the closer you are, and vice versa. But "normal" Bluetooth has power control on links: if a device can't hear its peer clearly, it asks it to speak up; and if its getting deafened, asks it to be quieter. That obviously gets in the way of ranging. But, (a) this is BLE so there is no power control3 and anyway (b) there's no link up so there's no power control.

But although Bluetooth can have a long range in open air it can have a short range when expected to go through squishy wet human bodies (is your phone in your back pocket away from the person you're very close to?); it can bounce off walls; and (as RA points out) it can go through thin walls and glass.

All of which comes down to: distance estimation is difficult.

Protocol


Your phone sends out BLE "adverts", which the other side receives. And, vice versa. But, each side is one-way, so to speak: there's no link, there's no two way exchange (the Verge seems confused on this, writing about a two-way code swap, even though their text is about a diagram that clearly shows one-way flow).

The adverts are non-connectable undirected (section 2.3.1.3 of 5.2 Core Spec if you want details; I only copy this here to show you the level of detail they are providing, for those interested). Non-connectable means they are outgoing adverts, and cannot be used to attempt to form a connection back again (this is one of the design functionalities of BLE: devices can be temperature or battery sensors, that put out little blobs of data ("adverts") and never know if anyone heard them).

The other side "scans" (aka listens) for these adverts, and will record those it hears.

Whenever you have this kind of TX-RX pattern, you need to arrange it so that the communication has a reasonable chance of working, whilst not using too much power. So if devA TXs an advert every second, but devB is only listening for a packet start in a 1 ms window every 5 minutes, you're very unlikely to get lucky and hear devA. In this case the protocol says TX about every 200 ms, i.e. 4-5 times a second, which is fair enough, but the words about scanning are somewhat vaguer: Scanning interval and window shall have sufficient coverage to discover nearby Contact Detection Service advertisers within 5 mins. Scanning strategy that works best is opportunistic (leveraging existing wakes and scan windows) and with minimum periodic sampling every 5 mins. So I think this is saying that if you're scanning already, as you may well be, just leverage that. Notice that although this appears to say "scan every 5 minutes" it doesn't actually say that; it says scan-to-detect-within-5-minutes which is rather different. Minor: note that BLE adverts can be on one of three channels (unless you deliberately restrict yourself to just one, and the spec doesn't say to do that) so the scanning needs to be across those three channels. Also, I'd have thought you want to distinguish people who you briefly passed as against people you've actually been next to for some time, for which scanning rather more frequently and keeping those you've seen quite a few of might be more helpful.

Refs


* Without Apple and Google, the UK’s contact-tracing app is in trouble - the Verge, 2020/05/05
UK virus-tracing app switches to Apple-Google model - Beeb, 2020/06/19 - aka "govt IT falls part into steaming heap of drivel shocker" surprises no-one.

Notes


1. And it talks about BLE "beacons", which I don't fully understand in this context. I think they mean just adverts with a 16-byte payload, for a 16-byte Contact Detection Service service (which Gapple tell me is 0xFD6F), leaving 1 byte for flags, which would be a 31-byte advertising payload, which is the largest you're allowed.

2. It went through a variety of names while the marketing folk tried to find a name than conveyed the idea of long battery life but didn't sound wimpy; so ULP ("Ultra Low Power") came and went.

3. OK, there is power control in the 5.2 spec, but most devices in the field aren't 5.2.

4. An article I read but cannot now find said that at least on Apple, Apps using Bluetooth need to be running in the foreground, i.e. to be the active App. And that this was some kind of security measure. This is all way up the stack from me, but this Apple article appears to support that. Maybe Apple would remove that requirement for Covid-tracking baked into its OS?

5. Or, if we're honest, probably not. Me on COVAD-19 Contact Tracing Apps is Bruce Schneier offering his opinion.

2 comments:

Paul Wright said...

Ranging: the last time someone thought it was a good idea to use signal strength for ranging, there was also the fading problem, i.e. destructive interference from multipath. You can do averaging across frequencies to help with that a bit.

You've still got the "those are small, those are far away" problem with differentiating between people with phones in hand vs in pocket, as you allude to.

On the other hand, DP3T stores a contact duration so they're not silly enough to think that a single advert received means you've now got the plague. Duration long enough and adveraged RSSI high enough, plus a notification to user of the contact wallclock time (so you know that if you were in a room alone for the duration of that period, you can't have it even if beacons were received from next door's flat) might be good enough.

William M. Connolley said...

> destructive interference from multipath

Ah yes I should have mentioned that. Hello, BTW. Good to know you're still lurking. I await the "surgical robots cure COVID" post. Or perhaps they're good because they don't need masks :-)