GRIMOIRE: Synthesizing Structure while Fuzzing

Abstract

In the past few years, fuz­zing has re­cei­ved si­gni­fi­cant at­ten­ti­on from the re­se­arch com­mu­ni­ty. Howe­ver, most of this at­ten­ti­on was di­rec­ted towards pro­grams wi­thout a de­di­ca­ted par­sing stage. In such cases, fuz­zers which le­ver­a­ge the input struc­tu­re of a pro­gram can achie­ve a si­gni­fi­cant­ly hig­her code co­ver­a­ge com­pa­red to tra­di­tio­nal fuz­zing ap­proa­ches. This ad­van­ce­ment in co­ver­a­ge is achie­ved by ap­p­ly­ing lar­ge-sca­le mu­ta­ti­ons in the ap­p­li­ca­ti­on's input space. Howe­ver, this im­pro­ve­ment comes at the cost of re­qui­ring ex­pert do­main know­ledge, as these fuz­zers de­pend on struc­tu­re input spe­ci­fi­ca­ti­ons (e.g., gram­mars). Gram­mar in­fe­rence, a tech­ni­que which can au­to­ma­ti­cal­ly ge­ne­ra­te such gram­mars for a given pro­gram, can be used to ad­dress this short­co­ming. Such tech­ni­ques usual­ly infer a pro­gram's gram­mar in a pre-pro­ces­sing step and can miss im­portant struc­tu­res that are un­co­ver­ed only later du­ring nor­mal fuz­zing.

In this paper, we pre­sent the de­sign and im­ple­men­ta­ti­on of GRI­MOIRE, a fully au­to­ma­ted co­ver­a­ge-gui­ded fuz­zer which works wi­thout any form of human in­ter­ac­tion or pre-con­fi­gu­ra­ti­on; yet, it is still able to ef­fi­ci­ent­ly test pro­grams that ex­pect high­ly struc­tu­red in­puts. We achie­ve this by per­for­ming lar­ge-sca­le mu­ta­ti­ons in the pro­gram input space using gram­mar-li­ke com­bi­na­ti­ons to syn­the­si­ze new high­ly struc­tu­red in­puts wi­thout any pre-pro­ces­sing step. Our eva­lua­ti­on shows that GRI­MOIRE out­per­forms other co­ver­a­ge-gui­ded fuz­zers when fuz­zing pro­grams with high­ly struc­tu­red in­puts. Fur­ther­mo­re, it im­pro­ves upon exis­ting gram­mar-ba­sed co­ver­a­ge-gui­ded fuz­zers. Using GRI­MOIRE, we iden­ti­fied 19 dis­tinct me­mo­ry cor­rup­ti­on bugs in re­al-world pro­grams and ob­tained 11 new CVEs.