Configuring Timing Parameters to Ensure Execution-Time Opacity in Timed Automata

Étienne André, Engel Lefaucheux, Didier Lime, Dylan Marinho, Jun Sun

Abstract

Timing information leakage occurs whenever an attacker successfully deduces confidential internal information by observing some timed information such as events with timestamps. Timed automata are an extension of finite-state automata with a set of clocks evolving linearly and that can be tested or reset, making this formalism able to reason on systems involving concurrency and timing constraints. In this paper, we summarize a recent line of works using timed automata as the input formalism, in which we assume that the attacker has access (only) to the system execution time. First, we address the following execution-time opacity problem: given a timed system modeled by a timed automaton, given a secret location and a final location, synthesize the execution times from the initial location to the final location for which one cannot deduce whether the secret location was visited. This means that for any such execution time, the system is opaque: either the final location is not reachable, or it is reachable with that execution time for both a run visiting and a run not visiting the secret location. We also address the full execution-time opacity problem, asking whether the system is opaque for all execution times; we also study a weak counterpart. Second, we add timing parameters, which are a way to configure a system: we identify a subclass of parametric timed automata with some decidability results. In addition, we devise a semi-algorithm for synthesizing timing parameter valuations guaranteeing that the resulting system is opaque. Third, we report on problems when the secret has itself an expiration date, thus defining expiring execution-time opacity problems. We finally show that our method can also apply to program analysis with configurable internal timings.

Introduction

In modern cybersecurity, side-channel attacks represent a significant threat. These attacks exploit physical implementation details—such as power consumption or execution time—to leak sensitive internal information. For instance, if a password-checking routine takes longer for a correct prefix than an incorrect one, the timing itself becomes a vulnerability. This paper addresses the challenge of Execution-Time Opacity (ET-opacity), focusing on how to configure a system's internal timing parameters to ensure that an attacker, observing only the total execution time, cannot determine whether a "secret" state was visited.

Theoretical Framework: Timed and Parametric Automata

To formally reason about these systems, the authors utilize Timed Automata (TA), which extend finite-state automata with clocks that evolve linearly. In many real-world scenarios, specific timing constraints are not fixed but are variables to be configured. This leads to the use of Parametric Timed Automata (PTA).

Example of a Parametric Timed Automaton (PTA) where $p_1$ and $p_2$ represent unknown timing parameters.

In a PTA, the goal is often to synthesize values for parameters (like $p_1$ and $p_2$ in the figure above) such that the resulting system satisfies security properties. The authors identify a specific subclass, Lower/Upper Parametric Timed Automata (L/U-PTA), which offers a balance between expressivity and mathematical tractability.

Defining Execution-Time Opacity

The research categorizes opacity into several distinct flavors:

  • $∃$-ET-opacity: Determines if there exists at least one execution time that is "safe" (i.e., ambiguous to an observer).
  • Full ET-opacity: Requires that all possible execution times are safe.
  • Weak ET-opacity: Ensures that if a secret path exists for a specific duration, a non-secret path of the same duration must also exist.
  • Expiring Opacity: A realistic extension where a secret is only considered sensitive if it occurred within a certain window ($Δ$) of the system's completion.

To analyze these properties, the authors employ techniques such as Self-Composition, where a system is compared against a copy of itself to check for indistinguishable behaviors, and Parametric TCTL, a logic for describing timed system properties.

Decidability and Key Results

A primary contribution of this work is the "decidability map," which outlines which security-checking problems can be solved algorithmically.

Decidability and complexity results for various ET-opacity problems across TA and PTA formalisms.

As shown in the table above, most opacity problems for standard Timed Automata are decidable, typically falling within PSPACE or 5EXPTIME complexity classes. However, for general Parametric Timed Automata, many problems become undecidable, meaning no general algorithm can solve them for all possible cases.

One surprising insight is the non-monotonicity of security in these systems: increasing a delay does not necessarily improve security. In some parametric configurations, a longer delay might create a unique timing signature that inadvertently leaks information.

Practical Application and Benchmarks

Despite the theoretical undecidability of general PTA problems, the authors developed a semi-algorithm implemented in the tool IMITATOR. This tool was successfully used to analyze and find safe timing configurations for the DARPA STAC Benchmarks—Java programs translated into Timed Automata to highlight timing vulnerabilities. This demonstrates that formal methods can provide practical security guarantees even in complex, parameterized environments.

Limitations and Future Outlook

While the framework is robust, several challenges remain. The translation of high-level code (like Java) into Timed Automata is currently a manual process that struggles to capture hardware-level nuances like CPU pipelining. Furthermore, the mathematical sets of safe parameters can sometimes be too complex to represent efficiently.

Future research aims to move from "checking" opacity to "controlling" it—automatically generating controllers that dynamically adjust system delays to maintain security without significantly degrading performance.

Summary updated

Abstract

:Timing information leakage occurs whenever an attacker successfully deduces confidential internal information by observing some timed information such as events with timestamps. Timed automata are an extension of finite-state automata with a set of clocks evolving linearly and that can be tested or reset, making this formalism able to reason on systems involving concurrency and timing constraints. In this paper, we summarize a recent line of works using timed automata as the input formalism, in which we assume that the attacker has access (only) to the system execution time. First, we address the following execution-time opacity problem: given a timed system modeled by a timed automaton, given a secret location and a final location, synthesize the execution times from the initial location to the final location for which one cannot deduce whether the secret location was visited. This means that for any such execution time, the system is opaque: either the final location is not reachable, or it is reachable with that execution time for both a run visiting and a run not visiting the secret location. We also address the full execution-time opacity problem, asking whether the system is opaque for all execution times; we also study a weak counterpart. Second, we add timing parameters, which are a way to configure a system: we identify a subclass of parametric timed automata with some decidability results. In addition, we devise a semi-algorithm for synthesizing timing parameter valuations guaranteeing that the resulting system is opaque. Third, we report on problems when the secret has itself an expiration date, thus defining expiring execution-time opacity problems. We finally show that our method can also apply to program analysis with configurable internal timings.
BibTeX
@inproceedings{andre2023configuring,
  author = {Étienne André and Engel Lefaucheux and Didier Lime and Dylan Marinho and Jun Sun},
  title = {{Configuring Timing Parameters to Ensure Execution-Time Opacity in Timed Automata}},
  booktitle = {TiCSA@ETAPS},
  year = {2023},
  url = {https://openreview.net/forum?id=8110Yol3V2},
}
Figure