基于數(shù)據(jù)依賴圖的主域變量識別方法

（1.河南科技大學 電子信息工程學院， 河南 洛陽 471003;2.凱邁（洛陽）電子有限公司， 河南 洛陽 471003）

摘 要：隨著企業(yè)/組織中大量遺留系統(tǒng)的產(chǎn)生，遺留系統(tǒng)的業(yè)務邏輯提取技術(shù)也受到越來越多的關(guān)注。對于提取業(yè)務邏輯，主域變量是一個很好的入口點。在應用領(lǐng)域中，主域變量對應著重要的業(yè)務對象，分析主域變量的狀態(tài)變化以及主域變量間的關(guān)系可以獲得大部分的業(yè)務邏輯。但現(xiàn)今，國內(nèi)外對于主域變量識別技術(shù)的研究大多只提到它的重要性，并沒有提出如何提取主域變量的具體方法。給出了一種基于數(shù)據(jù)依賴圖(DDG)的主域變量識別方法，并將該方法運用到一大型遺留系統(tǒng)的業(yè)務邏輯提取中。實踐證明該方法大大提高了提取效率，并有效地降低了出錯的可能性。

關(guān)鍵詞：遺留系統(tǒng)；主域變量；數(shù)據(jù)依賴圖

中圖分類號：TP314 文獻標志碼：A

文章編號：10013695(2009)01015903



Technology of domain variable identification based on data dependence graph

SHEN Yujia1，HAN Songfeng2，DIAO Hainan1，2，LIU Yong1

(1.College of Electronic Information Engineering， Henan University of Science Technology， Luoyang Henan 471003， China;2.CAMA(Luoyang)Electronics Co.， Ltd， Luoyang Henan 471003， China)

Abstract:As a large number of legacy systems in the business enterprise/ organization ， the legacy system’s business rules extraction technology has been more and more attention by public.Regarding the business rules extraction， domain variable is a good entry point. In the application area， domain variables corresponding to important business objects. Most of the business rules can be obtained from the changing of domain variables and the relationship between them.But now， at home and abroad， most of the business rules extraction only mentioned the importance of domain variable and have not certainly proposed how to extract the main domain variables .This paper gave a method to identify domain variables automatically based on DDG， and made use of this method to a large legacy systems. Practice proves that this method raises efficiency greatly， and also reduces the possibility of mistakes.

Key words:legacy system；domain variable；DDG



0 引言

在遺留代碼的業(yè)務邏輯提取框架中，大部分的業(yè)務邏輯可以從分析主域變量的狀態(tài)變化以及主域變量間的關(guān)系獲得，因此主域變量的識別就顯得尤為重要。一些工作涉及到了從遺留代碼中識別主域變量。H.Huang等人[1]提出了一個選取主域變量的啟發(fā)式規(guī)則，主要思想是將系統(tǒng)的輸入和輸出作為主域變量，函數(shù)過程的輸入和輸出作為主域變量。大型遺留系統(tǒng)通常包含著數(shù)以千計的函數(shù)調(diào)用過程，僅僅通過啟發(fā)式規(guī)則來選取主域變量是遠遠不夠的，而且增加了出錯的可能性。H.M.Sneed等人[2]提出一種通過數(shù)據(jù)流識別和程序拆模(stripping)來識別和提取業(yè)務邏輯的方法。其中只強調(diào)了識別主域變量的重要性，但并沒有提出如何識別主域變量。大型遺留系統(tǒng)含有大量的主域變量，如果主域變量可以有效地被識別，分析人員就可以集中主要精力分析主域變量間的關(guān)系，并把這些業(yè)務邏輯片段整合起來，從而大大提高了提取的工作效率。

本文以啟發(fā)式規(guī)則為引導，以數(shù)據(jù)依賴圖為基礎，給出了一個識別主域變量的方法。

1 基本概念

1.1 主域變量

主域變量有以下兩種類型[3]：

a)純主域變量，是指那些在應用領(lǐng)域可以直接對應到業(yè)務實體的變量。

b)派生主域變量，是指那些與純主域變量有依賴關(guān)系的變量。

1.2 數(shù)據(jù)依賴圖

數(shù)據(jù)依賴圖(DDG)[4]是一種表達語句間數(shù)據(jù)依賴關(guān)系的圖。圖中的節(jié)點表示語句；邊表示節(jié)點之間的數(shù)據(jù)依賴關(guān)系。如果語句S1定義或改變了一個變量，而語句S2引用了這個變量，并且程序中從S1到S2的路徑上這個變量沒有被再次定義，那么語句S1與S2之間存在數(shù)據(jù)依賴關(guān)系。DDG最初用于將隱含在代碼中的定義與使用關(guān)系進行直接表達，從而優(yōu)化編譯器。同樣，DDG可以用來從遺留代碼中識別主域變量。

2 問題描述

