面對科技日新月異地進步，人們漸漸開始重視資訊安全相關議題。除了軟體的資訊安全之外，在過去十年間科學家發現了人們使用的電子儀器中可能潛藏著危害，稱為硬體安全。硬體安全源自全球分工製造晶片，駭客得以在過程中被插入可疑電路，科學家將此可疑電路命名為硬體木馬。一旦硬體木馬被啟動，可能會造成資訊外洩、效能降低，甚至直接毀壞使用中的電子儀器。因此，如何有效且低成本地偵測硬體木馬成為了一項重要的議題。然而，直接根據簡單的定義進行硬體木馬的偵測將會造成硬體木馬在電路中的可能性過多，最終導致偵測成本高居不下。為了解決這個問題，本篇論文從駭客的角度出發分析真正會被安插的硬體木馬應該擁有的必要條件，並根據這些必要條件提出藏於電路中難以偵測硬體木馬的定義。根據難以偵測硬體木馬的定義，本篇論文建立難以偵測硬體木馬模型的生成演算法。在不同的電路之中，此流程皆能抓出可能潛藏的硬體木馬危害為何，且其模型的結果能夠作為硬體木馬測試基準。實驗結果顯示本篇論文所提出的模型生成流程能夠刪去平均96.44%不必要的硬體模型，凸顯出電路中真正可能潛藏危害的地方為何。
為了進一步降低硬體木馬的測試成本，本篇論文除了使用難以偵測硬體木馬模型之外，也針對這些硬體木馬提出一測試圖樣生成演算法。透過硬體木馬模型條件的組合並壓縮在相同的測試圖樣中測試，本篇論文的使用ISCAS’85測試基準電路進行實驗的結果與過去的方法相比可以減少平均84.48%的測試圖樣，且難以偵測硬體木馬的平均偵測率可高達97.08%。

Due to the globalization of integrated circuit (IC) production flow, adversary (or attacker) can easily implant malicious circuit into ICs, resulting in leakage of confidential information, or even destroy of the whole system. These malicious circuits, referred to as hardware Trojan, are deeply hidden in the normal operation, and only triggered in some specific situation. This characteristic makes hardware Trojan hard to be detected by typical manufacturing test methodology. However, the number of potential hardware Trojan will grow significantly larger for bigger circuits, causing high testing overhead. In order to reduce the number of potential hardware Trojans, we analyzed four factors of hardware Trojan and define hard-to-detect Trojan (HTD Trojan). Accordingly, a systematic generation flow of test sets for HTD Trojan models is developed, which can generate the proper hardware Trojans models in different circuits. The result shows that this flow can reduce up to 96.44% inappropriate models and highlights critical hardware Trojan risks in the circuit. For the purposes of minimizing testing overhead, a HTD Trojan test pattern generation method is proposed. This method combines multiple conditions of HTD models into groups to achieve highly efficient detection. To study the effectiveness of patterns generated by the proposed method, we used ISCAS’85 benchmark circuits to evaluate the Trojan detectability. When comparing to the previous research, our method can reduce up to 84.48% test patterns on average and detects 97.08% HTD models on average.

論文審定書 i
致謝 ii
摘要 iv
Abstract v
目錄 vi
圖目錄 ix
表目錄 xi
第一章 概論 1
1.1. 研究背景 1
1.2. 研究動機 2
1.3. 研究貢獻 2
1.4. 論文大鋼 4
第二章 相關文獻探討 5
2.1. 硬體安全性的困難點 5
2.2. 硬體木馬(Hardware Trojan) 7
2.3. 硬體木馬偵測方法 8
2.4. 硬體木馬測試基準(Hardware Trojan Benchmark)之分類 10
2.5. 硬體木馬模型之建立(Hardware Trojan Modeling) 12
第三章 難以偵測木馬(Hard-To-Detect Trojan, HTD Trojan) 14
3.1. 硬體木馬可能存在數量之分析 14
3.2. 硬體木馬偵測難易度之分析 15
3.3. 難以偵測木馬之必要條件探討 16
3.3.1. 必要條件一：硬體木馬需要具有高隱藏性[4] 16
3.3.2. 必要條件二：硬體木馬攻擊效應的可傳遞性 17
3.3.3. 必要條件三：完美的硬體木馬不會造成接線問題 19
3.3.4. 必要條件四：硬體木馬的激發機率應盡可能低 21
3.4. 難以偵測硬體木馬之定義 22
第四章 難以偵測硬體木馬建模演算法 23
4.1. 硬體木馬激發條件之數量範圍分析 23
4.1.1. 考量一：測試流程常用測試圖樣 23
4.1.2. 考量二：VLSI設計條件 23
4.1.3. 考量三：旁通道(Side-Channel Information)資訊洩漏 24
4.2. 難以偵測硬體木馬建模演算法之實現流程 25
4.2.1. 步驟一：硬體木馬激發條件之挑選 26
4.2.2. 步驟二：硬體木馬載體位置之挑選 27
4.2.3. 步驟三：硬體木馬接線檢查步驟 28
4.2.4. 步驟四：硬體木馬模型篩檢 29
4.3. 變數調校 30
4.3.1 硬體木馬載體位置選擇步驟的行為模式部分之實現效益與困難性分析 30
4.3.2 N次測試圖樣之測試數量分析 32
4.3.3 硬體木馬模型之隨機取樣 33
4.4. 實驗結果與分析 33
4.4.1. 難以偵測硬體木馬模型之數量結果 34
4.4.2. 接線檢查的預處理步驟之效益分析 36
4.4.3. 執行時間 37
第五章 難以偵測硬體木馬測試圖樣生成演算法 38
5.1. 現有測試圖樣生成演算法 38
5.1.1. N次測試圖樣 38
5.1.2. 條件式單一固定型錯誤測試圖樣產生演算法[4] 39
5.2. 難以偵測硬體木馬測試圖樣生成演算法 40
5.2.1. 難以偵測硬體木馬測試圖樣生成演算法之原理 40
5.2.2. 用於難以偵測硬體木馬測試圖樣生成之模型隨機取樣 42
5.3. 難以偵測硬體木馬測試圖樣生成演算法之實現流程 43
5.3.1. 難以偵測硬體木馬條件式之整理 43
5.3.2. 難以偵測硬體木馬條件式壓縮與測試圖樣生成 44
5.4. 生成測試圖樣所需硬體木馬模型之數量分析 46
5.5. 實驗結果與分析 48
5.5.1. 測試圖樣之數量 48
5.5.2. 難以偵測硬體木馬之偵測率 49
5.5.3. 難以偵測硬體木馬測試圖樣之生成執行時間 50
5.5.4. 難以偵測硬體木馬之壓縮比例分析 50
第六章 結論與未來展望 52
參考文獻 53

