testability security 最近の更新履歴 Hideo Fujiwara

LSIのテスタビリティとセキュリティ

ー 相反する概念を両立させる ー

大阪学院大学 情報学部

藤原 秀雄

話の内容  

予備知識

  _{論理回路のテスト}

  テスト容易化設計（スキャン設計）

テスタビリティとセキュリティ

  _{相反する概念}

  シフトレジスタ等価回路の導入

  セキュアでテスト容易なスキャン設計

2

話の内容  

予備知識

  _{論理回路のテスト}

  テスト容易化設計（スキャン設計）

テスタビリティとセキュリティ

相反する概念

シフトレジスタ等価回路の導入

セキュアでテスト容易なスキャン設計

3

組合せ論理回路のテスト

1 1

1/0 0

1/0

1/0 1

0

0 ₁

0

テストパターン を印加

信号線 _f が０に縮退する故障をテストするためのテストパターン

故障 _{f s-a-0}

誤 検出

AND

AND

OR AND

NOT

順序論理回路のテスト

外 部

入 力

外 部

出 力

順序論理回路

レジスタ, FF

テストパターンを印加する

テストパターンをセットする

制御が困難

誤 を検出す

誤 を外部出力ま 伝搬す

観測 困難

5

テスト容易化設計（スキャン設計）  ^1/4

6

FF FF FF

外 部

入 力

外 部

出 力

組合せ論理回路

テスト容易化設計（スキャン設計）  ^2/4

7

外 部

入 力

外 部

出 力

組合せ論理回路

FF FF FF ^スキャン _出力

モード切替＋シフトレジスタ

で制御・観測容易に

スキャン

入力

スキャン

モード制御

テスト容易化設計（スキャン設計）  ^3/4

外 部

入 力

外 部

出 力

組合せ論理回路

FF FF FF

通常モードとして動作

スキャン

モード＝０

スキャンモード＝０の時、通常モードとして動作

テスト容易化設計（スキャン設計）  ^4/4

9

外 部

入 力

外 部

出 力

組合せ論理回路

FF FF FF ^スキャン _出力

シフトレジスタとして動作

スキャン

入力

スキャン

モード＝１

スキャンモード＝１の時、 シフトレジスタとして動作

 したがって、FFの値の制御・観測が容易

話の内容  

予備知識

コンピュータの内部

論理回路のテスト

テスト容易化設計（スキャン設計）

テスタビリティとセキュリティ

  _{相反する概念}

  シフトレジスタ等価回路の導入

  セキュアでテスト容易なスキャン設計

10

スキャン設計のテスタビリティとセキュリティ

FF FF FF FF

シフトレジスタ

 

テスタビリティ： テスト容易? → Yes

レジスタ（FF群）を容易に制御•観測できる

 

セキュリティ： 安全？ → No

レジスタ（FF群）が筒抜け、データ漏洩の危険

暗号回路の秘密鍵解読

リバースエンジニアリング

11

相反する概念： Testability and Security

Testability: テストするために内部を見たい

         容易に制御•観測したい

Security:  情報保護のため内部を見せたくない

制御•観測させたくない

両方の要求を同時に満たす回路設計は？

シフトレジスタと等価な回路

（影武者）を用いる   ^1/3

1. 

外部から見るとシフトレジスタとして振る舞う

2. 

内部の振る舞いはシフトレジスタと異なる

13

シフトレジスタ

シフトレジスタ等価回路（影武者）

x y₁ y₂ ^… yk z

y₁ y₂ y_k

x ^… z

影武者は

シフトレジスタと等価な回路

（影武者）を用いる   ^2/3

14

SR等価回路

影武者の例

シフトレジスタ ^{x y}

^y

^y

^z

x

z

y

y

_＋ y

_＋

y

x y

y

_z

x

＋ ^y

＋ y

^y

z

NOT

XOR

シフトレジスタと等価な回路

（影武者）を用いる   ^3/3

15

影武者の

テスタビリティ： 回路構造を知っていれば制御•観測容易

セキュリティ： 回路構造を知らなければ制御•観測できない     

回路構造が特定される確率 ＝ SR等価回路数N(k)の逆数に比例

 影武者が多いほど安全

y1

x y2 y3 z

シフトレジスタ SR等価回路(影武者)の集合

x y1 y2 ＋ y3 ＋ z

y1

x y2 y3 z

x ＋ ^y1 ＋ y2 ^y3 z

他に多数存在

N(k)= (2

)!/k! - 1

シフトレジスタ等価回路

k段シフトレジスタ, SR

k段シフトレジスタ等価回路, C

任意の時刻 t に対して、z(t+k) = x(t) となるとき、

回路Cはk段シフトレジスタと機能等価となり、

「Cはk段SR等価である」という.

x y₁ y₂ ^… yk z

y₁ y₂ yk

x ^… z

時刻 t の入力 x の値が、k クロックサイクル後に出力 z に現れる

記号シミュレーションでSR等価判定

x y₁ y₂ y₃ z

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

x(1) x(0) x(0) y₁(0) y₂(0) y₂(0)

x(2) x(1) x(1) x(0) y₁(0) y₁(0)

x(3) x(2) x(2) x(1) x(0) x(0)

↓ 時

刻

y1 y2 ^y3

x z

y₁ y₂ y3

x z

x y

y

y

z

x(0) y

(0) _y

(0) y

(0) y

(0)

x(1) x(0) y

(0) _y

(0) y

(0)

x(2) _x(1) x(0) y

(0) _y

(0)

x(3) _x(2) x(1) x(0) x(0)

↓ 時

刻

^x (1) ^x (1) ^x (0) = 0 ^x (0) = x(0) 17

状態 (y

(t+3),y

(t+3),y

(t+3))

に遷移させるための入力系列

x(t),x(t+1),x(t+2)は

左のように求まる

x(t) = y

(t+3) ^⊕ y

(t+3)

x(t+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) = y

^{(t) ⊕ y}

^(t)

x(t+1) x(t) y

(t) x(t) ^⊕ y

(t) z(t+1) = y

(t)

x(t+2) x(t+1) x(t) x(t+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)}

SR等価回路の制御  ^1/3

y1 y2 y3

x z

↓ 時

刻

18

R

状態 (y

(t+3),y

(t+3),y

(t+3))

に遷移させるための入力系列

x(t),x(t+1),x(t+2)は

左のように求まる

x(t) = y

(t+3) ^⊕ y

(t+3)

x(t+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) = y

(t) ^⊕ y

(t)

x(t+1) x(t) y

(t) x(t) ^⊕ y

(t) z(t+1) = y

(t)

x(t+2) x(t+1) x(t) x(t+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)}

SR等価回路の制御  ^2/3

y1 y2 y3

x z

↓ 時

刻

19

初期状態に無関係に

所望の状態へ遷移させる

入力系列 容易に求まる

制御 容易

R

x y

y

y

z

1 a b c

1 1 a 1 b

1 1 1 1 a

1 1 0

SR等価回路の制御  ^3/3

y₁ y₂ y₃

x z

x y

y

y

z

0 a b c

1 0 a b

1 1 0 a

1 1 0

y₁ y₂ y3

x z

↓ 時

刻

↓ 時

刻

ト タ 場合 状態 _{(1, 1, 0)}

へ 遷移系列 _{(0, 1, 1)}

SR ^等価回路 R

^{場合 状態} (1, 1, 0)

へ 遷移系列 (1, 1, 1).

攻撃者はR

の回路構造を知らないので

状態(1, 1, 0)へ遷移させるのに失敗する

R

初期状態 (y

(t), y

(t), y

(t))は、

出力 z(t), z(t+1), z(t+2)から

右の式で一意的に識別できる

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) x(t) ^⊕ y

(t) _z ( t+ 1) = y

(t)

x(t+2) x( t+ 1) x(t) x( t+ 1) ⊕ y

(t) _z ( t+ 2) = y

(t)

x( t+ 2) _x( t+ 1) _x( t+ 2) ⊕ _{x(t) z(} t+ 3) = _x(t)

y

(t) = z (t+2)

y

(t) = z(t+1)

y

(t) = z(t) ^⊕ z(t+2)

y1 y2 y3

x z

SR等価回路の観測  ^1/3

21

R

初期状態 (y

(t), y

(t), y

(t))は、

出力 z(t), z(t+1), z(t+2)から

右の式で一意的に識別できる

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) x(t) ^⊕ y

(t) z( t+ 1) = y

(t)

x(t+2) x( t+ 1) x(t) x( t+ 1) ⊕ y

(t) z( t+ 2) = y

(t)

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

y

(t) = z (t+2)

y

(t) = z(t+1)

y

(t) = z(t) ^⊕ z(t+2)

y1 y2 y3

x z

SR等価回路の観測  ^2/3

22

出力系列だけ ら初期状態

を容易に識別で る

観測 容易

R

x y

y

y

z

a 1 1 1 0

b a 1 a 1 1

c b a b 1 1

SR等価回路の観測  ^3/3

y1 y2 y3

x z

x y

y

y

z

1 1 0 0

1 1 １

1 １

y1 y2 y3

x z

↓ 時

刻

↓ 時

刻

ト タ 場合

出力系列 _{(0, 1, 1)} 得 たす _,

初期状態 _{(1, 1, 0)} 識別 _.

SR ^等価回路 R

^場合

出力系列 _{(0, 1, 1)} 得 たす _,

初期状態 _{(1, 1, 1)} 識別 _.

23

攻撃者はR

の回路構造を知らないので

出力系列(0, 1, 1)から初期状態(1, 1, 1)を特定できない

