[發(fā)明專利]基于文件的Linux基礎(chǔ)軟件依賴關(guān)系分析方法

有效

• 申請?zhí)枺?/td>: 201410291217.2
• 申請日: 2014-06-25
• 公開（公告）號: CN104063220B
• 公開（公告）日: 2017-04-12
• 發(fā)明（設(shè)計(jì)）人: 陶品;馮立新
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: G06F9/44
• 分類號: G06F9/44;G06F17/30
• 代理公司: 北京華睿卓成知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)11436
• 代理人: 張麗新,彭武

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

本發(fā)明總體地涉及Linux系統(tǒng)，更具體地涉及Linux基礎(chǔ)軟件依賴關(guān)系分析方法。

背景技術(shù)

一個典型的Linux系統(tǒng)中包含數(shù)以千計(jì)的軟件包，數(shù)以萬計(jì)的可執(zhí)行文件，如果每個軟件的功能實(shí)現(xiàn)都從Linux最底層的系統(tǒng)調(diào)用開始構(gòu)建，軟件的設(shè)計(jì)會異常復(fù)雜、工作量很大，因此實(shí)際的Linux軟件系統(tǒng)中都包含各種面向不同目標(biāo)的軟件庫。Linux系統(tǒng)中這些軟件包的二進(jìn)制可執(zhí)行文件與庫文件之間存在互相依賴關(guān)系，不同的軟件由不同的開發(fā)者或開發(fā)團(tuán)隊(duì)進(jìn)行開發(fā)，為了使得軟件開發(fā)更加高效，軟件的開發(fā)者會根據(jù)自己的知識和軟件開發(fā)效率的考慮，使得一些軟件的功能可以通過調(diào)用其他軟件庫的API調(diào)用來實(shí)現(xiàn)，從而讓整個Linux系統(tǒng)的軟件呈現(xiàn)出一種復(fù)雜的積木式結(jié)構(gòu)，即每個軟件功能都不是很大，但通過復(fù)雜的組合形成一個較為復(fù)雜、較為完備的應(yīng)用系統(tǒng)。

傳統(tǒng)的Linux系統(tǒng)采用包管理的方式來組織管理Linux系統(tǒng)中復(fù)雜的軟件結(jié)構(gòu)，每個軟件包中都包含一個描述文件來表述該軟件包依賴哪些其他軟件包，比如RPM包管理系統(tǒng)等，這樣的設(shè)計(jì)使得Linux系統(tǒng)的使用和管理較為方便。不過包管理系統(tǒng)中的軟件包依賴關(guān)系描述文件是由富有經(jīng)驗(yàn)的Linux系統(tǒng)開發(fā)人員手工指定的，不能自動化的生成軟件的依賴關(guān)系圖，也不能用于Linux系統(tǒng)開發(fā)的結(jié)構(gòu)分析和Linux系統(tǒng)的安全性分析。。

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

鑒于現(xiàn)有技術(shù)的以上情況，提出了本發(fā)明。

根據(jù)本發(fā)明的一個方面，提出了一種用于分析Linux基礎(chǔ)軟件之間的依賴關(guān)系的Linux基礎(chǔ)軟件依賴關(guān)系分析方法，可以包括：

步驟1：掃描一個Linux系統(tǒng)，得到所有二進(jìn)制可執(zhí)行文件和庫文件的列表；

步驟2：獲得該列表中的文件之間的依賴關(guān)系；

步驟3：消除二進(jìn)制文件的循環(huán)依賴關(guān)系，構(gòu)建集合{X}，其中集合{X}由彼此之間不存在循環(huán)依賴關(guān)系的元素組成，元素X為由處于一個循環(huán)依賴鏈上的所有文件構(gòu)成的集合或者由不存在于任何一個循環(huán)依賴鏈中的單個文件構(gòu)成的集合；

步驟4：對集合{X}中的每個元素，依據(jù)步驟2獲得的文件之間的依賴關(guān)系，建立元素之間的依賴關(guān)系，如果一個元素中存在多個文件與另一個元素中的多個文件存在依賴關(guān)系，兩個元素之間只記為一個依賴關(guān)系，集合{X}中各元素的依賴關(guān)系是一個內(nèi)部不存在循環(huán)依賴的樹狀依賴關(guān)系圖。

利用本發(fā)明實(shí)施例的Linux基礎(chǔ)軟件依賴關(guān)系分析方法，可以在無需軟件包描述信息的情況下，直接獲得Linux系統(tǒng)中內(nèi)核之上的所有軟件的二進(jìn)制可執(zhí)行文件和庫文件之間的依賴關(guān)系。

根據(jù)本發(fā)明的另一方面，提供了一種用于分析Linux基礎(chǔ)軟件之間的依賴關(guān)系的Linux基礎(chǔ)軟件依賴關(guān)系分析方法，可以包括：

步驟1：掃描一個Linux系統(tǒng)中，得到所有二進(jìn)制可執(zhí)行文件和庫文件的列表；

步驟2：逐個分析每個二進(jìn)制可執(zhí)行文件和庫文件的函數(shù)調(diào)用關(guān)系，獲得該文件所依賴的其他二進(jìn)制可執(zhí)行文件和庫文件的集合；

步驟3：對上述集合中的每個被依賴的二進(jìn)制文件，建立一個從被分析的二進(jìn)制文件到集合中被依賴的該二進(jìn)制文件的有向依賴連接；

步驟4：檢查Linux系統(tǒng)中的所有二進(jìn)制文件是否都被分析過，如果還有沒有被分析的二進(jìn)制文件，回到步驟2；否則進(jìn)入步驟5；

步驟5：查找系統(tǒng)二進(jìn)制文件的循環(huán)依賴關(guān)系，對于找到的每個循環(huán)依賴關(guān)系，處于循環(huán)依賴鏈上的所有文件構(gòu)成一個集合，記為集合Xi，i＝0...M-1，M表示整個系統(tǒng)中沒有重疊的循環(huán)依賴鏈個數(shù)；其他不存在于任何一個循環(huán)依賴鏈中的文件被記為只有一個元素的集合Xj，j＝M...M+N-1，N表示系統(tǒng)中不在任何一個循環(huán)依賴鏈中的文件個數(shù)；由所有的Xi和Xj構(gòu)成一個新的集合{X}，該集合的大小為N+M；

步驟6：對集合{X}中的每個元素，依據(jù)步驟2到步驟4獲得的文件之間的依賴關(guān)系，建立元素之間的依賴關(guān)系，如果一個元素中存在多個文件與另一個元素中的多個文件存在依賴關(guān)系，兩個元素之間只記為一個依賴關(guān)系，集合{X}中各元素的依賴關(guān)系是一個內(nèi)部不存在循環(huán)依賴的樹狀依賴關(guān)系圖；

步驟7：初始化集合{X}中每個元素對應(yīng)的計(jì)數(shù)器A和計(jì)數(shù)器B值均為0。計(jì)數(shù)器A的值表示該二進(jìn)制文件被其他文件依賴的次數(shù)，計(jì)數(shù)器B的值表示該二進(jìn)制文件一共依賴多少個其他二進(jìn)制文件；

步驟8：逐個處理集合{X}中的每個元素，如果該元素依賴其他某個元素，則被依賴的元素(即所述的其他某個元素)所對應(yīng)的計(jì)數(shù)器A執(zhí)行加一操作，該元素對應(yīng)的計(jì)數(shù)器B值等于該元素依賴的其他元素的總個數(shù)；