對象級粗粒度切片方法

柴玉梅，劉東昊，王黎明

（鄭州大學 信息工程學院，河南 鄭州450001）

0 引 言

程序切片技術是一種用于分解程序的程序分析技術，在程序開發(fā)、測試、理解等軟件過程中有著廣泛的應用［1－2］，本文的研究可以應用到程序理解中。程序切片的實質(zhì)是分析程序元素之間的影響關系。這項技術最早由M.Weiser博士于1979年在他的博士論文中建立起來，發(fā)展到現(xiàn)在程序切片技術已經(jīng)比較成熟。

當前較為主流的軟件開發(fā)語言很多都是面向?qū)ο蟮?，有許多研究者做了大量工作。例如A.Krishnaswamy用OPDG來計算面向?qū)ο蟪绦蚯衅?。D.Liang，L.D.Larsen和M.J.Harrold用SDG來計算對象級切片和面向?qū)ο笳绦虻那衅?。ZHAO Jian－jun等人用DODG和SDN來計算面向?qū)ο蟪绦虻膭討B(tài)切片和并發(fā)切片。李必信等人提出OOAF逐層求精計算面向?qū)ο蟪绦蚯衅?］。也有對傳統(tǒng)依賴圖進行擴充來對Java程序做切片的［4］。A.N.Martin等人提出了針對Java程序的層次切片方法［5］。也有對面向?qū)ο蟪绦蚯衅鲗Ρ妊芯康模?］。

在面向?qū)ο蟪绦蚯衅夹g中，絕大部分是語句級的切片，對對象的探討大都是融合在整個切片體系中的。李必信等人用簡化的系統(tǒng)依賴圖構造了粗粒度的切片，粒度是方法級的，也有文章如文獻 ［7］對李必信的粗粒度切片有一定擴展的。D.Liang和 M.J.Harrold的對象級切片方法是基于SDG的。專門對對象間的關系的探討如文獻 ［8］，闡述了對象間的關系類型。本文在程序切片技術思想的基礎上，依據(jù)對象間的關聯(lián)、組合等UML類間關系［9］構造對象級切片，提出一種對象級粗粒度切片方法，這種對象級粗粒度切片相對于龐大的語句級切片在一定程度上有更好的可讀性和實用性，為人們分析面向?qū)ο蟪绦虻膶ο罂蚣芴峁┝艘环N途徑。

1 基本概念

本節(jié)主要介紹本文算法所要用到的相關概念，并給以適度的形式化描述。

定義1 對象圖［10］：對象圖為一個二元組＜O，R＞，集合O是程序 （本文以Java程序為例）中出現(xiàn)的對象的集合。R為O×O上有特定關系的邊的集合，R＝ ｛（o，o’）｜（o∈O）∧ （o’∈O）∧ （（（o，o’）∈Rf）∨ （（o，o’）∈R［］）∨ （（o，o’）∈Rr））｝，其中：

Rf＝ ｛（o，o’）｜ （o∈O）∧ （o’∈O）∧ （o的字段f引用o’）｝；

R［］＝ ｛（o，o’）｜ （o∈O）∧ （o’∈O）∧ （o的數(shù)組元素引用o’）｝；

Rr＝ ｛（o，o’）｜ （o∈O）∧ （o’∈O）∧ （（o的實例方法或構造方法有一個局部變量r引用o’）∨ （o的實例方法或者構造方法調(diào)用的靜態(tài)方法有一個局部變量r引用o’））∧ （﹁Rf）｝；

對象圖的構造要用到指向分析技術［11］，本文不再詳述。

定義2 簡化對象圖［10］：簡化對象圖＜O，R’＞是對對象圖＜O，R＞中的R進行修改得到的。R’＝R∩（﹁Rtemp）；Rtemp＝ ｛（o，o’）｜ （（o，o’）∈R）∧ （o’在o中被創(chuàng)建）∧ （o’在沒被使用的情況下就被傳遞到o之外）｝。 （說明：如returnnewA（…）；或newA（newB（…）））簡便期間，下文提到對象圖都指簡化過的對象圖。

根據(jù)定義1和定義2可得圖1中類ArrayList，Literator，Apple，Pear和main1所組成的程序P1的初始對象圖和簡化對象圖，如圖2所示。對象圖中root代表P1中的main1，其它節(jié)點是程序P1中的產(chǎn)生的對象集合O中的元素，我們用對象名后加數(shù)字標號來區(qū)分程序中可能出現(xiàn)的類型相同且對象名也相同的對象。對象圖中的邊表示對象間的關系，圖2中邊root→fruit1由語句11得。邊root→apple1由語句12得。邊root→pear1由語句13得。邊root→e1由語句16得。邊e1→fruit1∈Rf由類LIterator中的字段定義得。邊f(xié)ruit1→e1∈Rr由語句4得，但是又由于fruit1→e1∈Rtemp，故在簡化對象圖中省略。邊e1→apple1∈Rr由語句17得。邊f(xié)ruit1→apple1∈Rr由語句14得。邊e1→data1∈Rr由語句7得，但是又由于e1→data1∈Rtemp故在簡化對象圖中省略。邊f(xié)ruit1→data1∈Rf由類ArrayList中的字段定義得。邊data1→apple1∈R［］由語句14得。邊data1→pear1∈R［］由語句15得。邊f(xié)ruit1→pear1∈Rr由語句15得。

