ResiLogic: Leveraging Composability and Diversity to Design Fault and Intrusion Resilient Chips
Ahmad T. Sheikh Ali Shoker Suhaib A. Fahmy Paulo Esteves-Verissimo











: Leveraging Composability and Diversity to Design Fault and Intrusion Resilient Chips
    Ahmad T. Sheikh, Ali Shoker, Suhaib A. Fahmy and Paulo Esteves-Verissimo
CEMSE Division, King Abdullah University of Science and Technology (KAUST)

Thuwal 23955-6900, Kingdom of Saudi Arabia

{ahmad.sheikh, ali.shoker, suhaib.fahmy, paulo.verissimo{@kaust.edu.sa}}
    September 9, 2024
=============================================================================================================================================================================================================================================================================








§ ABSTRACT 
A long-standing challenge is the design of chips resilient to faults and glitches. Both fine-grained gate diversity and coarse-grained modular redundancy have been used in the past. However, these approaches have not been well-studied under other threat models where some stakeholders in the supply chain are untrusted. Increasing digital sovereignty tensions raise concerns regarding the use of foreign off-the-shelf tools and IPs, or off-sourcing fabrication, driving research into the design of resilient chips under this threat model. This paper addresses a threat model considering three pertinent attacks to resilience: distribution, zonal, and compound attacks. To mitigate these attacks, we introduce the framework that exploits Diversity by Composability: constructing diverse circuits composed of smaller diverse ones by design. This gives designer the capability to create circuits at  design time without requiring extra redundancy in space or cost. Using this approach at different levels of granularity is shown to improve the resilience of circuit design in against the three considered attacks by a factor of five.
Additionally, we also make a case to show how E-Graphs can be utilized to generate diverse circuits under given rewrite rules.




Chip Resilience, Hardware Diversity, TMR, Fault and Intrusion Tolerance (FIT), E-Graphs 







§ INTRODUCTION


Integrated Circuit (IC) development is a pressing challenge in the modern digital ecosystem. The huge supply chain and toolchain across the development pipeline involves a large number of known and unknown stakeholders and dependencies. This has compounded the development complexity and results in higher likelihood of unintentional faults, glitches, bugs, etc. <cit.> and other intentional intrusions with malicious intent <cit.>. While resilience to unintentional benign faults has been well studied and mitigated in the literature, mainly using hardening and redundancy <cit.>, the case of resilience against malicious actors (e.g., vendors and foundries) has often been ignored. 
With nation states aligning their priorities to develop local semiconductor manufacturing, technological excellence, and bridge recent global chip shortages <cit.>, the quest for new resilience methods to withstand untrusted stakeholders is regaining momentum.



Our work is the first that studies chip design resiliency assuming a threat model in which vendors and silicon fabs may be untrusted.
Typical chip design can be more productive when the designer relies on available off-the-shelf tools and libraries from different vendors and then sends the design to a silicon fab for manufacturing. The premise is that the vendors and fab are trusted, both ethically and technically. With the recent digital sovereignty tensions, the former is not guaranteed and hardly measurable, while the latter has been shown to be unrealistic with such a complex development process, incurring too many dependencies on third party tools, libraries, and sometime open source resources <cit.>. Our analysis shows that a design is highly prone to three potential attacks of relevance to resiliency (as outlined in Section <ref>): Distribution attacks (supply chain trojans and backdoors), Zonal attacks (using electromagnetic or Laser beam interference), and Compound attacks (simultaneous Distribution and Zonal attacks).

Redundancy in space is a fundamental resilience approach that is used to mask faults and intrusions <cit.>. Two main directions for redundancy at different granularity are studied in state of the art chip design. The first is fine-grained, where redundancy is applied at the logic gate level <cit.>. This approach aims at diversifying the logic circuit design through adding various basic logic gates, e.g., AND and Inverter. While this approach has been shown to be effective, e.g., increasing design resilience up to 90% under (benign) faults <cit.>, it is designed to be incorporated in the vendor's IP libraries and tools, where the designer has little control. The designer must either  create libraries (costly and unproductive) or live under the mercy of the vendor and fab (who may collude). The second approach is course-gained, following the Triple Modular Redundancy <cit.> (TMR) style replication that requires three identical copies of a circuit followed by a majority voter to mask the faulty one. However, this works well as long as a minority of circuits are non-faulty and assuming the independence of failures, i.e., the absence of Common Mode Failures (CMF, henceforth); this is often considered a hard assumption <cit.>. 
To demonstrate this, we conducted an experiment that shows, in Figure <ref>, that the average failure probability of TMR (red curve) is around 70%, even when used together with the aforementioned fine-grained design approach <cit.> (see more details in Section <ref>). 

In this paper, we bridge this gap by introducing , a framework for building resilient diversified integrated circuits.
To do this, combines course-grained (TMR) style replication with fine-grained gate-level redundancy that uses the concept of diversity by composability. This concept leverages the properties of higher level composable logic circuits, i.e., circuits whose modular structure is composed of smaller linked circuits. 
Since various circuits are composable by nature, e.g., N-bit Adder, N-bit Multiplier, Vector Unit, Systolic Array, etc. <cit.>, this makes the approach feasible for many modern applications (see Section <ref> for details). 






