src/match.c

   1 /** \ingroup Matching
   2  * @file
   3  * @author      David Llewellyn-Jones <david@flypig.co.uk>
   4  * @version     $(VERSION)
   5  *
   6  * @section LICENSE
   7  *
   8  * Copyright David Llewellyn-Jones, 2020
   9  * Released under the GPLv2.
  10  *
  11  * @brief Provides a way to match collected RPIs with downloaded DTKs.
  12  * @section DESCRIPTION
  13  *
  14  * This class provides functionality allowing RPIs that have been collected
  15  * over Bluetooth to be matched against DTKs downloaded from a Diagnosis
  16  * Server.
  17  *
  18  * The list of RPIs and DTKs can be constructed easily using the
  19  * \ref Container functions.
  20  *
  21  */
  22
  23 /** \addtogroup Matching
  24  *  @{
  25  */
  26
  27 // Includes
  28
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <stddef.h>
  32 #include <stdint.h>
  33
  34 #include <openssl/crypto.h>
  35 #include <openssl/hmac.h>
  36 #include <openssl/err.h>
  37
  38 #include "contrac/contrac.h"
  39 #include "contrac/utils.h"
  40 #include "contrac/log.h"
  41 #include "contrac/rpi_list.h"
  42 #include "contrac/dtk_list.h"
  43
  44 #include "contrac/match.h"
  45
  46 // Defines
  47
  48 // Structures
  49
  50 /**
  51  * @brief A match list element
  52  *
  53  * This is an opaque structure that represents a single item in the list and
  54  * captures a match between an RPI and a DTK.
  55  *
  56  * The structure typedef is in match.h
  57  */
  58 struct _MatchListItem {
  59         uint32_t day_number;
  60         uint8_t time_interval_number;
  61
  62         MatchListItem * next;
  63 };
  64
  65 /**
  66  * @brief The head of a match list
  67  *
  68  * This is an opaque structure that represents the head of the list. Each item
  69  * in the list captures a match between an RPI and a DTK.
  70  *
  71  * This is the object usually passed as the first parameter of every non-static
  72  * function.
  73  *
  74  * The structure typedef is in match.h
  75  */
  76 struct _MatchList {
  77         size_t count;
  78         MatchListItem * first;
  79         MatchListItem * last;
  80 };
  81
  82 // Function prototypes
  83
  84 MatchListItem * match_list_item_new();
  85 void match_list_item_delete(MatchListItem * data);
  86 void match_list_append(MatchList * data, MatchListItem * item);
  87
  88 // Function definitions
  89
  90 /**
  91  * Creates a new instance of the class.
  92  *
  93  * @return The newly created object.
  94  */
  95 MatchList * match_list_new() {
  96         MatchList * data;
  97
  98         data = calloc(sizeof(MatchList), 1);
  99
 100         return data;
 101 }
 102
 103 /**
 104  * Deletes an instance of the class, freeing up the memory allocated to it.
 105  *
 106  * This will also delete all items contained in the list.
 107  *
 108  * @param data The instance to free.
 109  */
 110 void match_list_delete(MatchList * data) {
 111         if (data) {
 112                 match_list_clear(data);
 113
 114                 free(data);
 115         }
 116 }
 117
 118 /**
 119  * Creates a new instance of the class.
 120  *
 121  * @return The newly created object.
 122  */
 123 MatchListItem * match_list_item_new() {
 124         MatchListItem * data;
 125
 126         data = calloc(sizeof(MatchListItem), 1);
 127
 128         return data;
 129 }
 130
 131 /**
 132  * Deletes an instance of the class, freeing up the memory allocated to it.
 133  *
 134  * @param data The instance to free.
 135  */
 136 void match_list_item_delete(MatchListItem * data) {
 137         if (data) {
 138                 free(data);
 139         }
 140 }
 141
 142 /**
 143  * Clears all items from the list.
 144  *
 145  * Removes all items from the list to create an empty list. The memory
 146  * associated with the items in the list is freed.
 147  *
 148  * @param data The list to operate on.
 149  */
 150 void match_list_clear(MatchList * data) {
 151         MatchListItem * item;
 152         MatchListItem * next;
 153
 154         item = data->first;
 155         while (item) {
 156                 next = item->next;
 157                 match_list_item_delete(item);
 158                 item = next;
 159         }
 160
 161         data->first = NULL;
 162         data->last = NULL;
 163         data->count = 0;
 164 }
 165
 166 /**
 167  * Returns the number of items in the list.
 168  *
 169  * Immediately after creation, or after the \ref match_list_clear() function
 170  * has been called, this will return zero.
 171  *
 172  * @param data The list to operate on.
 173  */
 174 size_t match_list_count(MatchList * data) {
 175         return data->count;
 176 }
 177
 178 /**
 179  * Returns the first item in the list.
 180  *
 181  * Useful for iterating through the items in the list.
 182  *
 183  * @param data The list to operate on.
 184  * @return The first item of the list.
 185  */
 186 MatchListItem const * match_list_first(MatchList const * data) {
 187         return data->first;
 188 }
 189
 190 /**
 191  * Returns the next item in the list.
 192  *
 193  * Useful for iterating through the items in the list.
 194  *
 195  * @param data The current item in the list.
 196  * @return The next item in the list following the current item.
 197  */
 198 MatchListItem const * match_list_next(MatchListItem const * data) {
 199         return data->next;
 200 }
 201
 202
 203 /**
 204  * Returns the day number of the item in the list.
 205  *
 206  * This will represent the day number of when an interaction occurred with
 207  * someone who has subsequently uploaded their DTK to a diagnosis server due to
 208  * testing positive.
 209  *
 210  * @param data The list to operate on.
 211  * @return The day number for this item.
 212  */
 213 uint32_t match_list_get_day_number(MatchListItem const * data) {
 214         return data->day_number;
 215 }
 216
 217 /**
 218  * Returns the time interval number of the item in the list.
 219  *
 220  * This will represent the time interval number of when an interaction occurred
 221  * with someone who has subsequently uploaded their DTK to a diagnosis server
 222  * due to testing positive.
 223  *
 224  * @param data The list to operate on.
 225  * @return The time interval number for this item.
 226  */
 227 uint8_t match_list_get_time_interval_number(MatchListItem const * data) {
 228         return data->time_interval_number;
 229 }
 230
 231 /**
 232  * Adds an item to the list.
 233  *
 234  * This adds a match to the list. It's primarily for internal use.
 235  *
 236  * @param data The list to append to.
 237  * @param item The match to append.
 238  */
 239 void match_list_append(MatchList * data, MatchListItem * item) {
 240         if (data->last == NULL) {
 241                 data->first = item;
 242                 data->last = item;
 243         }
 244         else {
 245                 data->last->next = item;
 246                 data->last = item;
 247         }
 248         data->count++;
 249 }
 250
 251 /**
 252  * Returns a list of matches found between the beacons and diagnoses.
 253  *
 254  * This searches through the list of DTKs and the list of RPIs provided, and
 255  * returns a list of matches.
 256  *
 257  * If the returned list has any elements in, this would suggest that the user
 258  * has been in contact with someone who tested positive and uploaded their DTK
 259  * to a Diagnosis Server.
 260  *
 261  * The match list isn't cleared by this call and so any new values will be
 262  * appended to it.
 263  *
 264  * @param data The list that any matches will be appended to.
 265  * @param beacons A list of RPIs extracted from overheard BLE beacons.
 266  * @param diagnosis_keys A list of DTKs downloaed from a Diagnosis Server.
 267  */
 268 void match_list_find_matches(MatchList * data, RpiList * beacons, DtkList * diagnosis_keys) {
 269         // For each diagnosis key, generate the RPIs and compare them against the captured RPI beacons
 270         DtkListItem const * dtk_item;
 271         RpiListItem const * rpi_item;
 272         uint8_t interval;
 273         bool result;
 274         Rpi * generated;
 275         MatchListItem * match;
 276         Dtk const * diagnosis_key;
 277         Rpi const * rpi;
 278
 279         dtk_item = dtk_list_first(diagnosis_keys);
 280         generated = rpi_new();
 281
 282         while (dtk_item != NULL) {
 283                 diagnosis_key = dtk_list_get_dtk(dtk_item);
 284                 // Generate all possible RPIs for this dtk and compare agsinst the beacons
 285                 for (interval = 0; interval < RPI_INTERVAL_MAX; ++interval) {
 286                         result = rpi_generate_proximity_id(generated, diagnosis_key, interval);
 287                         if (result) {
 288                                 // Check against all beacons
 289                                 rpi_item = rpi_list_first(beacons);
 290                                 while (rpi_item != NULL) {
 291                                         rpi = rpi_list_get_rpi(rpi_item);
 292                                         result = rpi_compare(rpi, generated);
 293
 294                                         if (result) {
 295                                                 if (interval != rpi_get_time_interval_number(rpi)) {
 296                                                         result = false;
 297                                                         LOG(LOG_DEBUG, "Matched beacons don't match intervals\n");
 298                                                 }
 299                                         }
 300
 301                                         if (result) {
 302                                                 match = match_list_item_new();
 303                                                 match->day_number = dtk_get_day_number(diagnosis_key);
 304                                                 match->time_interval_number = interval;
 305                                                 match_list_append(data, match);
 306                                         }
 307
 308                                         rpi_item = rpi_list_next(rpi_item);
 309                                 }
 310                         }
 311                 }
 312
 313                 dtk_item = dtk_list_next(dtk_item);
 314         }
 315
 316         rpi_delete(generated);
 317 }
 318
 319 /** @} addtogroup Matching*/
 320