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

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

TL;DR

This paper explores how to prevent "timing leaks" in real-time systems by ensuring that an attacker cannot deduce secret internal states simply by measuring how long a system takes to run. By modeling systems as Timed Automata, the authors identify which configurations are "opaque" (secure) and provide a roadmap of which security-checking problems are mathematically solvable (decidable) versus those that are impossible to solve for all cases.

What Problem Does This Paper Address?

In cybersecurity, a "side-channel attack" occurs when an attacker gains information not from the intended output of a program, but from physical implementation details—like power consumption or, in this case, execution time. If a security-critical process (like checking a password) takes 10ms when the password is wrong but 15ms when it's right, the timing itself leaks the secret.

The authors tackle Execution-Time Opacity (ET-opacity). They assume an attacker knows the system's model and can measure the total time from start to finish. The challenge is to configure the system’s internal timing parameters so that for any given execution time, the attacker cannot tell whether a "secret" part of the system was visited. The paper specifically looks at Timed Automata (TAs)—a mathematical way to model systems with clocks—and their parametric versions (PTAs), where some timing constraints are unknown variables.

Methods

The authors categorize and analyze several flavors of opacity:

  • $\exists$-ET-opacity: Does there exist at least one execution time that is safe (ambiguous)?
  • Full ET-opacity: Are all possible execution times safe?
  • Weak ET-opacity: If a secret path exists for a certain duration, does a non-secret path also exist for that same duration?
  • Expiring Opacity: A more realistic model where a secret is only "sensitive" if it happened recently (within $\Delta$ time units of the system finishing).

To solve these, they use:

  1. Parametric TCTL: A logic used to describe properties of timed systems. They show that checking opacity in TAs can be reduced to checking these logic formulas.
  2. Self-Composition: A technique where the system is compared against a copy of itself to see if their behaviors (and timings) are indistinguishable.
  3. IMITATOR: A software tool used to implement their "semi-algorithm" for synthesizing safe timing parameters.

Datasets

While this is a theoretical paper, the authors validated their approach using:

  • DARPA STAC Benchmarks: A set of Java programs designed by researchers to highlight space/time vulnerabilities. The authors manually translated these into Timed Automata.
  • Literature Benchmarks: Standard examples of Parametric Timed Automata used in previous formal methods research.

Key Insights and Ideas

  • The "Black Box" Advantage: By limiting the attacker to only seeing the total execution time (rather than every intermediate event), many security problems that were previously thought to be "undecidable" (unsolvable by a computer) actually become decidable for Timed Automata.
  • Non-Monotonicity: A surprising "aha moment" is that making a system slower doesn't necessarily make it more secure. In parametric systems, increasing a delay might actually create a unique timing signature that leaks information, rather than hiding it.
  • The L/U-PTA Sweet Spot: The authors identify "Lower/Upper Parametric Timed Automata" as a useful middle ground. In this subclass, we can decide if a safe configuration exists, even though we might not be able to perfectly calculate every possible safe configuration.
  • Expiration Dates for Secrets: Introducing the $\Delta$ parameter (expiring opacity) bridges the gap between theoretical models and real-world systems like caches, where old data is eventually overwritten and no longer needs to be hidden.

Key Results

The paper provides a comprehensive "decidability map" (Tables 1 and 2):

  • For Timed Automata (TAs): Most opacity checking problems are decidable, typically within PSPACE or 5EXPTIME complexity.
  • For Parametric Timed Automata (PTAs): Most general problems are undecidable. You cannot write a program that will always find the perfect timing parameters for every possible system.
  • Practicality: Despite the theoretical "undecidability," their semi-algorithm implemented in the tool IMITATOR was able to successfully analyze and find safe timing configurations for the DARPA STAC benchmarks.

Limitations and Future Work

  • Modeling Complexity: Translating a real-world Java program into a Timed Automaton is currently a manual and difficult process. It struggles to account for complex hardware features like CPU pipelining or OS scheduling.
  • Intractability of Synthesis: Even when a problem is "decidable," the resulting set of safe parameters can be so complex that they cannot be represented using standard mathematical shapes (polyhedra), making them hard to use in practice.
  • Future Directions: The authors suggest moving from "checking" to "control"—automatically generating a "controller" that forces a system to wait or delay just enough to maintain opacity without ruining 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},
}

Loading related content...

Figure