Nathaniel A Conos
email: conos@cs.ucla.edu

Saro Meguerdichian

Miodrag Potkonjak
email: miodrag@cs.ucla.edu

Gate Sizing under Uncertainty

Keywords: Gate Sizing, Low Power, Input Vector Control, Switching Activity, Yield Optimization

We present a gate sizing approach to efficiently utilize gate switching activity (SA) and gate input vector control leakage (IVC) uncertainty factors in the objective function in order enable more efficient power and speed yield tradeoffs. Our algorithm conducts iterative gate freezing and unlocking with cut-based search for the most beneficial gate sizes under delay constraints. In an iterative flow, we interchangeably conduct gate sizing and IVC refinement to adapt to new circuit configurations. We evaluate our approach on benchmarks in 45 nm technology and demonstrate up to 62% (29% avg.) energy savings compared to a traditional objective function that does not consider SA and IVC. We further adapt our approach to optimize yield objectives by addressing processing variation (PV). Significant improvements were achieved under identical timing yield targets of up to 84% max (55% avg.) and 74% max (25% avg.) mean-power savings for selected ISCAS-85 and ITC-99 benchmarks, respectively.

Introduction

Gate sizing is a powerful optimization technique used to minimize power and/or area under strict timing constraints by altering the widths of transistors in gates. Gate sizing has been extensively studied over the past three decades [START_REF] Shiyan | Gate Sizing For Cell Library-Based Designs[END_REF][START_REF] Ozdal | Gate sizing and device technology selection algorithms for high-performance industrial designs[END_REF][START_REF] Joshi | An Efficient Method for Large-Scale Gate Sizing[END_REF][START_REF] Ozdal | The ISPD -2012 Discrete Cell Sizing Contest and Benchmark Suite[END_REF] and several approaches have been proposed. Previous approaches, however, do not consider optimization uncertainty factors, such as switching activity (SA) and the impact of input vector control leakage (IVC), which greatly impact the overall optimization strategy. Additionally, the impact technological uncertainty, i.e., process variation (PV), has increased in the deep-micron regime, and traditional techniques lack the ability to effectively address yield targets. As a result, the modern design flow imposes a number of modeling and optimization challenges, that require new methods in accounting for uncertainty, both technological and optimization.

One major challenge is the simplification of timing and power models, which may lead to suboptimal solutions when mapping out to real designs, thus, increasing optimization uncertainty. Accounting for accurate gate and interconnect delay and its dependencies on capacitive load slew are often ignored [START_REF] Ozdal | The ISPD -2012 Discrete Cell Sizing Contest and Benchmark Suite[END_REF]. Additionally, nominal gate switching activity and/or average gate leakage are generally assumed in previous works limiting the potential improvements by accounting for realistic operating conditions. Moreover, previous approaches are either dynamic or leakage power-centric in their optimization flows, which do not address the varying application usage characteristics present in high-performance systems (e.g., data-centers, super-computing) to energy constrained mobile devices (e.g., tablets, smart-phones).

Cell library-based optimization has emerged as the de facto standard for modeling power and delay of a circuit design. Many previous approaches, however, utilize simplified timing models by assuming convex and/or linear delay and power models [START_REF] Joshi | An Efficient Method for Large-Scale Gate Sizing[END_REF]. Empirical analysis has shown that accurate timing models are non-linear/non-convex. Furthermore, optimizing circuit designs using a discrete cell library, however, leads to solving an NP-Hard problem [START_REF] Li | Strongly NP-hard discrete gate-sizing problems[END_REF]. As a result, many heuristics have been developed in order to address the huge optimization problem search space. A major drawback of these methods is that they require heavy parameter tuning and are difficult to reproduce, since they are technology dependent and are driven by a set of sensitivity functions. These methods often perform iterative per-gate or per-group improvement and are too compute intensive and are impractical to be applied on modern IC sizes, even with incremental updates. Furthermore, these approaches mainly perform local optimization (i.e., local-moves) and are susceptible to be trapped in local minimas [START_REF] Agarwal | Statistical timing based optimization using gate sizing[END_REF]. In this work, we interchangeably use the term gate and cell to represent the granularity in which we size gates, which is at the cell-level.

The usage of modern cell libraries, however, have enabled the support of various supply/threshold voltages, and drive strengths, thus, enabling a rich performance and energy trade-off to address the potentially vastly differing device usage characteristics. However, current tools do not account for realistic conditions into their objective functions (e.g., gate activity, duty cycle, input vector control), with respect to their applications, potentially impacting obtained results.

In this chapter we focus on two main contributions. The first contribution, introduced in [START_REF] Conos | Gate sizing in the presence of gate switching activity and input vector control[END_REF], improves state-of-the-art sizing methodologies by simultaneously considering gate switching activity (SA) and gate input vector control (IVC) uncertainty. The key contribution is that significant benefits of incorporating actual gate SA and gate IVC in the objective function over the equivalent approach that only uses averaged values. Additionally, we show how the obtained solution varies when accounting varying duty cycles. The second contribution, introduced in this chapter, is the integration our SA+IVC technique with a pre-characterization step to improve power and yield targets.

The focal point of our approach is a scalable gate sizing algorithm that considers gate SA and IVC leakage. The steps are to: 1) extract the SA of gates based on simulation of real workloads; and 2) conduct IVC to obtain the input vector that induces the lowest total leakage energy across all gates, and 3) an iterative gate sizing approach freezes maximally-constrained gates (ones that are at high-power states as determined by SA and IVC) while searching for a sizing option that best improves the current picture. The objective function in step 3 to be considered at the iteration depends on the types of options available and their impacts on both delay and energy. The algorithm prevents the algorithm from reaching a local minima by freezing gates as they are sized until all gates have been frozen, then unfreezes all gates, re-conducts IVC (since new gates may be energy-dominant), and reiterates steps 2 and 3 until the solution converges or the delay constraint cannot be met.

B[1]

A [START_REF] Conos | Gate sizing in the presence of gate switching activity and input vector control[END_REF] Cin [START_REF] Conos | Gate sizing in the presence of gate switching activity and input vector control[END_REF] Carry The concept introduced in this chapter is the extension of our gate sizing technique to account for the impact of process variation for maximizing yield targets with respect to specified delay and power targets. Efficient yield optimization is achieved by a precharacterization step which identifies the most critical cells that are likely to impact delay targets through an efficient Monte Carlo simulation that considers epsilon-paths (ε-paths). The intuition is to simultaneously speed-up critical paths in order to minimize the impact of process variation across generated circuit instances and minimize the power costs by conducted gradual gate sizing.

[1] B[0] A[0] Cin[0] Carry[0] G6 G5 G4 G7 G2 G1 G0 G3 1 0 0 1 1 1 0 0 0 1 1 1 1 1 B[2] A[2] Cin[2] Carry[2] G10 G9 G8 G11 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1
We evaluate our gate sizing approach on benchmarks included in ISCAS-85/89, ITC99 and arithmetic units first without consideration of PV. Our results indicate over 62% (29% avg.) energy improvement over a method that assumes nominal SA and IVC, demonstrating that gate SA and IVC play an major role in the guiding sizing decisions over an equivelent sizing algorithm that does not. We then present results using our PVaware technique, which further imroves our original gate sizing algorithm to address yield objectives. We demonstrate the effectiveness of our process variation-aware (PVaware) against a non PV-aware technique across ISCAS-85 and ITC99 benchmarks, achieving 64% and 48% power savings with respect to identical target delays.

Motivation

We begin by providing a small realistic example demonstrating the importance of considering both SA and IVC uncertainty factors in the gate sizing optimization process. Consider the carry propagation of a 3-bit carry-ripple adder, shown in Figure 1. Assume that 2-and 3-input NAND gates have input-dependent leakage power consumption values for two possible sizes, small (X1) and large (X2), shown in Table 1. Also assume that the given input vectors (A = 101, B = 101, and C in = 1) are realized throughout the entire duration of the application. Figure 1 shows the input vectors to each gate. Therefore, the overall leakage power of the circuit is 288 nW. For simplicity, ignoring load and slew dependencies, assume that all gates have delay of 10 ps at size X1 and 5 ps at size X2. Finally, assume that at the beginning of the optimization process, all gates are nominally sized to size X1. Therefore, there are eight nominal critical paths (colored), {G0, G2} → G3 → {G4, G6} → G7 → {G8, G10} → G11, with nominal delay 60 ps. Consequently, total leakage energy of the circuit is 1.73 × 10 -17 J.

As an example, consider a delay constraint of 55 ps. It is clear that one of gates G3, G7, or G11 should be sized up to X2, as all critical paths pass through these bottleneck gates and decrease the delay of each of these gates will decrease the overall delay. A traditional approach to gate sizing would consider these gates equally. In other words, increasing the size of either would decrease delay and increase switching and leakage power by the same amounts. However, from Table 1, we see that the leakage power of a gate, due to transistor stacking, strongly depends on its applied inputs, with up to a 43X difference between the lowest-leakage state (input vector "100": 1.29 nW) and highestleakage state (input vector "111": 55.8 nW) of a 3-input NAND gate. Furthermore, switching energy of a gate is directly proportional to its activity factor, or the likelihood that the gate will switch. Therefore, because the gates have both different applied input vectors and different activity factors, sizing up each one will have a different effect on overall power and energy consumption, so they should not be weighted equally in the optimization process.

First, consider the case where the duty cycle of the adder is low and therefore leakage energy dominates. We can determine from Table 1 that increasing the size of gates G3, G7, or G11 will increase leakage power by 9.96 nW, 167.42 nW, or 56.35 nW, respectively, while decreasing the overall delay by 5 ps. Therefore, the optimal decision is to increase the size of gate G3, which will have minimal impact on leakage energy, increasing leakage power to 298 nW and decreasing leakage energy to 1.64 × 10 -17 J. Increasing the size of G7 would instead increase leakage power to 455 nW, increasing leakage energy to 2.50 × 10 -17 J. Thus, considering IVC in this example in the optimization algorithm can improve the energy by roughly 60%. Now, consider the high duty cycle scenario, where switching energy is the dominant factor. Again, for simplicity, assume that all gates consume 10 nJ and 20 nJ of switching energy at nominal activity factor 1.0 for a given application at sizes X1 and X2, respectively. Figure 1 shows the activity factors (α) for each gate. Therefore, overall switching energy consumption at the nominal size is 35.5 nJ. In this case, increasing the size of gate G7 is the optimal decision, since it has the lowest activity factor and consumes less switching energy than when up-sizing either G3 or G11. In fact, this decision results in a switching energy of 36.5 nJ, whereas increasing the size of G11 would result in a switching energy of 41.5 nJ. Therefore, the decision that considers SA performs roughly 14% better.

