Dedurre il numero di nuovi utenti positivi dalle TEK di Immuni

A differenza che in altri paesi, in Italia la gestione del progetto di Contact Tracing elettronico basato sulla tecnologia di Exposure Notification implementato da Apple e Google (il cosiddetto GAEN) non ha brillato per trasparenza.

Mentre in Svizzera le statistiche di utilizzo sono disponibili in real time sia attraverso sito web, sia attraverso API Endpoint per il trattamento automatico dei dati, in Italia gli unici dati disponibili sono il numero di download e un numero totale di notifiche e utenti reso disponibile “quando si ricordano” attraverso una apposita dashboard.

In questo articolo propongo un metodo per il recupero del numero di utenti positivi a partire dai Batch messi a disposizione dagli Endpoint di Immuni per la app.

Un po' di background

Il Sistema di Contract Tracing basato su GAEN funziona tramite lo scambio tra i dispositivi portatili (smartphone) di particolari chiavi crittografiche attraverso la tecnologia Bluetooth Low Energy (da qui in avanti, BT o BLE).

Per preservare la privacy degli utenti e impedire di collegare le chiavi e le informazioni divulgate a precise identità di persone, Google e Apple hanno previsto una serie di operazioni di pseudonimizzazioni basate su algoritmi di crittografia forte.

Ogni dispositivo (device) che ha installato la App immuni, giornalmente genera una chiave segreta denominata Temporary Exposure Key (TEK). A partire da essa, tramite hash crittografico (cioè, semplificando all’estremo, una funzione irreversibile) ogni 10 minuti (Rolling Period) viene generato un codice chiamato Rolling Proximity Identifier (RPI). Tale codice viene trasmesso tramite BLE a tutti i dispositivi nelle immediate vicinanze. Questi ultimi ricevono e registrano l’RPI assieme all’ampiezza del segnale, il quale è un proxy efficace se pur non molto preciso della distanza.

Quando un utente risulta positivo a un test PCR, l’operatore del Servizio Sanitario lo invita a sbloccare il caricamento delle proprie TEK inserendo un codice di autorizzazione temporaneo (OTP, One Time Passcode). A questo punto il dispositivo trasmette, dopo averlo firmato digitalmente, il pacchetto delle proprie TEK, fino ad allora segreto.

Il pacchetto di TEK viene ricevuto dal server (ingestion o reporting), processato e quindi impacchettato assieme ad altre TEK del giorno.

Nota: questo punto differisce leggermente tra l’applicazione italiana e quella di altri paesi.

Periodicamente tutti i dispositivi scaricano dal server centrale l’elenco delle TEK segnalate da utenti positivi ai test. Nella versione italiana, lo scaricamento è organizzato in batch (pacchetti) identificati con un numero progressivo: un endpoint (Index) comunica il numero dell’ultimo pacchetto disponibile e di quello più vecchio, corrispondente grossomodo al 14 giorno precedente.

All’interno del batch, oltre alla firma digitale che attesta l’autenticità del batch, sono presenti alcune informazioni, e l’elenco di parte o tutte le TEK del giorno; ogni giorno possono essere messi a disposizione anche più batch.

Ciascun dispositivo quindi a partire da ciascun TEK positivo e dallo “slot” di 10 minuti del relativo giorno, ricalcola i Rolling Proximity Identifier inviato dal dispositivo dell’utente infetto, e li confronta con gli RPI che quel giorno ha ricevuto. Qualora vi sia un riscontro (match), che significa la presenza ravvicinata con lo stesso dispositivo, viene calcolata distanza e durata e se superiore ad una certa soglia, l’utente viene allertato del contatto stretto ed invitato a isolarsi e a contattare la propria ASL di riferimento.

Come si vede, tutto il sistema garantisce l’anonimato delle persone coinvolte, in quanto in nessun caso è possibile collegare un RPI ricevuto né un TEK positivo comunicato dal server ad un dispositivo o a un utente specifico.

Contare le TEK

Vista la mancanza di comunicazione di numeri verificabili e tempestivi da parte di chi ha in carico la gestione del progetto, è nata naturale la curiosità di conoscere l’andamento dell’accettazione da parte dei cittadini italiani di questo mezzo di tracciamento, di conoscere l’efficacia dell’uso dello stesso per intercettare i focolai e di fare un confronto con le realtà degli altri paesi europei che utilizzano lo stesso sistema.

