[發明專利]一種面向FPGA芯片的網表環路識別方法

有效

• 申請號: 202010167733.X
• 申請日: 2020-03-11
• 公開（公告）號: CN111353182B
• 公開（公告）日: 2023-05-05
• 發明（設計）人: 王堅;李桓;楊鍊;陳哲;郭世澤
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F21/76
• 分類號: G06F21/76
• 代理公司: 北京正華智誠專利代理事務所(普通合伙) 11870
• 代理人: 李夢蝶

本發明公開了一種面向FPGA芯片的網表環路識別方法，包括以下步驟：S1：提取FPGA芯片的網表文件；S2：建立有向圖模型；S3：結合棧結構對有向圖模型進行深度優先遍歷，識別有向圖模型的環路；S4：識別嵌套環路；S5：基于嵌套環路，利用分步循環聚合策略提取聚合環路，得到FPGA芯片的網表環路識別結果。本發明提出了一種新型的FPGA芯片網表環路識別方法。該網表環路識別方法利用構建有向圖模型，對其進行識別；同時提出了嵌套環路的概念，對網表中的嵌套環路進行識別；最后提出了分布循環聚合的策略，識別有向圖模型中的聚合環路。該識別方法操作簡單，能夠保證對網表環路的正確識別。

技術領域

本發明屬于芯片硬件安全技術領域，具體涉及一種面向FPGA芯片的網表環路識別方法。

背景技術

當前，半導體工業和各種生產技術廣泛發展，芯片越來越小，功能卻越來越復雜。然而，無論是在設計階段，還是實際芯片制造階段，數字化集成電路都可能會遇到各種各樣的硬件攻擊。集成電路的一種新型硬件攻擊，稱為硬件木馬，已經成為一種重要的近年來的研究課題。硬件木馬可以禁用或更改集成電路的功能，或泄漏敏感的用戶信息。現代FPGA自動化設計基本流程包括綜合、映射、布局布線和生成比特流，其中綜合后生成的網表文件占據著極其重要的地位。此外，網表文件也是硬件木馬入侵的主要文件。因此，對于網表文件的相關研究對于硬件安全的保護至關重要。

芯片網表環路是網表中的一種常見結構，在基于網表的研究中往往需要進行特殊處理。然而，由于網表中元器件的數量多，元器件之間的邏輯關系復雜，研究人員很難準確地識別網表中的環路，導致后續基于網表的研究也無法正常進行。目前，學術界很少有關于FPGA網表文件中環路識別相關的研究。基于以上情況，本發明提出了一種面向FPGA芯片的網表環路識別方法。

發明內容

本發明的目的是為了解決FPGA芯片的網表環路識別方法的問題，提出了一種面向FPGA芯片的網表環路識別方法。

本發明的技術方案是：一種面向FPGA芯片的網表環路識別方法包括以下步驟：

S1：輸入FPGA芯片的網表文件；

S2：建立網表文件的有向圖模型；

S3：結合棧結構對有向圖模型進行深度優先遍歷，識別有向圖模型的環路；

S4：識別環路中的嵌套環路；

S5：利用分步循環聚合策略提取環路中的聚合環路，得到FPGA芯片的網表環路識別結果。

本發明的有益效果是：本發明提出了一種新型的FPGA芯片網表環路識別方法。該網表環路識別方法利用構建有向圖模型，對其進行識別；同時提出了嵌套環路的概念，對網表中的嵌套環路進行識別；最后提出了分布循環聚合的策略，識別有向圖模型中的聚合環路。該識別方法具有操作簡單和易于實現的特點，能夠保證對網表環路的正確識別。

進一步地，步驟S2包括以下子步驟：

S21：設定網表文件的寄存器集合為R；

S22：根據寄存器集合構建網表文件的頂點集合為V；

S23：根據寄存器集合構建網表文件的有向邊集合為E，得到有向圖模型G＝(V，E)，完成有向圖模型的建立。

上述進一步方案的有益效果是：在本發明中，使用G＝(V，E)表示有向圖，其中G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合，其表示方法簡單易操作。

進一步地，步驟S22中，寄存器集合R和頂點集合V具有一對一的關系，記為r_i→v_i，r_i∈R，v_i∈V，其頂點集合V有如下性質：

對于使得r_i→v_i成立；