Another key component modern design flow that requires attention is the process variation (PV) impact on sizing moves. For example, sizing alterations, such as the ones discussed in this section, are mostly performed in the pre-silicon phase. Therefore, there is uncertainty in how sizing alterations are affected by on-chip variations once the design has been manufactured. Optimizing for yield can be exhaustive and require extensive statistical characterization; however, conducting a pre-characterization step may reveal more suitable circuit alterations that may not be possible to capture in a traditional static flow. For example, designers may leverage spatial and temporal correlations in a design to determine the best cell(s) to size. For example, G3 may belong to a path whose delay is more susceptible by PV; thus, it would be more beneficial for G3 to be up sized eve though G7 was identified to be a more efficient move in terms of power-speed trade-off under a traditional static optimization approach. As a result, the benefits of accounting the impact of PV in a circuit is clear when optimizing for yield. To present these motivations, we have made a number of assumptions that when relaxed make the optimization much more complex in practice. It is reasonable to assume that additional information (gate switching, input vector state, and pre-characterization statistics) can be readily obtained by modern CAD tools and/or by implementing a simple gate-level simulator combined with statistical packages. Such information is beneficial since it enables the simultaneous consideration of low duty cycle and high duty cycle scenarios, as in real use cases at current and pending deep-submicron feature sizes, leakage and switching may both have significant impacts on overall energy. For example, sizing up G7 in the high duty cycle scenario may in reality not be optimal, since its input gates have higher values for α than, the input gates of G3, and thus their switching energies would increase by larger factors. Thus, this IVC depends on how the circuit is sized and its duty-cycle. Therefore, a feedback loop exists between gate sizing and IVC that must be addressed simultaneously during the optimization. The example here demonstrates that both IVC and SA are crucial considerations in gate sizing for energy optimization in the presence of delay deadlines. Furthermore, combining PV-uncertainty can further provide key insight in guiding circuit alterations.

Related Work

We cover a set of related gate sizing approaches that have considered a variant of SA or IVC. Several approaches exist that address continuous and discrete gate sizing. Common methods to solve the gate sizing problem have been convex optimization [START_REF] Joshi | An Efficient Method for Large-Scale Gate Sizing[END_REF], Lagrangian Relaxation [START_REF] Shiyan | Gate Sizing For Cell Library-Based Designs[END_REF][START_REF] Ozdal | Gate sizing and device technology selection algorithms for high-performance industrial designs[END_REF], [START_REF] Li | An efficient algorithm for library-based cell-type selection in high-performance low-power designs[END_REF], and gradient and sensitivity-based optimization [START_REF] Coudert | Gate sizing for constrained delay/power/area optimization[END_REF], [START_REF] Hu | Sensitivity-guided metaheuristics for accurate discrete gate sizing[END_REF].

Gate sizing methods have also been combined with V dd and V th assignment to minimize power under various gate SA ratios [START_REF] Srivastava A | Power minimization using simultaneous gate sizing, dual-Vdd and dual-Vth assignment[END_REF], [START_REF] Huang | Switching-activity driven gate sizing and Vth assignment for low power design[END_REF]. These works, however, have only considered average leakage values when accounting for leakage and have not explored real application activity factors when considering gate switching activity. Leakage minimization using IVC is a popular technique for due to its strong dependency on the input vector state [START_REF] Abdollahi | Leakage current reduction in CMOS VLSI circuits by input vector control[END_REF]. IVC and gate replacement techniques have also been combined [START_REF] Yuan | A combined gate replacement and input vector control approach for leakage current reduction[END_REF] by replacing gates at their worse-case leakage state with equivalent gates with lower leakage power.

To the best of our knowledge, we are the first to consider gate sizing in the presence of both SA, IVC, and duty cycle. Prior approaches have at most considered one or two terms accurately [START_REF] Tsui | Minimizing the dynamic and subthreshold leakage power consumption using least leakage vector assisted technology mapping[END_REF], and/or do not differentiate between the duty cycle with respect to switching and leakage energy weights, leaving many approaches to be either dynamic or leakage power-centric. For example, the state-of-the-art gate sizing contest considers only nominal leakage power [START_REF] Ozdal | The ISPD -2012 Discrete Cell Sizing Contest and Benchmark Suite[END_REF]. Our technique minimizes total energy, such that both the switching and leakage energy components are accurately accounted for in accordance to their usage or duty cycle.

Cell Library Energy and Delay

The total energy of a CMOS integrated circuit can be characterized into two main components: 1) dynamic (switching) energy due to charging of input pin/output load capacitance's; and 2) static (leakage) energy, which we model from the dominant subthreshold leakage and gate leakage currents. Thus, the total energy consumed can be computed as:

E total = E switch + E leak (1)
E switch = N ∑ i es(g i ), E leak = N ∑ i el(g i ) (2)
es and el represent the switching and leakage energies, respectively, for gate g i . es is the product between probability that a gate's input pin j will switch, α (SA), and the estimated full-cycle (e f c ) power consumed from propagating a signal from input pin j to output pin k. el is the sum of leakage energies consumed at each possible leakage state of a gate, which is also dependent the ratio of the total time spent at each leakage state for both active and standby (idle) periods. The total time (T ) is directly proportional to product of the circuit delay (D) and total cycles, where D represents the critical outputpin arrival time (rise or f all) of a primary output gate ot r, f (g i ):

D = max(ot r, f (g i )) s.t. g i ∈ G out (3)
G out represents a circuit's set of primary output gates. Therefore, the delay of a circuit can be determined by solving:

ot r, f (g i ) = dl r, f (g i ) + max(ot( f in f ,r j )) (4) s.t. f in i ∈ FI i f in f ,r
j is the f all, rise arrival time of a fan-in gate j in the set FI i of gate g i . Note that the propagation of delay depends on the unateness assumption. For simplicity, we assume all cells are negative unate, thus, rise (r) and fall ( f ) gate delays are propagated as assumed to the next stage.

We use a cell table library look-up as [START_REF] Ozdal | The ISPD -2012 Discrete Cell Sizing Contest and Benchmark Suite[END_REF] to model gate rise and f all delay (dl r, f ) as a function of its input slew (transition time), and driving load. However, we use an alternate 45 nm cell library (Nandgate) [START_REF]Nangate FreePDK 45 nm Library[END_REF] to account for switching and input vector dependent leakage power, which are obtained in a similar look-up table fashion, provided per-input pin accurate switching, and input vector state probabilities, which can be obtained using gate-level simulation. Our gate sizing procedure is composed of three major phases (Figure 2). The first phase extracts gate switching activity factors (SA) for a given circuit by performing eventdriven gate simulation from a set of input bit vectors. Figure 3 illustrates an example SA extraction for a carry-look-ahead unit (cla4) from two applications (mpeg2enc/dec). The second step identifies a primary input bit vector that places gates in low leakage states in order to minimize the total energy of the circuit, which accounts for leakage consumption for both active (obtained from SA) and idle periods. IVC techniques range from random simulation to satisfiability (SAT) and model counting-based formulations. The final component is the gate sizing algorithm, where the goal is to minimize total energy consumption under a delay constraint. The approach is iterative; at each iteration, gates are either frozen or unlocked based on their leakage (IVC) and switching (SA) impact, while a search is conducted for the most beneficial current move.

Switching Activity Extraction

Input Vector Control

Gate Sizing Optimization

Fig. 3. Gate switching activity for a 32-bit CLA circuit when using real mpeg2enc/dec application input stimulus. Shown are varying distribution of gate activity within a circuit and across two applications.

Our algorithm is sensitivity-based in nature in terms of determining which move or set of moves to perform. A gate sizing move can have 1 of 3 effects (increase, decrease, have no effect) on 2 parameters (energy and delay), leading to a total of 9 separate possible classes for a move. The algorithm classifies each move to and enforces a priority scheme in order to select a move that has higher precedence. There are three precedence levels, where level 1 is the highest priority. Moves that improve both parameters are at precedence 1, moves that improve just one parameter and do not affect the other are at precedence 2, and moves that improve one parameter at the expense of degrading another are of precedence 3. Note that moves that degrade both parameters are never selected. Each precedence level has its own objective function for selecting the best move: 1) the product of the respective improvements; 2) the single improvement; and 3) the normalized ratio of improvement and degradation.

The algorithm considers a cut of M gates at a time and restricts one gate to be sized per group visit. Once a size move is committed, the gate is locked and is no longer considered within that phase. The completion of a phase is defined as having locked all gates, or having no more acceptable moves among sizable gates that improve the objective function. The algorithm terminates after the solution converges or if a target delay (D target ) can not be met after a number of phases. All gates are unlocked before the start of each new sizing phase.

The algorithm initially freezes the top K energy-critical gates by setting them to their minimal sizes at the beginning of the phase. We note that this initial set potentially restricts some delay critical gates, as improving the delay of these gates may be required in meeting a deadline. To relax this constraint (i.e., if a solution cannot be obtained), K is relaxed through a locking threshold ratio γ, where a new K is computed (e.g., K = K •γ), thereby, enabling potentially more delay critical gates to be reduced. It is crucial to identify the top K energy-critical gate, which in turn depends on both SA and IVC; this maximally-constrained gate locking is one of the key innovations of the approach, and prevents being trapped at a local minima by encouraging global circuit optimization.

We utilize an epsilon tree to minimize circuit delay updates (ε path ), which consists of gates that were on the critical path during the last accurate delay computation (Figure 4a). Since the critical path may change during optimization, we also include the immediate fan-out gates of each critical gate (e.g., nodes 1 and 3), fan-in nodes may be added for greater accuracy as their slews may also impact timing propagation. The figure shows bold-outlined nodes (e.g., 7, 8, 9, 5 and 6) are the primary outputs (G out ), and are transitively connected to at least one node belonging to the critical path (e.g., 0, 2, 4, 8). Thus, the delay cost of sizing a gate on the ε path can be estimated by the sum of its δ i with respect to the target delay (D target ) is used to estimate the delay impact of each move via a delay cost formula, as shown below:

