# Investigating the Effects of Permanent Faults in QDI Circuits: A Formal Perspective

Raghda El Shehaby, Matthias Függer, Florian Huemer, Andreas Steininger

► To cite this version:

Raghda El Shehaby, Matthias Függer, Florian Huemer, Andreas Steininger. Investigating the Effects of Permanent Faults in QDI Circuits: A Formal Perspective. 2025 29th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), May 2025, Portland, United States. pp.142-150, 10.1109/ASYNC65240.2025.00027 . hal-05187822

HAL Id: hal-05187822

https://hal.science/hal-05187822v1

Submitted on 26 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Investigating the Effects of Permanent Faults in QDI Circuits: A Formal Perspective

Raghda El Shehaby*, Matthias Függer†, Florian Huemer*, Andreas Steininger*

*TU Wien, Institute of Computer Engineering, Vienna, Austria

{relshehaby, fhuemer, steininger}@ecs.tuwien.ac.at

†Université Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, Gif-sur-Yvette, France

mfuegger@lmf.cnrs.fr

**Abstract**—In the presence of permanent faults, QDI circuits exhibit the attractive property of halting their operation until a repair process has taken place and the fault has been bypassed. This is not always enough, however, as a recovery of the internal state of the circuit might be needed in case of its corruption before the deadlock. Some studies have attempted to provide an analysis for the circuit's behavior from a quantitative perspective based on empirical findings.

In this study, we present a formal framework aimed at comprehensively identifying the vulnerable windows of a QDI circuit for permanent faults. We establish a model for this type of faults and, based on our framework, demonstrate the equivalence of fault scenarios within certain windows. We leverage these insights in a tool that we showcase using a multiplier and an ALU following the 4-phase communication protocol.

***Index Terms***—permanent faults, QDI circuits, automatic evaluation

## I. INTRODUCTION

Due to their event-based (rather than state-based) operation, the fault susceptibility of asynchronous, specifically quasi delay-insensitive (QDI), circuits substantially differs from that of synchronous circuits. A known weakness in this respect is their sensitivity to extra transitions that may upset the protocol and corrupt or erroneously produce or remove data items. Their known strengths are insensitivity to delay-related effects, as well as fail-stop behavior in case of permanent faults. The latter, however, comes with the restriction that, even though the circuit indeed eventually stops as a consequence of a permanent fault, its state may become polluted until then, which complicates recovery [1].

The overarching goal of the research underlying this paper is to gain better insights when this state pollution happens and how it can best be mitigated. A natural approach towards that is to subject suitable target circuits to fault injection and study their behavior (For our purposes we currently restrict ourselves to single faults). However, a common problem with those experiments – most often simulations on gate-level – is the huge space of fault parameters that must be covered; specifically time and location of the fault event. Especially in

the time domain there is the fundamental limitation that fault injection is naturally bound to a discrete set of choices, typically a regular grid, to which neither faults nor fault sensitivity windows are bound. So even with the most elaborate and time consuming experiment one may always miss an important case.

Here a formal approach can come to the rescue: Experience, as well as formal results from [2], show that for every signal there are equivalence windows within which a fault has the same effect, no matter at which specific position it is injected. If we are able to identify all of these windows we obtain two substantial advantages: Firstly, by taking care to inject at least one fault into each of these windows during the campaign we obtain certainty to cover all relevant cases. And secondly, due to the equivalence property, we know that it is sufficient to inject just one fault per region, no matter how large it may be, and still obtain a complete picture. We can even weight each observed fault effect by the size of its associated sensitivity window. This allows to considerably reduce the fault space and thereby reduce the computational effort.

***Contributions and organization.*** In the following we present an algorithm which relies on a formalization of circuits based on the production rules formalism introduced by Martin [3] and adapted by El Shehaby, Függer, and Steininger [2] for unstable and non-binary signals. In Section IV, we prove that this algorithm correctly finds all SA faults in a circuit. Section IV-D discusses an implementation in Python and results for medium-sized circuits like a multiplier and an ALU. We conclude in Section V with an outlook on potential future improvements.

## II. BACKGROUND AND RELATED WORK

***Permanent faults in asynchronous circuits.*** The stuck-at fault (SAF) model has been widely adopted in the semiconductor industry, as it can effectively analyze the impacts of permanent faults on the gate-level [4]–[6]. Existing literature establishes that delay-insensitive circuits are inherently self-checking under the SAF model, leading to circuit halting [7]. The former study, along with [8] and [9], examines the specific conditions that cause a circuit to halt its operation.

It is important to note that the early work by Beerel [10], followed by Liebelt's study [11], have shown that under certain conditions, a SAF may not halt the circuit. Instead, it can cause the circuit to cycle within a so-called fake equivalence

<footnote>This research was partially supported by the project ENROL (grant I 3485-N31) of the Austrian Science Fund (FWF), the Doctoral College on Resilient Embedded Systems (DC-RES), the French National Research Agency (ANR) projects DREAMY (ANR-21-CE48-0003) and COSTXPRESS (ANR-23-CE45-0013), as well as the SAIF project, funded by the France 2030 government investment plan managed by ANR, under the reference ANR-23-PEIA-0006.</footnote>
class, making its behavior indistinguishable from the fault-free operation. However, this also means the SAF has no effect. Although this is definitely an issue for testing, it is unproblematic in our context of fault sensitivity.

Roncken and Bruls [12] examined the test quality of asynchronous circuits, highlighting the limitations of conventional test methods designed for synchronous designs. They demonstrate that holding a circuit between a handshake request and its acknowledgment is essential for improving test effectiveness. Through defect-oriented fault simulations, they show that this approach provides sufficient control for scan and IDDQ test techniques, which are particularly effective in detecting CMOS manufacturing defects.

In [13], LaFrieda and Manohar conduct a thorough analysis of faults in QDI circuits, exploring both transient and permanent faults. They classify their effects as deadlock, synchronization failure, and token generation and consumption. They conclude that SAFs, specifically, eventually lead to deadlocks. Similarly, [14] confirms these results and further shows that a SAF can also result in isochronic fork violations. It is widely agreed that achieving a fail-safe deadlock in the presence of permanent faults is preferred over allowing the circuit to continue operating erroneously [13], [15], [16].

