Line data    Source code

       1             : #if !FD_HAS_HOSTED
       2             : #error "This target requires FD_HAS_HOSTED"
       3             : #endif
       4             : 
       5             : #include <stdio.h>
       6             : #include <stdlib.h>
       7             : 
       8             : #include "../../util/fd_util.h"
       9             : #include "../../util/sanitize/fd_fuzz.h"
      10             : #include "fd_reedsol.h"
      11             : 
      12             : int
      13             : LLVMFuzzerInitialize( int  *   argc,
      14          18 :                       char *** argv ) {
      15             :   /* Set up shell without signal handlers */
      16          18 :   putenv( "FD_LOG_BACKTRACE=0" );
      17          18 :   fd_boot( argc, argv );
      18          18 :   atexit( fd_halt );
      19          18 :   return 0;
      20          18 : }
      21             : 
      22             : #define SHRED_SZ_MIN ( 32UL )
      23             : #define SHRED_SZ_MAX ( 63UL )
      24             : 
      25             : struct reedsol_test {
      26             :   ulong shred_sz;
      27             :   ulong data_shred_cnt;
      28             :   ulong parity_shred_cnt;
      29             :   ulong erased_shred_cnt;
      30             :   ulong corrupt_shred_idx;
      31             :   uchar data[ ];
      32             : };
      33             : typedef struct reedsol_test reedsol_test_t;
      34             : 
      35             : int
      36             : LLVMFuzzerTestOneInput( uchar const * data,
      37             :                         ulong         size ) {
      38             :   if( FD_UNLIKELY( size<sizeof( reedsol_test_t ) ) ) return -1;
      39             :   reedsol_test_t const * test = ( reedsol_test_t const * ) data;
      40             : 
      41             :   fd_rng_t _rng[1];
      42             :   fd_rng_t * rng = fd_rng_join( fd_rng_new( _rng, 0U, 0UL ) );
      43             : 
      44             :   uchar mem[ FD_REEDSOL_FOOTPRINT ] __attribute__((aligned(FD_REEDSOL_ALIGN)));
      45             : 
      46             :   uchar const * data_shreds = test->data;
      47             :   uchar parity_shreds[ SHRED_SZ_MAX * FD_REEDSOL_PARITY_SHREDS_MAX ];
      48             :   uchar recovered_shreds[ SHRED_SZ_MAX * ( FD_REEDSOL_PARITY_SHREDS_MAX+1UL ) ];
      49             :   
      50             :   uchar const * d[ FD_REEDSOL_DATA_SHREDS_MAX   ];
      51             :   uchar *       p[ FD_REEDSOL_PARITY_SHREDS_MAX ];
      52             :   uchar *       r[ FD_REEDSOL_PARITY_SHREDS_MAX+1UL ];
      53             :   uchar const * erased_truth[ FD_REEDSOL_PARITY_SHREDS_MAX+1UL ];
      54             : 
      55             :   ulong shred_sz = SHRED_SZ_MIN + test->shred_sz % ( SHRED_SZ_MAX-SHRED_SZ_MIN+1UL );
      56             :   ulong d_cnt = test->data_shred_cnt % FD_REEDSOL_DATA_SHREDS_MAX + 1UL;
      57             :   ulong p_cnt = test->parity_shred_cnt % FD_REEDSOL_PARITY_SHREDS_MAX + 1UL;
      58             :   ulong e_cnt = test->erased_shred_cnt % ( p_cnt+2UL );
      59             :   ulong corrupt_idx = test->corrupt_shred_idx % ( d_cnt+p_cnt );
      60             : 
      61             :   if( FD_UNLIKELY( size < sizeof( reedsol_test_t ) + shred_sz*d_cnt ) ) return -1;
      62             : 
      63             :   for( ulong i=0UL; i<d_cnt; i++ )  d[ i ] = data_shreds + shred_sz*i;
      64             :   for( ulong i=0UL; i<p_cnt; i++ )  p[ i ] = parity_shreds + shred_sz*i;
      65             :   for( ulong i=0UL; i<e_cnt; i++ )  r[ i ] = recovered_shreds + shred_sz*i;
      66             : 
      67             :   fd_reedsol_t * rs = fd_reedsol_encode_init( mem, shred_sz );
      68             :   for( ulong i=0UL; i<d_cnt; i++ ) fd_reedsol_encode_add_data_shred(   rs, d[ i ] );
      69             :   for( ulong i=0UL; i<p_cnt; i++ ) fd_reedsol_encode_add_parity_shred( rs, p[ i ] );
      70             :   fd_reedsol_encode_fini( rs );
      71             : 
      72             :   /* Use reservoir sampling to select exactly e_cnt of the shreds
      73             :      to erased */
      74             :   ulong erased_cnt = 0UL;
      75             :   rs = fd_reedsol_recover_init( mem, shred_sz );
      76             :   for( ulong i=0UL; i<d_cnt; i++ ) {
      77             :     /* Erase with probability:
      78             :        (e_cnt - erased_cnt)/(d_cnt + p_cnt - i) */
      79             :     if( fd_rng_ulong_roll( rng, d_cnt+p_cnt-i ) < (e_cnt-erased_cnt) ) {
      80             :       erased_truth[ erased_cnt ] = d[ i ];
      81             :       fd_reedsol_recover_add_erased_shred(    rs, 1, r[ erased_cnt++ ] );
      82             :     } else fd_reedsol_recover_add_rcvd_shred( rs, 1, d[ i ] );
      83             :   }
      84             :   for( ulong i=0UL; i<p_cnt; i++ ) {
      85             :     if( fd_rng_ulong_roll( rng, p_cnt-i ) < (e_cnt-erased_cnt) ) {
      86             :       erased_truth[ erased_cnt ] = p[ i ];
      87             :       fd_reedsol_recover_add_erased_shred(    rs, 0, r[ erased_cnt++ ] );
      88             :     } else fd_reedsol_recover_add_rcvd_shred( rs, 0, p[ i ] );
      89             :   }
      90             : 
      91             :   if( FD_UNLIKELY( erased_cnt!=e_cnt ) ) {
      92             :      /* If this fails, the test is wrong. */
      93             :      __builtin_trap();
      94             :   }
      95             :   int retval = fd_reedsol_recover_fini( rs );
      96             : 
      97             :   if( FD_UNLIKELY( e_cnt>p_cnt ) ) {
      98             :     if( FD_UNLIKELY( retval!=FD_REEDSOL_ERR_PARTIAL ) ) {
      99             :       __builtin_trap();
     100             :     }
     101             :   } else {
     102             :     if( FD_UNLIKELY( FD_REEDSOL_SUCCESS!=retval ) ) {
     103             :       __builtin_trap();
     104             :     }
     105             : 
     106             :     for( ulong i=0UL; i<e_cnt; i++ ) {
     107             :       if( FD_UNLIKELY( memcmp( erased_truth[ i ], r[ i ], shred_sz ) ) ) {
     108             :         __builtin_trap();
     109             :       }
     110             :     }
     111             :   }
     112             : 
     113             :   /* Corrupt one shred and make sure it gets caught */
     114             :   uchar corrupt_shred[ SHRED_SZ_MAX ];
     115             :   ulong byte_idx = fd_rng_ulong_roll( rng, shred_sz );
     116             :   if( corrupt_idx<d_cnt ) {
     117             :     fd_memcpy( corrupt_shred, d[ corrupt_idx ], shred_sz );
     118             :     corrupt_shred[ byte_idx ] ^= (uchar)1;
     119             :     d[ corrupt_idx ] = &corrupt_shred[0];
     120             :   } else p[ corrupt_idx-d_cnt ][ byte_idx ] ^= (uchar)1;
     121             : 
     122             :   rs = fd_reedsol_recover_init( mem, shred_sz );
     123             :   for( ulong i=0UL; i<d_cnt; i++ ) fd_reedsol_recover_add_rcvd_shred( rs, 1, d[ i ] );
     124             :   for( ulong i=0UL; i<p_cnt; i++ ) fd_reedsol_recover_add_rcvd_shred( rs, 0, p[ i ] );
     125             : 
     126             :   if( FD_UNLIKELY( FD_REEDSOL_ERR_CORRUPT!=fd_reedsol_recover_fini( rs ) ) ) {
     127             :     __builtin_trap();
     128             :   }
     129             : 
     130             :   if( corrupt_idx<d_cnt )  d[ corrupt_idx       ]              = data_shreds + shred_sz*corrupt_idx;
     131             :   else                     p[ corrupt_idx-d_cnt ][ byte_idx ] ^= (uchar)1;
     132             : 
     133             :   fd_rng_delete( fd_rng_leave( rng ) );
     134             :   FD_FUZZ_MUST_BE_COVERED;
     135             :   return 0;
     136             : }