L’unica informazione disponibile è il batch giornaliero. Attraverso gli endpoint è possibile scaricare i batch dei precedenti 14 giorni.

Il formato del batch è disponibile attraverso un file protobuf, ed è reperibile da varie fonti, ad esempio la documentazione google, o dai sui sorgenti del backend di immuni.

Il batch è un file zip composto da due file, export.bin, il batch vero e proprio, e la firma digitale export.sig.

Il file export è composto da un identificatore di tipo di file lungo 12 caratteri ("EK Export v1"), con padding a 16 byte tramite spazi UTF-8; segue il file vero e proprio.

Di seguito il formato del corpo principale così come riportato dal file protobuf.

<code>syntax = "proto2";
message TemporaryExposureKeyExport {
  // Time window of keys in this batch based on arrival to server, in UTC seconds.
  optional fixed64 start_timestamp = 1;
  optional fixed64 end_timestamp = 2;
  // Region for which these keys came from, such as country.
  optional string region = 3;
  // For example, file 2 in batch size of 10. Ordinal, 1-based numbering.
  // Note: Not yet supported on iOS.
  optional int32 batch_num = 4;
  optional int32 batch_size = 5;
  // Information about associated signatures
  repeated SignatureInfo signature_infos = 6;
  // The TemporaryExposureKeys for initial release of keys.
  // Keys should be included in this list for initial release,
  // whereas revised or revoked keys should go in revised_keys.
  repeated TemporaryExposureKey keys = 7;
  // TemporaryExposureKeys that have changed status.
  // Keys should be included in this list if they have changed status
  // or have been revoked.
  repeated TemporaryExposureKey revised_keys = 8;
}</code>

Si notino i campi start_timestamp, end_timestamp che indicano il campo di validità del batch in formato Unix Timestamp (numero di secondi dal 1/1/1970, “the epoch”).

Il campo keys identifica le chiavi TEK vere e proprie, il cui formato è il seguente:

<code>message TemporaryExposureKey {
  // Key of infected user
  optional bytes key_data = 1;
  // Varying risk associated with a key depending on diagnosis method
  optional int32 transmission_risk_level = 2 [deprecated = true];
  // The interval number since epoch for which a key starts
  optional int32 rolling_start_interval_number = 3;
  // Increments of 10 minutes describing how long a key is valid
  optional int32 rolling_period = 4
  [default = 144]; // defaults to 24 hours
  // Data type representing why this key was published.
  enum ReportType {
    UNKNOWN = 0;  // Never returned by the client API.
    CONFIRMED_TEST = 1;
    CONFIRMED_CLINICAL_DIAGNOSIS = 2;
    SELF_REPORT = 3;
    RECURSIVE = 4;  // Reserved for future use.
    REVOKED = 5;  // Used to revoke a key, never returned by client API.
  }

  // Type of diagnosis associated with a key.
  optional ReportType report_type = 5;

  // Number of days elapsed between symptom onset and the TEK being used.
  // E.g. 2 means TEK is 2 days after onset of symptoms.
  optional sint32 days_since_onset_of_symptoms = 6;
}</code>

Le chiavi vere e proprie sono contenute nel campo key_data e sono array di byte. E' importante notare inoltre il campo rolling_start_interval_number e il campo rolling_period. Entrambi permettono di localizzare il periodo di validità della chiave.

Con il numero di TEK da solo è possibile avere una stima approssimativa del numero di utenti se si considera la lunghezza media del set di TEK pubblicato da ciascun utente. Inizialmente si è stimato a 10 il numero medio di chiavi, considerando che esso può andare da un minimo di 1 ad un massimo di 14.

Una stima più precisa tuttavia si può fare facendo una considerazione diversa.

Si assume che in ciascun batch del giorno X siano presenti solo ed esclusivamente le TEK degli utenti che le hanno caricate il giorno X-1; dunque ciascun utente avrà caricato la propria sequenza di TEK, in numero variabile tra 1 e 14. In ogni caso, è verosimile che la TEK del giorno X-1 sia sempre presente, pertanto contando il numero di TEK del giorno X-1 di ciascun batch, si ha il numero di utenti relativo.