D cost = ∑ |G out | i (δ i -D target ) 2 (5)
This formulation enables very efficient delay estimation by only considering the delay impact of a small subset of gates at a time. A drawback of this approach, however, is that a potentially new critical path may emerge. This remains to be a major challenge for existing gate sizing techniques that attempt to maintain delay accuracy during optimization [START_REF] Coudert | Gate sizing for constrained delay/power/area optimization[END_REF], [START_REF] Li | An efficient algorithm for library-based cell-type selection in high-performance low-power designs[END_REF], [START_REF] Hu | Sensitivity-guided metaheuristics for accurate discrete gate sizing[END_REF]. To address this issue, the frequency of delay updates can be increased by adjusting M and γ to be larger values, as we have done. These parameters can be adjusted, to trade-off accuracy vs run-time. Our used values of M and γ achieved a delay accuracy to be within 5%, while achieving linear run-time scaling with respect to circuit size (Figure 4b).

Maximizing Yield

In this section, we extend our gate sizing technique to account for the impact of process variation in order to maximize yield targets with respect to delay and power. Cell Characterization. As a pre-processing step, we characterize each cell's ability to improve the circuit delay when its size is increased by one. The objective is to capture its delay impact on a set of ε-critical paths when its size is increased. We define the ε-critical paths as the set of paths whose cell slack is within an ε-threshold value with respect to the critical slack. The distinguishing factor of our PV gate sizing method against our non-PV method is that we aim to improve a set of ε-critical paths. Doing so improves the circuit's resiliency against the potentially harmful effects of PV by over-optimizing one or few critical paths that do not consider PV. The major challenge of our cell characterization phase is that it incurs additional run-time overhead of O(n 2 ), since the delay impact of sizing each cell is required to be computed. The timing overhead, however, can be minimized by considering a smaller ε-critical set and is practical, since this step can be performed only once or a few times. Additionally, the typical distribution of critical cells in the circuit is anywhere from 1% to 10% during the initial stages of our gate sizing method when all cells are initially set to their valid minimal size configuration. It is important to note, however, the number of cells that belong within ε-critical paths increases as the circuit becomes more sensitive. At these inflection points, additional characterization phases can be performed in order to improve accuracy.

Figure 5 presents the circuit slack impact (y-axis) when increasing the size of each cell (x-axis) independently. The y-axis represents a normalized slack sum value across a set of 1000 generated circuit instances with process variation using 3-sigma normal threshold-voltage and gate effective length distribution [START_REF] Asenov | Random dopant induced threshold voltage lowering and fluctuations in sub-0.1 um MOSFET's: a 3-D atomistic simulation study[END_REF]. The x-axis lists cell id's ranked in ascending order from left to right with respect to its initial slack value for a circuit without PV. It is important to note that a larger slack for a given cell indicates that it has a greater potential to improve circuit delay (increase overall slack) when it is up sized. Also note that cells are originally listed in ascending order with respect to their original slack computed without PV, thus demonstrating that greedily up sizing the most critical gates (left-most gates) does not yield a result in the most delay improvement when increasing their size. In fact, some cells that are not on the critical path yield better delay improvements than cells with smaller slack, as shown with some cells in between 60 and 160 for circuit c432. This behavior can be attributed to cells that may not be initially on the critical path, but are an immediate fan-out of a cell that is, and therefore, increasing their size may cause subsequent up-sizing of their critical transitive fan-in cells, thus improving circuit delay greater than individually sizing a gate on the critical path. For our approach, we then rank the cells by their normalized slack value when considering which cells are more critical with respect to timing when conducting gate sizing.

PV-Aware Gate Sizing Algorithm. We present several extensions to our PV-aware gate sizing approach for yield optimization. Specifically, these extensions are introduced to guide which cells are chosen to be sized first based on their pre-processing characterization result described in the previous subsection. As previously mentioned, the cells which are first considered to be sized are based on their normalized slack sum value acquired during the pre-processing characterization step and are ranked in descending order. Thus, the cells with the largest slack-sum are sized or configured first.

We conduct the same cut-based search gate sizing algorithm presented in Section 5.1. However, we also further prune the potential candidate cells to be sized by sizing cells that fall under an ε-critical path, as well as further selecting cells which are the least constraining cells (smallest size) to be sized. We define the least constraining cells as the set of cells currently in the sizing phase set that are currently configured as the minimum size among the cells belonging to the ε-critical paths. For example, assume that the current ε-set include cells A, B, C, and D with sizes 1X, 1X, 2X, and 3X, respectively. Then, cells A and B are to be considered to be sized first during this phase. To break ties between cells A and B, their respective cost score (Eq. 5) is multiplied by their respective normalized slack sum value. Increasing the size of these cells enable more balanced ε-critical paths, thus, effectively enabling more efficient delay-power trade-offs to be performed in later sizing iterations that achieve tighter delay constraints; this is achieved since optimizing a set of ε-critical prevents from over optimizing a few paths, which may cause certain paths to converge to a timing wall.

Experimental Results

We evaluated our gate sizing approach on a set of benchmarks in ISCAS-85/89, ITC-99 suites, as well as integer arithmetic units consisting of adders (carry ripple, carry-lookahead, Kogge-Stone) and multipliers (array, Dadda). All units were synthesized using a single threshold (HVt) 45 nm open cell library from [START_REF]Nangate FreePDK 45 nm Library[END_REF] under the typical cell configuration. An in-house timing/power engine was implemented in C++ and was correlated to an industrial tool, Synopsys PrimeTime, to be within 10 -3 ps. All results were optimized using identical rules such as ensuring no slew or load violations exists in the final design, as presented in [START_REF] Ozdal | The ISPD -2012 Discrete Cell Sizing Contest and Benchmark Suite[END_REF]. The only differences in our framework is the choice in cell library, which was done in order to enable accurate IVC computations, as well as the choice of circuit benchmarks. In handling slew and load violations, we adopt an iterative approach as proposed in [START_REF] Hu | Sensitivity-guided metaheuristics for accurate discrete gate sizing[END_REF].

The SA of gates and IVC for each circuit were obtained from simulation of random input vectors. However, real application switching activity factors were obtained from mpeg2enc/dec benchmarks from recorded operand values from each unit type, running ARM7TDMI-ISA mpeg2-enc/dec traces [START_REF] Lee | MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems[END_REF][START_REF] Mudge | The SimpleScalar-Arm power modeling project[END_REF]. The initial simulation parameters set were, K = 25%, M = twice the length of average critical path, γ = 0.2, and were fixed across all benchmarks. The delay target for each circuit was set as the median between the achieved delay when all gates were set to their maximal size, and the achieved delay when all gates are at their minimal size. Five duty cycle scenarios (D0=10%, D1=20%, D2=33%, D3=50%, and D4=100%) were considered.

Gate Sizing under Switching Activity and IVC Uncertainty

We first evaluate our sizing algorithm under two gate sizing assumptions: 1) SA+IVC, which considers gate switching activity factors and input vector control in the objective function; and 2) Base, where the objective function uses only nominal gate switching (50%) and average gate leakage values for total energy computation. Table 2 compares the two methods, where Max (%) savings corresponds to the maximum energy improvement achieved over the Base method across the five duty cycle cases (D0 to D4) for each circuit under the same timing constraint. As expected, the maximum improvement observed varies across duty cycles and circuits, motivating the advantage of utilizing accurate power and delay knowledge.

Table 4 provides overall energy improvements across the benchmark suites. The results generated by the new approach achieved a maximum energy improvement of 62% for circuit c2670 and 29% average overall for the same delay.

Figure 6 provides a normalized energy and delay plot for c2670, which illustrates the advantage of using more accurate power and delay information. A delay of 0.87 shows that the Perceived (green) energy deviates from the trend of the Actual (red) energy plot. In performing move-trace analysis, we noted that the Base method caused the algorithm to over-size a few selected critical paths and encountered a timing wall much earlier, whereas SA+IVC was able to efficiently trade-off delay for an additional 0.05 delay units, as shown.

Figure 7 shows a cumulative distribution of gate switching and leakage energies of the max improved result for SA + IVC over Base for circuit c2670. Our approach Table 2. Energy savings when considering gate SA and IVC during the gate sizing procedure over the Base method. The obtained switching and leakage energies are presented for the SA+IVC. The maximum energy deltas (∆ %), corresponds to the max difference in energy profile "perceived" by the Base method during optimization.

shows that accurate knowledge enabled the algorithm to efficiently guide the circuit to a lower energy state, as shown with higher percentage of gates falling under lower energy profiles for both leakage and switching energy. This is important to note since due to the difficulty of comparing gate sizing algorithms, many existing algorithms are sensitivity-based in nature, thus, the ability to guide an algorithm to determine more promising "moves" greatly impacts the optimization procedure.

Table 3 presents results comparing the minimal configuration found by SA + IVC and the perceived minimal configuration obtained by Base. The minimum energy con-Table 3. Energy savings of (SA+IVC) over Base using extracted gate switching activity and input vector control from mpeg2enc/dec applications assuming a (D2) "33%" duty cycle. The units represent an single-adder (32b) and multiplier (8b) configuration of an ARM7TDMI core [START_REF] Mudge | The SimpleScalar-Arm power modeling project[END_REF]. figuration determined was cla432 and dad8, optimized under the same timing constraints determined by the multiplier. For these configurations, our approach shows additional savings in both leakage and switching categories where the majority of the savings for both cases (15% mpeg2enc, 25% mpeg2dec) were achieved by the multiplier circuit. Fig. 6. Energy vs delay plot of c2670. The SA+IVC approach consistently outperforms the Base method.

Energy

Yield Optimization

Figure 8 (a-b) compares the power reduction (%) of using a PV-aware gate sizing approach against one that does not. Each result compares the highest performance target (smallest delay), where both the PV-aware and non-PV-aware solution are able to satisfy. Average power savings of up to 64% and 48% were achieved for ISCAS-85 and ITC-99 benchmarks, respectively. We compare the highest comparable performance delay target since solutions obtained at lower performance delays require few circuit alterations, thus, achieve similar power results. The accurate SA+IVC approach results in a higher percentage of gates at lower energy.

The complete sizing optimization procedure can be observed in Figures 9 and10 for ISCAS-85 and ITC-99 benchmarks, respectively. Two sizing solutions are compared for each benchmark: 1) PV-aware gate sizing (red circle); and 2) non-PV gate sizing (blue triangle). Each point corresponds to a sizing phase where up to K cells are sized simultaneously. Therefore, for each circuit, the gate sizing procedure begins with all cells set to their minimal power configuration and is represented by the right-most point. The left-most point corresponds to the fastest achieved delay for each sizing procedure.

