Policy Change for Treelike Monitors

arXiv:2609.10114 · cs.LO · Submitted 2026-09-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Policy Change for Treelike Monitors".

Jane: Here's the gist of the paper. We study the policy change problem that arises in the runtime verification of long-running systems The online monitors typically used in this context are generally treelike, in that they maintain substates that monitor subformulae of the target policy.

Tom: We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

Jane: Problem Definition and Scope The problem formally defines the policy change problem in a general setting, independent of any specific (treelike) monitor implementation.

Tom: The core question addressed is: "under which condition is policy change possible?" when exploiting only the information stored in the monitor’s state.

Title and authors: Tom: So we're looking at this paper called Policy Change for Treelike Monitors. Jane, what's the main thing you want to get across about what this research is actually doing?

Jane: It deals with a problem in runtime verification of long-running systems where you have online monitors that are usually treelike—meaning they keep track of sub-parts of the system's rules. The core question they tackle is, under what conditions can you actually change the policy being monitored while the system is running, just by looking at what the monitor has stored about past events.

Lu: It's interesting because they formally define this policy change problem in a general way, without locking it down to one specific type of monitor implementation first. They then show that for past-time metric temporal logic, which we call pMTL, this policy change is decidable but the bounds are quite tight—meaning they're not super easy to solve.

Meng: Decidable but tight bounds sound good on paper, but what does that mean for us when we try to actually deploy something? Does it mean we have a practical way to figure out if changing a requirement will break our system in real time?

Jane: That's the big question, Meng. The paper explains that they show policy change for pMTL is decidable, but with real-time semantics, it has these tight non-primitive recursive lower and upper bounds. This means we have a formal limit on how hard it is to check if a policy change is possible using only the monitor's state information.

Tom: Non-primitive recursive bounds are serious. I'm hearing something about discrete time semantics being EXPSPACE-complete, which tells us that for discrete systems, this problem gets significantly harder computationally compared to real-time ones.

Lu: Exactly. They show that with discrete time semantics, policy change for pMTL is EXPSPACE-complete. This is a lot of computational power required to solve it on a computer when you have those specific types of monitors.

Meng: EXPSPACE completeness suggests that if we move to discrete time, the verification process becomes very computationally expensive, even if the logic itself is sound and decidable in principle. What does that imply for our deployment pipeline?

Jane: It implies that for systems where you only have discrete time steps, adapting policies dynamically requires a lot of computational overhead during the check. They also mention that if you drop the assumption that monitors must be treelike, things change, which is an interesting point for generalization.

Title and authors: Tom: I'm curious about the methodology they use to prove those complexity bounds. Is it just a simple reduction, or are they doing something more intricate to show that it's truly non-primitive recursive?

Lu: They do it by reducing policy change to validity checking in a hyperlogic, specifically by computing information formulae called the lower bound and upper bound of the policy change. The decision procedure works if the lower bound entails the upper bound, which is what they call "phi1 entails upi2" or "phi1 to upi2 is valid".

Meng: So, instead of replaying everything, we are checking a logical formula to see if one state information set implies another. That sounds like a clever way to avoid replaying the entire history of every single event.

Jane: That's right. The decision procedure reduces Policy Change to validity checking in a hyperlogic by computing those information formulae, and this final step reduces satisfiability in the existential universal fragment of one-HyperpTPTL to pMTL satisfiability over finite words sixteen two <ref:2609.10114#pg1>.

Tom: That's a big leap from just saying it's decidable. They are showing that the decision procedure itself has non-primitive recursive complexity because of that reduction from pMTL satisfiability on finite traces.

Lu: That reduction is key because it shows how hard the underlying problem is by linking it to something we already know, like pMTL satisfiability on finite traces. This proves that the lower bounds they established are tight for real-time systems sixteen two <ref:2609.10114#pg1>.

Meng: If we take their findings about past-time metric temporal logic and apply it to our actual production monitoring systems, what's the immediate practical implication for us right now?

Jane: The immediate implication is that if you're working with metric temporal logic—things involving time measurements like deadlines or delays—you need to be very careful about how you structure your monitor state. You can only safely change policies if the state contains enough information to reconstruct what happened up to that point, and they show exactly how much information is needed.

Tom: So the main thing for us is understanding the necessary information content of those monitor states so we don't try to make a policy change that's just impossible because we forgot some past event.

Title and authors: Lu: And their work extends this idea by looking at non-treelike monitors too, where they show that even without the treelike assumption, discrete-time policy change for pMTL is in 2EXPSPACE, which is still a high complexity class <ref:2609.10114#pg1>.

Meng: So even when we remove the structural restriction on the monitor, if we use discrete time steps—like in many control systems—we still face a very high computational cost to verify policy changes.

Jane: That's what they found. They show that for non-treelike monitors, discrete-time policy change for pMTL is in 2EXPSPACE sixteen two <ref:2609.10114#pg1>. This gives us a more general result than just the treelike case we first discussed.

Tom: So to wrap up this paper, the main point is that while policy change for real-time metric temporal logic is decidable with tight non-primitive recursive bounds, and discrete time is EXPSPACE-complete, it really forces us to be precise about what information the monitor state holds.

Lu: They've established a strong foundation here by proving these complexity results for pMTL over both real-time and discrete time semantics sixteen two <ref:2609.10114#pg1>.

