11 WRTLT pptx 最近の更新履歴 Hideo Fujiwara

SR-Quasi-Equivalent:

Yet Another Approach to

Secure and Testable Scan Design

Katsuya Fujiwara*, Hideo Fujiwara**, and Hideo Tamamoto*

* Akita University

** Osaka Gakuin University

Outline

1. Background and Motivation 2. Previous Works

3. Objective of the Study 4. SR-Equivalent Circuits

5. SR-Quasi-Equivalent Circuits 6. Application to Scan Design

7. Cardinality of SR-Quasi-Equivalents 8. Conclusion

3

Background and Motivation

 

Reliability

 

Scan Design:

most popular DFT

 

Protection of

information

 Scan Design:

increases

vulnerability of

chip

3

Quality 

scan

reset Scan-in



Combinational Logic Circuit   (Kernel)

Contradiction between Testability and 

Security   Solution? 

x

Previous Works

  Recent works focus on secure scan design:

› D. Hely, et al. 2004, 2007 – scrambling

› B. Yang, et al. 2004, 2006 – MKR

› J. Lee, et al. 2006, 2007 – lock & key

› S. Paul, et al. 2007 – Vlm-scan

› G. Sengar, et al. 2007 – flipped-scan-chain

› U. Chandran, et al. 2009 –

  All approaches (except Sengar) add extra hardware outside of scan registers.

Which means:

› high area overhead

› timing overhead or performance degradation

› increased complexity of testing

› limited security for the registers part

5

Objective of the Study

  Proposed a secure scan design approach (ASP-DAC 2010, 2011, WRTLT 2010)

◦  Satisfies both testability and security

◦  Replaces original scan registers with modified scan registers (called SR-equivalent circuits) only

Which leads to:

◦  Little area overhead

◦  No performance overhead

  Introduce a wider class of circuits called SR-quasi-equivalents

◦  Still satisfy both testability and security

◦  Cover the class of SR-equivalents Which leads to:

◦  Higher cardinality than SR-equivalents

◦  More secure than SR-equivalents

  Clarify the cardinality of each equivalent class in SR-quasi-equivalents to estimate the security level

SR-Equivalent Circuits

k-stage shift register, SR

k-stage SR-equivalent circuit, C

A circuit C with a single input x, a single output z, and k flip-flops is called functionally equivalent to a k-stage shift register

(or SR-equivalent)

if the input value applied to x at any time t appears at z after k clock cycles, i.e., z(t+k) = x(t) for any time t.

x y₁ y₂ ^… y_k z

y₁ y₂ y_k

x ^… z

7

Example: SR-equivalent circuit R

y₁ y₂ y₃

x z

x y₁ y₂ y₃ z

x(t) y₁(t) y₂(t) y₃(t) x(t+1)

x(t+2)

Symbolic simulation

Example: SR-equivalent circuit R

y₁ y₂ y₃

x z

x y₁ y₂ y₃ z

x(t) y₁(t) y₂(t) y₃(t) z(t) = y₂(t)^⊕y₃(t) x(t+1) x(t) y₁(t) y₁(t)^⊕y₂(t) z(t+1) = y₂(t) x(t+2) x(t+1) x(t) x(t)^⊕y₁(t) z(t+2) = y₁(t) x(t+2) _x(t+1) x(t+1)^⊕x(t) z(t+3) = x(t)

The input value applied to x at time t

9

y₁ y₂ y₃

x z

y₁ y₂ y₃

x z

y₁ y₂ y₃

x z

y₁ y₂ y₃

x z

y₁ y₂ y₃

x z

Inversion-Inserted SR (I²SR)

Linear Feed-Forward SR (LF²SR)

Inversion-Inserted Linear Feed-Forward SR (I²LF²SR)

Linear Feedback SR (LFSR)

Inversion-InsertedLinear Feedback SR (I²LFSR)

Five Types of Linear Circuits

How to Control/Observe SR-Equivalents

k-stage shift register, SR

k-stage SR-equivalent circuit, C

State-Justification: (Scan-in)

x y₁ y₂ ^… y_k z

y₁ y₂ y_k

x ^… z

To generate an input sequence to transfer the circuit C into a given desired state.

State-Observation: (Scan-out)

To identify the initial state by observing the output sequence from the state.

To utilize the SR-equivalent circuit C as a shift register SR, we need to consider the following two problems.

11

How to Control SR-Equivalent Circuits _{, R 2}

To find input sequence x(t),x(t+1),x(t+2) for final state (y₁(t+3),y₂ (t+3),y₃ (t+3))

Equations for state-justification

y₁ y₂ y₃

x z

x(t) = 1^⊕y₁(t+3)^⊕y₃(t+3) x(t+1) = 1^⊕y₂(t+3)

x(t+2) = y₁(t+3)

