本文關(guān)鍵詞： 復(fù)雜網(wǎng)絡(luò) 軟件執(zhí)行網(wǎng)絡(luò) 關(guān)鍵節(jié)點(diǎn) 關(guān)鍵路徑 圖序列　出處：《燕山大學(xué)》2016年博士論文　論文類型：學(xué)位論文

【摘要】：隨著信息化時(shí)代的來(lái)臨,軟件已經(jīng)被應(yīng)用到人們生活的各個(gè)不同方面,不斷改變著人們的交流和生活方式。而在這個(gè)過(guò)程中,軟件系統(tǒng)的結(jié)構(gòu)也越來(lái)越復(fù)雜化,多樣化。隨之帶來(lái)的軟件安全性問(wèn)題也越來(lái)越受到研究者們的重視。研究者們從多個(gè)角度多個(gè)層次對(duì)復(fù)雜軟件系統(tǒng)的安全性進(jìn)行度量研究,例如從軟件的拓?fù)浣Y(jié)構(gòu)方面進(jìn)行分析研究。如何將復(fù)雜軟件系統(tǒng)的拓?fù)浣Y(jié)構(gòu)抽象為軟件執(zhí)行網(wǎng)絡(luò)模型,如何更加快速地發(fā)現(xiàn)對(duì)軟件執(zhí)行過(guò)程影響較大的關(guān)鍵節(jié)點(diǎn),如何更好地區(qū)分具有相似結(jié)構(gòu)的關(guān)鍵節(jié)點(diǎn),如何快速地發(fā)現(xiàn)軟件執(zhí)行關(guān)鍵路徑等問(wèn)題也成為現(xiàn)今主要研究工作之一。為了解決上述提到的問(wèn)題,本文對(duì)軟件網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)和關(guān)鍵路徑挖掘進(jìn)行了研究,并輔以一些開(kāi)源的軟件作為實(shí)驗(yàn)對(duì)象進(jìn)行分析研究。首先,為了更好地度量軟件的拓?fù)浣Y(jié)構(gòu),現(xiàn)將軟件系統(tǒng)的執(zhí)行轉(zhuǎn)換為軟件網(wǎng)絡(luò)。將軟件功能模塊定義為節(jié)點(diǎn),模塊之間的調(diào)用依賴關(guān)系抽象為邊,并將它們之間的調(diào)用次數(shù)設(shè)為邊上的權(quán)值,以此來(lái)構(gòu)建軟件有向加權(quán)網(wǎng)絡(luò)模型。使用GNU編譯工具和pvtrace追蹤工具來(lái)獲得軟件的執(zhí)行路徑情況,并將結(jié)果轉(zhuǎn)換成三列矩陣,對(duì)其進(jìn)行節(jié)點(diǎn)度以及度分布等一系列的特性分析。其次,根據(jù)復(fù)雜網(wǎng)絡(luò)中相繼故障原理,網(wǎng)絡(luò)中節(jié)點(diǎn)的關(guān)鍵性程度決定其影響軟件正常運(yùn)行的大小。本文在軟件有向加權(quán)網(wǎng)絡(luò)模型的基礎(chǔ)上,提出了一種基于相繼故障原理的關(guān)鍵節(jié)點(diǎn)挖掘算法。該算法深度遍歷軟件執(zhí)行網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn),通過(guò)計(jì)算故障節(jié)點(diǎn)的影響力度來(lái)衡量該節(jié)點(diǎn)的關(guān)鍵性,并對(duì)其進(jìn)行等級(jí)劃分和排序操作。再次,使用上述關(guān)鍵節(jié)點(diǎn)度量挖掘方法時(shí),可能會(huì)出現(xiàn)多個(gè)節(jié)點(diǎn)處于同一等級(jí)的情況。針對(duì)這一現(xiàn)象,本文提出了一種基于PageRank和介數(shù)度量方法的關(guān)鍵節(jié)點(diǎn)挖掘算法。該算法首先使用測(cè)試用例形成結(jié)果圖集合,然后利用頻繁子圖挖掘方法確定關(guān)鍵節(jié)點(diǎn)集合,最后為了獲得更準(zhǔn)確地軟件執(zhí)行網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn),將熵運(yùn)用到PageRank和介數(shù)兩個(gè)方法度量中,并對(duì)節(jié)點(diǎn)進(jìn)行排序。最后,為了挖掘軟件執(zhí)行過(guò)程中的關(guān)鍵路徑,本文提出了一種關(guān)鍵路徑挖掘算法。在這一過(guò)程中,按照軟件執(zhí)行網(wǎng)絡(luò)中邊出現(xiàn)情況生成對(duì)應(yīng)的0/1邊序列,并將形成的邊序列存放到有向圖矩陣中。利用序列頻繁閥值和邊重復(fù)率大小,去除不符合規(guī)則的邊,從而獲得軟件執(zhí)行網(wǎng)絡(luò)的關(guān)鍵路徑。對(duì)于上述提到的算法,本文以多種開(kāi)源軟件進(jìn)行實(shí)驗(yàn)分析,發(fā)現(xiàn)能夠這些研究方法能夠更有效地挖掘軟件中起到重要作用的關(guān)鍵節(jié)點(diǎn)和關(guān)鍵路徑。
[Abstract]:With the advent of the information age, software has been applied to different aspects of people's lives, constantly changing people's communication and lifestyle. In this process, the structure of software systems is becoming more and more complex. The problem of software security has been paid more and more attention to by researchers, who measure the security of complex software systems from many angles and levels. For example, from the aspect of software topology analysis, how to abstract the topological structure of complex software system into software execution network model. How to find the key nodes which have a great influence on the software execution process more quickly, and how to better distinguish the key nodes with similar structure. How to quickly discover the critical path of software execution has become one of the main research work. In order to solve the above mentioned problems, this paper studies the key nodes and critical path mining in the software network. And with some open source software as experimental object to analyze and study. First, in order to better measure the software topology. Now the execution of the software system is transformed into the software network. The software function module is defined as the node, the call dependency between the modules is abstracted as the edge, and the number of calls between them is set to the weight of the edge. In this way, the software directed weighted network model is constructed, and the execution path of the software is obtained by using the GNU compiler tool and the pvtrace tracing tool, and the result is converted into a three-column matrix. A series of characteristics such as node degree and degree distribution are analyzed. Secondly, according to the principle of sequential fault in complex network. The critical degree of nodes in the network determines the size of the normal operation of the software. This paper is based on the software directed weighted network model. A key node mining algorithm based on sequential fault principle is proposed, which deeply traverses every node in the software execution network, and measures the key of the node by calculating the influence of the fault node. Thirdly, when we use the above key node metric mining method, there may be more than one node in the same level. In this paper, a key node mining algorithm based on PageRank and medium metric is proposed, which uses test cases to form the result graph set. Then we use frequent subgraph mining method to determine the set of key nodes. Finally, in order to obtain more accurate software execution network key nodes, entropy is applied to the measurement of PageRank and medium. Finally, in order to mine the critical path in the process of software execution, this paper proposes a key path mining algorithm. The corresponding 0/1 edge sequences are generated according to the occurrence of the edges in the software execution network, and the resulting edge sequences are stored in the directed graph matrix. The irregular edges are removed by using the sequence frequent threshold values and the size of the edge repetition rate. In order to obtain the critical path of software execution network. For the above mentioned algorithms, this paper uses a variety of open source software for experimental analysis. The key nodes and critical paths which play an important role in the software can be more effectively mined by these research methods.
【學(xué)位授予單位】：燕山大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 徐心和;關(guān)鍵路徑的極大代數(shù)解法[J];系統(tǒng)工程理論與實(shí)踐;1989年05期

