[發(fā)明專利]基于遺傳算法和變異分析的優(yōu)化測試向量生成方法

在審

• 申請?zhí)枺?/td>: 201710692560.1
• 申請日: 2017-08-14
• 公開（公告）號: CN107590313A
• 公開（公告）日: 2018-01-16
• 發(fā)明（設(shè)計(jì)）人: 趙毅強(qiáng);劉燕江;解嘯天;劉阿強(qiáng)
• 申請（專利權(quán)）人: 天津大學(xué)
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06N3/12
• 代理公司: 天津市北洋有限責(zé)任專利代理事務(wù)所12201
• 代理人: 劉國威

1.一種基于遺傳算法和變異分析的優(yōu)化測試向量生成方法，其特征是，通過分析母本電路網(wǎng)表的特點(diǎn)，篩選出電路的低活性節(jié)點(diǎn)，并利用軟件測試的變異思想，將低活性節(jié)點(diǎn)的電路結(jié)構(gòu)執(zhí)行變異操作，生成變異體，最后結(jié)合遺傳算法的搜索思想的方法來篩選能殺死變體的測試向量。

2.如權(quán)利要求1所述的基于遺傳算法和變異分析的優(yōu)化測試向量生成方法，其特征是，具體步驟細(xì)化為：

步驟1：搭建測試驗(yàn)證平臺，隨機(jī)產(chǎn)生測試向量并激勵電路：圍繞原始電路搭建測試驗(yàn)證平臺，利用仿真工具VCS對原始電路的門級網(wǎng)表進(jìn)行仿真測試，保存仿真過程文件；

步驟2：統(tǒng)計(jì)電路節(jié)點(diǎn)的翻轉(zhuǎn)情況與翻轉(zhuǎn)概率：分析電路的仿真過程文件，利用腳本編程統(tǒng)計(jì)內(nèi)部節(jié)點(diǎn)的翻轉(zhuǎn)情況和電路運(yùn)行的相關(guān)狀態(tài)，確定電路內(nèi)部各節(jié)點(diǎn)的翻轉(zhuǎn)概率P_i；

步驟3：計(jì)算節(jié)點(diǎn)的低活性臨界概率閾值P_th，并確定低活性節(jié)點(diǎn)列表：根據(jù)內(nèi)部節(jié)點(diǎn)各節(jié)點(diǎn)的翻轉(zhuǎn)概率信息列表，求解節(jié)點(diǎn)翻轉(zhuǎn)率曲線的方差σ²，將3σ作為臨界閾值P_th根據(jù)臨界閾值概率P_th，將翻轉(zhuǎn)概率小于臨界閾值概率P_th的認(rèn)定為低活性節(jié)點(diǎn)，并將重復(fù)節(jié)點(diǎn)、不活動節(jié)點(diǎn)等可疑節(jié)點(diǎn)剔除，確定低活性節(jié)點(diǎn)列表；

步驟4：低活性節(jié)點(diǎn)變異：將低活性節(jié)點(diǎn)分類，分別確定為低1節(jié)點(diǎn)和低0節(jié)點(diǎn)，將兩個(gè)低0節(jié)點(diǎn)的下一級的邏輯電路進(jìn)行低0節(jié)點(diǎn)的變異操作，將兩個(gè)低1節(jié)點(diǎn)的下一級邏輯電路進(jìn)行低1節(jié)點(diǎn)的變異操作，并保存為變體網(wǎng)表；

步驟5：初始化測試向量種群：隨機(jī)產(chǎn)生一組測試向量作為初始種群，另外設(shè)置交叉概率，變異概率和最大迭代次數(shù)等參數(shù)；

步驟6：計(jì)算種群的目標(biāo)函數(shù)值：將種群對應(yīng)的測試向量激勵變異網(wǎng)表，判斷電路響應(yīng)與預(yù)期響應(yīng)是否一致，如果一致，則根據(jù)目標(biāo)函數(shù)計(jì)算種群每個(gè)個(gè)體的目標(biāo)函數(shù)值，否則不計(jì)算目標(biāo)函數(shù)值，繼續(xù)進(jìn)行迭代運(yùn)算；

步驟7：對種群的個(gè)體進(jìn)行選擇、交叉和變異操作：對目標(biāo)函數(shù)值進(jìn)行升序排列，選擇優(yōu)良的個(gè)體進(jìn)入下一次迭代過程，舍棄適應(yīng)度低的個(gè)體，從當(dāng)代個(gè)體進(jìn)行交叉和變異操作，產(chǎn)生下一代個(gè)體；

步驟8：判斷迭代條件是否滿足：判斷當(dāng)前迭代過程是否滿足迭代要求，如果是則輸出當(dāng)代中目標(biāo)函數(shù)值最大的個(gè)體的測試向量為最優(yōu)測試向量，否則返回步驟6繼續(xù)進(jìn)行迭代運(yùn)算。

3.如權(quán)利要求1所述的基于遺傳算法和變異分析的優(yōu)化測試向量生成方法，其特征是，以低活性節(jié)點(diǎn)的翻轉(zhuǎn)次數(shù)作為目標(biāo)函數(shù)，如果目標(biāo)函數(shù)值越大，代表低活性節(jié)點(diǎn)的翻轉(zhuǎn)越頻繁，也就越有可能激活植入在低活性節(jié)點(diǎn)的硬件木馬，目標(biāo)函數(shù)f(t)如式1所示：

f(t)=Σi=1nTCi(t)---(1)]]>

其中n為低活性節(jié)點(diǎn)的數(shù)量，TC_i(t)為第i個(gè)低活性節(jié)點(diǎn)的在t次迭代過程中的翻轉(zhuǎn)次數(shù)。