VirtualBox

Changeset 77650 in vbox


Ignore:
Timestamp:
Mar 11, 2019 12:48:14 PM (6 years ago)
Author:
vboxsync
Message:

Runtime/fuzz: Add mutators to change possible integers to some interesting ones and to crossover two different mutations. Cache the generated data up to a certain threshold to avoid alaways recreating the whole mutation

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/Runtime/common/fuzz/fuzz.cpp

    r77564 r77650  
    3535#include <iprt/assert.h>
    3636#include <iprt/avl.h>
     37#include <iprt/critsect.h>
    3738#include <iprt/ctype.h>
    3839#include <iprt/dir.h>
    … …  
    6768
    6869/**
     70 * Mutator class.
     71 */
     72typedef enum RTFUZZMUTATORCLASS
     73{
     74    /** Invalid class, do not use. */
     75    RTFUZZMUTATORCLASS_INVALID = 0,
     76    /** Mutator operates on single bits. */
     77    RTFUZZMUTATORCLASS_BITS,
     78    /** Mutator operates on bytes (single or multiple). */
     79    RTFUZZMUTATORCLASS_BYTES,
     80    /** Mutator interpretes data as integers and operates on them. */
     81    RTFUZZMUTATORCLASS_INTEGERS,
     82    /** Mutator uses multiple mutations to create new mutations. */
     83    RTFUZZMUTATORCLASS_MUTATORS,
     84    /** 32bit hack. */
     85    RTFUZZMUTATORCLASS_32BIT_HACK = 0x7fffffff
     86} RTFUZZMUTATORCLASS;
     87
     88
     89/**
    6990 * Mutator preparation callback.
    7091 *
    … …  
    140161    /** Mutator index. */
    141162    uint32_t                    uMutator;
     163    /** Mutator class. */
     164    RTFUZZMUTATORCLASS          enmClass;
    142165    /** Additional flags for the mutator, controlling the behavior. */
    143166    uint64_t                    fFlags;
    … …  
    172195    /** The AVL tree core. */
    173196    AVLU64NODECORE              Core;
     197    /** The list node if the mutation has the mutated
     198     * data allocated. */
     199    RTLISTNODE                  NdAlloc;
    174200    /** Magic identifying this structure. */
    175201    uint32_t                    u32Magic;
    … …  
    178204    /** The fuzzer this mutation belongs to. */
    179205    PRTFUZZCTXINT               pFuzzer;
    180     /** Parent mutation (reference is held), NULL means root or original data. */
    181     PCRTFUZZMUTATION            pMutationParent;
     206    /** Parent mutation (no reference is held), NULL means root or original data. */
     207    PRTFUZZMUTATION             pMutationParent;
    182208    /** Mutation level. */
    183209    uint32_t                    iLvl;
    … …  
    190216    /** Size of the mutation dependent data. */
    191217    size_t                      cbMutation;
     218    /** Size allocated for the input. */
     219    size_t                      cbAlloc;
     220    /** Pointer to the input data if created. */
     221    void                        *pvInput;
    192222    /** Flag whether the mutation is contained in the tree of the context. */
    193223    bool                        fInTree;
     224    /** Flag whether the mutation input data is cached. */
     225    bool                        fCached;
    194226    /** Mutation dependent data, variable in size. */
    195227    uint8_t                     abMutation[1];
    … …  
    216248        struct
    217249        {
    218             /** Size to allocate initially. */
    219             size_t              cbAlloc;
    220             /** Input data size. */
    221             size_t              cbInput;
    222250            /** Pointer to the input data if created. */
    223251            void                *pvInput;
    … …  
    230258        } Stream;
    231259    } u;
    232     /** Array holding all the individual mutations, variable in size. */
    233     PCRTFUZZMUTATION            apMutations[1];
    234260} RTFUZZINPUTINT;
    235261/** Pointer to the internal input state. */
    … …  
    266292    /** Pointer to the mutator descriptors. */
    267293    PRTFUZZMUTATOR              paMutators;
     294    /** Maximum amount of bytes of mutated inputs to cache. */
     295    size_t                      cbMutationsAllocMax;
     296    /** Current amount of bytes of cached mutated inputs. */
     297    size_t                      cbMutationsAlloc;
     298    /** List of mutators having data allocated currently. */
     299    RTLISTANCHOR                LstMutationsAlloc;
     300    /** Critical section protecting the allocation list. */
     301    RTCRITSECT                  CritSectAlloc;
    268302    /** Total number of bytes of memory currently allocated in total for this context. */
    269303    volatile size_t             cbMemTotal;
    … …  
    361395
    362396
     397/**
     398 * Integer replacing mutator additional data.
     399 */
     400typedef struct RTFUZZMUTATORINTEGER
     401{
     402    /** The integer class. */
     403    uint8_t                     uIntClass;
     404    /** Flag whether to do a byte swap. */
     405    bool                        fByteSwap;
     406    /** The index into the class specific array. */
     407    uint16_t                    idxInt;
     408} RTFUZZMUTATORINTEGER;
     409/** Pointer to additional integer replacing mutator data. */
     410typedef RTFUZZMUTATORINTEGER *PRTFUZZMUTATORINTEGER;
     411/** Pointer to constant additional integer replacing mutator data. */
     412typedef const RTFUZZMUTATORINTEGER *PCRTFUZZMUTATORINTEGER;
     413
    363414/*********************************************************************************************************************************
    364415*   Internal Functions                                                                                                           *
    … …  
    376427static DECLCALLBACK(int) rtFuzzCtxMutatorByteSequenceDeletePrep(PRTFUZZCTXINT pThis, uint64_t offStart, PRTFUZZMUTATION pMutationParent,
    377428                                                                PPRTFUZZMUTATION ppMutation);
     429static DECLCALLBACK(int) rtFuzzCtxMutatorIntegerReplacePrep(PRTFUZZCTXINT pThis, uint64_t offStart, PRTFUZZMUTATION pMutationParent,
     430                                                            PPRTFUZZMUTATION ppMutation);
     431static DECLCALLBACK(int) rtFuzzCtxMutatorCrossoverPrep(PRTFUZZCTXINT pThis, uint64_t offStart, PRTFUZZMUTATION pMutationParent,
     432                                                       PPRTFUZZMUTATION ppMutation);
    378433
    379434static DECLCALLBACK(int) rtFuzzCtxMutatorCorpusExec(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
    … …  
    391446static DECLCALLBACK(int) rtFuzzCtxMutatorByteSequenceDeleteExec(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
    392447                                                                uint8_t *pbBuf, size_t cbBuf);
     448static DECLCALLBACK(int) rtFuzzCtxMutatorIntegerReplaceExec(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
     449                                                            uint8_t *pbBuf, size_t cbBuf);
     450static DECLCALLBACK(int) rtFuzzCtxMutatorCrossoverExec(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
     451                                                       uint8_t *pbBuf, size_t cbBuf);
    393452
    394453static DECLCALLBACK(int) rtFuzzCtxMutatorExportDefault(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
    … …  
    397456                                                      PFNRTFUZZCTXIMPORT pfnImport, void *pvUser);
    398457
     458static DECLCALLBACK(int) rtFuzzCtxMutatorCrossoverExport(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
     459                                                         PFNRTFUZZCTXEXPORT pfnExport, void *pvUser);
     460static DECLCALLBACK(int) rtFuzzCtxMutatorCrossoverImport(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, void *pvMutation,
     461                                                         PFNRTFUZZCTXIMPORT pfnImport, void *pvUser);
     462
    399463
    400464/*********************************************************************************************************************************
    401465*   Global Variables                                                                                                             *
    402466*********************************************************************************************************************************/
     467
     468/** Signed 8bit interesting values. */
     469static int8_t s_ai8Interesting[]    = { INT8_MIN, INT8_MIN + 1, -1, 0, 1, INT8_MAX - 1, INT8_MAX };
     470/** Unsigned 8bit interesting values. */
     471static uint8_t s_au8Interesting[]   = { 0, 1, UINT8_MAX - 1, UINT8_MAX };
     472/** Signed 16bit interesting values. */
     473static int16_t s_ai16Interesting[]  = { INT16_MIN, INT16_MIN + 1, -1, 0, 1, INT16_MAX - 1, INT16_MAX };
     474/** Unsigned 16bit interesting values. */
     475static uint16_t s_au16Interesting[] = { 0, 1, UINT16_MAX - 1, UINT16_MAX };
     476/** Signed 32bit interesting values. */
     477static int32_t s_ai32Interesting[]  = { INT32_MIN, INT32_MIN + 1, -1, 0, 1, INT32_MAX - 1, INT32_MAX };
     478/** Unsigned 32bit interesting values. */
     479static uint32_t s_au32Interesting[] = { 0, 1, UINT32_MAX - 1, UINT32_MAX };
     480/** Signed 64bit interesting values. */
     481static int64_t s_ai64Interesting[]  = { INT64_MIN, INT64_MIN + 1, -1, 0, 1, INT64_MAX - 1, INT64_MAX };
     482/** Unsigned 64bit interesting values. */
     483static uint64_t s_au64Interesting[] = { 0, 1, UINT64_MAX - 1, UINT64_MAX };
     484
     485
    403486/**
    404487 * The special corpus mutator for the original data.
    … …  
    412495    /** uMutator. */
    413496    RTFUZZMUTATOR_ID_CORPUS,
     497    /** enmClass. */
     498    RTFUZZMUTATORCLASS_BYTES,
    414499    /** fFlags */
    415500    RTFUZZMUTATOR_F_DEFAULT,
    … …  
    429514static RTFUZZMUTATOR const g_aMutators[] =
    430515{
    431     /* pszId         pszDesc                                          uMutator     fFlags                      pfnPrep                                       pfnExec                                       pfnExport                      pfnImport */
    432     { "BitFlip",     "Flips a single bit in the input",               0,           RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorBitFlipPrep,                  rtFuzzCtxMutatorBitFlipExec,                  rtFuzzCtxMutatorExportDefault, rtFuzzCtxMutatorImportDefault },
    433     { "ByteReplace", "Replaces a single byte in the input",           1,           RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteReplacePrep,              rtFuzzCtxMutatorByteReplaceExec,              rtFuzzCtxMutatorExportDefault, rtFuzzCtxMutatorImportDefault },
    434     { "ByteInsert",  "Inserts a single byte sequence into the input", 2,           RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteInsertPrep,               rtFuzzCtxMutatorByteInsertExec,               rtFuzzCtxMutatorExportDefault, rtFuzzCtxMutatorImportDefault },
    435     { "ByteSeqIns",  "Inserts a byte sequence in the input",          3,           RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteSequenceInsertAppendPrep, rtFuzzCtxMutatorByteSequenceInsertAppendExec, rtFuzzCtxMutatorExportDefault, rtFuzzCtxMutatorImportDefault },
    436     { "ByteSeqApp",  "Appends a byte sequence to the input",          4,           RTFUZZMUTATOR_F_END_OF_BUF, rtFuzzCtxMutatorByteSequenceInsertAppendPrep, rtFuzzCtxMutatorByteSequenceInsertAppendExec, rtFuzzCtxMutatorExportDefault, rtFuzzCtxMutatorImportDefault },
    437     { "ByteDelete",  "Deletes a single byte sequence from the input", 5,           RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteDeletePrep,               rtFuzzCtxMutatorByteDeleteExec,               NULL,                          NULL                          },
    438     { "ByteSeqDel",  "Deletes a byte sequence from the input",        6,           RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteSequenceDeletePrep,       rtFuzzCtxMutatorByteSequenceDeleteExec,       NULL,                          NULL                          }
     516    /* pszId          pszDesc                                                uMutator     enmClass                     fFlags                      pfnPrep                                       pfnExec                                       pfnExport                        pfnImport                         */
     517    { "BitFlip",      "Flips a single bit in the input",                     0,           RTFUZZMUTATORCLASS_BITS,     RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorBitFlipPrep,                  rtFuzzCtxMutatorBitFlipExec,                  rtFuzzCtxMutatorExportDefault,   rtFuzzCtxMutatorImportDefault     },
     518    { "ByteReplace",  "Replaces a single byte in the input",                 1,           RTFUZZMUTATORCLASS_BYTES,    RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteReplacePrep,              rtFuzzCtxMutatorByteReplaceExec,              rtFuzzCtxMutatorExportDefault,   rtFuzzCtxMutatorImportDefault     },
     519    { "ByteInsert",   "Inserts a single byte sequence into the input",       2,           RTFUZZMUTATORCLASS_BYTES,    RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteInsertPrep,               rtFuzzCtxMutatorByteInsertExec,               rtFuzzCtxMutatorExportDefault,   rtFuzzCtxMutatorImportDefault     },
     520    { "ByteSeqIns",   "Inserts a byte sequence in the input",                3,           RTFUZZMUTATORCLASS_BYTES,    RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteSequenceInsertAppendPrep, rtFuzzCtxMutatorByteSequenceInsertAppendExec, rtFuzzCtxMutatorExportDefault,   rtFuzzCtxMutatorImportDefault     },
     521    { "ByteSeqApp",   "Appends a byte sequence to the input",                4,           RTFUZZMUTATORCLASS_BYTES,    RTFUZZMUTATOR_F_END_OF_BUF, rtFuzzCtxMutatorByteSequenceInsertAppendPrep, rtFuzzCtxMutatorByteSequenceInsertAppendExec, rtFuzzCtxMutatorExportDefault,   rtFuzzCtxMutatorImportDefault     },
     522    { "ByteDelete",   "Deletes a single byte sequence from the input",       5,           RTFUZZMUTATORCLASS_BYTES,    RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteDeletePrep,               rtFuzzCtxMutatorByteDeleteExec,               NULL,                            NULL                              },
     523    { "ByteSeqDel",   "Deletes a byte sequence from the input",              6,           RTFUZZMUTATORCLASS_BYTES,    RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorByteSequenceDeletePrep,       rtFuzzCtxMutatorByteSequenceDeleteExec,       NULL,                            NULL                              },
     524    { "IntReplace",   "Replaces a possible integer with an interesting one", 7,           RTFUZZMUTATORCLASS_INTEGERS, RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorIntegerReplacePrep,           rtFuzzCtxMutatorIntegerReplaceExec,           rtFuzzCtxMutatorExportDefault,   rtFuzzCtxMutatorImportDefault     },
     525    { "MutCrossover", "Creates a crossover of two other mutations",          8,           RTFUZZMUTATORCLASS_MUTATORS, RTFUZZMUTATOR_F_DEFAULT,    rtFuzzCtxMutatorCrossoverPrep,                rtFuzzCtxMutatorCrossoverExec,                rtFuzzCtxMutatorCrossoverExport, rtFuzzCtxMutatorCrossoverImport   }
    439526};
    440527
    … …  
    449536static void *rtFuzzCtxMemoryAlloc(PRTFUZZCTXINT pThis, size_t cb)
    450537{
     538    AssertReturn(cb > 0, NULL);
     539
    451540    PRTFUZZMEMHDR pMemHdr = (PRTFUZZMEMHDR)RTMemAllocZ(cb + sizeof(RTFUZZMEMHDR));
    452541    if (RT_LIKELY(pMemHdr))
    … …  
    478567
    479568/**
     569 * Frees the cached inputs until the given amount is free.
     570 *
     571 * @returns Whether the amount of memory is free.
     572 * @param   pThis               The fuzzer context instance.
     573 * @param   cb                  How many bytes to reclaim
     574 */
     575static bool rtFuzzCtxMutationAllocReclaim(PRTFUZZCTXINT pThis, size_t cb)
     576{
     577    while (   !RTListIsEmpty(&pThis->LstMutationsAlloc)
     578           && pThis->cbMutationsAlloc + cb > pThis->cbMutationsAllocMax)
     579    {
     580        PRTFUZZMUTATION pMutation = RTListGetLast(&pThis->LstMutationsAlloc, RTFUZZMUTATION, NdAlloc);
     581        AssertPtr(pMutation);
     582        AssertPtr(pMutation->pvInput);
     583
     584        rtFuzzCtxMemoryFree(pThis, pMutation->pvInput);
     585        pThis->cbMutationsAlloc -= pMutation->cbAlloc;
     586        pMutation->pvInput = NULL;
     587        pMutation->cbAlloc = 0;
     588        pMutation->fCached = false;
     589        RTListNodeRemove(&pMutation->NdAlloc);
     590    }
     591
     592    return pThis->cbMutationsAlloc + cb <= pThis->cbMutationsAllocMax;
     593}
     594
     595
     596/**
     597 * Updates the cache status of the given mutation.
     598 *
     599 * @returns nothing.
     600 * @param   pThis               The fuzzer context instance.
     601 * @param   pMutation           The mutation to update.
     602 */
     603static void rtFuzzCtxMutationMaybeEnterCache(PRTFUZZCTXINT pThis, PRTFUZZMUTATION pMutation)
     604{
     605    RTCritSectEnter(&pThis->CritSectAlloc);
     606
     607    /* Initial corpus mutations are not freed. */
     608    if (   pMutation->pvInput
     609        && pMutation->pMutator != &g_MutatorCorpus)
     610    {
     611        Assert(!pMutation->fCached);
     612
     613        if (rtFuzzCtxMutationAllocReclaim(pThis, pMutation->cbAlloc))
     614        {
     615            RTListPrepend(&pThis->LstMutationsAlloc, &pMutation->NdAlloc);
     616            pThis->cbMutationsAlloc += pMutation->cbAlloc;
     617            pMutation->fCached = true;
     618        }
     619        else
     620        {
     621            rtFuzzCtxMemoryFree(pThis, pMutation->pvInput);
     622            pMutation->pvInput = NULL;
     623            pMutation->cbAlloc = 0;
     624            pMutation->fCached = false;
     625        }
     626    }
     627    RTCritSectLeave(&pThis->CritSectAlloc);
     628}
     629
     630
     631/**
     632 * Removes a cached mutation from the cache.
     633 *
     634 * @returns nothing.
     635 * @param   pThis               The fuzzer context instance.
     636 * @param   pMutation           The mutation to remove.
     637 */
     638static void rtFuzzCtxMutationCacheRemove(PRTFUZZCTXINT pThis, PRTFUZZMUTATION pMutation)
     639{
     640    RTCritSectEnter(&pThis->CritSectAlloc);
     641    if (pMutation->fCached)
     642    {
     643        RTListNodeRemove(&pMutation->NdAlloc);
     644        pThis->cbMutationsAlloc -= pMutation->cbAlloc;
     645        pMutation->fCached = false;
     646    }
     647    RTCritSectLeave(&pThis->CritSectAlloc);
     648}
     649
     650
     651/**
    480652 * Destroys the given mutation.
    481653 *
    … …  
    485657static void rtFuzzMutationDestroy(PRTFUZZMUTATION pMutation)
    486658{
     659    if (pMutation->pvInput)
     660    {
     661        rtFuzzCtxMemoryFree(pMutation->pFuzzer, pMutation->pvInput);
     662        if (pMutation->fCached)
     663        {
     664            RTCritSectEnter(&pMutation->pFuzzer->CritSectAlloc);
     665            RTListNodeRemove(&pMutation->NdAlloc);
     666            pMutation->pFuzzer->cbMutationsAlloc -= pMutation->cbAlloc;
     667            RTCritSectLeave(&pMutation->pFuzzer->CritSectAlloc);
     668        }
     669        pMutation->pvInput = NULL;
     670        pMutation->cbAlloc = 0;
     671        pMutation->fCached = false;
     672    }
    487673    rtFuzzCtxMemoryFree(pMutation->pFuzzer, pMutation);
    488674}
    … …  
    501687                  || pMutation->fInTree)
    502688              && cRefs < _1M, ("%#x %p\n", cRefs, pMutation));
     689
     690    if (cRefs == 1)
     691        rtFuzzCtxMutationCacheRemove(pMutation->pFuzzer, pMutation);
    503692    return cRefs;
    504693}
    … …  
    515704    uint32_t cRefs = ASMAtomicDecU32(&pMutation->cRefs);
    516705    AssertMsg(cRefs < _1M, ("%#x %p\n", cRefs, pMutation));
    517     if (cRefs == 0 && !pMutation->fInTree)
    518         rtFuzzMutationDestroy(pMutation);
     706
     707    if (cRefs == 0)
     708    {
     709        rtFuzzCtxMutationMaybeEnterCache(pMutation->pFuzzer, pMutation);
     710
     711        if (!pMutation->fInTree)
     712            rtFuzzMutationDestroy(pMutation);
     713    }
     714
    519715    return cRefs;
    520716}
    … …  
    546742
    547743/**
    548  * Returns a random mutation from the corpus of the given fuzzer context.
    549  *
    550  * @returns Pointer to a randomly picked mutation (reference count is increased).
     744 * Locates the mutation with the given key.
     745 *
     746 * @returns Pointer to the mutation if found or NULL otherwise.
    551747 * @param   pThis               The fuzzer context instance.
    552  */
    553 static PRTFUZZMUTATION rtFuzzCtxMutationPickRnd(PRTFUZZCTXINT pThis)
    554 {
    555     uint64_t idxMutation = RTRandAdvU64Ex(pThis->hRand, 1, ASMAtomicReadU64(&pThis->cMutations));
    556 
     748 * @param   uKey                The key to locate.
     749 */
     750static PRTFUZZMUTATION rtFuzzCtxMutationLocate(PRTFUZZCTXINT pThis, uint64_t uKey)
     751{
    557752    int rc = RTSemRWRequestRead(pThis->hSemRwMutations, RT_INDEFINITE_WAIT);
    558753    AssertRC(rc); RT_NOREF(rc);
    … …  
    562757     * already but the mutation is not yet in the tree.
    563758     */
    564     PRTFUZZMUTATION pMutation = (PRTFUZZMUTATION)RTAvlU64GetBestFit(&pThis->TreeMutations, idxMutation, false /*fAbove*/);
    565     AssertPtr(pMutation);
    566 
    567     /* Increase reference count of the mutation. */
    568     rtFuzzMutationRetain(pMutation);
     759    PRTFUZZMUTATION pMutation = (PRTFUZZMUTATION)RTAvlU64GetBestFit(&pThis->TreeMutations, uKey, false /*fAbove*/);
     760    if (RT_LIKELY(pMutation))
     761        rtFuzzMutationRetain(pMutation);
     762
    569763    rc = RTSemRWReleaseRead(pThis->hSemRwMutations);
    570764    AssertRC(rc); RT_NOREF(rc);
    571765
    572766    return pMutation;
     767}
     768
     769
     770/**
     771 * Returns a random mutation from the corpus of the given fuzzer context.
     772 *
     773 * @returns Pointer to a randomly picked mutation (reference count is increased).
     774 * @param   pThis               The fuzzer context instance.
     775 */
     776static PRTFUZZMUTATION rtFuzzCtxMutationPickRnd(PRTFUZZCTXINT pThis)
     777{
     778    uint64_t idxMutation = RTRandAdvU64Ex(pThis->hRand, 1, ASMAtomicReadU64(&pThis->cMutations));
     779    return rtFuzzCtxMutationLocate(pThis, idxMutation);
    573780}
    574781
    … …  
    598805        pMutation->cbMutation      = cbAdditional;
    599806        pMutation->fInTree         = false;
     807        pMutation->fCached         = false;
     808        pMutation->pvInput         = NULL;
     809        pMutation->cbInput         = 0;
     810        pMutation->cbAlloc         = 0;
    600811
    601812        if (pMutationParent)
    … …  
    610821
    611822/**
    612  * Destorys the given fuzzer context freeing all allocated resources.
     823 * Destroys the given fuzzer context freeing all allocated resources.
    613824 *
    614825 * @returns nothing.
    … …  
    618829{
    619830    RT_NOREF(pThis);
     831}
     832
     833
     834/**
     835 * Creates the final input data applying all accumulated mutations.
     836 *
     837 * @returns IPRT status code.
     838 * @param   pMutation           The mutation to finalize.
     839 */
     840static int rtFuzzMutationDataFinalize(PRTFUZZMUTATION pMutation)
     841{
     842    if (pMutation->pvInput)
     843        return VINF_SUCCESS;
     844
     845    /* Traverse the mutations top to bottom and insert into the array. */
     846    int rc = VINF_SUCCESS;
     847    uint32_t idx = pMutation->iLvl + 1;
     848    PRTFUZZMUTATION *papMutations = (PRTFUZZMUTATION *)RTMemTmpAlloc(idx * sizeof(PCRTFUZZMUTATION));
     849    if (RT_LIKELY(papMutations))
     850    {
     851        PRTFUZZMUTATION pMutationCur = pMutation;
     852        size_t cbAlloc = 0;
     853
     854        /*
     855         * As soon as a mutation with allocated input data is encountered the insertion is
     856         * stopped as it contains all necessary mutated inputs we can start from.
     857         */
     858        while (idx > 0)
     859        {
     860            rtFuzzMutationRetain(pMutationCur);
     861            papMutations[idx - 1] = pMutationCur;
     862            cbAlloc = RT_MAX(cbAlloc, pMutationCur->cbInput);
     863            if (pMutationCur->pvInput)
     864            {
     865                idx--;
     866                break;
     867            }
     868            pMutationCur = pMutationCur->pMutationParent;
     869            idx--;
     870        }
     871
     872        pMutation->cbAlloc = cbAlloc;
     873        uint8_t *pbBuf = (uint8_t *)rtFuzzCtxMemoryAlloc(pMutation->pFuzzer, cbAlloc);
     874        if (RT_LIKELY(pbBuf))
     875        {
     876            pMutation->pvInput = pbBuf;
     877
     878            /* Copy the initial input data. */
     879            size_t cbInputNow = papMutations[idx]->cbInput;
     880            memcpy(pbBuf, papMutations[idx]->pvInput, cbInputNow);
     881            rtFuzzMutationRelease(papMutations[idx]);
     882
     883            for (uint32_t i = idx + 1; i < pMutation->iLvl + 1; i++)
     884            {
     885                PRTFUZZMUTATION pCur = papMutations[i];
     886                pCur->pMutator->pfnExec(pCur->pFuzzer, pCur, (void *)&pCur->abMutation[0],
     887                                        pbBuf + pCur->offMutation,
     888                                        cbInputNow - pCur->offMutation);
     889
     890                cbInputNow = pCur->cbInput;
     891                rtFuzzMutationRelease(pCur);
     892            }
     893
     894            Assert(cbInputNow == pMutation->cbInput);
     895        }
     896        else
     897            rc = VERR_NO_MEMORY;
     898
     899        RTMemTmpFree(papMutations);
     900    }
     901    else
     902        rc = VERR_NO_MEMORY;
     903
     904    return rc;
    620905}
    621906
    … …  
    8281113
    8291114
    830 
    8311115/**
    8321116 * Mutator callback - deletes a byte sequence in the input.
    … …  
    8681152
    8691153/**
     1154 * Mutator callback - replaces a possible integer with something interesting.
     1155 */
     1156static DECLCALLBACK(int) rtFuzzCtxMutatorIntegerReplacePrep(PRTFUZZCTXINT pThis, uint64_t offStart, PRTFUZZMUTATION pMutationParent,
     1157                                                            PPRTFUZZMUTATION ppMutation)
     1158{
     1159    int rc = VINF_SUCCESS;
     1160    PRTFUZZMUTATORINTEGER pMutInt = NULL;
     1161    PRTFUZZMUTATION pMutation = rtFuzzMutationCreate(pThis, offStart, pMutationParent, sizeof(*pMutInt), (void **)&pMutInt);
     1162    if (RT_LIKELY(pMutation))
     1163    {
     1164        size_t cbLeft = pMutationParent->cbInput - offStart;
     1165        uint32_t uClassMax = 0;
     1166
     1167        switch (cbLeft)
     1168        {
     1169            case 1:
     1170                uClassMax = 1;
     1171                break;
     1172            case 2:
     1173            case 3:
     1174                uClassMax = 3;
     1175                break;
     1176            case 4:
     1177            case 5:
     1178            case 6:
     1179            case 7:
     1180                uClassMax = 5;
     1181                break;
     1182            default:
     1183                uClassMax = 7;
     1184                break;
     1185        }
     1186
     1187        pMutInt->uIntClass = (uint8_t)RTRandAdvU32Ex(pThis->hRand, 0, uClassMax);
     1188        pMutInt->fByteSwap = RT_BOOL(RTRandAdvU32Ex(pThis->hRand, 0, 1));
     1189
     1190        switch (pMutInt->uIntClass)
     1191        {
     1192            case 0:
     1193                pMutInt->idxInt = (uint16_t)RTRandAdvU32Ex(pThis->hRand, 0, RT_ELEMENTS(s_ai8Interesting) - 1);
     1194                break;
     1195            case 1:
     1196                pMutInt->idxInt = (uint16_t)RTRandAdvU32Ex(pThis->hRand, 0, RT_ELEMENTS(s_au8Interesting) - 1);
     1197                break;
     1198            case 2:
     1199                pMutInt->idxInt = (uint16_t)RTRandAdvU32Ex(pThis->hRand, 0, RT_ELEMENTS(s_ai16Interesting) - 1);
     1200                break;
     1201            case 3:
     1202                pMutInt->idxInt = (uint16_t)RTRandAdvU32Ex(pThis->hRand, 0, RT_ELEMENTS(s_au16Interesting) - 1);
     1203                break;
     1204            case 4:
     1205                pMutInt->idxInt = (uint16_t)RTRandAdvU32Ex(pThis->hRand, 0, RT_ELEMENTS(s_ai32Interesting) - 1);
     1206                break;
     1207            case 5:
     1208                pMutInt->idxInt = (uint16_t)RTRandAdvU32Ex(pThis->hRand, 0, RT_ELEMENTS(s_au32Interesting) - 1);
     1209                break;
     1210            case 6:
     1211                pMutInt->idxInt = (uint16_t)RTRandAdvU32Ex(pThis->hRand, 0, RT_ELEMENTS(s_ai64Interesting) - 1);
     1212                break;
     1213            case 7:
     1214                pMutInt->idxInt = (uint16_t)RTRandAdvU32Ex(pThis->hRand, 0, RT_ELEMENTS(s_au64Interesting) - 1);
     1215                break;
     1216            default:
     1217                AssertReleaseFailed();
     1218        }
     1219
     1220        pMutation->cbInput = pMutationParent->cbInput;
     1221        *ppMutation = pMutation;
     1222    }
     1223    else
     1224        rc = VERR_NO_MEMORY;
     1225
     1226    return rc;
     1227}
     1228
     1229
     1230static DECLCALLBACK(int) rtFuzzCtxMutatorIntegerReplaceExec(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
     1231                                                            uint8_t *pbBuf, size_t cbBuf)
     1232{
     1233    RT_NOREF(pThis, pMutation, cbBuf);
     1234    union
     1235    {
     1236        int8_t   i8;
     1237        uint8_t  u8;
     1238        int16_t  i16;
     1239        uint16_t u16;
     1240        int32_t  i32;
     1241        uint32_t u32;
     1242        int64_t  i64;
     1243        uint64_t u64;
     1244    } Int;
     1245    PCRTFUZZMUTATORINTEGER pMutInt = (PCRTFUZZMUTATORINTEGER)pvMutation;
     1246    size_t cb = 0;
     1247
     1248    switch (pMutInt->uIntClass)
     1249    {
     1250        case 0:
     1251            Int.i8 = s_ai8Interesting[pMutInt->idxInt];
     1252            cb = 1;
     1253            break;
     1254        case 1:
     1255            Int.u8 = s_au8Interesting[pMutInt->idxInt];
     1256            cb = 1;
     1257            break;
     1258        case 2:
     1259            Int.i16 = s_ai16Interesting[pMutInt->idxInt];
     1260            cb = 2;
     1261            if (pMutInt->fByteSwap)
     1262                Int.u16 = RT_BSWAP_U16(Int.u16);
     1263            break;
     1264        case 3:
     1265            Int.u16 = s_au16Interesting[pMutInt->idxInt];
     1266            cb = 2;
     1267            if (pMutInt->fByteSwap)
     1268                Int.u16 = RT_BSWAP_U16(Int.u16);
     1269            break;
     1270        case 4:
     1271            Int.i32 = s_ai32Interesting[pMutInt->idxInt];
     1272            cb = 4;
     1273            if (pMutInt->fByteSwap)
     1274                Int.u32 = RT_BSWAP_U32(Int.u32);
     1275            break;
     1276        case 5:
     1277            Int.u32 = s_au32Interesting[pMutInt->idxInt];
     1278            cb = 4;
     1279            if (pMutInt->fByteSwap)
     1280                Int.u32 = RT_BSWAP_U32(Int.u32);
     1281            break;
     1282        case 6:
     1283            Int.i64 = s_ai64Interesting[pMutInt->idxInt];
     1284            cb = 8;
     1285            if (pMutInt->fByteSwap)
     1286                Int.u64 = RT_BSWAP_U64(Int.u64);
     1287            break;
     1288        case 7:
     1289            Int.u64 = s_au64Interesting[pMutInt->idxInt];
     1290            cb = 8;
     1291            if (pMutInt->fByteSwap)
     1292                Int.u64 = RT_BSWAP_U64(Int.u64);
     1293            break;
     1294        default:
     1295            AssertReleaseFailed();
     1296    }
     1297
     1298    memcpy(pbBuf, &Int, cb);
     1299    return VINF_SUCCESS;
     1300}
     1301
     1302
     1303/**
     1304 * Mutator callback - crosses over two mutations at the given point.
     1305 */
     1306static DECLCALLBACK(int) rtFuzzCtxMutatorCrossoverPrep(PRTFUZZCTXINT pThis, uint64_t offStart, PRTFUZZMUTATION pMutationParent,
     1307                                                       PPRTFUZZMUTATION ppMutation)
     1308{
     1309    int rc = VINF_SUCCESS;
     1310
     1311    if (pThis->cMutations > 1)
     1312    {
     1313        uint64_t *pidxMutCrossover = NULL;
     1314        PRTFUZZMUTATION pMutation = rtFuzzMutationCreate(pThis, offStart, pMutationParent, sizeof(*pidxMutCrossover), (void **)&pidxMutCrossover);
     1315        if (RT_LIKELY(pMutation))
     1316        {
     1317            uint32_t cTries = 10;
     1318            PRTFUZZMUTATION pMutCrossover = NULL;
     1319            /*
     1320             * Pick a random mutation to crossover with (making sure it is not the current one
     1321             * or the crossover point is beyond the end of input).
     1322             */
     1323            do
     1324            {
     1325                if (pMutCrossover)
     1326                    rtFuzzMutationRelease(pMutCrossover);
     1327                pMutCrossover = rtFuzzCtxMutationPickRnd(pThis);
     1328                cTries--;
     1329            } while (   (   pMutCrossover == pMutationParent
     1330                         || offStart >= pMutCrossover->cbInput)
     1331                     && cTries > 0);
     1332
     1333            if (cTries)
     1334            {
     1335                pMutation->cbInput = pMutCrossover->cbInput;
     1336                *pidxMutCrossover = pMutCrossover->Core.Key;
     1337                *ppMutation = pMutation;
     1338            }
     1339            else
     1340                rtFuzzMutationDestroy(pMutation);
     1341
     1342            rtFuzzMutationRelease(pMutCrossover);
     1343        }
     1344        else
     1345            rc = VERR_NO_MEMORY;
     1346    }
     1347
     1348    return rc;
     1349}
     1350
     1351
     1352static DECLCALLBACK(int) rtFuzzCtxMutatorCrossoverExec(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
     1353                                                       uint8_t *pbBuf, size_t cbBuf)
     1354{
     1355    RT_NOREF(cbBuf);
     1356    uint64_t idxMutCrossover = *(uint64_t *)pvMutation;
     1357
     1358    PRTFUZZMUTATION pMutCrossover = rtFuzzCtxMutationLocate(pThis, idxMutCrossover);
     1359    int rc = rtFuzzMutationDataFinalize(pMutCrossover);
     1360    if (RT_SUCCESS(rc))
     1361    {
     1362        memcpy(pbBuf, (uint8_t *)pMutCrossover->pvInput + pMutation->offMutation,
     1363               pMutCrossover->cbInput - pMutation->offMutation);
     1364        rtFuzzMutationRelease(pMutCrossover);
     1365    }
     1366
     1367    return rc;
     1368}
     1369
     1370
     1371static DECLCALLBACK(int) rtFuzzCtxMutatorCrossoverExport(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, const void *pvMutation,
     1372                                                         PFNRTFUZZCTXEXPORT pfnExport, void *pvUser)
     1373{
     1374    RT_NOREF(pMutation);
     1375
     1376    uint64_t idxMutCrossover = *(uint64_t *)pvMutation;
     1377    idxMutCrossover = RT_H2LE_U64(idxMutCrossover);
     1378    return pfnExport(pThis, &idxMutCrossover, sizeof(idxMutCrossover), pvUser);
     1379}
     1380
     1381
     1382static DECLCALLBACK(int) rtFuzzCtxMutatorCrossoverImport(PRTFUZZCTXINT pThis, PCRTFUZZMUTATION pMutation, void *pvMutation,
     1383                                                         PFNRTFUZZCTXIMPORT pfnImport, void *pvUser)
     1384{
     1385    RT_NOREF(pMutation);
     1386
     1387    uint64_t uKey = 0;
     1388    int rc = pfnImport(pThis, &uKey, sizeof(uKey), NULL, pvUser);
     1389    if (RT_SUCCESS(rc))
     1390    {
     1391        uKey = RT_LE2H_U64(uKey);
     1392        *(uint64_t *)pvMutation = uKey;
     1393    }
     1394
     1395    return rc;
     1396}
     1397
     1398
     1399/**
    8701400 * Creates an empty fuzzing context.
    8711401 *
    … …  
    8801410    if (RT_LIKELY(pThis))
    8811411    {
    882         pThis->u32Magic         = RTFUZZCTX_MAGIC;
    883         pThis->cRefs            = 1;
    884         pThis->enmType          = enmType;
    885         pThis->TreeMutations    = NULL;
    886         pThis->cbInputMax       = UINT32_MAX;
    887         pThis->cMutations       = 0;
    888         pThis->fFlagsBehavioral = 0;
    889         pThis->cbMemTotal       = 0;
     1412        pThis->u32Magic            = RTFUZZCTX_MAGIC;
     1413        pThis->cRefs               = 1;
     1414        pThis->enmType             = enmType;
     1415        pThis->TreeMutations       = NULL;
     1416        pThis->cbInputMax          = UINT32_MAX;
     1417        pThis->cMutations          = 0;
     1418        pThis->fFlagsBehavioral    = 0;
     1419        pThis->cbMutationsAllocMax = _1G;
     1420        pThis->cbMemTotal          = 0;
     1421        RTListInit(&pThis->LstMutationsAlloc);
    8901422
    8911423        /* Copy the default mutator descriptors over. */
    … …  
    8991431            if (RT_SUCCESS(rc))
    9001432            {
    901                 rc = RTRandAdvCreateParkMiller(&pThis->hRand);
     1433                rc = RTCritSectInit(&pThis->CritSectAlloc);
    9021434                if (RT_SUCCESS(rc))
    9031435                {
    904                     RTRandAdvSeed(pThis->hRand, RTTimeSystemNanoTS());
    905                     *ppThis = pThis;
    906                     return VINF_SUCCESS;
     1436                    rc = RTRandAdvCreateParkMiller(&pThis->hRand);
     1437                    if (RT_SUCCESS(rc))
     1438                    {
     1439                        RTRandAdvSeed(pThis->hRand, RTTimeSystemNanoTS());
     1440                        *ppThis = pThis;
     1441                        return VINF_SUCCESS;
     1442                    }
     1443
     1444                    RTCritSectDelete(&pThis->CritSectAlloc);
    9071445                }
    9081446
    … …  
    9321470    PRTFUZZCTXINT pFuzzer = pThis->pFuzzer;
    9331471
    934     if (   pFuzzer->enmType == RTFUZZCTXTYPE_BLOB
    935         && pThis->u.Blob.pvInput)
    936         rtFuzzCtxMemoryFree(pFuzzer, pThis->u.Blob.pvInput);
    937 
    9381472    rtFuzzMutationRelease(pThis->pMutationTop);
    9391473    rtFuzzCtxMemoryFree(pFuzzer, pThis);
    9401474    RTFuzzCtxRelease(pFuzzer);
    941 }
    942 
    943 
    944 /**
    945  * Creates the final input data applying all accumulated mutations.
    946  *
    947  * @returns IPRT status code.
    948  * @param   pThis               The fuzzing input to finalize.
    949  */
    950 static int rtFuzzInputDataFinalize(PRTFUZZINPUTINT pThis)
    951 {
    952     Assert(!pThis->u.Blob.pvInput);
    953 
    954     int rc = VINF_SUCCESS;
    955     uint8_t *pbBuf = (uint8_t *)rtFuzzCtxMemoryAlloc(pThis->pFuzzer, pThis->u.Blob.cbAlloc);
    956     if (RT_LIKELY(pbBuf))
    957     {
    958         pThis->u.Blob.pvInput = pbBuf;
    959         pThis->u.Blob.cbInput = pThis->pMutationTop->cbInput;
    960 
    961         size_t cbInputNow = pThis->apMutations[0]->cbInput;
    962         for (uint32_t i = 0; i < pThis->pMutationTop->iLvl + 1; i++)
    963         {
    964             PCRTFUZZMUTATION pMutation = pThis->apMutations[i];
    965             pMutation->pMutator->pfnExec(pThis->pFuzzer, pMutation, (void *)&pMutation->abMutation[0],
    966                                          pbBuf + pMutation->offMutation,
    967                                          cbInputNow - pMutation->offMutation);
    968 
    969             cbInputNow = pMutation->cbInput;
    970         }
    971 
    972         Assert(cbInputNow == pThis->u.Blob.cbInput);
    973     }
    974     else
    975         rc = VERR_NO_MEMORY;
    976 
    977     return rc;
    9781475}
    9791476
    … …  
    12831780        pMutation->pMutator = &g_MutatorCorpus;
    12841781        pMutation->cbInput  = cbInput;
     1782        pMutation->pvInput  = pvCorpus;
    12851783        memcpy(pvCorpus, pvInput, cbInput);
    12861784        rc = rtFuzzCtxMutationAdd(pThis, pMutation);
    … …  
    13301828            pMutation->pMutator = &g_MutatorCorpus;
    13311829            pMutation->cbInput  = cbFile;
     1830            pMutation->pvInput  = pvCorpus;
    13321831            rc = RTVfsFileRead(hVfsFile, pvCorpus, cbFile, NULL);
    13331832            if (RT_SUCCESS(rc))
    … …  
    14941993
    14951994            /* Create a new input. */
    1496             PRTFUZZINPUTINT pInput = (PRTFUZZINPUTINT)rtFuzzCtxMemoryAlloc(pThis, RT_UOFFSETOF_DYN(RTFUZZINPUTINT, apMutations[pMutation->iLvl + 1]));
     1995            PRTFUZZINPUTINT pInput = (PRTFUZZINPUTINT)rtFuzzCtxMemoryAlloc(pThis, sizeof(RTFUZZINPUTINT));
    14971996            if (RT_LIKELY(pInput))
    14981997            {
    … …  
    15032002                RTFuzzCtxRetain(pThis);
    15042003
    1505                 /* Traverse the mutations top to bottom and insert into the array. */
    1506                 uint32_t idx = pMutation->iLvl + 1;
    1507                 PCRTFUZZMUTATION pMutationCur = pMutation;
    1508                 size_t cbAlloc = 0;
    1509                 while (idx > 0)
    1510                 {
    1511                     pInput->apMutations[idx - 1] = pMutationCur;
    1512                     cbAlloc = RT_MAX(cbAlloc, pMutationCur->cbInput);
    1513                     pMutationCur = pMutationCur->pMutationParent;
    1514                     idx--;
    1515                 }
    1516 
    1517                 pInput->u.Blob.cbAlloc = cbAlloc;
     2004                rtFuzzMutationRelease(pMutationParent);
    15182005                *phFuzzInput = pInput;
    15192006                return rc;
    … …  
    15242011    } while (++cTries <= 50);
    15252012
     2013    rtFuzzMutationRelease(pMutationParent);
    15262014    if (RT_SUCCESS(rc))
    15272015        rc = VERR_INVALID_STATE;
    … …  
    15382026
    15392027    int rc = VINF_SUCCESS;
    1540     if (!pThis->u.Blob.pvInput)
    1541         rc = rtFuzzInputDataFinalize(pThis);
     2028    if (!pThis->pMutationTop->pvInput)
     2029        rc = rtFuzzMutationDataFinalize(pThis->pMutationTop);
    15422030
    15432031    if (RT_SUCCESS(rc))
    15442032    {
    1545         AssertPtr(pThis->u.Blob.pvInput);
    1546         Assert(pThis->u.Blob.cbInput > 0);
    1547 
    1548         *ppv = pThis->u.Blob.pvInput;
    1549         *pcb = pThis->u.Blob.cbInput;
     2033        *ppv = pThis->pMutationTop->pvInput;
     2034        *pcb = pThis->pMutationTop->cbInput;
    15502035    }
    15512036
    … …  
    16012086
    16022087    int rc = VINF_SUCCESS;
    1603     if (!pThis->u.Blob.pvInput)
    1604         rc = rtFuzzInputDataFinalize(pThis);
     2088    if (!pThis->pMutationTop->pvInput)
     2089        rc = rtFuzzMutationDataFinalize(pThis->pMutationTop);
    16052090
    16062091    if (RT_SUCCESS(rc))
    16072092    {
    16082093        uint8_t abHash[RTMD5_HASH_SIZE];
    1609         RTMd5(pThis->u.Blob.pvInput, pThis->u.Blob.cbInput, &abHash[0]);
     2094        RTMd5(pThis->pMutationTop->pvInput, pThis->pMutationTop->cbInput, &abHash[0]);
    16102095        rc = RTMd5ToString(&abHash[0], pszDigest, cchDigest);
    16112096    }
    … …  
    16232108
    16242109    int rc = VINF_SUCCESS;
    1625     if (!pThis->u.Blob.pvInput)
    1626         rc = rtFuzzInputDataFinalize(pThis);
     2110    if (!pThis->pMutationTop->pvInput)
     2111        rc = rtFuzzMutationDataFinalize(pThis->pMutationTop);
    16272112
    16282113    if (RT_SUCCESS(rc))
    … …  
    16322117        if (RT_SUCCESS(rc))
    16332118        {
    1634             rc = RTFileWrite(hFile, pThis->u.Blob.pvInput, pThis->u.Blob.cbInput, NULL);
     2119            rc = RTFileWrite(hFile, pThis->pMutationTop->pvInput, pThis->pMutationTop->cbInput, NULL);
    16352120            AssertRC(rc);
    16362121            RTFileClose(hFile);
Note: See TracChangeset for help on using the changeset viewer.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette