最近の更新履歴 Hideo Fujiwara

How to Satisfy Contradictory Concepts:

Testability and Security of LSI

Hideo Fujiwara 

藤原 秀雄

2

Abstract

It is important to find an efficient design-for-testability methodology that satisfies both security and testability though there exists an inherent contradiction between security and testability for digital circuits. We reported a secure and testable scan design approach by using extended shift registers that are functionally equivalent but not structurally equivalent to shift registers, and clarified the cardinality of shift-register equivalents (SR- equivalents) to evaluate the security level.

In this talk, we present how to apply SR-equivalent circuits to scan design so that the modified scan designed circuits are both secure and testable. We consider 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 discuss how secure the modified scan designed circuits are.

3

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

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

8. Conclusion

4

Background and Motivation

 

Reliability

 Scan Design: most popular DFT

 

Protection of

information



4

Quality 

scan

reset Scan-in



Combinational Logic Circuit   (Kernel)

Contradiction between Testability and 

Security   Solution? 

x

5

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 –

› M. A. Razzaq, et al. 2011 – test key randomization

  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

6

Our Works

  Our works focus on secure scan design:

› H. Fujiwara, et al. 2010 – ASP-DAC 2010 “SR-equivalents”

›  K. Fujiwara, et al. 2010 – DDECS 2010

›  K. Fujiwara, et al. 2010 – WRTLT 2010

“SR-equivalent generator”

› H. Fujiwara, et al. 2011 – ASP-DAC 2011

“Differential behavior attack”

›  K. Fujiwara, et al. 2011 – WRTLT 2011 “SR-quasi-equivalents”

› K. Fujiwara, et al. 2012 – WRTLT 2012

“Generalized Feed Forward SR ”

7

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

  Consider security level

8

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

9

Example: SR-equivalent circuit R

y₁ y₂ y₃

x z

x y₁ y₂ y₃ z

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

x(1) x(2)

10

Example: SR-equivalent circuit R

y1 y2 y3

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)

11

y1 y2 y3

x z

y₁ y₂ y₃

x z

y₁ y₂ y₃

x z

y1 y2 y3

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

12

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₁(0) x(2) 1^⊕x(1) x(2)^⊕1^⊕x(0) z(3)=x(2)^⊕1^⊕x(0)

13

Given I²LF²SR

Symbolic simulation

y1 y2 y3

x z ^x y1 y2 y3 ^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₁(0) 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

14

How to Control/Observe SR-Equivalents

k-stage shift register, SR

k-stage SR-equivalent circuit, C

State-Justification: (Scan-in)

x y₁ y₂ ^… yk z

y1 y2 yk

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.

15

How to Control SR-Equivalent Circuits , R ₂

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

y1 y2 y3

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) ¹

⊕_x(1)

=y₂(3) ^x(2)

⊕₁⊕_x(0)

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

16

How to Control SR-Equivalent Circuits , R ₂

SR-equivalent I²LF²SR, R₂

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

On the other hand, for a shift register, the transfer sequence for (y₁(3),y₂ (3),y₃ (3)) = (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).

y₁ y₂ y₃

x z

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

17

How to Observe SR-Equivalent Circuits , R

To identify initial state (y1(0),y2 (0),y3 (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₂

y1 y2 y3

x z

18

How to Observe SR-Equivalent Circuits , R

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

For instance, suppose the output sequence is (z(0), z(1), z(2)) = (1, 1, 0), then (y₁(0),y₂ (0),y₃ (0)) = (0, 0, 0).

So, the initial state (0, 0, 0) is identified from the output sequence. On the other hand, for 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 (0, 0, 0) from the output sequence (z(0), z(1), z(2)) = (1, 1, 0).

19

Application to Scan Design 1/3

Scan-designed circuit

Scan Chain

…

Combinational Logic Circuit (Kernel)

Scan Chain

…

…

… … …… …

Standard scan register

y1 y2 ^y3

x ^z

0 1

0 1

0 1

20

Standard scan register

Modified scan register (SR-equivalent)

y1 y2 ^y3

x ^{0 1 0 1 0 1 z}

y1 y2 ^y3

x ^{0 1 0 1 0 1 z}

Application to Scan Design 2/3

21

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

22

Program SREEP

(Shift Register Equivalents Enumeration and Synthesis Program)

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

http://www.fujiwaralab.net/en/sreep/

23

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.

24

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.

25

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)

26

Synthesis for SR-Equivalent Circuits 4/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)