Significant savings were achieved in six out of the eight ISCAS-85 benchmarks since the enhanced PV-aware algorithm was able to avoid hitting a timing wall. The greatest savings were achieved from solutions where the non-PV sizing approach hit the timing wall earlier than the PV approach; however, this is not always the case as shown by one instance where the PV-aware sizing procedure achieved a lower performance delay target than its corresponding non-PV-aware approach as shown in Figure 12 (h), thus, high lighting the optimization uncertainty and room for potential improvement. It is also important to note that in circuit c1355, the target delays between 0.48 and 0.58 show solutions where the non-PV technique obtained superior results, which can be explained by speeding up a larger set of cells that belong in the ε-critical path early in the sizing effort, resulting with potentially more cells sized earlier than needed in order to achieve a lower performance target. However, sizing these ε-paths, enabled more efficient gate sizing, in terms of power-delay trade-offs, to be performed since the circuit was placed at a less-constrained sizing state, where each cell drives a smaller capacitive load, thus reducing the likelihood of getting stuck in a timing wall.

A timing wall scenario can be described where the cells that belong on the ε-critical paths are in such a state that increasing their size no longer improves circuit critical delay. Our experiments show that a gate sizing procedure that focus on the current critical path, result with over-optimizing a small set of critical paths, which in turn increases the convergence rate to an achievable target delay.

Tables 5 and6 present yield results for selected ISCAS-85 and ITC-99 benchmarks. Yield results are acquired from computing the normalized delay and power values from 1000 PV-generated circuits for each benchmark. Timing and power values are reported for each benchmark from two obtained solutions in the previous gate sizing procedure. For fair comparison, each benchmark was optimized to meet an identical delay target. We report results obtained using two scenario optimization assumptions: 1) process variation-aware (PV), which uses the enhanced gate sizing algorithm presented in this 5.2; and 2) non-process variation-aware (nPV), which uses the standard gate-sizing algorithm presented in Section 5.1. The min, max, mean, standard deviation (std.), and variation values are presented for each benchmark. Variation is computed as std.

mean and represents how much each yield result varies with respect to the mean. To summarize the results: ISCAS-85 benchmarks achieved a mean-power savings of 55% (9% min, 84% max), whereas ITC-99 benchmarks achieved a mean-power savings of 25% (2% min, 74% max).

Figures 11 and12 present the cumulative distribution graphs for their respective delay (left-graph) and power (right-graph) yield results for selected benchmarks, as presented in Tables 5 and6. As shown, the circuits optimized using the PV-aware approach achieved significant power yield improvements with respect to target delay yields. Note that although the obtained solutions were originally optimized to satisfy the same target delay under both PV and non-PV gate sizing techniques, their representative yields demonstrate that the PV-aware approach achieved significant yield improvements in both delay and power. For instance, circuit c432 achieved a normalized mean delay yield of 0.875 under the PV scenario compared to 0.920 for the non-PV scenario. Additionally, the delay variation factor of the PV scenario is 22% less compared to the non-PV scenario. Collectively, the PV-aware solutions obtained lower variation factors in 14 out of the 19 studied benchmarks. Significant power reductions are also shown in the respective c432 power yield graphs, achieving an 84% mean-power savings (0.125 PV vs. 0.818 nPV), demonstrating the effectiveness of combining cell characterization and the gradual gate sizing technique over our presented gate sizing technique. Overall, the PV-aware solutions also achieved reduced variation factors in 14 out of the 19 benchmarks.

Conclusion

We have presented a new gate sizing approach that includes the switching activity (SA) and input vector control (IVC) to minimize overall energy. First, the new objective function has several ramifications on the optimization procedure, including the need for reiteration between gate sizing and input vector selection and freezing and unlocking of high-power gates. On a comprehensive set of benchmarks, from ISCAS-85/89, ITC-99, and arithmetic units, synthesized using 45 nm technology, we reduce average actual energy consumption by 30%.

Next, we presented an extension of our gate sizing procedure for conducting delay and power yield optimization under uncertainty. Here, we further improve upon our presented gate sizing procedure to optimize a set of critically identified ε-critical paths in order to mitigate the impact of PV, thus, enabling more efficient delay and power trade-offs to be performed using our gradual gate sizing procedure. Under the yield optimization task, we compare generated solutions from selected circuits in ISCAS-85 and ITC-99 benchmark suites and show significant delay and power yield improvements of up to 55% mean-power savings for ISCAS-85 circuits, and 25% savings for ITC-99 circuits under equivalent timing targets.

We note that our presented techniques are generic in the sense that thermal impacts and multi-V th can be easily addressed using the new optimization procedure.

Fig. 2 .

 2 Fig. 2. Gate sizing optimization flow

Fig. 4 .

 4 Fig. 4. (a) An example of ε critical path (ε path ); the critical path in dashed-red; transitive fan-out output nodes in bold outlines; and ε i corresponds to the absolute delay difference w.r.t to the target delay used for estimating delay cost of a move. (b) The linear run-time of the new gate sizing approach

Fig. 5 .

 5 Fig.5. Impact of independent gate sizing. Gates are ordered left to right in ascending order with respect to their slack (without PV). Larger normalized sum slack values (y-axis) indicate greater ability to improve delay (reduce delay, increase slack) across 1000 generated circuit instances with PV when size is increased to the next discrete size.

Fig. 7 .

 7 Fig.7. Cumulative distribution of leakage and switching energy after sizing for gates in c2670. The accurate SA+IVC approach results in a higher percentage of gates at lower energy.

Fig. 8 .Fig. 9 .Fig. 10 .

 8910 Fig.8. Power savings (%) achieved when comparing generated sizing solutions using a process variation-aware over a non-process variation-aware gate sizing technique. Reported savings are generated from the minimum delay result achieved with respect to each approach.

Fig. 11 .Fig. 12 .

 1112 Fig.11. Selected ISCAS-85 yield result comparing generated 1000 process variation instances with respect to identical target delay using generated solution from: (a) process variation-aware (PV); and (2) non-process variation-aware (non-PV)

Table 1 .

 1 NAND gate leakage values (nW ) for two sizes (X1, X2) based on input vector control (IVC) from a single threshold 45 nm cell library[START_REF]Nangate FreePDK 45 nm Library[END_REF], where min and max leakage states are represented by bold and italicized fonts, respectively.

		NAND-3
	IVC	X1	X2
	000 3.32	13.28		NAND-2
	001 18.18 72.73	IVC	X1	X2
	010 4.21	16.84	00	3.48	13.93
	011 39.49 157.97	01	24.8	99.2
	100 1.29	5.15	10	4.09	16.34
	101 18.78 75.13	11 37.21 148.83
	110 3.76	15.04
	111 55.8 223.22

Table 4 .

 4 Overall energy savings with respect to benchmark suite Benchmark Max Tot Avg. Tot Avg. Sw Avg.

	Lk

Table 5 .

 5 ISCAS-85 : yield results comparing 1000 generated process variation instances from a base circuit utilizing a: 1) process variation-aware (PV); or 2) non-process variation-aware (nPV) technique

	Benchmark Scenario Metric Min Max Mean Std. Variation
	c1355	PV	Delay 0.853 0.983 0.900 0.022 0.956
		nPV	0.862 1.000 0.919 0.023 1.000
		PV Power 0.738 0.946 0.829 0.029 1.000
		nPV	0.827 1.000 0.913 0.027 0.850
	c1908	PV	Delay 0.869 0.980 0.914 0.017 0.943
		nPV	0.887 1.000 0.939 0.018 1.000
		PV Power 0.368 0.457 0.406 0.016 0.980
		nPV	0.818 1.000 0.895 0.036 1.000
	c2670	PV	Delay 0.870 0.994 0.915 0.018 1.000
		nPV	0.872 1.000 0.913 0.016 0.901
		PV Power 0.195 0.233 0.211 0.007 0.830
		nPV	0.801 1.000 0.881 0.034 1.000
	c3540	PV	Delay 0.877 0.966 0.921 0.014 0.974
		nPV	0.899 1.000 0.939 0.015 1.000
		PV Power 0.385 0.504 0.441 0.019 1.000
		nPV	0.825 1.000 0.916 0.033 0.869
	c432	PV	Delay 0.828 0.951 0.875 0.019 0.771
		nPV	0.858 1.000 0.920 0.026 1.000
		PV Power 0.107 0.157 0.125 0.008 1.000
		nPV	0.706 1.000 0.818 0.053 0.992
	c5315	PV	Delay 0.872 0.959 0.906 0.015 0.729
		nPV	0.882 1.000 0.928 0.021 1.000
		PV Power 0.324 0.376 0.347 0.009 0.863
		nPV	0.861 1.000 0.930 0.028 1.000
	c6288	PV	Delay 0.914 1.000 0.946 0.013 1.000
		nPV	0.890 0.968 0.926 0.012 0.940
		PV Power 0.172 0.196 0.182 0.004 0.820
		nPV	0.860 1.000 0.916 0.024 1.000
	c7552	PV	Delay 0.856 0.945 0.891 0.014 0.836
		nPV	0.882 1.000 0.920 0.017 1.000
		PV Power 0.309 0.346 0.328 0.007 0.967
		nPV	0.860 1.000 0.929 0.020 1.000
	c880	PV	Delay 0.822 0.954 0.872 0.021 0.875
		nPV	0.833 1.000 0.891 0.025 1.000
		PV Power 0.640 0.828 0.724 0.037 0.828
		nPV	0.746 1.000 0.841 0.051 1.000

