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.

A laser-based, table-top instrument is constructed to perform femtosecond soft x-ray transient absorption spectroscopy. Ultrashort soft x-ray pulses produced via high-order harmonic generation of the amplified output of a femtosecond Ti:sapphire laser system are used to probe atomic core-level transient absorptions in atoms and molecules. The results provide chemically specific, time-resolved dynamics with sub-50-fs time resolution. In this setup, high-order harmonics generated in a Ne-filled capillary waveguide are refocused by a gold-coated toroidal mirror into the sample gas cell, where the soft x-ray light intersects with an optical pump pulse. The transmitted high-order harmonics are spectrally dispersed with a home-built soft x-ray spectrometer, which consists of a gold-coated toroidal mirror, a uniform-line spaced plane grating, and a soft x-ray CCD camera. The optical layout of the instrument, design of the soft x-ray spectrometer, and spatial and temporal characterization of the high-order harmonics are described. Examples of static and time-resolved photoabsorption spectra collected on this apparatus are presented.

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.

Sub-Nyquist sampling has received a huge amount of interest in the past decade. In classical compressed sensing theory, if the measurement procedure satisfies a particular condition known as Restricted Isometry Property (RIP), we can achieve stable recovery of signals of low-dimensional intrinsic structures with an order-wise optimal sample size. Such low-dimensional structures include sparse and low rank for both vector and matrix cases. The main drawback of conventional compressed sensing theory is that random measurements are required to ensure the RIP property. However, in many applications such as imaging and array signal processing, applying independent random measurements may not be practical as the systems are deterministic. Moreover, random measurements based compressed sensing always exploits convex programs for signal recovery even in the noiseless case, and solving those programs is computationally intensive if the ambient dimension is large, especially in the matrix case.

The main contribution of this dissertation is that we propose a deterministic sub-Nyquist sampling framework for compressing the structured signal and come up with computationally efficient algorithms. Besides widely studied sparse and low-rank structures, we particularly focus on the cases that the signals of interest are stationary or the measurements are of Fourier type. The key difference between our work from classical compressed sensing theory is that we explicitly exploit the second-order statistics of the signals, and study the equivalent quadratic measurement model in the correlation domain. The essential observation made in this dissertation is that a difference/sum coarray structure will arise from the quadratic model if the measurements are of Fourier type. With these observations, we are able to achieve a better compression rate for covariance estimation, identify more sources in array signal processing or recover the signals of larger sparsity.

In this dissertation, we will first study the problem of Toeplitz covariance estimation. In particular, we will show how to achieve an order-wise optimal compression rate using the idea of sparse arrays in both general and low-rank cases. Then, an analysis framework of super-resolution with positivity constraint is established. We will present fundamental robustness guarantees, efficient algorithms and applications in practices. Next, we will study the problem of phase-retrieval for which we successfully apply the sparse array ideas by fully exploiting the quadratic measurement model. We achieve near-optimal sample complexity for both sparse and general cases with practical Fourier measurements and provide efficient and deterministic recovery algorithms. In the end, we will further elaborate on the essential role of non-negative constraint in underdetermined inverse problems. In particular, we will analyze the nonlinear co-array interpolation problem and develop a universal upper bound of the interpolation error. Bilinear problem with non-negative constraint will be considered next and the exact characterization of the ambiguous solutions will be established for the first time in literature. At last, we will show how to apply the nested array idea to solve real problems such as Kriging. Using spatial correlation information, we are able to have a stable estimate of the field of interest with fewer sensors than classic methodologies. Extensive numerical experiments are implemented to demonstrate our theoretical claims.