在目前現(xiàn)有的主域變量識別技術(shù)研究中，以H.Huang提出的啟發(fā)式規(guī)則最為突出。H.M.Sneed只在識別和提取業(yè)務邏輯的方法中強調(diào)了識別主域變量的重要性，但并沒有給出如何提取主域變量的方法。

在大型遺留系統(tǒng)中，主域變量不僅只存在于輸入/輸出變量中，在程序的過程中也存在大量的主域變量。由于啟發(fā)式規(guī)則提出得較早，又沒有對其進行系統(tǒng)的總結(jié)，已經(jīng)遠遠不能滿足提取業(yè)務邏輯中識別主域變量的要求，但它給人們很多的啟發(fā)。根據(jù)啟發(fā)式規(guī)則，可以總結(jié)出系統(tǒng)和函數(shù)的輸入/輸出必然含有主域變量。本文也是以此為前提，給出了一種基于數(shù)據(jù)依賴圖的主域變量識別方法。

3 基于數(shù)據(jù)依賴圖的主域變量識別方法

這種方法的基本原理如下:與普通的系統(tǒng)I/O一樣，數(shù)據(jù)庫交互也被視為一種系統(tǒng)的輸入/輸出，那么輸入/輸出變量中一定包含一些純主域變量，剩下的工作就是識別遺留系統(tǒng)中其他純主域變量和所有派生的主域變量，而且識別過程中的變量關(guān)系被保存在主域變量庫中，以方便分析人員進行主域變量管理和分析。

基于數(shù)據(jù)依賴圖的主域變量識別方法可以分為三個步驟:a)建立控制流圖(CFG);b)建立數(shù)據(jù)依賴圖；c)識別影響輸出主域變量的其他主域變量。其中數(shù)據(jù)依賴圖是由控制流圖得到的。該識別方法的具體過程如圖1所示。

本文以一個簡單程序為例，介紹基于數(shù)據(jù)依賴圖的主域變量識別方法。實例程序如下：

cin>>n;

if(n<0)

n*=n;

sum=1;

i=1;

j=0;

while(i

j+=2;

sum+=i;

i+=1;

}

cout<

3.1 控制流圖

控制流圖是程序的靜態(tài)表達，表示程序的所有可能通路。控制流圖包含表示每個語句的節(jié)點，包括賦值、條件和循環(huán)語句，同樣也包含程序中的控制謂詞。程序起始和終止節(jié)點標志為start和stop，條件語句在控制流圖中表示為兩個分支，控制流圖中的回路表示程序中存在一個循環(huán)語句。

CFG可表示為一四元組〈S，E，start，stop〉。其中：S為節(jié)點集，程序中的語句對應圖中的節(jié)點；邊集E={(si，sj)|si，sj∈S，且語句si執(zhí)行后可能立即執(zhí)行sj}；start和stop分別為程序段的入口和出口節(jié)點。若語句序列(s1，s2，…，sn) 滿足1≤i＜n:(si，si+1)∈E，則稱(s1，s2，…，sn)為該程序的一條從s1到sn的路徑。圖2表示了示例程序的控制流圖。

3.2 數(shù)據(jù)依賴圖

本文給出得到數(shù)據(jù)依賴圖的方法是，首先在控制流圖中表示出各節(jié)點的數(shù)據(jù)依賴關(guān)系；然后刪除圖中的控制依賴關(guān)系。

3.2.1 數(shù)據(jù)依賴的定義

DEF(i)表示節(jié)點i上變量定義和改變的集合。DEF(i)={v|v是節(jié)點i所定義或改變了的變量的集合};REF(i)表示節(jié)點i上引用變量的集合:REF(i)={v|v是節(jié)點i所引用的變量集合}。如果存在一個變量x滿足以下條件，則節(jié)點j數(shù)據(jù)依賴于i:

a)x∈DEF(i)；

b)x∈REF(j)；

c)存在一條通路從i到j，其間沒有對x重新定義，并且不在同一語句中。

根據(jù)上述定義，程序段中的數(shù)據(jù)依賴信息可以從控制流圖中直接得到。由此可以得到實例程序段各節(jié)點的數(shù)據(jù)依賴關(guān)系，如圖3所示。

3.2.2 數(shù)據(jù)依賴圖的構(gòu)建

數(shù)據(jù)依賴圖是表示語句之間的數(shù)據(jù)依賴關(guān)系，可以通過刪除控制流圖的控制依賴來獲得數(shù)據(jù)依賴圖。對于識別主域變量而言，數(shù)據(jù)依賴足以表達主域變量間的依賴信息。圖4表示了實例程序的數(shù)據(jù)依賴圖。

3.3 識別主域變量

