Programs are not immutable. In fact, most programs are under constant changes for security (e.g, vulnerability fix) and non-security (e.g., new features) reasons. These code changes, however, expose great security challenges. Android packers, as a set of code transformation techniques, are gaining increasingly popularity among Android malware, rendering existing malware detection techniques obsolete. Despite the importance of this emerging trend (app packing), no comprehensive study has ever been conducted to help the community understand the status quo of Android packing and unpacking techniques.

Android third-party libraries (TPL) that can provide complementary functionalities and ease the app developments have become one of the major sources of Android security issues due to the pervasive outdatedness issue. Prior efforts have been made to understand and mitigate specific types of security issues in TPLs, but there exists no generic solution to solve the issues and keep them up-to-date.

Binary Code Differential Analysis, a.k.a, binary diffing, is a fundamental analysis capability that aims to quantitatively measure the similarity between two given binaries and produce the fine-grained block level matching. It has enabled many critical security usages including patch analysis and malware analysis. Existing binary diffing techniques suffer from low accuracy, poor scalability, coarse granularity or require extensive labeled training data to function. A new technique is needed to accurately and efficiently perform binary diffing at a fine-grained basic block level.

This dissertation addresses these problems by presenting concepts, methods and techniques to perform generic Android packer analysis, automatically generate updates for outdated TPLs and propose an novel unsupervised deep neural network based program-wide code representation learning technique for binary diffing.

Binary diffing analysis quantitatively measures the differences between two given binaries and produces fine-grained basic block matching. It has been widely used to enable different kinds of critical security analysis. However, all existing program analysis and learning based techniques suffer from low accuracy, poor scalability, coarse granularity especially on COTS binaries which did not contains complete debug information. On the other hands, some learning based approaches require extensive labeled training data to function, so that precise labelled and representative dataset is needed to obtain great results. To surmount such limitations, in this paper, we come up with a novel learning based code representation generation approach to solve the binary diffing problem. We rely only on the code semantic information as well as the program-wide control flow structural information to generate block embeddings without supporting of any debug information. Furthermore, we propose a K-hop greedy matching algorithm to find the optimal diffing results using the generated block representations. We implement a prototype called DeepBinDiff and evaluate its effectiveness and efficiency with large number of binaries and real-world vulnerabilities. The results show that our tool could outperform the state-of-the-art binary diffing tools by large margin for both cross-version and cross-optimization level diffing. A case study for OpenSSL using real-world vulnerabilities further demonstrates the usefulness of our system.

Fuzzing, or fuzz testing, is an automated program testing technique aimed at uncovering security flaws in software. This method generates and injects crafted inputs into a Program-Under-Test (PUT) to monitor for abnormal runtime behavior, with the goal of identifying potential defects and vulnerabilities. A generic fuzzing framework involves two essential components that influence its testing performance: 1) a scheduler that determines the current optimal strategy for program state space exploration, and 2) a mutator that produces concrete inputs based on the scheduler's strategy.

In this thesis, we propose an enhanced fuzzing framework leveraging stochastic modeling and generative AI (genAI).

Firstly, we introduce an intelligent scheduler that models program execution traces as Markov Chain, with transitions between branches stochastically represented. A reinforcement learning algorithm allows the scheduler to refine its exploration strategy for more efficient and comprehensive testing of the PUT, by learning from outcomes of past explorations. We integrate this scheduler in a whitebox fuzzer/concolic executor, Marco, and evaluate it against state-of-the-art concolic executors on real-world programs, demonstrating Marco's superior performance.

Secondly, we propose to enhance the mutator using genAI. To fully reveal the potential of uncustomized, out-of-the-box large language models (LLMs) for producing high quality inputs for fuzzing, we conduct a comprehensive study of eight state-of-the-art (SOTA) LLMs, encompassing both large and small models from three LLM families. This study establishes a baseline for the fuzzing capabilities of uncustomized LLMs and provides insights for developing more effective collaboration strategies between conventional and LLM-based mutators. We also showcase the performance of an LLM-empowered greybox fuzzer, ChatFuzz, against state-of-the-art greybox fuzzers, demonstrating that ChatFuzz significantly improves coverage findings, and is comparable to or better than the baseline approach for vulnerability detection.