2 劉彥;求關(guān)鍵路徑的一種方法[J];湘潭大學(xué)自然科學(xué)學(xué)報(bào);1991年04期

3 朱嘉鋼;關(guān)鍵路徑概念的延伸[J];江南學(xué)院學(xué)報(bào);1999年04期

4 李勇建,邵秀麗,涂?jī)錾?串聯(lián)加工網(wǎng)絡(luò)關(guān)鍵路徑的計(jì)算與擾動(dòng)分析[J];南開(kāi)大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年03期

5 趙云;石俊;;關(guān)鍵路徑在現(xiàn)代工程中的應(yīng)用[J];科技信息;2008年36期

6 肖渡;胡漢輝;;擬關(guān)鍵路徑及其在網(wǎng)絡(luò)計(jì)劃優(yōu)化中的應(yīng)用[J];決策借鑒;1992年03期

7 涂?jī)錾?離散事件動(dòng)態(tài)系統(tǒng)的關(guān)鍵路徑與擾動(dòng)分析[J];系統(tǒng)科學(xué)與數(shù)學(xué);1996年04期

8 白云洪;周冬明;趙東風(fēng);杜華;;基于改進(jìn)型脈沖耦合神經(jīng)網(wǎng)絡(luò)的關(guān)鍵路徑求解[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年03期

9 錢鑫;吳曉軍;張?zhí)鹛?易宇;;求解關(guān)鍵路徑的元胞自動(dòng)機(jī)算法[J];陜西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年06期

