cs.CROct 26, 2026
SaveSoK: Timestamps Are Not a Time Model: Rethinking Temporal Reasoning in Host-Based Intrusion Detection
Organizations: datAInsights GmbH
Abstract
Host-based intrusion detectors order events, window audit streams and sequence attack stages by their timestamps. Every conclusion they draw therefore rests on assumptions about clocks, delivery, entity identity and the integrity of the evidence, and most of these assumptions go unstated. This Systematization of Knowledge (SoK) makes them explicit. Drawing on temporal databases, stream processing and runtime verification, we distill five components of a time model, together with a checklist of evidence assumptions and four levels of guarantee, and walk through a running campaign with them. A documented search yields fifteen families of detection and investigation. For papers selected by screening role and period, plus named systems and landmarks, we check the stated assumptions in the full texts, and we assess eleven temporal knowledge representation and reasoning (KRR) formalisms and a learned baseline on nine attack patterns. Some early alert correlators stated clock and delivery assumptions, and forensics measures clock error. Current provenance-based detectors state no clock bound. Four audited papers describe input-ordering conditions or conventions, but none specifies conditions for conclusion validity across a stated class of delivery failures. In the selected provenance-based systems, campaign composition uses system-specific procedures or objectives, learned state, causal graph queries or language models, and beyond CEP-based query systems, we found no temporal rule language or stream reasoner from KRR applied to host audit data. In 28 of 38 audited provenance-era detector papers, capture or stored evidence is trusted or its manipulation is placed out of scope, and none says which conclusions survive deleted, delayed or forged records. Five open challenges follow from these gaps.
Figures & tables
| Survey | Focus | Learned detectors | Symbolic security systems | Temporal KRR formalisms | Joint comparison of detectors and temporal KRR |
|---|---|---|---|---|---|
| Zipperle et al. 2022 | Provenance-based intrusion detection | Yes | Yes | No | No |
| Inam et al. 2023 | System auditing and provenance analysis | Partly | Yes | No | No |
| Salah et al. 2013 | Alert correlation | No | Yes | Partly | No |
| Hakim et al. 2025 | Neuro-symbolic AI for cybersecurity | Yes | Partly | No | No |
| Ammar et al. 2025 | Integrity, attestation and auditing of program execution | No | No | No | No |
| Breitinger et al. 2025 | Timeline-based event reconstruction in digital forensics | No | Partly | No | No |
TABLE I: Scope of this survey compared with related surveys.
| Notion | What it is | Typical source | What can go wrong |
|---|---|---|---|
| Event time | The time at which the sensor says an action occurred, on the sensor’s clock | Kernel audit record timestamp | Host clock skew; records lost in races between occurrence and commitment [ 37 ] |
| Observation time | When a record reaches the analysis pipeline | Collector or SIEM ingest timestamp | Delay and reordering across hosts |
| File metadata time | Time attributes stored with a file object | Modification, access, change and birth times | Timestomping rewrites them [ 2 ] |
| Causal order | The order implied by information flow, such as a fork before the child’s first action | Provenance edges | Missing edges when records are lost or deleted |
TABLE II: Four notions used to interpret timestamps and order.
| Level | Question | Example |
|---|---|---|
| Specification | Is it defined unambiguously what counts as a match or a campaign? | A chronicle, an Event Calculus specification in RTEC, a program in the stream reasoning language LARS |
| Evaluation | Is the algorithm correct, and possibly complete, with respect to that definition? | VeriMon is formally verified for metric first-order temporal logic (MFOTL) [ 59 , 60 ] ; for a fixed query in the unary-filter fragment of complex event logic (CEL), the compiled automaton has proven semantics and constant update cost per event, with results enumerated separately [ 61 ] |
| Certificate | Can a single output be checked independently? | WhyMon’s proof trees, checked by a formally verified checker [ 62 ] |
| Correspondence | Under which assumptions about sensors, extraction and attacker does the output describe actual behavior? | Only partial guarantees exist: tamper-evident auditing shows that committed records were not altered, under a trusted-execution assumption [ 55 ] ; the inspected systems state some trust assumptions (Table C1), but none gives a contract per conclusion covering capture, extraction, identity, timestamp meaning and attacker influence |
TABLE III: Four levels of guarantee.
| Step | Observed fact | Derived hypothesis | Correspondence assumption | If evidence is missing |
|---|---|---|---|---|
| 1. Credential read on A | Read(p, f)@t1, with t1 on A’s clock | p read a store of credential c; that p obtained c needs evidence that the read returned it | f’s path or ontology class identifies a store of c; process identifiers are not reused within the horizon | The fact and the hypothesis are not derived; this says nothing about whether a read occurred |
| 2. Use by another process | Flow edges from f, or from p’s memory, to process q, with event times | q holds c | The recorded flow carried c itself rather than other data; the edges of the witness path were captured and are authentic. A provenance path shows dependency, not the identity of a credential | The link between steps 1 and 3 is not derivable |
| 3. Authentication on B | Logon(u, from address a)@t3, with t3 on B’s clock | u authenticated with c, after step 1 | u’s credential is c, which the logon record alone does not show; a identifies host A; the relative offset of A’s and B’s timestamps, rounding included, is at most , so step 1 precedes step 3 if t3 t1 > | The hypothesis is not derived |
| 4. Exfiltration from B | Outbound transfer by process r on B at t4, with its volume | r’s outbound transfer exfiltrated data from A | r descends from u’s session; the transfer carries data from A, which its volume alone does not show | The hypothesis is not derived |
TABLE IV: The running example: observed facts, derived hypotheses and correspondence assumptions.
Fig. 1: The fifteen families, placed by the pipeline stage they mainly serve: knowledge, recognition, composition, and investigation and explanation. Blue marks the families whose recognition or composition rests on a declarative temporal specification, of which temporal-logic monitoring can also certify its explanations. Orange marks the families in which campaigns are composed by a system-specific procedure or an LLM agent. Section 5.2 compares how selected systems compose campaigns.
| Family | Correct evaluation of a declarative attack specification | Explanation form | Independently checkable | Order and metric time | Long horizons | Recursion and joins | Counting | Uncertainty | Defaults, incompleteness, conflicts | Semantic context | Demonstrated raw-stream operation | Late or out-of-order data | Adversarial manipulation | Knowledge update |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| L1 Dynamic graph learning | Scores, summary graphs | + | + | ++ 1 | ++ | n/s | + 1 | |||||||
| L2 Semantic-structural fusion | Scores, attention weights | + | + | ++ | ++ | n/s | + 1 | |||||||
| L3 LLM investigation agents | Narratives | n/s | + | n/s | ++ | n/s | n/s | n/s | + | |||||
| L4 Knowledge-guided learning | + | Rules with weights | n/s | + 1 | + | + | + | ++ 1 | + 1 | ++ | ++ 1 | n/s | + 1 | + |
| L5 Host behavior models | Anomalies, policy violations | + | + | ++ | ++ | n/s | + | |||||||
| S1 Alert correlation, plan recognition | + | Derivations, scenario graphs | + | ++ | + | + | n/s | ++ | + | dep | + | + | + | ++ |
TABLE VI: Families compared on fourteen dimensions.
| Pattern | Data flow | Representative systems | What is formally specified | Main limitation |
|---|---|---|---|---|
| P1 Symbolic over extracted facts | Expert rules or queries over extracted audit, configuration or vulnerability facts | SLEUTH, HOLMES, POIROT, KRYSTAL, MulVAL | The rules or queries; evaluation correctness is rarely stated | Rule coverage and the accuracy of extracted facts limit the conclusions; evasion has been demonstrated for particular rule sets |
| P2 Learned detection | Events to embeddings to scores | Unicorn, KAIROS, TFLAG, R-CAID, NODLINK, FLASH, EagleEye, CrossGuard | Training and inference procedures; no declarative campaign definition | Windows, expressiveness bounds, mimicry |
| P3 Learned detection, then LLM investigation | Scores select evidence; an LLM assembles the campaign | OCR-APT, ANCHOR, ProvSEEK, ProvAgent | No declarative campaign semantics identified | Composition without specification; bounded context |
| P4 Knowledge into learning | Rules shape training, learning tunes rule parameters, or logic labels embeddings | KnowGraph, CAPTAIN, Eckhoff et al. (alert embeddings) | Rule structure; parameters and weights are learned | Rules mostly atemporal; Eckhoff et al. add timestamp-order preferences as weak constraints; differentiable temporal logics exist outside security (Section 7.3) |
| P5 Learning into symbolic artifacts | Learned models draft rules, queries or specifications | SIGMERGE, ThreatRaptor, IRIS, invariant mining, LTLf patterns from reports (Eckhoff et al.) | The generated artifact, but not its agreement with the analyst’s intent | Mostly single rules or one pattern template; validation ad hoc |
| P6 Recognition, then symbolic temporal composition | Recognized alerts or techniques are composed by ordering rules or temporal formulas | HOLMES, RapSheet, KnowHow; Eckhoff et al. (LTLf in telingo) | System-specific composition procedures in the first three; a temporal logic with known semantics in Eckhoff et al. | Recognition is rule- or signature-based; the general formalism is used only in a proof of concept over short symbolic alert traces |
TABLE VII: Integration patterns observed in the literature.
| System | Recognition | Composition across events, windows or hosts | Declarative specification of composition |
|---|---|---|---|
| Ning et al., CCS 2002 | Intrusion detection alerts | Prerequisite and consequence chaining | Yes, logical prerequisites and consequences |
| Morin and Debar, RAID 2003 | Intrusion detection alerts | Chronicle recognition with metric constraints | Yes, chronicles |
| Albanese et al., ESORICS 2011 | Incoming alerts associated with vulnerability exploits | Matching and indexing of attack occurrences against probabilistic temporal attack graphs, with possible continuations | Yes, an explicit temporal and probabilistic attack-occurrence model over alerts, a task distinct from learned provenance detection |
| HOLMES, S&P 2019 | Rules map events to tactics | High-level scenario graph ordered by kill-chain stage | No; a system-specific construction procedure |
| RapSheet, S&P 2020 | Endpoint alerts | Tactical provenance graph scored by temporal order | No; a scoring function |
| Unicorn, NDSS 2020 | Learned graph sketches | Evolutionary model over the sketch stream | No |
TABLE VIII: Campaign composition in representative systems.
| Formalism | AP1 | AP2 | AP3 | AP4 | AP5 | AP6 | AP7 | AP8 | AP9 | Applied to security data |
|---|---|---|---|---|---|---|---|---|---|---|
| Temporal message-passing GNN | L | L | L | L | L | a L, b L | L | a L, b – | L | Yes, provenance detectors (L1, L2) |
| MFOTL (MonPoly, VeriMon) | ✓ | ✓ | ✓ | ✓recursive let (VeriMon) | ✓ | a ✓, b ✓ | – | a ✓, b – | ✓recursive let (VeriMon) | Mainly compliance logs; ORCHIDS uses its own temporal logic |
| CEP (chronicles) | ✓ | ✓ | ✓ | – | ✓ | a ✓, b ✓ | – | a ◐, b – | – | Chronicles over intrusion detection alerts |
| Event Calculus (RTEC) | ◐ | ◐ | ✓ | ◐ | ✓ | a ◐, b ◐ | ◐probabilistic EC | a ✓, b – | ◐ | Event Calculus for security monitoring [ 286 ] ; none for RTEC |
| LARS | ✓ | ✓ | ✓ | ◐ | ✓ | a ✓, b ✓ | – | a ✓, b ◐ | ◐ | We found none |
| Temporal ASP (telingo) | ◐metric temporal ASP | ◐ | ✓ | ◐ | ✓ | a ◐, b ◐ | ? probabilistic ASP | a ◐, b ◐ | ◐ | Short SIEM alert traces; alert-cluster labeling with ordering preferences [ 22 ] |
TABLE IX: Constructs for the attack-reasoning patterns, by formalism.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
| Literature | Main round | Earlier years | Final round | Total |
|---|---|---|---|---|
| Security, screened | 3,045 | 1,064 | 760 | 4,869 |
| Security, retained | 613 | 282 | 108 | 1,003 |
| KRR, screened | 1,216 | 608 | 726 | 2,550 |
| KRR, retained | 661 | 259 | 89 | 1,009 |
TABLE A1: Records screened and retained, by literature and round.
| Query | Line of work | Search expression | Open | Recent | Venue | Included | Early | Included early |
|---|---|---|---|---|---|---|---|---|
| Q1 | Provenance-based detection and investigation | (provenance OR "causal graph" OR "dependency graph" OR "audit graph") AND (intrusion OR attack OR attacks OR threat OR threats OR APT OR "advanced persistent" OR forensic OR forensics OR investigation OR malware OR "lateral movement") | 4101 | 3037 | 320 | 174 | 98 | 10 |
| Q2 | Audit-log and host-based detection | ("audit log" OR "audit logs" OR "system audit" OR "kernel audit" OR "system logs" OR "security logs" OR "event logs" OR "system call" OR "system calls" OR "host-based" OR "host intrusion detection" OR endpoint OR "endpoint detection and response" OR EDR OR "Windows event" OR Sysmon OR eBPF OR ETW) AND (attack OR attacks OR intrusion OR "advanced persistent" OR APT OR "threat hunting" OR forensic OR investigation OR "lateral movement") | 8001 | 4467 | 571 | 216 | 423 | 123 |
| Q3 | Multi-step attacks and campaign reconstruction | ("alert correlation" OR "multi-step attack" OR "multi-step attacks" OR "multistage attack" OR "multi-stage attack" OR "multi-stage attacks" OR "attack scenario" OR "attack scenarios" OR "kill chain" OR "attack reconstruction" OR "attack story" OR "attack stories" OR "attack campaign" OR "attack campaigns" OR "attack graph" OR "attack graphs" OR SIEM OR "security information and event management" OR "event reconstruction" OR "timeline reconstruction" OR "lateral movement") | 12251 | 7729 | 905 | 209 | 369 | 137 |
| Q4 | Symbolic and knowledge-based security reasoning | ("temporal logic" OR datalog OR "logic programming" OR "answer set programming" OR "rule-based" OR "rule based" OR ontology OR "knowledge graph" OR "event calculus" OR "complex event processing" OR "runtime verification" OR "query language") AND (intrusion OR "attack detection" OR "threat hunting" OR "attack investigation" OR "threat detection" OR forensics OR "security monitoring" OR "audit logs" OR "audit data") | 3314 | 2355 | 120 | 52 | 81 | 32 |
| Q5 | Learned detection over host data | ("graph neural network" OR "graph neural networks" OR transformer OR "language model" OR "language models" OR "anomaly detection" OR "representation learning") AND (provenance OR "audit log" OR "audit logs" OR "system logs" OR "host-based" OR endpoint OR "system call") AND (attack OR attacks OR intrusion OR APT OR threat) | 1641 | 1342 | 99 | 119 | 40 | 29 |
| Q6 | Threat-intelligence knowledge and ATT&CK | ("threat intelligence" OR CTI OR "ATT&CK" OR TTP OR TTPs OR "attack technique" OR "attack techniques") AND (extraction OR "knowledge graph" OR ontology OR mapping OR detection OR provenance OR "audit" OR "attack graph" OR correlation) | 6107 | 4677 | 336 | 162 | 21 | 2 |
TABLE A2: Security queries and hits (OpenAlex, 23 and 24 October 2026).
| Role | Main round | Earlier years | Final round | Total |
|---|---|---|---|---|
| Learned detection (L1, L2) | 186 | 0 | 4 | 190 |
| LLM investigation (L3) | 14 | 0 | 0 | 14 |
| Knowledge-guided learning (L4) | 8 | 0 | 0 | 8 |
| Alert correlation and plan recognition (S1) | 61 | 69 | 3 | 133 |
| Temporal-logic and event-pattern detection (S2, S3) | 0 | 11 | 16 | 27 |
| Rule-based analysis and queries (S4, S5) | 26 | 0 | 0 | 26 |
TABLE A3: Retained security papers by role and round.
| Domain | Search expression | Open | Recent | Venue | Included | Early | Included early |
|---|---|---|---|---|---|---|---|
| B1 Temporal logics and runtime verification | ("runtime verification" OR "runtime monitoring" OR "online monitoring" OR "metric temporal logic" OR "metric first-order temporal logic" OR MFOTL OR "first-order temporal logic" OR "linear temporal logic" OR LTL OR LTLf OR "temporal logic") AND (monitor OR monitoring OR monitors OR monitorability) AND (log OR logs OR trace OR traces OR stream OR streams OR timestamp OR timestamps OR "out-of-order") | 748 | 303 | 235 | 149 | 63 | 39 |
| B2 Event recognition, complex event processing and stream reasoning | ("complex event processing" OR "complex event recognition" OR "composite event" OR "event pattern" OR "event patterns" OR "event calculus" OR "chronicle recognition" OR "stream reasoning") AND (semantics OR formal OR logic OR "temporal constraints" OR intervals OR "interval-based" OR recognition) | 566 | 131 | 131 | 97 | 129 | 64 |
| B3 Datalog-based temporal rule languages | (DatalogMTL OR "metric temporal datalog" OR "temporal datalog" OR vadalog OR (datalog AND ("metric temporal" OR "temporal operators" OR "temporal reasoning" OR streams))) | 121 | 33 | 59 | 45 | 6 | 3 |
| B4 Non-monotonic reasoning, argumentation and belief revision | ("temporal answer set programming" OR "temporal equilibrium logic" OR telingo OR ("answer set programming" AND (temporal OR "time-dependent" OR stream OR streams OR "dynamic domains")) OR ("belief revision" AND temporal) OR ("argumentation framework" AND temporal) OR ("argumentation frameworks" AND temporal) OR ("defeasible logic" AND temporal) OR ("defeasible reasoning" AND temporal) OR ("abductive reasoning" AND (temporal OR "event"))) | 287 | 121 | 104 | 79 | 76 | 33 |
| B5 Uncertainty and neuro-symbolic reasoning | ("probabilistic logic programming" OR "probabilistic logic" OR "probabilistic temporal logic" OR "temporal logic point process" OR "Markov logic" OR "annotated logic" OR "neuro-symbolic" OR neurosymbolic OR "differentiable logic" OR "logic tensor networks" OR "probabilistic event calculus") AND (temporal OR time OR sequence OR sequences OR events OR streams) | 1655 | 1192 | 207 | 63 | 75 | 20 |
| B6 Description logics, ontologies and ontology-based data access | ("description logic" OR "description logics" OR "ontology-based data access" OR OBDA OR "ontology-mediated") AND (temporal OR "time-stamped" OR "temporal data" OR "temporal query" OR "temporal queries") | 193 | 35 | 47 | 38 | 58 | 27 |
TABLE A4: KRR queries and hits (OpenAlex, 23 and 24 October 2026).
| Domain | Design-time task | Detection-time task | Sources |
|---|---|---|---|
| Propositional LTL | Satisfiability: PSPACE-complete | Past-time monitoring of a fixed propositional formula with memory independent of trace length | [ 316 , 249 ] |
| Metric temporal logic | Satisfiability: EXPSPACE-complete over integer time; undecidable over the reals in the pointwise and continuous semantics of infinite traces, with MITL EXPSPACE-complete | Online monitoring of monitorable first-order fragments | [ 317 , 318 , 157 ] |
| Complex event logic | — | Fixed queries in the unary-filter fragment: constant update cost per event, then constant-delay enumeration of results | [ 61 ] |
| Datalog | — | Query evaluation: P-complete in data, EXPTIME-complete combined | [ 250 ] |
| DatalogMTL | — | Fact entailment: PSPACE-complete in data, EXPSPACE-complete combined; tractable fragments in Appendix B.3 | [ 319 , 320 ] |
| Answer set programming | — | Stable model existence for finite propositional programs: NP-complete for normal, -complete for disjunctive programs | [ 250 ] |
TABLE B1: Complexity across KRR domains, by task.
| Q1 and Q5 are summarized per family in Table 5 and coded per system in the evidence ledger, which gives the passage behind every cell and also records the input layer and the eligibility of each paper for the Q4 and Q6 counts of Section 4.3. — means that no statement was located, and n/a means that the question does not apply. † marks systems coded from an abstract or a description in another paper, for which Q3 to Q6 could not be assessed. Family F lists the digital-forensics papers on time and event reconstruction, which are not detection systems. The ledger distinguishes delivery conditions and observations from statements about output validity under delivery failures. | |||||
|---|---|---|---|---|---|
| System | Family | Order (Q2) | Clocks (Q3) | Delivery (Q4) | Trust in the evidence (Q6) |
| Liu et al. 2019 (Log2vec) | L1 | Chronological edges between log entries of a user | — | — | — |
| Wang et al. 2020 (ProvDetector) | L1 | Causal paths in temporal order | — | — | Kernel, audit system or logs trusted (TCB) |
| ATLAS | L1 | Temporal order in an entity’s neighborhood | — | — | OS and audit trusted; causal graph tamper-proof |
| KAIROS | L1 | Windows of wall-clock time; queue across windows | — | Edges ingested chronologically as they appear in the stream | Kernel, audit framework and analysis code trusted |
| King and Huang 2022 (Euler) | L1 | Temporal link prediction across windows | — | — | — |
TABLE C1: Statements about order, clocks, delivery and trust in the evidence in the sampled systems.
| Dimension | What is assessed | ++ requires | or indicates |
|---|---|---|---|
| Correct evaluation of a declarative attack specification | Whether outputs are correct with respect to a stated declarative specification of attack behavior (Section 2, evaluation level); it concerns an explicit campaign or attack-pattern specification, and specifications of permitted program behavior (L5) are distinguished in the evidence and not counted | Sound, and where claimed complete, evaluation of such a specification | No declarative attack specification is evaluated ( ), or generation is unconstrained ( ) |
| Explanation form | The kind of justification an alert comes with | Not rated; the form is named | — |
| Independently checkable | Whether a single output can be verified by a checker separate from the producing system | A separate checker for the explanation format exists; whether that checker is itself formally verified is noted in the evidence per family below | No checkable format |
| Order and metric time | Native support for event order and time bounds | Metric temporal operators or constraints | Order ignored or only within windows |
| Long horizons | Whether reasoning relates evidence across windows, hours and days without a horizon-dependent cut-off | No cut-off on how far back evidence can be related; memory use is reported separately and may grow with the number of entities | Context capped by window or sequence length |
| Recursion and joins | Unbounded paths and joins across non-adjacent entities | Recursive rules or path queries, together with joins on shared variables | Bounded by message-passing depth, or no join construct |
TABLE C2: Assessment criteria for the dimensions of Table 6.
More in this topic
Cybersecurity
Cybersecurity develops methods to protect digital and cyber-physical systems from attacks, vulnerabilities, data loss, and misuse.
See all 355 papers