[發(fā)明專利]一種基于元胞自動(dòng)機(jī)的軟件故障傳播規(guī)律發(fā)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310706727.7
• 申請(qǐng)日: 2013-12-19
• 公開（公告）號(hào): CN104734870B
• 公開（公告）日: 2019-03-29
• 發(fā)明（設(shè)計(jì)）人: 張琨;王琦;陳旋;卞雪雯;劉藝
• 申請(qǐng)（專利權(quán)）人: 南京理工大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 南京理工大學(xué)專利中心 32203
• 代理人: 朱顯國

本發(fā)明公開了一種基于元胞自動(dòng)機(jī)的軟件故障傳播方法。首先，對(duì)元胞自動(dòng)機(jī)的空間和鄰居定義進(jìn)行擴(kuò)展，再建立元胞自動(dòng)機(jī)模型，引入傳播概率和節(jié)點(diǎn)容錯(cuò)率機(jī)制，對(duì)軟件網(wǎng)絡(luò)中的所有節(jié)點(diǎn)狀態(tài)進(jìn)行循環(huán)遍歷更新，直到滿足條件退出循環(huán)。采用此方法，能夠很好的模擬軟件故障傳播的過程，從而掌握軟件故障傳播規(guī)律，更好的控制軟件故障傳播造成的危害。

技術(shù)領(lǐng)域

本發(fā)明屬于復(fù)雜網(wǎng)絡(luò)中的故障傳播規(guī)律發(fā)現(xiàn)技術(shù)，特別是一種基于元胞自動(dòng)機(jī)的軟件故障傳播規(guī)律發(fā)現(xiàn)方法。

背景技術(shù)

隨著人類活動(dòng)的加深加劇，軟件在社會(huì)的各個(gè)領(lǐng)域中發(fā)揮著重要的作用。人類對(duì)軟件的需求的增加，軟件的規(guī)模也越來越大，軟件中的節(jié)點(diǎn)，如服務(wù)、構(gòu)件、包、類、方法等，之間的交互也越來越緊密，直接導(dǎo)致軟件越來越復(fù)雜。而在軟件運(yùn)行過程中，軟件代碼的缺陷、軟件運(yùn)行環(huán)境的不確定等因素都會(huì)產(chǎn)生軟件故障。由于軟件故障的產(chǎn)生與呈現(xiàn)并不存在一致的對(duì)應(yīng)關(guān)系，這造成了軟件故障在傳播過程中的不確定性。在當(dāng)今社會(huì)，隨著計(jì)算機(jī)化的日趨加重，一旦軟件系統(tǒng)發(fā)生了嚴(yán)重故障，很有可能對(duì)人類生命和財(cái)產(chǎn)造成無法估量的損失。因此，研究軟件故障的傳播動(dòng)力學(xué)行為，掌握其傳播規(guī)律，并提出相應(yīng)有效措施，有效的降低軟件故障所造成的危害，這對(duì)人類的發(fā)展和社會(huì)的進(jìn)步都有著重大的意義。

目前國內(nèi)外對(duì)復(fù)雜網(wǎng)絡(luò)的故障傳播研究主要集中在對(duì)電力系統(tǒng)和通信系統(tǒng)的故障傳播規(guī)律上，分析復(fù)雜系統(tǒng)的傳播動(dòng)力學(xué)，研究成果已經(jīng)比較完善。軟件系統(tǒng)的研究方法，大部分都采取將軟件中的元素作為一個(gè)單位節(jié)點(diǎn)，節(jié)點(diǎn)之間的依賴關(guān)系作為邊，對(duì)軟件系統(tǒng)結(jié)構(gòu)進(jìn)行網(wǎng)絡(luò)拓?fù)浠４罅垦芯勘砻鳎浖W(wǎng)絡(luò)同樣符合復(fù)雜網(wǎng)絡(luò)中的“無標(biāo)度”網(wǎng)絡(luò)特性，同時(shí)還具有高度的復(fù)雜性、不確定性、傳播性、并發(fā)性等特征，所以可以運(yùn)用復(fù)雜網(wǎng)絡(luò)的傳播動(dòng)力學(xué)理論，通過計(jì)算機(jī)的仿真，對(duì)軟件故障的傳播進(jìn)行研究分析，建立軟件故障傳播模型，將復(fù)雜網(wǎng)絡(luò)與軟件工程相關(guān)研究領(lǐng)域結(jié)合。

