CS Paper Radar

Execution-Time Opacity Logic: A Logic for Ensuring ET-Opacity in Timed Systems

Jean Leneutre, Dylan Marinho, Vadim Malvone, James Ortiz

cs.FL ·submitted 2026-09-09 11:42 UTC · v1
hot direction

Abstract

Ensuring confidentiality in Cyber-Physical Systems is critical, especially when attackers exploit execution times to infer sensitiveinformation. Traditional opacity models are inadequate for timed systems, as verifying opacity in Timed Automata is undecidable. To address this challenge, we propose Execution-Time Opacity Logic (ETOL), a new formalism that specifies opacity by requiring that for every execution satisfying a secret formula, there exists another execution of the same duration that does not satisfy it. ETOL guarantees that timing observations cannot reveal confidential agent activities. We present a decidable and efficient verification framework based on zone-based model checking, supported by a dedicated algorithm that systematically identifies duration-equivalent executions. Our approach is validated through an ATM case study, showing that ETOL enables efficient verification of execution-time confidentiality under timing attacks. We also developed a prototype tool for the ETOL logic that supports symbolic model checking over timed systems. It allows users to verify ETOL formulas based on clock-constrained execution paths.

Closest papers

Nearest neighbours by meaning across the whole index.

Execution-Time Opacity in (Controllable) Timed Automata is Hard

cs.CC cs.FL ·2026-10-11 ·Sarah Dépernet, Engel Lefaucheux
publishedtheory similarity 0.77
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Timing information leakage occurs whenever an attacker successfully deduces confidential internal information by observing some timed information such as the total duration of a run. Timed automata (TAs) are an extension of finite-state automata with a set of clocks evolving at the same rate and that can be tested or reset. Hence, this formalism is able to represent systems involving timing constraints reacting to the passage of time. Some of the transitions in a timed automaton may be controlled, i.e., enabled or disabled, to limit the runs that are allowed. Execution-time opacity (ET-opacity) aims at studying timing information leakage through the analysis of timed automata. More precisely, the ET-opacity problem consists in deciding whether an attacker can deduce whether some secret locations were visited by a run, solely from the run's duration. When control is allowed, the goal becomes to find a strategy that blocks the runs leaking information. This problem has been shown decidable for TAs, with and without control. However, these existing results only provide upper bounds on the complexity of the ET-opacity problem, sometimes largely above the tight bound. Our main contribution is to provide tight lower bounds for those two results. Moreover, for controllable TAs, two variants of ET-opacity (depending on whether detecting if a run did not visit a secret location represents an information leakage or not, and named full and weak ET-opacity respectively) had been separately studied; we prove here that these two notions are inter-reducible.

0.25

Practical Runtime Enforcement of First-Order Temporal Requirements

cs.SE ·2026-10-03 ·François Hublet, David Basin, Srđan Krstić
similarity 0.73
Abstract

Runtime enforcers observe a system's behavior and exert control over it to ensure that the system always adheres to its requirements. Many natural requirements not only formulate restrictions on the system's present behavior, but also impose obligations on its future behavior; for instance, agentic security may require personal data collected during a run to be erased by some deadline. In an ever-growing compliance landscape, real-world systems may be subject to hundreds of such requirements. However, existing enforcement mechanisms supporting complex policies are often too slow for production software; instead, developers may resort to non-temporal access control mechanisms and ad-hoc instrumentation, but these scale poorly with requirement complexity. To address this problem, we introduce an efficient algorithm and tool for enforcing complex temporal requirements and demonstrate its performance. Specifically, we identify a fragment of Metric First-Order Temporal Logic (MFOTL) that can be enforced with low runtime complexity while supporting a rich family of practically relevant requirements, including obligations. We then design an enforcement algorithm for this fragment and implement it in EnfFlash, a novel tool that enforces requirements with latency up to 44x lower than EnfGuard, the previous state-of-the-art enforcer, on standard benchmarks, and up to three orders of magnitude lower on security policies for LLM agents. This performance is achieved by compiling requirements into imperative programs that we efficiently interpret. We evaluate EnfFlash both standalone, on existing benchmarks, and integrated in web applications as an enforcement backend. We demonstrate that it can enforce a substantial 400-line MFOTL formula specifying the GDPR on a social network while adding under 15 ms to each page view, which is sufficient for most interactive and real-time applications.

