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