一種基于有限自動(dòng)機(jī)的程序分析技術(shù)研究

王超

摘? 要： 程序分析在軟件測(cè)試和軟件維護(hù)方面均有著重要作用。為實(shí)現(xiàn)軟件程序的自動(dòng)分析，基于有限自動(dòng)機(jī)理論，提出一種實(shí)現(xiàn)軟件靜態(tài)信息識(shí)別的程序分析技術(shù)，根據(jù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則對(duì)程序語(yǔ)句進(jìn)行了分類，針對(duì)每類語(yǔ)句設(shè)計(jì)了對(duì)應(yīng)的識(shí)別自動(dòng)機(jī)，在此基礎(chǔ)上設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)程序分析原型系統(tǒng)。系統(tǒng)應(yīng)用結(jié)果表明，利用這一技術(shù)可以有效的提取出程序的控制流和數(shù)據(jù)流信息，能夠?yàn)檐浖|(zhì)量的定量分析和軟件維護(hù)工作奠定良好基礎(chǔ)。

關(guān)鍵詞： 有限自動(dòng)機(jī); 程序分析; 信息識(shí)別; 軟件維護(hù)

中圖分類號(hào)：TP39? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1006-8228（2019）12-12-03

A technique of program analyzing based on the theory of finite automata

Wang Chao

（Dalian Naval Academy， Dalian， Liaoning 116018， China）

Abstract： Program analysis plays an important role in software testing and software maintenance. To realize the automatic analysis of the program， this paper presents a technique of information identification based on theory of finite automata. The program code is classified according to the grammar rules of the programming language， the finite automata is designed in allusion to the each kind of code， and then an archetypal of the program analysis is designed and realized. The application of the system indicates that the information of control-flow and data-flow can be analyzed effectively with this method， which will establish a favorable foundation for software quality analyzing and software maintenance.

Key words： finite automata; program analyzing; information identification; software maintenance

0 引言

軟件的靜態(tài)分析是軟件測(cè)試和軟件維護(hù)活動(dòng)中一個(gè)必不可少的環(huán)節(jié)[1-2]。通過(guò)對(duì)軟件實(shí)施靜態(tài)分析，軟件研發(fā)人員可以了解它的整個(gè)結(jié)構(gòu)及各部分之間的相互關(guān)系，了解其中所采用的數(shù)據(jù)結(jié)構(gòu)及變量的使用情況，有助于對(duì)軟件的缺陷跟蹤和軟件可維護(hù)性預(yù)測(cè)等工作的開展[3]。隨著軟件規(guī)模的不斷增長(zhǎng)，采用人工方式實(shí)現(xiàn)軟件理解工作已經(jīng)越來(lái)越困難。

有限自動(dòng)機(jī)作為一種自動(dòng)識(shí)別裝置，能夠按照程序語(yǔ)言的語(yǔ)法規(guī)則識(shí)別出各種程序單元和實(shí)體[4]，因此可以用作開發(fā)程序分析器的自動(dòng)構(gòu)造工具。本文在有限自動(dòng)機(jī)的理論基礎(chǔ)之上，提出一種實(shí)現(xiàn)軟件靜態(tài)信息識(shí)別的程序分析技術(shù)。

1 基本定義

構(gòu)造有限自動(dòng)機(jī)之前，首先需要對(duì)程序語(yǔ)言的詞法規(guī)則和語(yǔ)法規(guī)則進(jìn)行形式化描述，文法作為形式化語(yǔ)言理論的基本概念之一[5]，是闡明程序語(yǔ)言語(yǔ)法的一個(gè)重要工具。

定義1 描述語(yǔ)言語(yǔ)法結(jié)構(gòu)的形式規(guī)則稱為文法。

文法[G]表示為一個(gè)四元組：[G=VT，VN，S，P]，其中[VN]是一個(gè)非空有限集，每個(gè)元素稱為非終結(jié)符;[VT]是一個(gè)非空有限集，每個(gè)元素稱為終結(jié)符。[VT?VN=?]，即[VT]與[VN]不含公共元素。用[V]表示[VT?VN]， [V]稱為文法[G]的字母表。[P]是一個(gè)有限的具有如下形式的規(guī)則的集合：[α→β]。其中，[α∈V+]稱為規(guī)則的左部，[β∈V*]稱為規(guī)則的右部（此處[?]表示作閉包運(yùn)算）;[S]是一個(gè)非終結(jié)符，稱為開始符號(hào)，它至少要在一條規(guī)則中作為左部出現(xiàn)。

