fuzz/hashtable.c

   1 /*
   2  * Copyright 2024 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  * https://www.openssl.org/source/license.html
   8  * or in the file LICENSE in the source distribution.
   9  */
  10
  11 /*
  12  * Test hashtable operation.
  13  */
  14 #include <limits.h>
  15 #include <openssl/err.h>
  16 #include <openssl/bio.h>
  17 #include <internal/common.h>
  18 #include <internal/hashtable.h>
  19 #include "fuzzer.h"
  20
  21 /*
  22  * Make the key space very small here to make lookups
  23  * easy to predict for the purposes of validation
  24  * A two byte key gives us 65536 possible entries
  25  * so we can allocate a flat table to compare to
  26  */
  27 HT_START_KEY_DEFN(fuzzer_key)
  28 HT_DEF_KEY_FIELD(fuzzkey, uint16_t)
  29 HT_END_KEY_DEFN(FUZZER_KEY)
  30
  31 #define FZ_FLAG_ALLOCATED (1 << 0)
  32 typedef struct fuzzer_value_st {
  33     uint64_t flags;
  34     uint64_t value;
  35 } FUZZER_VALUE;
  36
  37 IMPLEMENT_HT_VALUE_TYPE_FNS(FUZZER_VALUE, fz, static)
  38
  39 static size_t skipped_values = 0;
  40 static size_t inserts = 0;
  41 static size_t replacements = 0;
  42 static size_t deletes = 0;
  43 static size_t flushes = 0;
  44 static size_t lookups = 0;
  45 static size_t foreaches = 0;
  46 static size_t filters = 0;
  47 static int valfound;
  48
  49 static FUZZER_VALUE *prediction_table = NULL;
  50 static HT *fuzzer_table = NULL;
  51
  52 /*
  53  * Operational values
  54  */
  55 #define OP_INSERT  0
  56 #define OP_DELETE  1
  57 #define OP_LOOKUP  2
  58 #define OP_FLUSH   3
  59 #define OP_FOREACH 4
  60 #define OP_FILTER  5
  61 #define OP_END     6
  62
  63 #define OP_MASK 0x3f
  64 #define INSERT_REPLACE_MASK 0x40
  65 #define OPERATION(x) (((x) & OP_MASK) % OP_END)
  66 #define IS_REPLACE(x) ((x) & INSERT_REPLACE_MASK)
  67
  68 static int table_iterator(HT_VALUE *v, void *arg)
  69 {
  70     uint16_t keyval = (*(uint16_t *)arg);
  71     FUZZER_VALUE *f = ossl_ht_fz_FUZZER_VALUE_from_value(v);
  72
  73     if (f != NULL && f == &prediction_table[keyval]) {
  74         valfound = 1;
  75         return 0;
  76     }
  77
  78     return 1;
  79 }
  80
  81 static int filter_iterator(HT_VALUE *v, void *arg)
  82 {
  83     uint16_t keyval = (*(uint16_t *)arg);
  84     FUZZER_VALUE *f = ossl_ht_fz_FUZZER_VALUE_from_value(v);
  85
  86     if (f != NULL && f == &prediction_table[keyval])
  87         return 1;
  88
  89     return 0;
  90 }
  91
  92 static void fuzz_free_cb(HT_VALUE *v)
  93 {
  94     FUZZER_VALUE *f = ossl_ht_fz_FUZZER_VALUE_from_value(v);
  95
  96     if (f != NULL)
  97         f->flags &= ~FZ_FLAG_ALLOCATED;
  98 }
  99
 100 int FuzzerInitialize(int *argc, char ***argv)
 101 {
 102     HT_CONFIG fuzz_conf = {NULL, fuzz_free_cb, NULL, 0};
 103
 104     OPENSSL_init_crypto(OPENSSL_INIT_LOAD_CRYPTO_STRINGS, NULL);
 105     ERR_clear_error();
 106     prediction_table = OPENSSL_zalloc(sizeof(FUZZER_VALUE) * 65537);
 107     if (prediction_table == NULL)
 108         return -1;
 109     fuzzer_table = ossl_ht_new(&fuzz_conf);
 110     if (fuzzer_table == NULL) {
 111         OPENSSL_free(prediction_table);
 112         return -1;
 113     }
 114
 115     return 0;
 116 }
 117
 118 int FuzzerTestOneInput(const uint8_t *buf, size_t len)
 119 {
 120     uint8_t op_flags;
 121     uint16_t keyval;
 122     int rc;
 123     int rc_prediction = 1;
 124     size_t i;
 125     FUZZER_VALUE *valptr, *lval;
 126     FUZZER_KEY key;
 127     HT_VALUE *v = NULL;
 128     HT_VALUE tv;
 129     HT_VALUE_LIST *htvlist;
 130
 131     /*
 132      * We need at least 11 bytes to be able to do anything here
 133      * 1 byte to detect the operation to preform, 2 bytes
 134      * for the lookup key, and 8 bytes of value
 135      */
 136     if (len < 11) {
 137         skipped_values++;
 138         return -1;
 139     }
 140
 141     /*
 142      * parse out our operation flags and key
 143      */
 144     op_flags = buf[0];
 145     memcpy(&keyval, &buf[1], sizeof(uint16_t));
 146
 147     /*
 148      * Initialize our key
 149      */
 150     HT_INIT_KEY(&key);
 151
 152     /*
 153      * Now do our operation
 154      */
 155     switch(OPERATION(op_flags)) {
 156     case OP_INSERT:
 157         valptr = &prediction_table[keyval];
 158
 159         /* reset our key */
 160         HT_KEY_RESET(&key);
 161
 162         /* set the proper key value */
 163         HT_SET_KEY_FIELD(&key, fuzzkey, keyval);
 164
 165         /* lock the table */
 166         ossl_ht_write_lock(fuzzer_table);
 167
 168         /*
 169          * If the value to insert is already allocated
 170          * then we expect a conflict in the insert
 171          * i.e. we predict a return code of 0 instead
 172          * of 1. On replacement, we expect it to succeed
 173          * always
 174          */
 175         if (valptr->flags & FZ_FLAG_ALLOCATED) {
 176             if (!IS_REPLACE(op_flags))
 177                 rc_prediction = 0;
 178         }
 179
 180         memcpy(&valptr->value, &buf[3], sizeof(uint64_t));
 181         /*
 182          * do the insert/replace
 183          */
 184         if (IS_REPLACE(op_flags))
 185             rc = ossl_ht_fz_FUZZER_VALUE_insert(fuzzer_table, TO_HT_KEY(&key),
 186                                                 valptr, &lval);
 187         else
 188             rc = ossl_ht_fz_FUZZER_VALUE_insert(fuzzer_table, TO_HT_KEY(&key),
 189                                                 valptr, NULL);
 190
 191         /*
 192          * mark the entry as being allocated
 193          */
 194         valptr->flags |= FZ_FLAG_ALLOCATED;
 195
 196         /*
 197          * unlock the table
 198          */
 199         ossl_ht_write_unlock(fuzzer_table);
 200
 201         /*
 202          * Now check to make sure we did the right thing
 203          */
 204         OPENSSL_assert(rc == rc_prediction);
 205
 206         /*
 207          * successful insertion if there wasn't a conflict
 208          */
 209         if (rc_prediction == 1)
 210             IS_REPLACE(op_flags) ? replacements++ : inserts++;
 211         break;
 212
 213     case OP_DELETE:
 214         valptr = &prediction_table[keyval];
 215
 216         /* reset our key */
 217         HT_KEY_RESET(&key);
 218
 219         /* set the proper key value */
 220         HT_SET_KEY_FIELD(&key, fuzzkey, keyval);
 221
 222         /* lock the table */
 223         ossl_ht_write_lock(fuzzer_table);
 224
 225         /*
 226          * If the value to delete is not already allocated
 227          * then we expect a miss in the delete
 228          * i.e. we predict a return code of 0 instead
 229          * of 1
 230          */
 231         if (!(valptr->flags & FZ_FLAG_ALLOCATED))
 232             rc_prediction = 0;
 233
 234         /*
 235          * do the delete
 236          */
 237         rc = ossl_ht_delete(fuzzer_table, TO_HT_KEY(&key));
 238
 239         /*
 240          * unlock the table
 241          */
 242         ossl_ht_write_unlock(fuzzer_table);
 243
 244         /*
 245          * Now check to make sure we did the right thing
 246          */
 247         OPENSSL_assert(rc == rc_prediction);
 248
 249         /*
 250          * once the unlock is done, the table rcu will have synced
 251          * meaning the free function has run, so we can confirm now
 252          * that the valptr is no longer allocated
 253          */
 254         OPENSSL_assert(!(valptr->flags & FZ_FLAG_ALLOCATED));
 255
 256         /*
 257          * successful deletion if there wasn't a conflict
 258          */
 259         if (rc_prediction == 1)
 260             deletes++;
 261
 262         break;
 263
 264     case OP_LOOKUP:
 265         valptr = &prediction_table[keyval];
 266         lval = NULL;
 267
 268         /* reset our key */
 269         HT_KEY_RESET(&key);
 270
 271         /* set the proper key value */
 272         HT_SET_KEY_FIELD(&key, fuzzkey, keyval);
 273
 274         /* lock the table for reading */
 275         ossl_ht_read_lock(fuzzer_table);
 276
 277         /*
 278          * If the value to find is not already allocated
 279          * then we expect a miss in the lookup
 280          * i.e. we predict a return code of NULL instead
 281          * of a pointer
 282          */
 283         if (!(valptr->flags & FZ_FLAG_ALLOCATED))
 284             valptr = NULL;
 285
 286         /*
 287          * do the lookup
 288          */
 289         lval = ossl_ht_fz_FUZZER_VALUE_get(fuzzer_table, TO_HT_KEY(&key), &v);
 290
 291         /*
 292          * unlock the table
 293          */
 294         ossl_ht_read_unlock(fuzzer_table);
 295
 296         /*
 297          * Now check to make sure we did the right thing
 298          */
 299         OPENSSL_assert(lval == valptr);
 300
 301         /*
 302          * if we expect a positive lookup, make sure that
 303          * we can use the _type and to_value functions
 304          */
 305         if (valptr != NULL) {
 306             OPENSSL_assert(ossl_ht_fz_FUZZER_VALUE_type(v) == 1);
 307
 308             v = ossl_ht_fz_FUZZER_VALUE_to_value(lval, &tv);
 309             OPENSSL_assert(v->value == lval);
 310         }
 311
 312         /*
 313          * successful lookup if we didn't expect a miss
 314          */
 315         if (valptr != NULL)
 316             lookups++;
 317
 318         break;
 319
 320     case OP_FLUSH:
 321         /*
 322          * only flush the table rarely
 323          */
 324         if ((flushes % 100000) != 1) {
 325             skipped_values++;
 326             flushes++;
 327             return 0;
 328         }
 329
 330         /*
 331          * lock the table
 332          */
 333         ossl_ht_write_lock(fuzzer_table);
 334         ossl_ht_flush(fuzzer_table);
 335         ossl_ht_write_unlock(fuzzer_table);
 336
 337         /*
 338          * now check to make sure everything is free
 339          */
 340        for (i = 0; i < USHRT_MAX; i++)
 341             OPENSSL_assert((prediction_table[i].flags & FZ_FLAG_ALLOCATED) == 0);
 342
 343         /* good flush */
 344         flushes++;
 345         break;
 346
 347     case OP_FOREACH:
 348         valfound = 0;
 349         valptr = &prediction_table[keyval];
 350
 351         rc_prediction = 0;
 352         if (valptr->flags & FZ_FLAG_ALLOCATED)
 353             rc_prediction = 1;
 354
 355         ossl_ht_foreach_until(fuzzer_table, table_iterator, &keyval);
 356
 357         OPENSSL_assert(valfound == rc_prediction);
 358
 359         foreaches++;
 360         break;
 361
 362     case OP_FILTER:
 363         valptr = &prediction_table[keyval];
 364
 365         rc_prediction = 0;
 366         if (valptr->flags & FZ_FLAG_ALLOCATED)
 367             rc_prediction = 1;
 368
 369         htvlist = ossl_ht_filter(fuzzer_table, 1, filter_iterator, &keyval);
 370
 371         OPENSSL_assert(htvlist->list_len == (size_t)rc_prediction);
 372
 373         ossl_ht_value_list_free(htvlist);
 374         filters++;
 375         break;
 376
 377     default:
 378         return -1;
 379     }
 380
 381     return 0;
 382 }
 383
 384 void FuzzerCleanup(void)
 385 {
 386     ossl_ht_free(fuzzer_table);
 387     OPENSSL_free(prediction_table);
 388     OPENSSL_cleanup();
 389 }