0.19

Verification of Security Properties of Cryptographic Protocols

cs.CR ·2026-11-06 ·Simona Bernardi, Joaquín Ezpeleta
published similarity 0.69
Abstract

Developing cryptographic protocols that are free from vulnerabilities is very challenging, as evidenced by numerous design flaws and implementation bugs in widely used protocols. Recent work has leveraged model checking to generate negative test cases, that is test cases that include the behavior of Dolev-Yao attacker. In this paper, we address the problem of analyzing execution traces produced by testing protocol implementations with such negative test cases. We propose a method for detecting violations of security properties by model-checking execution traces. Our approach employs a model checker based on DLTL, a Linear Temporal Logic with freeze operators, and supports automation of the testing process through pre- and post-processing steps. These steps, respectively, bridge the gap between different levels of abstraction and synthesize the results produced by the model checker.We present experimental results as a proof of concept for the feasibility of the proposed method.

0.33

Automated Abstraction Refinement for Information Flow Security in Embedded Systems

cs.CR cs.PLcs.SE ·2026-09-24 ·Jonas Becker-Kupczok, Lukas Ernst, Paula Herber
published similarity 0.68
Abstract · 18 pages, 3 figures, 1 table. Accepted at the 24th International Conference on Software Engineering and Formal Methods (SEFM 2026), to be pu…

Information flow analysis (IFA) is a powerful technique for verifying confidentiality and integrity and is therefore highly desirable for security-sensitive embedded systems. However, as these systems are inherently concurrent and time-dependent, existing IFA for embedded systems tend to be either imprecise or expensive. In this paper, we propose an approach to tackle this problem using automatic abstraction refinement. The key idea is to heuristically choose abstraction levels based on information about dependencies between states and detected potential information leakage. Our approach builds on previous work, where we leverage symbolic execution to precisely capture data, control, timing, and event dependencies between processes within an IFA. To capture values symbolically, this analysis uses abstract interpretation. While the existing approach requires manual definition of abstraction levels, our novel contribution in this paper is using carefully designed heuristics to select these levels automatically. The aim is to keep analysis times acceptable while also retaining enough information to decide whether or not illegal information flow is possible. We have implemented our approach for the system design language SystemC and demonstrate its feasibility with experimental results on several shared bus architectures.

0.44

Privacy-Preserving Robust Monitoring of Dense-Time Temporal Logic

cs.LO ·2026-10-19 ·Charles Koll, Mike Rosulek, Houssam Abbas
published similarity 0.66
Abstract · 13 pages, 8 figures, presented at Formal Methods in Computer-Aided Design (FMCAD) 2026

Motivated by the use of third-party testing, this paper presents a privacy-preserving implementation of the robustness monitoring of Signal Temporal Logic (STL). STL is a specification language for systems whose output traces have real-valued timestamps -- most prominently, cyber-physical systems. Its robust semantics, which assign real rather than binary truth values, are an essential ingredient of systems testing and runtime monitoring. In a number of system testing scenarios, the designer and the tester are separate parties. This testing-as-a-service model is common in software, avionics, and semiconductors, and is growing in importance in the red-teaming of machine learning models. In such a model, the designer seeks to preserve the privacy (or secrecy) of its design, while the tester seeks to preserve the privacy of its collateral, including the detailed specification suite. This paper presents a secure multi-party implementation of the robust semantics using arithmetic circuits. This implementation allows one party, which provides a secret trace, and a second party which provides a secret formula, to jointly compute the robustness without either party being able to learn the other party's secret input. We present a number of algorithmic modifications to the robustness computation to enable an efficient multi-party robustness computation. We also present new, semi-linear, robust semantics for STL that take advantage of the efficiencies of arithmetic circuits. The experimental results demonstrate that not only is this privacy-preserving monitor efficient on its own, but also that it can be used in a testing loop without affecting the speed at which bugs are found during robustness-guided system testing.

