Discovering and Repairing Flaws in C Binaries Without Requiring Codebase and Instrumentation

We propose PatchBin, an approach and tool for identifying and removing BO vulnerabilities and validating the effectiveness of applied patches. All three actions are deployed by accessing the binary, i.e., without codebase access and code instrumentation. To this end and to address the challenges of Section 3, the approach uses a combination of different techniques, namely $(i)$ fuzzing: to detect BO vulnerabilities, validate the effectiveness of patches, and check whether they have not introduced new vulnerabilities, $(ii)$ reverse engineering: through reverse data-flow static analysis to identify the bPUT’s binary code involved in the exploited BOs, $(iii)$ automatic program repair: through instruction punning and binary trampolines to rewrite the binary code directly, thus removing the BOs. The trampoline concept is applied for the first time in software security to correct code and remove vulnerabilities. And, $(iv)$ regression testing: which, combined with fuzzing, allows validation of patches’ effectiveness.

Figure 2 gives an overview of the approach architecture and its four main modules: Vulnerability Exploiter, Vulnerability Identifier, Binary Patcher, and Patch Validator. The first and fourth modules respect the fuzzing phases, with the fourth also including regression testing, the second the reverse engineering, and the third the APR part. In a nutshell, the approach fuzzes a non-instrumented bPUT to detect BOs and their corresponding exploits (test cases), while simultaneously storing the associated binary traces and memory states, including CPU register contents. Next, reverse engineering, using a bottom-up data-flow analysis approach over the binary traces and the memory states, determines the sensitive sink of the exploited BOs, as well as the code involved in them. All collected data is used to generate appropriate fixes, which are then applied directly to the bPUT to remove the vulnerabilities, using trampolines and static code rewriting. The validation process, through fuzzing and regression testing, tests the new bPUT using the exploits (provided from the previous fuzzing phase) to confirm that the patch process was successful, i.e., that the program no longer crashes or hangs. It will also generate new test cases to ensure that no other exploits can break the fixes or exploit new vulnerabilities introduced by them. In the next sections, we detail the modules of PatchBin.

The first phase of our approach (marked as $1$ in Figure 2) involves discovering vulnerabilities by exploiting them. To do so, the module receives the non-instrumented binary (bPUT) and a set of initial benign test cases that allow bPUT to run normally. Afterwards, it starts the fuzzing activity, mutating the initial test cases to generate new ones and executing them with bPUT. This aims to increase code coverage and identify test cases that cause crashes or hangs in bPUT, i.e., exploit vulnerabilities. These, which we call exploits, are saved for later use by the other modules. During the fuzzing session, the module monitors its activity to stop the ongoing session when a predefined target number of crashes is reached or if no new crashes are observed during a specific (and predefined) time period.

The Vulnerability Identifier ($2$ in Fig. 2) is responsible for confirming the BOs that occurred and finding the code associated with them. During this phase, it collects as much information as possible about the sensitive sink call, including the arguments, their sizes and data types, and their location within the code. However, for that, the module needs to obtain the binary traces for the exploited BOs, capturing the information of what is being executed (e.g., CPU registers, concrete values of variables, memory states), which later will be used by the Vulnerability Debugger to find the locations within bPUT where the exploited BOs reside.

The module starts by disassembling bPUT and retains the PLT (Procedure Linkage Table) section, which contains the information (memory addresses and offsets) of the standard C library functions (e.g., strcpy, puts) called throughout the bPUT’s code. Also, the names of the user functions are extracted from the .text section (which contains the program’s actual code), and checkpoints are set at the beginning of these functions. This activates the possibility of reversing them and easily switching between functions during the debugging step (explained next). Afterwards, the module creates a vulnerability debugging session for each exploit encountered in the previous phase by executing the following four steps.

This module (marked as $3$ in Fig. 2) is responsible for creating and applying the fixes to remove the BOs found, using a static binary rewriting technique. The result is a new patched bPUT. Based on the sensitive sink information gathered by the previous module, for each BO, the Binary Patcher chooses the appropriate fix template from the Fixes Templates database, fills the fix with the data it received, generates the fix’s binary, and then applies the fix. These actions are performed by the following tasks: Fix generation, and Fix application.

The Patch Validator ($4$ in Fig. 2) verifies if the fixes successfully removed the BOs. It considers a vulnerability fixed only if none of the exploits associated with it (stored in the Exploits database) break the fix and crash the new bPUT, nor new test cases derived from the exploits.

