程序切片技術在程序理解中的應用

摘要：隨著計算機軟件技術的飛速發展，軟件系統的規模變得越來越大，軟件的維護工作也隨之越來越復雜。絕大部分軟件開發的主要精力都消耗在維護或者擴展原有的系統上面，而不是重新開發新系統。因此，對于軟件系統的維護問題變得極其重要，對于遺留軟件的維護、理解在軟件開發過程中已經變得越來越重要。分別介紹了程序理解的模型及工具，并結合程序切片技術探討程序切片在程序理解中的應用。

關鍵詞：程序切片； 程序理解； 逆向工程

中圖分類號：TP311 文獻標識碼：A文章編號：2095-2163（2013）02-0097-03

0引言

大多數軟件系統在開發過后都會經歷一個相當長的維護過程。在這個過程中，軟件維護人員常常需要根據已知測試結果和反饋得來的BUG進行各類糾錯，并且還可能會需要進行修改以致重新設計。實踐經驗表明，軟件開發的絕大部分精力都耗費在對原有系統的維護上面，而不是用于新系統的重新開發。專家估計用于維護的資源和時間已經占到總開發的50%到70%[1]，因而需要對其給予高度重視，并對其實現有效調控。

程序理解是從計算機程序中獲取有效知識信息的一個重要過程。這些知識信息可以用于程序排錯、完善程序、重用程序以及整理文檔等很多方面的工作[2]。簡單來講，程序理解就是通過特定的方法和技術來得到一個認知，就是這個程序是“做什么”的以及是“如何做”的。如果對其進行完整、周密的定義，可以將程序理解看作如下的一個任務：以軟件維護、升級和再實踐為目的，在不同的抽象層次上建立有關基本軟件的概念模型，包括從程序代碼本身的模型到基本應用領域的模型?；谝陨隙x，程序理解的基礎是要建立軟件產品間的直接對應關系，維護人員借助這些對應關系，就可以根據自身擁有的軟件系統的相關知識，快速定位到與其存在關聯的一系列軟件產品，比如，找到實現相應業務邏輯的可執行代碼，或者在看到代碼以后，了解到這些代碼可實現的具體業務邏輯，又或是根據一個業務邏輯，找到與其有關的特定業務邏輯。

但是，程序理解是一個復雜的任務，因其涉及對軟件系統不同抽象層次的有效理解及其之間的精確知識匹配。例如，存在于系統問題域和系統實現域之間的巨大“語言差距”就是程序理解的難點之一。程序理解過程的復雜性主要表現在如下幾個方面：

（1）具體應用領域與程序設計領域之間的專業鴻溝有待跨越。在理解某一應用領域的程序時，不僅需要程序方面的知識，還需要這一領域的專業知識，專業知識的匱乏必然給程序理解帶來相當的理解難度。

（2）軟件系統的耦合度非常高。各個功能模塊出現了交叉，由此導致程序理解難度的增加。

（3）軟件系統的不斷升級，導致程序邏輯結構的混亂。

（4）程序理解過程中，缺少必要的源程序說明文檔及相關文字材料。

（5）程序理解中，人員的心理因素也是程序理解難度增加的一個不可忽視的影響因素。

1程序理解模型及工具

11程序理解模型

隨著程序理解的發展，現已提出了許多模型[2]，這些模型在程序理解過程中發揮著關系全局的重要作用。在程序理解中，采用一種有效的程序理解模型，有助于實現高質量、高成功率的程序理解，下面對程序理解的主要模型進行簡單的說明和論述。

（1）自頂向下模型。程序理解時，采用自頂向下的理解方式，是首先假設已經理解，然后去驗證所提出的假設，最后再修改此假設的一個順序理解過程。這種理解方式需要程序員熟悉該程序應用領域的有關背景知識，然后將這些背景知識和具體程序源代碼不斷嘗試對應的過程。詳述此過程就是，將對程序進行假設作為開始，其后在代碼中驗證該假設是否成立。當初始假設獲得驗證后，可以精化出附屬的子假設，于是這些大、小假設就構成了一個樹狀結構，并按照深度優先原則，不斷地進行著驗證的深一層精化。Soloway和Ehrlich已通過經驗性研究發現，自頂向下的理解方式常常發生在程序員較為熟悉編寫代碼的技術和編碼風格的時候。