Meng: For my deployment team, the thing that sticks is that if we need to adapt requirements dynamically, we need to design our monitor state carefully so it satisfies those lower bounds they calculated.

Jane: And the paper’s overall contribution is showing exactly how hard this problem is by reducing it to things like pMTL satisfiability on finite traces sixteen two <ref:2609.10114#pg1>. It gives us a formal map of the complexity we are dealing with when trying to evolve our system specifications.

Tom: So we have a formal tool now to understand the limits of dynamic adaptation in systems monitored by treelike structures, and they also showed how that scales up to discrete time and non-treelike monitors.

Lu: It sets a clear baseline for what's achievable with current verification methods when dealing with policy changes in long-running systems.

Meng: For us at the startup, this means we know upfront if we need to invest heavily in exploring more complex verification techniques before we start designing those dynamic update features.

Jane: It’s a lot of formal logic and complexity, but it gives us concrete numbers about the computational cost involved in making our systems self-adaptive. That’s what this paper delivers on.

The paper's summary: Tom: So, to recap, this paper is about figuring out if we can safely change the rules of what an online monitor is watching while it's already running, specifically for systems that use metric temporal logic.

Jane: Right, so they look at these monitors which are usually treelike structures—think of them like a tree where every branch monitors a part of the system’s requirements. The big question is whether we can switch from monitoring one set of rules to another set of rules without having to restart everything or re-read all the history.

Lu: They formalize this policy change by saying it only works if the monitor’s current state has enough information to bridge the gap between the old rule, phi one, and the new rule, phi two. This is formalized using something called deep bisimilarity.

Tom: Deep bisimilarity sounds complicated. What does that actually mean for us in practice? Is it just checking if two states look similar?

Jane: It’s more than just looking similar; it’s a formal requirement that the substates corresponding to the different temporal rules—the subformulas—must be equivalent in some deep way. If they are bisimilar, then changing the rule is possible using only what the monitor has stored.

Lu: The complexity results are pretty specific: for real-time systems, past-time metric temporal logic pMTL, they show it's decidable but has bounds that grow faster than anything primitive recursive.

Tom: Faster than primitive recursive means it’s not something you can solve with a simple algorithm in constant time or even polynomial time. What does that say about our verification tools?

Jane: It means the tool we use to decide if policy change is possible has to be pretty sophisticated, relying on checking if one logical formula implies another—that the lower bound entails the upper bound. That check itself is hard.

Lu: And then they show that for discrete-time systems, this problem jumps up to EXPSPACE completeness for pMTL. That’s a huge jump in computational difficulty, meaning the verification process gets exponentially harder as time steps become discrete.

Tom: So we've got real-time metric temporal logic being hard but decidable, and discrete time being completely intractable in terms of space complexity unless you have very small systems.

Jane: Exactly. And they also looked at a generalization where the monitor structure isn't necessarily treelike—that’s called policy change star—and even there, for discrete time pMTL, they found it is decidable within two EXPSPACE.

Lu: The big picture here is that as long as you have metric temporal logic and you are dealing with systems that run over a lot of time, dynamic policy changes aren't trivial; the cost scales up significantly depending on whether time is continuous or discrete.

Tom: It sounds like we can’t just slap a simple check on top of our existing monitoring system to handle requirements changes easily without paying a serious computational price.

Jane: That’s the point. The paper gives us the formal complexity numbers so we know exactly how hard it is to make those systems self-adaptive in the real world.

The paper's improvements: Tom: So, they’re not just stopping there; they're suggesting ways to make these results more practical by looking at different types of monitors and logic systems.

Jane: Right, so the paper points out that their initial work was focused on treelike monitors, but they generalize the whole setup to non-treelike structures too. That means it applies even when the monitor’s internal structure isn't strictly a tree.

Lu: They introduce a concept called policy change star, which handles this more general case by defining new versions of the policy change problem and proving that the lower bounds they found in the treelike case still hold for these unrestricted monitors.

Tom: So if you have a more complex monitoring setup that doesn't fit the tree structure, you can still use those same hard complexity bounds to understand what’s possible.

Jane: That’s right. The point is that the hardness of changing policies isn't just a quirk of having a tree structure; it seems to be tied to the underlying logic and time semantics themselves.

Lu: They also look at how these results connect back to other verification problems, showing how this work relates to things like past-time linear temporal logic pLTL.

Tom: What does that linkage mean for us who are just trying to implement a monitor? Does it give us hints about what kind of structure we need in our monitoring code?

Jane: It suggests that understanding the complexity of policy change gives you a roadmap for designing monitors that can handle dynamic requirements effectively, showing you where the computational wall is.

Lu: The authors are also looking ahead to future work, specifically trying to find out the complexity of the more general problem even under real-time semantics.

Tom: They want to see if those tight bounds they proved for treelike monitors hold true when we remove that structural restriction for real-time systems.

Jane: They’re aiming to see if their preliminary results on non-treelike monitors are actually the same as what they found for the restricted case, which would be a big piece of information.

Lu: If they can nail down that complexity for the unrestricted version in real time, it would clarify whether we need to worry about those higher complexity classes when designing systems that adapt their own rules.

Tom: So basically, they are trying to bridge the gap between their specific treelike findings and a more general understanding of dynamic system monitoring.

Jane: It gives us a clearer path forward for researchers who want to move beyond just looking at one specific structure and understand the whole problem space.