Initially, using the exploits could be enough to consider the fix successful. However, to ensure its validation, this module uses the exploits as the initial set of test cases. It uses the Vulnerability Checker once again in order to initialise a new fuzzing session that will mutate these exploits, trying to find new vulnerable paths and new exploits, i.e., attempting to break the fixes or find a new vulnerability that the fixes might have introduced. If a fix is broken, an alarm is generated, which contains the information about the vulnerability collected during the process (e.g., target function, sensitive sink) for further manual inspection.

To better evaluate PatchBin, we tested it on 2 datasets – synthetic and real –, with the first allowing us to validate the tool and the second assessing it in real-world applications. The synthetic dataset comprises vulnerable C programs, some designed specifically to test the tool with particular code and others sourced from the NIST SARD [36] repository. For the second dataset, we used real-world applications and modified some of them to introduce BO vulnerabilities. This allows us to test our tool in scenarios with applications containing multiple code paths and a larger number of lines of code. Our modifications were minor, involving either replacing secure sensitive sink calls with their vulnerable versions or adding a vulnerable call before the return of an output.

Also, to verify how PatchBin performs with security protection mechanisms, all programs were compiled twice – with and without canary [8] protection. Then, using the two versions, we evaluate the effectiveness of the patching module and the fix templates we built. Finally, to measure the performance overhead introduced by the fix, we run both the patched and the vulnerable bPUT 5 times with good inputs, which will not trigger an overflow (otherwise, the vulnerable binary would crash). For each binary, we recorded the execution time and computed the average across 5 runs.

The synthetic dataset contains 695 C programs, where 685 were from SARD, a repository with vulnerable and non-vulnerable programs used for testing purposes, and 10 were created by us. In order to evaluate the effectiveness of the tool, we manually analysed the SARD programs and classified them as vulnerable and not vulnerable. The vulnerable cases contain at least one sensitive sink supported by the tool. In turn, in the other 10 applications (created by us), each application contains at least 3 sink calls (distinct or repeated), and we tried to cover the most common programming practices seen in real applications (e.g., nested if statements and loops).

Table 1 summarises the characterisation of this dataset. In sum, the dataset contains 360 vulnerable (Vul) and 335 not-vulnerable (N-Vul) cases, divided by the functions supported by PatchBin. We conducted three types of tests using the dataset: One-Vulnerability, Multi-Vulnerabilities, and No-Vulnerabilities. With the first two tests, we aim to measure the tool’s effectiveness and performance. With the last test, we intend to check how the tool behaves with safe programs.

To test our tool in a more robust environment, we downloaded 6 applications from GitHub and SourceForge and ran two types of tests: one with vulnerable applications that we forced to be vulnerable, and another with applications whose security state we did not know.

For the first test, since we need specific vulnerable functions to be available in the application and to test the Vulnerability Identifier and Binary Patcher modules, we modified two applications from the dataset (TicTacToe [15] (App 1) and Simple Password Generator [7] (App 2)). So, we replaced the secure sensitive sink they contained with their insecure alternatives, thereby creating vulnerabilities that our tool could identify and fix. Listing 4 shows, for example, the modifications made to TicTacToe, where we replaced fgets by gets.

Both applications were compiled with and without canaries, and all tests followed the same methodology as in Section 6.2. The results presented in Table 3 are very similar to the ones obtained with synthetic applications (Section 6.2). Both applications were successfully patched and validated.

For the second test, we used 4 applications, whose characterisation is shown in Table 4, columns Files and LoC. We compared the results of PatchBin (last 2 columns) with those of CorCA [24] tool (4th and 5th columns), a tool that finds potential BO vulnerabilities in the source code of C programs, and then repairs the code with fixes, after confirming that the potential vulnerabilities are effective. Both tools handled the 4 applications, meaning they processed 59K LoC across 109 files. PatchBin performed slightly better than CorCA, fixing 3 more BOs. It can be seen that the tool was able to fix all BOs it found, while CorCA had to decide which of the 44 potential vulnerabilities were real BOs. The 6 real vulnerabilities identified by CorCA were also found by our tool, and the other 3 BOs identified only by PatchBin were checked manually.

Based on the results of both tests, we can answer question Q6 and demonstrate our tool’s ability to discover and correct vulnerabilities even in more robust environments without needing codebase access or code instrumentation. Also, with the results of the second test, we can respond to Q7, i.e., PatchBin performs better than other code repair tool.