元胞自動(dòng)機(jī)(Cellular Automata，簡稱CA)，也有人譯為細(xì)胞自動(dòng)機(jī)、分子自動(dòng)機(jī)、點(diǎn)格自動(dòng)機(jī)等，是復(fù)雜性科學(xué)的核心技術(shù)之一。元胞自動(dòng)機(jī)是一個(gè)模型框架，或者說是模型集，他提供模擬復(fù)雜系統(tǒng)的基本模型，不同的模型可以通過不同的模擬參數(shù)模擬不同的復(fù)雜系統(tǒng)。通常來說，就是在離散的時(shí)間、空間上，由具有離散狀態(tài)的元胞(Cell)按照確定的局部演化規(guī)則做同步更新的動(dòng)態(tài)進(jìn)化系統(tǒng)。但是不同于一般的動(dòng)力學(xué)模型，元胞自動(dòng)機(jī)的構(gòu)建沒有嚴(yán)格定義的物理方程、數(shù)學(xué)公式，構(gòu)造方式多樣、自由，只是用一系列模型構(gòu)造的規(guī)則來構(gòu)建，所以凡是滿足這些規(guī)則的模型都可以算作是元胞自動(dòng)機(jī)模型。元胞自動(dòng)機(jī)在模擬復(fù)雜系統(tǒng)和同步并行過程及其在非線性科學(xué)方面的出色表現(xiàn)，使他也能夠很好的模擬由軟件內(nèi)部節(jié)點(diǎn)之間的相互作用引起的故障傳播動(dòng)態(tài)過程。同時(shí)，元胞自動(dòng)機(jī)的離散特性也有利于表達(dá)軟件運(yùn)行過程中各個(gè)節(jié)點(diǎn)(如類、方法)在每個(gè)時(shí)間點(diǎn)的運(yùn)行狀態(tài)。在軟件故障傳播過程中，由于軟件運(yùn)行環(huán)境的不穩(wěn)定和軟件具有的容錯(cuò)性，使得故障的發(fā)生與傳播都具有一定的不確定性和隨機(jī)性，元胞自動(dòng)機(jī)是一種完善的數(shù)學(xué)工具，可以有效的與模糊、概率相結(jié)合。

發(fā)明內(nèi)容

本發(fā)明的目的是提出一種基于元胞自動(dòng)機(jī)的軟件故障傳播規(guī)律發(fā)現(xiàn)方法，建立故障傳播模型，當(dāng)軟件被惡意攻擊時(shí)，得到軟件系統(tǒng)中故障的傳播動(dòng)力學(xué)特點(diǎn)，從而得出軟件故障傳播的規(guī)律，有效改進(jìn)軟件的設(shè)計(jì)和降低軟件故障所造成的危害。

由于元胞自動(dòng)機(jī)模型的運(yùn)用在多方面都有嚴(yán)格的限制，雖然能很好的對(duì)復(fù)雜現(xiàn)象進(jìn)行模擬，但是對(duì)不同的復(fù)雜系統(tǒng)，在內(nèi)部結(jié)構(gòu)不明確、演化機(jī)制不了解的情況，為了更好的對(duì)軟件復(fù)雜的系統(tǒng)進(jìn)行模擬，本發(fā)明對(duì)元胞自動(dòng)機(jī)的元胞空間和鄰居元胞定義進(jìn)行擴(kuò)展。

本發(fā)明所采用的方法如下。

(一)建立元胞自動(dòng)機(jī)，定義軟件網(wǎng)絡(luò)化得到的拓?fù)鋱D中的節(jié)點(diǎn)即為元胞，則CA模型通過一個(gè)四元組定義為CA＝(C，Q，V，f)，其中C表示元胞空間，此時(shí)擴(kuò)展為平面空間，元胞不再局限于空間的某一特定位置，而是散布在平面空間上；Q表示元胞狀態(tài)，一個(gè)離散的有限集和；V表示中心元胞的鄰居集合，此時(shí)不再局限為空間上相鄰的元胞，而是擴(kuò)展為有邊相連即為鄰居；f為狀態(tài)轉(zhuǎn)換規(guī)則；