Generation of diverse circuits using E-Graphs <cit.> is also proposed, that leverages powerful equality saturation technique to implement rewrite driven functionally equivalent but structurally different artifacts.

The rest of the paper is organized as follows. Section <ref> introduces the threat and fault models. Section <ref> introduces the notion of Diversity by Composability that is a basis for the framework in Section <ref>. Section <ref> discusses E-Graph based diversity generation method, evaluation results are presented in Section <ref>, followed by related works and concluding remarks in Sections <ref> and <ref>, respectively.




§ THREAT AND FAULT MODELS





 §.§ Actors and Adversaries

We consider a typical design process of three main actors in the ecosystem: designer, vendor, and fab. The designer may use several products from several vendors  (e.g., many tools and implementations) to develop a resilient chip design, which is sent to the fab for fabrication. The roles and trust models of the actors are as follows:

    
  * Designer: the designer of the chip and the main user of . They are assumed to be a trusted entity, and a target/victim of acting adversaries.
    
  * Vendor: the provider of pre-designed prerequisites like design libraries, implementations, or toolchains. Not all vendors are trusted entities.
    
  * Fab: the post-design fabrication foundry that uses silicon technology to implement the design as an integrated circuit. Not all fabs are trusted entities. 




 §.§ Intrusions and Faults

During the design and manufacture process, the design is prone to unintentional faults and intentional intrusions, leading to some functional circuit failure. Faults can be induced at any stage, even by the designer; while intrusions are assumed to be performed through attacking the circuit by the vendor or the fab, who can also collude. Intrusions and faults and their corresponding failures manifest as  faults <cit.>—being a binary domain. In this model, the injected fault/intrusion on a logic gate results in a logic  () or  (). Figure <ref> depicts a schematic of intrusion/fault injection between (a) two gates G1 and G2, leading to (b)  or (c)  faults. This can be replicated between any two gates in the design.





 §.§ Threats and Attacks

We consider the threat model where the goal of the adversaries, i.e., vendor and fab, is to break the integrity of the design or circuit. The aim is to subvert the output either permanently or occasionally. 

We define three types of potential integrity attacks, i.e., Distribution, Zonal, and Compound attacks, defined as follows: 



  §.§.§ Distribution Attack

It is typically faster and cheaper for the designer to use off-the-shelf tools, pre-designed modules, compilers, synthesizers, etc, to create a new design. Any malicious vendor in this chain can induce intrusions, trojans, or backdoors <cit.>. 
The Distribution attack (or fault) is a supply-chain attack where a fault or intrusion can be induced at any step prior to or after design <cit.>. This attack targets any circuit module, channel, or zone. 








  §.§.§ Zonal Attack

The Zonal attack is a directed attack on the design layout. As shown in Figure <ref>, the attack can target a chip in many ways, among them: (1) using an electric bus to overheat an edge <cit.>, (2) using an Electromagnetic field to subvert another edge <cit.>, or (3) using an optical laser beam to target a specific zone after fabrication <cit.>. 






  §.§.§ Compound Attack

The Compound attack is a more complex attack where Distribution and Zonal attacks are preformed simultaneously. In this case, these attacks could be coordinated, e.g., collusion between vendor and fab, or uncoordinated. Although the former is more directed, both scenarios are devastating to the circuit as we show in the simulated experiments. 




§ DIVERSITY BY COMPOSABILITY


In this section, we provide the motivations and design decisions behind .



 §.§ The Quest for Resilience

Designing for resilience often requires redundancy in space or time <cit.>.
Redundancy in time entails repeating computation using the same hardware.
This is effective against transient failures, but not permanent faults and longer term intrusions.
Hence, redundancy in space through replicated hardware, with convergence to a final output is often used.
This final output can incorporate the replicated outputs or choose between them, depending on application.
Since most applications require determinism, reconciling outputs by majority voting is the most common approach in the literature <cit.>.
This is usually on top of Double- or Triple-Modular-Redundancy (TMR).
Clearly, majority voting only works if the replicated logic units do not fail together due to Common Mode Failures (CMF) <cit.>.
Consequently, using diverse replicas—that are functionally equivalent but structurally different—is one way to enhance this approach.
Without diversity, modular redundancy exhibits limited resilience (e.g, against transient failures), at a high hardware cost.
We elaborate further on this in Section <ref>.



 §.§ Diversity Levels




For integrated circuits, we identify three possible levels of diversity: Gate-level, Module-level, and Artifact-level diversity.
We are interested in providing the designer with a mechanism to build resilient circuits, following a bottom-up approach, where diversity at the gate level is utilized to create larger diverse artifacts by composition.



  §.§.§ Gate-level diversity

The lowest level of diversity we consider, targets designing diverse primitive logic modules composed of basic logic gates, e.g., AND, OR. 




Diversity at this level can be achieved using different combinations of logic gates while maintaining the same functionality. This can be done manually, but preferably using an automated algorithm as we do in this work, inspired by <cit.>. As an example, 