[1] M. Lipp, et al. “Meltdown: Reading kernel memory from user space,” in Security Symposium, pp. 973-990, 2018.
[2] P. Kocher, et al. “Spectre attacks: Exploiting speculative execution,” in IEEE Symposium on Security and Privacy, pp. 1-19, 2019.
[3] M. Tehranipoor and K. Farinaz, “A survey of hardware trojan taxonomy and detection,” IEEE design & test of computers, vol. 27, no.1, pp. 10-25, 2010.
[4] Z. Zhou, G. Ujjwal and V. D. Agrawal, “Modeling and test generation for combinational hardware Trojans,” in IEEE VLSI Test Symposium, pp. 1-6, 2018.
[5] M. L. Bushnell and V. D. Agrawal, “Digital DFT and scan design,” in Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits, Springer Science & Business Media, 2004.
[6] R. S. Chakraborty, S. Narasimhan and S. Bhunia, “Hardware Trojan: Threats and emerging solutions,” in IEEE International High-Level Design Validation and Test Workshop, pp. 166-171, 2009.
[7] M. Tehranipoor and C. Wang, “Security and testing,” in Introduction to Hardware Security and Trust, Springer Science & Business Media, 2011.
[8] S. Yao, et al. “FASTrust: Feature analysis for third-party IP trust verification,” IEEE International Test Conference, pp. 1-10, 2015.
[9] H. Salmani and M. Tehranipoor, “Vulnerability analysis of a circuit layout to hardware Trojan insertion,” IEEE Transactions on Information Forensics and Security, vol.11, no.6, pp. 1214-1225, 2016.
[10] J. Robertson and M. Riley (2018). The Big Hack: How China Used a Tiny Chip to Infiltrate U.S. Companies [Online]. Available: https://www.bloomberg.com/news/features/2018-10-04/the-big-hack-how-china-used-a-tiny-chip-to-infiltrate-america-s-top-companies
[11] Semiconductor Industry Association (2018). Global Billings Report History [Online]. Available: http://www.sia-online.org/galleries/Statistics/GSR1976-March09.xls.
[12] Defense Science Board (2005). Task Force on High Performance Microchip Supply [Online]. Available: http://www.acq.osd.mil/dsb/reports/200502HPMSReportFinal.pdf.
[13] DARPA (2007). Trust in Integrated Circuits - Proposer Information Pamphlet [Online]. Available: http://www.darpa.mil/MTO/solicitations/baa07-24/index.html.
[14] Chakraborty, Rajat Subhra, et al. “MERO: A statistical approach for hardware Trojan detection,” in International Workshop on Cryptographic Hardware and Embedded Systems, pp. 396-410, 2009.
[15] Y. Huang, S. Bhunia and P. Mishra, “Scalable test generation for Trojan detection using side channel analysis,” IEEE Transactions on Information Forensics and Security, vol. 13, no. 11, pp. 2746-2760, Nov. 2018.
[16] Hasegawa, Kento, et al. “Hardware Trojans classification for gate-level netlists based on machine learning,” in IEEE International Symposium on On-Line Testing and Robust System Design, pp. 203-206, 2016.
[17] Z. Huang, Q. Wang, Y. Chen and X. Jiang, “A survey on machine learning against hardware Trojan attacks: Recent advances and challenges,” IEEE Access, vol. 8, pp. 10796-10826, 2020.
[18] Narasimhan, Seetharam, et al. “Hardware Trojan detection by multiple-parameter side-channel analysis,” IEEE Transactions on Computers, vol. 62, no.11, pp. 2183-2195, 2012.
[19] Du, Dongdong, et al. “Self-referencing: A scalable side-channel approach for hardware Trojan detection,” in International Workshop on Cryptographic Hardware and Embedded Systems, pp. 173-187, 2010.
[20] Y. Liu, K. Huang and Y. Makris, “Hardware Trojan detection through golden chip-free statistical side-channel fingerprinting,” in Design Automation Conference, pp. 1-6, 2014.
[21] S. Borkar, T. Karnik, S. Narendra, J. Tschanz, A. Keshavarzi and V. De, “Parameter variations and impact on circuits and microarchitecture,” in ACM/IEEE Design Automation Conference, pp. 338-342, 2003.
[22] M. Zou, X. Cui, L. Shi and K. Wu, “Potential trigger detection for hardware Trojans,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 37, no. 7, pp. 1384-1395, July 2018.
[23] H. Salmani, M. Tehranipoor and J. Plusquellic, “A novel technique for improving hardware Trojan detection and reducing Trojan activation time,” IEEE Transactions on Very Large Scale Integration Systems, vol. 20, no. 1, pp. 112-125, Jan. 2012.
[24] M. Yoshimura, T. Bouyashiki and T. Hosokawa, “A hardware Trojan circuit detection method using activation sequence generations,” IEEE International Symposium on Dependable Computing, pp. 221-222, 2017.
[25] Aarestad, Jim, et al. “Detecting Trojans through leakage current analysis using multiple supply pad,” IEEE Transactions on Information Forensics and Security, vol.5, no.4, pp. 893-904, 2010.
[26] H. Salmani, M. Tehranipoor (2018) System-level & Chip-level Trojan Benchmarks [Online]. Available: https://trust-hub.org/benchmarks
[27] D. Bryan, “The iscas’85 benchmark circuits and netlist format,” North Carolina State University, vol. 25, 1985.
[28] K. Y. Cho, S. Mitra and E. J. McCluskey “Gate exhaustive testing,” IEEE International Conference on Test, pp. 1-7, 2005.
[29] M. L. Bushnell and V. D. Agrawal, Essentials of Electronic Testing for Digital Memory and Mixed-Signal VLSI Circuits, Springer, 2000.
[30] “TSMC 0.13 μm CMOS process,” TSMC, Inc., 2000.
[31] “TSMC 90 nm CMOS process,” TSMC, Inc., 2004.
[32] “TSMC 40 nm CMOS process,” TSMC, Inc., 2008.
[33] “UMC 0.18 μm CMOS process,” UMC, Inc., 1999.
[34] S. Saha, R. S. Chakraborty, S. S. Nuthakki and D. Mukhopadhyay, “Improved test pattern generation for hardware trojan detection using genetic algorithm and boolean satisfiability,” in International Workshop on Cryptographic Hardware and Embedded Systems, pp. 577-596, 2015.
[35] S. Saha, R. S. Chakraborty and D. Mukhopadhyay, “Testability based metric for hardware Trojan vulnerability assessment,” in Euromicro Conference on Digital System Design, 2016.
[36] V. Kumar, “Algorithms for constraint-satisfaction problems: A survey,” AI magazine, vol.13, no.1, pp. 32-32, 1992.
[37] N. Een, A. Mishchenko and N. Amla, “A single-instance incremental SAT formulation of proof-and counterexample-based abstraction,” Formal Methods in Computer Aided Design, pp. 181-188, 2010.
[38] T. Eibach, E. Pilz and G. Völkel, “Attacking Bivium using SAT solvers,” in International Conference on Theory and Applications of Satisfiability Testing, pp. 63-76, 2008.
[39] M. Järvisalo, D. L. Berre, O. Roussel and L. Simon, “The international SAT solver competitions,” AI Magazine, vol. 33, no. 1, pp. 89-92, 2012.