一種基于有限自動機的程序分析技術研究

王超

摘? 要： 程序分析在軟件測試和軟件維護方面均有著重要作用。為實現軟件程序的自動分析，基于有限自動機理論，提出一種實現軟件靜態信息識別的程序分析技術，根據程序設計語言的語法規則對程序語句進行了分類，針對每類語句設計了對應的識別自動機，在此基礎上設計并實現了一個程序分析原型系統。系統應用結果表明，利用這一技術可以有效的提取出程序的控制流和數據流信息，能夠為軟件質量的定量分析和軟件維護工作奠定良好基礎。

關鍵詞： 有限自動機; 程序分析; 信息識別; 軟件維護

中圖分類號：TP39? ? ? ? ? 文獻標志碼：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 引言

軟件的靜態分析是軟件測試和軟件維護活動中一個必不可少的環節[1-2]。通過對軟件實施靜態分析，軟件研發人員可以了解它的整個結構及各部分之間的相互關系，了解其中所采用的數據結構及變量的使用情況，有助于對軟件的缺陷跟蹤和軟件可維護性預測等工作的開展[3]。隨著軟件規模的不斷增長，采用人工方式實現軟件理解工作已經越來越困難。

有限自動機作為一種自動識別裝置，能夠按照程序語言的語法規則識別出各種程序單元和實體[4]，因此可以用作開發程序分析器的自動構造工具。本文在有限自動機的理論基礎之上，提出一種實現軟件靜態信息識別的程序分析技術。

1 基本定義

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

定義1 描述語言語法結構的形式規則稱為文法。

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

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

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

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

[NFA]和[DFA]的區別在于轉換函數[f]的不同，[DFA]的[f]是在[K×Σ→K]上的單值映射，某種狀態下給入一個輸入字符將會確定的轉到后繼狀態，而[NFA]的[f]則是多值映射，每種狀態的后繼狀態數量不是唯一的。

2 基于DFA的程序分析

2.1 有限自動機的表示

有限自動機通常采用狀態圖表示，以[DFA]為例，假定[DFA] M有m個狀態，n個輸入字符，那么這個狀態圖含有m個結點，每個結點最多有n條弧射出，整個圖含有唯一一個初態結點和若干個終態結點，初態結點冠以“[?]”，終態結點用雙圈表示，若[fki，a=kj]，則從狀態結點[ki]到狀態結點[kj]，畫標記為a的弧。例如，對于這樣一個[DFA]：

其中[f]定義為：

用狀態圖表示為：

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

2.2 程序識別分類

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

2.3 程序分析流程

在程序分類的基礎上，設計基于DFA的程序分析流程如下。

Step1：根據每種類型語句的語法規則分別構造一個DFA;

Step2：掃描源程序并經過匹配分析，識別出程序中的關鍵字;

Step3：根據關鍵字來確定待識別的語句類型，并將該關鍵字有效作用范圍內的代碼提取出來，構造一個待識別的標識符集合;

Step4：將該類型語句的DFA與掃描得出的標識符集合進行匹配，匹配的同時，根據該句型的特點對程序的結構信息等屬性進行提取和存儲。

重復Step1～ Step4，最終可以達到理解整個源程序的目的。

例如，對于函數型程序，可以這樣構造如下DFA：

其狀態圖表示如圖2所示。

在使用DFA對源程序進行匹配、分析的同時，需要不斷的將識別出的標識符進行分類記錄，分類的依據是狀態的變遷。DFA的每個狀態都代表著一定的含義，因此每次發生狀態改變時，字符掃描庫里所記錄的字符串都是具有特殊含義的。

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

2.4 程序分析技術的實現

基于以上理論研究成果，構建了一個基于DFA的程序分析原型系統，體系結構如圖3所示。

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

3 結束語

對于軟件維護人員來說，程序分析是一項困難且費時的任務，本文提出的基于有限自動機的程序分析技術，根據程序設計語言的語法規則設置相關有限自動機后，能夠對軟件的多項靜態參數進行識別，顯著降低了用戶理解軟件的難度，對提高軟件維護人員工作效率、減少軟件維護成本能夠發揮積極作用。本文提出的方法目前主要適用于C語言開發的軟件，進一步的工作需要將該方法擴展到C++、Java等多種語言環境，增加適用的領域和范圍。

參考文獻（References）：

[1] 丁劍潔，魚濱，候紅.軟件維護中程序理解的應用與研究[J].計算機技術與發展，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].北京：機械工業出版社，2013

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

[5] 殷人昆，鄭人杰，馬素霞，白曉穎.實用軟件工程[M].北京：清華大學出版社，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