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 hunters must determine whether an APT targeted an enterprise, a task that can require lengthy analysis of host and network logs. POIROT aligns graphs of CTI-described attack behavior with kernel-audit provenance graphs, searching graphs with millions of nodes and pinpointing attacks within minutes.
Problem
Determining whether an APT targeted an enterprise can require lengthy, complicated analysis of host and network logs.
Source: §1 · p. 1Method
POIROT models CTI-described attack behavior and kernel-audit provenance as graphs, then aligns them to find the behavior in audit data.
Source: §1 · p. 2, §3.1 · p. 3, §3.2 · p. 3Results
POIROT searches graphs containing millions of nodes and pinpoints attacks in a few minutes.
Source: §1 · p. 2Takeaways & Limitations
Across evaluated real-world and red-team attacks, POIROT detected all attacks with high confidence and no false signals.
Source: §6 · p. 15The search assumes a stationary provenance-graph snapshot, with no node or edge changes during a run.
Source: §4.2 · p. 7
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 uses relationships among CTI indicators to represent attack behavior and align it with kernel-audit provenance records. It aims to identify attack campaigns robustly and efficiently, even when individual artifacts change.
Introduction
- Threat hunting must link indicators across weeks or months and millions of mostly benign events while identifying campaigns despite mutated artifacts and limiting false positives.Analysts need timely searches that reveal the attack scenario rather than isolated indicator matches.Source: §1 · p. 1
- Existing approaches often use fragmented signatures or timestamp heuristics, which can miss long-running attack behavior, generate false signals, and fail when attackers change tools or signatures [15, 64].The paper argues that relationships among indicators encode attacker behavior tied to goals and are harder to change [77].Source: §1 · pp. 1–2
- Poirot models CTI indicators and their relationships as a query graph, then searches for its embedding in a provenance graph built from kernel audit logs.The paper describes kernel audits as reliably capturing relationships among system entities, provided the kernel is uncompromised and logs are stored on a separate secure server.Source: §1 · p. 2
- Poirot formulates threat hunting as graph pattern matching over causal dependencies and information flows, prioritizing flows by attacker production cost and using an approximation function and novel similarity metric to align graphs.The approximation addresses the NP-completeness of graph matching, while attacker-cost prioritization is intended to resist evasive attacks such as mimicry.Source: §1 · p. 2
- Poirot searches graphs containing millions of nodes and pinpoints attacks in a few minutes, and the paper reports that it outperforms other threat-hunting tools.The evaluation uses DARPA adversarial engagements, public real-world incident reports, and attack-free user activities; kernel-log parsers support Linux, FreeBSD, and Windows.Source: §1 · p. 2
2 RELATED WORK
Prior work covers log-based analytics, provenance graphs, query systems, behavior discovery, and graph matching. POIROT focuses on threat hunting with best-effort graph alignment over large, adversarial provenance graphs.
Log-based Attack Analytics
- Log-based attack analytics use DNS, proxy, NetFlow, and multi-source logs, while system-audit-log research supports forensic analysis and attack reconstruction.Opera et al. [51] detect early-stage infection; Disclosure extracts NetFlow features to detect botnet C&C channels; DNS logs detect malicious domains; Hercule correlates logs to reconstruct attack stages; audit-log work [20, 21, 42, 56] supports forensics and reconstruction.Source: §2 · p. 2
Provenance Graph Explorations
- Provenance-graph research addresses scale and granularity through compression, summarization, log reduction, finer process units, record-and-replay, and parallel execution.Recent applications include alert triage, zero-day attack-path identification, detection, and reconstruction; POIROT instead targets threat hunting rather than real-time detection or forensic analysis.Source: §2 · p. 2
Query Processing Systems
- Query systems offer optimization, indexing, and investigation tools, while prior frameworks are orthogonal to POIROT and could support its search algorithm.Examples include anomaly queries in SAQL [17], forensic campaign queries in AIQL [18], real-time provenance analysis in CamQuery [53], and human-assisted hunting tools.Source: §2 · p. 2
Behavior Discovery
- Prior behavior-discovery methods mine malware traces or use symbolic execution, whereas POIROT searches whole-system correlations and information flows; TGMiner emphasizes query formulation and uses subsequence matching.Christodorescu et al. mine behavior from dynamic malware traces; Kolbitsch et al. generate behavior models using symbolic execution; TGMiner [77] mines discriminative patterns from training audit logs and searches test data using.Source: §2 · p. 2
Graph Pattern Matching
- POIROT develops best-effort graph matching for large, labeled, directed, typed provenance graphs, where adversarial events and missing query-node or edge alignments challenge existing approaches.GPM is NP-complete in general; random-walk approaches can be unreliable against attackers who generate fake events, while many methods require an alignment for every query node and edge.Source: §2 · p. 3
3 APPROACH OVERVIEW
POIROT models kernel audit activity and CTI-described attack behavior as graphs, then searches for an alignment between them. The approach constructs provenance and query graphs before matching query flows against audit activity.
3.1 Provenance Graph Construction
- Kernel audit logs become a labeled, typed, directed provenance graph whose entity nodes and causality or information-flow edges support tracking across Windows, Linux, and FreeBSD.Fast hashing and reverse indexing map process and file names to unique node IDs for efficient search.Source: §3.1 · p. 3
3.2 Query Graph Construction
- CTI reports supply indicators and relationships for query graphs, with automated extraction optionally refined by analysts to reduce noise.Reports may be natural-language or structured formats such as OpenIOC, STIX, and MISP; verbs can be mapped to file, network, or process interactions.Source: §3.2 · pp. 3–4
- Query-graph entities become typed nodes and their relationships become directed edges; POIROT currently uses names and types to map query nodes to provenance nodes.Analysts may also associate nodes and edges with annotations such as hashes or creation times.Source: §3.2 · p. 3
- Query graphs summarize reported information flows rather than precisely reproducing the full attack graph, and experimental graphs typically contain 10–40 nodes and up to 150 edges.The DeputyDog example illustrates entities including a malware process, dropped file, registry entry, and Internet location.Source: §3.2 · p. 4
3.3 Graph Alignment
- Because a high-level query edge may correspond to a multi-edge audit path, POIROT searches for graph alignments and prioritizes paths using an influence score based on attacker effort.The score is intended to exclude irrelevant paths and mitigate dependency explosion, while accounting for evasive behavior that can defeat length- or proximity-based prioritization.Source: §3.3 · p. 4
- After alignment, POIROT scores similarity and alerts when the score exceeds a threshold, reporting aligned nodes, information flows, and timestamps for forensic analysis.If the threshold is not exceeded, the search proceeds from the next seed-node candidate.Source: §3.3 · p. 5
4 ALGORITHMS
POIROT aligns a CTI query graph with provenance subgraphs using an influence-based score, then searches for high-scoring matches with a best-effort procedure tailored to provenance graphs.
4.1.1 Influence Score.
- The influence score is inversely proportional to the minimum independent compromises needed to control a flow, based on common process ancestors, and takes the maximum across available flows.A cutoff Cthr makes flows requiring more distinct compromises have zero influence; the approach is intended to resist noise that preserves the attack’s common ancestors.Source: §4.1.1 · p. 6
4.1.2 Alignment Score.
- POIROT scores an alignment from 0 to 1 by normalizing the influence scores of provenance flows between aligned nodes against the number of query flows.A score of 1 means every query node and flow is matched by flows with maximal influence; a score of 0 means no proper node alignment or similar flow is found.Source: §4.1.2 · pp. 6–7
4.2 Best-Effort Similarity Search
- The search proposes candidate node alignments using names, types, annotations, or user input, then seeds traversal from query nodes with the fewest candidates.Because provenance graphs can contain millions of nodes and edges, influence scores and paths are computed on demand against a stationary graph snapshot.Source: §4.2 · p. 7
- Bidirectional traversals explore candidate connections and stop along paths when influence reaches zero, reducing search complexity while preserving paths that remain within the compromise cutoff.The procedure repeats traversals from previously visited nodes when needed to cover the query graph.Source: §4.2 · p. 7
- To avoid brute-forcing all candidate graph alignments, the procedure greedily fixes node matches with the greatest estimated contribution to the alignment score, reusing prior results as matches are fixed.After all matches are fixed, it calculates the alignment score and repeats the search from another seed if the score is below threshold.Source: §4.2 · p. 8
5 EVALUATION
POIROT was evaluated on DARPA TC attack scenarios, public real-world malware reports, and attack-free audit datasets, testing its detection, mutation robustness, false-signal resistance, and efficiency.
5.1 Evaluation on the DARPA TC Dataset
- Across 10 DARPA TC attacks on BSD, Windows, and Linux, POIROT found a threshold-bypassing alignment in the first iteration in 9 scenarios.The exact query-graph match occurred in BSD-4; the maximum score was reached in the first iteration in 7 of 10 scenarios and in iterations 4 or 5 in the other three, partly because reports and implementations differed.Source: §5.1 · pp. 9–10, Table 3 · p. 9
5.2 Evaluation on Public Attacks
- POIROT exceeded its 1/3 alignment threshold on every public-malware test case, including mutated samples whose isolated IOCs other tools often missed.POIROT aligned only a subset of query entities in most cases, but aligned every entity in DustySky; other tools detected four samples with known unique IOCs and missed isolated IOCs in three other cases.Source: §5.2 · p. 11, Table 4 · p. 11
5.3 Evaluation on Benign Datasets
- On attack-free datasets, POIROT's highest alignment score was at most 0.16, below the 1/3 threshold; the optimal F-score range was [0.17, 0.54].The datasets included more than seven months of benign audit records and billions of records across Windows, Linux, and FreeBSD; the interval midpoint, 0.35, maximized the margin between attack and benign scores.Source: §5.3 · pp. 11, 14, Figure 8 · p. 14
5.4 Efficiency
- Across DARPA TC scenarios, query graphs were on average 209K times smaller than provenance graphs, yet Poirot found exact embeddings very fast; runtime depended on graph sizes, query-graph shape, and candidate alignments.In controlled malware experiments, Splunk and Poirot each searched for all listed IOCs in less than one minute; in-memory provenance graphs averaged 1:4 compression (25%) compared with on-disk logs.Source: §5.4 · pp. 14–15
6 CONCLUSION
POIROT frames cyber threat hunting as graph pattern matching, aligning threat behavior with kernel-audit provenance graphs to detect known attacks. It detected all evaluated attacks with high confidence, no false signals, and in minutes.
6 CONCLUSION
- Across real-world attacks and ten professional red-team scenarios on three OS platforms, POIROT detected all attacks with high confidence, no false signals, and in minutes.The evaluation covered tens of millions of kernel audit records.Source: §6 · p. 15
A APPENDIX
The appendix summarizes the malware behaviors and report statements used to construct POIROT’s query graphs. Across the examples, those statements capture attack sequences from execution and persistence to credential collection and command-and-control communication.
njRAT
- njRAT’s query graph captures configuration access, keystroke logging, persistence, registry changes, and beaconing to C2 server 217.66.231.245.It also records writes to .pf files and the launch of a netsh process.Source: A APPENDIX · p. 17
DeputyDog
- DeputyDog’s query graph represents malware reported to have targeted organizations in Japan.The graph is shown in Fig. 2 and described in section 3.Source: A APPENDIX · p. 17
Uroburos
- Uroburos-family malware installs dropped Windows libraries through rundll32.exe, creates a boot-start registry key, makes log files, and removes files.The report names Uroburos, ComRAT, Snake, Turla, and Agent.BTZ as members of the family.Source: A APPENDIX · p. 17
Carbanak
- Carbanak’s sequence runs from spear-phishing exploitation to service-based persistence, command storage, configuration reads, and C2 communication; reported cumulative losses reached one billion dollars.It copies itself as svchost.exe under %system32% and deletes the original exploit-created file.Source: A APPENDIX · p. 17
DustySky
- DustySky’s query graph covers a disguised Word-file execution, an Arabic decoy document, and VM-evasion checks for VirtualBox and VMware.DustySky Core is dropped to %TEMP%, and keystroke logs are saved under %TEMP%\temps.Source: A APPENDIX · p. 17
OceanLotus
- OceanLotus’s sequence uses a legitimate signed Symantec application to load a dropped malicious DLL before accessing registry resources and connecting to its mothership.Execution also drops a decoy document, an eraser application, an encrypted backdoor, and the malicious DLL.Source: A APPENDIX · p. 17
HawkEye
- HawkEye’s graph follows process hollowing into RegAsm, credential collection by child processes, temporary-file handling, and exfiltration to an attacker email address.Its application nodes can align through dependencies even when identically labeled or when the applications are not installed: checks can trigger OPEN events detected by POIROT.Source: A APPENDIX · p. 17