王超

摘? 要： 程序分析在軟件測試和軟件維護(hù)方面均有著重要作用。為實(shí)現(xiàn)軟件程序的自動分析，基于有限自動機(jī)理論，提出一種實(shí)現(xiàn)軟件靜態(tài)信息識別的程序分析技術(shù)，根據(jù)程序設(shè)計(jì)語言的語法規(guī)則對程序語句進(jìn)行了分類，針對每類語句設(shè)計(jì)了對應(yī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)鍵詞： 有限自動機(jī); 程序分析; 信息識別; 軟件維護(hù)

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

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

1 基本定義

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

定義1 描述語言語法結(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é)符，稱為開始符號，它至少要在一條規(guī)則中作為左部出現(xiàn)。

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

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

定義2 一個(gè)確定的有限自動機(jī)（[DFA]）[M]是一個(gè)五元組：[M=K，Σ，f，S，Z]，其中， [K]是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài);[Σ]是一個(gè)有限字母表，它的每個(gè)元素稱為一個(gè)輸入字符，所以也稱[Σ]為輸入符號字母表;[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è)輸入字符將會確定的轉(zhuǎn)到后繼狀態(tài)，而[NFA]的[f]則是多值映射，每種狀態(tài)的后繼狀態(tài)數(shù)量不是唯一的。

2 基于DFA的程序分析

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

有限自動機(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的弧。例如，對于這樣一個(gè)[DFA]：

其中[f]定義為：

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

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

2.2 程序識別分類

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

2.3 程序分析流程

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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