（2）自底向上模型。假設程序理解人員并不透徹了解具體業務邏輯，此時就需從閱讀程序源代碼來理解程序，再通過自底向上的方式創建程序控制流抽象，直至建立高層抽象。具體來說，該種理解方式中，程序理解人員會逐行理解程序源碼，逐步建立上一層的抽象模型。這些較高層次的抽象表現形式又將組合在一起，提取出更高層次的抽象結果。在這個過程中，語法知識與特定編程語言相關，需要考慮的是程序中的語句和基本單元，而語法知識的積累則有助于程序員形成精神模型。程序的語義知識則與特定語言無關，并隨著程序員精神模型的不斷建立而漸次獲取相應內容，內容所描述的就是程序應用領域的業務知識。大量實驗研究表明，當程序員采用這種方法來理解程序時，更多關注的是程序中的結構化信息，同時在腦海中根據這些結構化信息，首先建立程序模型。如程序員將聚焦程序中的控制流程，建立控制流圖，又或者集中在程序中的數據上，建立數據流圖，再根據數據流圖來實現程序理解。

（3）綜合模型。這種模型是自底向上和自頂向下模型的結合，并根據上述模型建立相應的知識庫，在知識庫的輔助下完成程序理解過程。

12程序理解工具

目前，已經存在多種支持程序理解的軟件工具，下面擇選較為典型的程序理解軟件工具做以分析介紹。

（1）Understand。是一款分析大型軟件工程的有力工具，由Scitool公司開發。該工具能夠分析出函數聲明或定義、數據結構的定義、交叉引用以及函數的調用圖等程序內部信息，并且也可以計算出函數的復雜度和控制語句的嵌套深度。同時Understand還集成了代碼編輯器、代碼跟蹤器和代碼分析器，提供了功能強大的用戶界面，可將分析結果以各種形式（圖形、圖表、架構圖等）呈現給用戶，為程序員進行代碼開發、維護、調試提供了更大程度的便利。目前，Understand已能支持C/C++/C#、 Ada、 Java、 FORTRAN、 Delphi 和Jovial等眾多編程語言，實現程序理解。

（2）JBPAS。是由北大青鳥研制開發的一款支持C++語言的程序理解輔助系統，由信息管理器、C++前端分析器及程序分析工具集三大主體部分構成。該系統能夠生成OOD（Object-OrientedDesign）文檔和Rose文檔。C++前端分析器則是通過數據庫的概念模型對C++程序源代碼展開分析，再將抽取出的程序片段信息保存在數據庫中。

（3）BDCom-C++。是一款支持C++語言的程序理解系統，由信息管理器、信息抽取器和用戶界面所組成。該系統以增量式分析技術對程序源代碼實現靜態分析，信息庫則是由增量型數據庫組成，同時存儲了經由信息抽取器分析后所收集到的程序信息。第2期杜均，等：程序切片技術在程序理解中的應用智能計算機與應用第3卷

（4）Rigi。是一個可裁剪、可擴展的逆向工程環境的程序理解系統，主要由Rigi-server、Rigi-reverser和Rigi-edit3這三大部分組成。其中，Rigi-server是一個用于存儲從源程序代碼抽取所得信息的靜態信息庫；Rigi-reverser是一個支持C、COBOL等程序語言的靜態信息解析器；Rigi-edit則是一個交互性的窗口編輯器，通過圖形方式展示和操控程序的靜態信息。Rigi的一個重要功能就是，可過濾掉用戶不感興趣的信息，但卻不支持對程序源代碼文本的直接搜索功能的實現。

2程序切片

21程序切片定義

程序切片概念是由Weiser于1979年在其博士論文中首次提出[3]。Weiser 等人通過對程序源代碼的分析以及對控制流程圖（CFG）的研究發現，程序的某一輸出只與源程序中的部分語句相關，即使刪除其它語句也不會影響這一輸出結果。這個發現表明，對該輸出來說，源程序和刪除無關語句后得到的可執行程序在語義上是一致的。Weiser等人即將這種只與某個輸出有關的語句段落所構成的程序，稱為源程序的一種切片[4]。由數類實踐可知，程序切片技術在軟件分析、理解、調試、測試、度量、重用、軟件質量保證、逆向工程等許多方面已經獲得廣泛的應用，并獲得良好應用效果。

22程序切片分類

目前，程序切片主要分成以下三類，分析如下。

（1）靜態切片。是指在計算程序切片時，不需考慮程序運行時候的具體輸入，只是采用靜態分析法，對由程序源代碼所得到的程序切片展開分析。該切片方法對程序的輸入通常不作任何假設，而是要考慮程序中能夠執行的所有軌跡，故而計算量較大。靜態切片的例子如圖1（a）所示。

