WorksComputer Science
Mine Locally, Verify Globally: Exact Recovery, Compilation, and Distortion of Mined Temporal Rules
Abstract
Specification mining extracts temporal rules that describe relationships between events in recorded system traces. Applying these rules in distributed monitoring systems is more difficult because observations come from different nodes, whose clocks may not be synchronized, and events may be lost or reordered during transmission. In this paper, we study how to aggregate the coverage of mined rules across observers, determine whether their temporal windows are needed during monitoring, and characterize their detection under event loss. Our evaluation uses IPv6 packet traces collected from 21 receivers across four continents. We show that local mining followed by global confirmation recovers centralized rule coverage under suitable conditions while substantially reducing communication overhead. In contrast, merging traces with unaligned clocks can distort coverage by introducing incorrect temporal matches. A window-gain criterion identifies rules that require temporal state, while our loss analysis and broker experiments demonstrate why contiguous losses can be more damaging than independent losses. The results identify separate requirements for aggregating observations, selecting monitor state, and handling event loss.
Introduction
Runtime verification checks a system while it runs. It is useful when correctness cannot be settled before deployment [26, 27, 28]. A monitor needs two things, a property to check and evidence to check it against, and each has its own literature. Writing properties by hand scales poorly. Specification mining therefore infers them from observed behaviour, as data invariants [8], as temporal rules [9, 10, 12], or as rules with explicit time bounds [6]. Evidence in a distributed system is spread over many nodes. Decentralised runtime verification therefore splits a formula across the nodes that observe it and combines their verdicts [18, 19, 20, 21]. Layered monitoring architectures add delivery and continuity guarantees, so that a verdict keeps its meaning when a component crashes or is overloaded [2].
These two lines of work rarely meet. Miners run centrally and offline. A mined rule is judged by how well it scores on the traces it was learned from. Monitors execute properties that a person wrote, online, over a network that may drop, delay and reorder events. Nobody has measured what a mined rule’s verdict is worth when its evidence arrives incomplete or out of order. Runtime verification does study imperfect observation, but mostly as missing events [30, 31, 32, 33, 35]. Disorder is treated as a problem for the monitoring algorithm, which should undo it [36].
We met this question in a concrete setting. Our dataset comes from an active-probing campaign. Twenty-one receivers on four continents record which IPv6 extension headers survive transit [7]. The properties an operator would want have exactly the shape of a mined rule, for example “if the payload is not medium-sized, then no fragment header follows within four seconds”. The monitoring fabric that would run such a rule is also real, with bounded buffers, a crash window and a wide-area path [2]. We expected loss to be the main problem, since lost events cost detections. The experiments showed a different picture. Our rules ask for some matching event inside a window. Losing one candidate is cheap when the window holds many. Reordering the stream, on the other hand, moves extra candidates into windows and creates matches that never occurred. Merging traces from observers whose clocks all start at zero does the same, because a window at one receiver can then be satisfied
Full version of a short paper accepted at the 28th International Conference on Distributed Computing and Networking (ICDCN 2027), Surathkal, India, January 4–7, 2027. This is the authors’ version, released under CC-BY 4.0. by an event recorded on another continent. A monitoring system pays for false alarms [41, 42], and these invented matches become false alarms.
We organise the paper around three questions. Each answer has a proof and a measurement.
Where should mining run? Coverage, the score we use, adds up across observers. Mining at each observer and exchanging short summaries is therefore exact, not an approximation (Sect. 3). The step that needs justification is the usual one, central mining over merged traces.
Which mined rules need a temporal monitor? Earlier work found that the main rule of this dataset is a co-occurrence inside a single packet. Its time window does nothing [1]. We turn that observation into a compilation decision that applies to any rule (Sect. 4).
What does the transport do to a deployed rule? It distorts the score in both directions. In the cases we measured, invented matches were the more frequent direction (Sect. 5). Loss follows a law indexed by redundancy inside each window. A law indexed by rule length gives wrong answers. Reordering is harder to summarise. Very large displacement ends at the rule’s same-event version, which we define in Sect. 4. The shuffle test of Sect. 4 measures something else. Neither of the two bounds the effect of moderate displacement, which can exceed both when the displacement scale is close to the rule’s window.
Contributions. Figure 1 shows the pipeline end to end.

