Abstract
Binary protocols are widely used in the Internet, industrial control systems, and Internet of Things applications, and vulnerabilities in their implementation can directly affect system security. Existing binary-protocol fuzzers face three practical challenges: identifying effective mutation positions in messages with implicit field boundaries, inferring mutation constraints for different protocol fields, and scheduling appropriate mutation operators to explore new program paths without generating excessive invalid test cases. This paper proposes MPAuzz, a greybox fuzzer for binary protocols driven by the Marine Predators Algorithm (MPA). MPAuzz first performs feedback-based mutation position exploration and classifies message regions as mutable, restricted, or immutable. It then formulates mutation operator scheduling as a multidimensional optimization problem, where each dimension corresponds to an operator choice for a mutation region. By simulating the staged exploration and exploitation process of MPA, MPAuzz adaptively adjusts operator combinations according to program responses and coverage feedback. Experiments on binary protocol implementations including MQTT, DTLS, DNS, and CoAP show that MPAuzz achieves an average valid-test-case ratio of 98.1%, improves branch coverage by 38.3% over AFLNet and 26.5% over StateAFL on average, and triggers the highest number of crashes across all targets.
Introduction
Binary protocol is a structured encoding specification designed for efficient data exchange in communication systems, characterized by representing data directly as binary byte sequences. Compared with text-based protocols, binary protocols are more compact, eliminating the need for additional character representations or redundant elements such as delimiters and tags commonly found in text protocols. Binary protocols are widely used in network devices, industrial control systems, and Internet of Things (IoT) applications. A representative example is the EternalBlue vulnerability in the SMB protocol, which resulted from improper parsing of binary protocol messages and led to buffer overflow and remote code execution, causing severe global impact (Schiller et al. 2022). Therefore, research on vulnerability discovery in binary protocols is of great significance.
Mutation-based greybox fuzzing has been widely used for vulnerability discovery. Greybox fuzzing lies between whitebox and blackbox fuzzing in that it does not require complete knowledge of program internals, but uses lightweight runtime feedback, such as coverage information obtained through instrumentation, to guide input mutation. This approach generates malformed test cases for the target program and monitors its runtime behavior to detect abnormal executions and potential vulnerabilities triggered by these inputs.
Many researchers have focused on improving the efficiency and effectiveness of fuzzing in discovering vulnerabilities. Representative greybox fuzzers such as AFL (American Fuzzy Lop) (Zalewski 2016), AFL++ (Fioraldi et al. 2020), and MOPT (Lyu et al. 2019) run without prior knowledge of the target program’s input format. These tools generate test cases by applying mutation operators to existing seed inputs. The seeds are typically well-formed messages that conform to the expected input format. The fuzzers apply mutations, such as bit flip and character substitution, on the seeds to produce malformed protocol messages, which are then sent to the protocol implementation for testing.
However, existing fuzzers often lack effective mechanisms for selecting mutation positions and scheduling mutation operators, resulting in many discarded test cases because the test cases violate the protocol format specification. This lowers fuzzing efficiency (Zhang et al. 2024). Overall, binary protocol fuzzing faces three main challenges:
-
(1)
Difficulty in Protocol Parsing. Binary protocols represent data as bit streams, with unclear field boundaries and implicit semantics (e.g., lack of explicit delimiters), rendering manual parsing labor-intensive. Fuzzing often requires identifying field boundaries to determine valid mutation positions, making protocol parsing a significant challenge in fuzzing such protocols.
-
(2)
Difficulty in Evaluating the Mutation Value of Different Fields. A protocol message contains multiple fields with different semantics and constraints. Mutating a field may either help explore new execution paths or simply break the protocol format and cause the test case to be discarded. Since the value of a field mutation depends on runtime behavior, field dependencies, and target-program responses, it is difficult to determine statically. Therefore, fuzzers need to dynamically evaluate field mutation effectiveness based on testing feedback, including message validity, response changes, coverage increases, and abnormal behaviors.
-
(3)
Blind Scheduling of Mutation Operators. Existing fuzzers lack the ability to schedule mutation operators based on the characteristics of target fields (e.g., field type, format). Mutation operators refer to operations that modify input data, including bitflip, insert, delete, and other basic operations. Different semantic fields in protocols (e.g., length fields, flag fields) exhibit significantly varying responses to mutation operators. Current fuzzers fail to select appropriate mutation operators based on field semantics, and they generally apply a uniform mutation strategy, which results in inefficient fuzzing. For instance, applying bitflip to a function code field of the protocol may drive the target program into different logical states, thus exploring a broader code space, while the same operation on a data field only alters the data content. Additionally, there are often semantic dependencies and constraints between protocol fields, such as the relationship between length fields and data fields. The value of a length field cannot be modified blindly without adjusting the corresponding content in the affected range. If these dependencies are ignored during the mutation process, the mutation can break the structure of the message. This would cause the test case to be discarded during the protocol parsing phase, preventing in-depth exploration of the target program’s code. Therefore, it is essential to design a mechanism that can intelligently schedule mutation operators based on field semantics, while maintaining the semantic constraints between fields during mutation, thus improving the effectiveness of test cases and enhancing fuzzing efficiency.
For Challenge (1), existing research mainly offers two approaches: static reverse analysis and dynamic interaction reasoning. BinaryInferno (Chandler et al. 2023) uses multiple semantic detectors, such as floating-point numbers, timestamps, and length fields, to identify field boundaries, clarifying the types and relationships of the fields to achieve protocol format parsing. DYNPRE (Luo et al. 2024) learns the server’s interaction rules, employing exploratory requests to obtain semantic information and supplement samples to optimize field partition. These methods either rely on high-quality samples or require frequent interactions with servers, rendering the method costly to apply.
For Challenges (2) and (3), protocol fuzzers such as AFLNet (Pham et al. 2020) and StateAFL (Natella 2022) parse message requests and responses by predefining message formats and identifying protocol fields to ensure that the generated test cases comply with the protocol specification. However, constructing format models requires expert knowledge and is difficult to adapt to context-dependent field semantics, where the meaning or layout of subsequent fields may vary with message types, function codes, or protocol states. For example, if a field is a function code, its value might alter the number of subsequent fields, and the same position may carry different meanings in different contexts. BLEEM (Luo et al. 2023) guides fuzzing using system state tracking graphs and generates packet sequences that conform to protocol logic based on interactive traffic. Although the method ensures that the message sequences are logically consistent, it provides insufficient guidance on which parts of the message can be mutated and how to mutate them effectively.
This paper proposes MPAuzz, a mutation-based greybox fuzzer for binary protocols driven by the Marine Predators Algorithm. The core idea is to obtain the mutation properties of different message regions from fuzzing feedback, and use the knowledge to guide operator scheduling. Specifically, MPAuzz performs bit-level message partition and generates test cases through lightweight bitflip mutations. Program responses and protocol-format feedback are then used to classify each bit, and adjacent bits with similar mutation characteristics are merged into continuous regions.
Based on the regions, MPAuzz schedules mutation operators through an MPA-based optimization mechanism. The scheduling problem is formulated as a multidimensional search problem, where the operator selected for each mutation region is one dimension of the candidate solution. The staged search process of MPA is used to balance global exploration of new operator combinations and local exploitation of combinations that have produced satisfying coverage feedback.
We evaluated MPAuzz on four binary protocol implementations covering MQTT, DTLS, DNS, and CoAP, and compared MPAuzz with AFLNet and StateAFL. The results show that MPAuzz improves test case validity, branch coverage, and vulnerability discovery efficiency substantially. The main contributions of this paper are as follows:
-
1.
We propose MPAuzz, a greybox fuzzing framework for binary protocols that combines feedback-based mutation region exploration with adaptive mutation operator scheduling. This design reduces invalid mutations caused by protocol-format violations and improves the efficiency of coverage exploration.
-
2.
We design a mutation position exploration method that partitions protocol messages at bit-level granularity. The method classifies message regions as mutable, restricted, or immutable according to program responses and protocol-format feedback, thereby providing region-specific constraints for subsequent mutation.
-
3.
We formulate mutation operator scheduling as a multidimensional optimization problem and solve it using an MPA-based staged search strategy. The scheduler uses coverage and response feedback to update operator combinations for different mutation regions, balancing exploration and exploitation throughout fuzzing.
-
4.
We evaluate MPAuzz on four representative protocol implementations. Compared with AFLNet and StateAFL, MPAuzz achieves higher branch coverage and more effective vulnerability discovery in the experiments.
Related work
Mutation-based fuzzing
Greybox fuzzers exemplified by AFL have uncovered numerous security vulnerabilities. Its derivatives such as AFLnwe (Natella and Pham 2021), AFLNet, StateAFL, and NSFuzz (Qin et al. 2023) are applicable to vulnerability discovery in binary protocol implementations. The tools employ mutation-based fuzzing, and do not require testers to predefine input formats. Instead, the tools mutate seed messages using operators such as bitflip to generate test cases for fuzzing.
The AFL workflow is shown in Algorithm 1. Before the fuzzing process begins, AFL initializes the seed queue SeedQueue and the error queue ErrorQueue. SeedQueue stores the seeds selected for mutation, whereas ErrorQueue stores the test cases that cause the target program to crash. The fuzzing process consists of three stages:
-
1.
Seed Selection (Lines 1–4). The fuzzing process maintains a prioritized seed queue, which holds the test cases that will be sent to the target program. The queue is initially constructed based on a user-provided seed corpus, and the seeds are selected from the queue for fuzzing. The queue is continuously updated during the fuzzing process.
-
2.
Seed Mutation. The selected seeds undergo mutation to generate new test cases. This stage consists of two sub-stages: a) Deterministic Mutation (Lines 5–10). In this phase, a predefined set of deterministic mutation operators (as shown in Table 1) is applied. A mutation operator op is selected and applied sequentially at each position pos of the seed. The mutation operator is applied as defined by the mutation Operate L/S, where Operate represents the type of mutation, L denotes the length of the operation (i.e., the number of bits mutated), and S represents the step size (i.e., the offset of the mutation in the input). For example, the mutation operator bitflip 1/1 flips each bit of the test case, while interest 8/8 replaces each byte position in the test case with a predefined “interesting value”. b) Havoc Mutation (Lines 11–22). In this phase, the number of Havoc mutations applied to a seed is determined based on the seed’s energy value score. Each Havoc mutation involves a large number of random mutations. For each random mutation, a mutation operator and position are randomly selected and applied to the current test case. This stage is designed to thoroughly explore the target program’s execution paths.
-
3.
Execution & Feedback (Lines 23–31). The mutated test cases are sent to the target program for execution, and the execution results are monitored. If the test case triggers a new code path, it is marked as interesting and added to the SeedQueue as a candidate seed for further mutation. If the program crashes or hangs, the test case is added to the ErrorQueue to reproduce the error.
AFL and its extensions (such as AFLnwe and AFLNet) primarily rely on random exploration or heuristic methods. The sequential operations (i.e., deterministic mutation) and equiprobable random operations (i.e., Havoc mutation) do not adequately consider the selection of mutation positions and the scheduling of mutation operators, and they often produce a large number of malformed test cases.
Mutation strategies for binary protocols
Binary protocols use binary encoding and eliminate redundant characters such as newline characters, spaces, and delimiters. The compact data structures enhance encoding efficiency, improve parsing performance, and increase processing throughput.
To effectively identify vulnerabilities in binary protocol programs, some researchers have proposed optimization strategies for mutation position exploration and mutation operator scheduling.
The exploration of mutation positions directly affects the effectiveness of subsequent fuzzing. For instance, when performing fuzzing on binary protocol target programs, test cases are typically generated by mutating binary messages that conform to the protocol format. However, as shown in Line 6 of Algorithm 1, during the deterministic mutation phase, fuzzers mutate each position in the message sequentially, although different positions may have different mutation effects. As illustrated in Fig. 1, an MQTT protocol request message includes fields such as Msg Len, Protocol Name Length, and Client ID Length. If the fields are mutated randomly, the mutation may lead to abnormal boundary determination, and the server may fail to provide proper responses.
Representative studies on mutation position exploration include ProFuzzer (You et al. 2019), Snipuzz (Feng et al. 2021), REDQUEEN (Aschermann et al. 2019), and GREYONE (Gan et al. 2020). ProFuzzer performs byte-by-byte mutation on the input fields to identify their type and semantics, and guides mutation based on feedback information. Snipuzz mutates fields suitable for mutation by inferring from the target program’s responses, significantly reducing the search space and improving fuzzing efficiency. REDQUEEN tracks the comparison instructions in the program, and considers a position to have mutation value if the position’s modification reveals a new execution path. GREYONE drives fuzzing through taint analysis, locates critical mutation positions based on data flow characteristics, and evaluates the mutation value of different positions. However, these approaches involve program analysis, which introduces substantial overhead and affects fuzzing efficiency.
Furthermore, when applying the methods to fuzzing binary protocol programs, the fixed granularity of field divisions (usually byte-level) may ignore some key fields. For example, in the MQTT message shown in Fig. 1, the Header Flags field’s high 4 bits determine the message type, while the low 4 bits serve as flags. Byte-level granularity cannot finely distinguish these bit-level fields, rendering effective mutation difficult. Additionally, the methods do not consider the impact of mutation operator scheduling on fuzzing.
Mutation operator scheduling refers to selecting the most appropriate mutation operation (such as arithmetic addition/subtraction, bit flipping, constant replacement, block deletion/insertion, etc.) based on the semantics of the target position (e.g., length fields, flags, checksums). A reasonable mutation operator can significantly improve the effectiveness of the mutation process. Studies such as CMFuzz (Wang et al. 2021), DARWIN (Jauernig et al. 2022), and SeamFuzz (Lee et al. 2023) have examined mutation operator scheduling. Since mutation operators vary significantly in their effectiveness during fuzzing, the operators need to be scheduled based on observed performance during the fuzzing process (Rajpal et al. 2017).
CMFuzz uses a context-based multi-armed bandit (MAB) algorithm to select appropriate mutation operators for different seeds. However, the method only considers static characteristics of the seeds and does not provide comprehensive analysis. DARWIN employs evolutionary strategies to optimize the probability distribution of mutation operators, simulating the biological evolutionary process to dynamically adjust the mutation strategy. Compared with traditional uniform random selection methods, the method does not require manual parameter adjustments, thus avoiding poor fuzzing results due to improper configuration. However, DARWIN optimizes a mutation operator probability distribution for the target program without considering structural differences among input seeds, which may degrade mutation performance for certain seed formats.
SeamFuzz automatically captures the input features of seeds and applies differentiated mutation strategies for different seeds. Some studies have considered the combined effects of mutation positions and mutation operators. For example, PosFuzz (Zou et al. 2023) constructs an Effective Position Distribution for each mutation operator based on historical performance of mutation positions, using the Good-Turing frequency estimation method. This distribution maps input byte positions to selection probabilities. A higher probability value indicates a greater likelihood that mutation at the position will trigger a new path. However, the method does not fully consider the diversity of the mutation process and mutation positions. It relies on historical statistical information, and tends to repeatedly mutate effective positions that are already known. The positions that have not been adequately explored may get insufficient mutation resources, which limits the effectiveness of the exploration.
Marine predator algorithm
The Marine Predators Algorithm (Faramarzi et al. 2020) is a metaheuristic optimization algorithm inspired by the foraging behavior of marine predators in nature. MPA mimics the foraging strategies of predators in the marine environment, where predators adjust their behavior through encounters and captures of the prey. The core idea of the algorithm is to dynamically adjust the step size and migration strategy to balance broad exploration of the solution space (global exploration) with fine-grained exploitation of promising regions (local exploitation).
MPA simulates the predator’s foraging behavior by dynamically switching between Lévy flights (long-distance jumps) and Brownian motion (small-step fine search) to achieve comprehensive exploration of the solution space. Specifically, MPA describes the population state through Elite (current best solution) and Prey (candidate solution) matrices during the search process, and dynamically adjusts the search step size based on the relative velocity between the predator and prey.
MPA has three stages: early, middle, and final stages. In the early stage, the predator performs large-scale exploration using the Brownian motion strategy, where larger step sizes help broadly explore the solution space and avoid local optima. In the middle stage, the algorithm balances exploration and exploitation. Part of the population continues global exploration, while the rest gradually shifts toward local exploitation of promising regions. In the final stage, MPA focuses on precise local exploitation by performing high-precision search near the optimal solution. The staged exploration strategy enhances global search capability while maintaining stable convergence as the algorithm approaches the optimal solution.
MPA has been successfully applied to many engineering optimization fields, such as pressure vessel design and welding beam optimization, and it demonstrates good applicability and robustness. MPA’s core advantage lies in the dynamic balancing of exploration and exploitation behaviors based on the optimization process. This mechanism is realized through adaptive step size adjustment and stage transition strategies, rendering MPA highly effective in handling complex optimization tasks and indicating strong application potential.
Mutation scheduling in MPAuzz is formulated as a joint optimization problem that assigns mutation operators to multiple message regions on the basis of region-specific constraints and inter-region dependencies. A multi-armed bandit strategy is well suited to settings in which each arm represents an independent action with an independently observable reward. In binary protocols, however, the effect of mutating a region often depends on other regions. Specifically, the operator selected for a region and the resulting change to that region’s content or length may require corresponding updates to related regions. For example, if an insertion, deletion, or overwrite operation changes the size of a payload region, the corresponding length field must be recalculated. Otherwise, the generated test case may violate the protocol format and be rejected before reaching deeper program logic. Therefore, treating each region as an independent arm may produce structurally invalid test cases. Particle swarm optimization (PSO) can search over combinations of mutation operators, but its velocity-based update mechanism may cause the population to concentrate prematurely on a limited set of combinations when early coverage gains are dominated by only a few mutation regions. In contrast, MPA organizes the search into an early exploration stage, a middle stage that balances exploration and exploitation, and a final exploitation stage. This staged search process is consistent with the requirements of fuzzing. The scheduler first evaluates diverse operator combinations and then progressively refines combinations that provide effective coverage feedback while satisfying region-specific mutation constraints.
Design of MPAuzz
Overview
To address blind position exploration and insufficient operator scheduling in existing binary protocol fuzzing, we designed MPAuzz. The method partitions the message into mutation regions for differentiated mutation. It further schedules mutation operator combinations using an MPA-based staged optimization strategy, where scheduling decisions are driven by region-specific constraints, coverage feedback, and historical mutation effectiveness. By balancing exploration of new operator combinations and exploitation of effective ones, MPAuzz reduces invalid test case generation and improves fuzzing efficiency.
MPAuzz is a greybox fuzzer developed on the basis of the AFL framework. It leverages coverage information collected during the fuzzing process to effectively guide the fuzzing. AFL adopts a blind strategy combining deterministic sequential mutations and Havoc random mutations, and often generates invalid test cases discarded by the target program due to illegal formats. In contrast, MPAuzz, through effective mutation position exploration and metaheuristic mutation operator scheduling, not only determines the mutation value for each region but also dynamically schedules mutation operators for efficient fuzzing. The main workflow of MPAuzz is shown in Fig. 2.
In MPAuzz, before fuzzing starts, tools such as afl-gcc or afl-clang instrument the source code of the System Under Test (SUT). These instrumentation tools wrap the compilation process of GCC or Clang to insert coverage-tracking code at the entry points of basic blocks, enabling accurate tracking of execution paths and discovery of new paths.
The goal of protocol fuzzing is typically to test the protocol server system, and the fuzzer usually acts as the client. MPAuzz extracts the request payload of the target protocol sent to the server from packet capture files (PCAP) as initial seeds, forming the seed corpus. Each seed corresponds to a protocol message.
During seed selection, MPAuzz initializes the candidate queue and selects seeds from this queue for mutation following an AFL-style queue scheduling strategy. Specifically, seeds that have previously increased coverage or triggered abnormal responses are retained in the queue and given further mutation opportunities. During mutation, each selected seed is treated as a protocol message. The mutation position exploration module analyzes the message to identify mutable, restricted, and immutable regions, and the mutation operator scheduling module selects region-aware mutation operators to generate test cases.
The mutation position exploration module divides the message payload at bit-level granularity and applies simple mutation operations sequentially to each bit position. Specifically, for a given message, only one bit is mutated at a time. The mutated bit is then concatenated with the unmutated parts of the message to form a complete message, which is sent to the target for testing. Based on the response from the target program and the compliance of the message structure, the mutation properties of each bit position are determined. Subsequently, according to predefined feature classification rules, bit positions are categorized as mutable, restricted, or immutable. For example, if mutating a particular bit results in a normal program response, the bit is classified as a mutable bit. Adjacent bits with similar mutation properties are then merged into continuous regions. Compared with traditional methods that apply uniform mutations across a message, MPAuzz partitions the mutation regions and determines the type of each region based on the feedback from mutated messages. This approach provides effective guidance for subsequent mutations and reduces the generation of invalid test cases.
MPAuzz uses the Marine Predators Algorithm for mutation operator scheduling. The mutation operator scheduling module treats the selection and scheduling of mutation operators as a multidimensional optimization problem, simulating the dynamic interaction between predator and prey. Each mutation region is viewed as a dimension in the space, and the mutation operators correspond to different values along that dimension. In this way, the mutation operator scheduling process is modeled as a predator–prey chase, aiming to iteratively optimize and find the best operator combination for the current mutation region.
During the mutation scheduling process, MPAuzz employs a three-stage adaptive search mechanism to optimize region-aware mutation operator combinations. In MPAuzz, a mutation region denotes a contiguous bit-level segment identified by the feedback-based mutation position exploration module. Such a region may correspond to a protocol field or sub-field, but it is derived from mutation feedback rather than predefined field boundaries or manual protocol parsing.
Based on these regions, a mutation operator combination is defined as a region-wise operator assignment vector \(S = [op_1,op_2,...,op_k]\), where k is the number of mutation regions and \(op_i\) denotes the mutation operator assigned to the i-th region. Therefore, the term operator combination in MPAuzz refers to an ordered and region-specific assignment of mutation operators. Each region can select the operators permitted by its mutation type and region-specific constraints. For example, immutable regions are excluded from mutation, mutable regions may select an operator from the available mutation operators, and restricted regions must be mutated in accordance with the corresponding protocol constraints.
The objective of mutation scheduling is to search for a feasible and effective operator combination that improves coverage feedback while preserving test case validity. In the early stage, the historically best operator combination is treated as the predator, while candidate operator combinations are treated as prey, enabling broad exploration of potential operator-region mappings. In the middle stage, MPAuzz balances the exploration of new operator combinations and the exploitation of historically effective ones. In the final stage, the scheduler performs local search around the historically best operator combination by changing the operator assignments of only one or a few regions, that is, by modifying only one or a few components of the combination while keeping the remaining components unchanged. A candidate operator combination is retained only if it satisfies the region-specific constraints and improves coverage feedback, thereby improving branch coverage while preserving test case validity.
MPAuzz applies the most suitable mutation operator for each mutation, avoiding blind operator selection. This strategy not only improves the quality of test cases but also effectively avoids getting trapped in local optima, maximizing mutation efficiency. Finally, based on feedback information such as changes in branch coverage and whether anomalies are triggered, MPAuzz evaluates and optimizes the mutation operator combination, efficiently generating new test cases.
Test cases mutated from the seeds are sent to the protocol SUT via network sockets. Test cases that increase branch coverage are considered valuable for further exploration and are added to the candidate queue for reuse. During test case execution, the anomaly monitoring module tracks the SUT’s runtime status, recording errors such as hangs and crashes. Test cases that trigger errors are stored in the error case repository, which aids in analyzing the causes of vulnerabilities.
By combining global exploration of new operator combinations with local exploitation of known efficient combinations, MPAuzz dynamically adapts effective operator combinations for different mutation regions, generating high-quality test cases that significantly enhance the overall efficiency and effectiveness of fuzzing.
Feedback-based mutation position exploration module
The mutation position exploration module addresses two core issues. First, the module fully utilizes the seeds to analyze potential mutation positions. Second, the module evaluates the value of mutation positions while controlling resource consumption. The mutation position exploration module in MPAuzz is designed based on response information, and the specific process is illustrated in Fig. 3.
The module first divides the binary message into bit-level granularity, forming an initial set of candidate mutation bits {\(b_1\), \(b_2\),..., \(b_k\)}. The core goal of the module is to explore the influence of mutating each bit position on the behavior of the target program. During this process, the bitflip mutation operator, which has a relatively low computational cost, is prioritized for exploration.
The module sequentially selects a bit position, applies the bitflip mutation operator to the bit, and keeps the other bits unchanged. The mutated test case is then sent to the target program. By monitoring the request message and the target program’s runtime status, the feedback from the target program is obtained, and the relationship between the mutated bit and its adjacent bits is evaluated. The feedback information is classified into three categories in this study:
Normal Feedback: The target program runs normally without observable anomalies, such as abnormal return codes or memory error logs, indicating that the bit mutation did not disrupt the normal protocol interaction.
Format Anomaly Feedback: The target program does not crash but responds abnormally or times out. Upon analysis with protocol parsing tools like Tshark, errors such as length field mismatches or unrecognized protocol names may be detected. This feedback indicates that the mutation violates the protocol format constraints, and mutation at this position should be avoided. Such format anomaly feedback requires protocol parsing tools to understand the message format of the protocol under test.
Fatal Anomaly Feedback: The mutation causes the target program to crash (e.g., null pointer dereferencing, buffer overflow) or to fail to terminate within a predefined timeout. This indicates that the mutation triggered a serious error, and the associated test case is highly valuable for analyzing mutation patterns and identifying similar vulnerabilities. However, during the exploration phase, the likelihood of directly triggering fatal anomalies through simple mutations (such as bitflip) on individual bit positions is relatively low.
On the basis of the feedback, the mutation position exploration module classifies mutation regions of the protocol message into three categories:
Mutable Region: These regions can be freely mutated during fuzzing (e.g., main payload of the message).
Restricted Region: These regions must adhere to the protocol format constraints during mutation (e.g., length fields, checksums). Blind mutations, such as randomly modifying length values without adjusting related data, would generate invalid test cases.
Immutable Region: These regions involve fields such as protocol names and function codes, which are prohibited from mutation. For example, the protocol name is essential for protocol recognition, and blindly mutating it would prevent the message from being correctly parsed. Function codes often control protocol state transitions, and any changes to the fields can disrupt the fundamental logic of protocol interaction.
Each mutation region is a contiguous sequence of bits with the same mutation type. To accurately determine the mutation type of each bit in a message, the mutation position exploration module uses a feedback-based classification rule, which combines both direct and indirect feedback information. Direct feedback is based on observable information such as program responses, while indirect feedback requires external tools (such as protocol parsing tools) to identify anomalies. Based on the feedback for each test case, the mutation type of each bit is determined. The feature classification rules are shown in Table 2.
According to the classification rules, if the response triggered by the mutation of a certain bit is normal, the bit is identified as a mutable bit. If the mutation results in an abnormal message format, the bit is regarded as a restricted bit. When the mutation occurs in control fields such as the protocol name, function code, or header fields (e.g., type or version) and causes the protocol analysis tool to report an error, the bit is considered immutable.
After determining the mutation type of each bit in the message, a region merging algorithm traverses all the bits. Adjacent bits with the same mutation type are merged into a continuous mutation region. The detailed process of mutation region exploration is described in Algorithm 2.
The algorithm first divides the binary message at the bit level, where each element in the BitList represents a single bit. The test cases are then generated sequentially based on each bit and sent to the target program. According to the feedback information, the mutation type of each bit is determined following the feature classification rules. Finally, adjacent bits with identical mutation types are merged into a single mutation region, and the mutation type is consistent with the type of the bits inside the region.
Mutation scheduling module based on marine predator algorithm
The mutation position exploration module divides a message into multiple mutation regions, and identifies the type of each region. Based on the information, the mutation operator scheduling module selects appropriate mutation operators for each region on the basis of historical fuzzing experience. Essentially, mutation scheduling is an iterative optimization problem, and the optimal mutation operator for each region must be continuously explored during the fuzzing process to determine the mutation direction and select the most effective operator.
Traditional mutation operator scheduling methods face two challenges. The first is the local optimum trap, where the scheduling strategy may prematurely converge to a seemingly effective combination of operators while neglecting potentially better ones. The second challenge is the exploration and exploitation balance. Exploration refers to trying new combinations of operators to discover high-value regions, while exploitation focuses on prioritizing historically effective operator combinations to quickly improve coverage. Although random selection enhances exploration by continuously using new operators, it is inefficient. Conversely, a purely greedy strategy yields short-term gains but easily falls into local optima. Therefore, an effective scheduling strategy must dynamically adjust the proportion between exploration and exploitation across different fuzzing phases.
To address the aforementioned challenges, MPAuzz incorporates the core principles of the Marine Predators Algorithm and proposes a mutation operator scheduling mechanism. The optimization of mutation operator combinations is modeled as a dynamic “predator–prey” interaction process. Current historically optimal operator combination \(S_{elite}\) acts as the predator, representing a verified effective strategy, while the candidate operator combination \(S_{curr}\) serves as the prey, symbolizing unexplored strategies. The predator guides the prey’s movement through an interaction process, simulating the prey’s generation of new positions while evading capture. The interaction enables the mutation strategy to dynamically alternate between broadly exploring new combinations and elaborately adjusting existing ones.
The effectiveness of a mutation operator combination is evaluated using branch coverage as the objective function. An adaptive three-stage search mechanism is employed to efficiently explore and optimize operator combinations, thereby determining effective mutation directions. The workflow of the scheduling module is illustrated in Fig. 4. First, the scheduling strategy is determined according to the current fuzzing progress, and the mutation operator combination is dynamically updated. The updated combination is then applied to the inputs, and the generated test cases are executed. Based on the observed changes in coverage, the best mutation operator combination is iteratively updated. This process repeats until the maximum number of iterations is reached, and the optimal operator combination is then retained for subsequent fuzzing.
In the mutation process, a mutation operator combination can be represented by a k-dimensional vector \(S = [op_1,op_2,...,op_k]\), where k denotes the total number of mutation regions derived from the seed and \(op_i\) denotes the mutation operator assigned to the i-th region in the current mutation iteration. Based on the identified mutation region types, different mutation rules are applied. Immutable regions are excluded from mutation, operators can be freely selected for mutable regions, and restricted regions must be mutated in compliance with protocol constraints.
In binary protocols, restricted fields such as length fields are often used to define message boundaries. When mutating these fields, it is necessary to simultaneously adjust their associated regions, referred to as influence regions, which are constrained by the restricted field. The range of an influence region is determined by the semantic rules of the protocol. For instance, the value of a length field specifies the number of bytes in the subsequent data field. It is important to note that the criteria for defining restricted regions and influence regions differ. A restricted region is categorized based on its mutation properties, while an influence region is identified according to its semantic dependencies.
The relationship between a restricted region and its influence region forms a restricted region combination. The most common combinations can be classified into two types:
Restricted region + immutable region: This combination frequently appears in cases such as a protocol name length field (restricted region) paired with a protocol name field (immutable region), as seen in the MQTT protocol’s Protocol Name Length and Protocol Name. Since this combination directly affects protocol recognition, to maintain the stability of the protocol format, the restricted region should be treated as immutable.
Restricted region + mutable region: This combination typically occurs with message length fields (restricted regions) and message payload fields (mutable regions). When mutating such combinations, the content and the length of the mutable region should be adjusted according to the semantics of the restricted field, thereby ensuring the validity of the message.
MPAuzz applies a repairing step to restricted regions after mutation. Length-related restricted regions are a representative case. Such a region usually contains a value that describes the byte length of an associated influence region. During mutation-region analysis, MPAuzz identifies the dependency between the length region and its corresponding influence region, and records the original representation of the length value in the message. If the influence region is immutable, the scheduler disables direct mutation of the corresponding length region to avoid breaking the protocol structure. If the influence region is mutable, MPAuzz first mutates the influence region, recalculates its byte length, and then updates the length region accordingly. For nested length dependencies, inner regions are repaired before outer regions to ensure the final message remains structurally consistent. Other restricted regions, such as checksum fields, can also be repaired when corresponding protocol-specific rules are available.
Multi-layer nested restricted region combinations are common. For example, in the MQTT protocol illustrated in Fig. 1, the Msg Len field’s influence region includes both Protocol Name Length and Client ID Length, which respectively correspond to the “restricted region + immutable region” combinations and “restricted region + mutable region” combinations. When handling such nested structures, mutation operations must adhere to the semantic constraints of each restricted field. For instance, the value of Msg Len must accurately match the size of its influence region to ensure the overall structural validity.
MPAuzz is an extension of the AFL framework and inherits AFL’s mutation operators, including Bitflips, Arithmetic, and Havoc, among others. For each mutation region, there are m optional mutation operators, with index values ranging from 0 to m-1 (where 0 indicates that no mutation is applied to the region, and the other values correspond to the operator index).
Considering dynamic exploration and exploitation characteristics of fuzzing, MPAuzz introduces a three-stage optimization logic for the scheduling of mutation operator combinations.
High-speed exploration stage. This stage emphasizes global exploration, and new combinations of mutation operators are comprehensively tested to enhance diversity and discover potential high-value regions.
Balanced coordination stage. This stage seeks to balance exploration and exploitation, and well-performing operator combinations are refined while exploring new ones.
Low-speed exploitation stage. This stage focuses on local exploitation, and computational resources are spent on fine-tuning the most effective operator combinations identified in the previous stages.
Each stage has distinct objectives and adjustment strategies for operator selection, ensuring that the fuzzing process effectively maintains an optimal balance between global search and local optimization throughout its lifecycle. The following sections provide detailed descriptions of the three stages.
In this study, the increment of branch coverage is used as the feedback evaluation function, denoted as F(S). Current best operator combination \(S_{elite}\) is regarded as the predator, while current candidate combination \(S_{curr}\) represents the prey. The continuous update of candidate combinations adopts an element-wise (Hadamard) operation, denoted by \(\odot\), as shown in Equation (1). This operation multiplies corresponding elements of the two vectors to achieve local adjustments in each dimension within the combination.
stage 1: High-speed exploration stage (Early stage)
At the early stage of fuzzing, global exploration of potentially effective operator combinations is required to avoid premature convergence to local optima, which would slow the growth of branch coverage. This stage simulates the scenario in the MPA where the prey moves faster than the predator. At this point, the historically optimal mutation operator combination (predator) has not yet stabilized, so Lévy motion is employed to achieve wide-range exploration of operator combinations, while an adaptive weight \(\omega\) is introduced to dynamically adjust the step size.
The update formulas for operator combinations in this stage are given in Equations (2) and (3). Equation (2) defines stepsize as the step-size controller, which dynamically adjusts the magnitude of operator updates to fit the varying needs of exploration and exploitation at different fuzzing stages. Equation (3) specifies the update rule for wide-range operator combination exploration during this stage.
A random vector \(R_L\) following the Lévy distribution (\(\alpha = 1.5\)) simulates large-scale exploratory movements, enabling transitions to untested operators (e.g., switching from Bitflip to Arithmetic). The adaptive weight \(\omega\), defined in Equation (4), balances the effectiveness of operator combinations, while P is a constant coefficient controlling exploration intensity. To prevent isolated local searches and leverage group experience, a social dynamic term SocialTerm, defined in Equation (5), aggregates the historical information of other candidate combinations to guide updates of the current combination. This mechanism accelerates convergence and reduces ineffective random jumps.
By generating diverse operator combinations during the high-speed exploration stage, MPAuzz can rapidly cover a wide range of mutation strategies and store the initially effective operator combinations \(S_{elite}\) for subsequent refinement.
stage 2: Balanced coordination stage (Middle stage)
During the mid-stage of fuzzing, it is essential to balance exploration and exploitation. In other words, it is necessary to fine-tune already effective operator combinations while maintaining the capacity to explore new ones. This stage corresponds to the MPA scenario where the predator and prey move at similar speeds. Having accumulated enough promising operator combinations, more computational resources can be allocated to exploitation, i.e., prioritizing historically well-performing combinations to improve path discovery efficiency. However, a certain degree of exploration must still be maintained to look for potentially better combinations.
To achieve this, candidate combinations are divided into two groups. One group focuses on exploitation (fine-tuning \(S_{elite}\)) and the other on exploration (introducing new combinations). Brownian motion is introduced to enhance local optimization precision. The update formulas for exploiting well-performing combinations are given in Equations (6) and (7).
A random vector \(R_B\) following Brownian motion introduces small-scale perturbations around the current elite combination. In Equation (6), \(stepsize_i\) measures the direction and magnitude by which the current operator choice in the i-th region should move toward the neighborhood of \(S_{elite,i}\). The neighborhood of the elite combination refers to candidate operator combinations that retain most of the effective region-operator assignments in \(S_{elite}\), while only slightly modifying the operator choices of a small number of regions. Therefore, the formulation constrains the update around the current elite combination and enables controlled local refinement of operator combinations that have already produced promising coverage gains.
Equation (7) updates the current operator choice by combining three factors. The term \(\omega \cdot S_{elite,i}\) preserves the influence of the best historical combination. The term \(P \cdot CF \odot stepsize_i\) controls the adjustment scale according to the convergence stage. The constant P controls the overall perturbation strength, while CF determines how aggressively the scheduler should modify the current combination.
The convergence factor CF, defined in Equation (8), decreases quadratically as fuzzing progresses. A larger CF in the earlier iterations allows broader local adjustments, while a smaller CF in later iterations forces the scheduler to make finer changes. The fitness value of an operator combination is repeatedly evaluated through the generated test case’s coverage gain and response validity. Therefore, Equations (6)-(8) implement a controlled local exploitation mechanism rather than an unconstrained random search.
In the middle stage of fuzzing, the scheduler has already accumulated operator combinations that provide promising coverage feedback. Therefore, instead of regenerating a completely new operator combination vector from scratch, MPAuzz refines the existing promising combinations in the neighborhood of the historically best combination \(S_{elite}\). Local refinement means that most effective region-operator mappings in \(S_{elite}\) are preserved, while only a small number of regions are selectively adjusted. Specifically, the scheduler may replace the mutation operator assigned to these regions with another feasible operator permitted by the region type and protocol constraints, and then evaluate whether the updated combination improves coverage while maintaining response validity.
In this mechanism, the update is anchored to the historically best combination \(S_{elite}\), and the Brownian perturbation \(R_B\) introduces small-scale variations around \(S_{elite}\). Meanwhile, the convergence factor CF adaptively controls the update magnitude as fuzzing progresses. This design enables MPAuzz to preserve effective region-operator mappings while selectively adjusting uncertain or under-optimized regions. As a result, the scheduler can improve coverage more stably, reduce disruptive mutations, and maintain a higher validity of test cases.
For the bottom 50% underperforming combinations, Lévy motion is used to explore untested mutation operators such as attempting Interest value replacement near immutable regions using the same update formulas as in stage 1.
This stage thus optimizes effective operator combinations while discovering new ones, maintaining both efficiency and diversity in the middle stage of fuzzing.
stage 3: Low-speed exploitation stage (Final stage)
In the final stage of fuzzing, the focus shifts to local optimization of operator combinations to maximize branch coverage and ensure the validity of test cases while minimizing ineffective mutations. This stage corresponds to the MPA scenario where the predator moves faster than the prey, indicating that \(S_{elite}\) lies near the global optimum.
Here, Brownian motion is used to enable \(S_{curr}\) to rapidly converge toward the optimal combination \(S_{elite}\). Additionally, an enhanced social learning mechanism amplifies the group’s collaborative effect, allowing candidate combinations to align more quickly and stably with the optimal one. The stepsize used in this stage is the same as that in Equation (6), while the operator combination update rule is defined in Equation (9).
In this update formula, the reinforced social learning term \(0.3 \cdot \left( S_{elite,i} - S_{curr,i} \right)\) accelerates convergence by guiding each candidate combination toward the optimal one, making this stage particularly suitable for fine-tuning optimal mutation operator combinations during the final stage of fuzzing.
The mutation process of MPAuzz, as illustrated in Algorithm 3, begins by defining the mutation operator combination space based on the mutation regions and their characteristics identified from feedback analysis. Before each seed test, a mutation operator combination is randomly selected as the initial best combination and executed in the target program. Code coverage serves as the evaluation metric to assess the rationality of the mutation direction.
Subsequently, the algorithm dynamically adjusts the mutation strategy according to the fuzzing progress, performing stage-based optimization of mutation operator combinations to progressively approach the optimal mutation.
Following this strategy, MPAuzz leverages historical fuzzing experience and employs a coverage-guided, stage-wise dynamic optimization mechanism to refine mutation operator combinations. The adaptive optimization effectively enhances the effectiveness of the generated test cases and significantly improves the overall fuzzing efficiency.
Implementation of MPAuzz
MPAuzz adopts a hybrid development architecture combining Python and C to fully leverage the strengths of both languages. The underlying core modules, such as real-time monitoring of binary protocol entities and memory resource management, are implemented in C to ensure efficient tracking and precise resource control of the target program. The upper-layer logic, including fuzzing process scheduling and the implementation of novel mutation strategies, is developed in Python. Based on the core principles of the AFL framework, MPAuzz integrates a feedback-driven mutation position exploration module and an MPA-based mutation scheduling module, forming a complete and closed-loop fuzzing system. The detailed procedure of MPAuzz is presented in Algorithm 4.
The mutation framework of MPAuzz is specifically optimized based on AFL. The mutation position exploration module leverages the packet parsing functionality provided by Tshark (Merino 2013) to perform protocol format analysis on the input seeds with the Scapy (secdev 2024) tool. Each input seed is divided at the bit level, and bitwise mutation testing is used to obtain mutation properties. Adjacent bits with identical mutation properties are merged into a mutation domain. Subsequently, the mutation scheduling module, which is based on the MPA, assigns the optimal mutation operator to each mutation domain.
The use of Tshark and Scapy provides practical protocol-format feedback for common binary protocols. When the target protocol is proprietary, undocumented, or unsupported by existing parsers, MPAuzz can still use target responses and coverage feedback to infer whether a mutation preserves the protocol structure and contributes to path exploration. However, the precision of restricted and immutable region identification may decrease because indirect format feedback is usually incomplete. In such cases, MPAuzz functions as a feedback-guided greybox fuzzer with limited protocol-semantic information. Integrating dynamic taint analysis, grammar inference, and protocol reverse engineering is a promising direction for reducing the dependency on protocol analysis tools.
To balance mutation strategy exploitation and exploration, MPAuzz adopts a preset and adaptive configuration for its scheduling parameters. Initially, the testing time is evenly divided among three scheduling stages, with stage boundary parameters set as \(\alpha = 1/3\) and \(\beta = 2/3\), partitioning the testing process into three stages: \([0, \alpha )\), \([\alpha , \beta )\), and \([\beta , 1]\). As fuzzing progresses, \(\alpha\) and \(\beta\) are dynamically updated based on the branch coverage gain per unit time (\(\Delta cov/\Delta t\)) of each stage. If a particular stage yields a significantly higher coverage gain, the system proportionally increases its time allocation. Conversely, if a stage exhibits diminishing returns or coverage saturation (i.e., near-zero growth), its time share is reduced so as to devote testing efforts to more productive stages.
This adaptive mechanism emphasizes global exploration during the early stage and focuses on high-yield strategies in the mid-to-final stages. As a result, it mitigates excessive exploration in the beginning while reducing inefficient attempts and waste of resources, thereby improving overall fuzzing efficiency.
Evaluation
To demonstrate the generality and effectiveness of MPAuzz, we selected four widely used binary protocol implementations covering protocols such as MQTT, DNS, and DTLS. The detailed information of the target programs is shown in Table 3.
MPAuzz adopts a greybox fuzzing approach. To evaluate its effectiveness, we selected AFLNet and StateAFL, two well-known greybox protocol fuzzers that are widely used in both academia and industry as baselines for comparison. Since both AFLNet and StateAFL are mutation-based fuzzers, we used the same seed corpus for all the fuzzers. The corpus was constructed from captured interaction traffic of the corresponding target programs. In addition, we extended AFLNet and StateAFL to support additional protocols that are not originally recognized by these tools (e.g., CoAP and MQTT).
Given the inherent randomness of fuzzing, performance may fluctuate. Therefore, for each selected target, we ran each fuzzer continuously for 24 h and repeated the experiment 10 times to evaluate long-term performance, convergence behavior, and possible plateau effects. All experiments were conducted on a machine equipped with an AMD Ryzen 7 9800X3D processor featuring 8 logical cores running at 4.7 GHz, with 32 GB of main memory, and operating under Ubuntu 20.04 LTS.
To further examine whether the performance gain comes from the MPA-based scheduling strategy, we introduce two scheduler variants for the validity and branch coverage experiments. Both variants keep the same mutation position exploration module, repairing rules, seed corpus, target programs, and execution budget as MPAuzz. The first variant, denoted as MPAuzz-MAB, replaces the MPA-based scheduler with a multi-armed bandit scheduler that treats each mutation operator as an arm and updates its selection probability according to feedback. The second variant, denoted as MPAuzz-PSO, replaces the MPA-based scheduler with a particle swarm optimization scheduler that searches operator combinations through velocity and position updates. The design helps analyze the influence of the mutation scheduling algorithm while keeping the other fuzzing components unchanged.
Validity of test cases
In the experiment, the generation of test cases primarily involved two processes: simple mutations performed by the mutation position exploration module, and targeted mutations applied to specific mutation regions by the mutation operator scheduling module.
Mutation position exploration was conducted to identify mutation regions, and the type of each region was determined based on feedback responses. Table 4 reports the distribution of valid and invalid test cases produced during the exploration phase and the subsequent scheduling phase. The Percent column denotes the proportion of valid test cases among all the test cases generated for each target and each method.
The validity of test cases was determined from both program responses and protocol parsing results. A test case was considered valid if the target program could parse and process the test case successfully and the protocol analysis tool did not report any format errors. Test cases that caused abnormal execution, such as crashes or timeouts, or produced protocol-format inconsistencies were classified as invalid.
Invalid test cases were generated when mutations affected fixed fields, such as function codes, protocol names, or length fields. Such mutations can prevent the target implementation from reaching deeper parsing or state-processing logic. After the exploration stage, the identified region types were therefore used to constrain operator selection in the scheduling stage, with the aim of complying with protocol specifications while maintaining mutation diversity.
Some invalid cases may also be generated when feedback is insufficient to distinguish semantic boundaries. For example, bits near field boundaries may be classified to an inappropriate mutation category, causing mutations to cross semantic boundaries and violate protocol format.
The results in Table 4 show that MPAuzz preserved a high proportion of valid test cases during mutation operator scheduling. For the four protocol entities, MPAuzz achieved an average valid-test-case ratio of 98.1%, compared with 83.1% for MPAuzz-MAB and 79.5% for MPAuzz-PSO. The valid-test-case ratio of MPAuzz exceeded 97% for every target, indicating that the improvement was consistent across different protocol implementations.
These results suggest that region-aware operator scheduling is important for maintaining protocol validity. A scheduler that treats operators independently may fail to capture dependencies between control fields, length fields, and their influence regions. A PSO-based scheduler, which searches operator combinations globally, may also favor operator combinations that increase coverage feedback while producing format-invalid messages. The staged MPA-based scheduler updates operator combinations under region-specific constraints. Immutable regions are excluded from mutation, restricted regions are handled together with their influence regions through repairing rules, and mutable regions still allow diverse operator choices. This design enables MPAuzz to reduce format-invalid test cases while preserving enough mutation diversity for coverage exploration.
Branch coverage analysis
Branch coverage is a standard metric for evaluating the exploration capability of fuzzers (Klees et al. 2018). It measures the number of program branches executed during fuzzing. Table 5 reports the average branch coverage of MPAuzz, AFLNet, and StateAFL over ten 24-hour runs. In this comparison, AFLNet and StateAFL are used as the baseline fuzzers. The comparison includes three metrics: coverage improvement, speed-up, and the Vargha-Delaney effect size (Neumann et al. 2015). Coverage improvement denotes the relative increase in the number of covered branches at the end of the 24-hour fuzzing runs. Speed-up measures how faster MPAuzz reaches a coverage level compared with the baseline fuzzer. A larger value indicates faster coverage growth. The Vargha-Delaney effect size measures the probability that a randomly selected run of MPAuzz achieves higher branch coverage than the baseline, where 0.5 indicates no difference and values closer to 1 indicate a stronger advantage for MPAuzz. Figure 5 shows the time-dependent coverage growth of the baseline tools and scheduler variants.
Table 5 shows that MPAuzz achieved higher branch coverage than AFLNet and StateAFL on all the targets. Relative to AFLNet, the average improvement was 38.3%, with the largest gain on Mosquitto (60.7%) and the smallest gain on Dnsmasq (25.2%). Compared with StateAFL, MPAuzz improved coverage by 26.5% on average, with per-target gains ranging from 13.8% to 37.1%. The speed-up results show a similar pattern. MPAuzz reached comparable coverage 3.47\(\times\) faster than AFLNet and 2.22\(\times\) faster than StateAFL on average. The Vargha-Delaney effect sizes were analyzed for the pairwise comparisons between MPAuzz and each baseline over repeated runs. Most values were at least 0.85, indicating that MPAuzz achieved higher coverage than the corresponding baseline in most runs.
Figure 5 shows the coverage-growth process over time. The curves indicate that MPAuzz generally increases branch coverage earlier and reaches a higher final coverage than the baseline fuzzers. This difference is especially obvious on Mosquitto and Libcoap, where preserving valid stateful messages helps the fuzzer reach deeper protocol-handling logic. On Dnsmasq, the coverage curves of MPAuzz and the scheduled variants become closer in the later hours, which is consistent with the relatively smaller coverage gain reported in Table 5. This result suggests that some Dnsmasq branches can also be reached by the baseline mutation strategies when execution time is sufficient.
Table 6 compares the effect of the scheduling strategy. MPAuzz outperformed both scheduler variants on all the targets, improving branch coverage by 7.8% over MPAuzz-MAB and 19.2% over MPAuzz-PSO on average. The smaller but consistent gain over MPAuzz-MAB suggests that selecting operators according to their individual historical feedback is insufficient for messages with interdependent regions. The larger gain over MPAuzz-PSO suggests that the PSO-based search is more prone to premature convergence. The trajectories in Fig. 5 show the same tendency: MPAuzz-MAB approaches MPAuzz in the early stage but gradually falls behind, whereas MPAuzz-PSO maintains lower branch coverage than MPAuzz on most targets.
Table 7 further separates the contribution of mutation position exploration and mutation scheduling. Under the same exploration condition, the exploration stage of MPAuzz discovered more branches than AFLNet on every target. For example, it reached 803.2 branches on Mosquitto and 707.4 branches on Libcoap, compared with 691.0 and 540.3 branches for AFLNet, respectively. The scheduling stage further improved coverage after the identification of mutation regions as the fuzzer selected operators according to region types and protocol constraints. The improvement introduced by scheduling was more evident on Mosquitto and Libcoap, whereas Dnsmasq and Tinydtls showed smaller gains. This suggests that region classification is useful for identifying promising mutation areas, while adaptive scheduling is especially helpful for reaching deeper paths that depend on valid protocol structure and state transitions.
Vulnerability discovery ability
MPAuzz demonstrates strong vulnerability-discovery performance, exposing abnormal program behaviors early in the fuzzing process. Its mutation position exploration module first partitions each input message into multiple mutation regions and classifies them according to feedback responses. Region-specific mutation constraints are then applied to reduce invalid modifications. Subsequently, the mutation operator scheduling module selects suitable operators for each region, improving the validity and fault-triggering effectiveness of the generated test cases.
To evaluate vulnerability discovery effectiveness more accurately, we instrumented the target programs with AddressSanitizer (ASAN) (Serebryany et al. 2012), enabling us to capture a broader set of memory-related exceptions. Therefore, counting crashes triggered by each fuzzer provides a more comprehensive measure of the fuzzer’s abilities to expose security-relevant faults.
Table 8 reports the average number of crashes triggered during the 24-hour runs. MPAuzz produced more crashes than AFLNet and StateAFL on all the target programs. The largest gain was observed on Mosquitto, where MPAuzz triggered 87.8 crashes on average, compared with 3.9 for AFLNet and 43.2 for StateAFL. A similar improvement was observed on Tinydtls, where MPAuzz reached 63.4 crashes, whereas AFLNet and StateAFL reached 11.6 and 39.6 crashes, respectively. The improvements on Dnsmasq and Libcoap were more moderate but remained consistent. These results indicate that feedback-based mutation-region identification and MPA-based region-aware operator scheduling reduce parser-level rejections and increase the likelihood of reaching vulnerable states in protocol implementations.
Figure 6 further characterizes the temporal distribution of crash discovery. On Mosquitto and Libcoap, MPAuzz began accumulating crashes earlier than the baselines and maintained a clear lead throughout the experiment. On Dnsmasq, all the fuzzers exposed crashes at an early stage, but MPAuzz continued to uncover additional crashes later in the experiment. On Tinydtls, the crash-growth curves of MPAuzz and StateAFL were closer, indicating that state modeling was also effective for this target. Nevertheless, MPAuzz still achieved the highest final crash number. Overall, the results show that region-aware mutation and adaptive scheduling improve both the scale and continuity of crash discovery.
We also recorded the time of first crash for each fuzzer as an evaluation metric for vulnerability discovery efficiency. As shown in Table 9, MPAuzz generally exposed crashes earlier than the baselines. On Mosquitto, AFLNet did not trigger a crash within the given time, whereas MPAuzz exposed the first crash in 32 min and StateAFL exposed the first crash in 134 min. On Tinydtls, MPAuzz reduced the time to first crash to 15 s, compared with 73 s for AFLNet and 36 s for StateAFL. On Libcoap, MPAuzz found the first crash in 5 min, substantially earlier than 17 min for StateAFL and 95 min for AFLNet. Dnsmasq was the only exception, where StateAFL triggered the first crash in 21 min, slightly earlier than 24 min for MPAuzz. This result is consistent with the similar crash-growth trends observed for Dnsmasq in Fig. 6. Overall, the time-to-first-crash results show that MPAuzz improves vulnerability-discovery efficiency on most targets while achieving the highest final crash number across all the targets.
We further analyzed the triggered crashes and validated the proof-of-concept (PoC) inputs. The analysis showed that the anomalies detected in Mosquitto and Libcoap correspond to the medium-severity vulnerability CVE-2021–28166 and the high-severity vulnerability CVE-2024–46304, respectively. As illustrated in Fig. 7, the Mosquitto crash was caused by a null pointer dereference in the acl__check_dollar function of the Mosquitto server, where pointer validity was not checked properly. This vulnerability was triggered when an authenticated client sent a fuzzer-generated, mutated SUBSCRIBE message before the server issued a PUBLISH message, resulting in a null pointer dereference on the server side.
These findings demonstrate that MPAuzz can identify real-world security vulnerabilities induced by abnormal protocol-state sequences, showing its ability to fuzz complex stateful protocols.
Discussion and limitations
The experimental results show that region-aware mutation and adaptive mutation-operator scheduling can improve the effectiveness of binary-protocol fuzzing on the target implementations. These results also clarify the conditions under which MPAuzz is most likely to be effective. In its current design, MPAuzz takes advantage of parser-assisted feedback from tools such as Tshark and Scapy to identify mutable, restricted, and immutable message regions. For proprietary, undocumented, or insufficiently supported protocols, such feedback may be unavailable or incomplete, which can reduce the accuracy of region inference. In such cases, MPAuzz can still rely on runtime responses and coverage feedback to prioritize promising mutations, but its structural understanding of the protocol may remain incomplete and may not fully reflect protocol-specific semantics or field dependencies.
Second, the repairing mechanism for restricted regions is applicable only when the dependency between a restricted region and its influence region can be identified. The current implementation mainly supports automatic repair for length-related restricted regions. When the corresponding influence region and the original representation of the length value are available, MPAuzz recalculates the byte length after mutation and updates the length region before sending the test case. More complex constraints, such as checksums, authentication-related fields, or state-dependent fields, usually require protocol-specific repairing rules. When such rules are unavailable, MPAuzz avoids directly mutating the corresponding restricted regions and filters out invalid test cases to prevent malformed inputs from entering the seed queue.
Third, although each fuzzing experiment was set to 24 h and repeated ten times, the evaluation is still limited to four protocol implementations. Additional targets, seed sets, and longer experiments may provide further evidence on how MPAuzz behaves under different circumstances.
Conclusion
This paper proposes MPAuzz, a Marine Predators Algorithm driven greybox fuzzer for binary protocols. MPAuzz addresses two practical limitations of existing protocol fuzzers: the difficulty of identifying effective mutation regions in structured binary messages, and the lack of region-aware mutation operator scheduling.
MPAuzz introduces a feedback-based mutation position exploration module that divides protocol messages into mutable, restricted, and immutable regions. It then models operator selection as a staged multidimensional optimization problem. This design allows the fuzzer to explore diverse operator combinations in the early stage, refine effective combinations in the middle stage, and exploit high-value combinations in the final stage.
Experiments on multiple protocol implementations show that MPAuzz improves branch coverage and vulnerability discovery considerably compared with AFLNet, StateAFL, and scheduler variants using MAB or PSO. These findings suggest that combining protocol-aware region classification with adaptive MPA-based operator scheduling is a practical way to improve binary-protocol fuzzing. Future work will reduce reliance on external protocol parsers and strengthen support for proprietary protocols with complex field dependencies.
Data availability
All public dataset sources are as described in the paper.
References
Aschermann C, Schumilo S, Blazytko T (2019) Redqueen: Fuzzing with input-to-state correspondence. NDSS. pp 1–15
Chandler J, Wick A, Fisher K (2023) Binaryinferno: A semantic-driven approach to field inference for binary message formats. NDSS,
Faramarzi A, Heidarinejad M, Mirjalili S et al (2020) Marine predators algorithm: a nature-inspired metaheuristic. Expert Syst Appl 152:113377
Feng X, Sun R, Zhu X (2021) Snipuzz: Black-box fuzzing of iot firmware via message snippet inference. In: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security. pp 337–350
Fioraldi A, Maier D, Eißfeldt H, et al (2020) \(\{\)AFL++\(\}\): Combining incremental steps of fuzzing research. In: 14th USENIX workshop on offensive technologies (WOOT 20)
Gan S, Zhang C, Chen P, et al (2020) \(\{\)GREYONE\(\}\): Data flow sensitive fuzzing. In: 29th USENIX security symposium (USENIX Security 20), pp 2577–2594
Jauernig P, Jakobovic D, Picek S (2022) Survival of the fittest fuzzing mutators. Darwin, arXiv:2210.11783 arXiv preprint
Klees G, Ruef A, Cooper B (2018) Evaluating fuzz testing. In: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security. pp 2123–2138
Lee M, Cha S, Oh H (2023) Learning seed-adaptive mutation strategies for greybox fuzzing. In: 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE). IEEE, pp 384–396
Luo Z, Yu J, Zuo F (2023) Bleem: Packet sequence oriented fuzzing for protocol implementations. In: 32nd USENIX Security Symposium (USENIX Security 23). pp 4481–4498
Luo Z, Liang K, Zhao Y (2024) Dynpre: Protocol reverse engineering via dynamic inference. Proc. NDSS. pp 1–18
Lyu C, Ji S, Zhang C, et al (2019) \(\{\)MOPT\(\}\): Optimized mutation scheduling for fuzzers. In: 28th USENIX security symposium (USENIX security 19), pp 1949–1966
Merino B (2013) Instant traffic analysis with Tshark how-to. Packt Publishing, Birmingham
Natella R (2022) Stateafl: Greybox fuzzing for stateful network servers. Empir Softw Eng 27(7):191
Natella R, Pham VT (2021) Profuzzbench: A benchmark for stateful protocol fuzzing. In: Proceedings of the 30th ACM SIGSOFT international symposium on software testing and analysis. pp 662–665
Neumann G, Harman M, Poulding S (2015) Transformed vargha-delaney effect size. International Symposium on Search Based Software Engineering. Springer, pp 318–324
Pham VT, Böhme M, Roychoudhury A (2020) Aflnet: A greybox fuzzer for network protocols. 2020 IEEE 13th International Conference on Software Testing. IEEE, Validation and Verification (ICST), pp 460–465
Qin S, Hu F, Ma Z et al (2023) Nsfuzz: Towards efficient and state-aware network service fuzzing. ACM Transactions on Software Engineering and Methodology 32(6):1–26
Rajpal M, Blum W, Singh R (2017) Not all bytes are equal: Neural byte sieve for fuzzing. arXiv preprint arXiv:1711.04596
Schiller E, Aidoo A, Fuhrer J et al (2022) Landscape of iot security. Computer Science Review 44:1–18
secdev (2024) Scapy: Packet crafting for python2 and python3. https://scapy.net
Serebryany K, Bruening D, Potapenko A, et al (2012) \(\{\)AddressSanitizer\(\}\): A fast address sanity checker. In: 2012 USENIX annual technical conference (USENIX ATC 12), pp 309–318
Wang X, Hu C, Ma R et al (2021) Cmfuzz: context-aware adaptive mutation for fuzzers. Empir Softw Eng 26(1):10
You W, Wang X, Ma S (2019) Profuzzer: On-the-fly input type probing for better zero-day vulnerability discovery. In: 2019 IEEE symposium on security and privacy (SP). IEEE, pp 769–786
Zalewski M (2016) American fuzzy lop. http://lcamtuf.coredump.cx/afl/
Zhang X, Zhang C, Li X et al (2024) A survey of protocol fuzzing. ACM Comput Surv 57(2):1–36
Zou Y, Zou W, Zhao J et al (2023) Posfuzz: augmenting greybox fuzzing with effective position distribution. Cybersecurity 6(1):11
Acknowledgements
Not applicable.
Funding
This research was supported by the National Natural Science Foundation of China (Grant No.62172432)
Author information
Authors and Affiliations
Contributions
Chuan Jiang: Conceptualization, Methodology, Software, Writing - Original Draft. Zheng Hong: Writing - Review & Editing, Validation, Supervision. Guomin Zhang: Formal analysis, Investigation. Yuxuan Li: Software. Jinbang Gu: Resources, Data Curation.
Corresponding author
Ethics declarations
Competing interests
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/
About this article
Cite this article
Jiang, C., Hong, Z., Zhang, G. et al. Binary protocol greybox fuzzing driven by marine predators algorithm. Cybersecurity 9, 214 (2026). https://doi.org/10.1186/s42400-026-00646-8
Received:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1186/s42400-026-00646-8