Source-linked AI summary
POIROT: Aligning Attack Behavior with Kernel Audit Records for Cyber Threat Hunting
Sadegh M. Milajerdi, Birhanu Eshete, Rigel Gjomemo, V. N. Venkatakrishnan
TL;DR
Threat hunting must determine whether CTI-described attack behavior occurred within large, noisy, and potentially evasive enterprise activity. POIROT builds query and provenance graphs from CTI correlations and kernel audits, then aligns them using an inexact graph-matching approach. It successfully detected evaluated attacks, including ten DARPA scenarios across three operating systems, while searching million-node graphs in minutes.
Problem
Threat hunting lacks robust ways to connect related CTI indicators across long periods of large, noisy logs when attackers mutate isolated artifacts.
Method
POIROT aligns a CTI-derived query graph with a kernel-audit provenance graph using approximate graph pattern matching and a novel similarity metric.
Results
POIROT successfully detected all evaluated attacks with high confidence and no false signals, searching graphs with tens of millions of audit records in minutes.
Takeaways & Limitations
CTI correlations can serve as robust and reliable artifacts for threat hunting when represented as relationships among attack entities.
Takeaways & Limitations
Analytics assume a stationary provenance-graph snapshot during each search, with no node or edge changes until termination.
Abstract
from arXiv · showhide
Cyber threat intelligence (CTI) is being used to search for indicators of attacks that might have compromised an enterprise network for a long time without being discovered. To have a more effective analysis, CTI open standards have incorporated descriptive relationships showing how the indicators or observables are related to each other. However, these relationships are either completely overlooked in information gathering or not used for threat hunting. In this paper, we propose a system, called POIROT, which uses these correlations to uncover the steps of a successful attack campaign. We use kernel audits as a reliable source that covers all causal relations and information flows among system entities and model threat hunting as an inexact graph pattern matching problem. Our technical approach is based on a novel similarity metric which assesses an alignment between a query graph constructed out of CTI correlations and a provenance graph constructed out of kernel audit log records. We evaluate POIROT on publicly released real-world incident reports as well as reports of an adversarial engagement designed by DARPA, including ten distinct attack campaigns against different OS platforms such as Linux, FreeBSD, and Windows. Our evaluation results show that POIROT is capable of searching inside graphs containing millions of nodes and pinpoint the attacks in a few minutes, and the results serve to illustrate that CTI correlations could be used as robust and reliable artifacts for threat hunting.
1 INTRODUCTION
Poirot addresses threat hunting’s difficulty in linking related indicators across large, noisy, and evolving enterprise logs. It models CTI correlations and kernel-audit provenance as graphs, then aligns them to identify attack campaigns efficiently.
- Threat hunting asks whether an enterprise was targeted by an APT identified through released indicators of compromise.Answering this confidently requires searching host and network logs, recognizing described entities, and assessing whether the APT successfully infiltrated the enterprise.
- Existing approaches often use fragmented indicators or timestamp heuristics, limiting reconstruction of attacks over long periods and increasing susceptibility to evasion.Adversaries can mutate hashes, IP addresses, names, or other artifacts, while legitimate tools and activities may generate false signals.
- IOC relationships encode attack behavior and provide clues tied to attacker goals, making them harder for adversaries to change than isolated artifacts.
- Poirot represents CTI correlations as a query graph and kernel audit records as a provenance graph, then searches for an embedding between them.Kernel audits capture causal relations and information flows among system entities and are assumed to be stored on a separate secure server to preserve integrity.
- Poirot uses an approximation function and similarity metric to align graphs while prioritizing information flows according to the attacker’s production cost.This formulation treats threat hunting as graph pattern matching despite the general problem’s NP-completeness.
- Poirot searched graphs containing millions of nodes and pinpointed attacks in a few minutes across Linux, FreeBSD, and Windows evaluations.The evaluation used DARPA adversarial engagements, real-world incident reports, attack-free user activity, simulated attacks, and comparisons with existing tools.
2 RELATED WORK
Prior work spans log-based analytics, provenance-graph exploration, query processing, behavior discovery, and graph pattern matching. Poirot differs by focusing on CTI-derived graph query processing over whole-system causal and information-flow relationships.
- Log-Based Attack Analytics: Log-based analytics uses DNS, web proxy, NetFlow, or multi-source logs to detect infections, command-and-control channels, malicious domains, or reconstructed attack stages.
- Provenance Graph Explorations: Provenance-graph research constructs graphs from kernel audits, while compression, summarization, and log reduction address their large size and coarse granularity.
- Query Processing Systems: Query-processing systems apply optimization, indexing, anomaly queries, forensic languages, and other methods to support timely investigations of historical audit data.
- Behavior Discovery: Behavior-discovery methods mine or generate malware behavior models, whereas Poirot searches whole-system correlations and information flows without symbolic expressions.TGMiner emphasizes query formulation and uses subsequence matching, unlike Poirot’s graph pattern matching approach.
- Graph Pattern Matching: Graph pattern matching searches large graphs for subgraphs with conjunctively specified connections, but the general problem is NP-complete.Some prior methods use bounded-hop paths, vector-space joins, neighborhood proximity, graph shape, edge attributes, or random walks.
3 APPROACH OVERVIEW
Poirot converts CTI descriptions and kernel audit logs into typed directed graphs, then searches for an inexact alignment between attack behavior and system provenance. Its alignment process accommodates low-level paths, noise, and large graphs.
- Query Graph Construction: Poirot presents an architecture that extracts CTI indicators and their relationships to construct a query graph representing reported attack behavior.
- Provenance Graph Construction: Kernel audit logs become a labeled, typed, directed provenance graph whose nodes are system entities and whose edges represent directed causality or information flow.Poirot supports Windows, Linux, and FreeBSD kernel audit logs and constructs the provenance graph in memory.
- Query Graph Construction: A query graph contains entities as nodes and relationships as directed edges, with names, types, hashes, times, and other annotations available for matching.The current implementation uses names and types.
- Query Graph Construction: CTI report language such as writing, downloading, spawning, or clicking can be mapped by an analyst to file, network, or process relationships in the query graph.
- Graph Alignment: A single query-graph edge may correspond to a multi-edge provenance path, so alignment must match high-level flows against lower-level activity and attacker-added noise.
- Graph Alignment: Graph matching is NP-complete in general, motivating Poirot’s approximate alignment and similarity approach.
- Graph Alignment: Poirot seeds candidate node alignments, expands them, scores the resulting aligned subgraph, and raises an alert when the score exceeds a threshold.Otherwise, it starts from the next seed candidate and reports aligned nodes for forensic analysis after finding an attack subgraph.
4 ALGORITHMS
POIROT aligns a CTI-derived query graph with a kernel-audit provenance graph by scoring attacker-controllable flows and searching efficiently for high-scoring matches. Its design uses influence-based alignment scoring, thresholded alarms, on-demand graph traversal, and iterative candidate selection for provenance graphs with millions of nodes and edges.
- Alignment Metric: POIROT models threat hunting as selecting the best alignment between a query graph and a provenance graph.The query graph represents CTI-described behavior, while the provenance graph represents kernel-audit entities, information flows, and causal dependencies.
- Influence Score: An influence score estimates how likely an attacker can produce a flow between two nodes.It is based on the minimum number of distinct, independent compromises required to control that flow.
- Alignment Score: The alignment score aggregates normalized influence scores for provenance paths corresponding to query-graph flows.For each query flow, the formula sums influence scores over aligned provenance-node pairs and normalizes by the maximum possible sum.
- Influence Score: Higher minimum compromise counts make flows harder for attackers to construct, while flows exceeding Cthr are treated as attacker-uninitiated under the model.The threshold assumes attackers compromise only a small number of independently exploitable entry-point processes.
- Alignment Score: An alignment score above τ declares a match and raises an alarm, with τ set from the assumed maximum number of independent attacker entry points.The score is the average of the influence scores, and τ is tied to Cthr.
- Best-Effort Similarity Search: The search avoids brute force by iteratively choosing node candidates using an approximation of each alignment’s maximal contribution to the final score.Because provenance graphs can contain millions of nodes and edges, influence scores and reachability are computed through on-demand traversals; the search assumes a stationary graph snapshot.
5 EVALUATION
POIROT was evaluated on adversarial, real-world, and attack-free datasets across BSD, Windows, and Linux. It identified attack alignments quickly, remained robust to benign overlap and mutated malware, and searched provenance graphs far larger than the query graphs.
- Evaluation datasets: POIROT was evaluated in three experiments covering DARPA adversarial engagements, publicly reported attacks, and attack-free user activity.The DARPA evaluation included ten scenarios: four BSD, two Windows, and four Linux attacks.
- DARPA TC dataset: 9 out of 10 scenarios produced an alignment above the threshold in the first search iteration, while BSD-4 yielded an exact query-graph match.Across repeated searches, the maximum alignment score was reached in the first iteration for 7 of 10 scenarios and in the fourth or fifth for the remaining three.
- Public attacks: POIROT detected alignments above the threshold for every public-attack test case, including cases with benign or non-unique entity names.Its causal and information-flow matching also gave it a better chance of detecting mutated malware when behavior remained constant.
- Benign datasets: In attack-free datasets, alignment scores were at most 0.16, below the threshold, despite benign logs sharing nodes and events with the query graphs.The influence score pruned many flows that appeared similar by chance.
- Efficiency: The query graphs were on average 209K times smaller than the provenance graphs, yet POIROT found exact embeddings quickly.Graph-search expansion was the main bottleneck, and runtime depended on query and provenance graph sizes among other factors.
6 CONCLUSION
Poirot formulates cyber threat hunting as graph pattern matching over kernel audit provenance graphs and detects attacks across platforms with high confidence and no false signals in minutes.
- Poirot models cyber threat hunting as graph pattern matching over provenance graphs built from kernel audit records.Its alignment algorithm embeds threat-behavior graphs into much larger provenance graphs.
- Ten attack scenarios conducted by a professional red team were evaluated across three operating-system platforms.The evaluation also included real-world cyber attacks and tens of millions of audit records.
- Poirot successfully detects all evaluated attacks with high confidence, no false signals, and search times measured in minutes.
A APPENDIX
The appendix describes malware behaviors used to construct query graphs and shows that dependencies distinguish entities even when labels and types are identical.
- Malware backgrounds: njRAT is a publicly available remote-access Trojan that gives attackers full control over victim systems.The reported attacks primarily targeted organizations in the Middle East across government, telecom, and energy sectors.
- Malware behaviors: OceanLotus execution drops a decoy document and eraser application, opens the document in Microsoft Word, and decrypts resources before dropping another copy.
- Graph alignment: HawkEye query-graph nodes with identical labels and types align differently because their dependencies connect them to browser or email and instant-messaging applications.The alignment of browser or mail application nodes is independent of whether those applications are installed on the system.