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