Static and dynamic analysis are the two widely used methodologies to detect software vulnerabilities. Static analysis [38] is commonly used in software development and is performed in a non-runtime environment, testing and evaluating the application’s code (source or binary) for patterns that may indicate vulnerabilities. As such, it relies heavily on an updated set of patterns and rules to function properly; otherwise, its accuracy and precision will be significantly affected by the high levels of false positives and negatives it produces. Dynamic analysis [38], on the other hand, is performed at runtime, evaluating the application’s running state and manipulating it in order to discover new vulnerabilities. Although it can expose complex vulnerabilities that would not be easily found with static analysis, it can only analyse parts of the code that are actually executed.

Fuzzing is the most used dynamic analysis technique, which tries to achieve maximum code coverage by generating new test cases. It helps discover and explore new code paths while monitoring the application to detect any possible errors and crashes. AFL [50] is one of the best-known grey-box fuzzers (a mix of static and dynamic analysis), and it uses compile-time instrumentation along with a genetic algorithm to discover new test cases that could trigger new internal states, thus improving the functional coverage of the code. AFL++ [17][18], an improved version of AFL, supports faster instrumentation modules such as LLVM [21] and QEMU [4], as well as new and better mutators such as MOPT [30], a mutation scheduling to discover vulnerabilities more efficiently. SmartSeed [29] improves fuzzing efficiency by enhancing the genetic algorithm that mutates the seed files provided by the users to create several new inputs that will later be used to test the target application in order to try to trigger potential crashes. The fuzzer leverages a machine learning model to learn and generate high-value binary seeds. Ispoglou et al. presented FuzzGen [26], a library fuzzing tool that automatically synthesises fuzzers for complex libraries in a given environment. Rustamov et al. [39] designed DeepDiver, a hybrid fuzzing tool that combines AFL++ with concolic execution, whose objective is to discover vulnerabilities deep within the code while negating roadblock checks, a limitation found in other existing hybrid fuzzing frameworks, and thus allowing the fuzzer to explore new execution paths that can trigger vulnerabilities deep within the binary. Vadayath et al. [48] identified a set of vulnerability properties that improve the precision of static vulnerability detection and the scalability of dynamic vulnerability detection, and created a prototype, Arbitrer, that implements some of these properties using a hybrid analysis technique.

Automatic program repair (APR) consists of the automatic correction of software errors (e.g., faults, bugs) without human intervention by healing the software state and/or repairing its behaviour [37, 32], the latter being more effective since it modifies the software code. This is a challenging task, as it requires identifying the code to be repaired and the appropriate fix, and applying the fix without introducing new faults. Various approaches were proposed to repair program source code. Some works, in order to discover the errors to be corrected, require instrumenting the code during the compilation process [45, 28], others, instead of repairing, give suggestions on how to fix the errors found [19, 42], and still others fix the code but do not validate that the correction is effective and does not introduce new errors [44, 11, 35]. Just a few validate the correction, for example, verifying if the patch terminates correctly [1]. Yet, recently, repair AI-based approaches have emerged, showing promising results in this field [12, 5, 22].

Shahriar et al. [42] proposed a rule-based approach to identify and mitigate BO in C/C++ programs, addressing both simple and complex code forms, ranging from unsafe library function calls to pointer usage in control-flow structures. Klieber et al. [27] presented a technique to repair the source code of C programs by using an intermediate language representation to invalidate potential violations of spatial memory safety, in contrast to traditional program repair techniques that focus on preventing attackers from exploiting vulnerabilities. Inácio et al. [24] presented CorCA, a tool that extracts vulnerable program slices from the original program, fixes them, and then fixes the original program after validating the fixed program slices. Bader et al. [3] address the issue of automatically fixing common bugs by learning from past fixes. Schulte et al. [40] established a benchmark for different binary rewriting techniques. They concluded that rewriters that resort to intermediate representations of the code are unsuitable for generality and reliability. Interesting results from other rewriters were found, including a decision tree model trained on the features they identified to predict whether a specific rewriter suits a target binary. One rewriting technique is to rewrite the binary code directly. Schulte et al. [41] proposed an approach of this technique to repair binary programs directly in embedded and mobile systems using evolutionary computation algorithms. Another type of technique not included in such a benchmark is the use of existing fragments of binary code as a reference to repair functional and security bugs [43].

The approach we propose directly repairs the binary code without requiring its source code and code instrumentation, and allows for the identification of vulnerabilities and the locations where the code must be fixed. Additionally, our approach validates the fixed code, ensuring that no new flaws have been introduced during the repair process.