High-Performance Graph Computing and Application in Cybersecurity
Open AccessGraph is a natural representation for many real-world applications, such as road map, protein-protein interaction network, and code graph. The graph algorithms can help mine useful knowledge from the corresponding graphs, such as navigation on road map graph and vulnerability detection from code graphs. This dissertation strives to build fast and scalable graph analytics techniques and apply them to cybersecurity applications.Chapter 1 introduces the background of graph connectivity algorithms, graph neural networks, and graphs in cybersecurity applications. Later, it summarizes related works and highlights the challenges and contributions of this dissertation.Chapter 2 introduces iSpan, a fast spanning tree construction method for computing strongly connected component. iSpan consists of parallel, relaxed synchronization construction of spanning trees for detecting the large and small SCCs, combined with fast trims for small SCCs. The evaluations show that iSpan is able to significantly outperform current state-of-the-art DFS and BFS-based methods by average 18× and 4×, respectively.Chapter 3 describes Aquila, an adaptive parallel computation framework that covers a wide range of different highly optimized graph connectivity algorithms. Given a graph, Aquila first transforms the query if it can be answered with partial computation. During the computation, Aquila is able to greatly reduce the workload by up to 98%. Furthermore, Aquila identifies the irregular tasks in the connectivity algorithms and applies different parallel strategies for different tasks. As a result, Aquila significantly outperforms existing systems by orders of magnitude.Chapter 4 designs BugGraph, which performs source-binary code similarity detection in two steps. First, BugGraph identifies the compilation provenance of the target binary and compiles the comparing source code to a binary with the same provenance. Second, BugGraph utilizes a new graph triplet-loss network on the attributed control flow graph to produce a similarity ranking. The experiments on four real-world datasets show that BugGraph achieves 90% and 75% true positive rate for syntax equivalent and similar code, respectively, an improvement of 16% and 24% over state-of-the-art methods. Moreover, BugGraph is able to identify 140 vulnerabilities in six commercial firmware.Chapter 5 presents Vestige, a new compilation provenance identification system for binary code. Vestige builds a new representation of the binary code, i.e., attributed function call graph (AFCG), that covers three types of features: idiom features at the instruction level, graphlet features at the function level, and function call graph at the binary level. Vestige applies a graph neural network model on the AFCG and generates representative embeddings for provenance identification. The experiment shows that Vestige achieves 96% accuracy on the publicly available datasets of more than 6,000 binaries, which is significantly better than previous works. When applied for binary code vulnerability detection, Vestige can help to improve the top-1 hit rate of three recent code vulnerability detection methods by up to 27%.Most graph neural networks (GNNs) work on the classical attributed graph structure, while we observe that a nested graph structure is a more accurate representation for many practical applications. Observing no existing GNNs can directly learn on such graph structure by synchronizing both the outer and inner graphs, Chapter 6 designs NestedGNN, the first graph neural network for nested graphs. NestedGNN consists of three layers, i.e., inner GNN layers, nested graph layers, and outer GNN layers. We successfully build NestedGNN on top of four different types of traditional GNNs and evaluate with three case studies where NestedGNN is able to significantly improve the performance over traditional GNN models.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.