R

スキャン設計への適用  ^1/3

キャン設計回路

Scan Chain

…

Combinational Logic Circuit (Kernel)

Scan Chain

…

…

… … …… …

通常 キャン回路

y1 ^y2 ^y3

x ^z

0 1

0 1

0 1

通常 キャン タ

拡張 キャン タ _SR 等価回路

y₁ y2 y3

x ^{0 1 0 1 0 1 z}

y₁ y2 y3

x ^{0 1 0 1 0 1 z}

スキャン設計への適用  ^2/3

25

SR ^{等価 キャン回路 置 換え}

Scan Chain

Secret Register

Secret Register

Standard Scan

Chain

Standard Scan

Chain

Modified Scan

Chain

(SR-equivalent)

スキャン設計への適用  ^3/3

26

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)

SR等価回路を実現する5種類の線形回路

27

SR等価回路族の濃度

セキュリティレベル： 

構造が特定される確率 ＝ SR等価回路数の逆数に比例

  濃度が大きい → 特定されにくい

I

SR

LF

SR

LFSR

I

LF

SR

I

LFSR

(2

-1)(2

-1)

(2

-1)(2

-1)

2

-1

2

- 1

2

- 1

SR ^等価

k段SR等価回路総数 N(k) = ⁽²

^)! ー 1

発表論文   ^(1/3)   

29

SR ^等価

（１）SR等価回路の列挙と合成

(1-1) Hideo Fujiwara and Marie E. J. Obien, A Secure Scan Design Approach using Extended de Bruijn Graph, 信学会 DC研究会, Feb. 2009.

(1-2) 藤原克哉, 藤原秀雄,玉本英夫 セキュアスキャン設計のためのシフトレジスタ等価回路の列挙      と合成について, 信学会 DC研究会, Dec. 2009.

(1-3) Hideo Fujiwara and Marie E. J. Obien,"Secure and Testable Scan Design Using Extended de Bruijn Graphs, ASP-DAC 2010.

(1-4) 藤原克哉、藤原秀雄、オビエン・マリー・エンジェリン, 玉本英夫、"セキュアスキャン設計の ためのシフトレジスタ等価回路の列挙と合成, 信学会 和文論文誌D-I, Nov. 2010.

（２）SR等価回路の微分動作同値類

(2-2) Hideo Fujiwara, Katsuya Fujiwara, and Hideo Tamamoto, "Secure Scan Design Using Shift Register Equivalents against Differential Behavior Attack, ASP-DAC 2011. (2-3) 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.

発表論文   ^(2/3)    

30

SR ^等価

（３）セキュアスキャン設計支援ツール

(3-1) 藤原克哉, 藤原秀雄, 玉本英夫, SREEP: SR等価回路を用いたセキュアスキャン設計支援ツール, 信学会 DC研究会, Dec. 2010.

(3-2) Katsuya Fujiwara, Hideo Fujiwara, Marie Engelene J. Obien, and Hideo Tamamoto, "SREEP: Shift Register Equivalents Enumeration and Synthesis Program for Secure Scan Design, DDECS 2010.

(3-3) Katsuya Fujiwara, Hideo Fujiwara, and Hideo Tamamoto, "SREEP-2: SR-Equivalent Generator for Secure and Testable Scan Design, WRTLT'10, Dec. 2010.

発表論文   ^(3/3)    

31

SR ^{等価 拡張} SR ^準等価 GFFSR

（４）SR準等価回路を用いたセキュアスキャン設計

(4-1) 藤原克哉, 藤原秀雄, 玉本英夫: シフトレジスタ準等価な回路を用いたセキュアでテスト容易な スキャン設計について, 信学会 VLD研究会, Nov. 2011.

(4-2) Katsuya Fujiwara, Hideo Fujiwara, and Hideo Tamamoto, "SR-Quasi-Equivalents: Yet Another Approach to Secure and Testable Scan Design, WRTLT'11,Nov. 2011. (4-3) Katsuya Fujiwara, Hideo Fujiwara, and Hideo 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.

（５）GFFSRを用いたセキュアスキャン設計

(5-2) Katsuya Fujiwara and Hideo 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.

SREEP: セキュアスキャン設計支援ツール

SREEP (Shift Register Equivalents Enumeration and Synthesis Program)

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

プ グ 公開し います

33

SR ^{等価回路 制約パ ータ設定例}

SREEP SR ^{等価回路へ 変更例} 34

35

SREEP R

^{状態正当化／観測 例}

16 ^段 SR ^等価回路 C

^{結果表示例} 37

まとめ

LSI ^{コン ュータ け}

テ タ テ セキュ テ

あ 意味 相反す 概念

相反す 概念を両立させ こ

キャン設計を例

セキュ つテ ト容易

キャン設計 可能 あ こ を紹介しました

38