Conclusion: Tom: So we’ve covered the core of "Policy Change for Treelike Monitors," showing how policy changes in metric temporal logic are either decidable with tight bounds in real time or EXPSPACE complete in discrete time.

Jane: Exactly, it’s about establishing the hard computational limits when you try to adapt the rules of a system while it's running, whether that system is continuous or step-by-step.

Lu: The paper gives us a very clear picture of what kind of information you need in your monitor state to allow for such a change without replaying everything.

Tom: It puts a ceiling on how much history we can rely on for adaptation, which is useful when designing these long-running systems.

Jane: And they also showed that even if the monitor structure isn't strictly treelike, the complexity doesn't suddenly drop to something easy when dealing with discrete time steps.

Meng: For us shipping models, this means we know upfront that if we want dynamic policy changes in a discrete environment, we need to budget for an EXPSPACE level of computational effort during verification.

Lalam: I’m quite sure about this; the results for pMTL over discrete time being EXPSPACE complete is a very solid finding based on the reduction they used.

Tom: It does show us that designing self-adaptive systems isn't just about writing the logic, it’s deeply tied to the underlying structure of time and monitoring.

Jane: So for anyone working on runtime verification, this paper is a great reference point for understanding where you need to invest your effort when considering dynamic updates.

Lu: It really pushes us to think about how we represent the state information in our models because that’s what dictates the complexity of the entire problem.

Meng: If we want to deploy features that change requirements on a running system, this paper tells us exactly how much verification time we should expect to spend on those checks.

Lalam: I’m confident this work provides a very rigorous foundation for understanding these constraints in monitoring systems.

Institute of Information Security, Department of Computer Science, ETH Zurich

cs.LO

Submitted: 2026-09-09

Updated: 2026-11-10

Comments: 39 pages, 5 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: We study the policy change problem that arises in the runtime verification of long-running systems The online monitors typically used in this context are generally treelike…

Key concepts

Online Monitors
These are typically tree-like structures used to monitor system policies. They maintain substates that track specific parts (subformulas) of the target policy being checked over time. This structure is key because it limits how much information the monitor can store about past events.
Policy Change
This occurs when a monitor transforms its state after observing a trace, switching from checking one policy ($\phi_1$) to another ($\phi_2$). This change is only possible if the information stored in the monitor's current state is sufficient to guarantee that all future verdicts will match what they would have been if it had always been checking $\phi_2$.
Deep Bisimilarity
This formal concept defines when two states in a treelike monitor are considered equivalent. For policy change, deep bisimilarity is required between substates corresponding to temporal subformulas. This ensures that the state transition correctly reflects the semantic equivalence of checking one policy versus another.
pMTL and Discrete-Time Semantics
pMTL (past-time metric temporal logic) deals with properties involving time metrics, such as deadlines or durations. When combined with discrete-time semantics, the complexity of determining if a policy change is possible becomes EXPSPACE-complete, indicating high computational difficulty.

Terminology

Summary

We study the policy change problem that arises in the runtime verification of long-running systems The online monitors typically used in this context are generally treelike, in that they maintain substates that monitor subformulae of the target policy. p. 0

Where the paper says it

Policy Change for Treelike Monitors François Hublet # Ñ Institute of Information Security, Department of Computer Science, ETH Zurich, Switzerland Dhruv Nevatia # Ñ Institute of Information Security, Department of Computer Science, ETH Zurich, Switzerland Joshua Schneider Institute of Information Security, Department of Computer Science, ETH Zurich, Switzerland Abstract We study the policy change problem that arises in the runtime verification of long-running systems. The online monitors typically used in this context are generally treelike, in that they maintain substates that monitor subformulae of the target policy.

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. p. 0
Where the paper says it

We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

Problem Definition and Scope

The problem formally defines the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. The core question addressed is: under which condition is policy change possible? when exploiting only the information stored in the monitor’s state.

Formal Definitions of Monitors

Online monitors are typically treelike, maintaining substates that monitor subformulae of the target policy. A generic treelike monitor is defined as a triple of mappings ⟨M, T, f⟩ where M is a generic monitor and for all φ, the triple ⟨Mφ, T φ, f φ⟩ is a treelike monitor. p. 4

Where the paper says it

The corresponding treelike monitor is the triple ⟨Mφ, T φ, f φ⟩. A generic treelike monitor is a triple of mappings ⟨M, T, f⟩ such that M is a generic monitor and for all φ, the triple ⟨Mφ, T φ, f φ⟩ is a treelike monitor.

The definition of deep bisimilarity between states in treelike monitors requires that substates corresponding to temporal subformulae be bisimilar. p. 6
Where the paper says it

Schneider XX:7 ∼=f φ essentially enforces that the substates corresponding to φ’s temporal subformulae be bisimilar. We now redefine policy change in terms of deep bisimilarity.

Policy Change Mechanism

Policy change is defined as transforming the state of the monitor after monitoring a policy φ1 on an arbitrary trace to a state for a different policy φ2 such that all future verdicts are the same as if the monitor had been checking φ2 since the beginning of the trace. This is formalized using deep bisimilarity, requiring that a function C implements policy change from φ1 to φ2 iff q ∼=f φ1 µφ1(qφ10, s) =⇒ C(q) ∼=f φ2 µφ2(qφ20, s).

Complexity Results and Reductions

