晶片領域中，過去的設計大部分著眼在速度與面積的改善，但近年來隨著個人隱私與資訊安全的意識高漲，晶片設計也開始針對資安的議題進行考量。過去的數年間，科學家發現不只是軟體上的資訊安全，不安全的硬體設計也有可能造成損害。在全球分工的製造流程中，惡意者可能會把可疑的電路插入晶片中，造成資訊漏洞、效能降低，更有甚者可能損壞晶片。這種可疑的電路被稱為硬體木馬(Hardware Trojan,HT)。亦有多國報告已經警告不明的可疑電路可能造成的威脅，硬體木馬是亟需被注意的潛在威脅。因此也有許多相關的偵測方法被學界提出。
然而，這些方法在進行效能評估時，大都使用隨機取出的節點進行硬體木馬的模型來進行衡量，而這些隨機選取的硬體木馬模型因為其分布機率大部分都偏高，可能會有容易被觸發的問題，從而導致評估結果失準。另外，也有過去研究提到由於低觸發機率之硬體木馬只會在罕見情形下被觸發，現行的偵測方法往往需要巨大的測試成本。我們也需要一個有效的方法進行測試向量(test vector)的生成。最後，既有的方法會遭遇到擴展性(scalability)的瓶頸，我們也需要一個合適的方法來進行解決。
本文同時扮演攻擊者與防禦者角色，作為攻擊方，本文提出一新型混合高低機率硬體木馬，透過本論文所提出方法能夠快速地產生此種難以觸發、難以偵測硬體木馬(HDaT)模型。經實驗結果顯示，本篇論文提出的流程較以往更有效率，相較文獻能達到275.15倍之加速成果，並能依照使用者需求篩選出觸發機率更低的硬體木馬，可以降低觸發機率至少四個數量級。使用者可以自行定義所需之閾值(threshold)來進行模型觸發機率的限定。作為防禦方，本論文也提出一針對這些難以偵測硬體木馬的偵測方法，此方法針對ISCAS’85為本的難以觸發、難以偵測硬體木馬(HDaT)模型中可以有平均93%的觸發覆蓋率以及86%的木馬覆蓋率表現。成本方面，相較其他方法也能以較低的成本達到更高的偵測率。

In the chip field, most of the past designs focused on improving speed and area. In recent years, chip designer has begun to consider security issues with the increasing awareness of personal privacy and information security. Researchers have discovered that not only cyber security but also insecure hardware design may cause severe damage. Adversaries may get their chance to insert suspicious circuits into the chip in the complex global division of labor which causes information loopholes, performance degradation, or damage to the chip. This kind of unidentified circuit is called a Hardware Trojan (HT). Many nation reports have warned about the possible threats caused by hardware trojans, which are potential threats that need urgent attention. Therefore, academia has proposed many detection methods.
However, most use randomly selected inner nodes to model an HT model set to assess these methods. These randomly constructed HT models often have a high trigger probability and may be easily detected, which may lead to inaccurate assessment results. In addition, some literature mentioned that since HT with low trigger probability will only be triggered in rare situations, current detection methods often require huge test costs. We need an effective generation method of test vectors. Finally, the existing methods will encounter scalability bottlenecks, we also need a suitable method to solve them.
This thesis acts the attacker and defender role at the same time. As an attacker, we propose a new hybrid midi-rare trigger probability HT model. The method can also quickly generate this kind of hard-to-detect-and-trigger(HDaT) HT models. The experimental results show that the proposed approach in this paper is more efficient than the previous one. Compared with the literature, it can achieve 275.15 times the acceleration results. It can also filter out HTs with a lower trigger probability according to user needs, reduce the trigger probability by at least four orders of magnitude. Users can define the required threshold to limit the model trigger probability. This method aims ISCAS'85-based HDaT models can achieve an average of 93% trigger coverage and 86% trojan coverage performance. In terms of cost, it can also achieve a higher detection rate at a lower cost than other methods.