Mazumder, Datta, Bodoh, and Sakib [17] present a comprehensive formal framework aimed at verifying and analyzing the vulnerabilities of redundancy-based error-resilient QDI NCL asynchronous circuits. The framework employs model checking techniques to systematically evaluate the fault-tolerance and security aspects of these circuits. Even though their study focuses on single-event upsets (SEUs) and single-event latch-ups (SELs), the work corroborates the importance of using formal methods to test for circuit weakness points, which effectively covers corner-case scenarios that might be overlooked by extensive fault-injection simulations.

**Fault injection analysis.** From a more experimental standpoint, many fault-injection tools have been tailored to examine QDI circuits. The Distributed Fault Injection Tool (DiFIT) [18] is a powerful tool that was used in many studies, that enabled the authors to provide a quantitative analysis by identifying the windows of vulnerability to Single-Event Transients (SETs) and assess the impact of specific parameter choices on circuit resilience [19], [20]. The tool was also extended to accommodate SAFs in [21], where the findings suggest that the choice of buffer type influences performance more significantly than the logic function, and that the implementation style of the logic affects the circuit's fault tolerance.

These studies offer important insights into the impact of faults on asynchronous circuits' behavior. They enable quantitative predictions based on a representative parameter set, reducing the need for exhaustive design space exploration and allowing progress toward the investigation of more complex circuits. However, as previously mentioned, simulations alone can fail to detect outliers/marginal cases.

**QDI circuits described in PRS.** QDI circuits can be modeled at various levels, with the Production Rule Set (PRS), introduced by Martin [3], being a widely used, low-level

representation that can be directly mapped to a CMOS transistor implementation. In [22], Jang and Martin propose efficient buffer reshuffling techniques to enhance SEU tolerance in QDI circuits. They model the circuits using Handshaking Expansion (HSE) and PRS notations, applying the doubling scheme at the HSE level to achieve more efficient PRS implementations.

More recently, both [2], and [19] use PRS for describing their target circuits in simulations experiments. The former proposed a formal framework that can provably exhaustively identify the susceptible windows where a QDI circuit is vulnerable to transient faults. However, the model of arbitrarily short pulses with arbitrarily short propagation delay they use as a worst-case assumption for SETs obviously cannot be applied to permanent faults. So our mission in this paper is to come up with a new modeling approach (plus formal proof) that is suitable for permanent faults and, based on that, identify the vulnerable windows similar to [2]. This requires substantially different techniques.

### III. MODEL

Towards the goal of proving correct our fault-discovery algorithm, we start with definitions of a circuit and an execution of a circuit. We rely on the model by Martin [3] with an extension that allows for delays and non-binary values [2], which we briefly recap here. We then extend the model for permanent faults (in the form of SAFs) and the definition of equivalent behavior on executions.

**Signals, values, and signal traces.** Signals represent the input and output ports of a circuit as well as the internal gate interconnection points/nets. The finite set $S$ holds all signals in a circuit. For example, a simple circuit comprising only an And gate may have signals $S = \{A, B, C\}$ where A and B are the gate's inputs and C is its output.

In a circuit, we distinguish input signals $\mathcal{I}$, local internal signals $\mathcal{L}$, and output signals $\mathcal{O}$ (sets $\mathcal{I}$, $\mathcal{L}$, and $\mathcal{O}$ are a partition of $S$, with possibly empty $\mathcal{I}$ or $\mathcal{L}$).

Signals have values assigned to them that may change over time. For a signal $s \in S$ we write $s(t)$, with $t \ge 0$, for the value of signal $s$ at time $t$. We call $t \to s(t)$ the signal trace, to distinguish it from the signal $s$. We restrict signal traces to contain only finitely many value-changes in each finite time interval, excluding Zeno behavior.

Since our model requires to capture non-binary, unstable, or metastable signal values, we resort to a three-valued set $B_X = \{0, X, 1\}$ of signal values, extending the Boolean signal values $B = \{0, 1\}$. Following Friedrichs, Függer, and Lenzen [23], we use $X$ as a potentially non-binary value that includes non-full-swing glitches, oscillations, metastable values, etc. For the semantics of Boolean formulas on $B_X$ we resort to the 3-valued Kleene logic, introduced in the context of hazards by Goto [24]. It is obtained by an isomorphism between $B_X$ with its logical operations and the real values $\{0, 0.5, 1\}$ with the classical algebraic interpretation of Boolean formulas with $\neg a \equiv 1-a$, $a \wedge b \equiv \min(a, b)$, and $a \vee b \equiv \max(a, b)$. We refer the reader to the work by Brzozowski, Ésik, and Iland [25] for a summary of multi-valued logics. We want to emphasize
<figure><img src="image_2.png" /><figcaption>Fig. 1. Circuit buf_MCE2 with a buffer and a Muller C-element. If not stated otherwise, we assume initial values of 0 for b and out and delays 10 and 0.5 for the buffer and the C-element, respectively.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. Circuit feedbackMCE2, similar to buf_MCE2 with a feedback including an inverter. If not stated otherwise, initial values and delays are as in buf_MCE2 with the inverter delay being 3, the buffer delay being 2, and the initial value of b1 being 0.</figcaption></figure>

that this semantics allows for logical masking, e.g., of an And-gate that has a metastable signal (X) at one input and a 0 at its other input. In fact $X \wedge 0 = 0$, while the same gate with its other input being 1 would potentially not mask the metastable input: $X \wedge 1 = X$. Please note that in this logic $X \vee \neg X = X$, which is different from the interpretation of X as either 0 or 1, for which this expression would evaluate to 1.

**Production rules and circuits.** Circuits will be specified in terms of production rules (PRs), i.e., guarded Boolean actions with delay. We use the notation $G \rightarrow s = v [d]$, where the guard G is a Boolean formula over S, $s \in \mathcal{L} \cup \mathcal{O}$ is the signal whose value will be set to $v \in \mathbf{B}$, and $d \in (0, \infty)$ is the propagation delay, i.e., the delay between the guard becoming true and the value of s being changed to v. Typically, a gate with output s will be modeled by two production rules, one for driving s to 1 and the other for driving it towards 0. For the example And-gate with delay 1, the production rules are $A \wedge B \rightarrow C = 1$ [1] and $\neg(A \wedge B) \rightarrow C = 0$ [1].