x y₁ y₂ y₃ z

x(t) y₁(t) y₂(t) y₃(t) z(t)=1^⊕y₁(t)^⊕y₃(t) x(t+1) x(t) 1^⊕y₁(t) x(t)^⊕y₂(t) z(t+1)=1^⊕y₂(t) x(t+2) x(t+1) 1^⊕x(t) x(t+1)^⊕1^⊕y₁(t) z(t+2)=y₁(t)

x(t+2)

=y₁(t+3) ¹

⊕_x(t+1)

=y₂(t+3) ^x(t+2)

⊕₁⊕_x(t)

=y₃(t+3) ^z(t+3)=x(t)

How to Control SR-Equivalent Circuits _{, R 2}

For instance, the transfer sequence for (y₁(t+3),y₂ (t+3),y₃ (t+3)) = (1, 1,0) is (x(t), x(t+1), x(t+2)) = (0, 0, 1).

On the other hand, for a shift register

the transfer sequence for final state (1, 1, 0) is (0, 1, 1). Since the attacker does not know the above equations,

he cannot find out the transfer sequence for final state (1, 1, 0). x(t) = 1^⊕y₁(t+3)^⊕y₃(t+3)

x(t+1) = 1^⊕y₂(t+3) x(t+2) = y₁(t+3)

y₁ y₂ y₃

x z

13

How to Observe SR-Equivalent Circuits , R

To identify initial state (y₁(t), y₂ (t), y₃ (t)) from output sequence z(t), z(t+1), z(t+2)

Equations for state-observation

x y₁ y₂ y₃ z

x(t) y₁(t) y₂(t) y₃(t) z(t+t)=1^⊕y₁(t)^⊕y₃(t) x(t+1) x(t) 1^⊕y₁(t) x(t)^⊕y₂(t) z(t+1)=1^⊕y₂(t)

x(t+2) x(t+1) 1^⊕x(t) x(t+1)^⊕1^⊕y₁(t) z(t+2)=y₁(t) x(t+2) 1^⊕x(t+1) x(t+2)^⊕1^⊕x(t) _z(t+3)=x(t)

y₁(t) = z(t+2) y₂(t) = 1^⊕z(t+1) y₃(t) = 1^⊕z(t)^⊕z(t+2)

y₁ y₂ y₃

x z

How to Observe SR-Equivalent Circuits , R

y₁(t) = z(t+2) y₂(t) = 1^⊕z(t+1)

y₃(t) = 1^⊕z(t)^⊕z(t+2)

For instance, suppose the output sequence is 110 ,i.e., (z(t), z(t+1), z(t+2)) = (1, 1, 0),

then (y₁(t), y₂ (t), y₃ (t)) = (0, 0, 0).

So, the initial state (0, 0, 0) is identified from the output sequence.

On the other hand, in case of a shift register, the initial state is (0, 1, 1). Since the attacker does not know the above equations,

he cannot identify the initial state as (0, 0, 0).

y₁ y₂ y₃

x z

15

SR-Quasi-Equivalent Circuits

A circuit C with a single input x, a single output z, and k flip-flops is called functionally quasi-equivalent to a k-stage shift register

(or SR-quasi-equivalent)

if the input value applied to x at any time t appears at z

after k clock cycles with exclusive-OR of some inputs and/or constant 1, i.e.,

z(t+k) = x(t) ^⊕ c₀ ^⊕ c₁x(t+1) ^⊕ c₂x(t+2) ^⊕_{…⊕ ck}x(t+k)

where c₀ , c₁, c_{2, … , ck} are 0 or 1.

(c₀ , c₁, c_{2, … , ck} ) is called characteristic coefficient

x y₁ y₂ ^… y_k z

SR-Quasi-Equivalent Circuits

Any SR-equivalent circuit is an SR-quasi-equivalent circuit such that its characteristic coefficient is (0, 0, …, 0).

x y₁ y₂ ^… y_k z

If a circuit is SR-equivalent, z(t+k) = x(t).

z(t+k) = x(t) ^⊕ c₀ ^⊕ c₁x(t+1) ^⊕ c₂x(t+2) ^⊕_{…⊕ ck}x(t+k) Hence, (c₀ , c_{1, … , ck} ) = (0, 0, … , 0)^.

17

Example of SR-Quasi-Equivalent Circuits _{, R 3}

y₁ y₂ y₃

x
z

Symbolic simulation

x y₁ y₂ y_{3 z!}

x(t) y₁(t) y₂(t) y₃(t) z(t)=y₃(t)

x(t+1) x(t) 1 y₁(t) x(t) y₂(t) z(t+1)=x(t) y₂(t)