Table 6 .

 6 ITC-99 : yield results comparing 1000 generated process variation instances from a base circuit utilizing a: 1) process variation-aware (PV); or 2) non-process variation-aware (nPV) technique

	Benchmark Scenario Metric Min Max Mean Std. Variation
	b10	PV	Delay 0.720 0.900 0.789 0.029 0.885
		nPV	0.727 1.000 0.809 0.034 1.000
		PV Power 0.486 0.866 0.608 0.057 0.961
		nPV	0.571 1.000 0.703 0.068 1.000
	b11	PV	Delay 0.748 0.912 0.806 0.024 0.620
		nPV	0.759 1.000 0.849 0.041 1.000
		PV Power 0.193 0.247 0.219 0.009 0.663
		nPV	0.682 1.000 0.841 0.052 1.000
	b12	PV	Delay 0.749 0.946 0.815 0.035 1.000
		nPV	0.775 1.000 0.834 0.029 0.802
		PV Power 0.285 0.389 0.332 0.019 0.837
		nPV	0.673 1.000 0.815 0.056 1.000
	b13	PV	Delay 0.707 0.885 0.772 0.026 0.683
		nPV	0.760 1.000 0.846 0.042 1.000
		PV Power 0.579 0.874 0.698 0.046 0.849
		nPV	0.630 1.000 0.756 0.058 1.000
	b14	PV	Delay 0.816 0.925 0.847 0.016 0.974
		nPV	0.885 1.000 0.928 0.018 1.000
		PV Power 0.546 0.664 0.587 0.017 1.000
		nPV	0.838 1.000 0.906 0.024 0.943
	b15	PV	Delay 0.833 0.926 0.866 0.014 0.888
		nPV	0.893 1.000 0.938 0.017 1.000
		PV Power 0.545 0.675 0.602 0.023 0.910
		nPV	0.789 1.000 0.867 0.037 1.000
	b17	PV	Delay 0.896 0.984 0.929 0.013 1.000
		nPV	0.912 1.000 0.943 0.013 0.993
		PV Power 0.864 0.978 0.903 0.016 0.995
		nPV	0.899 1.000 0.937 0.017 1.000
	b18	PV	Delay 0.873 0.946 0.897 0.010 0.841
		nPV	0.919 1.000 0.949 0.013 1.000
		PV Power 0.886 0.978 0.906 0.008 0.949
		nPV	0.907 1.000 0.930 0.009 1.000
	b20	PV	Delay 0.814 0.901 0.845 0.015 0.665
		nPV	0.857 1.000 0.912 0.024 1.000
		PV Power 0.863 0.967 0.902 0.015 0.875
		nPV	0.881 1.000 0.928 0.018 1.000


Sk Subidh

Samah Mohamed Saeed

Ozgur Sinanoglu

Ramesh Karri
email: rkarri@nyu.edu

New Scan-Based Attack Using Only the Test Mode And An Input Corruption Countermeasure

Keywords: AES, Scan Chain, Scan Attack, Scan-based DFT, Testability, Security

Scan-based design-for-testability, which improves access and thus the test quality, is highly vulnerable to scan attack. While in-field test is enabled through the scan design to provide debug capabilities, an attacker can leverage the test mode to leak the secret key of the chip. The scan attack can be thwarted by a simple defense that resets the data upon a switch from the normal mode to the test mode. We proposed a new class of scan attack in [15] using only the test mode of a chip, circumventing this defense. In this book chapter we extend our earlier work by introducing case studies to explain this new attack in greater detail. Furthermore, we study the effectiveness of existing countermeasures to thwart the attack and propose a new input corruption countermeasure that requires a smaller area overhead compared to the existing countermeasures.

Introduction

Scan-based design-for-testability (DFT) technique is widely used, which provides internal access to the circuit in order to enhance the testability of manufacturing defects. To provide debug capabilities, in-field test is enabled, by retaining scan capabilities. However, the scan design can be misused by an attacker to leak secret information of a crypto-chip. The intermediate results of a crypto-chip can be shifted out during the test mode through the scan interface. This attack is known as a scan-based side-channel attack, and was reported first in [START_REF] Yang | Scan Based Side Channel Attack on Dedicated Hardware Implementations of Data Encryption Standard[END_REF], which targets Data Encryption Standard (DES) chip. The attacker applies the plaintext in the normal mode after which he/she switches to the test mode to observe the intermediate result of the DES chip. With this information in hand, the attacker can retrieve the secret key by applying differential analysis on the response patterns. Scan-based side-channel attack can also reveal the 128-bit secret key of Advanced Encryption Standard (AES) chip even in the presence of advanced DFT techniques such as partial scan [START_REF] Kapur | Security vs. test quality: are they mutually exclusive?[END_REF], X-masking [4], and X-tolerant architecture [START_REF] Ege | Differential Scan Attack on AES with Xtolerant and X-masked Test Response Compactor[END_REF][START_REF] Darolt | Scan Attacks and Countermeasures in Presence of Scan Response Compactors[END_REF]. Other ciphers such as RSA [START_REF] Nara | Scan-based side-channel attack against rsa cryptosystems using scan signatures[END_REF][START_REF] Darolt | A New Scan Attack on RSA in Presence of Industrial Countermeasures[END_REF], ECC [START_REF] Nara | Scan-based attack against elliptic curve cryptosystems[END_REF][START_REF] Da Rolt | A scanbased attack on elliptic curve cryptosystems in presence of industrial design-for-testability structures[END_REF], and stream ciphers [START_REF] Liu | Scan-based attacks on linear feedback shift register based stream ciphers[END_REF], are also vulnerable to scan attack.

The existing scan-based attacks switch the chip between the normal mode and the test mode and assume that the content of the scan cells is retained intact. A mode-reset countermeasure [START_REF] Hely | Test Control for Secure Scan Designs[END_REF] thwarts these attacks by resetting the scan cells upon switching from the normal mode to the test mode.

We proposed a new scan-based attack on AES using only the test mode to circumvent the mode-reset countermeasure [START_REF] Ali | New scan-based attack using only the test mode[END_REF]. The attack showed how to overcome the challenges introduced by the mode-reset countermeasure and to leak the secret key of a AES crypto core. In this book chapter we explain the attack in greater detail with case studies. We also discuss some of the existing countermeasures and their effectiveness against our test-mode-only attack. We also propose a novel cost-effective input corruption countermeasure, crafted to thwart our test-mode-only scan attack.

The remainder of the paper is organized as follows. Section 2 provides background on AES and DfT. Section 3 provides motivations and challenges of the test-modeonly attack. Section 4 describes the proposed test-mode-only attack. Section 5 gives an overview of the existing countermeasures against scan attacks while Section 6 provides a new countermeasure to thwart the test-mode-only attacks. Finally, we conclude the paper and elaborate on our future work in Section 7.

Preliminaries 2.1 AES

AES is a 128-bit symmetric key block cipher available in three different key lengths: 128, 192 and 256 bits. The entire AES algorithm is divided into several identical round operations. The number of rounds in the three different versions of AES are 10 (128bit key), 12 (192-bit key) and 14 (256-bit key) respectively. Each round comprises of following four basic transformations, -SubBytes is a non-linear substitution operation.

-ShiftRows is the byte-wise permutation.

-MixColumns is the four-byte mixing operation -AddRoundKeys is the XORing the state with the round key.

We will refer to these operations as SB, SR, MC and ARK respectively. Figure 1 shows the structure of first round of AES which contains an extra key XORing at the beginning.

Each transformation of AES round has specific properties. We use the following properties in our attack.

Differential Properties of AES

In S-box, for an input X and the input difference α, the output difference β is represented as

β = SB(X ⊕ α) ⊕ SB(X) (1)
For a given value of (α, β ), there could be two, four or no solution of X [START_REF] Nyberg | Generalized feistel networks[END_REF]. In case of two solutions, if one solution is δ , the other solution will always be δ ⊕ α. On the other hand for four solutions, the solutions will be δ , δ ⊕ α, 0 and α.

Shift Rows

S S S S S S S S S S S S S S S S

′ 15 k ′ 14 k ′ 13 k ′ 12 k ′ 11 k ′ 10 k ′ 9 k ′ 8 k ′ 7 k ′ 6 k ′ 5 k ′ 4 k ′ 3 k ′ 2 k ′ 1 k ′ 0 r15 r14 r13 r12 r11 r10 r9 r8 r7 r6 r5 r4 r3 r2 r1 r0 k15 k14 k13 k12 k11 k10 k9 k8 k7 k6 k5 k4 k3 k2 k1 k0
Fig. 1. First round of AES: p i is the plaintext byte, k i is the initial key byte, q i is the SR output byte, k i is the round key byte, and r i is the round output byte Lemma 1. For a given input X and two one-bit differences e i and e j (where e i and e j are eight bit strings with a 1 in position i and j respectively where i = j), the output differences d i and d j are generated as

d i = SB(X) ⊕ SB(X ⊕ e i ) d j = SB(X ⊕ e j ) ⊕ SB(X ⊕ e j ⊕ e i )
For any value X, d i can not be the same as d j .

Proof. We prove this by contradiction. Let as assume that there is a value x of X for which d i = d j . We also have y = x ⊕ e j . Therefore, we have two equations:

d i = SB(x) ⊕ SB(x ⊕ e i ) d j = SB(y) ⊕ SB(y ⊕ e i ),
where d i = d j implies x and y are the two solutions of (1) where β = d i = d j and α = e i . If x and y are the two solutions of the equation, then either y = x ⊕ e i or one of these two values must be zero and the other equals e i . If we consider the first case then y = x ⊕ e i ⇒ x ⊕ e j = x ⊕ e i ⇒ e j = e i which contradicts our assumption. Let us consider the second case, x = 0 and y = e i which implies y = x ⊕ e j = e i ⇒ e j = e i . Again this contradicts our assumption. Therefore, d i and d j can not be the same under the given condition.

DFT Structure

Scan design is a well-known DFT technique that provides direct access to flip-flops. Scan design converts each flip-flop into a fully accessible scan cell that can be controlled and observed easily through shift operations. Due to the limited number of tester channels, especially for integrated circuits with a large number of input/output pins, boundary scan design [START_REF]IEEE Standard Test Access Port and Boundary-Scan Architecture[END_REF] is used, which associates a boundary scan cell to each primary input/output of the circuit (BSC in Figure 2). Boundary scan design enables a cost-effective few-pin access to the primary inputs/outputs in the test mode. On one hand, in the normal mode, the input pins directly drive the primary inputs (PIs) of the chip, while the primary outputs (POs) drive the output pins. On the other hand, in the test mode, the boundary scan cells break the connection between the chip pins and the primary input/outputs. The test mode consists of shift and capture operations. During shift operations, the test vectors are serially shifted into the scan chains through the chip input pins, while test responses can be observed through the chip output pins. During the capture operation, the scan cells capture the response of the combinational logic, while the boundary scan cells drive the PIs and capture the POs. As a result, there is no direct path from the chip inputs to the primary inputs in the test mode.

System Logic Chipin1 Chipin2 Chipout2 Chipout1 PI1 PI2 PO3 PO4 BSC1 BSC2 BSC3 BSC2 Fig. 2.
DFT structure for a design with two scan chains; TDI/TDO pins not shown

Motivation and Challenges

In this section we review the existing state-of-the-art scan attack on AES and discuss its limitations. Subsequently, we elaborate on how to overcome these limitations and propose a new scan attack on AES: test-mode-only scan attack.

State-Of-The-Art Scan Attack

The state-of-the-art scan attack requires switching between the normal and test modes. Figure 3 shows the AES core with a single scan chain which consists of AES round register flip-flops (SC in the figure). In the normal mode, a plaintext is applied to the AES core through the primary input and the results are stored in the round register.