A circuit is specified by its signals, initial signal values, and set of production rules. We assume that all $s \in \mathcal{L} \cup \mathcal{O}$ are assigned initial values. Furthermore, for the production rules themselves we assume that: (i) For each signal s, there is at most one production rule that sets s to 1, and at most one that sets s to 0. This is to make sure that there is only gate driving a particular signal; an assumption that is plausible for standard digital circuits. (ii) Guards of production rules that set a signal s are mutually exclusive. This is to ensure that a signal is not driven to 0 and 1 at the same time; again being plausible for standard CMOS circuits where p- and n-stacks are designed to not drive the gate output at the same time.

Example circuits are shown in Figures 1 and 2. The production rules for the first circuit buf_MCE2 are

$$ 
\begin{array}{l@{\qquad}l@{\qquad}l}
a \wedge b \rightarrow out = 1 [0.5] & \text{and} & \neg a \wedge \neg b \rightarrow out = 0 [0.5] \\
b1 \rightarrow b = 1 [10] & \text{and} & \neg b1 \rightarrow b = 0 [10].
\end{array}
$$

The second circuit feedbackMCE2 has a buffer delay of 2 instead of 10, and the additional production rules,

$$ out \rightarrow b1 = 0 [3] \quad \text{and} \quad \neg out \rightarrow b1 = 1 [3]. $$

**Execution induced by a circuit.** In presence of input signal traces, circuits induce signal traces on local and output signals, the collection of which is called an *execution*. Intuitively, executions are generated by repeatedly checking the production rules' guards, and scheduling signal changes after the respective delays in case a guard evaluates to 1. While a guard that remains 1 until the scheduled action has taken place, behaves as expected, it remains to be specified what happens if a guard evaluates to 0 before the associated action is carried out. As in [2], we assume that in this case the scheduled action is canceled and the affected signal is immediately set to X (technically, after a small time $\epsilon > 0$). This value X is then propagated accordingly throughout the circuit; always with delay $\epsilon$. The faster than gate delay propagation accounts for the fact that non-binary signals may propagate faster than full- swing binary signals and is essentially a worst-case assumption.

Indeed, the semantics of an execution captures (i) generation of metastability and unstable signals by state-holding gates, (ii) generation of glitches by stateless, combinational gates, and (iii) propagation of such non-binary behavior.

We also give a formal definition of an *execution prefix until time* $T \ge 0$, *induced by the circuit and the input signal traces*, as a collection of signal trace prefixes until time $T$ for all local and output signals that is obtained by the algorithm from [2], referred to as *GenerateExecution* in the following:

1) **Initially.** All signals are set to their initial values as specified by the circuit (and the environment). Further, the current time $t = 0$, and the set of scheduled actions is empty.

2) **Handle unstable guards.** For each production rule whose action $s = b$, with $b \in \mathbf{B}$, currently being scheduled: if the rule's guard evaluates to 0 or X, and $s(t) \neq b$ (we say the guard is unstable), then remove the event from the scheduled events and set $s = X$. (generate-X)

3) **Apply actions.** For each action $s = v$, with $v \in \mathbf{B}_X$, scheduled for time $t$, set $s(t) = v$ and remove the action from the scheduled actions.

4) **Schedule actions.** For each production rule,

* if its guard evaluates to 1, schedule the rule's action $s = b$ to take place after the rule's delay $d$, i.e., at time $t+d$ (unless $s(t) = b$ already).

* if its guard evaluates to X and the rule's action is $s = b$ with $s(t) \neq b$, schedule the action $s = X$ for time $t + \epsilon$ (unless $s(t) = X$ already). (propagate-X)

5) **Advance.** Set time $t$ to the nearest future time at which an action is scheduled or an input signal switches value. If $t \ge T$, return the local and output signal traces until time $T$; otherwise continue with step 2.

As observed in [2, Lemma 1], for any non-Zeno input signal traces, the algorithm generates non-Zeno execution prefixes. In addition, the algorithm is causal in the sense that input traces that are identical until time $T$ lead to execution prefixes that are identical until time $T$. This ensures the well-defined notion of a limit for $T \to \infty$, and thus the notion of an infinite execution.

Figure 3 shows three example execution prefixes until time 15 induced by circuit buf_MCE2 and signal traces for the
circuit's inputs *a* and *b1*. Signal trace *a* is a delayed, periodic clock signal, *b1* is a single rising transition at different times for the two execution prefixes. In all executions, this transition results in a delayed transition at *b*. While in the top execution, the transition leads to setting the C-element to 1, the same transition at a different time (shown in the middle), leads to the guard evaluation *a* ∧ *b* = 1 at time 10.6, scheduling the action of setting the C-element output to 1 at time 10.6 + 0.5 = 11.1. However, at time 11.0, the same guard evaluates to 0, because of *a* = 0. This results in an unstable guard at time 11, leading to a metastable output *X* of the C-element (marked in red in the figure) due to rule (generate-X) of the algorithm.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Example executions of circuit buf\_MCE2. The input signal is a delayed periodic clock signal. Top: Rising input transition of input b1 at time 0.1. Middle: Same as above, but with the input transition at time 0.6. Signal value X is marked in red with a line at value 0.5. Bottom: Analogous to top case, with transition at time 1.1.</figcaption></figure>

One observes that the C-element remains metastable forever in the simulation. This is due to the fact that none of the C-element's guards evaluates to 1 again, which would overwrite *X* with a stable signal. We do not model the fact that metastability may stabilize probabilistically over time, making the model a worst-case model. Finally, the execution prefix at the bottom is for an input transition at time 1.1 and seen to not result in a non-binary value.

**Stuck-at faults, states, regions, and equivalence of faults.**
We next extend executions to include SAFs. Formally, an SAF is of either type SA0 or SA1 occurring at a circuit's signal *s* at a time *t* ≥ 0. An execution induced by a circuit, input signal traces, and an SAF is obtained by extending Algorithm *GenerateExecution*, by scheduling an additional event of *s* being set to 0 for SA0 and to 1 for SA1 at time *t*, and not scheduling anymore events for *s* after time *t*. While we focus on single SAFs in this work, the definition is generalized to multiple faults in a straightforward way. For simplicity, we refer to the adapted algorithm with SAFs as *GenerateExecution*, too.

