LearnPerfFuzz: Generating Pathological Inputs using Greybox Fuzzing with Knowledge Enhancement

Algorithmic complexity vulnerabilities are issues that cause an algorithm to perform poorly when given pathological inputs that identify the worst-case scenario. The identification of these problems using statistical profiling techniques has drawn a lot of interest in the literature. However, where can one locate these inputs? In this study, we introduce LearnPerfFuzz, a knowledge-learn feedback-directed mutational fuzzing method to produce inputs automatically that identify worst-case behavior throughout the program locations. LearnPerfFuzz's core concept is to create inputs having maximum total execution path length and identify a lot of inputs that exercises different program hot spots. LearnPerfFuzz may acquire partial format information of some paths based on the format generation concept by examining the inputs which exercise such paths. Then LearnPerfFuzz mutates the inputs using this format knowledge, which is effective for exploring deeper paths and creating more pathological inputs. LearnPerfFuzz is built on top of AFL, a tool for coverage-guided fuzzing. We test LearnPerfFuzz in six actual C programs. LearnPerfFuzz can produce input with more comparisons in insertion sort, and in the word frequency program wf-0.41 Feodra Linux repository, it can create lengthy single-letter words that outperformed previous work. LearnPerfFuzz also regenerates crash in xpdf-4.04 pdftotext whose severity score is 7.8 (CVE-2022-30524)

Research Images