論文審定書 i
摘要 iii
Abstract v
目錄 vi
圖目錄 x
表目錄 xiv
第一章 概論 1
1.1. 研究背景 1
1.2. 研究動機 1
1.3. 研究貢獻 2
1.4. 論文章節摘要 3
第二章 研究背景與相關文獻回顧 5
2.1. 硬體木馬(Hardware Trojan) 5
2.2. 硬體木馬偵測方法(Detection Method) 6
2.2.1. 旁通道分析( Side-Channel Analysis, SCA) 7
2.2.2. 邏輯測試(Logic Testing) 9
2.3. 現行研究使用基準電路(Benchmark)來源 10
2.3.1. Trust-Hub基準電路[27] 10
2.3.2. 隨機取樣之硬體木馬模型 11
2.4. 木馬建模方法(Hardware Trojan Modeling) 12
2.5. 評鑑因子(Evaluation Factors) 13
2.5.1. 觸發覆蓋率(Trigger Coverage) 13
2.5.2. 木馬覆蓋率(Trojan Coverage) 13
第三章 硬體木馬 15
3.1. 電路潛藏之可能硬體木馬數量與縮減 15
3.2. 低觸發機率硬體木馬議題 16
3.2.1. 機率分析 16
3.2.2. 木馬模型之觸發機率(trigger probability)分析 18
3.3. 其他作品中的低觸發硬體木馬模型 23
3.4. 合適(Available)難以偵測、觸發之硬體木馬定義 25
第四章 HDaT硬體木馬模型產生流程 26
4.1. 流程之概述 26
4.1.1. 木馬建模流程(Trojan Modeling Process) 27
4.1.2. 木馬篩除流程(Trojan Filtering Process) 28
4.2. 滿足條件之木馬觸發圖樣狀態預先選取(Trojan Activate Pattern Condition Satisfied, TAP-CS) 29
4.2.1. 基於SAT之電路模擬(SAT-Based Simulation) 30
4.2.2. 稀有節點揀選(Rare Nodes Selection) 31
4.3. 可平行化之觸發(trigger)與載體(payload)選取 32
4.3.1. 稀有節點揀選(Rare Nodes Selection) 32
4.3.2. 平行化之運行架構 36
4.4. 內部接線確認(Interconnection Check) 38
4.5. 高觸發率硬體木馬篩除機制 41
4.5.1. N-detection篩選測試 41
4.5.2. 測量電路機制(Miter Circuit) 42
4.6. 混合型硬體木馬模型 43
4.6.1. 二次機率篩選(Second Probability Filtering) 43
4.6.2. 觸發選取空間擴展(Expansion of Trigger Selection Space ) 43
4.6.3. 經流程產生之硬體木馬類型與分類 45
4.7. 實驗結果與分析 47
4.7.1. 加速效果 47
4.7.2. 觸發機率與其在木馬偵測上的影響 48
4.7.3. 模型於偵測方法中之表現 56
第五章 偵測測試圖樣生成 59
5.1. 使用之基準電路與木馬模型、實驗設置 59
5.2. 現有之硬體木馬偵測方法介紹 59
5.2.1. MERO[8]演算法介紹 59
5.2.2. MERO之演算法虛擬碼與設置 60
5.2.3. MERO法之偵測表現 60
5.2.4. 改良型CSF[12]演算法之介紹 62
5.2.5. 改良式CSF之演算法虛擬碼與設置 64
5.2.6. 改良式CSF法之偵測表現 65
5.3. 本論文所提出之偵測方法 66
5.3.1. 混合演算法之介紹 66
5.3.2. 改良式CSF測試圖樣產生情境選用與分析 67
5.3.3. 基於SAT針對更稀有情境多次激發之圖樣產生方法 (SAT-based Multiple Excitation Targeting Rarer Occurrence Pattern Generation Method , METRO) 73
5.3.4. METRO選用之相關變數調整 74
5.3.5. 演算法實作與虛擬碼、實驗設置 76
5.3.6. CSF與METRO聯用之偵測率分析 77
5.3.7. CSF與METRO聯用之成本分析 81
第六章 結語與未來展望 84
參考文獻 86