Given a circuit and a signal $s \in S$, the effect of an SAF at some time $t$ is a priori different from an SAF of the same

type at any time $t' \neq t$. Intuitively, when injecting faults into a circuit, faults that lead to the same phenomena are considered the same, though.

We capture this intuition with the following definition of equivalence between executions. Fix an execution *e* and let 0, τ₀, τ₁, ... be the times at which any of the circuit's signals changes in *e*. We call the collection of all the circuit's signal values *s*(*t*) the circuit's state at time *t*. Further, we call the sequence of states at times 0, τ₀, τ₁, ... the sequence of circuit states and [0, τ₀), [τ₀, τ₁), ... the value regions of *e* [2]. Two executions *e* and *e'* induced by the same circuit, but potentially different input signals and faults are said to be equivalent if the sequence of circuit states is the same in both executions. We denote this equivalence with *e* ~ *e*'.

For example, for a circuit with a single input signal *i*, an output signal *o*, and a buffer from *i* to *o*, initial value *o* (0) = 0 and input trace *i* (*t*) = 0, the executions *e* and *e'* induced by the circuit, the input signal, and the SA1 faults on *i* at times *t* = 0.5 and *t*' = 1.0, respectively, fulfill *e* ~ ~*e*' since their sequence of states (*i*, *o*) is (0, 0), (1, 0), (1, 1) in both executions. If the circuit and the input signal traces are clear from the context, we say the two faults are equivalent. We write *F* ~ ~*F*′ to denote that *F* and *F*′ are equivalent.

In Figure 3, viewing the rising transitions of signal b1 as SA1 faults of the input signal b1(*t*) = 0, the faults in the top and bottom executions are examples for equivalent faults, while the top and the middle are examples for non-equivalent faults.

IV. RESULTS

A. Python-based tool for stuck-at fault-injection

We extended the available Python implementation of El Shehaby, Függer, and Steininger [2] from injecting transient faults to stuck-at faults. We have further extended plotting and reporting features, allowing us to sweep SAFs for signals in (small) equidistant time steps. Moreover, we have expanded the capabilities of the tool to accommodate larger QDI circuits with pipeline stages and logic functions between stages. Instead of the specification of the input signals in terms of transitions, which is tedious and error-prone for multi-rail inputs, we have introduced high-level tokens. Each token is comprised of a data value for each input of the circuit, which are in turn broken down to their corresponding dual-rail encodings and appointed to/coupled with synthesized single-rail signals in the circuit. Completion detection for the 4-phase communication protocol controls the token flow through the pipeline, with NULL tokens (spacers) inserted between every two DATA tokens. These new features greatly ease the testing and analysis of more complex, larger-scale QDI circuits, such as those presented in Section IV-D.

An example of a sweep of the circuit *feedbackMCE2* for stuck-at fault tolerance is shown in Figure 4. While arbitrary properties can be checked on the resulting sequence of states, we focus on the occurrence of non-binary values in this work: Figure 4 marks the times where an SA0 fault potentially leads to a non-binary value at one of its so-called monitored signals (until a predefined cutoff-time) in red, and those for
SA1 faults in green. In the example, the output *out* has been chosen as a monitored signal. The focus to non-binary faults at certain monitored signals is motivated by the fact that non-binary behavior is a particularly undesired behavior: while fault-detection circuits may detect binary-valued bad states such as deadlocks, non-binary faults like metastability and glitches may potentially upset the detection circuit.

From Figure 4, we observe that the characterization of susceptible windows for transient faults, established in [2, Theorem 2] does not hold for stuck-at faults: While for transient faults any value region can be split into a (potentially empty) left part that is non-susceptible and a (potentially empty) right part that is susceptible, this property does not apply to permanent faults. As an example, consider signal $b1$ within the value region [12.5, 19), which clearly constitutes a susceptible window that is neither aligned to the left nor to the right border.

In fact, within one value region there can be several switches between susceptible and non-susceptible windows, as demonstrated by the 5 susceptible windows for signal $b1$ within the value region [0, 10) in Figure 5.

The observation is easily generalized to arbitrarily many (increasing the number of clock pulses and the buffer delay) and arbitrarily short (decreasing the C-Element delay) susceptible windows within a single value region. This demonstrates a significant limitation of a fault-injection algorithm that simply performs equidistant faults-injections: for any fixed sweeping step-size, there exists a circuit that has arbitrarily many regions that are too small to be found by the algorithm.

## B. Equivalence for stuck-at faults

Towards the goal of an improved fault-injection algorithm, we next show central properties of stuck-at faults.

We say an action $a$ directly causes action $b$ in an execution if $a$ changes the value of a guard, such that $b$ is scheduled. We say an action $a$ causes an action $b$ if there is a chain of actions that starts with $a$ and ends with $b$, and for successive actions $a'$, $b'$, action $a'$ directly causes $b'$.

**Lemma 1.** Any action in an execution induced by a circuit, inputs, and a stuck-at fault is either caused by an input action (an input transition or an initial value) or the fault (setting the value to the stuck-at value).

*Proof.* The proof is by induction on the sequence of events generated by Algorithm *GenerateExecution* and observing that an action is only scheduled if a guard's evaluation changes (Steps 2 and 4). The latter is only due to previously scheduled actions being applied (Steps 2 and 3). □

