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, 1}; 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 perform, 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 if (rc == -1) 192 /* failed to grow the hash table due to too many collisions */ 193 break; 194 195 /* 196 * mark the entry as being allocated 197 */ 198 valptr->flags |= FZ_FLAG_ALLOCATED; 199 200 /* 201 * unlock the table 202 */ 203 ossl_ht_write_unlock(fuzzer_table); 204 205 /* 206 * Now check to make sure we did the right thing 207 */ 208 OPENSSL_assert(rc == rc_prediction); 209 210 /* 211 * successful insertion if there wasn't a conflict 212 */ 213 if (rc_prediction == 1) 214 IS_REPLACE(op_flags) ? replacements++ : inserts++; 215 break; 216 217 case OP_DELETE: 218 valptr = &prediction_table[keyval]; 219 220 /* reset our key */ 221 HT_KEY_RESET(&key); 222 223 /* set the proper key value */ 224 HT_SET_KEY_FIELD(&key, fuzzkey, keyval); 225 226 /* lock the table */ 227 ossl_ht_write_lock(fuzzer_table); 228 229 /* 230 * If the value to delete is not already allocated 231 * then we expect a miss in the delete 232 * i.e. we predict a return code of 0 instead 233 * of 1 234 */ 235 if (!(valptr->flags & FZ_FLAG_ALLOCATED)) 236 rc_prediction = 0; 237 238 /* 239 * do the delete 240 */ 241 rc = ossl_ht_delete(fuzzer_table, TO_HT_KEY(&key)); 242 243 /* 244 * unlock the table 245 */ 246 ossl_ht_write_unlock(fuzzer_table); 247 248 /* 249 * Now check to make sure we did the right thing 250 */ 251 OPENSSL_assert(rc == rc_prediction); 252 253 /* 254 * once the unlock is done, the table rcu will have synced 255 * meaning the free function has run, so we can confirm now 256 * that the valptr is no longer allocated 257 */ 258 OPENSSL_assert(!(valptr->flags & FZ_FLAG_ALLOCATED)); 259 260 /* 261 * successful deletion if there wasn't a conflict 262 */ 263 if (rc_prediction == 1) 264 deletes++; 265 266 break; 267 268 case OP_LOOKUP: 269 valptr = &prediction_table[keyval]; 270 lval = NULL; 271 272 /* reset our key */ 273 HT_KEY_RESET(&key); 274 275 /* set the proper key value */ 276 HT_SET_KEY_FIELD(&key, fuzzkey, keyval); 277 278 /* lock the table for reading */ 279 ossl_ht_read_lock(fuzzer_table); 280 281 /* 282 * If the value to find is not already allocated 283 * then we expect a miss in the lookup 284 * i.e. we predict a return code of NULL instead 285 * of a pointer 286 */ 287 if (!(valptr->flags & FZ_FLAG_ALLOCATED)) 288 valptr = NULL; 289 290 /* 291 * do the lookup 292 */ 293 lval = ossl_ht_fz_FUZZER_VALUE_get(fuzzer_table, TO_HT_KEY(&key), &v); 294 295 /* 296 * unlock the table 297 */ 298 ossl_ht_read_unlock(fuzzer_table); 299 300 /* 301 * Now check to make sure we did the right thing 302 */ 303 OPENSSL_assert(lval == valptr); 304 305 /* 306 * if we expect a positive lookup, make sure that 307 * we can use the _type and to_value functions 308 */ 309 if (valptr != NULL) { 310 OPENSSL_assert(ossl_ht_fz_FUZZER_VALUE_type(v) == 1); 311 312 v = ossl_ht_fz_FUZZER_VALUE_to_value(lval, &tv); 313 OPENSSL_assert(v->value == lval); 314 } 315 316 /* 317 * successful lookup if we didn't expect a miss 318 */ 319 if (valptr != NULL) 320 lookups++; 321 322 break; 323 324 case OP_FLUSH: 325 /* 326 * only flush the table rarely 327 */ 328 if ((flushes % 100000) != 1) { 329 skipped_values++; 330 flushes++; 331 return 0; 332 } 333 334 /* 335 * lock the table 336 */ 337 ossl_ht_write_lock(fuzzer_table); 338 ossl_ht_flush(fuzzer_table); 339 ossl_ht_write_unlock(fuzzer_table); 340 341 /* 342 * now check to make sure everything is free 343 */ 344 for (i = 0; i < USHRT_MAX; i++) 345 OPENSSL_assert((prediction_table[i].flags & FZ_FLAG_ALLOCATED) == 0); 346 347 /* good flush */ 348 flushes++; 349 break; 350 351 case OP_FOREACH: 352 valfound = 0; 353 valptr = &prediction_table[keyval]; 354 355 rc_prediction = 0; 356 if (valptr->flags & FZ_FLAG_ALLOCATED) 357 rc_prediction = 1; 358 359 ossl_ht_foreach_until(fuzzer_table, table_iterator, &keyval); 360 361 OPENSSL_assert(valfound == rc_prediction); 362 363 foreaches++; 364 break; 365 366 case OP_FILTER: 367 valptr = &prediction_table[keyval]; 368 369 rc_prediction = 0; 370 if (valptr->flags & FZ_FLAG_ALLOCATED) 371 rc_prediction = 1; 372 373 htvlist = ossl_ht_filter(fuzzer_table, 1, filter_iterator, &keyval); 374 375 OPENSSL_assert(htvlist->list_len == (size_t)rc_prediction); 376 377 ossl_ht_value_list_free(htvlist); 378 filters++; 379 break; 380 381 default: 382 return -1; 383 } 384 385 return 0; 386 } 387 388 void FuzzerCleanup(void) 389 { 390 ossl_ht_free(fuzzer_table); 391 OPENSSL_free(prediction_table); 392 OPENSSL_cleanup(); 393 } 394