[發(fā)明專利]一種基于網(wǎng)絡(luò)知識(shí)匯聚和迭代式搜索的程序自動(dòng)構(gòu)造方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011180161.5
• 申請(qǐng)日: 2020-10-29
• 公開（公告）號(hào): CN112162746B
• 公開（公告）日: 2022-07-05
• 發(fā)明（設(shè)計(jì)）人: 董威;劉加芯;章雅婷;王黛艷;陳立前;尹良澤;王戟
• 申請(qǐng)（專利權(quán)）人: 中國人民解放軍國防科技大學(xué)
• 主分類號(hào): G06F8/35
• 分類號(hào): G06F8/35;G06F8/41;G06F16/953;G06F16/36;G06K9/62
• 代理公司: 湖南兆弘專利事務(wù)所(普通合伙) 43008
• 代理人: 劉暢舟

本發(fā)明公開了一種基于網(wǎng)絡(luò)知識(shí)匯聚和迭代式搜索的程序自動(dòng)構(gòu)造方法，包括：從目標(biāo)網(wǎng)絡(luò)資源中挖掘API信息，對(duì)API分類并分別構(gòu)造方法排序器、return排序器以及核心API排序器；分別從構(gòu)造方法排序器、return排序器和核心API排序器中選取API構(gòu)建程序搜索空間，根據(jù)程序搜索空間中的API進(jìn)行程序合成，若在當(dāng)前程序搜索空間中找到了通過測(cè)試用例的候選程序，結(jié)束并退出，否則繼續(xù)從構(gòu)造方法排序器、return排序器和核心API排序器中選取API添加到程序搜索空間并根據(jù)程序搜索空間中的API進(jìn)行程序合成，直到生成了通過測(cè)試用例的候選程序。本發(fā)明可以對(duì)程序搜索空間進(jìn)行約束和縮小，以提高程序的合成效率。

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

本發(fā)明涉及軟件工程領(lǐng)域，尤其涉及一種基于網(wǎng)絡(luò)知識(shí)匯聚和迭代式搜索的程序自動(dòng)構(gòu)造方法。

背景技術(shù)

互聯(lián)網(wǎng)的快速發(fā)展使得人們對(duì)于軟件的需求越來越多也越來越高，軟件已經(jīng)成為人們生活中必不可少的工具，與此同時(shí)軟件的開發(fā)也面臨更嚴(yán)峻的挑戰(zhàn)。一方面，隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展和用戶需求的提高，軟件系統(tǒng)的規(guī)模和復(fù)雜性急劇增長(zhǎng)，如何提高軟件的開發(fā)效率和質(zhì)量是一個(gè)挑戰(zhàn)；另一方面，對(duì)于部分重復(fù)而枯燥的軟件開發(fā)活動(dòng)，如何能解放軟件開發(fā)人員編程的雙手，將重心放在更有挑戰(zhàn)性的任務(wù)上是另一個(gè)挑戰(zhàn)。為了將軟件開發(fā)人員從復(fù)雜繁重的開發(fā)工作中解放出來，提升軟件開發(fā)的效率與質(zhì)量，程序自動(dòng)合成將成為軟件工程的重點(diǎn)研究與投入方向之一。

程序合成(Program Synthesis)的任務(wù)是從底層的程序設(shè)計(jì)語言中自動(dòng)發(fā)現(xiàn)滿足以某種形式的約束表示的用戶意圖的程序。它旨在讓高級(jí)編程人員能夠在更高的抽象層次上進(jìn)行程序的設(shè)計(jì)工作，同時(shí)也能輔助初級(jí)開發(fā)人員進(jìn)行編程，從而提高程序開發(fā)的效率。但是程序合成存在兩個(gè)固有的挑戰(zhàn)：用戶意圖的不確定性、程序空間的難處理性。為了準(zhǔn)確的表達(dá)用戶意圖，可以方法采取形式化規(guī)范、自然語言、輸入輸出示例等作為用戶意圖對(duì)其進(jìn)行表示。但是對(duì)于程序空間這一問題，許多方法提出通過設(shè)計(jì)領(lǐng)域特定語言來實(shí)現(xiàn)對(duì)空間的約束，進(jìn)而保證程序的合成。雖然這些方法在字符串處理、數(shù)據(jù)操作、幾何構(gòu)造等特定領(lǐng)域是有效的，但是對(duì)于通用編程語言(例如，Java)的程序合成仍然是一個(gè)挑戰(zhàn)。

隨著可重用應(yīng)用程序編程接口(Application Programming Interfaces,APIs)和組件的蓬勃發(fā)展，基于組件(例如，APIs)的程序合成為生成通用語言的程序提供了一種可行的方案。而且在軟件開發(fā)活動(dòng)中，程序員經(jīng)常通過查閱相關(guān)軟件庫的標(biāo)準(zhǔn)文檔來識(shí)別有用的函數(shù)，并將這些函數(shù)與循環(huán)和條件結(jié)合起來以實(shí)現(xiàn)某些需要的功能。但是，使用大型的軟件庫不是一件容易的事，經(jīng)驗(yàn)豐富的程序員甚至都要花幾個(gè)小時(shí)從庫中確定一些必要的功能。為了簡(jiǎn)化類似的編程活動(dòng)，基于組件的(Component-based program synthesis)程序合成被給予了較多的關(guān)注和研究，它旨在通過使用組件庫中現(xiàn)有的函數(shù)進(jìn)行排列組合來自動(dòng)合成程序。SyPet是一個(gè)先進(jìn)的基于組件的程序合成工具，它利用Petri網(wǎng)來對(duì)庫中組件(APIs)及組件之間的關(guān)系進(jìn)行建模，通過遍歷Petri網(wǎng)的可達(dá)性圖來找到滿足用戶聲明的方法序列，通過使用SAT求解器檢查(type-check)變量和參數(shù)類型對(duì)序列進(jìn)行填充從而得到一系列候選程序，最終執(zhí)行測(cè)試用例對(duì)候選程序進(jìn)行驗(yàn)證直到找到滿足需求的解。盡管合成通用編程語言的程序這一需求得到了滿足，但是由于組件庫中組件數(shù)量的龐大，所構(gòu)造的程序合成空間也隨之很大，將導(dǎo)致搜索解的過程非常耗時(shí)，產(chǎn)生了很大的時(shí)間開銷。其次，由于程序空間隨著目標(biāo)程序規(guī)模的擴(kuò)大呈現(xiàn)指數(shù)數(shù)量級(jí)增長(zhǎng)，實(shí)際上只能小規(guī)模的程序。因此，為了使合成程序的速度更快、規(guī)模更大，如何能夠縮小程序合成的空間是一個(gè)亟待解決的問題。