In the following, let $[\tau, \tau')$ be a subset of a value region of a fault-free execution (prefix) $g$ induced by a circuit and some input signal traces (the golden run). We refer to such a subset as a region. A maximal region is a value region. Let $F$ and $F'$ be faults of the same type at the same signal $s$ at times $t$ and $t' \ge t$, with $t, t' \in (\tau, \tau')$, and denote by $e$ and $e'$ the executions induced by the circuit, the input signal traces, and the respective faults ($F$ for $e$ and $F'$ for $e'$).

**Lemma 2.** Assume in $e$, within $(\tau, \tau')$ the circuit's state does not change. Then:

1) The sequence of circuit states is the same until time $\tau'$ for $e$ and $e'$.

2) Let $S$ be the set of actions scheduled when the algorithm reaches or passes time $\tau'$ in execution $e$. Likewise let $S'$ be the set of actions scheduled when the algorithm reaches or passes time $\tau'$ in execution $e'$. Then an action $a$ is in $S$ if and only if either the same action $a$ is in $S'$ or there is an $a'$ in $S'$, identical to $a$, except for its time shifted by $t' - t$. In the former case, $a$ is caused by input actions and in the latter case, $a$ and $a'$ are (directly) caused by $F$ and $F'$, respectively.

*Proof.* By equivalence of all execution prefixes $e, e'$, and $g$ until before time $t$, we have that the lemma's statements hold until then. By definition of $[\tau, \tau')$ as a region, and the equivalence of the execution prefixes of $e$ and $g$ until time $t$, we have that the circuit's state $c$ in execution $e$ within $(\tau, t)$ is constant. After the occurrence of fault $F$ at time $t$, the state changes to some $\tilde{c}$, and remains constant until time $\tau'$ by the lemma's assumption.

By definition of a region, in execution $e'$, no state change occurs within $(\tau, t')$. Thus the state is equal to $c$ during this time. Further, at time $t'$, by the algorithm, the circuit's state changes to $\tilde{c}$. The state remains constant in $e'$ until time $\tau'$ by the following argument: A state change due to an action scheduled before time $t'$ contradicts the definition of $[\tau, \tau')$ as a region. Further, any state change due to an action directly caused by $F'$ implies the existence of an identical action (except for a time shift $t' - t$) directly caused by $F$. However, if such an action must occur at a time greater than $\tau'$ in $e$ by the lemma's assumption. From this follows that the action in $e'$ occurs at a time greater than $\tau' + t' - t > \tau'$. Thus the circuit's state is constant within $[t', \tau')$ in $e'$. This concludes the proof of the lemma's first statement.

The second statement follows from the fact that identical actions are scheduled at time $\tau$ in both $e$ and $e'$, and newly scheduled actions are identical (because of identical circuit states), except for a time difference of $t' - t$ for actions caused by $F$ and $F'$. □

Let $T > 0$ be the length of an execution prefix. We next define the set of affected points $A$ for a fault at signal $s$ and time $x$ inductively as the smallest (with respect to inclusion) set $A$ that fulfills:

* It is $(s, x) \in A$.

* If $(s', x') \in A$ and $s'$ appears in a guard with output signal $s''$ and delay $d$, then $(s'', x' + d) \in A$ if $x' + d \le T$.

Intuitively, $A$ contains the points (signals and times) at which a fault may cause new actions. Clearly, $A$ is of finite, though potentially large, size: assuming a minimal production rule delay of $d_{min} > 0$, we have $|A| \le |S|^{T/d_{min}}$. Indeed, exponentially large $A$ can be constructed from circuits with feedback-loops.

Figure 6 shows an example of an execution prefix of length $T = 21$ for the circuit `buf_MCE2`. All affected points for a fault at victim signal $b1$ at time 0 are marked in blue.
<figure><img src="image_5.png" /><figcaption>Fig. 4. Execution of circuit *feedbackMCE2*. Susceptible regions of time where an SA0 fault leads to a non-binary value of the monitored signal *out* are marked in red and those for SA1 faults are marked in green.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5. Zebra-stripe-shaped susceptible windows within a value region for circuit *buf_MCE2*. Each window has length 0.5, equal to the C-element delay. Monitored signal is *out*.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6. Affected points for an execution prefix induced by circuit *buf_MCE2* for a fault at signal *b1* at time 0 marked in blue. The set *A* of affected points is given by $A = \{(b1, 0), (b, 10), (out, 10.5)\}$.</figcaption></figure>

For an execution *e* induced by the circuit, some inputs, and a fault at time *t*, and *A* being the set of affected points for the fault, we define $\Delta(A) \in \mathbb{R}_0^+$ as the minimum over all times $\tau' - x > 0$ where *x* is a time of a point in *A*, and [$\tau, \tau'$] is either the (unique) value region of *e* which contains time *t* or the (unique) value region of execution *g* induced by the same circuits and inputs, but without a fault (i.e., the golden run). By the finiteness of *A*, the minimum $\Delta(A) > 0$ is well-defined. For the example in Figure 6, one obtains $\Delta(A) = \min\{10, 1, 0.5\} = 0.5$ as the closest distance of an affected point to a right boundary of a value region in the fault-free shown execution and the execution with an initial stuck-at fault at signal *b1* (see Figure 1 top).

We are now in the position to prove our main result for the equivalence of faults.

**Theorem 1.** Let *e* be an execution induced by a circuit, inputs, and a fault *F*. Let *s* and *t* be victim signal and time of fault *F*. Then, for any fault *F'* that has the same type as *F* and occurs

at signal *s* and a time *t'* ∈ [*t*, *t* + Δ(*A*)), it is *F* ~ *F*'.

*Proof.* Let *e'* be the execution induced by the circuit, inputs, and *F*'. Further, let *g* be the golden run (the fault-free execution induced just by the circuit and the inputs). We will show that the sequence of circuit states is the same in *e* and *e*', i.e., *e* ~ *e*'.

The proof is by induction on the actions scheduled and applied by the Algorithm *GenerateExecution* for execution *e*, showing the statement of Lemma 2 for arbitrary times $\tau'$, without the restriction of $\tau'$ being an end of a region and the lemma's assumption of no state change until $\tau'$ in *e*.

*Base case.* With *t* being the time of fault *F*, set *A* being the affected points for *F*, let $\tau' = t + \Delta(A)$. One observes that the assumption of Lemma 2 is fulfilled. It follows that the theorem holds for prefixes until time $\tau'$.

*Induction step.* Let *a* be the earliest action that was applied in *e*, say at time *x*, for which the statement does not hold. By the induction hypothesis, the circuit's states after the previous corresponding actions, say *b* and $b'$, in *e* and $e'$, are the time, say *c*, and corresponding actions are scheduled in both executions. This implied that there is an action $a'$ corresponding to *a*. By Lemma 1, action $a'$ is either caused by an input or the fault.