Chomsky在1956年創(chuàng)立形式語(yǔ)言譜系的時(shí)候，把文法分為四種類型即0型、1型、2型和3型。其中，2型文法又稱為上下文無(wú)關(guān)文法，3型文法又稱為正規(guī)文法。上下文無(wú)關(guān)文法和正規(guī)文法解決了程序語(yǔ)言的形式化描述問(wèn)題，在此理論分析基礎(chǔ)之上，可以預(yù)先定義好程序語(yǔ)言所有的詞法語(yǔ)法規(guī)則，建立一個(gè)用于程序分析的規(guī)則庫(kù)。

有限自動(dòng)機(jī)作為一種識(shí)別裝置，能夠自動(dòng)識(shí)別包含一系列規(guī)則的文法所定義的語(yǔ)言。有限自動(dòng)機(jī)分為兩類：確定的有限自動(dòng)機(jī)（Deterministic Finite Automata，以下簡(jiǎn)稱DFA）和不確定的有限自動(dòng)機(jī)（Nondeterministic Finite Automata，以下簡(jiǎn)稱NFA）。

定義2 一個(gè)確定的有限自動(dòng)機(jī)（[DFA]）[M]是一個(gè)五元組：[M=K，Σ，f，S，Z]，其中， [K]是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài);[Σ]是一個(gè)有限字母表，它的每個(gè)元素稱為一個(gè)輸入字符，所以也稱[Σ]為輸入符號(hào)字母表;[f]是轉(zhuǎn)換函數(shù)，是在[K×Σ→K]上的映像，如[fki，a=kj][ki∈K，kj∈K]就意味著，當(dāng)前狀態(tài)為[ki]，輸入字符為[a]時(shí)，將轉(zhuǎn)換到下一狀態(tài)[kj]，我們把[kj]稱作[ki]的一個(gè)后繼狀態(tài);[S∈K]，是唯一的一個(gè)初態(tài);[Z?K]，是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。

[NFA]和[DFA]的區(qū)別在于轉(zhuǎn)換函數(shù)[f]的不同，[DFA]的[f]是在[K×Σ→K]上的單值映射，某種狀態(tài)下給入一個(gè)輸入字符將會(huì)確定的轉(zhuǎn)到后繼狀態(tài)，而[NFA]的[f]則是多值映射，每種狀態(tài)的后繼狀態(tài)數(shù)量不是唯一的。

2 基于DFA的程序分析

2.1 有限自動(dòng)機(jī)的表示

有限自動(dòng)機(jī)通常采用狀態(tài)圖表示，以[DFA]為例，假定[DFA] M有m個(gè)狀態(tài)，n個(gè)輸入字符，那么這個(gè)狀態(tài)圖含有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有n條弧射出，整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)終態(tài)結(jié)點(diǎn)，初態(tài)結(jié)點(diǎn)冠以“[?]”，終態(tài)結(jié)點(diǎn)用雙圈表示，若[fki，a=kj]，則從狀態(tài)結(jié)點(diǎn)[ki]到狀態(tài)結(jié)點(diǎn)[kj]，畫標(biāo)記為a的弧。例如，對(duì)于這樣一個(gè)[DFA]：

其中[f]定義為：

用狀態(tài)圖表示為：

對(duì)于[Σ*]中的任何字符串t，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的標(biāo)記符連接成的字符串等于t，則稱t是可以為該有限自動(dòng)機(jī)識(shí)別的，換一種方式描述，若[t∈Σ*]，[fS，t=P]，其中[S]為[DFA]的開始狀態(tài)，[P∈Z]，[Z]為終態(tài)集，則稱[t]可為[DFA][M]所識(shí)別。

2.2 程序識(shí)別分類

