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

SREEP-2: SR-Equivalent Generator

for Secure and Testable Scan Design

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

* Akita University

** Nara Institute of Science and Technology (NAIST)

2

Outline

1. Background and Motivation 2. Previous Works

3. Objective of the Study 4. Proposed Scan Design

4.1 SR-Equivalent Circuits

4.2 How to Design SR-Equivalent Circuits 4.3 How to Control/Observe SR-Equivalents 4.4 Application to Scan Design

5. Program SREEP-2

6. Security Level of Proposed Scan Design 7. Case Study

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

4

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

  Propose a secure scan design approach

◦  Satisfies both testability and security

◦  Replaces original scan registers with modified scan registers only

Which leads to:

◦  Little area overhead

◦  No performance overhead

  Introduce SR-equivalent circuits

◦  How to design SR-equivalents

◦  How to control/observe SR-equivalents

◦  How to apply it to scan design

  Introduce Program SREEP-2

  Consider security level

6

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(0) y₁(0) y₂(0) y₃(0) z(0) = y₂(0)^⊕y₃(0)

x(1) x(0) y₁(0) y₁(0)^⊕y₂(0) z(1) = y₂(0)

x(2) x(1) x(0) x(0)^⊕y₁(0) z(2) = y₁(0)

x(2) x(1) x(1)^⊕x(0) z(3) = x(0)

8

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

9

How to Design SR-Equivalent Circuits 1/2

Given I²LF²SR

Symbolic simulation

y₁ y₂ y₃

x z

x y₁ y₂ y₃ z

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

x(1) x(0) 1^⊕y₁(0) x(0)^⊕y₂(0) z(1)=x(0)^⊕y₂(0)

x(2) x(1) 1^⊕x(0) x(1)^⊕1^⊕y₁(0) z(2)=x(1)^⊕1⊕y₁⁽⁰⁾

x(2) 1^⊕x(1) x(2)^⊕1^⊕x(0) z(3)=x(2)^⊕1^⊕x(0)

10

Given I²LF²SR

Symbolic simulation

y₁ y₂ y₃

x z x y₁ y₂ y₃ z

Modified SR-equivalent I²LF²SR

x y₁ y₂ y₃ z

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

x(1) x(0) 1^⊕y₁(0) x(0)^⊕y₂(0) z(1)=x(0)^⊕y₂(0)

x(2) x(1) 1^⊕x(0) x(1)^⊕1^⊕y₁(0) z(2)=x(1)^⊕1⊕y₁⁽⁰⁾

x(2) 1^⊕x(1) x(2)^⊕1^⊕x(0) z(3)=x(2)^⊕1^⊕x(0)

How to Design SR-Equivalent Circuits 2/2

11

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.

12

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

SR-equivalent I²LF²SR, R₂

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

Equations for state-justification

y₁ y₂ y₃

x z

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

x(2) = y₁(3)

x y₁ y₂ y₃ z

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

x(1) x(0) 1^⊕y₁(0) x(0)^⊕y₂(0) z(1)=1^⊕y₂(0)

x(2) x(1) 1^⊕x(0) x(1)^⊕1^⊕y₁(0) z(2)=y₁(0) x(2)

=y₁(3)

1^⊕x(1)

=y₂(3)

x(2)^⊕1^⊕x(0)

=y₃(3) ^z(3)=x(0)

13

How to Observe SR-Equivalent Circuits , R

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

Equations for state-observation

x y₁ y₂ y₃ z

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

x(1) x(0) 1^⊕y₁(0) x(0)^⊕y₂(0) z(1)=1^⊕y₂(0)

x(2) x(1) 1^⊕x(0) x(1)^⊕1^⊕y₁(0) z(2)=y₁(0)

x(2) 1^⊕x(1) x(2)^⊕1^⊕x(0) z(3)=x(0)

y₁(0) = z(2) y₂(0) = 1^⊕z(1)