If the action is caused by an input, then *a* is also caused by an input, and by the induction hypothesis, scheduled for time *x*. Since $a'$ was not applied, the state in $e'$ just before time *x* must have been different from *c*. This can only be the case if *b* and $b'$ were both caused by a fault and thus occur at shifted times. By the induction hypothesis, if *b* occurs at a time *y*, then $b'$ occurs at time $y + (t' - t)$; that latter of which is larger than *x* for the state in $e'$ to be different from *c* at time *x*. However, by definition of $\Delta$ as a minimum and the fact that *A* covers signals and times at which actions caused by faults may occur, it is $\Delta(A) \le x - y$. Further, by the theorem's assumption, $t' \le t + \Delta(A)$; a contradiction to the initial assumption.

If the action is caused by the fault $F'$, then *a* is caused by the fault *F*, and by the induction hypothesis scheduled for time $x+t'-t$. 9By analogous arguments as in the previous case, one concludes that both actions are applied since both executions are in the same state just before times *x* (for *e*) and $x+t'-t$ (for $e'$). Again, the main argument is the choice of $t' - t \le \Delta(A)$, which prevents actions to be applied within the duration $t' - t$ in execution $e'$.

Since the algorithm is deterministic, and circuits are in identical states for corresponding actions, they schedule corre-
sponding actions (at identical times for those caused by inputs and at shifted times for those caused by faults).

The theorem's statement follows. ☐

### C. Two algorithms: Delta and DeltaMask

We present two algorithms that are obtained as a result from the analysis before.

**A basic algorithm: Delta.** Theorem 1 immediately leads to an algorithm to induce faults in a provably complete way. If we inject a fault at signal *s* and time *t*, and compute the set of affected points *A* for the fault, the theorem guarantees that all faults at the same signal within times [*t*, *t* + Δ(*A*)] are equivalent. Instead of sweeping with a fixed or randomly chosen time-step, we can thus simply advance by Δ(*A*) being sure not to overlook a fault with a new behavior. The resulting Algorithm 1 (Delta) is shown below.

**Algorithm 1 Delta**

1: **Inputs:** signal *s* and time *T*

2: *t* ← 0

3: susceptible_windows ← {}

4: **while** *t* < *T* **do**

5:     *A* ← affected point set for fault at signal *s* and time *t*

6:     Injected fault at signal *s* and time *t* + Δ(*A*)/2

7:     **if** susceptible to fault **then**

8:         add [*t*, *t* + Δ(*A*)] to susceptible_windows

9:     **end if**

10:     *t* ← *t* + Δ(*A*)

11: **end while**

12: **return** susceptible_windows

The set *A* of affected points in line 5 is computed via DFS:

**Algorithm 2 findDelta(s, t)**

1: **if** *t* > *T* **then** ▷ check if end of execution prefix

2:     **return** {}

3: **end if**

4:     points ← {(s, t)} ▷ add self

5:     **for** rules *G* → *s'* = *b* [*d*] with *s* in *G* **do** ▷ recurse