The paper establishes several complexity results:

  1. Policy change for real-time pMTL is NPR-hard via a reduction from pMTL satisfiability on finite traces. p. 1

    Where the paper says it

    We solve the decision problem associated with policy change for real-time pMTL with non-primitive recursive complexity by reducing policy change to 1-TPTL satisfiability over finite words [13]. We prove that such policy change is NPR-hard via a reduction from pMTL satisfiability on finite traces (Section 4).

  2. Policy change for discrete-time pMTL is EXPSPACE-complete. p. 0

    Where the paper says it

    We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

  3. If the assumption that monitors are treelike is removed, discrete-time policy change for pMTL is still decidable and in 2EXPSPACE, while policy change for pLTL is in EXPSPACE. p. 1

    Where the paper says it

    We prove that policy change for discrete-time pMTL is EXPSPACE-complete and policy change for pLTL is PSPACE-complete (Section 5). We show that if we remove the assumption that monitors are treelike, discrete-time policy change for pMTL is still decidable and in 2EXPSPACE, while policy change for pLTL is in EXPSPACE (Section 6).

Decision Procedure

The decision procedure reduces PolicyChange to validity checking in a hyperlogic by computing information formulae ↓φ1 and ↑φ2, such that policy change is possible iff ↓φ1 entails ↑φ2, i.e., iff ↓φ1 → ↑φ2 is valid. p. 6

Where the paper says it

Then, policy change is possible iff ↓φ1 entails ↑φ2, i. , iff ↓φ1 → ↑φ2 is valid.

This involves constructing HyperpTPTL (HyperpTPTL) based on TPTL to encode the information formulae for pMTL. p. 8
Where the paper says it

We find this fragment to be expressive enough to encode information formulae for pMTL. 1 pTPTL and (1-)HyperpTPTL.

The final decision procedure reduces satisfiability in the ∃∗∀∗ fragment of 1-HyperpTPTL to 1-pTPTL satisfiability. p. 8
Where the paper says it

Our augmented logic, which we call Hyper past-Time Propositional Temporal Logic or HyperpTPTL, is intractable. However, we carve out a fragment for which satisfiability can be reduced to 1-TPTL, which is decidable over finite words with non-primitive recursive complexity [13].

Generalization to Non-Treelike Monitors

The problem is generalized for non-treelike monitors by defining PolicyChange and PolicyChange∗, which considers a generic monitor M not necessarily treelike. The lower bounds proven for the treelike case still hold for the unrestricted counterparts. p. 1

Where the paper says it

We show that if we remove the assumption that monitors are treelike, discrete-time policy change for pMTL is still decidable and in 2EXPSPACE, while policy change for pLTL is in EXPSPACE (Section 6). The following table summarizes the results proven in Sections 4 and 5.

Conclusion

In this paper, we have introduced the policy change problem that arises in the context of online monitoring of changing specifications, and studied it for treelike monitors. We have shown that over real-time semantics our problem has tight non-primitive recursive bounds, while over discrete-time semantics it is EXPSPACE-complete. p. 0

Where the paper says it

We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

While we have some preliminary results (cf. p. 1
Where the paper says it

We show that if we remove the assumption that monitors are treelike, discrete-time policy change for pMTL is still decidable and in 2EXPSPACE, while policy change for pLTL is in EXPSPACE (Section 6). The following table summarizes the results proven in Sections 4 and 5.

Section 6), as part of future work, we would like to identify the complexity of the more general problem, even under real-time semantics. p. 1
Where the paper says it

We give a generalised definition of policy change for treelike monitors independent of any specific monitor implementation (Section 3). We solve the decision problem associated with policy change for real-time pMTL with non-primitive recursive complexity by reducing policy change to 1-TPTL satisfiability over finite words [13].

The tight bounds we proved in the treelike case are one exponent lower than our preliminary unrestricted counterparts. p. 0
Where the paper says it

We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

References

1 Rajeev Alur and Thomas A. Henzinger. Real-time logics: Complexity and expressiveness. p. 1

Where the paper says it

We give a generalised definition of policy change for treelike monitors independent of any specific monitor implementation (Section 3). We solve the decision problem associated with policy change for real-time pMTL with non-primitive recursive complexity by reducing policy change to 1-TPTL satisfiability over finite words [13].

p. 1
Where the paper says it

We give a generalised definition of policy change for treelike monitors independent of any specific monitor implementation (Section 3). We solve the decision problem associated with policy change for real-time pMTL with non-primitive recursive complexity by reducing policy change to 1-TPTL satisfiability over finite words [13].

Inf. Comput., 104(1):35–77, 1993

2 Rajeev Alur and Thomas A. Henzinger. A really temporal logic. p. 0

Where the paper says it

We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

p. 0
Where the paper says it

We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

J. ACM, 41(1):181–204, 1994

3 David Basin, Bhargav Nagaraja Bhatt, Srđan Krstić, and Dmitriy Traytel. Almost event-rate independent monitoring. p. 1

Where the paper says it

Yuan [24] presents a sound but incomplete algorithm that can perform changes between some pairs of first-order policies in the MonPoly tool [4]. In contrast to these works, we consider a decision procedure that determines, for every policy pair, whether adaptation is possible, independent of the specific monitoring algorithm used.

p. 1
Where the paper says it