（2）動態切片。在考慮特定輸入情況下，需要采用動態分析方法計算得到程序的動態切片。因此，動態切片的計算過程依賴于程序的特定輸入，計算時需利用程序中的某一特定執行路徑，計算工作量也較靜態切片小上很多。

（3）條件切片。由于靜態切片得到的切片結果過于寬泛，而動態切片得到的結果又過于精細，因此在計算條件切片時，可增加一個附加條件，只有滿足這個條件的輸入才能進入分析，這樣就很好避免了切片結果過于寬泛和精細問題。條件切片示例如圖1（b）所示。

23程序切片工具

（1）Wisconsin。是一個支持對C程序進行靜態切片的實用工具，主要包括三大功能：前向切片、后向切片和消片。同時，還提供生成控制流圖和函數調用圖等程序相關的設計圖。與其他C語言分析工具類似，Wisconsin也會將源程序代碼轉換為合適的中間代碼表示形式，以方便其后的程序切片工作進程。

（2）ChopShop。是由Carnegie Mellon大學計算機科學學院開發的一種逆向工程工具，能幫助程序員理解還不曾熟悉的C程序代碼。該工具采用了一種新算法，即靜態程序切片的模塊產生機制，藉此而成為一種全新的數據流分析技術。這種算法的采用使得生成結果比標準形式的切片更容易達成邏輯理解。ChopShop完全遵守ANSI標準，可以產生兩種形式的切片結果：文本形式和圖形化形式，而且還可以對結果進行分析并提供程序語言特性的處理功能。值得一提的是，ChopShop還是首個為過程提供數據抽象機制的程序切片工具。

（3）Ghinsu。是由Florida大學計算機和信息科學系主體研發，并得到軟件工程研究中心（SERC）提供基金贊助的一個項目，在其中集成了眾多輔助工具的程序切片系統，可用于軟件工程的諸多活動中，重點是在維護活動過程中發揮一些輔助作用。只是迄至目前為止，該系統僅僅支持C語言，并不支持其他語言。

（4）Unravel。是一個原型程序切片工具，可以對標準 C程序源代碼實施靜態程序切片。該項目得到美國核控制委員會（ NRC）和國家通信系統（NCS）的指定基金的鼎力援助。Unravel可以對程序切片進行組合和邏輯集合操作，通過這些操作可以識別在計算中至少出現一次的代碼。這些daima 信息對描述高級集成軟件重要且實用，因為包含在這種代碼中的一次失敗就可能導致軟件中多個邏輯構件的故障[5]。

（5）PSS/Ada。是由楊洪等人設計完成的一個Ada程序的靜態切片生成系統。該系統可以對Ada程序進行靜態數據依賴分析和控制依賴分析，并可通過這些分析結果得出Ada程序語句間存在的波動效應，相應地生成特殊形式的Ada程序切片。這一切片是從Ada程序中抽取某些語句、并以相同順序重新組成的—個新程序段。PSS/Ada系統是一個可以實現Ada軟件的測試、排錯、分析、理解和維護的有效工具，在Ada程序的并行性檢查、波動性分析、復雜性度量等方面也提供一定層次的支持力度。另外，PSS/Ada系統作為對Ada程序設計支持環境APSE的工具集的擴充，也進一步豐富了Ada軟件的開發環境[5]。

3結束語

作為一種程序理解的方法，程序切片其實就是基于原始程序而構造的一個刪減版本，切片計算時，需刪減程序中與興趣點無關的部分，從而能夠將關鍵、分散的變量由原本復雜的程序中提取出來，進而組成新的程序片段。通過對這一片段展開具體分析，可以得到所關注變量與其他變量之間的聯系，從而加速實現對程序的全面、精準理解。

參考文獻：

[1]丁劍潔，魚濱，侯紅. 軟件維護中程序理解的應用與研究[J]. 計算機技術與發展. 2007（4）：218-219.

[2]李瑩，張琴燕. 程序理解[J]. 計算機應用研究，2001（6）：41-43.

[3]WEISER M. Program slicing [J].IEEE Trans Software Eng， 1994，10（4）：352-357.

[4]李必信，鄭國梁，王云峰，等.一種分析和理解程序的方法 ——程序切片[J].計算機應用與發展，2000（3）：284-285.

[5]李必信.程序切片技術及其在面向對象軟件定量和軟件測試中的應用[D].南京：南京大學， 2000： 6-18.