6:         points ← points ∪ findDelta(*s'*, *t* + *d*)

7:     **end for**

8:     **return** points

Algorithm 1 (Delta) is highly parallelizable. First, it can be run in parallel for each signal and fault-type. Second, parallelization within a signal is possible, by executing the algorithm in parallel with *t* and *T* being such that [*t*, *t* + *T*) is a single value region. This is possible since the algorithm necessarily injects at the beginning of a value region (the step from *t* to *t* + Δ(*A*) never crosses a value region boundary).

Finally, note that in this work we define a fault to be susceptible if it generates an *X* at a circuit output. However, the result of equivalent faults, and thus the algorithm, readily generalizes to other properties on the sequence of circuit states.

**An improved algorithm: DeltaMask.** Figure 7 (left) shows the affected points for the circuit *feedbackMCE2*. It is clearly

<figure><img src="image_8.png" /><figcaption>Fig. 7. Affected points (marked in blue) for an execution prefix induced by circuit *feedbackMCE2* for a fault at signal *a* at time 0. Left: Points obtained by Algorithm 1 (Delta). Right: The remaining two points obtained by Algorithm *DeltaMask* for the same execution and fault.</figcaption></figure>

visible that the feedback in the circuit leads to many affected points, with *A* growing with an increased prefix length.

Indeed, one observes from the proof of Theorem 1 that the proof relies on set *A* for a fault *F* including all potential signals and times where a signal transition may be caused by fault *F*. This implies that we may safely remove affected points (*s*, *t*) from the set *A*, for which we are sure that an action at signal *s* and time *t* does not lead to a newly scheduled action. We call the potentially smaller set of these points the set of affected points with masking *A*<sub>mask</sub>.

Towards, a formal definition of *A*<sub>mask</sub>, let *e* be the execution with fault *F*, and *g* the execution without a fault (the golden run). For a signal *s* and an execution *e* we write *s*<sub>*e*</sub> to denote *s* in execution *e*. We then define *A*<sub>mask</sub> as the result of *findDeltaMask*(*s*, *t*) where *s* and *t* are the signal and time of fault *F*.

**Algorithm 3 findDeltaMask(s, t)**

1: **if** *t* > *T* **then** ▷ check if end of execution prefix

2:     **return** {}

3: **end if**

4:     points ← {(s, t)} ▷ add self

5:     **if** *s*<sub>*e*</sub>(*t*) = *X* **then** ▷ non-binary value was generated

6:         **return** points

7: **end if**

8:     **if** no change of *s*<sub>*e*</sub> at time *t* **then** ▷ masking occurred

9:         **return** points

10: **end if**
11: **for** rules *G* → *s'* = *b* [*d*] with *s* in *G* **do** ▷ recurse

12:     points ← points ∪ findDeltaMask(*s'*, *t* + *d*)

13: **end for**

14: **return** points

By the above observation and with a proof analogous to the proof of Theorem 1 we obtain:

**Theorem 2.** Let *e* be an execution induced by a circuit, inputs, and a fault *F*. Let *s* and *t* be the signal and time of fault *F*. Then, for any fault *F'* that has the same type as *F* and occurs at the signal *s* and a time *t'* ∈ [*t*, *t* + Δ(*A*<sub>mask</sub>)), it is *F* ~ *F*'.

The resulting Algorithm *DeltaMask* is analogous to Algorithm 1 (Delta) except for replacing set *A* by set *A*<sub>mask</sub>, and thus function *findDelta* by *findDeltaMask*. For the complexity, one has that *A*<sub>mask</sub> is about the number of transitions in a faulty execution.
## D. Implementation of the algorithm

In the following we discuss an implementation of both algorithms in Python, publicly available at [26].

At the heart of our implementation is the `checkSA` function that takes as arguments the circuit (including signals), an execution prefix of a circuit simulated without faults (golden run), the type of the stuck-at faults to inject, a set of monitored signals that are tested for X values, and victim signals at which faults are injected. Additional parameters allow one to control sink and source delays that feed the QDI circuit-under-test, and the tokens to be pushed through the QDI circuit.

The function `checkSA` iterates over all victim signals and all value regions of the golden run. For a certain victim signal and a value region, it does so, starting at the lower value region boundary until it reaches the top value region boundary. Within the regions, it iteratively injects a fault and with this result and the golden run computes the duration within which the faults are equivalent, and then advances to right after this duration. Via an argument, one can choose between the basic Algorithm 1 (Delta) and the improved Algorithm DeltaMask.

For the basic algorithm the `findDelta` function is computed via DFS as in Algorithm 2. However, for optimization, the function directly returns the duration $\Delta(A)$, evaluated on the respective subset of affected points, rather than the subset of affected points. Results of recursive calls are simply merged with min rather than with $\cup$. For purposes of visualization, though, we return the affected points, if needed.

For the improved algorithm, we use `findDeltaMask` (Algorithm 3) instead of `findDelta`. As for the implementation of `findDelta`, we directly compute $\Delta(A_{mask})$ and combine it via min, rather than returning affected points. The latter again is available for visualization, though.

Finally, the tool has options to return susceptible regions as objects for direct processing in Python or graphically as `svg` files with susceptible windows (e.g., Figure 4) and affected points (e.g., Figure 7).

## E. Benchmarks

To evaluate our approach, we utilize two example circuits with configurable data path widths. These circuits employ dual-rail encoding with DIMS gates for combinational logic and weak condition half buffers for pipelining.

The first circuit is a $n \times n$-bit unsigned multiplier implemented as a linear pipeline with $n$ pipeline buffers. Figure 8 visualizes the data path of this multiplier. Pipeline buffers are marked gray. The functionality implemented by the combinational logic (ellipses) is given as an equation above the respective stages.

The second circuit is a simple ALU. As shown by the data flow graph in Figure 9, here we have a slightly more complex control path with forks, demultiplexers and a merge operation. The width of the inputs $a$ and $b$ is again configurable, while the single-bit signals $c_0$ and $c_1$ select the actual operation.

The circuits are synthesized using `pypr [27]` from high-level descriptions of the modules. This process already yields production rule sets, albeit in a different format than the one

used by SeAL [26]. For that purpose, we translate the output of `pypr` into a SeAL-compatible representation, enabling a seamless integration between the two tools.

All simulations were done on a Lenovo ThinkPad (Intel Core i5, 8 GB) running Ubuntu 24.04 and Python 3.12.3. Table I shows, for each synthesized instance of the circuits, the total count of signals, production rules (PRs), and transitions in a fault-free execution. It also shows the time taken to mark the susceptible windows against SA0 and SA1 faults in victim signal `ack_in` for a selected simulated time window.

<table><caption>TABLE I
SUMMARY OF CIRCUIT PROPERTIES AND CHECK RUNTIME</caption><thead><tr><th></th><th># signals</th><th># PRs</th><th># transitions</th><th>marking time</th></tr></thead><tbody><tr><td>ALU 4-bit</td><td>296</td><td>550</td><td>12556</td><td>195 s (3.25 min)</td></tr><tr><td>ALU 8-bit</td><td>600</td><td>1126</td><td>31008</td><td>628 s (10.5 min)</td></tr><tr><td>ALU 16-bit</td><td>1208</td><td>2278</td><td>77982</td><td>1958 s (32.6 min)</td></tr><tr><td>MUL 4-bit</td><td>449</td><td>864</td><td>49544</td><td>353 s (5.8 min)</td></tr><tr><td>MUL 8-bit</td><td>2115</td><td>4164</td><td>389943</td><td>15444 s (4.29 h)</td></tr><tr><td>MUL 16-bit</td><td>9091</td><td>18052</td><td>1664019</td><td>- (> 10 h)</td></tr></tbody></table>

For the adder the steps from 4-bit towards 8 and 16-bit implementations each come with, roughly, a duplication in the number of signals and production rules. The number of transitions increases by a factor of roughly 2.4, while the computation time increases by slightly more than a factor of 3 (slightly higher than linear). This indicates good scalability.

For the multiplier the situation is a bit different: While the scaling in number of signals and production rules stays roughly linear from the 4 to the 16-bit variant, the transition count and the computation time do not follow a simple linear pattern. It appears that the greater complexity and most notably the additional feedback loops make the problem computationally harder. For the 16-bit multiplier the computation did not finish within 10 hours. However, the times listed in the table do not leverage parallelization.

## V. CONCLUSION & FUTURE WORK

Based on a notion of equivalence among faults, we have derived a fault-injection algorithm and demonstrated that one can efficiently test circuits expressed as production rules for their sensitivity to stuck-at faults. The algorithm is potentially faster than equidistant fault injection and, most notably, guarantees to find even the smallest susceptible window. We have shown in benchmarks that the algorithm performs well for non-toy QDI circuits. The scaling still needs some improvement.

A direction of future research is therefore to show lower and upper complexity bounds and further improve the algorithms by replacing the global, circuit-wide signal changes that determine the boundaries of the value regions with local value regions per gate. This results in a redefinition of $\Delta$ and potentially larger step sizes in the algorithms. When doing so, care has to be taken, though, for the cases that involve signal $X$, which propagates arbitrarily fast through the circuit. A further interesting direction is to include this approach into existing circuit design tools that rely on production rules.
<figure><img src="image_9.png" /><figcaption>Fig. 8. $n \times n$ bit unsigned multiplication circuit with $n$ pipeline buffers ($x[i]$ denotes the access to the $i^{th}$ bit of signal $x$, $x[i]$ & $y$ denotes a masking operation, where a logical AND operation between the bit $x[i]$ and each bit in $y$ is performed, the operators $\gg$ and $\ll$ denote a logical right and left shift, respectively)</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 9. ALU data flow circuit with four operations</figcaption></figure>

REFERENCES

[1] R. El Shehaby and A. Steininger, "On the Effects of Permanent Faults in QDI Circuits – A Quantitative Perspective," in *Proceedings. The 38th IEEE International Conference on Computer Design*. IEEE, 2020.

[2] R. E. Shehaby, M. Függer, and A. Steininger, "On the susceptibility of qdi circuits to transient faults," in *International Conference on Formal Modeling and Analysis of Timed Systems*. Springer, 2023, pp. 69–85.

[3] A. J. Martin, "Compiling communicating processes into delay-insensitive vlsi circuits," *Distributed computing*, vol. 1, no. 4, pp. 226–234, 1986.

[4] S. Al-Arian and D. Agrawal, "Physical failures and fault models of cmos circuits," *IEEE transactions on circuits and systems*, vol. 34, no. 3, pp. 269–279, 1987.

[5] E. J. McCluskey and C.-W. Tseng, "Stuck-fault tests vs. actual defects," in *Proceedings International Test Conference 2000 (IEEE Cat. No. 00CH37159)*. IEEE, 2000, pp. 336–342.

[6] M. O. Simsir, A. Bhoj, and N. K. Jha, "Fault modeling for finfet circuits," in *2010 IEEE/ACM International Symposium on Nanoscale Architectures*. IEEE, 2010, pp. 41–46.

[7] H. Hulgaard, S. M. Burns, and G. Borriello, "Testing asynchronous circuits: A survey," *Integration, the VLSI journal*, vol. 19, no. 3, pp. 111–131, 1995.

[8] A. J. Martin and P. J. Hazewindus, "Testing delay-insensitive circuits," California Institute of Technology Pasadena Department of Computer Science, Tech. Rep., 1990.

[9] P. Liden and P. Dahlgren, "Coverage of transistor-level and gate-level stuck-at-faults in cmos checkers," in *Proceedings of ISCAS'95 International Symposium on Circuits and Systems*, vol. 3. IEEE, 1995, pp. 2124–2127.

[10] P. A. Beerel, CAD tools for the synthesis, verification, and testability of *robust asynchronous circuits*. Stanford University, 1994.

[11] M. J. Liebelt and N. Burgess, "Detecting exitory stuck-at faults in semimodular asynchronous circuits," *IEEE transactions on computers*, vol. 48, no. 4, pp. 442–448, 1999.

[12] M. Roncken and E. Bruls, "Test quality of asynchronous circuits: a defect-oriented evaluation," in *Proceedings International Test Conference 1996. Test and Design Validity*, 1996, pp. 205–214.

[13] C. LaFrieda and R. Manohar, "Fault detection and isolation techniques for quasi delay-insensitive circuits," in *International Conference on Dependable Systems and Networks, 2004*. IEEE, 2004, pp. 41–50.

[14] M. Zamani, H. Pedram, and F. Lombardi, "Templated-based asynchronous design for testable and fail-safe operation," in *2011 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems*, 2011, pp. 146–152.

[15] S. J. Piestrak and T. Nanya, "Towards totally self-checking delay-insensitive systems," in *Twenty-Fifth International Symposium on Fault-Tolerant Computing. Digest of Papers*. IEEE, 1995, pp. 228–237.

[16] S. Peng and R. Manohar, "Efficient failure detection in pipelined asynchronous circuits," in *20th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT'05)*. IEEE, 2005, pp. 484–493.

[17] D. Mazumder, M. Datta, A. C. Bodoh, and A. A. Sakib, "A scalable formal framework for the verification and vulnerability analysis of redundancy-based error-resilient null convention logic asynchronous circuits," *Journal of Low Power Electronics and Applications*, vol. 14, no. 1, p. 5, 2024.

[18] P. Behal, F. Huemer, R. Najvirt, and A. Steininger, "An Automated Setup for Large-Scale Simulation-Based Fault-Injection Experiments on Asynchronous Digital Circuits," in *2021 24th Euromicro Conference on Digital System Design (DSD)*. IEEE, 2021, pp. 541–548.

[19] P. Behal, F. Huemer, R. Najvirt, A. Steininger, and Z. Tabassam, "Towards Explaining the Fault Sensitivity of Different QDI Pipeline Styles," in *2021 27th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC)*. IEEE, 2021, pp. 25–33.

[20] Z. Tabassam and A. Steininger, "Set hardened derivatives of qdi buffer template," in *2022 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT)*. IEEE, 2022, pp. 1–6.

