亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于代數(shù)的軟件路徑的自動生成

        2021-07-07 10:42:42李肇明
        信陽農(nóng)林學院學報 2021年2期
        關鍵詞:控制流表達式代數(shù)

        李肇明

        (安徽國際商務職業(yè)學院 信息工程學院,安徽 合肥 230000)

        軟件測試是軟件開發(fā)周期中的一個關鍵階段[1],在此階段可以發(fā)現(xiàn)潛在的軟件缺陷和故障,并確保這些問題能及時得到解決,從而提高軟件質量。白盒測試,又稱結構測試和邏輯驅動測試,是軟件測試中一種強大的技術,其目的是對要測試的軟件的內(nèi)部結構進行測試[2]。該方法在對軟件可靠性有較高要求的領域獲得廣泛運用,如軍事、金融和航空領域等。其中路徑測試是白盒測試中應用最為廣泛的方法之一。路徑測試的過程通常被分為代碼分析、控制流圖生成、路徑生成和測試用例四個部分[3]。因此,路徑測試的準確性與路徑生成密切相關。然而,隨著軟件規(guī)模的不斷增加,軟件系統(tǒng)中的循環(huán)結構出現(xiàn)次數(shù)也隨之增多,路徑成爆炸式增長,目前已有的軟件路徑生成方法代價大且困難。文獻[4-7]中對于軟件路徑的自動生成問題均提出了相關算法,但這些算法只生成了軟件的基本路徑集,并沒有生成軟件的完整路徑。文獻[8]提出了一種基于狀態(tài)圖自動生成軟件路徑的方法,并實現(xiàn)了對路徑的優(yōu)化,但該方法未對程序中循環(huán)結構的出現(xiàn)次數(shù)進行約束,致使該方法的工作量增加。

        本研究提出了一種基于代數(shù)的軟件路徑生成方法,該方法對源代碼進行分析,生成控制流圖;然后通過代數(shù)表示將控制流圖轉換為路徑表達式,并對路徑表達式中的循環(huán)進行展開,從而獲得軟件路徑。

        1 相關概念

        定義1 控制流圖(CFG)[9]:G=(N,E,b,f),N表示CFG中的節(jié)點集,每個節(jié)點n(n∈N)代表源程序的一個語句塊;E代表CFG中的有向邊集。每一條有向邊e(e∈E)對應源程序兩個節(jié)點之間的數(shù)據(jù)流向;b代表CFG中的入口節(jié)點;f代表CFG中的出口節(jié)點。CFG的入口和出口節(jié)點都只有一個。

        定義2 軟件路徑:軟件路徑(Path)是指在一個軟件的CFG中程序執(zhí)行控制流從b到f的一條路徑。其表示為邊的序列:P=ebe2…enef。其中eb表示入口節(jié)點b的出邊,ef表示出口節(jié)點f的入邊。

        CFG是一個程序的抽象表示,表示一個程序在執(zhí)行過程中可能會遍歷到的所有路徑。CFG一般通過圖的形式表示,但它也可以通過非圖示的形式表示,其中一種有效的方法是代數(shù)表示。在圖的代數(shù)表示中,首先給每一條邊唯一的標簽,使用小寫字母作為邊的標簽。'×'操作符表示串聯(lián)。當邊a連接邊c時,可被表示為ac,操作符'×'省略。'+'操作符表示選擇,當選擇邊a和邊c時,將其表示為a+c。當一系列的邊組成一條路徑時,把這條邊序列稱為路徑積。由路徑積和零或者更多的'+'操作符構成的表達式為路徑表達式。

        其中路徑積是沒有加法操作的路徑表達式的特殊情況。圖1是兩個控制流圖,圖1(a)有三條路徑:abdfi;abegi;achi;

        圖1(b)包含循環(huán)路徑,所以無法把它的全部執(zhí)行序列出來,下面是其中4條序列:abef;abcbef;abcbcbef;adf;

        在圖的代數(shù)表示中,如果一條邊、路徑積或路徑表達式被循環(huán)遍歷,可以通過指數(shù)表示循環(huán)次數(shù)。即a2=aa,a3=aaa,a*=aaa…a。

        與標準代數(shù)不同,路徑積不滿足交換律,即ab≠ba,這是由于它們具有先后連接的順序。但是它滿足結合律,即a(bc)=(ab)c=abc。圖1(a)中的所有路徑可以用abdfi+abegi+achi表示從,有'+'操作符連接的路徑都可以看作是獨立的軟件路徑。

        2 路徑生成

        提出一種基于代數(shù)的軟件路徑自動生成方法。其框架構圖如圖2所示。該方法可分為3個階段:第1階段,通過對軟件的源程序進行分析,構造控制流圖;第2階段,對控制流圖中的每一條邊進行標記,通過代數(shù)方法把控制流圖轉換

        為路徑表達式;第3階段,對路徑表達式中的循環(huán)展開,得到軟件路徑。

        3 構造控制流圖

        源程序生成控制流圖通常分為3個過程:詞法分析、語法分析和構造控制流圖。本研究使用Antlr工具實現(xiàn)詞法分析和語法分析。用戶所提交的語法文件通過Antlr自動生成相應的詞法分析器和語法分析器。在詞法分析過程中,源程序被分解為離散的字符組,也就是Tokens(標識符、關鍵字、操作符和符號等)。在語法分析過程中,語法分析其將通過詞法分析獲得的Tokens組織起來,并轉換為ATS(Abstract Syntax Tree, 抽象語法樹)。ATS上的每個節(jié)點都代表源代碼中的一種結構,通過對ATS遍歷以構造控制流圖。

        3.1 路徑表達式生成

        首先對邊標記,然后將源程序轉換為軟件路徑表達式。在控制流圖中,通過小寫字母依次對邊標記,如圖3所示。

        然后,使用代數(shù)方法將其轉換成路徑表達式,方法步驟如下:

        (1)合并所有連續(xù)邊,相乘邊的標簽。(2)合并所有平行的邊,用'+'操作符相加平行邊的標簽從而作為合并之后邊的標簽。(3)通過創(chuàng)建一個新“啞節(jié)點”引入一條含有指數(shù)操作符'*'邊的方法消除具有自循環(huán)的節(jié)點,隨后通過乘法來合并這三條邊。(4)選擇移除節(jié)點。(5)第一步到第四步被循環(huán)執(zhí)行直到圖中只有一條邊。

        圖3的轉換過程如圖4所示。

        3.2 循環(huán)展開

        路徑表達式中的每一條路徑積都應該在一個合適的循環(huán)下展開。如果循環(huán)次數(shù)過多,產(chǎn)生的路徑數(shù)量將急劇增加,將產(chǎn)生路徑爆炸問題。

        采用Z路徑覆蓋思想,只考慮循環(huán)0次和1次兩種情況。即針對代數(shù)表達式中的循環(huán)指數(shù),考慮操作符'*'為0和1兩種情況。圖4中路徑表達式abde*f(gde*f)*hi+ acde*f(gde*f)*hi展開為abdefgdefhi,abdefgdfhi,abdefhi,abdfgdefhi,abdfgdfhi,abdfhi,acdefgdefhi,acdefgdfhi,acdefhi,acdfgdefhi,acdfgdfhi,acdfhi。

        3.3 算法實現(xiàn)

        具體算法偽碼如表1所示。

        表1 算法偽碼

        ● 算法的輸入為CFG,輸出為軟件路徑;

        ● 算法第2~21行CFG約簡為路徑表達式;

        ● 算法第22~27行對路徑表達式中的循環(huán)做處理。

        表1續(xù)表

        4 案例研究

        為了驗證該方法的準確性,首先對兩個小規(guī)?;鶞食绦蜻M行路徑生成。程序規(guī)模較小,便于手工生成路徑,并與文中方法比較。為了驗證本方法的有效性,通過案例來說明。

        4.1 案例1

        三角形分類旨在確定3個輸入邊是否能形成一個三角形,及它們能形成什么類型的三角形;冒泡排序是一種排序算法,它將待排序的數(shù)據(jù)元素從大到小或從小到大排序。三角形分類控制流圖如圖5(a)所示,冒泡排序控制流圖如圖5(b)所示。

        通過本方法對三角形判別和冒泡排序進行路徑

        生成,結果如表2所示。

        表2 實驗結果

        圖5(a)中共有4條路徑,從表2可以看出該方法生成三角形分類的全部路徑。圖5(b)中存在兩個循環(huán),從表2中可以看出該方法生成的4條路徑對這兩個循環(huán)分別執(zhí)行0次和1次,實現(xiàn)對路徑的覆蓋。

        4.2 案例2

        選擇5個經(jīng)典案例進行實驗。在實驗環(huán)境不變的條件下對這5個經(jīng)典案例分別運行10次并計算出平均運行時間。由于從源程序轉換為控制流圖是通過工具輔助生成,其時間無法度量,所以該運行時間只包含將控制流圖轉換成軟件路徑所需時間,而且傳統(tǒng)方法求路徑集也需要人工生成控制流圖,時間也無法度量,因此不存在可比性。表3給出了案例的相關描述,該算法能有效生成5個案例的路徑。

        表3 5個經(jīng)典案例實驗結果

        圖6中,對算法進行比較,能夠看出,當代碼量迅速增大時,該算法生成軟件路徑所消耗的時間并未隨著快速增加,而是較為平緩增長。

        5 結語

        本研究提出一種基于代數(shù)的軟件路徑生成方法,該方法通過代數(shù)表示將控制流圖轉換為路徑表達式,并對循環(huán)展開0到1次以獲得軟件路徑。該方法最終有效地生成了軟件路徑。但是,該方法未考慮軟件中不可達路徑的問題,而且針對循環(huán)問題只考慮了0次和兩次循環(huán)這兩種情況。下一步工作將開展對不可達路徑檢測工作。

        猜你喜歡
        控制流表達式代數(shù)
        抵御控制流分析的Python 程序混淆算法
        兩個有趣的無窮長代數(shù)不等式鏈
        Hopf代數(shù)的二重Ore擴張
        工控系統(tǒng)中PLC安全漏洞及控制流完整性研究
        電子科技(2021年2期)2021-01-08 02:25:58
        抵御控制流分析的程序混淆算法
        什么是代數(shù)幾何
        科學(2020年1期)2020-08-24 08:08:06
        一個混合核Hilbert型積分不等式及其算子范數(shù)表達式
        表達式轉換及求值探析
        淺析C語言運算符及表達式的教學誤區(qū)
        一個非平凡的Calabi-Yau DG代數(shù)
        亚洲熟妇夜夜一区二区三区| 亚洲av无码一区二区二三区| 美腿丝袜在线一区二区| 尤物在线观看一区蜜桃| 极品尤物一区二区三区| 国产综合在线观看| 日韩制服国产精品一区| a级黑人大硬长爽猛出猛进| 日韩高清毛片| 白白色免费视频一区二区| 国产美女自拍国语对白| 日韩亚洲精选一区二区三区| 在线精品国产亚洲av麻豆| 欧美高清视频手机在在线| 正在播放强揉爆乳女教师| 九九久久精品无码专区| 最新亚洲av日韩av二区| 亚洲制服无码一区二区三区| 亚洲av永久无码精品成人| 成人综合激情自拍视频在线观看| 亚洲24小时免费视频| 国产毛片黄片一区二区三区| 亚洲乱码一区av春药高潮| 亚洲欧美日韩精品久久亚洲区| 四虎影视亚洲精品| 性无码国产一区在线观看| 人妖啪啪综合av一区| 老女老肥熟女一区二区| 99久久99久久久精品齐齐| 国产肥熟女视频一区二区三区| 高潮又爽又无遮挡又免费| 97精品伊人久久大香线蕉| 国产精品久久久一本精品| 国产一区二区三区尤物| 日本在线无乱码中文字幕| 无码无套少妇毛多18p| 大地资源在线播放观看mv| 无码中文字幕av免费放| 日日高潮夜夜爽高清视频| 亚州终合人妖一区二区三区| 欧美xxxxx高潮喷水麻豆|