y₃(0) = 1^⊕z(0)^⊕z(2)

SR-equivalent I²LF²SR, R₂

y₁ y₂ y₃

x z

14

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}

15

Standard scan register

Modified scan register (SR-equivalent)

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

16

Replacement of scan chain by modified scan chain

Scan Chain Secret Register

Secret Register

Standard Scan Chain

Standard Scan Chain Modified Scan

Chain (SR-equivalent)

Application to Scan Design 3/3

17

Program SREEP-2

Main functions:

(1)  Synthesis for SR-equivalent circuits.

(2)  State-justification for SR-equivalent circuits.

(3)  State-observation for SR-equivalent circuits.

(4)  Indication of security level of SR-equivalent circuits

18

Synthesis for SR-Equivalent Circuits 1/4

Procedure:

(1)  From the given constraints, enumerate possible circuits that satisfy the constraints.

(2)  For each enumerated circuit, check if it is SR-equivalent or not. If it is SR-equivalent, then it is an output as a solution.

Otherwise, add extra feed-forwards, feedbacks, and/or inverters so that the modified circuit becomes SR-equivalent.

19

Synthesis for SR-Equivalent Circuits 2/4

(1)  From the given constraints, enumerate possible circuits that satisfy the constraints.

Or, design a linear circuit by specifying feedback/forward connections.

20

Synthesis for SR-Equivalent Circuits 3/4

(2)  For each enumerated circuit, check if it is SR-equivalent or not. If it is SR-equivalent, then it is an output as a solution.

Otherwise, add extra feed-forwards, feedbacks, and/or inverters so that the modified circuit becomes SR-equivalent.

To change

z(3) = 1+x(0)+x(2) to

z(3) = x(0),

add 1+x(2) to z(3)

21

Synthesis for SR-Equivalent Circuits 3/4

(2)  For each enumerated circuit, check if it is SR-equivalent or not. If it is SR-equivalent, then it is an output as a solution.

Otherwise, add extra feed-forwards, feedbacks, and/or inverters so that the modified circuit becomes SR-equivalent.

To change z(3) = 1+x(0)+x(2) to z(3) = x(0),

add 1+x(2) to z(3)

22

State Justification for SR-Equivalent Circuits 1/3

Procedure:

(1)  By symbolic simulation, express the value of each flip-flop FF_i^(k) at final time k by input values, x(0), x(1), …, x(k-1).

(2)  Change the form of the obtained k equations into the form such that input values, x(0), x(1), … , x(k-1), are expressed by the values of flip-flops at final time k.

23

State Justification for SR-Equivalent Circuits 2/3

(1)  By symbolic simulation, express the value of each flip-flop FFi^(k)

at final time k by input values, x(0), x(1), …, x(k-1).  

FF₁(3) = x(2) FF₂(3) = 1 + x(1)

FF₃(3) = 1 + x(0) + x(2)

24

State Justification for SR-Equivalent Circuits 3/3

FF₁(3) = x(2) FF₂(3) = 1+x(1)

FF₃(3) = 1+x(0)+x(2)

x(0) = 1+FF₁(3)+FF₃(3) x(1) = 1+FF₂(3)

x(2) = FF₁(3)

(2)  Change the form of the obtained k equations into the form such that input

values, x(0), x(1), … , x(k-1), are expressed by the values of flip-flops at final time k.

25

State Observation for SR-Equivalent Circuits 1/3

Procedure:

(1)  By symbolic simulation, express the output values at all times, z(0), z(1), …, z(k), by the input value at time 0, x(0), and

the values of flip-flops at time 0, FF₁(0), FF_{2(0),…, FFk}(0).

(2)  Change the form of the obtained k equations into the form such that the value of each flip-flop, FF₁(0), FF_{2(0),…, FFk}(0), are expressed by the output values, z(0), z(1), … , z(k-1).

26

(1)  By symbolic simulation, express the output values at all times, z(0), z(1), …, z(k), by the input value at time 0, x(0), and