[21] R. El Shehaby and A. Steininger, "Study and comparison of qdi pipeline components' sensitivity to permanent faults," in *2022 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT)*. IEEE, 2022, pp. 1–6.

[22] W. Jang and A. J. Martin, "Seu-tolerant qdi circuits [quasi delay-insensitive asynchronous circuits]," in *11th IEEE International Symposium on Asynchronous Circuits and Systems*. IEEE, 2005, pp. 156–165.

[23] S. Friedrichs, M. Függer, and C. Lenzen, "Metastability-containing circuits," *IEEE Transactions on Computers*, vol. 67, no. 8, pp. 1167–1183, 2018.

[24] M. Goto, "Application of three-valued logic to construct the theory of relay networks," in *Proc. Joint Meeting IEE, IECE, and I. of Illum. E. of Japan*, 1948.

[25] J. A. Brzozowski, Z. Ésik, and Y. Iland, "Algebras for hazard detection," in *Proceedings 31st IEEE International Symposium on Multiple-Valued Logic*. IEEE, 2001, pp. 3–12.

[26] R. E. Shehaby, M. Függer, and A. Steininger, "Sensitivity analyzer for asynchronous logic (SeAL)," https://github.com/mfuegger/SeAL, 2023.

[27] F. Huemer, "Python Production Rules Package (pypr)," https://gitlab.eecs.tuwien.ac.at/eda/pypr, 2023.