Finally, motivated to tackle the path divergence issue, where the input produced by the mutator diverges from the desired path selected by the scheduler, and inspired by LLMs' potential as intelligent mutators, we propose a path-corrective LLM-based mutator to further enhance fuzzing. Specifically, we identify path-divergent inputs and use specialized prompts to instruct the LLM to generate corrected inputs that follow the desired paths. We present encouraging preliminary results.

Modern commercial antivirus systems increasingly rely on machine learning to keep up with the rampant inflation of new malware. However, it is well-known that machine learning models are vulnerable to adversarial examples. Previous works have shown that ML malware classifiers are fragile to the white-box adversarial attacks. However, ML models used in commercial antivirus products are usually not available to attackers and only return hard classification labels. Therefore, it is more practical to evaluate the robustness of ML models and real-world AVs in a pure black-box manner. Since existing state-of-the-art malware classifications are quite vulnerable to our attacks, the next question is how to create a new architecture to make the malware classifiers more robust against different kinds of adversarial attacks, including Benign content appending, content relocation, and code randomization. Finally, memory-only malware has become more and more popular in recent years. Since they are not written on disks, it becomes important to recognize their presence in memory. Moreover, these malware samples may hide their process information in the system, we need a way to identify them fast and robustly.This dissertation addresses these problems by presenting insights, methods, and techniques on how to perform attacks and defenses on malware classification. Firstly, a black-box Reinforcement Learning based framework called MAB-Malware is developed to generate adversarial examples for PE malware classifiers and AV engines. It has a much higher evasion rate than other off-the-shelf frameworks. Secondly, a selective hierarchical BERT-based new classification architecture is proposed to automatically select malicious functions for malware classification that is robust against different attacks. Thirdly, a graph-based deep learning approach is presented to automatically generate abstract representations for kernel objects, with which we could recognize the objects from raw memory dumps in a fast and robust way.

Modern software development increasingly relies on software supply chains, with third-party libraries constituting a significant portion of many projects. However, the complexity of dependency relationships and the lack of transparency in software make identifying and fixing vulnerabilities challenging and costly. For example, the average cost of a Log4j incident response has reached $90,000, and nearly 40% of applications still use vulnerable Lo4j two years after the vulnerability was disclosed. A Software Bill of Materials (SBOM), which lists the dependencies used to build software, has been proposed to enhance software visibility and aid in vulnerability detection. Despite this, there is not yet an accurate SBOM generation solution for both source code and binary. Current SBOM generators focus solely on metadata and produce inconsistent SBOM files, while the existing SBOM generators for binary files are either too slow or inaccurate.

In this thesis, we propose an accurate and fast SBOM generation approach for both source code and binary. First, to improve SBOM generation for source code, we conducted a differential analysis to compare and understand how the existing SBOM generators work and why they behave so differently. We found that these generators support only a subset of common metadata, and their self-implemented parsers for metadata have incomplete syntax supports, leading to erroneous SBOM results. We propose using package managers to simulate dependency installation for metadata-based SBOM generation. Second, we introduce DeepDi, a novel graph neural network-based disassembler that is both accurate and efficient for better SBOM generation for binaries. Our study showed that disassembly is often the bottleneck of binary analysis tasks, consuming up to 90% of processing time. DeepDi improves efficiency by hundreds of times compared to commercial disassemblers and is as accurate or better than them. Third, to further improve the accuracy of SBOM generation from binaries, we propose GrassDiff, a novel learning-free graph-matching algorithm that effectively and efficiently identifies static-linked libraries in large binaries.

Binary analysis remains an indispensable technique in the landscape of cybersecurity. It provides a foundational layer of security by enabling the early detection of vulnerabilities and malicious code, thereby contributing to the overall integrity and resilience of software systems. However, the effectiveness of binary analysis is often challenged by the complexity of modern software, which can arise from various factors, such as the extensive use of optimization techniques and the lack of debug information. These factors complicate the analysis process, making it more difficult to accurately understand and assess the software’s behavior and potential security issues.

This dissertation delves into two advanced techniques in binary analysis: pseudocode diffing and binary pointer analysis. The first project proposes a pseudocode diffing technique that accurately and efficiently characterizes code changes between two different binary programs at a fine-grained pseudocode token level. This technique is applicable in various security scenarios, including code plagiarism detection, lineage analysis, and vulnerability and patch analysis.