Il campo rolling_start_interval_number non è uno unix timestamp come gli altri campi, ma è il progressivo del Rolling Interval, ovvero il periodo di tempo di validità dei singoli RPI. Pertanto verosimilmente corrisponde al periodo di 10 minuti a partire dall’Epoch; con la semplice operazione

rolling_start_interval_number * 10 * 60

si ottiene il timestamp di inizio di validità.

Pertanto aggregando tutte le date relative a ciascun campo rolling start interval e contando le chiavi, si ottiene il numero di utenti positivi.

La validità di questa assunzione è comprovata dall’aggregazione dei singoli batch; i numeri di chiavi per data del singolo batch sono sempre decrescenti.

Un esempio concreto

Ho scritto un piccolo tool in Python maccheronico che spacchetta i vari batch e li importa in un semplice db sqlite3. Il db è composto da due tabelle unite da una foreign key sul codice del batch di provenienza.

Una volta importati i dati del codice nella tabella batches e le chiavi nella tabella keys, è possibile fare la una query ed ottenere (una stima de) il numero di utenti positivi che hanno caricato le chiavi.

Dapprima si raggruppano e si contano le chiavi per batch di riferimento e per start_timestamp. In questo modo si ottengono le chiavi per giorno in ciascun batch. Poi si raggruppano questi per batch e si tiene solo valore con start_timestamp più alto. Infine si raggruppano e si somma per giorno del batch, in quanto più batch possono essere riferiti allo stesso giorno.

La query che si ottiene è la seguente:

<code>SELECT sum(numkeys), dt FROM
(SELECT numkeys, batchid, max(start_timestamp) AS dt  FROM
    (SELECT count(key) as numkeys, b.batchid as batchid, start_timestamp
        from keys
            left outer join batches b on
                keys.batch = b.id and keys.country = b.country
        group by batch,start_timestamp
        order by start_timestamp DESC)
    group by batchid)
group by dt;</code>

Oggi, 20/10, ho scaricato tutti i batch disponibili, ossia dal 169 al 222; inseriti nel db e passati alla query si ottengono i seguenti numeri:

Il codice di questo tool è disponibile nel mio repository su GitHub, in licenza GPL3.

La dashboard

Il tool TekExplorer sviluppato da Fabio Lombardo (lombax), Giorgio Bonfiglio (grg), Fabrizio Carimati (Clodo), cui ho contribuito con qualche idea (tra cui questa), sarà presto on line, e illustra la situazione italiana confrontata con quella di altri paesi che usano applicazioni simili.

Gli altri paesi

Ciascun paese, pur utilizzando la tecnologia GAEN, tratta i batch in modo differente. Per quanto riguarda SwissCovid, per esempio, le TEK sono organizzate in batch giornalieri unici che riportano tutte e solo le TEK valide per quel giorno; di conseguenza i batch possono cambiare successivamente quando nuovi utenti vengono segnalati positivi. Da una parte questo metodo “preserva” ulteriormente la privacy degli utenti, rendendo non possibile correlare una particolare TEK con le altre dello stesso utente, d’altra parte però costringe i dispositivi a scaricare tutte le precedenti TEK, comprese quelle già in loro possesso, aumentando il traffico e dunque il carico sui server, aumentando il consumo di energia da parte dei dispositivi che devono ripetere il confronto degli RPI anche con quelli già processati, e impedisce l’identificazione del numero di nuovi utenti giornalieri senza un confronto storico dei pacchetti.

La Germania sembra utilizzare un approccio simile a quello italiano, per quanto si è riscontrato in alcuni batch che le chiavi possono iniziare anche qualche giorno dopo il primo giorno disponibile. Si riscontrano, per esempio, 1 chiave per il giorno X, 1 per il giorno X-1 e magari 250 per il giorno X-2. In questo caso la stima è meno precisa ma si può fare con un certo grado di approssimazione.

Per gli altri paesi, io e gli altri sopra citati stiamo ancora lavorando, e conto di aggiornare questo post presto.