Fig. <ref> shows two diverse implementations of the same boolean function. If all inputs are logic , the true output of both circuits is logic . If a  fault is injected at the same point, the two circuits exhibit different behaviors at the final output .
















  §.§.§ Module-level diversity

This diversity level aims at building a module artifact as a composition of diverse modules with some dependency between them.

The designer makes use of off-the-shelf modules, diversified at the Gate-level, to create higher order Composed Module Artifacts (CMAs) through additional diversity at this layer. 

We formally define a CMA as follows:




Consider an arithmetic logical artifact L with a deterministic specification S. An implementation A of L is an ordered set of modules M_i defined as:


    A = (M_1, M_2, ..., M_N) ∈Π = {M_i × M_j × ... × M_N}


where Π is a set of logical circuit modules. A is a Composable Module Artifact (CMA) iff it respects the specification S given a defined connectivity matrix Γ. 


    Γ_N × N = 
    cccc[cccc]
        V_0,0    V_0,1   ⋯    V_0,N-1
    
        V_1,0    V_1,1   ⋯    V_1,N-1
    ⋮   ⋮   ⋱   ⋮
    
        V_N-1,0    V_N-1,1   ⋯    V_N-1, N-1


where, 


    V_ij = 
    
      1    if a_i connected to a_j
    
      0    otherwise




An implementation A uses N modules to conform to the specification S. The connectivity matrix (Γ) of size N × N is a directed acyclic graph (DAG) that defines how Modules are connected with each other. 


For example, to construct an N-bit Ripple-Carry Adder (RCA), the connectivity matrix would simply be an identity matrix (I) as shown in1 Eqn. <ref> .
Similarly, an N-bit multiplier would require N^2 AND gates and 2N-1 adders (either half adders or full adders).

















Such CMAs can be applied to a wide range of designs such as N-bit Adders/Subtracters, N-bit Multipliers, N-bit Dividers, to mention few.
Even modern accelerator architectures are modular and can be implemented as CMAs, e.g. SHA-256 hashing, Vector units, or Machine Learning Systolic Array accelerators <cit.>.
To demonstrate the concept we discuss two widely used designs: N-bit Adder and 4-bit Multiplier.


N-bit Ripple-Carry Adder: Figure <ref> shows an N-bit Ripple-Carry Adder (RCA) composed of smaller modules which can be diverse or homogeneous structures.
The adder is composed of 4-bit full adder modules.
The basic resolution of a module can be decided by the designer.


The corresponding connectivity matrix in Equation <ref> highlights how the modules are connected. 




        
    Adder (Γ_N × N) = 
            ccccc    M_1     M_2    ⋯    M_N 
    c[cccc]
                M_0    1    0    ⋯    1 
    
                M_1     0    1   ⋯    0 
    ⋮   ⋮   ⋮   ⋱   ⋮
    
                M_N-1    0     0    ⋯   1










4-bit Array Combinational Multiplier: The 4-bit combinational multiplier in Fig. <ref> is composed of various Half-Adders (HA) and Full-Adders (FAs) which sum partial products.


The corresponding connectivity matrix is in Equation <ref>, Mul (Γ_N × N):





    
    c@c@c@c@c@c@c@c@c@c@c@c    HA_1     HA_2     HA_3     FA_1     FA_2     FA_3     FA_4     FA_5     FA_6     FA_7
    c[ccccccccccc]
                HA_0    1    0     0     0     0     0     0     0     0     0 
    
                HA_1     0     0    1    0     0     0     0     0     0     0 
    
                HA_2     0     0     0     0     0     0     0    1   1    0 
    
                HA_3     0     0     0     0     0     0     0    1    0     0 
    
                FA_0    1    0     0     0     0    1    0     0     0     0 
    
                FA_1     0    1    0     0     0    1    0     0     0     0 
    
                FA_2     0    1    0     0     0     0    1    0     0     0 
    
                FA_3     0     0    1    0     0     0     0    1    0     0 
    
                FA_4     0     0     0     0     0     0     0     0    1   1
    
                FA_5     0     0     0     0     0     0     0     0    1    0 
    
                FA_6     0     0     0     0     0     0     0     0     0    1










Systolic Arrays: Systolic arrays<cit.> are a class of parallel computing architectures designed to efficiently execute matrix computations, which are fundamental to many scientific and engineering applications <cit.>.

Based on Systolic architecture, Google proposed Tensor Processing Units (TPU) <cit.>, a custom ASIC to accelerate DNN applications. 
A typical Systolic array design consists of a 2-Dimensional grid of Processing Elements (PE), a controller and the on-chip memory/buffer.



Leveraging the design of diverse adders and multipliers, diverse PEs can be designed to enhance the resilience of systolic arrays.






















  §.§.§ Artifact-level diversity

This third level of diversity makes uses of multiple replicas of diverse CMAs running simultaneously, the outputs of which are computed using a majority voter. This is similar to TMR with an important difference: common mode failures are reduced significantly, since diverse CMAs of diverse modules can be used by composition. Visual examples are shown in Figure <ref>. Our evaluation in Section <ref> shows that this level is key to thwart Distribution and Compound attacks in particular.