x(t+2) x(t+1) 1 x(t) x(t+1) 1 y₁(t) z(t+2)=x(t+1) 1 y₁(t) x(t+3) x(t+2) _{1 x(t+1)} x(t+2) 1 x(t) z(t+3)=x(t+2) 1 x(t)

z(t+3) = x(t) ^⊕ 1^⊕ 0 x(t+1) ^⊕ 1 x(t+2) ^⊕ 0 x(t+3) Characteristic coefficient = 1010

Equations for State-Justification

x y₁ y₂ y_{3 z!}

x(t) y₁(t) y₂(t) y₃(t) z(t)=y₃(t)

x(t+1) x(t) 1 y₁(t) x(t) y₂(t) z(t+1)=x(t) y₂(t)

x(t+2) x(t+1) 1 x(t) x(t+1) 1 y₁(t) z(t+2)=x(t+1) 1 y₁(t) x(t+3) ^x(t+2)!

=y₁(t+3)

1 x(t+1)

=y₂(t+3)

x(t+2) 1 x(t)

=y₃(t+3) ^z(t+3)=x(t+2) 1 x(t)

x(t) = 1 y₁(t+3) y₃(t+3) x(t+1) = 1 y₂(t+3)

x(t+2) = y (t+3)

To find input sequence x(t), x(t+1), x(t+2) for final state (y₁(t+3), y₂ (t+3), y₃ (t+3))

19

A transfer sequence of length k to any desired final state can be expressed by the final state only.

x(t) = 1^⊕y₁(t+3)^⊕y₃(t+3) x(t+1) = 1^⊕y₂(t+3)

x(t+2) = y₁(t+3)

Equations for State-Justification

It does not depend on the initial state.

Hence, state-justification is easy, i.e., easy to scan-in.

Equations for State-Observation

x y₁ y₂ y_{3 z!}

x(t) y₁(t) y₂(t) y₃(t) z(t)=y₃(t)

x(t+1) x(t) 1 y₁(t) x(t) y₂(t) z(t+1)=x(t) y₂(t)

x(t+2) x(t+1) 1 x(t) x(t+1) 1 y₁(t) z(t+2)=x(t+1) 1 y₁(t) x(t+3) x(t+2) _{1 x(t+1)} x(t+2) 1 x(t) z(t+3)=x(t+2) 1 x(t)

y₁(t) = z(t+2) x(t+1) 1 y₂(t) = z(t+1) x(t)

y (t) = z(t)

y₁ y₂ y₃

x
z

To identify initial state (y₁(t), y₂ (t), y₃ (t)) from input/output sequence

x(t), x(t+1), x(t+2) / z(t), z(t+1), z(t+2)

21

y₁(t) = z(t+2) ^⊕x(t+1) ^⊕1 y₂(t) = z(t+1) ^⊕x(t)

y₃(t) = z(t)

Equations for State-Observation

Any present state (initial state) can be identified from the input- output sequence of length k and the connection information of the circuit, where the input sequence is arbitrary.

Hence, state-observation is easy, i.e., easy to scan-out.

SR-equivalence vs. SR-quasi-equivalence

SR-equivalent SR-quasi-equivalent

State-

Justification (Scan-in)

A transfer sequence of length k to the final state can be generated from the circuit structure, independently of the initial state.

Same as SR-equivalent

State-

Observation (Scan-out)

Any initial state can be identified from the

output sequence of

length k and the circuit structure.

Any initial state can be identified from the input- output sequence of length k and the circuit

structure.

23

Application to Scan Design 1/3

Scan-designed circuit

Scan Chain

…

Combinational Logic Circuit (Kernel)

Scan Chain

…

…

… … …… …

Standard scan register

y₁ y₂ y₃

x ^{0 1 0 1 0 1 z}

Standard scan register

y₁ y₂ y₃

x ^z

0 1

0 1

0 1

y₁ y₂ y₃

x ^z

0 1

0 1

0 1

Application to Scan Design 2/3

25

Replacement of scan chain by modified scan chain

Scan Chain Secret Register

Secret Register

Standard Scan Chain

Standard Scan Chain Modified Scan

Chain

(SR-quasi-equivalent)

Application to Scan Design 3/3

Security Level of Proposed Scan Design 1/3

We assume:

-  the attacker does not know the detailed information in the gate-level design

-  the attacker knows the presence of test pins (scan in/out, scan, and reset) and modified scan chains

-  the attacker does not know the structure of modified scan chains (the connection information, position of XOR and NOT, and the size)

A circuit C with a single input, a single output, and k flip-flops is called scan-secure if the attacker cannot determine the structure of C.

27

Security Level of Proposed Scan Design 2/3

Let C₁ and C₂ be SR-quasi-equivalent circuits. C₁ and C₂ have the same

characteristic coefficient ^{C1 and C2} are functionally equivalent

Suppose

C₁ and C₂ have different structures but the same characteristic coefficient.

