Algorithmic randomness and incompressibility in cybersecurity

The loop, from disclosure to detection

A detection engineer inherits a specific version of the incompressibility problem. The corpus a Large Language Model was trained on is frozen at some cutoff date; the vulnerability landscape of an organisation is never frozen, and the two facts collide in the same ninety days every quarter. A CVE is published. A proof-of-concept follows within days, sometimes hours. The organisation's own asset inventory does not know the CVE exists until someone tells it, and the next scheduled audit is weeks away. That gap is not a training problem. It is an intake problem, and it has the exact shape that algorithmic randomness predicts: the exposure is a new string, and no amount of computation on last quarter's scan results shortens it.

What arrives

Four kinds of stream feed the loop, and each has a different update rhythm. Disclosure feeds — the National Vulnerability Database, vendor advisories, the CISA Known Exploited Vulnerabilities catalogue — post structured records the moment a flaw becomes public, sometimes with a Common Vulnerability Scoring System number attached, sometimes not. Telemetry arrives continuously from endpoint agents, firewalls and identity providers: authentication attempts, process trees, DNS queries, at a volume that for a mid-sized estate runs into hundreds of millions of events a day. Malware corpora accumulate from sandboxes and threat-intelligence exchanges like VirusTotal, where a novel binary is a string with no prior entry, by definition incompressible against the existing signature set. Configuration drift arrives more quietly, as a cloud security posture tool notices that a storage bucket's access policy changed at 03:14 without a change ticket.

None of these four streams is optional and none substitutes for another. A perfect model of yesterday's telemetry says nothing about tomorrow's CVE. A perfect map of the CVE catalogue says nothing about which of the organisation's own machines run the affected library, at what version, behind what compensating control. Each stream carries a different slice of the incompressible residue, and the loop only functions if all four keep running rather than being sampled once and modelled from there.

What is held

Between arrival and action sits a belief store, and the honest version of that store looks nothing like a static risk register. Each entry — this host runs OpenSSL 3.0.2, this bucket is internet-facing, this CVE has a public exploit — carries a timestamp, a source, and a decay function. A vulnerability scan result is trustworthy for days, not months; a configuration snapshot pulled from a cloud provider's API is close to real time but only for the resource it touched; an EPSS exploitation-probability score updates daily and should be treated as stale by the following morning. Provenance matters because sources disagree. An asset inventory built from agent check-ins will miss anything unmanaged; a network scan will miss anything behind a segmentation boundary the scanner cannot reach. The belief that a given server is patched is not a fact filed once and trusted forever. It is a claim with an expiry date, and the expiry date is doing real work.

This is the point at which the lineage terminology earns its keep.

What triggers revision

Revision fires on a mismatch, not on a schedule. A new KEV entry lands, and it is joined automatically against the asset inventory: does anything in the estate run the affected product, at the affected version. A telemetry stream flags a process spawning from a document reader that has never done so before in this environment, and the belief "this host is clean" is downgraded before any human looks at it. A configuration scanner detects that a security group rule opened port 22 to 0.0.0.0/0, and the belief "this instance is not internet-facing" expires on the spot, not at the next audit. Each of these is a small act of absorbing an incompressible increment: something happened that the prior model, however good, could not have derived from what it already held. The alternative — waiting for the quarterly review to reconcile the register against reality — is exactly the failure mode the loop exists to prevent, and it is exactly the failure mode that keeps recurring in breach post-mortems, where the median finding is a control that was correct on the day it was checked and wrong for weeks afterward.

What the detection engineer sees

In practice the engineer does not see four streams. They see a queue, ranked and re-ranked as new evidence arrives, and the ranking is the whole product of the loop. A CVE with a public exploit, matched to an internet-facing asset with no compensating control, outranks a theoretical vulnerability on an isolated internal system, even if the second has a higher raw severity score. The interface that matters is less a dashboard than a diff: what changed since the belief store was last consulted, and why. A well-run version of this shows provenance on demand — this exposure is asserted from a scan three days old and a CVE feed updated an hour ago — so the engineer can judge how much to trust the ranking before acting on it. A badly run version hides the age of its inputs and presents everything with the same confident colour, which is how stale beliefs get treated as current ones and how the ninety-day gap opens in the first place.

What it costs

Running the loop continuously is expensive in a specific way: the cost is retention and reconciliation, not raw sensing. Telemetry at estate scale is cheap to generate and costly to store and query at the retention windows regulators and incident responders actually need, often twelve months or more. Reconciling four feeds with different update cadences and different failure modes requires a data model that tracks provenance and decay explicitly, which is more engineering than treating any one feed as ground truth. And false positives compound: a belief store that revises too eagerly on noisy telemetry drowns the queue and trains the engineer to ignore it, which is its own kind of failure. None of this is optional overhead. It is the price of the only remedy available for incompressible novelty, which is to keep watching rather than to model harder.

Two objections worth taking seriously

Most breaches trace back to known misconfiguration or unpatched systems, not to some exotic zero-day. Calling this "algorithmic randomness" dresses up an ordinary operations failure in mathematics it doesn't need.

That is largely true, and it does not weaken the point. Kolmogorov complexity is uncomputable in general and defined only up to an additive constant, so no engineer should invoke it as a diagnosis for a specific incident. The claim here is narrower: the counting fact behind the mathematics — that almost every specific configuration state has no shorter description than itself — explains why static inventories go stale. A misconfiguration is exactly an incompressible increment relative to the last audit: it cannot be derived from the prior snapshot, it can only be observed. The mundane operational failure and the formal argument point at the same fix, which is continuous intake rather than better modelling of old data.

Threat intelligence has gotten much better at generalising: family classification, YARA rules, behavioural detection all compress large volumes of novel-looking malware into a smaller number of recognisable patterns. Doesn't that mean novelty here is mostly compressible after all?

Genuinely, yes, and this matters. Most malware is not written from scratch; it repackages known families, and a good behavioural rule catches variants its author never saw. That is compression working exactly as intended. But every one of those rules was mined from samples already collected, and the rule's blind spot is precisely whatever the next sample does that the rule's authors did not anticipate — a new packer, a novel living-off-the-land technique, a supply-chain compromise with no prior family resemblance. The compressible majority is real. The residue is where the ninety-day exposures live, and the residue is only ever closed by the corpus growing, never by the model alone.

Why the axis stops here

Widening intake from a frozen disclosure archive, to a single scan, to every disclosure feed, telemetry stream, malware sample and configuration change held open with provenance and decay, is not a matter of taste. It is the only available response to a residue that is incompressible by definition. Past that point the improvements are more sensors, longer retention, better-trusted sources and finer decay models — matters of degree, not a new category of evidence. There is no fifth stream waiting beyond everything, continuously, with provenance attached.