Furthermore, due to the coarse granularity, the placement of these replicas can be directed to leverage some resilience to Zonal attacks. Combining placement with diversity at different levels boosts the resilience of the system against all considered attacks: Distribution, Zonal, and Compound, as we convey in the evaluations in Section <ref>. 









§ E-GRAPH BASED DIVERSITY GENERATION


An e-graph or equivalence graph is a data structure that compactly represents equivalence relations in the form of Abstract Syntax Trees (AST) <cit.>. Apart from theorem proving <cit.>, it has been used in the optimization of large datapath and arithmetic circuits <cit.> and technology aware synthesis <cit.>. 


Transformations in e-graph consists of two main steps 1)  and 2) . In this work we rely on Yosys/ABC logic synthesis <cit.> flow to synthesize a benchmark circuit into an equivalent  format that could be fed to the e-graph tool for design space exploration. 




Fig. <ref> highlights the application of e-graph  operation to a simple AST representing a simple operation (x × 2) >> 1 in Fig. <ref>. Since (2 × x) is equivalent to (x << 1), therefore, applying this  rule leads to an equivalent graph shown in Fig. <ref> with equivalent operations grouped in the same e-class (red dotted box).  rules are successively applied until the graph is saturated and no more rules can be applied. 

 refers to selecting an e-node (black dotted box) from each e-class based on a certain cost function. 


In this work we extract a number of equivalent relations to create a pool of functionally equivalent but structurally diverse implementations. For example, from Fig. <ref>, two relations can be extracted: 1)  (x × 2) >> 1 and 2) (x << 1) >> 1. 



 §.§ E-Graph Flow

Fig. <ref> shows the e-graph flow to generate diverse implementations of an input circuit represented in the verilog format. The verilog file is synthesized and converted into equation format which represents the circuit in the AND, OR and NOT format. Next, the  operation is applied until saturation and finally a pool of diverse implementations is extracted. Further, HOPE <cit.> parallel fault simulation tool is utilized to quantify the fault coverage of pooled netlists and further pruning can be applied to select the candidates that demonstrate low fault coverage i.e., high resiliency.

Table <ref> highlights the  rules applied in the   implementation. The rules are expanded rather than optimized/minimized to achieve the objective of enhanced resilience. This approach can be extended to generate N-version programs based on the  rules.








§ THE FRAMEWORK


This section presents the framework that is used by the designer to implement resilient designs based on the diversity concepts introduced in Section <ref>. The framework defines a mechanism to construct circuits while: (1) maintaining deterministic behaviour across the entire design despite replication and diversity, and (2) ensuring resiliency to the attacks outlined in Section <ref>.

In , the ultimate goal is to produce a resilient circuit corresponding to a CMA, e.g., 16-bit Adder, following Defintion <ref>. The process follows three main phases summarized in Algo. <ref>, with the details discussed next.



 §.§ Building Diverse Modules via Gate-diversity
 
This phase aims at identifying the different candidate module implementations m_i for use in a CMA implementation A = (m_1, m_2, ..., m_N); e.g., m_i:=4-bit-adder in our example. The aim is to generate diverse modules of m_x^l, m_x^t ∈ M_x, such that  out(m_x^t)=out(m_x^z), where out is the output function, but the structure differs in at least one logic gate, i.e., m_x^t≠ m_x^z.


In the case of a homogeneous CMA, a single module type is used across the entire tuple.







 §.§ Intra-diversity: building a CMA out of Diverse Modules
 
This phase leverages the generated diverse modules M_i to build a resilient diverse CMA A_i=(M_i, M_j, ...,M_N). The designer starts with the standard implementation of the CMA using any generated module implementations in the previous phase.
A conservative option is to use the most resilient CMA implementation A = (m_1, m_2, ..., m_N).
In general, this depends on the policy considering the resilience, cost, space, and time tradeoffs.

Diverse CMAs can be generated either by changing a single module implementation at index i or multiple modules in CMA A_i.











 §.§ Inter-diversity: building a replicated artifact
 
This phase uses TMR-style replication of the diverse CMAs.
The designer starts by selecting one CMA implementation and then replicates it into three replicas whose outputs are connected to a majority voter.
(One can generalize the replication to different numbers.)
The designer then iterates over the three tuples to replace the CMA implementations with diverse homogeneous or heterogeneous ones.
The latter is preferable as this utilizes Inter-diversity between CMAs to defend against Distribution and compound attacks by reducing common mode failures.
To defend against Zonal attacks, we leverage the course-grained nature of this CMA replication to define a resilient-aware placement in the chip design.
This is possible since we can enforce it at this level to avoid fab compiler optimisations that may remove the designed redundancy or optimize routing or layout space.











 §.§ Configurations