Yuan [24] presents a sound but incomplete algorithm that can perform changes between some pairs of first-order policies in the MonPoly tool [4]. In contrast to these works, we consider a decision procedure that determines, for every policy pair, whether adaptation is possible, independent of the specific monitoring algorithm used.

Formal Methods Syst. p. 0
Where the paper says it

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. 2012 ACM Subject Classification Theory of computation → Logic and verification; Security and privacy → Formal methods and theory of security Keywords and phrases Policy change, Monitoring, Online algorithms, Metric temporal logic, Hyperlogics Digital Object Identifier 10.

p. 0
Where the paper says it

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. 2012 ACM Subject Classification Theory of computation → Logic and verification; Security and privacy → Formal methods and theory of security Keywords and phrases Policy change, Monitoring, Online algorithms, Metric temporal logic, Hyperlogics Digital Object Identifier 10.

p. 0
Where the paper says it

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. 2012 ACM Subject Classification Theory of computation → Logic and verification; Security and privacy → Formal methods and theory of security Keywords and phrases Policy change, Monitoring, Online algorithms, Metric temporal logic, Hyperlogics Digital Object Identifier 10.

Des., 54(3):449–478, 2019

4 David Basin, Felix Klaedtke, Samuel Müller, and Eugen Zălinescu. Monitoring metric first-order temporal properties. p. 1

Where the paper says it

Yuan [24] presents a sound but incomplete algorithm that can perform changes between some pairs of first-order policies in the MonPoly tool [4]. In contrast to these works, we consider a decision procedure that determines, for every policy pair, whether adaptation is possible, independent of the specific monitoring algorithm used.

J. ACM, 62(2):15:1–15:45, 2015

5 Borzoo Bonakdarpour, Jyotirmoy V. Deshmukh, and Miroslav Pajic. Opportunities and challenges in monitoring cyber-physical systems security. p. 0

Where the paper says it

Policy Change for Treelike Monitors François Hublet # Ñ Institute of Information Security, Department of Computer Science, ETH Zurich, Switzerland Dhruv Nevatia # Ñ Institute of Information Security, Department of Computer Science, ETH Zurich, Switzerland Joshua Schneider Institute of Information Security, Department of Computer Science, ETH Zurich, Switzerland Abstract We study the policy change problem that arises in the runtime verification of long-running systems. The online monitors typically used in this context are generally treelike, in that they maintain substates that monitor subformulae of the target policy.

In Tiziana Margaria and Bernhard Steffen, editors, 8th Int. Symp. on Leveraging Applications of Formal Methods, Verification and Validation (ISoLA 2018), Part IV, volume 11247 of LNCS, pages 9–18

6 Marc Carwehl, Thomas Vogel, Genaína Nunes Rodrigues, and Lars Grunske. Runtime verification of self-adaptive systems with changing requirements. p. 1

Where the paper says it

Related work. The importance of policy change has been recognized in the context of self-adaptive systems, which use monitors to enact adaptation procedures if a violation of the system’s requirements is detected [9].

p. 1
Where the paper says it

Related work. The importance of policy change has been recognized in the context of self-adaptive systems, which use monitors to enact adaptation procedures if a violation of the system’s requirements is detected [9].

In 18th IEEE/ACM Symp. p. 0
Where the paper says it

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. 2012 ACM Subject Classification Theory of computation → Logic and verification; Security and privacy → Formal methods and theory of security Keywords and phrases Policy change, Monitoring, Online algorithms, Metric temporal logic, Hyperlogics Digital Object Identifier 10.

p. 0
Where the paper says it

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. 2012 ACM Subject Classification Theory of computation → Logic and verification; Security and privacy → Formal methods and theory of security Keywords and phrases Policy change, Monitoring, Online algorithms, Metric temporal logic, Hyperlogics Digital Object Identifier 10.

on Software Engineering for Adaptive and Self-Managing Systems (SEAMS 2023), pages 104–114

7 Michael R. Clarkson, Bernd Finkbeiner, Masoud Koleini, Kristopher K. Micinski, Markus N. Rabe, and César Sánchez. Temporal logics for hyperproperties. p. 8

Where the paper says it

2 Information Formulae for pMTL Our construction of information formulae will require time constraints spanning across multiple temporal operators. Such bounds are difficult to express in logics like MTL, where the interval constraints are local to each operator.

p. 8
Where the paper says it

2 Information Formulae for pMTL Our construction of information formulae will require time constraints spanning across multiple temporal operators. Such bounds are difficult to express in logics like MTL, where the interval constraints are local to each operator.

In Martín Abadi and Steve Kremer, editors, 3rd Int. Conf. on Principles of Security and Trust (POST 2014), volume 8414 of LNCS, pages 265–284

8 Michael R. Clarkson and Fred B. Schneider. Hyperproperties. J. Comput. Secur., 18(6):1157–1210, 2010

9 Martin S. Feather, Stephen Fickas, Axel van Lamsweerde, and Christophe Ponsard. Reconciling system requirements and runtime behavior. p. 0

Where the paper says it

We consider when and how the policy can be changed while the monitored system is running by only exploiting the information stored in the monitor’s state. This is relevant, for example, to account for new system functionality or changes in regulatory requirements.

p. 0
Where the paper says it

We consider when and how the policy can be changed while the monitored system is running by only exploiting the information stored in the monitor’s state. This is relevant, for example, to account for new system functionality or changes in regulatory requirements.

