The Automated Design of Network Graph Algorithms with Applications in Cybersecurity

Abstract

Graph representations and graph algorithms are commonplace in a wide variety of research domains, including computer and network security. Many problems can be expressed in terms of graphs in order to leverage the strengths of existing graph-based heuristics. Often, these applications employ general purpose, off-the-shelf graph algorithms that are agnostic of the particular problem domain. Customized heuristics can be developed that achieve improved performance by utilizing problem-specific knowledge, but this process can be expensive and time consuming. Hyper-heuristics can be used to automate this process to develop novel graph-based algorithms that are tailored to the specific application. This dissertation describes a number of contributions to the domains of evolutionary computation, hyper-heuristics, and cybersecurity. An evolutionary algorithm is combined with a graph partitioning approach to prescribe network access control configuration changes that reduce vulnerability to adversarial traversal while minimizing impact on legitimate users. A hyper-heuristic framework is detailed that automates the design and optimization of tailored graph algorithms and the potential of this framework is demonstrated on multiple network security applications. Graph generating algorithms are tailored to accurately model complex network behavior, both static and dynamic. Novel security metrics are produced that analyze network vulnerability to specific attack models. Graph partitioning heuristics are customized to reduce the application cost of network segmentation methods. Link prediction heuristics are automatically tailored for computer network anomaly detection applications. This work also contributes novel methods of improving hyper-heuristic performance on complex real-world applications by dynamically controlling the granularity of the heuristic search. Dynamic granularity control has the potential to improve the applicability and scalability of hyper-heuristic methods to a wide variety of application domains.