The above multi-level diversity is expressed through configurations that combine the Intra- and Inter-diversity.
We define these configurations as follows.
We denote the Intra-diversity of a CMA by α.
This refers to the number of different modules used in the CMA composition.
Since different CMAs in a replicated artifact can have different Intra-diversity α, we model these as a tuple 𝐈 whose dimension |𝐈| is the replication factor. In this case, each index I_i refers to the Intra-diversity value for the implementation A_i of replica i.
The β_𝐈 factor for a given tuple 𝐈, describes the Inter-diversity among the replica CMAs i.e., how diverse they are with respect to each other.
β_𝐈 is computed by taking the symmetric difference among replicated CMAs, as shown in Eqn. <ref>.
To compute β_𝐈 for |𝐈|>2, Eqn. <ref> can be applied iteratively.


    β_𝐈 = (A_i - A_i+1) ∪ (A_i+1 - A_i)


Fig. <ref> shows few example configurations for different values of 𝐈 and β_𝐈. The term CMAs/replicas will be used interchangeably. In Fig. <ref>, a single replica is created with a single module M_1 i.e., 𝐈 = (1). Fig. <ref> shows a single replica consisting of a set of four different modules {M1,M2,M3,M4} i.e., 𝐈=(4) and |𝐈|=1. Fig. <ref> shows a case where |𝐈|=2 with 𝐈=(4,4) i.e., two replicas are created with four diverse modules, however, they are the same as each other, hence β_𝐈=0. Fig. <ref> demonstrates a case where four distinct modules are used to create two replicas (𝐈=(4,4)) with two common modules M1 and M4, the inter-diversity (β_𝐈), computed using Eqn. <ref>, is 4.
Lastly, Fig. <ref> consists of two replicas created with configuration 𝐈=(4,4), β_𝐈=0, which implies each replica is composed of four different modules and there are no common modules between them, therefore, they are said to be totally diverse.


































































§ CMF COMPUTE ENGINE


We implemented a CMF Compute Engine to use as our evaluation testbed.
We plan to make this tool (implemented in Perl and  Verilog) publicly available for the research community.

To the best of our knowledge, there are two previous works that focus on how to quantify diversity in order to build fault tolerant redundant systems. Mitra et. al. <cit.> proposed fault injection at the gate level, computing if both designs produce same type of erroneous output, resulting in a CMF. This method is based on simulation and provides a reliability measure of the design in case of random faults.
However, to capture true CMFs, identical faults must be injected in redundant designs followed by fault simulation.
The work in <cit.> accelerate the diversity metric computation by analyzing circuit paths of gate level netlists of designs. The aim of the proposed tool is to measure the rate of CMF among redundant designs, therefore, a variant of the approach proposed in <cit.> is employed to cater for the need to inject identical faults. 



 §.§ Architecture

Fig. <ref> (Appendix <ref>) shows the block diagram of the proposed common mode failure computing engine. It fetches a set of diverse replicas from the library generated by the method discussed in Section <ref>.
No fault is injected in RR, which serves as a reference circuit producing the golden output. 
The number and sites of faults to be injected depends on the selected fault campaign as discussed in Section <ref>.
Eqn. <ref> highlights the fact that for the CMF output to be true, all outputs from the replicas must be equal to each other and different from the reference output RO: 









    CMF ≡ O_i=O_j    AND    O_1 ≠ RO   ∀ i ≠ j





































 §.§ Simulating Attacks


To simulate Distribution faults, faults are injected at the same location in the common modules among replicas. Evaluation is done by injecting faults across all possible locations in common modules. For example, consider Fig. <ref>, the common modules are M1 and M4 among the two replicas: faults will be injected at the same locations of M1 and M4 in these replicas. However, the total fault injection combinations will be the cross product of the number of gates in the respective common modules i.e., |M1|×|M4|.

In the Zonal fault model, faults are injected at the common zones of the redundant replicas. The zone granularity is a module. In Fig. <ref>, replicas are divided into four zones as each one of them has four modules. This approach emulates the faults that could be manifested due to external attacks on the same spatial zones of the replicas. 

∑_zones(z)∏_Replicas(i) |M_i,z|

Where |M_i,z| denotes the total number of gates in a module of replica i in zone z. The zonal fault injection campaign is more compute intensive in comparison to the distribution faults as it takes into account combinations of all possible locations in the replicas.
The distribution and zonal attacks are combined in the Compound attack model by injecting faults in common modules among replicas and then iterating through zones for zonal fault injection.
















§ RESULTS & DISCUSSIONS





 §.§ Experimental Settings

Our experimental settings make use of the CMF Compute Engine evaluation test-bed. The three attacks Distribution, Zonal, and Compound are simulated as described in the previous section. Intrusion/Fault simulations are randomly generated for 100K test vectors.
We evaluate (1) various configurations (variable α and β) compared to (2) TMR as a state-of-the-art replication method and (3) without replication as a baseline (No-TMR). The focus here is to create diverse N-bit adders.
We do not consider other CMAs due to space limitations and given that the N-bit adder is a good representative example.
For simulations and evaluations, the a 16-bit Ripple-Carry adder (RCA) artifact is considered. However, the proposed approach can be extended to any value of N. 

