基于改進(jìn)遺傳算法的軟件單元安全性測試仿真

王 超，龐先偉

(西南財(cái)經(jīng)大學(xué)，四川 成都 610074)

1 引言

目前，計(jì)算機(jī)軟件在各領(lǐng)域得到廣泛使用，已成為人們工作與生活的重要組成部分。軟件的安全問題會造成一定的財(cái)產(chǎn)與隱私風(fēng)險(xiǎn)。因此在軟件開發(fā)中安全檢測是關(guān)鍵環(huán)節(jié)。其主要目的是通過少量測試用例實(shí)現(xiàn)最大的檢測覆蓋面，保證及時(shí)發(fā)現(xiàn)軟件存在的安全隱患，進(jìn)而改善軟件可靠性。但是計(jì)算機(jī)程序日益復(fù)雜，軟件漏洞查找難度逐漸增大。為解決該問題，相關(guān)專家已經(jīng)得到了一些可應(yīng)用的研究成果。

文獻(xiàn)[1]提出軟件安全檢測方法。利用安全控制結(jié)構(gòu)，建立描述軟件過程的變量模型。綜合分析危險(xiǎn)發(fā)生系統(tǒng)上下文信息，將其作為軟件安全性要求。設(shè)計(jì)控制系統(tǒng)軟件，采用模型檢驗(yàn)技術(shù)對軟件安全性進(jìn)行測試。文獻(xiàn)[2]在區(qū)塊鏈基礎(chǔ)上構(gòu)建軟件安全檢測模型。當(dāng)一個(gè)區(qū)塊鏈高于六個(gè)區(qū)塊后，此區(qū)塊的內(nèi)容將不能被改變，認(rèn)為其達(dá)到穩(wěn)定狀態(tài)，威脅出現(xiàn)的概率有效降低，根據(jù)每個(gè)區(qū)塊到達(dá)穩(wěn)定狀態(tài)的幾率來判斷軟件是否安全。

上述兩種傳統(tǒng)方法具有較好安全檢測性能，但是實(shí)際應(yīng)用中出現(xiàn)了漏檢率偏高問題。為此本文利用改進(jìn)的遺傳算法測試軟件單元安全性。在傳統(tǒng)遺傳算法基礎(chǔ)上，引入種群活力思想，綜合分析種群多樣性與鄰近種群之間相似度，利用并行機(jī)理改進(jìn)變異操作過程。仿真結(jié)果表明，所提方法降低了漏檢率，對軟件可疑點(diǎn)測試更加全面，表現(xiàn)出了較高應(yīng)用價(jià)值。

2 軟件威脅分類與異常特征分析

2.1 安全威脅分類

1)系統(tǒng)軟件安全威脅

操作系統(tǒng)屬于最關(guān)鍵的軟件之一，是智能終端的核心，若系統(tǒng)存在安全威脅，則用戶隱私信息可能暴露?，F(xiàn)階段操作系統(tǒng)威脅分為：系統(tǒng)漏洞、系統(tǒng)底層API(Core Audio APls)濫用等。

系統(tǒng)漏洞[3]能夠?qū)浖踩斐蓺缧晕：?，例如iOS(Internet work Operating System)越獄行為就是通過存在的漏洞破壞系統(tǒng)，屬于主動破壞行為。一些漏洞問題會在網(wǎng)絡(luò)中公開，因此攻擊者能夠任意使用漏洞資源對軟件進(jìn)行攻擊。

2)應(yīng)用軟件安全威脅

此種威脅主要由惡意軟件[4]引起。在傳統(tǒng)互聯(lián)網(wǎng)中對惡意軟件研究起步較晚，缺乏對其識別的標(biāo)準(zhǔn)。為提高整體網(wǎng)絡(luò)安全環(huán)境，提出惡意軟件代碼描述規(guī)范。此規(guī)范中分類惡意元件，包括信息竊取、資費(fèi)消耗、系統(tǒng)破壞等。

2.2 軟件異常特征分析

軟件安全問題體現(xiàn)在多個(gè)方面，比如：CPU占用量較大，表明軟件存在潛在風(fēng)險(xiǎn)，可優(yōu)化其空間；電量大量消耗表明可能有惡意軟件正在資源消耗；內(nèi)存快速減少說明內(nèi)存遭到泄漏。結(jié)合上述的軟件安全分類結(jié)果，將軟件有關(guān)安全問題與系統(tǒng)性能特性指標(biāo)一一對應(yīng)，總結(jié)結(jié)果表1所示。

3 基于改進(jìn)遺傳算法的軟件單元安全性測試

3.1 軟件安全性度量性選擇

