Gray-Box Fuzzing in Local Space
Martin Jonáš, Jan Strejček, Marek Trtík · 2025
Read Gray-Box Fuzzing in Local Space by Martin Jonáš, Jan Strejček, Marek Trtík (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18046.txt.
Introduction
Martin Jonáš, Jan Strejček, and Marek Trtík sharpen gray-box fuzzing, a software testing method, by searching near an already-run path, in a research paper from 2025. Their test programs record how numeric comparisons came out during a run. The goal is a new input that repeats the same path but flips the last comparison.
The authors define that search problem formally for recorded comparison data. They then give an algorithm that hunts the flipped input efficiently. Trials on a standard competition benchmark suite showed the method works in practice. Better local search helps fuzzers reach rare branches where bugs hide.
Catalog record
| CREATOR | Martin Jonáš, Jan Strejček, Marek Trtík |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18046
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Gray-Box Fuzzing in Local Space Thanks: This work has been supported by the Czech Science Foundation grant GA23-06506S. Martin Jonáš, Jan Strejček, Marek Trtík Abstract We consider gray-box fuzzing of a program instrumented such that information about evaluation of program expressions converting values of numerical types to Boolean, like x <= y x<=y , is recorded during each program’s execution. Given that information for an executed program path, we formally define the problem for finding input such that program’s execution with that input evaluates all those expressions in the same order and with the same Boolean values as in the original execution path, except for the last one, which is evaluated to the opposite value. Then we also provide an algorithm searching for a solution of the problem effectively. The effectiveness of the algorithm is demonstrated empirically via its evaluation on the TestComp 2024 benchmark suite. 1 Introduction The primary goal of gray-box fuzzing [ 16 ] is to find as many defects in an analyzed program as possible. More precisely, the goal is to find inputs to the program such that program’s execution with them triggers different defects in the program. In this paper we use a simplified model for input. The program reads input via calls to reserved functions returning a value of a requested primitive type, like char , int , float , etc. For example, by calling read_int() the program receives an input value of the type int . Each call to these functions during program’s execution creates a fresh input variable of the corresponding type holding the returned value. The input variables are artificial, i.e., they do not appear in the program. They just represent the input for which the program executes along the path where the input variables were created. During gray-box fuzzing we do not read or otherwise use program’s code; neither source code nor binary. However, we record information about each program’s execution via probing code, which we instrument to the program before fuzzing is started. The recorded information is used for generation of next inputs. Execution of the probes slows down overall program’s execution. If we instrument too much or too complex probes to the program, then the number of executions within a given time budget can drop considerably compared to number of executions of the original (not instrumented) program. In that case we in fact decrease our chances to discover a defect. If the probes do not give us enough information for next input generation, we can easily generate inputs for which the program executes along paths executed before. We thus also decrease our chances to discover a defect. An optimal approach is to instrument as few and as simple probes as possible, which still provide enough information for generation of inputs for which program executes new paths. In this paper we consider a gray-box fuzzing, where probes record information about evaluation of program expressions converting values of numerical types to Boolean, like x<=y , x==5 . That is because Boolean values are primarily involved in program branching. We call any such expression as atomic Boolean expression ( abe ). We give precise definition later. For each executed abe we record the Boolean value it was evaluated to and also a signed distance to evaluation of the abe to the opposite value. For example, signed distance function for a comparison is the difference between the left and right operand, e.g., for x<=y-5 the signed distance is x-y+5 . But both operands must be casted to a wider type to prevent an overflow/underflow when taking their difference. So, for each executed program path we have a list of input variables, the sequence of abe s in the order of their execution and for each abe we know its Boolean value and the signed distance value. In the worst case, we can assume that all input variables affect signed distance of each abe . In our implementation, we apply taint-flow analysis along that execution path to optimize the correspondence between input variables and signed distances of abe s. The contribution of the paper is the following. Given all mentioned information associated with an executed program path, we first formally define the problem for finding input such that program’s execution with that input evaluates all abe s in the same order and with the same Boolean values as in the original execution path, except for the last abe , which is evaluated to the opposite value. That is done in Section 2 . Then we describe an algorithm searching for a solution of the problem effectively. That is done in Sections 3 - 7 . Finally, we demonstrate the effectiveness of the algorithm by its evaluation on the TestComp 2024 benchmark suite; we show improvement in outcomes over those from the original version of the gray-box fuzzer, called Fizzer , into which we implemented this algorithm. That is done in Section 8 . Remark 1 When the algorithm finds a solution to the problem, then we have two inputs (from the given path and the found one). They lead to evaluation of the last abe to opposite Boolean values. We thus say that abe is covered. That is the reason for calling the problem as coverage problem . Further note that if we are given information for an executed program path, then we can formulate the coverage problem for any prefix of that path. 2 Coverage problem definition Since we intensively use vectors and vector spaces in the rest of the paper, we start with the basic notation. If \vec{u} is a vector, then \vec{u}_{i} is the i -th coordinate of \vec{u} . If \vec{u} has all coordinates 0 except \vec{u}_{i} which is 1, then we call \vec{u} as i -th axis. If \vec{u} is a vector of vectors, then \vec{u}_{i,j} denotes the j -th coordinate of the i -th vector of \vec{u} . We naturally extend this notation to arbitrary nesting depth of vectors. We use only column vectors in this paper. Lastly, we denote the dot product of vectors \vec{u},\vec{v} as \vec{u}\cdot\vec{v} and the length of a vector \vec{u} as |\vec{u}| . Note that |\vec{u}|=\sqrt{\vec{u}\cdot\vec{u}} . A type is any signed or unsigned 8-, 16-, 32- or 64-bit integer or 32- or 64-bit floating point type of C language. The Boolean type is modelled as 8-bit unsigned integer with only two possible values 0 and 1. We denote a type of a variable x as \tau(x) and the finite size of the set of all possible values of the type as |\tau(x)| . We use the symbols x or x^{\prime} possibly with the lower index for denoting variables. An atomic Boolean expression ( abe ) is a function computing a value of the Boolean type from at least one parameter of a numerical type such that no logical connective is involved in the computation and also there is no abe comprised within definition of the function. The comparison instructions, like x_{1}=x_{2} , x_{1}\geq 10 etc., represent the most common and also the most important abe s. The type casting or truncating of a numerical value to a Boolean value are another examples of abe s. A valuation is any function I