The diverse adder modules are generated as per <cit.> and a subset of 10 CMA adder implementations with different diversity ratios are handpicked (but used fairly across all experiments). Note that 10 versions were enough to generate hundreds of permutations and millions of intrusion/fault injections, visiting the entire graph of each. The selected modules–functionally equivalent but structurally different–along with the gate count and failure probability (P_f) are shown in Table <ref>. They are also classified into three resilience levels which depends upon the respective failure probabilities of the module. 
The selected modules have varying fault tolerance, area and logic level.

P_f is computed by using the HOPE fault simulator <cit.>. 


From Table <ref> it is also evident that, as the number of gates increases, P_f decreases.
This is due to improvement in logical masking of the modules.














 §.§ Resilience under Distribution Attack/Fault

We first discuss the general patterns of failure probability for against TMR (without composition diversity) as state-of-the-art solutions and No-TMR (no replication) as baselines. We observe in Figure <ref> that all configurations of are significantly more resilient than the baselines. In particular, as more Inter-diversity is induced across replicas 's resilience ranges between 0.6 and 0.1, while both TMR and No-TMR (whose lines are separated for visibility) exhibit around 0.7 resilience. This shows that TMR is not effective without diversity as it fails similar to No-TMR due to common mode failures. 


We then discuss Intra- and Inter-diversity aside, showing that both are important and complementary. We omit No-TMR for clarity, knowing that its resilience is similar to TMR across all Distribution attack results. Fig. <ref> conveys the resilience for fixed β, while intra-diversity α varies between 2 and 4. The results consistently show that diversity by composition improves resilience of over TMR as α increases to 10% with each diverse module added. The improvement is significant for higher β. In the best case (f) where β=6, i.e., different modules are used in different replicas, the failure probability is lower than 0.1. These results are consistent with the case where α is fixed, whereas the Intra-diversity β varies in Figure <ref>. With few diverse modules (a) α=2 per replica, the resilience improves as long as more diverse modules are used in different replicas. The improvement is significant in the most diverse configuration α=4. The interesting observation in varying α and β is that the designer can tune the level of diversity based on the available versions, cost, and sensitivity of the application.



 §.§ Module placement and alignment across replicas

An impacting property of composition in is the position of common modules across replicas that plays an important role in overall resilience. We explain this in Fig. <ref>, where two replicas R1 and R2 are constructed in such a way that R1={M1, M2, M3, M4} and R2={M5, M6, M7, M1}. M1 is the common module and the placement distance difference between the location of M1 in two replicas is 3 i.e., M1 location in R1 and R2 is 0 and 3, respectively. From Fig. <ref>, it can be observed that increasing alignment distance between a common module across two replicas improves resilience because varying common module location in replicas has a direct impact on fault controllability and observability conditions, resulting in reduced CMFs. 






 §.§ Resilience under Zonal Attacks

We now evaluate under Zonal attacks. We pick two simulated scenarios: a horizontal attack (e.g., Electromagnetic field applied Figure <ref>) which affects an entire replica and its modules, and a vertical attack that affects one module of each replica. Since No-TMR has no replication, the entire modules of the CMA are attacked. As expected, under the horizontal zonal attack an entire CMA replica is attacked in TMR and (4,8) (full diversity).  The impact of the attack is 100% masked by the majority voting. The No-TMR case however fails drastically with failure probability close to 0.9. This reinforces the fact that TMR is useful in some cases even without modular diversity under Zonal attacks. The advantage is, however, not present in the case of vertical zonal attack, since all replicas in TMR and are hit by the attack, which cannot be masked by the voter. As expected, the failure probability in this case is only affected by the gate-level diversity of the modules used. 








 §.§ Resilience under Compound Attacks

We finally consider the case of Compound attack where the Zonal and Distribution attacks are simultaneously applied. 


We fix α=4, while varying the value of β in Fig <ref>. For the case of α=1,β=0, all modules are victims of the Distribution attack which has a huge impact on TMR and No-TMR as we have seen in Figure <ref>. For the case where replicas are composed of diverse modules and there are no common modules among them, a module is picked at random for the injection of the Distribution attack. 

can sustain the Compound attack with down to 0.1 failure probability compared to TMR and No-TMR which fail most of the time.




 §.§ Impact on Area, Power and Delay

To determine the impact of proposed technique on area, power and delay, the replicas are generated with specific resilience according to the classification levels mentioned in Table <ref>. The area, delay, and logic levels are calculated using the Berkeley-ABC synthesis tool <cit.> for the MCNC library. The MCNC library is slightly modified to include only 2-input NAND/NOR and XOR/XNOR gates along with an Inverter. This is done to make sure the library remains highly correlated with the designs mentioned in Table <ref> and also to restrict the map tool optimizations. The area is computed by adding the fanins of all gates in a circuit. The dynamic power consumption of a digital circuit is determined using the Berkeley-SIS tool <cit.> for the MCNC library operating at a supply voltage of 5V and a frequency of 20 MHz. 