The second project focuses on pointer analysis, a critical component in binary code reverse engineering. We propose a program analysis approach that jointly recovers points-to relations and data structures in binary code so that they can enhance each other. This technique can be leveraged in reconstructing a complete call graph of binaries that includes indirect call edges, which is the foundation of many downstream analyses such as binary code diffing and bug detection.

Deep learning has proven its effectiveness in a wide range of binary analysis tasks, such as function boundary detection, binary code search, function prototype inference, and value set analysis. Deep learning-based assembly language models, in particular, have garnered significant attention and delivered promising results. This dissertation presents approaches and evaluations for training assembly language models tailored to diverse security applications.

First, we introduce DeepBinDiff, an unsupervised technique for program-wide code representation learning. This approach leverages both code semantics and program-wide control flow information to generate basic block embeddings for fine-grained binary diffing.

Secondly, to enhance instruction representation and provide additional support for approaches like DeepBinDiff, we introduce PalmTree, a language model designed for generating general-purpose, high-quality instruction embeddings, which can be used to improve the downstream deep-learning models for various binary analysis applications.

Third, in light of more transformer-based assembly language models that have been proposed targeting different security downstream applications, each featuring unique architectural modifications and the introduction of novel pre-training tasks, we undertake a comprehensive evaluation of transformer-based models, including PalmTree, and their pre-training tasks in the context of four distinct security applications.

Lastly, based on the insights gained from our evaluations, we outline our forthcoming work, which focuses on a novel zero-shot learning approach for obfuscation detection. This is achieved through the re-use of the pre-training task of the assembly language model, with the expectation that it can deliver comparable performance to other supervised learning approaches.

Binary analysis is a critical discipline within the realm of cybersecurity and software development, focusing on the examination of compiled executable files – known as binaries – to understand their behavior, vulnerabilities, and overall functionality. Dynamic binary analysis emerges as a cornerstone in this field, enabling the real-time observation and manipulation of running binaries and gaining insight into program execution paths, memory status, system calls, and interactions with external resources. This method proves indispensable for identifying vulnerabilities such as buffer overflows, race conditions, and memory leaks, as well as for reverse engineering proprietary software, improving software performance, and enhancing overall system security.

In this dissertation, we propose to improve the performance of dynamic binary analysis by adding elasticity. Our key insight is that the runtime analysis should be aligned with the proportion of program states under examination.Simply put, the runtime analysis should only be performed when necessary to keep the overhead minimal.

First, we adopted the idea of elastic analysis to improve whole-system dynamic taint analysis. Compared to process-level taint analysis, the main barrier of applying whole-system dynamic taint analysis in practice is the large slowdown that can be sometimes up to 30 times. Elastic whole-system taint analysis strives to perform taint analysis as least frequently as possible while maintaining the precision and accuracy. Evaluation shows the prototype, DECAF++, achieves over 202\% speedup on various benchmarks.

Second, we present SymFit, a binary concolic execution with the benefit of elastic symbolic tracing and efficient symbolic expression management. Evaluation on real-world benchmarks showcases 10 times speedup over existing works. With the increased efficiency, we demonstrate a unique application of concolic execution by employing symbolic expressions for crash seed deduplication.

Third, we introduce SpecTaint, a Spectre-gadget detection tool that leverages the benefit of elastic taint analysis to track Spectre data flow pattern at runtime. The evaluation results indicate that it outperforms existing methods with respect to detection precision and recall and detect spectre gadgets in real-world applications like Caffe and Brotli.

Lastly, we present LogicMem, a novel method to enable VMI and memory forensics when the kernel profile is not available.

Analyzing software binaries can be helpful in tackling important problems such as plagiarism, malware or vulnerability detection. Detecting similarity between two binary functions coming from different sources can be done using binary code similarity detection. Existing approaches use Control-Flow graph information of binaries in some way or another i.e either graph matching or control-block embedding which is either slow or does not utilize all the information. In this work we propose novel way to use program dependency graph of functions to extract control and data dependency information and generate its embedding with help of Neural Network using this information. Measuring the distance between embedding of different binary functions can evaluate their similarity. Since this method does not rely on internal flow structure of the function it can be applied to more generally and is resilient to different compiler optimizations and heavy obfuscation techniques.