Exploring Answer Set Programming for Provenance Graph-Based Cyber Threat Detection: A Novel Approach

Abstract

Provenance graphs are useful and powerful tools for representing system-level activities in cybersecurity; however, existing approaches often struggle with complex queries and flexible reasoning. This paper presents a novel approach using Answer Set Programming (ASP) to model and analyze provenance graphs. We introduce an ASP-based representation that captures intricate relationships between system entities, including temporal and causal dependencies. Our model enables sophisticated analysis capabilities such as attack path tracing, data exfiltration detection, and anomaly identification. The declarative nature of ASP allows for concise expression of complex security patterns and policies, facilitating both real-time threat detection and forensic analysis. We demonstrate our approach's effectiveness through case studies showcasing its threat detection capabilities. Experimental results illustrate the model's ability to handle large-scale provenance graphs while providing expressive querying. The model's extensibility allows for incorporation of new system behaviors and security rules, adapting to evolving cyber threats. This work contributes a powerful, flexible, and explainable framework for reasoning about system behaviors and security incidents, advancing the development of effective threat detection and forensic investigation tools.