Algorithm <ref> is applied by fixing the values of α and β to {1,0}, {1,8} and {2,0} respectively. We generated 100 CMAs corresponding to each resilience level as shown in Table <ref> and results are averaged. Table <ref> provides valuable insights into the trade-offs between area, power, and delay across different redundancy configurations. It can be observed that with increasing resilience level, area, power, and delay also increase. This is due to the fact that the resilience of modules M_i is increased by injecting the functionally redundant logic leading to an increase in area and power. The introduction of redundant paths or logic can also affect the timing characteristics of a circuit. While some forms of redundancy, like parallel processing units, might aim to reduce processing time, others might introduce additional stages of logic that data must travel through, thus increasing the delay. 
Delay is a function of the critical path–the longest path between any input and output–of a circuit.

TMR is a special case of (α,β)={1,0}, where all replicas are identical and consumes maximum area in comparison to the other configurations. In the case of low module resilience for (α,β)={1,0} & {2,8}, the area decreases from 344 to 324, but power consumption and delay is increased. This is due to the introduction of XOR/XNOR gates in the redundant logic, which consume more power and have greater delay compared to NAND/NOR gates. Similarly, for the case of medium and high resilience, the corresponding area, power and delay is increased for both cases of (α,β). However, the area for the case of medium resilience reduced from 379 to 374. 










 §.§ Diversity and Resilience with E-Graphs


The effectiveness of E-GG based approach to generate diverse and resilient circuits is evaluated on the benchmark circuits shown in Table <ref>. The benchmarks are a mix of circuits from LGSynth <cit.>, ITC <cit.>, and ISCAS85 <cit.> benchmark suites. Additionally, an open source divider from OpenCores is also considered for evaluation.  <cit.> is also utilized to generate two multipliers (3x3 and 5x5). The  benchmark corresponds to the Multiply-Accumulate operation unit of a typical systolic array. 

The  (Table <ref>) and  methods of E-Graphs are implemented in  to interface with the  library. 

Fig. <ref> highlights the resilience range of chosen benchmark circuits. For benchmarks , ,  and  the  tool is able to generate diverse replicas with varying resilience (P_f) levels. Similarly, Fig. <ref> shows the spread of area across benchmark circuits. We are able to generate varying area profiles for ,  and , whereas for the rest the areas of generated diverse replicas almost remain constant. 
We observed that the resilience and corresponding area profiles are sensitive to the  rules which can be controlled by modifying them in Table <ref>. New rules added or existing ones modified can lead to different implementations and area/resilience profiles. can leverage these diverse replicas to create larger diverse artifacts. It should be noted that for the benchmarks in Table <ref>, we didn't perform the distribution and zonal attacks simulations. 

Impact of Synthesis Tools on Diversity Generation. The inherent nature of Electronic Design Automation (EDA) synthesis tools is to optimize circuits to meet the area, power and delay constraints. To achieve resilience, additional gates have to be added that doesn't change the function of circuit but increase the area and delay. Since E-Graph works on the ASTs of a given language, therefore, it relies on parser and lexer for text processing. Any redundancy in the resulting E-Graphs of diverse replicas will 1) be removed by the parser, or 2) removed by the synthesis tools. To avoid these optimizations, one way is to 1) add a different tag to each redundant gate, 2) declare all redundant gates as primary inputs to the circuit, 3) doing the synthesis now will not perform any optimization, and 4) remove redundant gates from the primary inputs list. Following these steps, it is observed that very high resilience can be achieved, but at the cost of exorbitant area (cf. Appendix <ref>). It will be interesting to investigate the impact of E-Graphs to generate diverse replicas at different levels of digital circuits abstraction. 




§ RELATED WORK


The resilience of a system is significantly improved by applying replication followed by a voter for majority consensus. Traditional approaches to avoid CMF in TMR/DMR have been to implement diverse systems at higher levels of abstraction <cit.>. Faults can be intentional or accidental and have predictable manifestations in digital circuits.
State of the art literature classifies faults/vulnerabilities into four categories: 1) hardware trojans or malicious implants, 2) backdoor through test/debug interfaces, 3) accidental/unintentional vulnerabilities <cit.>, and 4) external faults <cit.>.
To combat low level faults, resilience through design diversity must be applied at the gate level.
Cartesian Genetic Programming (CGP) <cit.> had been proposed to generate diverse isofunctional structures to improve resilience at the gate level of a design <cit.>. Similarly, redundant designs can be spatially separated to provide resilience against external faults in TMR systems <cit.>. attempts to build on this concept of diversity, however, proposes a novel approach to combine small diverse structures to create larger diverse artifacts.