10 胡美群;夏銀水;王倫耀;;基于分支限界的關(guān)鍵路徑求解算法[J];寧波大學(xué)學(xué)報(bào)(理工版);2011年02期

相關(guān)會(huì)議論文 前2條

1 劉瑞華;涂?jī)錾?;生產(chǎn)加工網(wǎng)絡(luò)的關(guān)鍵路徑與擾動(dòng)分析[A];1993中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];1993年

2 李勇建;涂奉生;;具有偏序結(jié)構(gòu)的一般網(wǎng)絡(luò)系統(tǒng)的關(guān)鍵路徑與擾動(dòng)分析問(wèn)題[A];第十九屆中國(guó)控制會(huì)議論文集（一）[C];2000年

相關(guān)重要報(bào)紙文章 前9條

1 唐曉玉/譯;關(guān)鍵路徑公司 虛增收入遭起訴[N];中國(guó)財(cái)經(jīng)報(bào);2003年

2 記者 吳生鋒;明確關(guān)鍵路徑 推進(jìn)跨越發(fā)展 加快轉(zhuǎn)型升級(jí) 實(shí)現(xiàn)二次騰飛[N];揚(yáng)州日?qǐng)?bào);2012年

3 記者 李建永;把城鎮(zhèn)建設(shè)作為率先建設(shè)沿海強(qiáng)市的關(guān)鍵路徑[N];秦皇島日?qǐng)?bào);2007年

4 劉小群;系統(tǒng)設(shè)計(jì)師考試 《數(shù)據(jù)結(jié)構(gòu)》試題分析[N];中國(guó)電腦教育報(bào);2004年

5 王文;血液安全：基于FDA關(guān)鍵路徑計(jì)劃的機(jī)遇和挑戰(zhàn)[N];中國(guó)醫(yī)藥報(bào);2008年

6 巫長(zhǎng)龍 胡建偉;深入推進(jìn)“人才興市”戰(zhàn)略[N];鎮(zhèn)江日?qǐng)?bào);2014年

7 ;明確“路標(biāo)” 強(qiáng)化執(zhí)行[N];人民郵電;2003年

8 本報(bào)記者 陳淑娟;裴兆旭:平衡“金三角”定律[N];計(jì)算機(jī)世界;2009年

9 ;明確“路標(biāo)”強(qiáng)化執(zhí)行[N];人民郵電;2003年

相關(guān)博士學(xué)位論文 前2條

1 王蕾;基于復(fù)雜網(wǎng)絡(luò)的軟件關(guān)鍵節(jié)點(diǎn)和關(guān)鍵路徑挖掘方法研究[D];燕山大學(xué);2016年

2 孫劍;考慮時(shí)序關(guān)鍵路徑的布線后雙重圖案光刻層分配算法研究[D];復(fù)旦大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 高智麟;汽車排放系統(tǒng)開(kāi)發(fā)項(xiàng)目的關(guān)鍵路徑和風(fēng)險(xiǎn)管理應(yīng)用[D];上海交通大學(xué);2014年

2 章興玲;柔性作業(yè)車間分批調(diào)度研究[D];合肥工業(yè)大學(xué);2015年

3 韓英杰;基于綜合調(diào)度關(guān)鍵路徑的多核任務(wù)調(diào)度研究[D];哈爾濱理工大學(xué);2014年

4 周勇;基于動(dòng)態(tài)關(guān)鍵路徑的復(fù)雜產(chǎn)品制造調(diào)度研究[D];哈爾濱理工大學(xué);2009年

5 王穎;嵌入關(guān)鍵路徑的掙值分析方法研究[D];天津理工大學(xué);2009年

6 王凱;基于關(guān)鍵路徑的控制圖式的項(xiàng)目時(shí)間管理[D];上海交通大學(xué);2011年

7 寧盼;短路關(guān)鍵面積提取與縮小方法研究[D];西安電子科技大學(xué);2013年

8 王丹;模糊網(wǎng)絡(luò)計(jì)劃技術(shù)研究[D];哈爾濱理工大學(xué);2008年

9 歐陽(yáng)永基;基于關(guān)鍵路徑覆蓋的二進(jìn)制程序測(cè)試技術(shù)研究[D];解放軍信息工程大學(xué);2011年

10 馬俊;基于Petri網(wǎng)的建筑工程項(xiàng)目時(shí)間—成本管理研究與優(yōu)化[D];廣西師范學(xué)院;2012年

，

本文編號(hào)：1458939