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

【摘要】：隨著信息化時代的來臨,軟件已經(jīng)被應用到人們生活的各個不同方面,不斷改變著人們的交流和生活方式。而在這個過程中,軟件系統(tǒng)的結構也越來越復雜化,多樣化。隨之帶來的軟件安全性問題也越來越受到研究者們的重視。研究者們從多個角度多個層次對復雜軟件系統(tǒng)的安全性進行度量研究,例如從軟件的拓撲結構方面進行分析研究。如何將復雜軟件系統(tǒng)的拓撲結構抽象為軟件執(zhí)行網(wǎng)絡模型,如何更加快速地發(fā)現(xiàn)對軟件執(zhí)行過程影響較大的關鍵節(jié)點,如何更好地區(qū)分具有相似結構的關鍵節(jié)點,如何快速地發(fā)現(xiàn)軟件執(zhí)行關鍵路徑等問題也成為現(xiàn)今主要研究工作之一。為了解決上述提到的問題,本文對軟件網(wǎng)絡中關鍵節(jié)點和關鍵路徑挖掘進行了研究,并輔以一些開源的軟件作為實驗對象進行分析研究。首先,為了更好地度量軟件的拓撲結構,現(xiàn)將軟件系統(tǒng)的執(zhí)行轉換為軟件網(wǎng)絡。將軟件功能模塊定義為節(jié)點,模塊之間的調用依賴關系抽象為邊,并將它們之間的調用次數(shù)設為邊上的權值,以此來構建軟件有向加權網(wǎng)絡模型。使用GNU編譯工具和pvtrace追蹤工具來獲得軟件的執(zhí)行路徑情況,并將結果轉換成三列矩陣,對其進行節(jié)點度以及度分布等一系列的特性分析。其次,根據(jù)復雜網(wǎng)絡中相繼故障原理,網(wǎng)絡中節(jié)點的關鍵性程度決定其影響軟件正常運行的大小。本文在軟件有向加權網(wǎng)絡模型的基礎上,提出了一種基于相繼故障原理的關鍵節(jié)點挖掘算法。該算法深度遍歷軟件執(zhí)行網(wǎng)絡中的各個節(jié)點,通過計算故障節(jié)點的影響力度來衡量該節(jié)點的關鍵性,并對其進行等級劃分和排序操作。再次,使用上述關鍵節(jié)點度量挖掘方法時,可能會出現(xiàn)多個節(jié)點處于同一等級的情況。針對這一現(xiàn)象,本文提出了一種基于PageRank和介數(shù)度量方法的關鍵節(jié)點挖掘算法。該算法首先使用測試用例形成結果圖集合,然后利用頻繁子圖挖掘方法確定關鍵節(jié)點集合,最后為了獲得更準確地軟件執(zhí)行網(wǎng)絡中關鍵節(jié)點,將熵運用到PageRank和介數(shù)兩個方法度量中,并對節(jié)點進行排序。最后,為了挖掘軟件執(zhí)行過程中的關鍵路徑,本文提出了一種關鍵路徑挖掘算法。在這一過程中,按照軟件執(zhí)行網(wǎng)絡中邊出現(xiàn)情況生成對應的0/1邊序列,并將形成的邊序列存放到有向圖矩陣中。利用序列頻繁閥值和邊重復率大小,去除不符合規(guī)則的邊,從而獲得軟件執(zhí)行網(wǎng)絡的關鍵路徑。對于上述提到的算法,本文以多種開源軟件進行實驗分析,發(fā)現(xiàn)能夠這些研究方法能夠更有效地挖掘軟件中起到重要作用的關鍵節(jié)點和關鍵路徑。
[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.
【學位授予單位】：燕山大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：O157.5

【相似文獻】

相關期刊論文 前10條

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

2 劉彥;求關鍵路徑的一種方法[J];湘潭大學自然科學學報;1991年04期

3 朱嘉鋼;關鍵路徑概念的延伸[J];江南學院學報;1999年04期

4 李勇建,邵秀麗,涂凍生;串聯(lián)加工網(wǎng)絡關鍵路徑的計算與擾動分析[J];南開大學學報(自然科學版);2002年03期

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

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

7 涂凍生;離散事件動態(tài)系統(tǒng)的關鍵路徑與擾動分析[J];系統(tǒng)科學與數(shù)學;1996年04期

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

9 錢鑫;吳曉軍;張?zhí)鹛?易宇;;求解關鍵路徑的元胞自動機算法[J];陜西師范大學學報(自然科學版);2009年06期

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

相關會議論文 前2條

1 劉瑞華;涂凍生;;生產(chǎn)加工網(wǎng)絡的關鍵路徑與擾動分析[A];1993中國控制與決策學術年會論文集[C];1993年

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

相關重要報紙文章 前9條

1 唐曉玉/譯;關鍵路徑公司 虛增收入遭起訴[N];中國財經(jīng)報;2003年

2 記者 吳生鋒;明確關鍵路徑 推進跨越發(fā)展 加快轉型升級 實現(xiàn)二次騰飛[N];揚州日報;2012年

3 記者 李建永;把城鎮(zhèn)建設作為率先建設沿海強市的關鍵路徑[N];秦皇島日報;2007年

4 劉小群;系統(tǒng)設計師考試 《數(shù)據(jù)結構》試題分析[N];中國電腦教育報;2004年

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

6 巫長龍 胡建偉;深入推進“人才興市”戰(zhàn)略[N];鎮(zhèn)江日報;2014年

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

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

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

相關博士學位論文 前2條

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

2 孫劍;考慮時序關鍵路徑的布線后雙重圖案光刻層分配算法研究[D];復旦大學;2012年

相關碩士學位論文 前10條

1 高智麟;汽車排放系統(tǒng)開發(fā)項目的關鍵路徑和風險管理應用[D];上海交通大學;2014年

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

3 韓英杰;基于綜合調度關鍵路徑的多核任務調度研究[D];哈爾濱理工大學;2014年

4 周勇;基于動態(tài)關鍵路徑的復雜產(chǎn)品制造調度研究[D];哈爾濱理工大學;2009年

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

6 王凱;基于關鍵路徑的控制圖式的項目時間管理[D];上海交通大學;2011年

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

8 王丹;模糊網(wǎng)絡計劃技術研究[D];哈爾濱理工大學;2008年

9 歐陽永基;基于關鍵路徑覆蓋的二進制程序測試技術研究[D];解放軍信息工程大學;2011年

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

，

本文編號：1458939