The round register content is again applied to the AES in the next round operation. The round operation is highlighted green in Figure 3. After completion of ten rounds the ciphertext output is generated at the primary outputs. In the test mode, the flip-flops of the round register are connected into a scan chain. During the shift cycle a test vector is shifted to the scan chain, while in the capture cycle the response of the AES core is captured and shifted out through the SO line. The attack works in two steps. In the first step, the chip is run in the normal mode with a desired input plaintext applied from the primary inputs for only one round of AES. The round output is stored in the round register. Then, in the second step, the chip is switched to the test mode and the stored round output is shifted out through the SO line by applying repeated shift cycles. These two steps are repeated for different plaintexts.

The attack uses one of the basic differential properties of the AES round operation. In AES, if one-bit difference is applied in the least significant bit of any one of the sixteen bytes, the output difference can have 18 possible hamming distances. Out of these hamming distances, only four can be generated by a unique pair of S-box inputs. Therefore, the attacker should follow the above two steps for all possible 2 7 pairs of plaintexts, in order to get any such hamming distance. Once the hamming distance is observed, the corresponding key byte is retrieved by XORing the plaintext byte with the corresponding unique pair of S-box inputs. Therefore, each unique pair will produce two possible key bytes. The same procedure is repeated for all the sixteen key bytes. Finally, by applying 2 7 • 16 = 2 11 plaintext pairs, the search space of the AES key is reduced to 2 16 . These 2 16 key hypotheses can be brute-forced by using the plaintextciphertext pairs in negligible time.

Limitations of the Existing Scan Attacks

One fundamental limitation of this kind of attacks is that they require switching from the normal mode to the test mode under the assumption that the data in the scan cells can be preserved intact during the switch. One simple countermeasure is resetting the device whenever there is a switch from the normal mode to the test mode. In this case, the attacker can perform the first step of the attack and the round output will be stored in the round register. However, whenever the second step of the attack is applied i.e., switching to the test mode, the content of the SCs will reset. Hence, the second step will only produce the zero response of the AES core. Therefore, any scan attack that requires switching between the normal and test modes is bound to fail against this simple countermeasure.

Overcoming the Limitations of Existing Scan Attacks

In order to overcome the limitations of the above attack, the attacker must come up with an attack that will only use the test mode. As there is no switching required from the normal mode to the test mode, the aforementioned mode-reset countermeasure will be circumvented. The attacker is then constrained to use only the operations highlighted in blue and green in Figure 3.

The major challenge associated with such an attack is to apply the desired input plaintext to AES. As explained in Section 2.3, the primary inputs are not directly accessible in the test mode. The inputs should rather be applied by shifting them in as test vectors through SI line. However, the problem is that the attacker does not know which scan cell drives which input of AES. The physical placement tools determine the mapping between scan cells and the AES inputs.

We need to leverage some of the basic differential properties of AES to (1) find out the exact order of the scan cells which correspond to the AES input register, and (2) launch the attack and leak out the secret key.

Test-Mode-Only Attack on AES

In this section we explain our test-mode-only attack on AES [START_REF] Ali | New scan-based attack using only the test mode[END_REF]. In this attack, the plaintexts are applied in the form of test vectors. Before going into the detail of the attack we first define the attackers ability in the form of the resources and information he/she has. As in the conventional scan attack, we assume that the attacker knows the AES algorithm running inside the security chip and the in-field debug of the chip is enabled. For the sake of simplicity, we assume that there are only 128 scan cells in the design, which correspond to the 128-bit round register.

Let us first consider one example of AES operation. Figure 4 shows the results corresponding to each step of the AES first round, and finally the corresponding roundoutput difference. P and P 120 are the two plaintexts (120 is the bit position of 1 from the right), while K 0 and K 1 are the first and the second round keys, respectively. It may be noted that K 0 is the whitening key, which is also the 128-bit AES key. The goal of the attacker is to retrieve K 0 . The values in the figure are represented in 32-digit hexadecimal format.

In test-mode-only attack, the major challenge to the attacker is to figure out which scan cell corresponds to which input bit of AES. For P, the test vector is same as the plaintext. However, in order to apply P 120 , the attacker should precisely know which scan cell corresponds to the 120-th input bit of AES. Therefore, to attack AES using only the test mode the attacker has to determine the mapping between the scan cells and the AES inputs. The mapping is determined by the physical placement tool and it is considered as almost random. We determine the mapping in three steps. In the first step, we determine the scan cells corresponding to the AES words. The second step determines the scan cells corresponding to the AES bytes. In the third step, the order of the bytes in a word is determined. Finally, we determine the order of the scan cells in a byte, and identify the corresponding key. Once we have the key bytes, we combine them as per the assumed order, and deduce the possible key hypotheses. In the next subsection, we explain the first step.

S--box Shi)Rows MixColumns S--box Shi)Rows MixColumns P=00000000000000000000000000000000 P 120 =01000000000000000000000000000000 K 0 =000102030405060708090A0B0C0D0E0F K 0 =000102030405060708090A0B0C0D0E0F 010102030405060708090A0B0C0D0E0F 7C7C777BF26B6FC53001672BFED7AB76 7C6B6776F201AB7B30D777C5FE7C6F2B 547543642C6D3351B0D95D61279C215C K 1 =D6AA74FDD2AF72FADAA678F1D6AB76FE K 1 =D6AA74FDD2AF72FADAA678F1D6AB76FE 000102030405060708090A0B0C0D0E0F 637C777BF26B6FC53001672BFED7AB76 636B6776F201AB7B30D777C5FE7C6F2B 6A6A5C452C6D3351B0D95D61279C215C BCC028B8FEC241AB6A7F2590F13757A2 82DF3799FEC241AB6A7F2590F13757A2 3E1F1F21000000000000000000000000

Determining the Mapping Between Scan Cells and AES Input Words

Similar to Figure 4, we use two types of test vectors. One with all zero bits (P) and the other (P i ) with only one bit set to one (i-th bit where 0 ≤ i ≤ 127) and the rest of the bits set to zero. At first, the test vector P is shifted in and the response R is captured and shifted out. It may be noted that R is the jumbled up value of the round output BCC028B8FEC241AB6A7F2590F13757A2.

Next, in each step a test vector P i is shifted in and the corresponding response R i is captured and shifted out. The difference D i = R ⊕ R i will pinpoint the positions where the bits are flipped. In our example, P 0 and P 120 differ in the 120-th bit. For this input pair, we apply a one-bit difference to the leftmost input byte. The figure shows that the output difference (0x3e1f1f21) confines within only the leftmost four bytes of the same word. The one-bit input difference affects only one output word. Therefore, two such input differences in the same input word will affect the same output word. We use this property of AES to partition the scan cells into AES input words.

Say, D j i is the j-th bit of D i and FD i = { j| D j i = 1}. So, FD i is the set of output bit-flip positions corresponding to input bit-flip at i. In 128 iterations, 128 different sets of output bit-flip positions (FD = {FD i |0 ≤ i ≤ 128}) are generated. These 128 sets are combined into four sets by considering the common bit-flip positions in the sets.

Algorithm 1 describes the detailed procedure, where Enc() is the AES round function. The first loop determines the 128 sets FD 0 . . . FD 127 . In the second loop, in each iteration, a set FD x is chosen from FD, and compared with the rest of the sets for common output bit-flip positions. If a common bit-flip position is found in any set (FD y ), both sets are combined into one set (FD x ) and the new set (FD y ) is deleted from FD. Therefore, at the end of the iteration, FD x will have all the output bit-flip positions, which correspond to a particular word. These bit-flip positions, which represent the positions of the scan cells, are saved in W i . Hence, four iterations of the second loop will partition the 128 scan cells into four words W 0 . . .W 3 , which correspond to four different MC operations of AES.

Algorithm 1: Determining the bits in the words Input: P and P i where 0

≤ i ≤ 127 Output: W 0 ,W 1 ,W 2 ,W 3 R = Enc(P) for i = 0 to 127 do R i = Enc(P i ); D i = R ⊕ R i for j = 0 to 127 do if D j i = 1 then FD i = FD i ∪ j end end FD = FD ∪ FD i end for i = 0 to 3 do Select any element FD x from FD FD = FD -FD x for Each element FD y in FD do if FD x ∩ FD y = / 0 then FD x = FD x ∪ FD y ; FD = FD -FD y end end W i = FD x end

Determining the Mapping Between Scan Cells and AES Input Bytes

In order to determine the mapping between scan sells and AES input bytes we use Lemma 1. Similar to previous step, we create four test vectors: P, P i , P j and P i j . We already have the response for the base plaintext P. Now we choose any two bit positions, say i and j, where i = j. We then create P i and P j . Say the byte corresponding to bit i is B l , where 0 ≤ l ≤ 15. We get the response R i = Enc(P i ) corresponding to P i . Therefore, the difference is D i = R ⊕ R i . It may be noted that any non-zero value in D i is due to the input difference in byte B l from the plaintext pair (P, P i ). In the rest of the 15 bytes, both plaintexts have the same values.

Next, we create P j and P i j , where P i j is the same as P j except in the i-th bit, which is also 1; P i j has only two ones in positions i and j. It may be noted that the j-th bit may be in the same byte as the i-th bit or in a different byte. We get the response R j = Enc(P j ) and R i j = Enc(P i j ) corresponding to plaintexts P j and P i j respectively. Therefore, we have another difference D j = R j ⊕ R i j . Still, this difference is due to the input difference in byte B l generated from the plaintext pair (P j , P i j ).

Now there are two possibilities: the j-th and the i-th bits are either in different bytes, or in the same byte B l . Let us consider the first case; the input difference in byte B l is only due to the flip in the i-th bit which is the same for both plaintext pairs (P, P i ) and (P j , P i j ). Therefore, the differences D i and D j corresponding to the two plaintext pairs will be the same. On the other hand if the i-th and j-th bits are both in B l , then we have the same input difference corresponding to bit i, but in addition to other differences as well. Therefore, as per Lemma 1, this should result in different output differences; the MC operation is linear. Therefore, D i and D j will be different in the second case.

For example in Figure 5, the two plaintext pairs (P, P 124 ) and (P 120 , P 124,120 ) have two bit-flips with respect to P; one in the 124-th bit and the other one in the 120-th bit. It may be noted that both bit-flips are in the same byte. Therefore, we have two different input pairs with the same input differences (in bit position 124). Hence, the output difference should always be different. As shown in the figure, the output differences D 0 and D 2 are unequal. If the second bit-flip (120-th) were in a different byte, say in the 100-th bit, the corresponding output differences would be the same. Therefore, by comparing the output differences we can determine whether the two input bit-flips are in the same byte. This way by flipping bits in input pairs we can partition the bits into the AES bytes.