遺傳方法是一種自適應(yīng)搜索算法，與優(yōu)勝略汰思想相同，存在自適應(yīng)性與并行性，有助于處理海量復(fù)雜數(shù)據(jù)，可以解決軟件質(zhì)量度量屬性選取問題[5]。此外，該方法還能對任意一個(gè)度量屬性做出優(yōu)劣評判，而不局限于評價(jià)單一軟件安全性，確保選擇的度量屬性子集最優(yōu)化，提高搜索效率，屬性選取過程如圖1所示。

圖1 遺傳算法的軟件質(zhì)量屬性選取過程

3.1.1 度量屬性編碼

編碼方式是遺傳算法的重要內(nèi)容，表示全部軟件屬性子集的解空間。常用的編碼方式較多，由于軟件質(zhì)量度量屬性僅有選中與不選兩種結(jié)果，因此本文利用二進(jìn)制編碼。

例如某六個(gè)軟件安全性度量屬性表示為{y1y2y3y4y5y6}，因此{(lán)111010}代表一個(gè)可能屬性子集合，其中1表示被選中，0表征未被選中。

3.1.2 初始種群選擇

在遺產(chǎn)算法中必須先確定一個(gè)潛在解，將其視為初始種群[6]。因?yàn)槌跏挤N群分布狀況會影響該算法全局收斂性，假設(shè){X(n);n≥1}表示算法中種群馬爾科夫鏈，pm=0，X(0)=X0，因此可以得出：

1)針對Y∈L(X0)，有n≥0的情況存在，所以P{Y∈X(n)/X(0)=X0}>0；

2)針對Y?L(X0)，有n≥0的情況發(fā)生，因此P{Y∈X(n)/X(0)=X0}=0。

上述中，pm表示變異幾率，L(X0)代表初始種群最小規(guī)模，X(n)為第n代種群，Y是種群中任意一個(gè)個(gè)體。

通過上述分析可知，初始種群確定問題的本質(zhì)是利用有限個(gè)體表示空間特征優(yōu)化。因此種群規(guī)模不可隨意確定，只有將空間內(nèi)最優(yōu)個(gè)體作為初始種群，才可以很好的體現(xiàn)空間內(nèi)部特性。因此在確定種群后需要自適應(yīng)調(diào)整交叉變異概率。

3.1.3 變異概率自適應(yīng)調(diào)整

本文改進(jìn)傳統(tǒng)的AGA(Adaptive Genetic Algorithm)與PAGA(Prominent Adaptive Genetic Algorithm)自適應(yīng)交叉變異概率調(diào)整方法。假定對第t代種群中第i個(gè)個(gè)體做交叉變異處理[7]，則AGA方法中變異幾率計(jì)算公式如下

(1)

(2)

式中，f′t表示未交叉的個(gè)體中較高的適應(yīng)度值，k1、k2、k3與k4是[0，1]區(qū)間的數(shù)，k3、k4高于k1、k2。在此種算法中，自適應(yīng)度值越高，參與交叉變異的幾率就越低。因此有利于在進(jìn)化過程中保存較多優(yōu)質(zhì)個(gè)體，但是其中一些優(yōu)質(zhì)個(gè)體無法參加遺傳操作，易產(chǎn)生早熟現(xiàn)象。

而在PAGA中，適應(yīng)度值越高，參與交叉操作的可能性就越大，其交叉概率計(jì)算公式表示為

(3)

研究上述兩種算法，得出產(chǎn)生問題的主要原因是這兩種方法均沒有分析整個(gè)種群進(jìn)化情況[8]。在進(jìn)化初始時(shí)期，種群差異性較大，自適應(yīng)值也相對較大，但為使優(yōu)良模式傳播效果更好，對自適應(yīng)度值較高的個(gè)體定義更大的交叉幾率。在進(jìn)化后半段，交叉概率隨交叉效果的下降而下降，此時(shí)應(yīng)該保存更多較優(yōu)個(gè)體。

綜合上述分析，本文使用種群活力改進(jìn)上述方法，提出一種新的自適應(yīng)變化規(guī)則：

式(4)定義的是交叉概率變換準(zhǔn)則，在進(jìn)化初始階段，優(yōu)質(zhì)個(gè)體可以得到有效傳播，在進(jìn)化后半段，能實(shí)現(xiàn)對優(yōu)質(zhì)個(gè)體的保護(hù)。式(5)描述變異幾率自適應(yīng)變換準(zhǔn)則，取值大小與種群活力程度相關(guān)。當(dāng)種群活力程度較低時(shí)，變異幾率取值應(yīng)較大，以此控制種群變壞。

(5)

