Efficient Query-based Analysis over Structured Representations for System Security
COM3 Level 2
MR21, COM3 02-61
Abstract:
Query-based analysis is a cornerstone of modern system security, supporting a wide range of applications such as data leak prevention, intrusion detection, and static application security testing. These applications rely on structured representations of system and program behavior to enable expressive and efficient querying. However, the complexity and scale of such representations often introduce severe performance bottlenecks, limiting the practicality of query-driven security analysis in real-world systems.
This thesis addresses these challenges through three complementary systems. We first present FlowMatrix, a GPU-based framework that models dynamic information flow tracking (DIFT) execution traces as linearly ordered graphs and reformulates taint propagation as matrix operations. We then introduce QuickSilver, an efficient provenance dependency query system designed for large-scale system auditing, which improves query performance by transforming provenance graphs into partially ordered graphs. Finally, we propose WARC, a static analysis system that leverages general program dependency graphs to identify implementation inconsistencies across WebAssembly (WASM) compilers and runtimes.
Collectively, this thesis demonstrates that systematically exploiting the structural properties of system representations is a powerful and general approach for improving the performance and scalability of security-oriented query systems.