MODELING CYBERATTACK SCENARIOS AS A MARKOV DECISION PROCESS WITH A SEMANTICALLY CONSTRAINED ACTION SPACE

Abstract

A formal model for representing cyberattack scenarios as a Markov decision process is proposed, in which, unlike static attack graphs, the dynamics of system state changes depending on the executed attack steps are explicitly defined, while the set of admissible actions is formed considering semantic dependencies between steps, in particular AND and OR type dependencies. The proposed approach provides a temporal interpretation of scenarios through the time-to-compromise (TTC) metric and allows describing both simple and complex multi-step compromise trajectories. The model combines a dynamic MDP representation with an invariant graph representation of states, constructed using graph neural network mechanisms. The experimental study was conducted on a set of stochastically generated MAL-graphs aligned with open attack models and web datasets and includes a comparison with baseline graph-based methods and reinforcement learning methods without semantic constraints. The obtained results show that the proposed approach provides a substantial reduction of the average time to compromise and decreases the variance of results, which indicates improved learning stability. It is demonstrated that the introduction of a semantically constrained action set eliminates irrelevant transitions and significantly increases the share of successful compromise scenarios. The greatest gain is observed on deep multi-step attack trajectories dominated by AND dependencies, where the semantic structure of the graph has a decisive impact on the space of available decisions. The practical significance lies in the possibility of applying the model for quantitative evaluation of cyberattack scenarios, ranking of compromise trajectories and decision support, as well as integration into automated penetration testing systems and cyber training ranges.