0.62

Enforcement of In-Kernel Stateful Security Policies via eBPF

cs.CR cs.PL ·2026-09-12 ·Letterio Galletta
published similarity 0.66
Abstract · This is the extended version of the paper appearing in Proc. ACM SIGSAC Conference on Computer and Communications Security (CCS '26). It inc…

Many attacks against workloads running on multi-tenant systems are multi-step and history-dependent: sequences of innocuous operations whose malicious nature emerges only over an execution trace. Defending against them requires security policies that are stateful, are enforced within the kernel, and have a precise semantics. Currently deployed proposals fail on at least one count: kernel's built-in syscall filtering and classical MAC frameworks are stateless, while current eBPF-based tools express their policies through ad hoc YAML rules that cannot capture temporal relations among events, and whose semantics is defined only by the implementation. We present BPFence, an in-kernel runtime-verification framework that satisfies the properties above. BPFence provides a policy language with a formal semantics that can express temporal relations among events. It also provides a type system that statically distinguishes events the kernel can control from those it can only observe. Every well-typed policy is compiled into a finite-state monitor proved correct with respect to its semantics, and then into eBPF programs that run inside the kernel. We evaluate BPFence on seven case studies drawn from real-world attack patterns, and on a set of micro- and macro-benchmarks to show that the enforcement overhead remains compatible with production deployment.

0.24

Runtime Verification under Split Past and Future

cs.LO ·2026-08-21 ·Dogan Ulus
similarity 0.66
Abstract

Runtime assurance for autonomous systems increasingly requires reasoning not only about observed executions but also about anticipated future behaviors. Traditional runtime verification, however, primarily evaluates the execution observed so far and does not directly account for predicted continuations. We propose a formal framework for runtime assurance that combines monitoring of the observed execution with analysis of multiple predicted continuations. To support this integration, we introduce Split Linear Temporal Logic (SplitLTL), a linear-time temporal logic that assigns complementary roles to past and future temporal specifications within a single specification. The past component uses the observed history to determine the assurance requirements applicable at the current point of execution, while the future component evaluates predicted continuations against those requirements. The framework therefore filters predicted continuations according to the requirements induced by the observed history, identifying admissible continuations that can support subsequent decision making. We formally define the syntax and semantics of SplitLTL and present an online monitoring architecture for evaluating observed executions together with predicted continuations.

0.20

Runtime Monitoring of Distributed Cyber-Physical Systems Without a Global Clock

cs.LO ·2026-08-13 ·Charles Koll, Houssam Abbas
published similarity 0.65
Abstract · Accepted to Runtime Verification 2026

We give the first theoretical characterization, and the first algorithm, for continuous monitoring of a distributed Cyber-Physical System (CPS) against a dense-time temporal logic specification. A distributed CPS is composed of multiple agents, each with a local clock; these clocks drift from each other, so there is no well-defined global time. When monitoring such a system's output signal against a temporal logic specification, it is not evident how to interpret the temporal constraints of the formula, and what satisfaction means. Yet CPS designers, like control engineers, typically think of their system's operation in terms of global time. Most existing techniques for monitoring distributed systems work with discrete-time specifications not suitable for CPS, and/or require an explicit mapping of temporal constraints to local clocks. We introduce an algorithm that addresses the above challenges for a fragment of Signal Temporal Logic (STL) that still includes all temporal operators. It relies on a novel extension of satisfaction signals to this partially synchronous setting (where clocks drift), and an analysis of the geometry of multi-dimensional partially synchronous time. The algorithm returns the set of all possible global moments that can satisfy the specification. Knowledge of these possible global moments is important for debugging distributed hybrid control systems such as fleets of drones and electrical grids. We derive the worst-case complexity of the algorithm, and implement a sound approximation of it that experimentally illustrates effective monitoring, even in scenarios of up to 50 agents.

0.23