In 9th Int. Workshop on Software Specification and Design (IWSSD 1998), pages 50–59

10 Bernd Finkbeiner and Christopher Hahn. Deciding hyperproperties. p. 6

Where the paper says it

Denoting x = (∅, 31), the former implies yˆ φ3 (µˆ φ3 (q, x), x) = 1 and the latter yˆ φ3 (µˆ φ3 (q, x), x) = 0, a contradiction. 4 Deciding Policy Change with Real-Time Semantics In this section, we decide PolicyChange in three steps.

p. 6
Where the paper says it

Denoting x = (∅, 31), the former implies yˆ φ3 (µˆ φ3 (q, x), x) = 1 and the latter yˆ φ3 (µˆ φ3 (q, x), x) = 0, a contradiction. 4 Deciding Policy Change with Real-Time Semantics In this section, we decide PolicyChange in three steps.

In Josée Desharnais and Radha Jagadeesan, editors, 27th Int. Conf. on Concurrency Theory (CONCUR 2016), volume 59 of LIPIcs, pages 13:1–13:14

11 Carlo Ghezzi, Joel Greenyer, and Valerio Panzica La Manna. Synthesizing dynamically updating controllers from changes in scenario-based specifications. p. 1

Where the paper says it

Changing specifications at runtime has also been studied from the perspective of controller synthesis from modal sequence diagrams [11]. There, the main problem is to delay the change until it can be done safely, whereas monitors are expected to respond to whatever changes occur in their environment.

In Hausi A. Müller and Luciano Baresi, editors, 7th Int. Symp. on Software Engineering for Adaptive and SelfManaging Systems (SEAMS 2012), pages 145–154

12 Giuseppe De Giacomo and Moshe Y. Vardi. Linear temporal logic and linear dynamic logic on finite traces. p. 3

Where the paper says it

XX:4 Policy Change for Treelike Monitors φ on s = (σ, δ) at i, is the least relation closed under the following rules: ⟨s, i⟩ |= true ⟨s, i⟩ |= P if P ∈ σi ⟨s, i⟩ |= ¬φ if ⟨s, i⟩ ̸|= φ ⟨s, i⟩ |= φ1 ∨ φ2 if ⟨s, i⟩ |= φ1 or ⟨s, i⟩ |= φ2 ⟨s, i⟩ |= Iφ if i > 0, τi − τi−1 ∈ I, and ⟨s, i − 1⟩ |= φ ⟨s, i⟩ |= φ1 SI φ2 if there exists j ≤ i such that τj − τi ∈ I, ⟨s, j⟩ |= φ2, and ⟨s, k⟩ |= φ1 for all k with j < k ≤ i The policy JφK consists of all non-empty traces s such that ⟨s, |s| − 1⟩ |= φ. Past-time linear temporal logic (pLTL) can be viewed as the fragment of pMTL where all intervals of and S operators are [0, ∞).

In Francesca Rossi, editor, 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI 2013), pages 854–860

13 Christoph Haase, Joël Ouaknine, and James Worrell. On Process-Algebraic Extensions of Metric Temporal Logic, pages 283–300

14 Klaus Havelund, Doron Peled, and Dogan Ulus. First-order temporal logic monitoring with BDDs. p. 1

Where the paper says it

Yuan [24] presents a sound but incomplete algorithm that can perform changes between some pairs of first-order policies in the MonPoly tool [4]. In contrast to these works, we consider a decision procedure that determines, for every policy pair, whether adaptation is possible, independent of the specific monitoring algorithm used.

Formal Methods Syst. Des., 56(1):1–21, 2020

15 Hsi-Ming Ho, Ruoyu Zhou, and Timothy M. Jones. Timed hyperproperties. p. 1

Where the paper says it

Carwehl et al. [6] present a policy change approach for monitors constructed from timed automata templates, which correspond to a fragment of future-time MTL.

Inf. Comput., 280:104639, 2021

16 Ron Koymans. Specifying real-time properties with metric temporal logic. p. 1

Where the paper says it

This leads us to the following research question: under which condition is policy change possible? In this paper, we answer this question for past-time metric temporal logic (pMTL) with both real-time and discrete-time semantics [16, 1] as the policy language.

Real Time Syst. p. 1
Where the paper says it

This leads us to the following research question: under which condition is policy change possible? In this paper, we answer this question for past-time metric temporal logic (pMTL) with both real-time and discrete-time semantics [16, 1] as the policy language.

, 2(4):255–299, 1990

17 François Laroussinie, Nicolas Markey, and Ph Schnoebelen. Efficient timed model checking for discrete-time systems. p. 2

Where the paper says it

In runtime verification, traces are obtained by observing the running system and are thus finite. We therefore model traces as finite timed words, using non-negative real numbers for the real time domain and natural numbers for the discrete time domain.

Theoretical Computer Science, 353(1-3):249–271, 2006

18 Leonardo Lima, Andrei Herasimau, Martin Raszyk, Dmitriy Traytel, and Simon Yuan. Explainable online monitoring of metric temporal logic. p. 0

Where the paper says it

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. 2012 ACM Subject Classification Theory of computation → Logic and verification; Security and privacy → Formal methods and theory of security Keywords and phrases Policy change, Monitoring, Online algorithms, Metric temporal logic, Hyperlogics Digital Object Identifier 10.