C₁ and C₂ are functionally equivalent

C₁ and C₂ cannot be distinguished merely from the input/output relation.

C₁ and C₂ are scan-secure

Security Level of Proposed Scan Design 3/3

The security level of the secure scan architecture is determined by the probability that an attacker can identify the structure of the SR- quasi-equivalent circuit.

Hence the attack probability approximates to the reciprocal of the cardinality of the class of SR-quasi-equivalents.

The attacker can identify the characteristic coefficient of SR-quasi- equivalents though the time complexity is exponential.

We need to clarify the cardinality of each equivalent class in SR-quasi- equivalents to estimate the attack probability.

29

Equivalent class I²SR

00…00 2^k - 1

00…01

~ 01…11

0

~ 0

10…00 2^k

10…01

~ 11…11

0

~ 0

Total 2^k+1-1

z(t+k) = x(t) (SR-equivalents)

z(t+k) = x(t) ^⊕ 1

Cardinality of SR-Quasi-Equivalents 1/5

Characteristic coefficient

y₁ y₂ y₃

x z

Inversion-Inserted SR

(I

SR)

Equivalent class LF²SR

00…00 2^k(k-1)/2 - 1

00…01

~ 01…11

2^k(k-1)/2

~ 2^k(k-1)/2

10…00 0

10…01

~ 11…11

0

~ 0

Total 2^k(k+1)/2 - 1

Cardinality of SR-Quasi-Equivalents 2/5

y₁ y₂ y₃

x z

Linear Feed-Forward SR

(LF

SR)

31

Equivalent class I²LF²SR

00…00 (2^k(k-1)/2 -1)(2^k -1) 00…01

~ 01…11

2^k(k-1)/2 (2^k–1)

~

2^k(k-1)/2 (2^k–1)

10…00 (2^k(k-1)/2 -1) 2^k

10…01

~ 11…11

2^k(k-1)/2 2^k

~ 2^k(k-1)/2 2^k

Total (2^k(k+1)/2 -1)(2^k+1-1)

Cardinality of SR-Quasi-Equivalents 3/5

y₁ y₂ y₃

x z

Inversion-Inserted

Linear Feed-Forward SR

(I

LF

SR)

Equivalent class I²LFSR

00…00 (2^k(k-1)/2 -1)(2^k -1) 00…01

~ 01…11

0

~ 0

10…00 (2^k(k-1)/2 -1) 2^k

10…01

~ 11…11

0

~ 0

Total (2^k(k-1)/2 -1)(2^k+1-1)

Cardinality of SR-Quasi-Equivalents 4/5

y₁ y₂ y₃

x z

Inversion-Inserted

Linear Feedback SR

(I

LFSR)

33

Equivalent class LFSR

00…00 2^k(k-1)/2 -1

00…01

~ 01…11

0

~ 0

10…00 0

10…01

~ 11…11

0

~ 0

Total 2^k(k-1)/2 -1

Cardinality of SR-Quasi-Equivalents 5/5

y₁ y₂ y₃

x z

Linear Feedback SR

(LFSR)

Covering Relation among Classes

I²SR

LF²SR

LFSR

I²LF²SR I²LFSR

SR equivalents SR quasi-equivalents

2

-1 (2

-1)(2

-1)

(2

-1) 2

(2

-1)(2

-1)

2

- 1

2

-1

35

All circuits in I²SR, LF²SR, and I²LF²SR are SR-quasi-equivalent.

Easy to design SR-quasi-equivalent circuits

I²SR

LF²SR

I²LF²SR

Which means:

It is very easy to design an SR-quasi-equivalent circuit.

(2

-1)(2

-1)

2

- 1

2

-1

We can use any of them to organize the secure and testable scan chains.

The complexity of identifying the structure of SR-quasi-equivalents is proportional to the cardinality of the class of SR-quasi-

equivalents.

Even if we limit the class to I²LF²SR, the cardinality of k-stage SR-quasi- equivalent I²LF²SRs is

₍₂ ^k(k+1)/2 _{- 1)( 2} ^k+1 _{- 1).}

Hence, the complexity or the difficulty of identifying the structure of SR-quasi-equivalent circuits increases more than exponentially as the number of flip-flops increases.

So, it is very hard and intractable to identify the structure of a given SR-quasi-equivalent circuit from the information on input/output relation only.

Security Level of Proposed Scan Design 4/4

37

Conclusion

  Introduced a new class of circuits called ^SR-quasi- equivalents

◦  Still satisfy both testability and security

◦  Cover the class of SR-equivalents Which leads to:

◦  Higher cardinality than SR-equivalents

◦  More secure than SR-equivalents

  Clarified the cardinality of each equivalent class in SR- quasi-equivalents to estimate the security level

Thank you