Optimal Honeypot Allocation Using Core Attack Graph in Partially Observable Stochastic Games

Abstract

This paper presents a scalable solution for zero-sum, one-sided, partially observable stochastic games (Z-POSGs) in the realm of cybersecurity. Existing heuristic search value iteration (HSVI) methods often face significant challenges with scalability in large and complex networks. To overcome this limitation, we introduce an innovative approach that leverages core attack graphs summarized abstractions that streamline incremental strategy generation. This technique reduces the belief and action spaces, making it possible to manage large-scale networks more efficiently. By focusing the analysis on the core attack graph, our approach minimizes the necessity to process the entire network, leading to substantial reductions in time and memory requirements while maintaining solution accuracy. Our method achieves an average solution accuracy within an epsilon value of 0.68%. Additionally, experimental results show that the execution time on the core attack graph is reduced by around 45% compared to that on the original graph, showcasing its significant performance advantage. Furthermore, we successfully solved the largest instances, comprising up to 300 nodes, underscoring the scalability and efficiency of our approach in handling complex, large-scale networks. Comparative evaluations demonstrate that integrating core attack graphs with existing HSVI techniques not only enhances scalability but also preserves solution quality. These findings highlight the proposed method’s potential for effective and efficient application in large-scale cybersecurity networks, outperforming state-of-the-art solutions.

Keywords

• Partially observable stochastic games
• lateral movement
• dynamic honeypot allocation
• core attack graph