27

State Justification for SR-Equivalent Circuits 1/3

Procedure:

(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).  

(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.

28

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)

29

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.

30

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).

31

(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

32

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, FF1(0), FF2(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)

33

Case Study for 16-bit SR-Equivalent Circuits

The program SREEP 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 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.

34

Symbolic Simulation for C ₁

35

State Justification for C ₁

36

State Observation for C ₁

37

Symbolic Simulation for C ₂

38

Security Level of Proposed Scan Design 1/8

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.

39

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

Security Level of Proposed Scan Design 2/8

I²SR LF²SR

LFSR I²LF²SR

I²LFSR (2^k(k-1)/2 -1)(2^k -1)

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

2^k -1

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

SR-equivalents

Total number of k-level SR-equivalents: N(k) = ^(2k)! k! ^{ー 1}

40

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

Security Level of Proposed Scan Design 3/8

I²SR LF²SR

LFSR I²LF²SR

I²LFSR (2^k(k-1)/2 -1)(2^k -1)

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

2^k -1

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

SR-equivalents

Total number of k-level SR-equivalents: N(k) = ^(2k)! k! ^{ー 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.

41

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

Security Level of Proposed Scan Design 4/8

I²SR LF²SR

LFSR I²LF²SR

I²LFSR (2^k(k-1)/2 -1)(2^k -1)

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

2^k -1

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

SR-equivalents

Total number of k-level SR-equivalents: N(k) = ^(2k)! k! ^{ー 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.

42

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 5/8

43

Consider SR-equivalent circuit C2. 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 6/8

44

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 7/8

45

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

SREEP 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 8/8

46

Conclusion

In this talk,

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 was presented to solve those problems.

47

References

[1] H. Fujiwara, Logic Testing and Design for Testability, The MIT Press 1985. [2] H. Fujiwara and M.E.J. Obien, “Secure and testable scan design using extended de Brujin graph,” 15th Asia and South Pacific Design Automation Conference, pp. 413-418, Jan. 2010.

[3] K. Fujiwara, H. Fujiwara, M.E.J. Obien, and H. Tamamoto, “SREEP: Shift register equivalents enumeration and synthesis program for secure scan design,” 13th IEEE International Symposium on Design and Diagnosis of Electronic Circuits and Systems, pp. 193-196, April 2010.

[4] K. Fujiwara, H. Fujiwara, and H. Tamamoto, "SREEP-2: SR-equivalent Generator for Secure and Testable Scan Design," 11th IEEE Workshop on RTL and High Level Testing, pp. 7-12, Dec. 2010.

[5] H. Fujiwara, K. Fujiwara, and H. Tamamoto, “Secure Scan Design Using Shift Register Equivalents against Differential Behavior Attack," 16th Asia and South Pacific Design Automation Conference, pp.818-823, Jan. 2011.

[6] Katsuya Fujiwara, Hideo Fujiwara, and Hideo Tamamoto, "Differential Behavior Equivalent Classes of Shift Register Equivalents for Secure and Testable Scan Design," IEICE Trans. on Inf. and Syst., Vol. E94-D, No. 7, pp. 1430-1439, July 2011.

48

References

[7] K. Fujiwara, H. Fujiwara, and H. Tamamoto,”SR-Quasi-Equivalents: Yet Another Approach to Secure and Testable Scan Design,” 12th IEEE Workshop on RTL and High Level Testing, pp. 77-82, Dec. 2011.

[8] K. Fujiwara, H. Fujiwara, and H. Tamamoto, "Secure and Testable Scan Design Utilizing shift Register Quasi-Equivalents," IPSJ Trans. on System LSI Design Methodology, Vol. 6, pp. 1-7, Feb. 2013.

[9] K. Fujiwara and H. Fujiwara, "WAGSR: Web Application for Generalized Feed Forward Shift Registers,” 13th IEEE Workshop on RTL and High Level Testing, pp.1.2.1-1.2.7, Nov. 2012.

[10] K. Fujiwara and H. Fujiwara, "Generalized Feed Forward Shift Registers and their Application to Secure Scan Design," IEICE Trans. on Inf. and Syst., Vol. E96-D, No. 5, pp. 1125-1133, May 2013.

[11] SREEP: http://www.fujiwaralab.net/en/sreep/ [12] WAGSR: http://www.fujiwaralab.net/en/wagsr

49

Thank you