[1] X. Ngo, V. Hoang and H. L. Duc, “Hardware Trojan Threat and Its Countermeasures,” NAFOSTED Conf. on Information and Computer Science (NICS), pp. 35-40, 2018.
[2] S. Skorobogatov and C. Woods, “Breakthrough Silicon Scanning Discovers Backdoor in Military Chip”, Int’l. Conf. on Cryptographic Hardware and Embedded Syst., pp. 23-40, 2012.
[3] Defense Science Board, DSB Task Force on High Performance Microchip Supply, 2005.
[4] M. Beaumont, B. Hopkins, T. Newby, Hardware Trojans - Prevention, Detection, Countermeasures (A Literature Review), 2011.
[5] S. Adee, “The Hunt for The Kill Switch,” IEEE Spectrum, 45(5), pp34-39, 2008. Tehranipoor and K. Farinaz, “A Survey of Hardware Trojan Taxonomy and Detection,” IEEE Design and Test of Computers, 27(1), pp. 10-25, 2010.
[6] Y. Jin and Y. Makris, “Hardware Trojan Detection Using Path Delay Fingerprint,” IEEE Int’l. Workshop on Hardware-Oriented Security and Trust, pp. 51-57 ,2008.
[7] D. Agrawal, S. Baktir, D. Karakoyunlu, P. Rohatgi, and B. Sunar, “Trojan Detection Using IC Fingerprinting,” IEEE Symp. on Security and Privacy, pp. 296-310, 2007.
[8] R. S. Chakraborty, F. Wolff, S. Paul, C. Papachristou, S. Bhunia, “MERO: A Statistical Approach for Hardware Trojan Detection”, Cryptographic Hardware and Embedded Syst., 2009.
[9] A. BasakChowdhury, A. Banerjee, B. B. Bhattacharya, “ATPG Binning and SAT-Based Approach to Hardware Trojan Detection for Safety-Critical Systems”, Int’l. Conf. on Network and Syst. Security (NSS), pp. 1-20, 2018.
[10] Z. Zhou, U. Guin, V. D. Agrawal, “Modeling and Test Generation for Combinational Hardware Trojans,” IEEE VLSI Test Symp., pp 1-6, 2018.
[11] S. Saha, R. S. Chakraborty, S. S. Nuthakki et al. “Improved Test Pattern Generation for Hardware Trojan Detection Using Genetic Algorithm and Boolean Satisfiability,” Int’l. Workshop on Crytographic Hardware and Embedded Syst., pp. 577-596, 2015.
[12] H. H. Lin, Efficient Identification and Test Methods of Hard-to-Detect Combinational Hardware Trojans, Master Thesis, Department of Electrical Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan, 2020.
[13] C. Bao, D. Forte and A. Srivastava, “On Reverse Engineering-Based Hardware Trojan Detection,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Sytm., pp 49-57, 2016.
[14] S. Dupuis, M. Flottes, G. Di Natale and B. Rouzeyre, “Protection Against Hardware Trojans With Logic Testing: Proposed Solutions and Challenges Ahead,” IEEE Design and Test, 35(2), pp. 73-90, 2018.
[15] K. Xiao, D. Forte, Y. Jin, R. Karri, S. Bhunia and M. Tehranipoor, “Hardware Trojans: Lessons Learned after One Decade of Research,” ACM Trans. Des. Autom. Electron. Syst., 22(1), pp. 1-23, 2016.
[16] N. Seetharam, D. Du. R. S. Chakraborty et al. “Hardware Trojan Detection by Multiple-Parameter Side-Channel Analysis,” IEEE Trans. on Computers, 62(11), pp. 2183-2195, 2012.
[17] D. Du, S. Narasimhan, R. S. Chakraborty and S. Bhunia “Self-Referencing: A Scalable Side-Channel Approach for Hardware Trojan Detection,” Int’l. Workshop on Cryptographic Hardware and Embedded Syst., pp. 173-187, 2010.
[18] Y. Huang, S. Bhunia and P. Mishra, “Scalable Test Generation for Trojan Detection Using Side Channel Analysis,” IEEE Trans. on Information Forensics and Security, 13(11), pp. 2746-2760, 2018.
[19] Y. Huang, S. Bhunia and P. Mishra, “MERS: Statistical Test Generation for Side-Channel Analysis based Trojan Detection”, ACM Conf. Comput. Commun. Security (CCS), pp. 131-141, 2016.
[20] N. Q. M. Noor, N. N. A. Sjarif, N. H. F. M. Azmi et al. “Hardware Trojan Identification Using Machine Learning-Based Classification,” Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(3-4), 23-27. 2017.
[21] K. Hasegawa, M. Oya, M. Yanagisawa et al., "Hardware Trojans Classification for Gate-level Netlists Based on Machine Learning,” Int’l. Symp. on On-Line Testing and Robust Syst. Design (IOLTS), pp. 203-206, 2016.
[22] Borkar, S., Karnik, T., Narendra, S., Tschanz, J., Keshavarzi, A., and De, V. “Parameter Variations and Impact on Circuits and Microarchitecture,” Design Automation Conf. , pp. 338-342, 2003.
[23] I. Pomeranz and S.M. Reddy, “A Measure of Quality for N-Detection Test Sets,” IEEE. Trans. on Computers, 53(11), pp. 1497-1503, 2004.
[24] Y. Lyu and P. Mishra, “Scalable Activation of Rare Triggers in Hardware Trojans by Repeated Maximal Clique Sampling,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Syst., 40(7), pp. 1287-1300, 2021.
[25] S. Narasimhan, D. Du, R. S. Charkraborty et al., “Hardware Trojan Detection by Multiple-Parameter Side-Channel Analysis,” IEEE Trans. on Computers, 62(11), pp. 2183-2195, 2013.
[26] J. Cruz, F. Farahmandi, A. Ahmed, and P. Mishra, “Hardware Trojan Detection Using ATPG and Model Checking,” Int’l. Conf. on VLSI Design and 2018 17th Int’l. Conf. on Embedded Syst. (VLSID), pp. 91-96, 2018.
[27] H. Salami, M. Tehranipoor (2018) System-level & Chip-level Trojan Benchmarks [Online]. Available: https://trust-hub.org/benchmarks
[28] H. Salmani, M. Tehranipoor and J. Plusquellic, “A Novel Technique for Improving Hardware Trojan Detection and Reducing Trojan Activation Time,” IEEE Trans. on Very Large Scale Integration Syst., 20(1), pp. 112-125, 2011.
[29] D. Bryan, The ISCAS’85 Benchmark Circuits and Netlist Format, North Carolina State University, 1985.
[30] F. Brglez, D. Bryan and K. Kozminski, “Combinational Profiles of Sequential Benchmark Circuits”, Int'l. Symp. Circuits and Syst., pp. 1929-1934, 1989.
[31] F. Corno, M.S. Reorda, G. Squillero, “RT-level ITC’99 Benchmarks and First ATPG Results,” IEEE Design & Test of Computers, 17(3), pp. 44-53, 2000.
[32] D. Deng, Y. Wang and Y. Guo, “Novel Design Strategy Toward A2 Trojan Detection Based on Built-In Acceleration Structure,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Syst., 39(12), pp. 4496-4509, 2020.
[33] S. Disch, C. Scholl, “Combinational Equivalence Checking Using Incremental SAT Solving, Output Ordering and Resets”, Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 1-6, 2007.
[34] N. Een, N. Sörensson, “An Extensible SAT-solver,” Int’l. Conf. on Theory and Applications of Satisfiability Testing, pp. 502-518, 2003.