D 0 =R⊕R 124 =49A9A9E0000000000000000000000000 01001001101010011010100111100000 D 1 =R⊕R 12o =3E1F1F21000000000000000000000000 00111110000111110001111100100001 P =00000000000000000000000000000000 P 124 =10000000000000000000000000000000 P 120 =01000000000000000000000000000000 P 124,120 =11000000000000000000000000000000 AES Round R =BCC028B8FEC241AB6A7F2590F13757A2 R 124 =F5698158FEC241AB6A7F2590F13757A2 R 120 =82DF3799FEC241AB6A7F2590F13757A2 R 124,120 =6521C980FEC241AB6A7F2590F13757A2 D 2 =R 120 ⊕R 124,120 =E7FEFE19000000000000000000000000 D 0 =R 0 ⊕R 124 =49A9A9E0000000000000000000000000
Fig. 5. Four inputs and the corresponding one round outputs, and the differences So one can determine whether two different bits are in the same byte by just observing the output differences D i and D j , and checking whether they are different. In order to determine the same for all the bytes, we follow Algorithm 2. It takes the set of bits W corresponding to a word, which is generated in the previous step, and partitions the bits into four bytes B 0 . . . B 3 . The outer loop selects a bit from W and passes it to the inner loop. The inner loop finds all the bits, which lie in the byte that corresponds to the given bit. The four iterations of the outer loop determine the four bytes B 0 . . . B 3 . In order to reduce the number of test vectors, we can use a single pair of test vectors to identify the differences in all the four words in one shot. As the four MC operations of AES in a round are independently calculated, we can apply the above technique to determine the bytes in all the four words simultaneously by flipping bits in four words of the input plaintexts. Therefore, the number of input test vectors will reduce by four.

Algorithm 2: Determining the bits in the bytes

Input: W Output: B 0 , B 1 , B 2 , B 3 for l = 0 to 3 do B l = / 0; W t = / 0 Select i where i ∈ W B l = B l ∪ i ; W = W -i; P i = P ⊕ (0x1 i) R i = Enc(P i ); R = Enc(P); D i = R ⊕ R i for Each j ∈ W do W = W -j P j = P ⊕ (0x1 j); P i j = P j ⊕ (0x1 i) R j = Enc(P j ); R i j = Enc(P i j ); D j = R j ⊕ R i j if D i = D j then B i = B i ∪ j end else W t = W t ∪ j end end W = W t ; W t = / 0 end
Note It may be noted that there could be more than 128 registers in the AES design. However, these extra registers can be identified by considering their effects on the AES round output. If the registers are not part of the round operation (e.g. AES controller registers), they will not affect the round output. If they are part of the round operation, their effect on the output will reveal their position in the round operation. Once identified, the extra registers can be discarded in the attack.

Determining the Order of Bytes in a Word

In this section, we try to determine the position of each byte in the words. In order to do that, we use the properties of the AES MC operation. Figure 6(a) shows the basic operation of AES MC in terms of a matrix multiplication operation. As illustrated in Figure 6(b), if there is a non-zero value a in only one of the four input bytes, the output bytes will have values (a, a, 2a, 3a). We analyze the hamming distance to determine the order of the bytes. As per the AES MC operation, two of the four output bytes will always have the same hamming distance (two output bytes with values a).

2 3 1 1 1 2 3 1 1 1 2 3 3 1 1 2 MixColumn b 0 b 1 b 2 b 3 a 0 a 1 a 2 a 3
We apply two plaintexts (P and P ) in a way that only one input byte of the MC operation gets a non-zero difference and the rest of the three bytes all get zero differences. Say we have scan cells corresponding to the four bytes B 0 , B 1 , B 2 , B 3 of a word. We need to find the actual order of these bytes corresponding to MC, i.e., to a 0 . . . a 3 in Figure 6(a). If the input difference value a is applied in B 0 , the output difference value 2a should be loaded in this byte. We need to determine which two bytes will have the same hamming distance. However, for some value of a, the rest of the three bytes (other than the byte B 0 ) may have the same hamming distance.

We experimentally observed that in 52 out of the 255 different values of a, more than two bytes will have the same hamming distance. We need to try at least 53 different values of a to exactly know the two bytes that correspond to the output differences a and a respectively. Say, B 2 and B 3 are the two bytes. Then we also determine that B 1 corresponds to the output difference 3a. However, as B 2 and B 3 have the same value, we can't directly identify the order of these two bytes. In order to determine their order, we next apply the input difference to the byte B 1 . Then B 0 corresponds to output difference a, and either B 2 corresponds to a and B 3 corresponds to 3a or vice versa. In the first case, the exact order of the four bytes is identified to be (B 0 , B 2 , B 3 , B 1 ), which corresponds to the first of the four cases presented in Figure 6(b). We can have three more possible permutations, which are the circular rotations of this permutation. The procedure is repeated for the rest of the three words. It may be noted that instead of applying difference in one byte at a time, we can apply the byte difference in four words corresponding to four different MC operations, which will help determine the order of the bytes in the four words simultaneously. So, given the four bytes in a word, we can tell the four possible permutations as per the AES input.

Determining the Order of Bits in a Byte

At this point, we do not know which scan cell corresponds to which bit of a given byte although we know the order of the bytes. If we apply the existing attack [START_REF] Ege | Differential Scan Attack on AES with Xtolerant and X-masked Test Response Compactor[END_REF] by varying the input pairs in order to get a particular hamming weight, we will uniquely determine the key byte. In our case we don't know the exact value of the input plaintext as we do not know the order of the bits in a byte. Therefore, the key byte which we determined is corresponding to the assumed order of the scan cells in the bytes. Eight scan cells corresponding to a byte can be arranged in 8! 4!•4! = 70 (consider the average case where half of the bits are one and rest are zero) ways. Therefore, in average each byte can have 70 possible values. If we combine all the sixteen bytes we get (10) 16 values, which is a large number. Therefore, we must determine the order of the scan cells.

We develop a new technique to determine the key despite the unknown order of the scan cells in the byte. In this scheme, instead of considering the difference in any particular bit, we consider eight different differences, each corresponding to a one-bit difference in one of the eight input bits. As all the bits are considered, the output signature is irrespective of the order of the bits. In order to do that, we choose an input plaintext P with all zero bits. Therefore, the chosen byte will have the value B = 00000000. Then we produce eight different plaintexts P 0 to P 7 by varying the bit-flip position 0 to 7.

Let us consider the chosen byte is the first byte. Then the first bytes of the eight plaintexts are 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, and 0x80. It may be noted that in these eight values, the bit-flip position varies from the right-most bit to the leftmost bit. Each of these eight plaintexts is paired with P. We compute the output difference D i ( 0 ≤ i ≤ 7) of each pair and get the hamming distance. From D i we get the hamming distance of the four bytes. Two of these bytes will have the same hamming distance as shown in Figure 6(b). So, we consider only one of these two.

We maintain a signature table where, for each value of K, we have eight the threebyte hamming distances corresponding to eight input differences. The values are shown in Table 1. The data in the table shows that the last eight columns uniquely determine the row. Therefore, given eight hamming distances corresponding to eight input differences, one can uniquely determine the value of K, which is the key byte itself. It may be noted that we have sixteen tables corresponding to sixteen S-boxes of AES. We need to search the eight hamming distances in all the sixteen tables.

Algorithm 3 shows the detail technique of determining the value of the key byte and the order of the bits in a byte. The attacker get the output differences corresponding to eight pair of plaintexts. She then determines the four output bytes which have got the non-zero output differences. The function Trim() determines four none-zero bytes and reduce them to three after removing the duplicate one. HD will have eight hamming distances correspond to eight input differences. These eight value are searched in the rows of Table 1. When a row matches, the value of K corresponding to that row is the value of the key byte. The position of the bit is determined by the column index of the hamming weight corresponding to the bit. The position of the i-th bit is the index of the column of HD i in the row K. Algorithm 3: Determining the key byte and the order of the bits in a byte Input: P and P i where 0 ≤ i ≤ 7

Output: Key and order of the bits

HD = / 0 R = Enc(P) for i = 0 to 7 do R i = Enc(P i ) D i = R ⊕ R i HD i = Trim(D i ) /*Getting three bytes*/ HD = HD ∪ HD i end for K = 0 to 255 do
Search HD in row K of Table 1 if All elements of HD is found in row K then Key=K Order of the bit is the column index of the element of HD end end

Determining the AES Key

In the previous section, we determine the order of the scan cells in a byte as well as the key corresponding to the byte. Now we have to determine the order of bytes in a word (Section 4.3). We have four possible permutations of the four bytes in a word. Therefore, if we know the position of the four words, then there will be 4 4 = 2 8 possible values of the key. However, we don't know the order of the four words, which can be arranged in 4! = 24 ways. The total possible hypotheses of the AES key is 24 • 256 = 6144 = 2 12.58 . As we know the plaintext and the ciphertext, we can brute-force the key hypotheses in negligible time.

Attack Complexity Analysis

In the first step of the attack (Section 4.1), we need 128 + 1 = 129 test vectors to partition scan cells into the AES words. In determining the bytes in a word in the second step (Section 4.2), we need (1+31•2)+(1+23•2)+(1+15 * 2) = 141 test vectors. For getting the order of the bytes in a word in the third step (Section 4.3), we used 52 • 2 = 104 test vectors. In the fourth step (Section 4.4), where we determine the order of the bits in bytes, we don't need any extra test vectors, because the required test vectors are already available from the first step. Therefore, in total we need 129 + 141 + 104 = 375 test vectors to determine the secret key.

Regarding the time complexity, it can be observed that most of the execution time is spent on partitioning the scan cells corresponding to bytes and in determining the order of bits in a byte. For the first part, the time complexity is 31 + 15 + 7 = 53. In the second part the time complexity is 256 • 8 = 2 11 . However, the final key hypotheses is around 2 12.58 , which need to be brute-forced to get the master key. Therefore, the time complexity of the complete attack is 2 12.58 .

Existing Countermeasures

So far we have shown that the mode-reset countermeasure, which provides protection against all the existing attacks, fails against the proposed test-mode-only attack. In this section we discuss some of the other existing countermeasures and their level of effectiveness against our proposed test-mode-only attack. Our goal is to devise a countermeasure for our attack.

