[發(fā)明專利]一種多階段程序分析的并行任務(wù)分配方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 202011272405.2
• 申請(qǐng)日: 2020-11-13
• 公開（公告）號(hào): CN112269648A
• 公開（公告）日: 2021-01-26
• 發(fā)明（設(shè)計(jì)）人: 陳睿;江云松;肖志恒;王崢;賈春鵬;高棟棟;于婷婷;丁戈;朱玉釗
• 申請(qǐng)（專利權(quán)）人: 北京軒宇信息技術(shù)有限公司
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/50
• 代理公司: 中國(guó)航天科技專利中心 11009
• 代理人: 陳鵬

本發(fā)明公開了一種多階段程序分析的并行任務(wù)分配方法及裝置。所述方法包括：根據(jù)待分析代碼中所有任務(wù)之間的依賴關(guān)系，構(gòu)建所述待分析代碼對(duì)應(yīng)的任務(wù)關(guān)系圖；獲取所述待分析代碼中需要運(yùn)行的分析任務(wù)；根據(jù)所述任務(wù)關(guān)系圖和所述分析任務(wù)，對(duì)所述分析任務(wù)進(jìn)行階段劃分，得到階段任務(wù)集合；所述階段任務(wù)集合中包含至少一個(gè)可被并行執(zhí)行的并行任務(wù)；根據(jù)并發(fā)運(yùn)行任務(wù)數(shù)，運(yùn)行所述階段任務(wù)集合中的階段任務(wù)，并獲取任務(wù)運(yùn)行結(jié)果。本發(fā)明能夠較大程度的發(fā)揮硬件性能，縮短整體分析時(shí)間，且能夠有效解決將所有檢查器結(jié)果堆積到同一個(gè)結(jié)果文件中，檢查結(jié)果較多時(shí)，結(jié)果文件過大，不便于讀取的問題。

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

本發(fā)明涉及代碼分析技術(shù)領(lǐng)域，特別是一種多階段程序分析的并行任務(wù)分配方法及裝置。

背景技術(shù)

代碼分析是保證軟件代碼正確性的重要方法。對(duì)現(xiàn)代大規(guī)模的復(fù)雜的軟件系統(tǒng)(比如千萬行代碼規(guī)模的Linux操作系統(tǒng))進(jìn)行高精度的靜態(tài)分析,分析精度的提高，往往意味著更長(zhǎng)的分析時(shí)間。精度、效率和可擴(kuò)展性相互制約,是靜態(tài)分析技術(shù)在工業(yè)界應(yīng)用的主要障礙。

在提升分析效率方面，人們做了大量的優(yōu)化研究工作，比如單機(jī)

CPU并行、分布式以及GPU實(shí)現(xiàn)等。鑒于本發(fā)明應(yīng)用的系統(tǒng)為單機(jī)環(huán)境，主要針對(duì)單機(jī)CPU并行情況進(jìn)行了研究。目前已有的一些并行分析算法有Méndez-Lojo等人提出的一種基于約束圖改寫的并行指向分析算法，Rodriguez等人提出的一種基于參與者模型的并行數(shù)據(jù)流分析算法，這兩種算法是針對(duì)某一類特定的靜態(tài)分析問題進(jìn)行特定的處理，不具有普遍性。Albarghouthi等人提出了一個(gè)使用map-reduce策略并行化自頂向下分析的通用框架，這種框架比較依賴內(nèi)存，內(nèi)存不足時(shí)，計(jì)算會(huì)受限。

對(duì)于使用多種類型檢查器同時(shí)進(jìn)行分析的情況，有些檢查器可能會(huì)有些前置任務(wù)，比如全局變量分析的檢查器在分析前，需要先進(jìn)行程序構(gòu)建，再進(jìn)行函數(shù)調(diào)用關(guān)系計(jì)算，檢查器的分析有一些前置的依賴條件，需要分多個(gè)階段運(yùn)行。如果每一個(gè)檢查器都要等待其前置任務(wù)完成，且所有檢查器都要順序進(jìn)行，那么必然存在項(xiàng)目完整分析效率低的問題。

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

本發(fā)明解決的技術(shù)問題是：克服現(xiàn)有技術(shù)的不足，提供了一種多階段程序分析的并行任務(wù)分配方法及裝置。

為了解決上述技術(shù)問題，本發(fā)明實(shí)施例提供了一種多階段程序分析的并行任務(wù)分配方法，包括：

根據(jù)待分析代碼中所有任務(wù)之間的依賴關(guān)系，構(gòu)建所述待分析代碼對(duì)應(yīng)的任務(wù)關(guān)系圖；

獲取所述待分析代碼中需要運(yùn)行的分析任務(wù)；

根據(jù)所述任務(wù)關(guān)系圖和所述分析任務(wù)，對(duì)所述分析任務(wù)進(jìn)行階段劃分，得到階段任務(wù)集合；所述階段任務(wù)集合中包含至少一個(gè)可被并行執(zhí)行的并行任務(wù)；

根據(jù)并發(fā)運(yùn)行任務(wù)數(shù)，運(yùn)行所述階段任務(wù)集合中的階段任務(wù)，并獲取任務(wù)運(yùn)行結(jié)果。

可選地，所述根據(jù)待分析代碼中所有任務(wù)之間的依賴關(guān)系，構(gòu)建所述待分析代碼對(duì)應(yīng)的任務(wù)關(guān)系圖，包括：

以所述所有任務(wù)作為圖節(jié)點(diǎn)；

根據(jù)所述依賴關(guān)系將具有依賴關(guān)系的圖節(jié)點(diǎn)相連，生成所述任務(wù)關(guān)系圖。

可選地，所述根據(jù)所述任務(wù)關(guān)系圖和所述分析任務(wù)，對(duì)所述分析任務(wù)進(jìn)行階段劃分，得到階段任務(wù)集合，包括：

獲取所述分析任務(wù)在所述任務(wù)關(guān)系圖中的目標(biāo)圖節(jié)點(diǎn)；

獲取所述目標(biāo)圖節(jié)點(diǎn)中為父節(jié)點(diǎn)的第一圖節(jié)點(diǎn)，并將所述第一圖節(jié)點(diǎn)劃分至階段任務(wù)集合；

在所述目標(biāo)圖節(jié)點(diǎn)中刪除所述第一圖節(jié)點(diǎn)，并對(duì)剩余的目標(biāo)圖節(jié)點(diǎn)循環(huán)執(zhí)行所述獲取所述目標(biāo)圖節(jié)點(diǎn)中為父節(jié)點(diǎn)的第一圖節(jié)點(diǎn)，并將所述第一圖節(jié)點(diǎn)劃分至階段任務(wù)集合的步驟，直至所有的分析任務(wù)均已劃分至階段任務(wù)集合。