没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记94(2004)59-69www.elsevier.com/locate/entcs从面向对象系统生成的动态信息的元模型1Abdelwahab Hamou-Lhadj和蒂莫西·C 莱斯布里奇2渥太华大学信息技术与工程学院加拿大渥太华摘要如果一个人仅限于对源代码进行静态分析,那么完全理解面向对象系统是困难的:需要基于动态分析的技术。有几种工具实现了分析对象交互的跟踪技术;然而,由于缺乏通用的交换格式,这些工具不能互操作。在本文中,我们提出了一个基于图形的格式,称为紧凑的轨迹格式(CTF),用于交换对象交互的轨迹。 CTF的设计考虑了使运行时信息难以操作的大小爆炸问题。 为了实现这一点,我们首先介绍了减少 没有任何痕迹,没有任何内容。然后,我们展示了如何将迹的树表示转换为非循环紧凑图的概念可以用来定义CTF模式的核心。关键词:元建模,动态分析,轨迹,交换轨迹,紧凑轨迹格式,DMM,逆向工程1介绍目前存在的大多数交换格式都集中在表示系统工件之间的静态关系[1,6,10]。然而,面向对象系统的出现吸引了越来越多的关注动态分析技术。这是因为多态性、继承和动态绑定使得完全理解面向对象系统变得特别困难,1本研究由NSERC、NCIT和QNX软件系统公司赞助2 电子邮件:{ahamou,tcl} @ site.uottawa.ca1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2004.01.00460 A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)59-69只进行静态分析。在本文中,我们将集中在表示面向对象的痕迹。然而,我们的模型的一个子集可以用于程序跟踪。面向对象系统的动态分析通常通过分析对象交互的痕迹来完成对象通过发送消息进行交互,这将导致消息调用。为了重现面向对象系统的良好表现,至少需要收集与方法进入和退出以及对象构造和破坏相关的事件[4]。这些可以在UML序列图上显示,或者更复杂地使用树结构。后一种表示法的优点在于,它允许使用对树进行操作的各种算法来处理轨迹。有几种工具可以对对象交互的痕迹进行操作,以帮助软件工程师进行日常维护活动[2,3,12,13,15,16]。然而,这些工具有不同的格式来表示跟踪,这阻碍了互操作性。为了更好地利用这些工具,我们需要定义一种通用格式来交换对象交互的痕迹。交换格式由两个主要部分组成:一个表示要交换的实体及其相互连接的模式,以及包含要交换的信息的文件的语法形式。本文介绍了一种用于表示对象交互的轨迹的模式,称为紧凑轨迹格式(CTF)。语法形式可以使用现有的格式来表示,例如GXL(图形交换语言)[11]或TA(元组属性语言)[10],我们将在第3节中解释。痕迹通常很大,难以处理。因此,一个好的为了实现这一点,我们使用了两种技术。第一种技术是基于调查方法来减少跟踪的大小而不删除其内容。例如,由于循环而导致的方法调用的重复可以被删除,并替换为重复次数,而无需删除跟踪的内容。正如我们在[8]中描述的先前实验中所示,这种技术可以导致重要的减少。第二种技术利用了这样一个事实,即与任何过程调用的跟踪一样,对象交互的跟踪形成树结构。此外,任何有根标号树都可以通过仅表示一次相同的子树而转换为有向无环图[5,7]。本文的其余部分组织如下;下一节重点介绍压缩技术。在第3节中,我们介绍了交换格式CTF。在第四节中,我们通过一个例子介绍了CTF的应用A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)59612压缩痕迹在本节中,我们将讨论如何更紧凑地表示轨迹。这里讨论的所有技术都可以在生成跟踪时实时应用,或者在生成跟踪后对其进行后处理。我们使用的过程是一种数据压缩形式,即减少数据所需的空间,同时保留信息内容。 但我们不能使用传统的数据压缩方法,使数据难以理解,因为我们不感兴趣的暂时缩小存储和传输的痕迹。 相反,我们希望使应用程序能够直接操作 永久压缩的痕迹。现实的痕迹可以是如此之大,适用于-阳离子不能有效地处理未压缩形式的数据。2.1通过变换我们将使用的一种密钥压缩方法是基于这样一个事实,即任何有根的有序标记树都可以通过仅表示相同子树的出现一次而转换为紧凑形式这种变换的结果是一个有向有序无环图。图1b.显示了一个有向有序的非循环图,它与图1a的轨迹完全对应(为了避免混乱,描述给定调用的信息,即类、对象和方法名称用一个字母表示)。请注意,交叉线允许保持调用的顺序。例如,对以B为根的树的第二次出现的调用在对E的调用之后一CDFCDa)b)、图1.将树转化为有向无环图无环图的节点数总是小于或等于迹(其树表示)的节点数。边的数量也减少了。这种技术首先由Downy,Sethi和Tarjan [5]引入,以促进工具的构建,从而有效地探索树木。Flajolet等人提出了一种有效而简单的变换算法。[7]的文件。BEB一BECDF62 A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)59-69我们使用术语理解单元来描述跟踪的不同子树。从理解的角度来看,软件工程师只需要理解这个序列一次,并在出现时重用这些知识。我们将触发给定理解单元的方法称为:理解单元启动器。可以很容易地注意到,图的节点数也是迹的理解单元数,因为重复的子树只表示一次。 图1A的轨迹。 包含9个调用,但只有6个理解单元,如图1所示1b. 这是因为以B为根的子树重复了两次。2.2删除重复在跟踪中重复方法调用是很常见的。 这背后的一个原因 去除这样的重复可以导致迹线的进一步压缩。由于循环或递归导致的单个理解单元的重复可以被移除,并且可以保存重复的次数,以便重建原始轨迹如图2所示。一BACDB(1)BCCDD(a)(b)图2.去除单个理解单元的重复然而,多个理解单元的重复需要添加我们称为控制节点的虚拟调用,以便维护跟踪的分层结构。 图3b. 显示了添加到图3a的轨迹中的还指示了重复次数一SEQ(1)CCECa)b)、图3.删除多个理解单元的重复阅读理解单元的非连续重复似乎是研究界关注最多的一BEBEBA. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)5963常见的假设是,它们可以用来弥合低级组件和高级领域概念之间的差距。由于在生成跟踪期间使用系统的方式,它们可能会出现在跟踪中。例如,软件工程师可能决定在不同的时间打开同一个对话框两次。这将导致相应的实现在跟踪中以非连续的方式出现,表明发生了相同的事情。这些重复也被称为模式,我们称之为跟踪模式。在有向非循环图上,迹模式被示为具有多个父节点的节点,如图1b所示3紧凑跟踪格式(CTF)在本节中,我们将介绍紧凑跟踪格式(CTF),这是一种用于交换对象交互的跟踪的格式。 我们使用UML类图来表示CTF所表示的信息。虽然这种格式只能表示对象之间的方法调用交互,但我们相信它可以很容易地扩展到表示其他类型的关系, 作为物体集群之间的相互作用。3.1模式图4显示了描述CTF模式的UML类图。Scenario类用于描述从中派生执行跟踪的使用场景我们允许一个场景由许多痕迹来表示,以支持自然的情况下,许多相同的场景的痕迹被收集来检测由非确定性引起的异常。类Trace是一个抽象超类,它描述了不同类型的跟踪可能具有的公共信息。此类允许扩展模型以考虑其他类型的跟踪,例如进程间通信的跟踪。虽然,我们专注于面向对象的系统,我们添加了codeineCallTrace类来表示过程系统的例程调用的跟踪。所谓例程,我们指的是任何不是类的方法的函数。除此之外,一些编程语言(如C++)使用例程和方法。为 了 解 决 这 个 问 题 , 我 们 决 定 将 方 法 调 用 的 跟 踪 表 示 为CockineCallTrace的一个子类。通过这样做,分析师可以创建仅例程调用的跟踪,仅方法调用的跟踪或例程和方法调用的跟踪,例如C++执行跟踪。除此之外,这允许保持设计简单和易于理解。64 A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)59-691家长1根1名发起人1孩子1重复单元0..1repetitions由于递归递归发生理解单元发起者RepetitionsDueToLoopsTraceEdge描述场景*常规行为元素*调用0..10.. 1是实例*对象ID对象方法验证节点模式发生*类方法SequenceControlNode0..1微量10..1--10.. 1方法追踪{ordered}*0..免费WiFiO图4. CTF架构由于子树在图中仅表示一次,因此任何子树的根这些是图中的节点;每个节点都可以有许多子节点和许多父节点,如图中使用父节点和子节点角色所示。边缘(即调用)使用类TraceEdge表示。如果存在循环,则用重复次数标记边节点(ComprehensionUnitInitiator)可以是例程调用节点、方法节点或控制节点。控制节点表示操纵跟踪所需的额外信息,如第2.2节中所示子类SequenceControlNode表示用于删除多个理解单元的连续重复的属性SEQ。还可以考虑其他几个有用的控制节点,并扩展ControlNode类来表示它们。尽管本文提出的模式侧重于描述运行时信息,但它的一些组件需要引用系统的静态组件。为此目的,类Routine、Method和Class被添加并关联到JavaCallNode,以描述对表示每个类、方法等的实际对象的引用。其他现有的模式,企业呼叫节点控制节点描述TracePattern电话呼叫跟踪A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)5965也可以使用系统的静态部件。在我们的案例中,我们选择了DMM [9],这是一种用于表示各种逆向工程应用程序的软件工件的模型。Object类和将其链接到MethodsObjectionN- ode的关联允许拥有描述对象级别调用的跟踪对象由对象ID标识。递 归 理 解 单 元 用 子 类 RecursionOccurrence 表 示 , 子 类RecursionOccurrence又指递归重复单元。RecursionOccurrence包含由于递归而导致的重复次数跟踪模式使用类TracePattern表示。此类包含一个可用于为跟踪模式分配高级描述的属性。相同的轨迹模式可以出现在多个轨迹中。事实上,出现在几个轨迹中的模式可能比仅出现在一个或两个轨迹中的另一个模式更相关。在这里,相关性是根据模式与设计概念的接近程度来定义的。最后,类PatternOccurrence用于描述模式发生在哪个轨迹3.2句法形式我们支持这样的想法,即模式应该独立于表示数据的文件的任何语法形式来定义。GXL [11]是CTF的句法载体的一个候选者。GXL文件由用于描述节点、边、属性等的XML元素组成。它旨在取代一些预先存在的图形格式,如GraX [6],TA [10]和RSF [14]。GXL已被工业界和学术界广泛采用为各种类型图形的标准交换格式。然而,由于使用XML标记以及明确需要将数据表示为GXL节点和边,CTF的GXL表示往往比所需的要大得多因此,CTF的紧凑性优势将被部分抵消。虽然在其他领域中表达中等大小的图时,GXL的冗长不会成为问题,但迹线的庞大表明替代方案可能是合适的。一种合理的替代语法形式是TA [10],它将最小化CTF跟踪所需的空间。未来的工作应该集中在确定哪种语法形式最适合CTF模式所表示的信息。我们还打算进行实证研究,以估计先前提出的压缩技术所达到的增益。66 A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)59-694应用在本节中,我们将通过一个示例来说明CTF模式的使用首先,我们解释了不同的技术提取对象交互的痕迹。然后,我们引入一个虚构的轨迹和模型,它使用CTF。结果是CTF架构的实例图。为了重现面向对象系统的执行,至少需要收集与对象构造和析构相关的事件,以及方法进入和退出[4]。 也可以收集其他信息。例如,如果系统是多线程系统,则需要收集与线程执行相关的事件。生成方法调用的跟踪通常有三种技术。第一种技术是基于对源代码的检测,包括在源代码中的不同位置插入探针(例如print语句)。第二项技术包括检测系统运行的执行环境例如,Java虚拟机或字节码可以被插装以生成感兴趣的事件。这种技术的优点是它不需要修改源代码。最后一种技术包括在调试器的控制下运行系统。在这种情况下,断点设置在感兴趣的位置。这种技术的优点是不需要修改源代码和环境;但是,它会大大降低系统的执行速度。目标1:A.m0obj3:C. m3obj3:C. m3(a)(b)图5. a)一个迹线作为树的例子。b)对应于迹a)为了说明CTF的使用,让我们考虑一个例子:假设使用特定系统的特性的结果生成图5a所示的跟踪。该轨迹的紧凑图如图5b所示跟踪涉及三个类,即A、B和C,以及三个对象,即obj1、obj2和obj3。有五个方法被调用:m0,m1,m2,m3和m4。我们注意到,生成的对obj2:B.m1的调用在跟踪中重复了五次,这可能是由于目标1:A.m04obj2:B.m1目标3:C.m2obj2:B.m4obj3:C.m3obj2:B.m1obj2:B.m1obj2:B.m1obj2:B.m1obj3:C.m2A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)5967:方法论obj1:对象根obj1Am0:方法验证节点对象ID =“obj1”e1:e2:repetitionsDueToLoops =4repetitionsDueToLoops = 0引发剂obj3Cm2:方法验证节点对象ID =“obj3”obj3:对象obj3Cm3:方法验证节点repetitionsDueToLoops = 0e3:TraceEdgerepetitionsDueToLoops = 0e4:TraceEdgeobj2Bm1:方法验证节点repetitionsDueToLoops = 0e5:TraceEdge描述=“画圆”:情景对象ID =“obj2”obj2:对象obj2Bm4:方法验证节点源代码.我们还注意到,这个跟踪包含一个模式,它由obj3:C.m2生成的调用序列组成,如图5b的有向有序非循环图所示。 有趣的是,注意到将迹线转换为图并去除连续的重复导致迹线的大小显著减小。《易经》云:“六道轮回”,“五行”,“五行”。:TracePattern描述=“绘制鼠标”:模式发生图6.使用CTF架构的示例实例关系图使用CTF模式的上述跟踪的实例图如图6所示。此图省略了静态模型类的实例(例如Class、Method.)避免混乱。我们假设整个场景被称为“画圆”(就像在绘图程序中一样);这个场景用Scenario类的对象表示,而轨迹则由Methods. cationTrace类的对象描述。节点用对象obj1Am0、obj2Bm1、obj3Cm2、obj3Cm3和obj2Bm4表示。每个节点都需要68 A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)59-69引用静态模型的实例。边使用TraceEdge类的实例有五个边缘。节点obj3Cm2)具有两个传入边。因此,使用OOL的软件工程师可以将其标记为模式,这里显示为一个实例模式发生。用户通过“描述”属性表明,该模式与“拖动鼠标”操作有关。它PatternOccurrence的实例显示了模式出现在哪个特定的跟踪中,以及哪些节点是发起者(在本例中是一个节点5结论和未来方向一个通用的交换格式对于允许不同的工具一起工作是很重要的。缺乏这样一种用于交换对象交互的跟踪的格式会阻碍操纵这些跟踪的工具之间的互操作性本文介绍了CTF(CompactTraceFormat)。我们使用UML类图描述CTF模式。为了解决执行轨迹的规模爆炸问题,我们将轨迹的树表示转化为相应的有向无环图,其中重复的子树只表示一次。我们还删除了重复以获得更好的压缩。未来的工作应该集中在三个方面:第一个方面包括实验许多系统的大量执行跟踪,以测试CTF的效率。所谓效率,我们指的是格式尽可能简洁地传达来自大型系统执行的信息的能力。第二个方面是关注通过CTF的工具建设者。为了实现这一点,我们需要安排几个工具构建者使用CTF或其后代作为标准格式。最后,我们需要扩展CTF来处理其他类型的执行跟踪,比如线程间通信的跟踪。引用[1] I. T.鲍曼,M. W. Godfrey和R. C. Holt,“连接架构重建框架”,Proc.第一届国际研讨会。《软件工程工具的构造》(CoSET' 9 9 ) , 洛 杉 矶 , 加 利 福 尼 亚 州 , 1 9 9 9 年 , 4 3 - 5 4 。[2] W.德波河Helm,D.黄文,[3] W. De Pauw ,E. Jensen ,N.米切尔,G 。Sevitsky,J. Vlissides,J. Yang,“VisualizingtheExecutionofJavaPrograms”,Proc. Int. 软件可视化研讨会,Dagstuhl,2002,151-162。A. Hamou-Lhadj,T.C. Lethbridge / Electronic Notes in Theoretical Computer Science 94(2004)5969[4] W. De Pauw,D.李文,[5] J.P Downey,R.塞西河E. Tarjan,ACM杂志。27(4),October 1980,758-771.[6] J. 埃伯特湾Kullbach,A.Winter,第六届逆向工程工作会议论文集,1999,89-98。[7] P. Flajolet,P. Sipala,J. -M.王志文,[8] A. Hamou-Lhadj,T. C. Lethbridge,[9] T. C. Lethbridge,“Dagstuhl中间元模型:逆向工程的模式”,(电子笔记理论计算机科学)(本卷),从第一届国际研讨会上提出的论文元模型和模式的逆向工程(ATEM),维多利亚州,2003年。[10] R. C.何德铭,[11] R. C. Holt,A. Wi n ter,A. S ch?rr,“GXL:向标准Ex c hange F ormat过渡”,P r o c. 第 七届逆向工程工作会议(WCRE),2000,162-171.[12] D. Jerding,S.鲁嘉伯,[13] D. B. Lange,Y.陈文,[14] H. A. Müller,K. Klashinsk y,“Rigi - A System for Programming-in-the-Large”,P r o c. 软件工程国际会议(ICSE),1988,80-86。[15] T.里奇纳,S。Ducasse,“使用动态信息进行协作和角色的迭代恢复”,第18届国际软件维护会议(ICSM),期刊,QC,2002,34-43。[16] T. Systéa,“理解J a v a程序的行为”,P r o c。第七届工作会议反求工程(WCRE),Brisbane,QL,2000,214-223。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功