In Sriram Sankaranarayanan and Natasha Sharygina, editors, 29th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2023), Part II, volume 13994 of LNCS, pages 473–491

19 Joël Ouaknine and James Worrell. On the decidability and complexity of metric temporal logic over finite words. p. 8

Where the paper says it

Our augmented logic, which we call Hyper past-Time Propositional Temporal Logic or HyperpTPTL, is intractable. However, we carve out a fragment for which satisfiability can be reduced to 1-TPTL, which is decidable over finite words with non-primitive recursive complexity [13].

Logical Methods in Computer Science, 3, 2007

20 Amir Pnueli and Aleksandr Zaks. PSL model checking and run-time verification via testers. p. 2

Where the paper says it

In runtime verification, traces are obtained by observing the running system and are thus finite. We therefore model traces as finite timed words, using non-negative real numbers for the real time domain and natural numbers for the discrete time domain.

In Jayadev Misra, Tobias Nipkow, and Emil Sekerinski, editors, 14th Int. Symp. on Formal Methods (FM 2006), volume 4085 of LNCS, pages 573–586

21 Martin Raszyk, David Basin, Srđan Krstić, and Dmitriy Traytel. Multi-head monitoring of metric temporal logic. p. 0

Where the paper says it

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. 2012 ACM Subject Classification Theory of computation → Logic and verification; Security and privacy → Formal methods and theory of security Keywords and phrases Policy change, Monitoring, Online algorithms, Metric temporal logic, Hyperlogics Digital Object Identifier 10.

In Yu-Fang Chen, Chih-Hong Cheng, and Javier Esparza, editors, 17th Int. Symp. on Automated Technology for Verification and Analysis (ATVA 2019), volume 11781 of LNCS, pages 151–170

22 Prasanna Thati and Grigore Roşu. Monitoring algorithms for metric temporal logic specifications. p. 0

Where the paper says it

We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete. 2012 ACM Subject Classification Theory of computation → Logic and verification; Security and privacy → Formal methods and theory of security Keywords and phrases Policy change, Monitoring, Online algorithms, Metric temporal logic, Hyperlogics Digital Object Identifier 10.

In Klaus Havelund and Grigore Roşu, editors, 4th Workshop on Runtime Verification (RV@ETAPS 2004), volume 113 of Electronic Notes in Theoretical Computer Science, pages 145–162

23 Yih-Kuen Tsay and Moshe Y Vardi. From linear temporal logics to büchi automata: the early and simple principle. p. 3

Where the paper says it

XX:4 Policy Change for Treelike Monitors φ on s = (σ, δ) at i, is the least relation closed under the following rules: ⟨s, i⟩ |= true ⟨s, i⟩ |= P if P ∈ σi ⟨s, i⟩ |= ¬φ if ⟨s, i⟩ ̸|= φ ⟨s, i⟩ |= φ1 ∨ φ2 if ⟨s, i⟩ |= φ1 or ⟨s, i⟩ |= φ2 ⟨s, i⟩ |= Iφ if i > 0, τi − τi−1 ∈ I, and ⟨s, i − 1⟩ |= φ ⟨s, i⟩ |= φ1 SI φ2 if there exists j ≤ i such that τj − τi ∈ I, ⟨s, j⟩ |= φ2, and ⟨s, k⟩ |= φ1 for all k with j < k ≤ i The policy JφK consists of all non-empty traces s such that ⟨s, |s| − 1⟩ |= φ. Past-time linear temporal logic (pLTL) can be viewed as the fragment of pMTL where all intervals of and S operators are [0, ∞).

In Model Checking, Synthesis, and Learning: Essays Dedicated to Bengt Jonsson on The Occasion of His 60th Birthday, pages 8–40

24 Simon Yuan. Policy change in MonPoly. p. 1

Where the paper says it

Yuan [24] presents a sound but incomplete algorithm that can perform changes between some pairs of first-order policies in the MonPoly tool [4]. In contrast to these works, we consider a decision procedure that determines, for every policy pair, whether adaptation is possible, independent of the specific monitoring algorithm used.

Master’s thesis, ETH Zurich, Switzerland, 2022

B Policy Change for Non-Treelike Monitors

1 Rajeev Alur and Thomas A. Henzinger. Real-time logics: Complexity and expressiveness. Inf. Comput., 104(1):35–77, 1993

2 Rajeev Alur and Thomas A. Henzinger. A really temporal logic. J. ACM, 41(1):181–204, 1994

3 David Basin, Bhargav Nagaraja Bhatt, Srđan Krstić, and Dmitriy Traytel. Almost event-rate independent monitoring. Formal Methods Syst. Des., 54(3):449–478, 2019

6 Marc Carwehl, Thomas Vogel, Genaína Nunes Rodrigues, and Lars Grunske. Runtime verification of self-adaptive systems with changing requirements. In 18th IEEE/ACM Symp. on Software Engineering for Adaptive and Self-Managing Systems (SEAMS 2023), pages 104–114

7 Michael R. Clarkson, Bernd Finkbeiner, Masoud Koleini, Kristopher K. Micinski, Markus N. Rabe, and César Sánchez. Temporal logics for hyperproperties. In Martín Abadi and Steve Kremer, editors, 3rd Int. Conf. on Principles of Security and Trust (POST 2014), volume 8414 of LNCS, pages 265–284

