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