式中，pc1、pc2、pc3、pm1、pm2分別表示原始設(shè)置的交叉變異機(jī)率；θ(t)代表第t代種群活力程度指標(biāo)，kc1與kc2均屬于交叉調(diào)節(jié)系數(shù)，取值范圍分別是[1，5]與[5，10]。km使變異調(diào)節(jié)系數(shù)，取值為[1，5]，γ的取值在[0.1，0.5]之間，σ∈[1，10]。

3.1.4 并行變異處理

經(jīng)過上述變異概率自適應(yīng)調(diào)整后在規(guī)定取值范圍內(nèi)形成一個(gè)隨機(jī)數(shù)，以此替換初始數(shù)據(jù)。但此數(shù)據(jù)存在一定隨機(jī)性，得到的結(jié)果對收斂精度改善并不顯著，無法有效提高局部尋優(yōu)能力。因此提出并行機(jī)理對變異操作進(jìn)一步優(yōu)化。

假設(shè)將對第t代任意個(gè)體x進(jìn)行變異處理，則

x1=r(xmax-xmin)+xmin

(6)

(7)

如果連續(xù)多代個(gè)體平均適應(yīng)度差值低于設(shè)定的閾值時(shí)，則認(rèn)為此種群已經(jīng)沒有繼續(xù)計(jì)劃的趨勢，可終止算法，并選擇適應(yīng)度最大的個(gè)體做并行解碼操作[9]，此時(shí)即可獲得軟件安全性要求的最佳屬性結(jié)合，可將其當(dāng)作下一步測試模型的輸入。

3.2 軟件安全性測試模型構(gòu)建

在利用改進(jìn)的遺傳方法進(jìn)行軟件安全性度量性選擇后，構(gòu)建安全測試模型。

當(dāng)網(wǎng)絡(luò)環(huán)境為開放性時(shí)，利用一個(gè)四叉樹模型代表軟件的分布特性，通過三元組SC=(Ex′，En′，He′)代表軟件屬性數(shù)值特性。設(shè)定集合O為在n′維論域μ中的軟件指標(biāo)參量，因此O的四叉樹可表示為

(8)

(9)

(10)

(11)

式中a為常數(shù)。

經(jīng)過以上設(shè)計(jì)，完成軟件安全測試模型的構(gòu)建，利用該模型能夠測試出軟件安全狀況。

4 實(shí)驗(yàn)結(jié)果與分析

為證明本文提出的軟件安全性測試方法性能，從三個(gè)不同軟件中挑選1000個(gè)樣本當(dāng)作仿真目標(biāo)，其中可疑樣本數(shù)量為300，訓(xùn)練數(shù)量為700，本文確定的安全性度量屬性如表2所示。

表2 安全性度量屬性表

利用改進(jìn)的遺傳方法獲得種群多樣性與鄰近代迭代種群多樣性變換曲線分別如圖2與圖3所示。

圖2 種群多樣性

圖3 鄰近代種群間相似度

從圖2與圖3中可以看出，隨著迭代次數(shù)的不斷增加，種群多樣性趨勢下降，但是相鄰迭代種群之間相似度不斷提升，證明本文方法選取的安全性度量屬性較為合理。

將交叉與遺傳概率分別設(shè)置為0.8與0.3，初始迭代次數(shù)為60，最大迭代次數(shù)為600，在此環(huán)境下，利用本文方法、文獻(xiàn)[1]方法、文獻(xiàn)[2]方法測試軟件可疑點(diǎn)數(shù)量，并對測試錯(cuò)誤率進(jìn)行對比。

由表3可知，在相同網(wǎng)絡(luò)環(huán)境下，所提方法可發(fā)現(xiàn)更多軟件存在的可疑點(diǎn)。這是因?yàn)樗岱椒ㄈ娣治鲕浖惓Ｌ卣鳎虼嗽跍y試過程中綜合考慮各種異常狀況，提高脆弱點(diǎn)發(fā)現(xiàn)幾率。

表3 不同方法可疑點(diǎn)測試結(jié)果對比表

圖4 不同方法軟件可疑點(diǎn)測試錯(cuò)誤率

從圖4可以看出，在所有可疑點(diǎn)測試結(jié)果中，本文方法測試的錯(cuò)誤率最低。這是因?yàn)樗岱椒ㄔ谶z傳算法中引入并行機(jī)理，獲取安全性要求的最佳屬性結(jié)合，提高了算法變異能力，避免陷入局部最優(yōu)，大幅度提升了測試的精準(zhǔn)度。

5 結(jié)論

本文改進(jìn)遺傳算法，利用并行變異處理，提高局部尋優(yōu)能力，更全面發(fā)現(xiàn)軟件可疑點(diǎn)，提高測試精度，將軟件安全問題造成的損失降到最低。