Figure 1. Overview of Mine–Merge–Confirm–Gate (Algorithm 1) on 21 observers holding 757,932 packets. No raw trace crosses the network. Observers exchange rule descriptions, count pairs and scalar summaries. For the mining rounds this costs 1658× less than shipping the traces, and it is exact when the traces are separated in time by more than a rule spans (Thm. 3.1). The gate uses the window gain to decide whether a rule keeps window state (Thm. 4.1). The ordering guarantee is decided from , the largest score change over the displacements the deployment admits (Prop. 5.4). The delivery guarantee comes from the loss law (Thm. 5.2).
A distributed mining protocol with an exact recovery identity (Thm. 3.1) and a communication bound (Prop. 3.2). We also measure the merging inflation: 79.9 percentage points on one rule, removed completely when the observers’ clocks are offset.
A two-stage compiler pass (Sect. 4). The first stage tests whether a rule needs its window and removes unneeded window state, with a soundness result (Thm. 4.1). The second stage measures how sensitive the remaining windowed monitors are to event order.
A detection law under loss (Thm. 5.2). An exact characterisation of where large displacement ends, together with a proof that the shuffle test does not reach that end point (Prop. 5.3). A counterexample to the natural conjecture that the shuffle gap bounds the effect of displacement (Prop. 5.4).
The 5-page conference version presents the first result in full and the other two in short form. This version adds all proofs, the reordering analysis, the false-alarm study and the broker measurements.
The rest of the paper is organised as follows. Section 2 defines the system, the rule model and the transport. Section 3 gives the distributed mining protocol, and the theorem that it recovers central coverage exactly, and the measurements. Section 4 introduces the compilation gate: the window gain, the shuffle gap and the out-of-sample check. Section 5 studies loss, reordering and the false alarms they cause, and measures real brokers. Section 6 states the threats to validity, Section 7 reviews related work, and Section 8 concludes. Appendix A contains the proofs.
| Symbol | Meaning | Symbol | Meaning |
| observers, | rule (1); its window | ||
| trace at observer | same-event version | ||
| rules mined at | local, global thresholds | ||
| local coverage; target count | coverage of the union | ||
| window gain (4) | shuffle gap (3) | ||
| largest score change over | tolerances | ||
| irreplaceable | windows; candidates in | ||
| loss rate; displacement width | loss budget; req. detection |
Table 1. Notation. The upper block is fixed by the dataset and the rule language. The lower block is computed or set by the deployment.
System and Rule Model
This section fixes three things: the shape of a mined rule, what an observer holds, and which timestamps a monitor reads. It also defines the terms used in the rest of the paper.
Rules
Table 1 collects the notation. We use the bounded-past rule language of PSIMINER [6]. A rule has the shape
Each bucket is a set of Boolean conditions on the attributes of one event. is the target condition. The symbol \##[0:k] means that the next bucket holds at most time units later. A match of the rule for a target event is a choice of events, one per bucket, that satisfy the buckets and respect these time bounds. We call such a choice a witness.
The time bound is existential. The rule asks that some matching event lies inside the window. It does not ask for a particular event. All results in Sect. 5 depend on this property.
The template leaves one convention open, and we fix it. Two different buckets may be satisfied by the same event when the time bounds allow it. This choice is used twice. The same-event version of Sect. 4 relies on it. The loss law of Thm. 5.2 needs witness events to be distinct, and states this as an explicit assumption.
Each rule has two scores. Coverage is the fraction of target events whose window contains a matching antecedent. It equals , where is the number of target events and is the number of those that the rule explains. Confidence is the reverse conditional, the fraction of antecedent matches followed by a target. We report the two separately, because mixing them makes association metrics misleading [1]. The protocol of Sect. 3 thresholds on coverage only. This is what makes Thm. 3.1 apply. Coverage is a ratio of counts, and counts add up over observers. With a threshold on both metrics, the observer with the highest coverage and the observer with the highest confidence can differ. Then no single observer needs to propose the rule. Extending recovery to a two-metric acceptance rule is open.
Observers
An observer is a node that holds its own trace and keeps its own clock. A distributed dataset is a family of traces , one per observer. Both properties are used below. Locality is what lets mining be distributed. Separate clocks are what make naive merging unsound.
Our dataset is the JAMES IPv6 extension-header dataset [7]. It has 21 controlled receivers on four continents (called vantage points in that work) and 757,932 packets. Each receiver captures what reaches it from a common set of senders. Header stripping in transit is therefore observable. We project each trace to a fixed per-packet schema that uses only IPv6 header fields.
Every receiver starts its clock at zero, and each trace spans roughly 4000 to 5400 s. Nothing in the dataset aligns the clocks. Section 3 shows what this costs when the traces are merged.
Key terms. Two terms recur and are defined here. Exact recovery means that a distributed procedure reports the same coverage as a central miner run on correctly separated traces. It is an identity, not an approximation. Merging inflation is the extra coverage that appears when all traces are placed on one time axis. A window opened at one receiver can then be satisfied by an event recorded at another.
Transport
Deployed monitors run over a monitoring fabric [2]. It has a message broker that receives events from devices and a durable broker that forwards them from the gateway to the back end. A small service attaches a timestamp to each event, and a local store keeps outgoing messages until their delivery is confirmed. The fabric offers guarantees on delivery, ordering, clock progress, isolation between consumers, and flow control.
We evaluate rules over the timestamps seen at the monitoring tier. These may be arrival times or broker timestamps. Transport delay therefore changes the time values that a rule uses. A deployment can avoid this by keeping trusted source timestamps and re-sorting events by source time before evaluation. That costs buffering, clock synchronisation and latency. This re-sorting is what the fabric’s ordering guarantee provides. The guarantees limit two remaining effects without removing them, and these two effects are our parameters. The first is per-event loss with rate . It comes from bounded buffers under sustained overload and from the crash window between delivery and durable storage. The second is reordering by up to time units on a wide-area path.
Distributed Specification Mining
A dataset collected at many observation points is normally mined by gathering all traces and mining their union. For coverage-based mining this step is unnecessary, because coverage adds up over observers. It is also unsafe. The observers of a real campaign do not share a clock, and merging their traces creates matches across observers. This section gives the protocol, the identity that justifies it, and the measured cost of naive merging.
Protocol
The protocol is called Mine–Merge–Confirm and runs in three rounds. Algorithm 1 gives the full procedure, including the gate of Sect. 4.
Round 1 (mine). Each observer runs the miner on its own trace with a local threshold and obtains a set of candidate rules . No trace leaves the observer. For every candidate, the observer sends a rule description to the gateway. A description lists the buckets, the window, the target and two counts: the number of targets the rule explains at that observer and the observer’s total number of targets . Its size depends on the number of buckets and not on the trace length.
Round 2 (merge). The gateway forms the union of all proposed rules. For each rule it can compute a weighted average of the coverages it has received, with each observer weighted by its number of targets,
where the sums run over the observers that proposed . This value is only an estimate. An observer whose local coverage was below , or whose miner failed, did not propose the rule and sent no counts for it. The gateway therefore applies no global threshold in this round.
Round 3 (confirm). The gateway sends every rule in back to every observer. Each observer checks the rule against its own trace, without mining, and returns its exact pair of counts. Now the gateway has counts from all observers, and the coverage of the union, , is exact. The gateway keeps the rules with . This round is what makes Thm. 3.1 usable in practice. It costs one more exchange of descriptions and never transfers events.
Algorithm 1 Mine–Merge–Confirm–Gate. Rounds 1–3 are Sect. 3. Round 4, the gate, is Sect. 4, and the guarantee and placement choices are Sect. 5. No raw trace crosses the network. Observers exchange rule descriptions, count pairs and scalar summaries.
Require: local traces ; thresholds ; compilation tolerance ; reordering tolerance ; loss budget ; required detection ; displacement grid that the transport admits, with its worst case
Ensure: for each accepted rule, a compiled form, a guarantee set and a tier
Precondition. The are separated in time by more than the span of every candidate, which is at most for an -bucket rule (Thm. 3.1). If the observers share a clock origin, offset the clocks first. Otherwise the merge inflates coverage.
Round 1: mine, at every observer in parallel
for each in parallel do
send to the gateway size independent of
end for
Round 2: merge, at the gateway
for each do
estimate only; no threshold
end for
confirm the whole union
Round 3: confirm, with exact counts from every observer
for each do
send to all; each returns checking only, no mining
exact
drop if
end for
Round 4: gate, plan, place. Each observer computes the same-event score, the shuffled scores and the displaced scores for on its own trace and returns scalars. The gateway averages them, weighted by target counts.
for each do
window gain, Eq. (4)
shuffle gap, Eq. (3)
if then
; Thm. 4.1
else
absolute value: disorder can raise or lower
if not from , Prop. 5.4
end if
largest , smallest
if exact then hypotheses of Thm. 5.2 hold
if
else
; mark uncertified
end if
place at the shallowest tier whose evidence path meets under
end for
return
Topology and message count. All messages go between an observer and the gateway. Observers never message each other, so the communication graph is a star. In Round 1 observer sends descriptions. In Round 3 the gateway sends each of the confirmed candidates to each of the observers, and each observer answers with one pair of counts per candidate. The protocol therefore uses messages in total. This is linear in for a fixed candidate set. It becomes quadratic in only when the observers propose disjoint rules, so that itself grows with . In our dataset the union has four rules.
Algorithm 1 also shows how the three results connect. The merge needs the traces to be separated in time. The gate takes the merged score and returns a compiled form and an exposure to reordering. The witness structure turns that into a guarantee set and a tier. The rest of this section analyses Rounds 1–3.
Exact Recovery
Write for the coverage of rule at observer , for the number of target events at , and for the coverage that a central miner reports on the union of all traces.
Coverage is a ratio of two counts. If no window can reach from one observer’s trace into another’s, both counts of the union are sums of the observers’ counts. The coverage of the union is then a weighted average of the local coverages.
Theorem 3.1 (Recovery). Suppose every condition of is evaluated within a single observer’s trace, and the traces are separated in time by more than the span of the rule, that is by more than for an -bucket rule. Then
Hence, if , every such rule that a central miner accepts is proposed by at least one observer, and Mine–Merge–Confirm recovers it. Two conditions are needed: at least one proposer’s description reaches the gateway, and every trace is available for checking in Round 3.
Proof. We split the union into the observers’ traces. With the separation assumed, every window lies inside one trace. The number of explained targets of the union is then the sum of the observers’ numbers, and the same holds for the number of targets. This gives the equality. Note that disjoint traces are not enough by themselves. Traces that are adjacent in time would let a window reach across the boundary. A separation larger than prevents that. Our offsets separate observers by an hour, against s. A weighted average cannot exceed its largest term. Since , some observer has and proposes .
After Round 1 nothing removes before confirmation. Round 2 forwards the whole union, and . Round 3 applies to exact counts from every observer. A screen on in Round 2 would fail when a miner fails. An observer whose miner failed contributes nothing to , however high its coverage. For example, let and , and let two observers have equal target counts. One proposes the rule with . The other has but its miner failed. Then , while . A Round 2 screen would drop a rule that has a valid proposer.
Thm. 3.1 has the same structure as the lemma for distributed association rules by Cheung et al. [5]: any itemset that is frequent globally is frequent at some site. Coverage plays the role of support, and a time window plays the role of the itemset. The hypothesis does not carry over. Support adds up over any split of the data. Coverage adds up only when no window spans two observers. The measurements below show the practical effect of this difference.
Measurement
What the miner produces. We ran PSIMiner once per observer, over a shared vocabulary, with FRAG as the target. The sets are therefore measured, not assumed. They are small. Each observer produced 0 to 3 assertions, 1.38 on average, and the union has four distinct rules. For the traffic figures we use a stipulated set of seven candidate rules at every observer, which gives the conservative 1658× of Prop. 3.2. With the miner’s own output, Round 3 costs more than Round 1, because confirming a four-rule union at 21 observers costs more than proposing it.
Two observations matter more. First, rule R1 was proposed independently by 18 of the 21 observers, with support between 80.4 and 90.3 and correlation between 89.5 and 98.9. The uniform case of Thm. 3.1 is therefore realised by the miner itself. Second, the miner crashed on 7 traces, three of them before writing any output. Local mining is therefore incomplete for a reason unrelated to the thresholds. This is why Round 2 forwards the whole union. Confirmation in Round 3 adds the counts of an observer whose miner failed, and R1 survives 7 such failures after 18 proposals. These are failures to generate candidates, not failures to read a trace. Round 3 still needs every trace to be readable by the checker. No round can recover a rule that no successful miner proposed. One surviving proposer per accepted rule is therefore required. That is weaker than complete local mining, but it is a real requirement.
Coverage over all observers. Table 2 evaluates five candidate rules over all 21 observers. The window gains of R1 and R2 appear in Table 3. For rules whose signal lies inside one packet, the weighted average and the merged value agree closely. For rules whose antecedent and consequent are different extension headers they differ sharply. R4 has coverage between 2.55% and 22.00% at every single observer, and its weighted average is 11.64%. Naive merging reports 91.59%, an inflation of 79.9 percentage points. R5 behaves the same way, with 78.9 points.
| Rule | local range | weighted | naive | offset |
| R1 ¬MED→¬FRAG | 89.7–98.5 | 95.04 | 99.70 | 95.04 |
| R2 MED→FRAG | 100.0–100.0 | 100.00 | 100.00 | – |
| R4 DST→RT | 2.6–22.0 | 11.64 | 91.59 | 11.64 |
| R5 RT→FRAG | 4.0–25.2 | 16.58 | 95.50 | 16.58 |
| R6 HLIM→FRAG | 96.7–100.0 | 99.35 | 100.00 | – |
Table 2. Coverage (%) over all 21 observers. Weighted is Thm. 3.1. Naive merges the traces as recorded. Offset merges them after separating the observers in time. All rules use window [0:4] s. MED abbreviates PLEN_MED.
Table 3: Window gain and shuffle gap (points of coverage). decides compilation. reports sensitivity to the shuffle only. R6 is the key case. Its interval contains zero while its interval is near 78. A single statistic would misclassify it.
| Rule | [95% CI] | [95% CI] | compile | guar. |
| R1 | 4.20 [2.39, 6.01] | −3.58 [−5.5, −1.7] | windowed | warn |
| R2 | 0.00 [0.00, 0.00] | 0.00 [0.00, 0.00] | stateless | – |
| R4 | 15.63 [9.10, 22.2] | −83.9 [−90.5, −77.4] | windowed | warn |
| R5 | 18.17 [10.8, 25.6] | −81.3 [−88.7, −74.0] | windowed | ord. / |
| R6 | 78.37 [76.1, 80.7] | −0.31 [−1.23, 0.61] | windowed | none / |
Table 3. Six observers, fifteen shuffles each over the full attribute tuple of (3); . Student- intervals with 5 degrees of freedom across observers. The within-observer shuffle standard deviation is at most 0.101. warn marks a large gap for which no displacement sweep was run. We make no deployment claim for these. The guarantee comes from (Sect. 5). Only R5 and R6 were swept.
The cause is the shared clock origin of Sect. 2. Merging puts 21 traces on one time axis. A window opened by an antecedent at one receiver can then be closed by a consequent recorded on another continent. The fix is to meet the hypothesis of Thm. 3.1. We offset each observer by the span of the previous one plus one hour. The merged value then equals the weighted average, with residuals of −0.000, +0.000 and +0.000 points on R1, R4 and R5. Thm. 3.1 is therefore not an approximation of central mining. It states central mining correctly. Naive merging is an error that is easy to miss, because it raises the reported score.
Proposition 3.2 (Communication). Including the confirmation round, the protocol exchanges symbols, where is the largest number of buckets in a candidate rule. This is independent of trace length. Merging the traces costs .
Proof. In Round 1, each locally mined rule costs one description of symbols plus two counts, and there are such rules. Round 2 happens at the gateway. In Round 3, each of the candidates is sent to all observers, and each returns a pair of counts. This costs symbols. No round sends events. Hence no term depends on . Merging sends every event.
The term is the price of exactness. The saving holds whenever the candidate set is small compared with the traces, which is the usual situation in mining. With seven stipulated candidates per observer and , Round 1 sends 10,101 B of descriptions. Round 3 sends the same amount and receives 1,176 B of count pairs. The total is 21,378 B, against 35,635,638 B for the traces. Round 1 alone is 3508× smaller. We quote 1658× for the full protocol, because only the full protocol computes an exact answer.
The Compilation Gate
A miner writes its rules with temporal operators. That does not show that the window does any work. Two separate questions arise. The first is whether a check on single events, with no window and no state, would give the same score. If so, the window and its state are wasted. The second is how much the score depends on the order of events inside the window, because order is what the transport disturbs. Each question gets its own statistic. We also show a real rule for which using the wrong statistic would have been costly.
Two Statistics
Shuffle gap. Let be a joint-row shuffle. It permutes the per-event attributes but leaves whole units over the fixed list of timestamps. Every association inside an event and every marginal distribution is kept. Only the order of events changes. The shuffle gap is
A negative Δ means that shuffling raises the score, and a positive Δ means that it lowers it. |Δ| is the size of the effect in either case.
A gate that compiles a rule to a stateless check whenever Δ is small would drop rules that need their window. Consider a rule whose antecedent and target never hold in the same event, with a window wide enough that almost every target has some antecedent inside it. Shuffling barely changes its score, and Δ ≈ 0. Its stateless version requires antecedent and target in one event. That never happens, and its score is zero. A small Δ says that order carries little information. It does not say that the window carries none. Saturated rules are exactly this case (Sect. 5.3).
Window gain. The gate must therefore compare a rule with its stateless version. The same-event version of sets every window to [0:0]. All buckets must then hold in one event. The window gain is
Theorem 4.1 (Gate soundness). Let the score be coverage. If , then the per-event check has a coverage at most below that of . In other words, window state adds at most to the score.
Proof. For positive existential rules, is a stronger condition than . Any witness of is a witness of in which all buckets fall on one event. Hence and . The rule needs all buckets at one event. It can therefore be evaluated without window state. By assumption its score is at most lower than that of . The argument needs coverage. With confidence as the score, a stronger antecedent can move the conditional in either direction. □
The guarantee holds for the trace and score on which was computed. We therefore test the decision on held-out data. We fixed two splits before computing . The first divides 12 observers into two groups of six. The second divides time into a first and a second half. Identifiers, seeds and per-rule values are in the artifact. In both splits, every decision taken over the pooled observers held on the other part. The one rule compiled stateless, R2, has held-out . No windowed rule has a held-out below . Decisions taken at single observers did not transfer. At one observer moved by up to 28.3 points between halves, and two rules would have been compiled stateless although their held-out exceeds . This supports taking the decision at the gateway.
The gate keeps the two statistics apart. decides compilation, that is, whether the window is worth its state. measures sensitivity to the shuffle, which keeps the timestamps in place and moves only attributes. § 5 shows that does not bound the effect of moderate displacement. A rule with compiles to a per-event check, with no window that could be disordered. A rule with keeps its window. Its ordering requirement is then decided by over the range of displacement that the deployment admits. A large may not be reached inside that range, and a small is no evidence of safety (Prop. 5.4).
Measurement
Table 3 reports both statistics. The main rule of the dataset, R2, has . Its window adds nothing over its same-event version, and by Thm. 4.1 it compiles to a stateless check. This turns the earlier negative finding on this dataset [1] into a decision procedure.
R6 shows why the two statistics must be kept apart. Its window gain is [76.1, 80.7], while its shuffle gap [−1.23, 0.61] contains zero. The window is essential, yet the ordered and shuffled scores cannot be told apart. We do not conclude that order is irrelevant for R6. The rule is almost saturated at 99.24, which limits how far any reordering can move it. The evidence is therefore weaker than the interval suggests. A gate based on , as
in our earlier formulation, would have compiled R6 to a stateless check and lost almost eighty points of coverage. As an instance of Algorithm 1, R5 has and is compiled as windowed. Its over the swept range is 33.3 points, which puts ORDERING in its guarantee set. R2, R6 and R1 (a variant of R1 with a zero-width window) have and request no ordering guarantee.
Shuffling almost always raises the score. In a randomly ordered dense trace, some event easily falls inside a window. § 5 starts from this observation.
Loss, Reordering, and Induced Distortion
A rule that passes mining and compilation can only be as good as the evidence that reaches it. The two transport effects that cannot be avoided behave very differently. Loss has a closed form that depends on the traffic, not on the rule’s syntax. Reordering has no such form. It lowers scores as easily as it raises them; its worst case lies between small and large displacement, and the cheap shuffle statistic measures something else.
Detection Under Evidence Loss
A simple estimate says that a rule which needs events to witness a violation detects it with probability under independent per-event loss . For existential windows this is wrong, and the error is measurable. Our windowed rules lose detection like , not like . A window usually holds many interchangeable candidates, and all of them are lost together only with probability .
Definition 5.1 (Witness structure). Fix a rule and a violation. Its witness consists of a irreplaceable events, which the rule pins down uniquely, and, for each existential window , a set of candidates, any one of which completes that window. The target event is always irreplaceable. If it is lost, the detection is lost whatever happens to the antecedents. An antecedent bucket is irreplaceable only when its window happens to hold exactly one candidate.
The witness structure belongs to a violation. A rule therefore has one per target. When we quote a single , we take the largest and the smallest over the targets. This makes (5) a conservative guarantee. When we compare with measured averages we use the dataset mean .
Theorem 5.2 (Detection under loss). Let a violation of have irreplaceable witness events and existential windows with candidate sets of sizes . Assume that (i) the events and the candidate sets are pairwise disjoint, (ii) they are freely combinable, that is, any choice of one member from each candidate set, together with the events, is a witness, and (iii) they are exhaustive, that is, the violation has no other witness. Under independent per-event loss with probability ,
Proof. Detection needs every irreplaceable event to arrive. By independence this has probability . Each window must also keep at least one candidate. This fails only if all candidates are lost, which has probability . Disjointness makes the survival of different sets independent. Free combinability makes the intersection of these events. The factors therefore multiply. The rule is positive in its buckets. Loss can therefore remove a detection but never create one. □
Free combinability is as important as disjointness. Without it the formula fails in the unsafe direction, because consecutive links of a chain can be coupled. A survivor in one window is useful only together with a compatible survivor in the next. Take , a target at , first-window candidates at and , and second-window candidates at and . Each second-window candidate is compatible with exactly one first-window candidate. Detection is then , which is lower than (5). We measure this case below. Overlap between windows pushes the other way, because shared events create positive dependence. So (5) is exact under its assumptions, and without them it is not a bound in either direction. This is important because Algorithm 1 uses it to decide whether to request a delivery guarantee.
Disjointness is what turns (5) into a product. When windows share events, the survival events of the windows become positively dependent. The product of the marginal probabilities then understates detection. Two windows that share one candidate survive together with probability , while the product gives . For monotone survival events under independent loss the product is a lower bound in this case. An exact value would need the reliability polynomial of the witness hypergraph. Our chain rules satisfy disjointness because of the projection we use, not because of IPv6. The schema records one nxt value per packet. The has_*_EH conditions are therefore mutually exclusive within one event, and no event can fill two buckets. A projection that kept the full header chain would lose this property. The chain results would then be lower bounds. We do not treat the general overlapping case.
Equation (5) contains the length-based formula as the special case , , which gives . It also explains why real windowed rules behave like . In a dense trace no antecedent window holds exactly one candidate. The target is then the only irreplaceable event, and .
We validated all three parameters on planted witnesses. Sweeps over at , and over against , agree with the law to within 0.0155 and 0.0098. Both sweeps have , and the dataset cannot test the product either, because window occupancies of 36 to 565 put every factor within of one. We therefore planted explicit timestamped chains with small , dropped events independently, and decided detection by a backward search for a witness among the surviving events. The geometry of the trace, not (5), fixes the outcome in this test. Over and , with 200,000 blocks per cell, the law holds to within 0.0025, against a binomial standard error of 0.0011. The test discriminates. At these cells range from 0.0625 to 0.4375. The coupled chain measures 0.2190. This matches its own closed form (0.2188) and not (5) (0.2812). The overstatement grows from 1.7% at to 28.6%. Free combinability is the dividing line, and we measured both sides of it.
Occupancy decides fragility, length does not. The template (1) allows any number of antecedent buckets. Longer chains might be expected to be more fragile. They are not. We implemented the full -bucket template, which the published validator cannot express. Chains of one, two and three buckets over sparse cross-family flag
at s degrade identically. They track to within 0.005 at . Each link is existential, and the measured occupancy of 36 to 565 candidates puts at every link, with throughout. Occupancy is not a property of the trace alone. At one fixed observer, changing only the rule moves the median occupancy from 0 to 58 at , and takes both values 1 and 2. The pair of rule and trace fixes , and the gate has to measure it. Thinning confirms the mechanism. We keep each non-target event with probability . This also occupancy and leaves the rule and its targets unchanged. At , detection stays at the linear value (0.501, 0.508, 0.495, 0.492) while the median occupancy falls from 372 to 109, 42 and 12. It then moves toward the quadratic value at (0.444 against the law’s 0.469) and at (0.352 against 0.250). The remaining gap comes from evaluating the law at the median of a skewed distribution.
Natural traffic lies beyond the end of this axis. The MAWI backbone capture of 31 December 2025 carries 508 extension-header packets among 8,246,274 IPv6 frames, a prevalence of 0.0062%. It has no Routing, Destination Options, ESP or AH headers at all. This is consistent with the reported dropping of packets with extension headers [?]. Windows in that trace are empty, not just sparse. It yields no cross-family witnesses and cannot measure detection. This is why the behaviour is probed actively. It also limits where such rules can be deployed at all.
On JAMES, relative detection at is 0.899, 0.701 and 0.501 for the same-event rule, and within 0.005 of these for both windowed rules. All of them track , as (5) predicts at and . A length-based estimate would give 0.810, 0.490 and 0.250 and cannot explain the data.
Distortion Under Reordering
Reordering can remove detections or invent them. Which effect dominates depends on where a rule’s evidence sits relative to its window, not on the transport. For the network and industrial rules we measured, the dominant effect is inflation. Moving timestamps brings extra candidates into windows and raises the score.
Additive displacement and the shuffle of Sect. 4 are different perturbations. Displacement adds a random offset to each timestamp and re-sorts the events. Large displacement eventually spreads events so far apart that no two lie within one window. The shuffle keeps the timestamps in place and therefore keeps the density of events in time. Displacement taken to its limit might be expected to give the shuffled score. It does not, because our rules are bounded in time, not in position.
Proposition 5.3 (Displacement end points). Let the displacements be , where the are independent, continuous and have a bounded density. Let score be the expected score after displacement and re-sorting, on a finite trace with fixed window . Our experiments use , so that . Then score and , the score of the same-event version. The total change from one end point to the other is exactly .
Proof sketch. Under large displacement, coincidences disappear. For two distinct events the displaced gap has density . A union bound then shows that, with probability tending to one, all events are more than apart. Only witnesses inside single events remain, and these are the witnesses of . Appendix A gives the details. □
This limits how may be used. The shuffle holds the timestamp grid fixed. It keeps the density that makes matches across events possible. Displacement destroys that density. For a logic with bounded durations the two are therefore not equivalent in the limit. is best read as a cheap test of whether events are exchangeable. On the synthetic trace tight, described below, the shuffle gives 0.248 and displacement at gives 0.002.
Prop. 5.3 fixes the two end points of the displacement curve. It says nothing about the curve between them. A natural conjecture is that for every , so that the shuffle gap bounds the effect of any displacement. This would follow if were monotone in . A bounded displacement could, however, move candidates into the relevant windows more effectively than a fully random one, and exceed . The conjecture is in fact false.
Proposition 5.4 (The shuffle gap does not bound displacement). There are traces and positive existential rules for which is not monotone in and for which . The trace offset below violates the one-sided form . The trace tight shows a decrease larger than .
Proof sketch. Take a trace of well-separated pairs of antecedent and target, each at distance . Its score is . No two of its timestamps lie within , so the shuffled score is also zero and . Displacement with nevertheless covers some pairs with positive probability. Appendix A gives the details. □
Two synthetic traces with 400 targets, and 40 repetitions quantify this. We sweep over 0, 0.5, 1, 2, 5 and . In tight, each window holds one antecedent just inside it. Its score runs 1.000, 0.750, 0.433, 0.229, 0.098 and 0.002, against a shuffled score of 0.248. The curve is monotone and ends at the same-event score, not at the shuffled score. In offset, the antecedent sits just outside each window. Its score runs 0.000, 0.120, 0.248, 0.187, 0.098 and 0.003, against a shuffled score of 0.000. It peaks near and then decays. Here 24.8 points of inflation occur where predicts none.
The mechanism is a resonance. Inflation is largest when the displacement scale is close to the distance between where the evidence sits and where the window expects it. Beyond that scale, disorder destroys structure faster than it creates matches. Both small and large displacement can therefore be safer than moderate displacement. A monotone bound would predict the opposite.
What the shuffle gap is good for. (3) is cheap, and the gate computes it anyway. It is useful for deciding which rules to sweep first. It is not the end point of additive displacement and not a bound on the distortion a transport can cause. It is weakest against a chosen reordering. On tight, a greedy adversary reaches 1.000 against a shuffled score of 0.248. Choosing an ordering guarantee therefore requires the whole curve. One must sweep over the range the transport can produce and take the maximum, including values of close to . Prop. 5.4 places the peak there, and a coarse grid would miss it.
The sweep on real data shows the inflating direction clearly. Over six observers with five repetitions per cell, coverage under displacement by at runs 18.18, 19.78, 21.71, 25.86, 34.60 and 51.45 for R5. For R6 it runs 99.24, 99.40, 99.56, 99.73, 99.68 and 99.76. R2 (100.00) and R1s (92.20) stay constant to two decimals. R5’s ordered coverage of 18.18, against 0.01 for its same-event version, gives the of Table 3, R5, with , therefore inflates to 2.83× its ordered coverage at . It is not heading for the shuffled score. By Prop. 5.3, displacement drives the score to the same-event value, 0.01 for R5. The curve must therefore turn down beyond the range that a wide-area path would produce.
We could not test the protective direction cleanly on this dataset. Every rule with a small is confounded. R2 sits at the ceiling of 100.00, where no reordering can move it. R6 is almost saturated at 99.24. R1s has a zero-width window and ignores order by construction. All three are flat. This is consistent with low exposure but does not establish it, and it does not imply that the original windowed rules would stay flat on a future trace. The one unconfounded case is synthetic and goes the other way. offset has and inflates by 24.8 points.
From Score Distortion to False Alarms
Score inflation is a problem only if it leads to wrong decisions. The WUSTL-IIoT-2021 dataset is labelled per flow. A firing can therefore be classified. If its target is an attack it is a true positive, and if its target is normal traffic it is a false positive. Table 4 reports what reordering does over 200,000 flows, of which 7.2% are attacks.
| Rule | sat. | FDR | 1 | 5 | 30 | 120 | |
| F1 | 1.00 | 0.0 | 0.233 → 0.233 | 1.000 | 1.000 | 1.000 | 1.000 |
| F1′ | 0.98 | −1.3 | 0.218 → 0.218 | 0.985 | 0.985 | 0.992 | 0.996 |
| F2 | 1.00 | 0.0 | 0.195 → 0.195 | 1.000 | 1.000 | 1.000 | 1.000 |
| F2′ | 0.69 | −10.6 | 0.228 → 0.201 | 0.962 | 0.962 | 0.962 | 0.970 |
| F3 | 0.49 | −49.5 | 0.879 → 0.886 | 0.943 | 0.971 | 1.046 | 1.072 |
| F3′ | 0.19 | −78.6 | 0.687 → 0.746 | 0.946 | 0.969 | 1.083 | 1.339 |
Table 4. Reordering on labelled IIoT flows (200,000 flows, s). The rules are F1 loss → RATE, F2 DUR → BYTES and F3 RATE → LOSS. A prime marks the same rule after thinning non-target events to , which removes saturation. sat. is the fraction of targets already firing, and is the shuffle gap of the firing rate. FDR is FP/(TP+FP), a false discovery rate over firings. It is not a false-positive rate over negatives; see Axelsson [41]. Italic cells are below 1: false positives first fall and then rise. Non-integer counts are means over repetitions.
At the largest displacement, inflation happens to grow with across these three rules: 1.00× at 1.3, 1.07× at 49.5 and 1.34× at 78.6. This is an association on three points and not a bound. Prop. 5.4 shows that no such bound exists. Even this association depends on reading only the end points. Every unsaturated cell is non-monotone in . False positives first fall, by 5.4% for F3′ and by 3.8% for F2′. The peak between the end points is therefore not a synthetic curiosity. Labelled industrial traffic shows it too, and this is why Algorithm 1 decides from over a grid. The two saturated rules stay flat, as expected when there is no room for additional firings.
The inflation consists entirely of false alarms. For F3′ the number of true positives changes by less than 0.03%, while false positives grow by 8,522. The FDR worsens from 0.687 to 0.746. Disorder finds no additional attacks. It produces additional alarms. Merging the source hosts onto one time axis reproduces the effect at 1.13×. WUSTL’s hosts share a clock. We therefore created the JAMES condition by resetting each host’s clock to zero.
One case goes the other way. Table 4 lists all six cells. The reader can therefore check that we did not select the direction. F2′, with , gains 286 true positives under reordering while its false positives fall by 18. Its FDR improves from 0.228 to 0.201.
What decides the direction is the mix of labels in the windows that a rule’s candidates fall into, and nothing in our analysis predicts that mix. therefore determines neither the direction of the change nor its size at intermediate displacement. We claim only what it is, a cheap test of exchangeability on a fixed grid, and not a predictor of harm.
Measured Broker Behaviour
All results so far inject and directly into the traces. To check them against a real transport, we ran the brokers of the fabric. MQTT with QoS 1 carries ingest, and NATS JetStream with durable streams carries traffic from the gateway to the back end. The brokers ran in containers on one host. Each measurement used 2000 messages per hop, three runs, a 4 ms pace and one publisher on one connection. Versions and host configuration are in the artifact.
Loss is severe, silent and not independent. We published a burst before the consumer attached. This models a monitor that lags or recovers and replays the durable stream. Any message evicted from the stream is then evidence the monitor never sees. A consumer that keeps pace would see the events first. When 2000 events are published into a stream bounded at 500 messages, 25% are kept. With a bound of 1000, 50% are kept. Under the discard-old policy not a single publish returns an error. Continuity is lost without any signal. Under discard-new the same volume is rejected and every drop is reported. The overload ratio sets how much is lost, and the configuration sets whether the loss is visible.
Eviction is not independent loss. The broker kept a contiguous suffix, the messages with identifiers 1500 to 1999. We applied this exact pattern to the real trace and measured the result. Here only non-target events are dropped, so the target always arrives; in the random-loss measurements above it could be lost too. At the same retained fraction of 0.25, relative detection under independent retention is 0.98 to 0.99 for R1 and R5 on two observers (means over 20 draws, each draw between 0.965 and 0.995). A window with many candidates survives random thinning. Under the broker’s own pattern, relative detection is 0.23 to 0.51. That is a gap of up to 0.76 in the unsafe direction. The shape of the loss costs more than its rate. Here (5) serves as a benchmark for independent loss, not as a prediction. The delivery guarantee is the one that counts here.
No reordering was observed. Latency was 0.85 ms at the median and 2.34 ms at the 99th percentile on JetStream, and 0.88 and 1.97 ms over MQTT. The widest range over three runs of 2000 events per hop was 27.9 ms. An unordered transport with this spread could swap adjacent publications sent 4 ms apart. The tested single-connection path nevertheless kept the order exactly. On both hops we counted zero inversions and zero displacement in rank. A spread of delays is therefore not the same as displacement. We take the observed range as a conservative ms. This is 143 times smaller than the window s. Over the grid , is at most 0.018 points for all four rules, more than 55 times below . Algorithm 1 therefore requests no ordering guarantee for any tested rule in this configuration. This is an empirical estimate and not a property of the transport. Several publishers, partitioned subjects or a wide-area path could raise it. The offset construction of Prop. 5.4 peaks near , more than 140 times beyond the observed range. In this deployment, loss is the binding effect and ordering is not, and neither conclusion follows from .
Comparing the Perturbations
Naive merging, timestamp displacement and the shuffle are different perturbations. Each one weakens the link between an event’s position in time and its attributes, and each can therefore remove or invent matches. Four of our measurements show the same phenomenon: the 79.9-point merging inflation, the 2.83× inflation under reordering, the shuffle gap of −83.9 points, and the 8,522 invented alarms. The main failure mode of mining followed by monitoring is a distortion of temporal correlation caused by collection and transport. In the security cases we measured, that distortion mostly invents matches.
Implications for deployment. A fabric offers a menu of guarantees at different costs [2]. The analysis says which of them a mined rule needs. Under the assumptions of Thm. 5.2, the delivery guarantee can be priced exactly from the witness structure. Without those assumptions, Algorithm 1 requests it as a precaution, and is then not certified. The ordering decision comes from over the admitted range, measured in Sect. 5.4. Against an adversary who chooses the displacement, neither quantity is sufficient.
Threats to Validity
Loss and displacement models. Thm. 5.2 assumes independent loss. § 5.4 shows the cost of that assumption. Real eviction is contiguous and removes up to 0.76 more relative detection than the independent law predicts at the same rate. We also model displacement as independent symmetric jitter followed by re-sorting. Real transports produce one-sided, correlated delay and keep the order within each partition.
Saturation. Saturated rules have little room for additional firings, and for them. They are not immune, because reordering can remove existing matches. Two of our three IIoT rules are saturated at full density. We had to thin the traces to see any effect at all.
The shuffle control. A joint-row shuffle keeps the structure inside each event. A rule could therefore depend on order in a way the shuffle does not reveal. The compilation criterion does not use the shuffle at all. An earlier version of the control left the him and flow attributes in place, so the antecedent of R6 was not perturbed. Over the full tuple, moves only from −0.35 to −0.31 and its interval still contains zero. The classification of R6 survives the change of control, and saturation remains the only confound.
Thresholds. and are free parameters. The within-observer standard deviation of the shuffle is at most 0.101 points. The widest interval of across observers spans about 15 points. Setting is therefore conservative against shuffle noise by an order of magnitude. It is not conservative against the spread between observers. With more heterogeneous observers the thresholds should be set from that spread.
Scope of recovery. Thm. 3.1 covers rules evaluated within one observer, whose counts add up across traces separated in time. Rules with antecedent and target at different observers are outside the scope of the protocol. It exchanges descriptions and counts and never events. It cannot assemble such a witness. Supporting these rules would need clocks that agree within a bounded skew and an exchange of timestamped events. We do not attempt this.
Causality. Mined rules report temporal precedence and association. They do not report the effect of an intervention, and nothing here supports a causal reading [1].
Evidence limitations. Section 5.4 measures brokers that run on one host with one publisher, where order is kept exactly. Several publishers, partitioned subjects or a wide-area path would all allow displacement, and we emulate none of them. We therefore treat as a baseline for this configuration and not as a bound for others. We do not measure the savings in state, latency or bandwidth that compilation is meant to deliver. The loss law is validated on two of the 21 observers, and the occupancy axis on a single pair of antecedent and target. The planted sweeps carry the coverage of the parameters. Finally, our dataset comes from an active-probing campaign whose vocabulary almost never appears in backbone traffic. Its rules are instruments for studying the mechanism, not rules an operator would deploy. What transfers is the structure of existential windows with bounded duration over per-event conditions.
Related Work
This work connects two literatures that rarely cite each other, specification mining and distributed runtime verification. It also draws on negative controls in statistics, monitoring under imperfect observation, and the cost of false alarms.
Specification mining
Inferring properties from traces is a mature line of work. Daikon infers likely data invariants at program points [8]. Perracotta mines two-event temporal patterns from imperfect traces [9]. Javert composes small patterns into larger ones [10]. Synoptic infers models constrained by invariants from logs [11], and Texada mines arbitrary LTL templates [12]. For timed behaviour, PSIMINER learns rules with bounded intervals [6]. We adopt its template in (1). This work mines centrally and offline and judges rules as predictions about a dataset. Section 3 treats mining over independent observers with a communication budget.
Ranking metrics and negative controls
Coverage, confidence, support and lift come from association-rule learning [13]. Its tendency to confuse co-occurrence with implication was criticised early [14]. That critique is the origin of our shuffle test. Destroying one structure while keeping others is also standard in time-series analysis, where it is called surrogate-data testing [15]. Temporal precedence together with association is Granger’s notion [16]. It is weaker than intervention [17]. Mined rules therefore support no causal reading. Sinha et al. [1] introduced the joint-row and independent-column controls and used them as diagnostics. We keep that diagnostic role for the shuffle gap. Prop. 5.3 shows that it is a control on a fixed grid and not a physical end point. Compilation gets its own criterion (Thm. 4.1).
Distributed and decentralised runtime verification
Monitoring a property whose witnesses are spread across nodes is well studied [18, 19, 20, 21]. For first-order properties, MFOTL monitoring has been scaled offline [23] and extended with aggregation [24]. BDD-encoded valuations make past-time first-order monitoring efficient over unbounded domains [25]. These works take a property as given and ask how to monitor it across nodes. We ask which properties should exist, whether each needs state, and which guarantees each needs. Hierarchical monitoring architectures for edge-IoT [3, 4] organise where such checks run. The closest work is failure-aware distributed monitoring [22]. Our concern complements it. A transport that only disorders evidence changes verdicts even when nothing fails.
Monitorability and imperfect observation
Whether violations can be detected from finite prefixes is the classical monitorability question [26, 27, 28, 29]. Another line accepts imperfect observation. It infers missing states probabilistically [30, 31, 32], schedules monitoring under a budget [33], or handles recording uncertainty and lossy traces [34, 35]. Thm. 5.2 belongs to this line with a different question. Those works ask how to recover a verdict despite missing observations. We ask how a rule’s own witness structure, its split into irreplaceable and interchangeable events, determines its sensitivity to loss. The answer depends on how full the rule’s windows are and not on the size of its host.
These works mostly study missing events. Disorder has been treated as a correctness problem for monitoring algorithms. Runtime verification over out-of-order streams reconstructs the verdict that a correctly ordered trace would give [36]. Our question is different, and as far as we know it has not been asked before. We ask how much a disordering transport changes the observed score of a mined rule, and whether this can be predicted before deployment. Our claim is the link to the shuffle statistic and its limits. That disorder affects monitoring is already known.
Aggregation artefacts and measurement methodology
Pooling heterogeneous observations can invent an association. This is an old warning in statistics [37]. Here it takes a temporal form, because observers restart their clocks, and distributed measurement depends on clock synchronisation [38, 39]. Section 3 measures the cost at 79.9 points and shows that offsetting the clocks removes it exactly. Datasets of this kind are routinely concatenated. The effect is therefore likely to occur in practice. The practical consequence is false alarms. Their cost in intrusion detection is governed by the base-rate fallacy, and it has long limited the deployment of learned detectors [41, 42]. § 5.3 measures our effect in those terms.
Conclusion
Connecting specification mining to distributed monitoring changes the expected failure mode. Coverage-based mining of rules evaluated within one observer distributes exactly, provided the traces are separated in time and the rule descriptions arrive. Central mining over merged traces is the step that needs justification. On a dataset whose observers share a clock origin, merging inflated one rule from 11.6% to 91.6%, and separating the clocks removed the inflation to within 0.000 points. Rule validation becomes a compiler pass with two statistics. Keeping them apart allows a rule whose window is worth 78 points, but whose shuffle gap cannot be distinguished from zero, to be compiled correctly. Under independent loss, detection depends on redundancy inside windows and not on rule length. Contiguous loss, as real brokers produce it, did far more damage than independent loss at the same rate. Reordering has no cheap summary. The same-event version fixes where large displacement ends, and the shuffle gap bounds neither moderate nor adversarial displacement. In practice we recommend mining where the data is observed, gating each rule before deployment, and choosing the ordering guarantee from the range of displacement that the deployment actually admits. On the fabric we measured, loss was the limiting factor and ordering was not.
Artifact Availability
The drivers, the chain evaluator, the synthetic generators, the broker harness and every reported result will be made publicly available. The datasets [7] and the mining engine [6] are third-party and public. Only Sect. 5.4 needs running brokers.
Acknowledgments
This work has received funding from the European Union’s Digital Europe Programme (CYBERGUARD, No. 101190251) and from its Horizon Europe research and innovation programme through the Smart Networks and Services Joint Undertaking (XTRUST-6G, No. 101192749).
Generative AI tools were used to help draft, edit and condense parts of the text. The authors designed the study, proved the results, ran the experiments, and checked, revised and approved all content. They take full responsibility for it.
References
Technical Proofs
This appendix proves the two propositions of Sect. 5. No measured value in the paper depends on it.
Proof of Prop. 5.3. At the trace is unchanged. Take two distinct events . The difference of their displaced timestamps has a density bounded by , where depends only on the density bound of . Hence , which tends to 0. There are finitely many pairs. By a union bound, with probability tending to one no two distinct events remain within of each other. Every remaining witness then has all of its buckets satisfied by one event, and these are exactly the witnesses of .
Two remarks complete the proof. First, is a conjunction of per-event conditions. Its score does not change under displacement. The limit is therefore a statement about the original trace. Second, under continuous , two distinct events receive equal displaced timestamps with probability zero. The limit thus equals , up to timestamp ties already present in the original trace. The last claim of the proposition is the definition (4). □
Proof of Prop. 5.4. Fix . Build a trace of disjoint pairs. Pair has an antecedent event at time and a target event at . The pairs are separated so that . Each event is displaced independently by .
First, . The only antecedent within before is , at distance . No target is covered.
Second, exactly. The shuffle changes which of the timestamps carry the antecedent attribute and leaves the timestamps in place. Every gap between two timestamps is either or larger than , so no two timestamps lie within . No assignment of attributes covers any target. Hence for every , and .
Third, for suitable finite . Pair is covered when . The difference of two independent variables has a triangular distribution on . This event therefore has positive probability whenever .
We obtain , so is not monotone in . We also obtain , so the shuffle gap does not bound the effect of displacement. □
References
- [1]P. Sinha, N. Kekatos, S. Basagiannis, A. A. Bruto da Costa, A. Lekidis, P. Mitra, T. Nianios, and E. Papageorgiou. Explainable rule mining of IPv6 extension-header presence patterns from paired-vantage captures. In IEEE Int. Conf. on Cyber Security and Resilience (CSR), GenXSec Workshop, 2026. arXiv:2610.08090.
- [2]N. Kekatos, M. Chintrì, P. Katsaros, A. Lekidis, T. Nianios, I. Seitoglou, A. Temperkidis, and S. Basagiannis. A resilient runtime-verification fabric for security monitoring of critical edge-IoT infrastructure. In Critical Information Infrastructures Security (CRITIS 2026), LNCS, Springer, 2026. arXiv:2610.07282.arxiv.org/abs/2610.07282
- [3]N. Kekatos, M. Chintrì, P. Katsaros, A. Lekidis, T. Nianios, I. Seitoglou, and S. Basagiannis. Hybrid hierarchical runtime verification for Edge-IoT security: combining MonPoly and RTLoLa. In Availability, Reliability and Security. ARES 2026 EU Projects Symposium Workshops, LNCS, pp. 222–240, Springer, 2026. doi:10.1007/978-3-032-37218-5_14. arXiv:2610.09825.DOI
- [4]N. Kekatos, M. Chintrì, P. Katsaros, A. Lekidis, T. Nianios, I. Seitoglou, and S. Basagiannis. Hierarchical security monitoring for Edge-IoT: a formal methods approach. In IEEE Int. Conf. on Cyber Security and Resilience (CSR), 2026. arXiv:2610.09817.
- [5]D. W. Cheung, J. Han, V. T. Ng, A. W. Fu, and Y. Fu. A fast distributed algorithm for mining association rules. In Int. Conf. on Parallel and Distributed Information Systems (PDIS), pages 31–42, 1996.
- [6]A. A. Bruto da Costa and P. Dasgupta. Learning temporal causal sequence relationships from real-time time-series. Journal of Artificial Intelligence Research, 70:205–243, 2021.
- [7]R. Léas, J. Jurman, É. Vyncke, and B. Donnet. Measuring IPv6 extension headers survivability with JAMES. In Proc. ACM Internet Measurement Conference (IMC), pages 746–747, 2022.DOI
- [8]M. D. Ernst, J. H. Perkins, P. J. Guo, S. McCamant, C. Pacheco, M. S. Tschantz, and C. Xiao. The Daikon system for dynamic detection of likely invariants. Science of Computer Programming, 69(1–3):45–55, 2007.DOI
- [9]J. Yang, D. Evans, D. Bhardwaj, T. Bhat, and M. Das. Perracotta: mining temporal API rules from imperfect traces. In ICSE, pages 282–291, 2006.
- [10]M. Gabel and Z. Su. Javert: fully automatic mining of general temporal properties from dynamic traces. In FSE, 2008.DOI
- [11]I. Beschastnikh, Y. Brun, S. Schneider, M. Sloan, and M. D. Ernst. Leveraging existing instrumentation to automatically infer invariant-constrained models. In ESEC/FSE, pages 267–277, 2011.
- [12]C. Lemieux, D. Park, and I. Beschastnikh. General LTL specification mining. In ASE, pages 81–92, 2015.DOI
- [13]R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In VLDB, pages 487–499, 1994.
- [14]S. Brin, R. Motwani, and C. Silverstein. Beyond market baskets: generalizing association rules to correlations. In SIGMOD, pages 265–276, 1997.
- [15]J. Theiler, S. Eubank, A. Longtin, B. Galdrikian, and J. D. Farmer. Testing for nonlinearity in time series: the method of surrogate data. Physica D, 58(1–4):77–94, 1992.
- [16]C. W. J. Granger. Investigating causal relations by econometric models and cross-spectral methods. Econometrica, 37(3):424–438, 1969.
- [17]J. Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2nd edition, 2009.
- [18]K. Sen, A. Vardhan, G. Agha, and G. Roşu. Efficient decentralized monitoring of safety in distributed systems. In ICSE, pages 418–427, 2004.
- [19]A. Bauer and Y. Falcone. Decentralised LTL monitoring. In FM, pages 85–100, 2012.
- [20]C. Colombo and Y. Falcone. Organising LTL monitors over distributed systems with a global clock. In RV, pages 140–155, 2014.
- [21]A. El-Hokayem and Y. Falcone. THEMIS: a tool for decentralized monitoring algorithms. In ISSTA, pages 372–375, 2017.
- [22]D. Basin, F. Klaedtke, and E. Zălinescu. Failure-aware runtime verification of distributed systems. In FSTTCS, pages 590–603, 2015.
- [23]D. Basin, G. Caronni, S. Ereth, M. Harvan, F. Klaedtke, and H. Mantel. Scalable offline monitoring. In RV, pages 31–47, 2014.
- [24]D. Basin, F. Klaedtke, S. Marinovic, and E. Zălinescu. Monitoring of temporal first-order properties with aggregations. Formal Methods Syst. Des., 46(3):262–285, 2015.
- [25]K. Havelund, D. Peled, and D. Ulus. First-order temporal logic monitoring with BDDs. In FMCAD, pages 116–123, 2017.
- [26]A. Pnueli and A. Zaks. PSL model checking and run-time verification via testers. In FM, pages 573–586, 2006.DOI
- [27]A. Bauer, M. Leucker, and C. Schallhart. Runtime verification for LTL and TLTL. ACM TOSEM, 20(4), 2011.DOI
- [28]Y. Falcone, J.-C. Fernandez, and L. Mounier. What can you verify and enforce at runtime? STTT, 14(3), 2012.DOI
- [29]L. Aceto, A. Achilleos, A. Francalanza, A. Ingólfsdóttir, and K. Lehtinen. Adventures in monitorability: from branching to linear time and back again. PACMPL, 3(POPL), 2019.DOI
- [30]S. D. Stoller, E. Bartocci, J. Seyster, R. Grosu, K. Havelund, S. A. Smolka, and E. Zadok. Runtime verification with state estimation. In RV, pages 193–207, 2011.DOI
- [31]E. Bartocci, R. Grosu, A. Karmarkar, S. A. Smolka, S. D. Stoller, E. Zadok, and J. Seyster. Adaptive runtime verification. In RV, pages 168–182, 2012.DOI
- [32]K. Kalajdziec, E. Bartocci, S. A. Smolka, S. D. Stoller, and R. Grosu. Runtime verification with particle filtering. In RV, pages 149–166, 2013.
- [33]B. Bonakdarpour, S. Navabpour, and S. F. Smetsers. Sampling-based runtime verification. In FM, pages 88–102, 2011.DOI
- [34]S. Wang, A. Ayoub, O. Soklsky, and I. Lee. Runtime verification of traces under recording uncertainty. In RV, pages 442–456, 2011.DOI
- [35]Y. Joshi, G. M. Tchamgoue, and S. Fischmeister. Runtime verification of LTL on lossy traces. In SAC, pages 1379–1386, 2017.DOI
- [36]D. Basin, F. Klaedtke, and E. Zălinescu. Runtime verification over out-of-order streams. ACM TOCL, 21(1), 2020.DOI
- [37]E. H. Simpson. The interpretation of interaction in contingency tables. JRSS B, 13(2), 1951.DOI
- [38]D. Mills, J. Martin (Ed.), J. Burbank, and W. Kasch. Network Time Protocol v4. RFC 5905, IETF, 2010.
- [39]IEEE. IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems. IEEE Std 1588-2019, 2020.