Faults based on external attacks can be due to various sources.
Power supplies can be tampered with to alter uniform behavior, resulting in erroneous results.
Similarly, power spiking can cause a processor to not only misinterpret an instruction but also induce memory faults <cit.>. 
Clock glitches, through a deviated clock signal, can be induced to cause execution of subsequent instructions before retirement of previous instructions, i.e., modification of the program counter (PC) at irregular intervals <cit.>.
This type of attack is considered to be the simplest as low-end FPGAs can be used to inject clock glitches <cit.>. 
Electronic devices function properly in a certain temperature range, however, when exposed to extreme temperatures, the data inside memories can be corrupted.
These attacks are easier to set up but their effect cannot be localized.
Optical attacks are performed by exposing the device to a focused laser beam or strong photo flash.
This attack  can be targeted on either side of the chip and can be confined to certain area to set or reset memory bits or switch transistor state <cit.>.
Similarly, electromagnetic (EM) interference can corrupt or modify memory contents by inducing eddy currents, resulting in a single or multiple bit faults <cit.>.
Both optical and electromagnetic attack fits our definition of zonal attacks in this paper. 

Attacks based on malicious implants can be inserted into a design at various stages, such as by an untrusted CAD designer, by a malicious tool, or at the foundry <cit.>.
Furthermore, hardware verification is a time-consuming and costly task, making it challenging to detect such trojans at scale <cit.>.
Malicious implants can be activated by an attacker using a carefully crafted strategy <cit.>.
Previous works have discussed hardware trojan activation using a combination of software-hardware <cit.> and triggers based on time, input sequence and traffic patterns <cit.>.
We model these Distribution Attacks by injecting fault(s) at specific location(s) in the design and investigate which input patterns are able to activate them. 







§ CONCLUSIONS


Existing approaches to resilient chip design have mostly been studied under benign fault models where no malicious actors exist <cit.>. addresses that gap, motivated by recent digital sovereignty concerns <cit.>.
Productive chip businesses focus on design, while making use of off-the-shelf tools and libraries from different vendors after which fabrication is outsourced. If vendors and fabs are not trusted, the design can be vulnerable to several attacks, among them three we introduced: Distribution, Zonal, and Compound.
To mitigate these attacks, we introduced the notion of Diversity by Composability that enables the building of resilient circuits out of smaller diverse modules.
Together with state of the art gate-level diversity and modular redundancy, we show that resilience to the aforementioned attacks is significantly improved, by the factor of five against considered attacks, and the designer retains some control on diversity. Additionally, we also showed how E-Graphs can be utilized to generate diverse replicas using the language independent  tool.






plain









§ 







There exists an N-bit Adder implementation that is a homogeneous CMA.



Consider the N-bit Ripple-Carry Adder (RCA) in Figure <ref>. The RCA is composed of a tuple of N modules (M_N,...,M_1) where M_i=N-bit-FA ∀ i ∈ [1,N]. Therefore all modules M_i are equivalent, i.e., homogeneous.
In addition, the RCA is defined by the Identity dependency matrix of these deterministic modules, in Eq. <ref>, that by design produces the same output(s) for the same input(s).





There exists an N-bit Multiplier implementation that is a heterogeneous CMA.



Consider the N-bit Array Combinational Multiplier (ACM) <cit.>, similar to the 4-bit one in Figure <ref>. RCA is composed of a tuple of L=2N-1 modules (M_L,...,M_1) where M_i=N-bit-FA or N-bit-HA ∀ i ∈ [1,L]. The same functional modules M_i can be implemented as homogeneous or diverse structures, i.e., heterogeneous. In addition, ACM is defined by the deterministic dependency matrix of these deterministic modules, e.g, Mul in Eq. <ref>, that by design produces the same output(s) for the same input(s).



 (A Diverse CMA is deterministic)

A CMA A_i=(M_i, M_j, ...,M_N) whose module implementations m_k^t belong to a diverse module M_k is deterministic.



Assume the contrary, that there exist at least two diverse CMA implementations P=(p_1^a, p_2^b, ..., p_N^z) and Q=(q_1^l, q_2^t, ..., q_N^k) with at least one tuple location x having (p_x^e≠ q_x^e), p_x^e, q_x^e∈ M_x (M_x being a diverse module), and such that out(P)≠ out(Q) (nondeterministic). Since all module implementations p_y^f and q_y^g belong to a diverse module M_y, then it is possible to replace each p_y^f with q_y^g at every index y in CMA P. This generates exactly equivalent tuple implementations P=Q. Since we assumed out(P)≠ out(Q), then out(P)≠ out(P). This means having one exact implementation of CMA that is not deterministic, which contradicts the CMA definition in Eq. <ref>.
Therefore, a diverse CMA is deterministic. 




§ 






Fig. <ref> illustrates the impact of synthesis on digital circuits (discussed in Section <ref>). Example circuit (Fig. <ref>) consists of 7 logical gates with P_f=1. Applying E-Graph rewrite and extract operations with optimizations i.e., not tagging each gate, the resulting area after synthesis is 16 gates with the corresponding P_f=0.84, as shown in Fig. <ref>. However, if each gate is tagged i.e., no optimization is applied, synthesis of the circuit will result in 25 logical gates with P_f=0.74, as shown in Fig. <ref>. This simple example highlights the area is increased by more than 3x if no optimization is applied. For larger circuits, we observed that the resulting area becomes exorbitantly high (with corresponding significant reduction in P_f) making the final design unfeasible for practical applications. 







§ 


Fig. <ref> highlights the flow of common mode failure computing engine.