the values of flip-flops at time 0, FF₁(0), FF_{2(0),…, FFk}(0).

z(0) = 1+FF₁(0)+FF₃(0) z(1) = 1+FF₂(0)

z(2) = FF₁(0)

State Observation for SR-Equivalent Circuits 2/3

27

FF₁(0) = z(2) FF₂(0) = 1+z(1)

FF₃(0) = 1+z(0)+z(2) (2)  Change the form of the obtained k equations into the form

such that the value of each flip-flop, FF₁(0), FF_{2(0),…, FFk}(0), are expressed by the output values, z(0), z(1), … , z(k-1).

State Observation for SR-Equivalent Circuits 3/3

z(0) = 1+FF₁(0)+FF₃(0) z(1) = 1+FF₂(0)

z(2) = FF₁(0)

28

Case Study for 16-bit SR-Equivalent Circuits

The program SREEP-2 was executed on the computer with Xeon E5550 (2.66GHz x 2)

with the constraints such that

the number of stages is 16,

the number of feed-forwards is between 2 and 4, and the number of feedbacks is 0.

SREEP-2 took 293 seconds to generate all SR-equivalent circuits that satisfy the constraints.

The number of SR-equivalent circuits that satisfy the above constraints is 58,393.

Let us observe two circuits out of them in the following.

29

Symbolic Simulation for _{C 1}

30

State Justification for _{C 1}

31

State Observation for _{C 1}

32

Symbolic Simulation for _{C 2}

33

Security Level of Proposed Scan Design 1/6

Let us consider how secure the modified scan designed circuits are, from two viewpoints;

1.  the complexity of identifying the structure of SR-equivalent circuits 2. the possibility of leakage of the contents in each FF.

34

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

In our previous work, we showed the cardinality of each class of SR- equivalent circuits.

For example, the cardinality of k-stage SR-equivalent I²LF²SRs is

(2

- 1)( 2

- 1).

Hence, the complexity or the difficulty of identifying the structure of SR-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-equivalent circuit from the information on input/output relation only.

Security Level of Proposed Scan Design 2/6

35

However, even if the structure of an SR-equivalent circuit is

different from that of SR and is hard to be identified, it is not secure if part of the contents of the SR-equivalent circuit leak out.

Security Level of Proposed Scan Design 3/6

36

Consider SR-equivalent circuit C₂. If we assign 8 flip-flops from FF1 to FF8 to the secret register, the contents of the secret register appear at the output because

OUT@15 = FF1@0, OUT@14 = FF2@0, OUT@13 = FF3@0, OUT@12 = FF4@0, OUT@11 = FF5@0, OUT@10 = FF6@0, OUT@9 = FF7@0, and OUT@8 = FF8@0.

Hence, it is not secure.

Security Level of Proposed Scan Design 4/6

37

On the other hand, consider the 16-bit SR-equivalent circuits C₁.

The contents of all flip-flops except FF1 do not leak out. So, if we use 8 flip- flops except FF1 as the secret register, the contents of the secret register never leak out and it is secure.

Security Level of Proposed Scan Design 5/6

38

To confirm the security, we need to check if the contents of each flip-flop leak out or not.

SREEP-2 generates the logic expressions of the output of the circuit at each clock cycle, which can be used to check if the

contents of each flip-flop appears at the output, i.e., it leaks out.

Security Level of Proposed Scan Design 6/6

39

Conclusion

In this paper,

We presented how to apply SR-equivalent circuits to scan design so that the modified scan designed circuits are both secure and testable. We presented how to design SR-equivalent circuits under several

constraints and how to control/observe SR-equivalent circuits to guarantee easy scan-in/out operations.

We also considered how secure the modified scan designed circuits are, from two viewpoints; one is the complexity of identifying the

structure of SR-equivalent circuits and the other is the possibility of leakage of each FF’s contents.

A program called SREEP-2 was presented to solve those problems.

40

Thank you