[發明專利]一種基于Kruskal算法的混淆有限狀態機構建方法

在審

• 申請號: 201810105737.8
• 申請日: 2018-02-02
• 公開（公告）號: CN108470083A
• 公開（公告）日: 2018-08-31
• 發明（設計）人: 張躍軍;潘釗;丁代魯;王佳偉
• 申請（專利權）人: 寧波大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 寧波奧圣專利代理事務所(普通合伙) 33226
• 代理人: 方小惠

本發明公開了一種基于Kruskal算法的混淆有限狀態機構建方法，該方法中采用Kruskal算法來確定所構建的混淆有限狀態機的各混淆狀態之間的跳轉方式，通過將任意兩個混淆狀態之間的漢明距離定義為Kruskal算法中對應的權重，采用Kruskal算法找尋權重最小的最小生成樹(Minimum Spanning Tree,MST)，即最小的漢明距離；優點是構建的混淆有限狀態機的開銷較小，通過實驗驗證，在基準電路和密碼算法電路中的實驗結果表明，本發明的方法構建的混淆有限狀態機的電路開銷比當前采用其他方法構建的混淆有限狀態機的電路開銷在整體上明顯減小。

技術領域

本發明涉及一種混淆有限狀態機構建方法，尤其是涉及一種基于Kruskal算法的混淆有限狀態機構建方法。

背景技術

集成電路(Integrated Circuit,IC)供應鏈中的硬件知識產權(IntellectualProperty,IP)盜版，過度生產和逆向工程的現象，給知識產權的侵犯創造了機會。現有的數據保護是通過混淆即改變IC設計來隱藏電路的功能來達到保護目的。目前的數字集成電路主要有組合電路和時序電路兩大類。對組合電路進行混淆是向IC設計的門級網表中插入額外的關鍵門，而設計者能通過密鑰對IC的功能進行控制；對時序電路進行混淆是通過對電路中的有限狀態機(Finite State Machine,FSM)狀態的修改，使得修改后的狀態機不能直接跳轉到原始有限狀態機的有效狀態，需要IC設計者對其解鎖才能正確跳轉到原始有限狀態機的有效狀態，從而保護硬件IP核。

目前，對于時序電路來說，常用來保護硬件IP核的方法是構建混淆有限狀態機。Lao等提出一種兩級混淆有限狀態機架構以及基于兩級混淆有限狀態機的新型自校正方法，其構建的兩級混淆有限狀態機架構不僅可驗證時序電路或時序電路內部的IP，也可消除誤差校正技術。但是其構建的兩級混淆有限狀態機架構沒有考慮各層混淆狀態之間的跳轉關系，由此導致構建的混淆有限狀態機硬件開銷較大等問題。

發明內容

本發明所要解決的技術問題是提供一種電路開銷小的基于Kruskal算法的混淆有限狀態機構建方法。

本發明解決上述技術問題所采用的技術方案為：一種基于Kruskal算法的混淆有限狀態機構建方法，包括以下步驟：

①采用Quartus軟件和Debussy軟件提取待保護的時序電路中的原始有限狀態機，根據提取的原始有限狀態機確定原始有限狀態機的起始位置、原始有限狀態機的有效狀態的數量以及各有效狀態的二進制編碼，將原始有限狀態機的有效狀態的數量記為M；

②將待構建的混淆有限狀態機的混淆狀態的數量記為N，N滿足條件：M+N＝2ⁿ，其中n為正整數，且n大于等于原始有限狀態機的有效狀態的二進制編碼的位寬；

③計算原始有限狀態機的M個有效狀態的二進制編碼對應的十進制數，從0～2ⁿ-1這2ⁿ個十進制數中去除原始有限狀態機的M個有效狀態的二進制編碼對應的十進制數，得到N個位于0～2ⁿ-1之間的十進制數，將這N個0～2ⁿ-1之間的十進制數與混淆有限狀態機中N個混淆狀態一一對應，將各個混淆狀態對應的十進制數轉換為n位的二進制編碼賦予該混淆狀態，并分別定義混淆有限狀態機的各混淆狀態的名稱；

④將N個混淆狀態的名稱以及N個混淆狀態的二進制編碼作為Kruskal算法的輸入，確定漢明距離之和最小情況下的各混淆狀態的連接關系，具體過程為：

a.采用Kruskal算法自動計算每兩個混淆狀態的二進制編碼之間的漢明距離以及各混淆狀態與自身的漢明距離，將計算得到的N×N個漢明距離的值存放在N×N的鄰接矩陣中，該鄰接矩陣具有對稱性，該鄰接矩陣的主對角線上存放的漢明距離的值全為零；