8 Michael R. Clarkson and Fred B. Schneider. Hyperproperties. J. Comput. Secur., 18(6):1157–1210, 2010

9 Martin S. Feather, Stephen Fickas, Axel van Lamsweerde, and Christophe Ponsard. Reconciling system requirements and runtime behavior. In 9th Int. Workshop on Software Specification and Design (IWSSD 1998), pages 50–59

10 Bernd Finkbeiner and Christopher Hahn. Deciding hyperproperties. In Josée Desharnais and Radha Jagadeesan, editors, 27th Int. Conf. on Concurrency Theory (CONCUR 2016), volume 59 of LIPIcs, pages 13:1–13:14

--- Page 5 ---

XX:5 Policy Change for Treelike Monitors

remainder against φ2 using only the information in its state. This avoids the two drawbacks mentioned above. p. 1

Where the paper says it

XX:2 Policy Change for Treelike Monitors remainder against φ2 using only the information in its state. This avoids the two drawbacks mentioned above.

For example, the policy change corresponding to shortening the registry’s notification deadline is always possible. p. 1
Where the paper says it

This avoids the two drawbacks mentioned above. For example, the policy change corresponding to shortening the registry’s notification deadline is always possible.

However, policy change is not always possible, as an efficient monitor’s state typically does not contain enough information to reconstruct all past events. p. 1
Where the paper says it

This information is sufficient to judge whether the new, shorter deadline is violated. However, policy change is not always possible, as an efficient monitor’s state typically does not contain enough information to reconstruct all past events.

The algorithm checks whether ↓φ1 entails ↑φ2, i.e., iff ↓φ1 → ↑φ2 is valid. This involves a reduction to 1-TPTL satisfiability over finite words. p. 1
Where the paper says it

We solve the decision problem associated with policy change for real-time pMTL with non-primitive recursive complexity by reducing policy change to 1-TPTL satisfiability over finite words [13]. We prove that such policy change is NPR-hard via a reduction from pMTL satisfiability on finite traces (Section 4).

The complexity of this decision procedure is non-primitive recursive because of the reduction from pMTL satisfiability on finite traces. p. 1
Where the paper says it

We solve the decision problem associated with policy change for real-time pMTL with non-primitive recursive complexity by reducing policy change to 1-TPTL satisfiability over finite words [13]. We prove that such policy change is NPR-hard via a reduction from pMTL satisfiability on finite traces (Section 4).

Where the gains come from

The tight bounds in the treelike case are one exponent lower than our preliminary unrestricted counterparts. The treelike decision procedure effectively takes advantage of the monitors’ structure to go beyond a naïve enumeration of possible state mappings. p. 1

Where the paper says it

Yuan [24] presents a sound but incomplete algorithm that can perform changes between some pairs of first-order policies in the MonPoly tool [4]. In contrast to these works, we consider a decision procedure that determines, for every policy pair, whether adaptation is possible, independent of the specific monitoring algorithm used.

The complexity analysis relies on reductions to pLTL or pMTL satisfiability, which do not rely on the assumption that the monitor is treelike. p. 1
Where the paper says it

We give a generalised definition of policy change for treelike monitors independent of any specific monitor implementation (Section 3). We solve the decision problem associated with policy change for real-time pMTL with non-primitive recursive complexity by reducing policy change to 1-TPTL satisfiability over finite words [13].

The preliminary results in Section 6 show that PolicyChange for non-treelike monitors is in EXPSPACE. p. 1
Where the paper says it

We show that if we remove the assumption that monitors are treelike, discrete-time policy change for pMTL is still decidable and in 2EXPSPACE, while policy change for pLTL is in EXPSPACE (Section 6). The following table summarizes the results proven in Sections 4 and 5.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Policy change for treelike monitors can be decided for real-time past-time metric temporal logic (pMTL) with non-primitive recursive complexity by reducing policy change to 1-TPTL satisfiability over finite words. This allows AI systems to formally determine if a new system functionality or regulatory requirement can be incorporated into a long-running system without replaying the entire history.

  2. The decision procedure for policy change over real-time semantics can be used to check whether policy change from phi1 to phi2 is possible, providing a formal guarantee that the monitor state information is sufficient for adaptation. This capability allows AI agents to safely modify system specifications at runtime based on observed system behavior while maintaining compliance with the new requirements.

  3. The problem of PolicyChange for discrete-time pLTL and pMTL can be solved, demonstrating that it is PSPACE-complete and EXPSPACE-complete, respectively. This formal complexity analysis helps in understanding the inherent computational difficulty of ensuring policy changes in systems with discrete time semantics, guiding the design of more efficient verification methods.

  4. PolicyChange for non-treelike monitors (PolicyChange star) is shown to be decidable in EXPSPACE for pLTL and 2EXPSPACE for pMTL over discrete-time semantics. This extends the ability of AI systems to perform policy changes even when the underlying monitoring structure is not restricted to a treelike format, offering a more general framework for dynamic system adaptation.

Abstract

We study the policy change problem that arises in the runtime verification of long-running systems. The online monitors typically used in this context are generally treelike, in that they maintain substates that monitor subformulae of the target policy. We consider when and how the policy can be changed while the monitored system is running by only exploiting the information stored in the monitor's state. This is relevant, for example, to account for new system functionality or changes in regulatory requirements. We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

Related papers