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
table_iterator(HT_VALUE * v,void * arg)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
filter_iterator(HT_VALUE * v,void * arg)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
fuzz_free_cb(HT_VALUE * v)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
FuzzerInitialize(int * argc,char *** argv)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
FuzzerTestOneInput(const uint8_t * buf,size_t len)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
FuzzerCleanup(void)388 void FuzzerCleanup(void)
389 {
390 ossl_ht_free(fuzzer_table);
391 OPENSSL_free(prediction_table);
392 OPENSSL_cleanup();
393 }
394
