SoK: Timestamps Are Not a Time Model: Rethinking Temporal Reasoning in Host-Based Intrusion Detection

Rene Heinzl, Markus NisslarXiv 2026 · arXiv

TL;DR

Host-based intrusion detection systems (HIDS) rely on timestamps to reconstruct complex attacks, yet they often treat these values as perfect ground truth. This paper reveals that most modern detectors make dangerous, unstated assumptions about clock synchronization and log integrity, and it proposes a formal framework to make temporal reasoning explicit, robust, and checkable.

What Problem Does This Paper Address?

In the world of cybersecurity, "when" something happened is just as important as "what" happened. To detect Advanced Persistent Threats (APTs), HIDS must link events across long time horizons and multiple hosts. This process relies entirely on timestamps.

However, a timestamp is not a "time model." In reality, clocks drift, network logs arrive out of order or late, and sophisticated attackers use "timestomping" to rewrite file attributes. The authors argue that the current generation of provenance-based detectors—systems that model system activity as a graph of information flow—largely ignore these issues. They often assume a "Trusted Computing Base" where logs are immutable and clocks are perfectly synced, leaving them vulnerable to mimicry and evidence manipulation.

Methods

The authors performed a massive Systematization of Knowledge (SoK) by:

  1. Literature Audit: Screening 4,869 security and 2,550 Knowledge Representation and Reasoning (KRR) papers. They performed a deep-dive audit of 160 full-text papers to see what they actually state about their time and evidence assumptions.
  2. Framework Distillation: They defined five components of a formal time model (domain, notion of time, delivery assumptions, order basis, and verdict policy) and a checklist of six evidence assumptions.
  3. Formal Assessment: They evaluated 11 symbolic KRR formalisms (e.g., Metric Temporal Logic, Event Calculus, DatalogMTL) and a learned baseline against nine precisely specified attack-reasoning patterns.
  4. Guarantee Levels: They categorized system claims into four levels: Specification (is it defined?), Evaluation (is the algorithm correct?), Certificate (can output be checked?), and Correspondence (does it match reality?).
TABLE 3. FOUR LEVELS OF GUARANTEE.

Datasets

As an SoK paper, this work does not introduce a new experimental dataset. Instead, it analyzes the methodologies used in systems evaluated on established benchmarks like:

  • DARPA Transparent Computing (TC)
  • OpTC
  • SWaT (for cyber-physical systems)

The authors point out a "performance plateau" and note that recent re-evaluations of learned detectors suggest that reported benchmark accuracy often overstates real-world quality once evaluation conditions become more realistic.

Key Insights and Ideas

  • The "Correspondence" Gap: Most research focuses on "Evaluation" (proving an algorithm matches its spec). However, if the input logs are manipulated or delayed, the "Correspondence" to what actually happened on the host breaks down.
  • Vanishing Rigor: Interestingly, early alert correlators from the early 2000s were often more explicit about clock skew and delivery failures than modern, high-tech provenance detectors.
  • Not All Times are Equal: The paper distinguishes between four notions of time (Event, Observation, Metadata, and Causal Order). Confusing these—for example, using observation time to infer causality—leads to false positives or missed detections.
TABLE 2. FOUR NOTIONS USED TO INTERPRET TIMESTAMPS AND ORDER.
  • KRR is Underutilized: While the KRR field has mature tools for reasoning about "imprecise" time and "incomplete" evidence, these are rarely applied to host audit data. Most modern systems use system-specific procedures or LLMs to "compose" a campaign rather than declarative temporal logic.
Figure 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.

Key Results

  • Trust is the Default: In 28 of 38 audited provenance-era papers, the capture mechanism or stored evidence is simply "trusted," with no discussion of what happens if records are deleted or forged.
  • Missing Bounds: Not a single sampled system stated a numeric bound on clock offset (e.g., "this system works if clocks are within 100ms of each other").
  • Expressibility Gaps: No single assessed KRR language covers all nine attack patterns natively. For example, reasoning about "absence with exceptions" (detecting a process start without a preceding logon) is only native in a few formalisms.
  • The Running Example: The authors walk through a credential-theft scenario to show that a "campaign claim" is actually a chain of hypotheses resting on unverified correspondence assumptions.
TABLE 4. THE RUNNING EXAMPLE: OBSERVED FACTS, DERIVED HYPOTHESES AND CORRESPONDENCE ASSUMPTIONS.

Limitations and Future Work

The authors acknowledge that their findings are bounded by their specific literature search and a single coding process. Because they focused on highly-cited and landmark systems, they might have missed niche papers that do address these temporal gaps.

Future Directions: 1. Typed Interfaces: Creating better handshakes between "learned" detectors (which output scores) and "symbolic" reasoners (which compose campaigns). 2. Robustness Benchmarking: Developing new benchmarks that specifically inject "evidence attacks" like clock skew, delayed logs, and deleted records to see which detectors survive. 3. Certified Explanations: Moving toward systems that don't just say "this is an attack," but provide a checkable proof tree linking the alert back to specific, verified audit records.

Summary updated

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.
BibTeX
@misc{heinzl2026sok,
  author = {Rene Heinzl and Markus Nissl},
  title = {{SoK: Timestamps Are Not a Time Model: Rethinking Temporal Reasoning in Host-Based Intrusion Detection}},
  year = {2026},
  eprint = {2610.35151},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.35151},
}
Figure