根據(jù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則，軟件程序由定義、判斷、函數(shù)、循環(huán)等多種類型的代碼組成，為實(shí)現(xiàn)程序信息的識(shí)別，首先需要根據(jù)語(yǔ)法規(guī)則對(duì)程序進(jìn)行分類，然后分別設(shè)計(jì)相應(yīng)的有限自動(dòng)機(jī)進(jìn)行識(shí)別。以C語(yǔ)言為例，可以將程序類型分為表達(dá)式型、函數(shù)型、判斷型、循環(huán)型、控制型、常量型、變量型和定義型等八大類，每種類型程序需要重點(diǎn)識(shí)別的屬性如表1所示。

2.3 程序分析流程

在程序分類的基礎(chǔ)上，設(shè)計(jì)基于DFA的程序分析流程如下。

Step1：根據(jù)每種類型語(yǔ)句的語(yǔ)法規(guī)則分別構(gòu)造一個(gè)DFA;

Step2：掃描源程序并經(jīng)過(guò)匹配分析，識(shí)別出程序中的關(guān)鍵字;

Step3：根據(jù)關(guān)鍵字來(lái)確定待識(shí)別的語(yǔ)句類型，并將該關(guān)鍵字有效作用范圍內(nèi)的代碼提取出來(lái)，構(gòu)造一個(gè)待識(shí)別的標(biāo)識(shí)符集合;

Step4：將該類型語(yǔ)句的DFA與掃描得出的標(biāo)識(shí)符集合進(jìn)行匹配，匹配的同時(shí)，根據(jù)該句型的特點(diǎn)對(duì)程序的結(jié)構(gòu)信息等屬性進(jìn)行提取和存儲(chǔ)。

重復(fù)Step1～ Step4，最終可以達(dá)到理解整個(gè)源程序的目的。

例如，對(duì)于函數(shù)型程序，可以這樣構(gòu)造如下DFA：

其狀態(tài)圖表示如圖2所示。

在使用DFA對(duì)源程序進(jìn)行匹配、分析的同時(shí)，需要不斷的將識(shí)別出的標(biāo)識(shí)符進(jìn)行分類記錄，分類的依據(jù)是狀態(tài)的變遷。DFA的每個(gè)狀態(tài)都代表著一定的含義，因此每次發(fā)生狀態(tài)改變時(shí)，字符掃描庫(kù)里所記錄的字符串都是具有特殊含義的。

例如，對(duì)于函數(shù)型語(yǔ)句的DFA，狀態(tài)0處記錄的是函數(shù)名，狀態(tài)1處記錄的是參數(shù)名，這樣，我們?cè)谠O(shè)計(jì)DFA時(shí)，就應(yīng)該在狀態(tài)0處將記錄的字符串作為函數(shù)名保存，在狀態(tài)1處將記錄的字符串作為參數(shù)名保存，對(duì)于這樣一條函數(shù)執(zhí)行語(yǔ)句：function（kind， num， color）;在采用DFA對(duì)其識(shí)別后，就可以記錄下列信息：函數(shù)名為“function”，參數(shù)包括“kind”、“num”、“color”，這樣即實(shí)現(xiàn)了對(duì)這條函數(shù)執(zhí)行語(yǔ)句的理解。

2.4 程序分析技術(shù)的實(shí)現(xiàn)

基于以上理論研究成果，構(gòu)建了一個(gè)基于DFA的程序分析原型系統(tǒng)，體系結(jié)構(gòu)如圖3所示。

基于該原型系統(tǒng)可以實(shí)施程序分析工作，通過(guò)對(duì)源程序的掃描、識(shí)別，提取出程序的靜態(tài)信息，將程序的內(nèi)部耦合關(guān)系、函數(shù)調(diào)用關(guān)系等數(shù)據(jù)流和控制流等信息以圖形化的方式進(jìn)行直觀的顯示，可以用于進(jìn)一步的軟件質(zhì)量度量、軟件缺陷追蹤，以及軟件維護(hù)活動(dòng)[6]，為項(xiàng)目的軟件質(zhì)量保證工作提供有益且實(shí)用的支持環(huán)境。

3 結(jié)束語(yǔ)

對(duì)于軟件維護(hù)人員來(lái)說(shuō)，程序分析是一項(xiàng)困難且費(fèi)時(shí)的任務(wù)，本文提出的基于有限自動(dòng)機(jī)的程序分析技術(shù)，根據(jù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則設(shè)置相關(guān)有限自動(dòng)機(jī)后，能夠?qū)浖亩囗?xiàng)靜態(tài)參數(shù)進(jìn)行識(shí)別，顯著降低了用戶理解軟件的難度，對(duì)提高軟件維護(hù)人員工作效率、減少軟件維護(hù)成本能夠發(fā)揮積極作用。本文提出的方法目前主要適用于C語(yǔ)言開發(fā)的軟件，進(jìn)一步的工作需要將該方法擴(kuò)展到C++、Java等多種語(yǔ)言環(huán)境，增加適用的領(lǐng)域和范圍。

參考文獻(xiàn)（References）：

[1] 丁劍潔，魚濱，候紅.軟件維護(hù)中程序理解的應(yīng)用與研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007.17（4）：218-221

[2] Liang Jia-biao，Li Zhao-peng，Zhu Ling.Symbolic execution engine with shape analysis[J].Computer Science， 2016.43（3）：193-198

[3] 劉磊.程序分析方法[M].北京：機(jī)械工業(yè)出版社，2013

[4] 蔣宗禮，姜守旭.編譯原理[M].北京：機(jī)械工業(yè)出版社，2017

[5] 殷人昆，鄭人杰，馬素霞，白曉穎.實(shí)用軟件工程[M].北京：清華大學(xué)出版社，2012

[6] Swarup Kumar Sahoo， John Criswell， Chase Geigle. Using likely invariants for automated software fault localization[J].ACM SIGARCH Computer Architecture News，2013.41（1）：139-152