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};
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 /*
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
FuzzerCleanup(void)384 void FuzzerCleanup(void)
385 {
386 ossl_ht_free(fuzzer_table);
387 OPENSSL_free(prediction_table);
388 OPENSSL_cleanup();
389 }
390