定義3 所有權模型［13］：所有權模型是J.Potter等人提出的，這個模型是建立在 “所有即決定”這一概念的基礎上。

我們舉例說明對象間的組合關系：設oi，oj∈O，oi中有一個字段f，f指向oj。若程序的執(zhí)行中，所有對f的訪問都經(jīng)oi對象，則說oi對象所有 （own）oj，oi和oj是一種一對一組合關系 （compositionrelationship）。若f為集合類型，則oi和oj是一種一對多組合關系。

一般地，設oi∈O，oj∈O，ok∈O，若有oi→oj，則在對象圖 （objectgraph）中不存在ok是以下兩種情形之一的情況下，oi排它的所有 （own）oj。這兩種情形是：①ok→oj且oi→oj且ok→oi；②ok→oj且oi→oj且oi→ok。若oi排它的所有oj則添加oj到oi的組合集CS（oi）中。識別組合關系的具體細節(jié)見文獻 ［10，12－13］，其正確性見文獻 ［14］。

2 對象級切片

由于程序的對象圖可以展示對象間的訪問關系，在對象圖的基礎上做切片得到的對象級粗粒度切片在復雜程序的理解上有一定作用，本節(jié)給出一個對象級粗粒度切片算法。該算法基于基本的切片思想，即程序中指定位置的元素可以影響到程序中的哪些元素，以及程序中的哪些元素可以影響到指定位置的元素，對本文來說元素就是對象，這些元素之間存在的是關聯(lián)關系。由于組合關系是最強的一種語義級關系，將對象間的組合關系結合到對象級切片中能夠使我們更清晰方便的理解程序結構。

設程序P的對象級切片準則為一個二元組C＝＜n，o＞，其中n為程序語句n處，o∈O為語句n處的指定對象（O是程序P中出現(xiàn)的對象集合）。設對象圖OG為依據(jù)定義1和定義2對程序P構建的對象間的關聯(lián)關系圖。設集合ForeS（o）為程序P相對于切片準則C＝＜n，o＞的前向?qū)ο蠹壡衅ＴO集合BackS（o）為程序P相對于切片準則C＝＜n，o＞的后向?qū)ο蠹壡衅?。設集合CS（o’）為和對象o’有組合關系且組合到o’的對象的集合，其中o’∈O和切片準則中的o沒有必然聯(lián)系。設集合SS（o）為精簡的BackS（o），即結合了CS（o’）的BackS（o）。

前向切片F(xiàn)oreS（o）包含且僅包含對象o能影響到的對象，后向切片BackS（o）包含且僅包含那些可以影響到對象o的對象。前向切片F(xiàn)oreS（o）和后向切片BackS（o）的獲取是建立在程序P的對象圖OG基礎上的。本文還引入文獻 ［10］中對象間組合關系的識別，由定義3獲取對象圖上的所有組合關系CS（o’），并將對象間的組合關系整合到對象切片BackS（o）中從而獲得對象o的精簡后向切片SS（o）。

算法得到集合ForeS（o），BackS（o），CS（o’），SS（o）后，還可以結合對象圖OG還原他們所含的對象之間的引用關系。

算法：對象級粗粒度切片算法

注：本文的前向切片和后向切片和傳統(tǒng)程序切片比如文獻 ［15］里所述的保持相同的含義，而不是相對于本文的對象圖的邊方向來說的。

3 實例分析

由圖1中的類ArrayList，Literator，Book，Status，Borrower，Manager和main2組成程序P2。程序P2的對象圖如圖3所示，我們用對象名后加數(shù)字來區(qū)分相同類的不同對象。root代表main2，borrower1代表在語句31處實例化的對象，status1在語句19處實例化，book2在語句20處實例化，manager1在語句32處實例化，status2在語句26處實例化，book1在語句30處實例化，books1在語句25處實例化，literator1在語句4處實例化，data1在語句1處實例化。

圖3 程序P2的對象圖及其中的組合關系

我們舉例來說明對象級粗粒度切片，由對象級粗粒度切片算法可得程序P2關于切片準則C＝＜25，books1＞的前向切片F(xiàn)oreS（books1）包含books1可以影響到的那些對象，在對象圖上來說就是books1可以通過邊 ｛manager1→books1｝，影響到對象manager1，可以通過邊 ｛literator1→books1｝影響到對象literator1，可以通過邊 ｛manager1→books1，root→manager1｝影響到root。故由算法步驟3可得到books1的前向切 片F(xiàn)oreS（books1）＝ ｛books1，manager1，literator1，root｝。我們還可以由算法得到P2關于切片準則C＝＜32，manager1＞的后向切片BackS（manager1）＝ ｛manager1，books1，book1，book2，data1，literator1，status2｝。圖3的組合關 系CS（o’） 有CS（borrower1） ＝ ｛status1｝；CS（manager1）＝ ｛books1，data1，literator1 ，status2｝；CS（books1）＝ ｛data1｝。再由算法步驟4可得程序P2關于切片準則C＝＜32，manager1＞的精簡后向切片SS（manager1）＝｛manager1，books1，book1，book2，literator1，status2｝。

