Line data Source code
1 : #if !FD_HAS_HOSTED
2 : #error "This target requires FD_HAS_HOSTED"
3 : #endif
4 :
5 : #include <assert.h>
6 : #include <stdio.h>
7 : #include <stdlib.h>
8 :
9 : #include "../../util/fd_util.h"
10 : #include "../../util/sanitize/fd_fuzz.h"
11 : #include "fd_bmtree.h"
12 :
13 : #define MAX_LEAF_CNT (256UL)
14 : #define MAX_DEPTH (9UL)
15 : #define MEMORY_SZ (70UL*1024UL*1024UL)
16 :
17 : static uchar memory1[ MEMORY_SZ ];
18 : static uchar memory2[ MEMORY_SZ ];
19 : static uchar inc_proof[ 32UL * ( MAX_DEPTH - 1UL ) ];
20 :
21 : int
22 : LLVMFuzzerInitialize( int * pargc,
23 18 : char *** pargv ) {
24 : /* Set up shell without signal handlers */
25 18 : putenv( "FD_LOG_BACKTRACE=0" );
26 18 : fd_boot( pargc, pargv );
27 18 : atexit( fd_halt );
28 18 : fd_log_level_core_set(3); /* crash on warning log */
29 18 : return 0;
30 18 : }
31 :
32 : static int
33 : fuzz_bmtree( fd_bmtree_node_t const * leafs,
34 : ulong leaf_cnt,
35 : ulong hash_sz,
36 0 : ulong prefix_sz ) {
37 :
38 : /* figure out the footprint needed given the leaf_cnt */
39 0 : ulong depth = fd_bmtree_depth( leaf_cnt );
40 :
41 0 : if( FD_UNLIKELY( depth > MAX_DEPTH ) ) return -1;
42 0 : ulong footprint = fd_bmtree_commit_footprint( depth );
43 :
44 : /* check that we have enough memory, check for overflows along the way */
45 0 : uchar * memory_start = memory1;
46 0 : uchar * first_tree_end = memory_start+footprint;
47 0 : if( FD_UNLIKELY( first_tree_end<memory_start || (ulong)first_tree_end<footprint ) ) {
48 0 : return -1;
49 0 : }
50 :
51 0 : uchar * second_tree_start = (uchar *)fd_ulong_align_up( (ulong)first_tree_end, FD_BMTREE_COMMIT_ALIGN );
52 0 : if( FD_UNLIKELY( second_tree_start<first_tree_end ) ) {
53 0 : printf("FD_UNLIKELY( second_tree_start<first_tree_end )\n");
54 0 : return -1;
55 0 : }
56 :
57 0 : uchar * memory_end = second_tree_start+footprint;
58 0 : if( FD_UNLIKELY( memory_end<second_tree_start || (ulong)memory_end<footprint ) ) {
59 0 : printf("FD_UNLIKELY( memory_end<second_tree_start || memory_end<footprint )\n");
60 0 : return -1;
61 0 : }
62 :
63 0 : ulong memory_required = (ulong) (memory_end - memory_start);
64 0 : if( FD_UNLIKELY( memory_required > MEMORY_SZ ) ) {
65 0 : printf("FD_UNLIKELY( memory_required < MEMORY_SZ )\n");
66 0 : printf("%lu < %lu\n", memory_required, MEMORY_SZ);
67 0 : return -1;
68 0 : }
69 :
70 : /* create first tree from leafs */
71 0 : fd_bmtree_commit_t * tree = fd_bmtree_commit_init( memory1, hash_sz, prefix_sz, 0UL );
72 0 : assert( tree );
73 :
74 : /* no leaf has been appended thus far */
75 0 : assert( 0UL == fd_bmtree_commit_leaf_cnt( tree ) );
76 :
77 : /* append all leafs */
78 0 : assert( tree == fd_bmtree_commit_append( tree, leafs, leaf_cnt ) );
79 :
80 : /* tree has the expected amount of leafs */
81 0 : assert( leaf_cnt == fd_bmtree_commit_leaf_cnt( tree ) );
82 :
83 : /* commit to the tree */
84 0 : uchar * root_1 = fd_bmtree_commit_fini( tree );
85 0 : assert( root_1 );
86 :
87 0 : assert( leaf_cnt == fd_bmtree_commit_leaf_cnt( tree ) );
88 :
89 : /* create second tree from proofs */
90 0 : fd_bmtree_commit_t * tree2 = fd_bmtree_commit_init( memory2, hash_sz, prefix_sz, depth );
91 0 : assert( tree2 );
92 :
93 0 : fd_bmtree_node_t proof_root_1[1];
94 0 : fd_bmtree_node_t proof_root_2[1];
95 0 : fd_bmtree_node_t leaf[1];
96 :
97 0 : for( ulong i=0UL; i<leaf_cnt; i++ ) {
98 0 : fd_memcpy( leaf, leafs+i, sizeof( fd_bmtree_node_t ) );
99 :
100 0 : int res = fd_bmtree_get_proof( tree, inc_proof, i );
101 0 : if ( res == -1 ) {
102 0 : FD_FUZZ_MUST_BE_COVERED;
103 0 : return 0;
104 0 : }
105 :
106 0 : assert( proof_root_1 == fd_bmtree_from_proof( leaf, i, proof_root_1, inc_proof, depth-1UL, hash_sz, prefix_sz ) );
107 :
108 0 : assert( fd_memeq( root_1, proof_root_1, hash_sz ) );
109 :
110 0 : assert( fd_bmtree_commitp_insert_with_proof( tree2, i, leaf, inc_proof, depth-1UL, proof_root_2 ) );
111 :
112 0 : assert( fd_memeq( root_1, proof_root_2, hash_sz ) );
113 :
114 0 : if( FD_LIKELY( leaf_cnt>1UL ) ) {
115 0 : FD_FUZZ_MUST_BE_COVERED;
116 0 : inc_proof[ 1 ]++; /* Corrupt the proof */
117 0 : assert( proof_root_1 == fd_bmtree_from_proof( leaf, i, proof_root_1, inc_proof, depth-1UL, hash_sz, prefix_sz ) );
118 :
119 0 : assert( !fd_memeq( root_1, proof_root_1, hash_sz ) );
120 :
121 0 : assert( !fd_bmtree_commitp_insert_with_proof( tree2, i, leaf, inc_proof, depth-1UL, NULL ) );
122 :
123 0 : inc_proof[ 1 ]--;
124 0 : } /* Otherwise the proof is empty, so there's nothing to corrupt */
125 :
126 0 : root_1[ 1 ]++; /* Corrupt the root */
127 0 : assert( proof_root_1 == fd_bmtree_from_proof( leaf, i, proof_root_1, inc_proof, depth-1UL, hash_sz, prefix_sz ) );
128 :
129 0 : assert( !fd_memeq( root_1, proof_root_1, hash_sz ) );
130 :
131 0 : root_1[ 1 ]--;
132 :
133 0 : leaf->hash[ 1 ]++; /* Corrupt the leaf */
134 0 : assert( proof_root_1 == fd_bmtree_from_proof( leaf, i, proof_root_1, inc_proof, depth-1UL, hash_sz, prefix_sz ) );
135 :
136 0 : assert( !fd_memeq( root_1, proof_root_1, hash_sz ) );
137 :
138 0 : assert( !fd_bmtree_commitp_insert_with_proof( tree2, i, leaf, inc_proof, depth-1UL, NULL ) );
139 :
140 0 : leaf->hash[ 1 ]--;
141 0 : }
142 0 : uchar * root_2 = fd_bmtree_commitp_fini( tree2, leaf_cnt );
143 0 : assert( root_2 );
144 :
145 0 : assert( fd_memeq( root_1, root_2, hash_sz ) );
146 :
147 0 : return 0;
148 0 : }
149 :
150 : struct bmtree_test {
151 : ulong leaf_cnt;
152 : uchar leaf_hashes[ ];
153 : };
154 : typedef struct bmtree_test bmtree_test_t;
155 :
156 : int
157 : LLVMFuzzerTestOneInput( uchar const * data,
158 : ulong size ) {
159 : if( FD_UNLIKELY( size<sizeof( bmtree_test_t ) ) ) return -1;
160 : bmtree_test_t * const test = ( bmtree_test_t * const ) data;
161 : ulong leaf_cnt = test->leaf_cnt % MAX_LEAF_CNT + 1UL;
162 :
163 : if( FD_UNLIKELY( size<sizeof( bmtree_test_t )+leaf_cnt*sizeof( fd_bmtree_node_t ) ) ) return -1;
164 : fd_bmtree_node_t const * leafs = ( fd_bmtree_node_t const * ) test->leaf_hashes;
165 :
166 : int result = fuzz_bmtree( leafs, leaf_cnt, 32UL, FD_BMTREE_SHORT_PREFIX_SZ );
167 : if ( result != 0 ) {
168 : return result;
169 : }
170 :
171 : result = fuzz_bmtree( leafs, leaf_cnt, 20UL, FD_BMTREE_LONG_PREFIX_SZ );
172 :
173 : FD_FUZZ_MUST_BE_COVERED;
174 : return result;
175 : }
|