Insertion of Inverters in the Scan Path

In this technique the scan chain is divided into multiple subchains in the form of a scan tree [START_REF] Sengar | An efficient approach to develop secure scan tree for crypto-hardware[END_REF]. The subchains are placed in a random order so that it will be difficult for the attacker to figure out the exact round output. Some of the scan cell values are flipped by placing inverters selectively on the scan paths (Figure 7). The location of the inverters is known only to the designer or the tester. Therefore, only the designer or the tester can retrieve the exact response of the chip, while the attacker can only observe the modified response of the chip. In the differential scan attack, such countermeasures will fail, as the effect of the inverters will be cancelled out in the output difference. Therefore, the proposed testmode-only attack can easily overcome this countermeasure through the differential analysis it employs. In the same way, our proposed scan attack can thwart the scan scrambling technique proposed in [START_REF] Hély | Scan Design and Secure Chip[END_REF].

Masking

There are two masking countermeasures proposed in [START_REF] Darolt | Scan Attacks and Countermeasures in Presence of Scan Response Compactors[END_REF]. The first method masks the 128-bit round register and then unmasks it for the subsequent round operation. The mask value is generated by using an input and a key of size 128-bit (Figure 8). During the normal operation, the masking remains transparent. In the capture operation during the test mode, the scan chain captures the masked response of the circuit. Only the tester and the designer have the knowledge about the mask value. Therefore, they can unmask the scan output and retrieve the actual response of the circuit. On the other hand, the attacker will be unable to retrieve the actual response, hence failing to apply the differential analysis to reveal the secret key. Thus the attack will fail. The drawback of this countermeasure is not only the area overhead, but also the prolongation of the critical path, and thus the performance degradation.

Round Register

AES Round

Mask Func2on

Input 128-bit Key 128-bit Fig. 8. Round register masking To overcome the critical path issue, a second masking technique is proposed, which modifies the response compactor output (Figure 9). This technique is based on an enhanced Linear Feedback Shift Register (eLFSR), which can either operate as a register or an LFSR. In the test mode, the LFSR output is XORed with the response compactor output bit-stream. Therefore, each compacted slice is XORed with a pseudorandom bit. A 128-bit LFSR is used to prevent the attacker from retrieving the initial state of the LFSR. Although the countermeasure has no impact on the critical path delay, the area overhead remains a problem, which is around 5% of the AES chip.

Noise Injection In the Scan Output

This technique is similar to the previous masking technique. It includes two levels of security: one is the LFSR and the other one is the True Random Number Generator (TRNG) [START_REF] Das | Security analysis of industrial test compression schemes[END_REF]. Figure 10 shows the architecture of the countermeasure. In this case, the masking values are controlled by both the LFSR and the TRNG. Therefore, on average

On-chip Comparison of Responses

The countermeasure in [START_REF] Da Rolt | On-chip test comparison for protecting confidential data in secure ics[END_REF] provides a scan protection scheme using an on-chip comparison of the circuit response and the expected response that is shifted in. The attacker can only observe a one pass-fail bit per test vector, which is insufficient to leak the secret key of the chip. Similar to the traditional test process, the test vector is shifted into the scan architecture during the shift operations. Then, the response is captured during the capture operation. Instead of shifting out the captured response, the expected response is shifted in through another pin that replaces the scan output pin, while shifting in the next test vector by using the scan input pin. This countermeasure performs an on-chip comparison, which produces a pass, only when the whole captured response matches the expected response. The test time and data volume is the same compared to traditional testing. This countermeasure impacts the diagnosis and debug capabilities of the IC, as the entire information about the IC under test consists of one pass-fail bit per test vector. To support the diagnosis of the IC, an expected faulty response of one fault at a time is shifted into the scan architecture instead of the fault-free response, which is compared with the captured response. However, such procedure is only valid for modeled faults. Furthermore, the diagnostic time becomes unaffordable.

Proposed Countermeasure

As we have seen in the previous section, there are various proposed countermeasures to provide a certain level of security against scan-based side-channel attack. However, all these countermeasures have been proposed with the existing scan attack model in mind, thus failing to provide protection against a fundamentally different attack model, such as the proposed test-mode-only attack. In this section, we present a countermeasure judiciously crafted for the test-mode-only attack that relies on the access to the scan input pin, which no other existing scan attack requires.

Our proposed test-mode-only attack is based on launching an individual bit-flip from each scan cell in the round register independently of the remaining scan cells. Disabling this capability will prevent the attacker from mapping each scan cell to its corresponding word and byte of the AES. We propose a defense mechanism, which injects random noise by randomly flipping the bits of the test vectors, while they are shifted through the scan input pin, hampering the attack's ability to classify scan cells into words and bytes. The LFSR randomly selects the locations of the bit-flips of each test vector. The LFSR generates a new bit per clock cycle that is XORed with the shifted test vector bit. In other words, the shifted bit is flipped if the output of the LFSR is one. No countermeasure for the existing scan attacks has considered the alteration of the test vector shifted through the scan input pin, mainly because the previously proposed scan attacks assume that the attacker can apply the plaintext through the primary inputs.

Without the capability of controlling the data delivered into the scan cells, the attacker fails to launch the desired bit-flips. The attacker thus needs to circumvent this defense by deciphering the LFSR sequence, which requires the LFSR structural details. The only way the attacker can identify the LFSR configuration is to apply the same test vector for a sufficient number of times by using the scan flush test capabilities, where the test vector can be shifted in and out without any capture operation. If the LFSR consists of m bits, the attacker has to apply the same test vector for 2 m -1 times to figure out the structure of the LFSR that can be chosen to implement a primitive polynomial. For an LFSR of medium size, this can be quite costly for the attacker. To provide a higher level of security, we propose the optional integration of a second defense mechanism to disallow a specific number of continuous shift cycles. Another possible smaller LFSR can be used to inject extra noise on the shifted stimulus, once a specific number of consecutive shift cycles with no capture operation in between is detected. The maximum allowed number of continuous shift cycles should be selected carefully to maintain both security and testability of the chip. If the maximum number of continuous shift cycles is too small, the scan flush test will be affected. On the other hand, permitting a large number of continuous shift cycles may enable the identification of the first LFSR structure, and thus, compromise the security of the chip. An n-bit counter can be used to allow up to 2 n -1 consecutive shift operations. Every clock pulse during the test mode increments the counter as long as the scan enable signal is high, indicating a shift operation. When the counter saturates, it signals the second LFSR to kick in and add a second level of bit flipping.

To circumvent the second level of defense, an attacker can employ a dummy capture attack as shown in Figure 11; in this scheme, the attacker pulls down the scan enable signal (to indicate capture) in between the active clock edges. The goal of the attacker is to reset the counter and be able to extend the number of the consecutive shift cycles without corrupting the scan chain content with a capture operation. To thwart such attacks, the reset structure of the counter is designed carefully. The counter is reset only with a capture during an active clock. Figure 12 provides the implementation details. The area cost is an m-bit LFSR and one XOR gate for the level-1 defense, and an s-bit LFSR, c-bit counter, 3 AND gates, one OR gate, one inverter, and one XOR gate in addition for the optional level-2 defense.

Conclusion and Ongoing Work

With a simple yet effective chip mode-reset countermeasure in place, none of the existing scan attacks can leak the secret information of a security-critical IC. In this work, we bring a new perspective to scan attack research by introducing a new class of scan attacks, test-mode-only attack, that targets circumventing this commonly used modereset countermeasure. The proposed attack misuses the in-field debug capabilities of the IC by leveraging operations, such as shift and capture that the test mode offers. By remaining in the test mode, the proposed attack circumvents the mode-reset countermeasure.

A fundamentally different type of scan attack comes with its own challenges to be tackled. As the boundary scan cells block the access to the primary inputs during the test mode, the proposed attack ends up having to use the scan interface to load the attack patterns, in contrast to all the existing scan attacks that benefit from the available PI access in the normal mode. The prerequisite for applying the proposed test-mode-only attack is therefore to decipher the mapping between the scan cells and the AES inputs, which is dictated by the physical position of the scan cells and the physical placement tools used by the designer.

In this work, we tackle the aforementioned challenges and devise a test-mode-only attack, which we illustrate for AES, while we note that the technique herein can be easily extended for other ciphers as well. The attack analysis shows that only 375 test vectors are sufficient to reveal the 128-bit AES secret key where the 128-bit key is reduced to only 12 bits. Furthermore, we also present a brief overview of existing countermeasures, and devise a cost-effective one that can circumvent the proposed test-mode-only attack. We thus present a two-level defense with an underlying input corruption countermeasure that prevents an attacker from launching the bit-flips required to leak the secret key.

Our future work will focus on contemporary scan architectures where a test stimulus decompressor and a response compactor reside on the scan path. We have already made some progress on attacks using compactor [START_REF] Ali | New scan attacks against state-of-the-art countermeasures and dft[END_REF] and boundary scan chains [START_REF] Ali | Test-mode-only scan attack using the boundary scan chain[END_REF]. The technique we present in this paper is readily applicable on ICs that enable debug and diagnostics with a bypass of such advanced DFT features. When this bypass capability is not supported, however, the attack should be enhanced by developing techniques to launch bit-flips through the decompressor in the scan cells, and to perform differential analysis on the compacted responses. The ultimate goal of this line of work is to develop techniques that facilitate the design of testable yet secure ICs.

Fig. 3 .

 3 Fig. 3. AES Core with a single scan chain; SC represents the flip-flop/scan cell of the round register

Fig. 4 .

 4 Fig. 4. Example input-outputs of each transformation of first round of AES

Fig. 6 .

 6 Fig. 6. AES Mixcolumns operation and its differential properties

Fig. 7 .

 7 Fig. 7. Insertion of inverters in the scan path

Fig. 9 .Fig. 10 .

 910 Fig. 9. Masking the compactor output

Fig. 11 .

 11 Fig. 11. Timing diagram of the clock signal and the scan enable signal in a dummy capture attack

Fig. 12 .

 12 Fig. 12. The proposed countermeasure for test-mode-only attack

Table 1 .

 1 Signature Table K B 0 B 1 B 2 B 3 B 4 B 5 B 6 B 7

	0 525 224 334 446 334 455 446 455
	1 525 233 444 466 367 233 358 233
	2 222 224 222 112 556 455 556 334
	3 222 233 556 224 222 556 334 345
	4 334 255 334 222 112 345 145 255
	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
	255 255 224 334 266 134 233 244 345