以輸出變量為起點識別主域變量，當把某個輸出變量作為純主域變量，數(shù)據(jù)依賴圖中對應的節(jié)點也相應地被確定，接下來反向跟蹤數(shù)據(jù)依賴就可以識別到新的主域變量，它們都是可能影響純主域變量的變量。這個反向跟蹤的操作將從新的主域變量再次執(zhí)行，當這個跟蹤閉包完成后，所有影響該輸出變量的所有主域變量都被識別出來。實例程序的主域變量如圖4（黑色部分）所示。

從圖4可知，j不是主域變量。可見，如果分析人員遺漏了一個純主域變量，很可能造成一連串主域變量的遺漏，這也是本方法未來工作中需要重點解決的問題。

4 算法執(zhí)行結(jié)果管理及應用

4.1 主域變量管理

對于復雜的規(guī)模較大的遺留系統(tǒng)，同一模塊的主域變量在變量庫中被集中管理，這樣分析人員可以關(guān)注于一個模塊的主域變量，集中精力分析該模塊的業(yè)務邏輯片段。

表1為從實例程序中分析出來的主域變量信息。因為實例程序比較簡單，沒有過程間調(diào)用，同義詞變量信息為空。本實例僅有一個main函數(shù)，所以模塊信息只有main，變量地址是行號信息。

表1 實例程序的主域變量

modulevariablelocationsynonym variablesynonym locationsynonym module

mainsum 4，9，11

mainn1，3

maini5，10

表2、3是通過數(shù)據(jù)依賴圖方法得出的業(yè)務邏輯提取輔助分析信息。表2中，前相關(guān)(forward relation)變量是指該變量所依賴的變量，后相關(guān)(backward relation)變量是指依賴于該變量的變量。表3中，控制依賴列(control dependence)記錄了這個變量由哪些語句控制。例如，變量n是由語句2和7來控制。

表2 主域變量相關(guān)依賴信息

4.2 算法應用

作為遺留系統(tǒng)業(yè)務邏輯提取方法，基于數(shù)據(jù)依賴圖的主域變量識別方法已經(jīng)成功運用于凱邁（洛陽）電子有限公司公用配變監(jiān)測系統(tǒng)主站軟件。

在該項目中，通信服務系統(tǒng)以及遠程監(jiān)控終端發(fā)送給系統(tǒng)指令中的每個信息域都是非常重要的主域變量。根據(jù)啟發(fā)式原則，從系統(tǒng)中共得到696個純主域變量，通過數(shù)據(jù)依賴圖方法遍歷出所有的遺留代碼，共有25 037個主域變量被識別出來。最后把它們存放在主域變量庫中。表4顯示了主域變量庫兩條記錄的部分信息。它們也是來自于公用配變監(jiān)測系統(tǒng)主站軟件的分片。

表4 公用配變監(jiān)測系統(tǒng)主站軟件分片中的主域變量管理

modulevariablelocationsynonymvariablesynonymlocationsynonymmodule

956QsQALL QPEALL1781

956 EframesonEALL

5 結(jié)束語

本文詳細描述了基于數(shù)據(jù)依賴圖的識別主域變量的方法。很明顯，對于大型遺留系統(tǒng)而言，該方法能有效地識別出程序的主域變量，同時該方法還能提供一些輔助信息，有效管理主域變量，使得數(shù)據(jù)分析更加容易。

本文方法在純主域變量的選取上，除了啟發(fā)式之外沒有更好的方法，如果漏掉了某些純主域變量，將會給業(yè)務邏輯提取帶來很多麻煩，很可能造成一連串主域變量的遺漏。這也是筆者進一步的研究工作。

參考文獻：

［1］

HUANG Hai，TSAI W T，BHATTACHARYA S，et al.Business rule extraction from legacy code[C]//Proc of the 20th Computer Software and Applications Conference. 2000:162167.

[2]SNEED H M. Extracting business logic from existing COBOL programs as a basisfor redevelopment[C]//Proc of the 9th International Workshop on Program Comprehension. 2001:167175.

[3]CHEN X P，TSAI W T，SJOINER J K，et al.Automatic variable classification for COBOL programs[C]//Proc of the 18th Annual International Computer Software and Applications Conference. 1994:432437.

[4]FERRANTE J，OTTENSTEIN K.The program dependence graph and its use in optimization[J]. ACM Trans on Programming Languages and Systems，1987，9(3):319349.

[5]艾麗蓉，趙慶蘭.面向Java語言的進化測試中分支依賴圖的構(gòu)建[J].計算機科學，2006，33(7):23.

[6]戚曉芳，徐寶文，周曉宇.一種基于程序可達圖的并發(fā)程序依賴性分析方法[J].電子學報，2007，35(2):23.

[7]EARLS A B，EMBURY S M， TURNER N H. A method for the manual extraction of business rules from legacy source code[J]. B T Technology Journal，2002，20(4):127145.

[8]BERGERETTIC J F，CARRE B A. Informationflow and dataflow analysis of programs[J]. ACM Trans on Programming Languagesand Systems，1985，7(1):3761.