4 結束語

本文提出了一種對象級粗粒度程序切片方法，可以獲取對象級程序切片，該切片沒有基于傳統(tǒng)的程序依賴圖和系統(tǒng)依賴圖。由于本文切片粒度比語句級切片大，故存在不精確性，但是顯然這種粗粒度切片效率和可理解性較語句級切片有優(yōu)勢，鑒于面向?qū)ο蟮幕窘Y構是對象，這種對象級粒度的切片是有其實用意義的。該算法更多的是提出一種方法思想，下一步將研究除了關聯(lián)、組合等關系外的其它對象間關系的切片。本文的概念都是建立在面向?qū)ο筇卣鞅容^明顯的Java程序的基礎上，對其它面向?qū)ο笳Z言的有待研究。

［1］SUN Jirong，LI Zhishu，WANG Li.Overview of software testing based on program slice ［J］.Application Research of Computers，2007，24 （5）：210－213 （in Chinese）.［孫繼榮，李志蜀，王莉.程序切片技術在軟件測試中的應用 ［J］.計算機應用研究，2007，24 （5）：210－213.］

［2］NA Rong.Using slicing technique in program comprehension［J］.Computer Engineering and Design，2003，24 （1）：30－32（in Chinese）.［納榮.在程序理解中使用切片技術 ［J］.計算機工程與設計，2003，24 （1）：30－32.］

［3］LI Bixin.Program slicing technique and its applications ［M］.Beijing：Science Press，2006：252－287 （in Chinese）.［李必信.程序切片技術及其應用 ［M］.北京：科學出版社，2006：252－287.］

［4］Hammer C，Snelting G.An improved slicer for Java ［C］.New York：Proceedings of the 5th ACM SIGPLAN－SIGSOFT Workshop on Program Analysis for Software Tools and Engineering，2004：17－22.

［5］Martin A N，ZHANG Dafang，MIAO Li.A method of static Shavhg of Java program ［J］.Computing Technology and Automation，2005，24 （3）：69－71 （in Chinese）.［Martin A N，張大方，繆力.一種Java程序靜態(tài)切片的方法 ［J］.計算機技術與自動化，2005，24 （3）：69－71.］

［6］WANG Xiaohua，GU Yidong，CHEN Weiwei，et al.Comparison and research of main object oriented slicing representation ［J］.Computer Engineering and Design，2008，29 （5）：1264－1267（in Chinese）.［王曉華，顧逸東，陳蔚薇，等.面向?qū)ο笾髁髑衅硎痉ǖ谋容^研究 ［J］.計算機工程與設計，2008，29 （5）：1264－1267.］

［7］DU Lin，JIANG Haiyan.A study of computing object－oriented program slicing technology ［J］.Journal of Shandong University，2008，38 （6）：41－47 （in Chinese）.［杜林，江海燕.計算面向?qū)ο蟪绦蚯衅夹g研究 ［J］.山東大學學報，2008，38 （6）：41－47.］

［8］LIU Kun，JIANG Shujuan，LIU Lei.Description method of object relationships in object－ oriented program ［J］.Computer Engineering and Design，2008，29 （20）：5250－5252 （in Chinese）.［劉坤，姜淑娟，劉蕾.面向?qū)ο蟪绦蛑袑ο箨P系的描述方法 ［J］.計算機工程與設計，2008，29 （20）：5250－5252.］

［9］Rumbaugh J，Jacobson I，Booch G.The unified modeling language reference manual［M］.2nd ed.Addison－Wesley，2004.

［10］Milanova A.Precise identification of composition relationships for UML class diagrams［C］.Proceedings of the 20th IEEE／ACM International Conference on Automated Software Engineering，2005：76－85.

［11］Sridharan M，Bodik R.Refinement－based context－sensitive point to analysis for Java［C］.New York，NY，USA：Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation，2006：387－400.

［12］Milanova A.Composition inference for UML class diagrams ［J］.Automated Software Engineering，2007，14 （2）：179－213.

［13］LIU Y，Milanova A.Ownership and immutability inference for UML－based object access control ［C］.29th International Conference on Software Engineering，2007：323－332.

［14］LIU Y，Milanova A.UML－based alias control［R］.Technical Report RPI／DCS－06－10Rensselaer Polytechnic Institute，2006.

［15］YI Tong.Relationship between forward slices and backward slices［J］.Computer Engineering and Applications，2008，44 （12）：42－44（in Chinese）.［易彤.前向切片與后向切片之間關系的研究 ［J］.計算機工程與應用，2008，44 （12）：42－44.］