软件系统协调模式发现与提取

理论计算机科学电子笔记260（2010）189-207www.elsevier.com/locate/entcs发现协调模式努诺湾罗德里格斯DI-CCTC，Universidade doMinho Braga，葡萄牙摘要越来越多的软件系统依赖于非平凡的协调逻辑来利用第三方服务或组件。因此，最重要的是要严格理解和掌握这一不断增长的协调层，因为这不仅会使核查更加容易，这些系统的原始规格，以及维护，进一步开发，测试，部署和集成。本文介绍了一种方法的基础上，几个程序分析技术（即依赖图，程序切片，图形模式分析）提取协调逻辑从遗留系统的源代码。这个过程由一系列预定义的协调模式驱动，并由一个专用图结构捕获，从中可以生成协调规范 在许多不同的形式主义。保留字：程序分析、协调、编排发现。1介绍软件系统的相关性和指数增长，无论是在规模还是数量上，都导致了同样数量的遗留代码，这些代码必须每天都要进行维护、改进、更换、调整和访问，以确保质量。奇怪的是，在运行软件工件的唯一质量认证仍然是生命周期耐久性的情况下，客户和软件生产商几乎没有准备修改或改进运行代码。然而，面对如此冒险的由于对遗留软件的依赖，管理人员越来越愿意花费资源来提高对代码的信心，即对代码的理解水平。此外，软件质量，要求系统符合严格和具体的质量标准，以及设计规范与实际实现的一致性，如果没有严格的运行系统模型，就不可能进行评估。这在新兴的面向服务的范例中尤其重要，在这种范例中，重要的协调问题位于应用程序的核心1电子邮件：nfr@di.uminho.pt1571-0661© 2009 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2009.12.038190N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189这就是程序理解、逆向工程和模型提取等表达的出现，指的是从遗留代码中提取特定和严格知识的广泛技术，将其表示为可延展的表示，并进行分析、分类和重建。整个系统的软件体系结构的提取通过这一点，我们理解，遵循[2]，一组特定范围的模型，暴露了系统部分（可能是组件，模块，流程）的特定方面以及它们之间的交互已经提出了几种方法来进行反向体系结构分析。其中类图生成器从面向对象的源代码中提取类图，模块图生成器从系统的模块，包或命名空间中构建框线图然而，这些都无法回答关于系统动态的关键问题：它如何与自己的组件和外部服务交互并协调它们以实现其目标？例如，从调用图中，可以识别在特定过程的执行期间调用了系统的哪些部分（有时甚至是外部系统）。然而，对于以下问题没有提供答案：如果外部资源不可用，系统是否会尝试无限期通信？如果某个进程关闭，是否会导致整个系统停止？系统是否会进入死锁状态？这些问题不能从大多数基于代码提取构建的模型中得到回答，这并不奇怪，因为行为分析被置于比大多数此类架构模型更高的抽象级别。实际上，恢复一个协调模型，能够捕捉系统的行为，其相互作用与不同的组件，是一个复杂的过程。 这种复杂性源于处理多个活动和多个参与者，而这些活动和参与者又受到多种约束的影响，例如异常情况，中断和失败。另一方面，随着越来越多的软件系统依赖于用于组合通常在不同平台上运行并由不同组织拥有的自主服务的非平凡协调逻辑，对用于识别、提取和记录运行应用的协调层的本文件是解决这一问题的一个步骤。 它的主要贡献是一种采用典型的程序分析算法即切片从遗留代码中恢复协调信息的技术。这是基于协调依赖图的概念，在续集中扩展到CDG，在这里提出作为经典程序分析中使用的标准程序依赖图的专门化[3]。在应用程序的源代码中发现协调模式是通过在相应的CDG中识别（子）图的过程来实现的。总体战略如图所示1.一、该过程首先提取一个全面的依赖图，N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189191♯原语交互规则源代码代码分析MSDG节点标签选择代码图案识别CDG图修剪&切片图案表示Fig. 1. 总体战略在续集中以首字母缩略词MSDG（在托管系统依赖关系图之后）指出，来自源代码。这是我们的方法的基本结构，并在几个方面，扩展了以前的工作，这样的程序表示。这在第2节中进行了简要的解释;完整的形式化出现在[13]中。 然后，在第3节中给出的两阶段过程中，从该结构计算上述CDG。首先，适当地标记与编码特定交互或控制原语的使用的规则相匹配的节点。然后，通过向后切片，MSDG被修剪掉与程序协调层的重构无关的所有子图。请注意，第一阶段在规则集中是参数化的，因此在所使用的交互机制类型中也是参数化的在分析中的程序。一旦生成了CDG，协调模式的发现就通过识别图中的哪些模式对它们进行编码来进行。在第4节中讨论了构成该方法中的另一个参数的这种模式以及相关联的发现算法。从CDG中发现的每个坐标模式中，识别并返回相应的源代码块。本文中讨论的技术是通用的，在这个意义上，它不依赖于编程语言或平台，在原始系统的开发。实际上，它可以实现为具有基本通信和多线程功能的任何语言。在第5节中，该方法用C中的一个（玩具）例子来说明，以保持演示文稿的独立性。然而，正在开发一个原型工具，其初步版本可从作者的网页上获得.Net Framework，每个Microsoft.Net兼容语言都编译为。2托管系统依赖图本文提出的协调发现方法的基本信息结构是一个综合依赖图-MSDG- 记录可以从其推断的基本实体和关系，192N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189+T节点= {△， △，○}SNode=Cls+Intf+Nsp=×关于我们使用适当的程序分析技术。MSDG是系统依赖图的扩展，以处理面向对象的功能，如[6，7，16]中所考虑的。我们自己的贡献是引入了一些以前没有提到的程序结构的新表示，即部分类和方法，委托，事件和lambda表达式。 对于MSDG的正式规范，以及在其构造中使用的技术的详细描述，读者可以参考[13]。但是，在本节中，我们将简要概述MSDG的结构，并根据第4节中介绍的模式发现算法的需要进行详细说明。在继续计算MSDG之前，需要首先对分析的程序进行预处理。这个预处理阶段相当于计算给定语句的使用和定义变量以及语句之间的控制依赖关系。语句中使用和定义的变量可以通过适当的表达式分析轻松计算。对于结构良好的语言，控制依赖性也可以通过triv- ially计算，就像这里讨论的那些，所以我们假设在这个阶段执行这样的分析。此外，我们还假设所有的对象引用别名都在这个预处理阶段被处理。虽然对象引用别名解析不是一个简单的操作，但我们依赖于解决这个问题的几项研究工作[14，15]，并假设所有对象别名都已正确解析。MSDG定义在三种代表程序实体的节点上：空间节点（细分为类Cls、接口Intf和名称空间Nsp）、方法节点（携带方法签名MSig、语句MSta和参数MPar的信息从形式上讲，节点=SNode+MNode+TNodeMNode=MSig+MSta+MPar哪里 表示集合不相交并集。 SNode类型的节点仅包含标识符 对于相关的程序实体。然而，其他节点表现出更进一步的结构。例如，MSta节点包括语句代码（或指向它的指针）和 标签，用于区分方法中可能的语句类型，即，MSta SType SCode类型mcall、cond、wloop、assgn，其中，例如，mcall代表包含对方法的调用的任何语句，cond代表条件表达式。 类似地，图中的MSig节点作为方法入口点节点，记录关于方法标识符及其签名的信息，即，MSig=Id ×Sig.方法参数通过N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189193▽○△ ▽○△xdefinedIn（x，v）（）下一页⟨⟨′ ⟩ ∈⇐∈{( −）∈ {}}′∈=+= × ×（+ ）×⟨ ⟩ ∈ ⇔ ()∧ ()–⟨ ⟩ ∈ ⇔ ∈ ∧ = ∧∈MPar类型的特殊节点，表示方法调用或声明中的输入（分别为输出）实际参数和形式参数从形式上讲，MPar PaIn PaOut PfIn PfOut最后，引入了结构节点TNode来处理并发性（和的情况）和表示递归定义的类（的情况）。我需要做一个简短的解释。 一node捕获生成线程的结果：它链接一个传入的控制流边，来自触发fork的顶点，和两个传出的边，一个用于新的执行流，另一个用于初始的。 线程联接由一个具有两条传入边和一条传出边的节点一个到单个恢复线程。一个节点表示一个递归定义的类，这似乎是一个比将对象树扩展到某个深度更好的选择，但固定，例如[7]中使用的深度当然，有几种类型的程序依赖关系表示为MSDG中的边。形式上，边是类型为边缘节点DepType Inf1节点其中DepType是关系类型，第三个组件可选地表示与之关联的附加信息。让我们简要回顾一下依赖关系的主要类型。dd类型的数据依赖关系将语句节点与公共变量连接起来。从形式上讲，v，dd，x，v′Edge defined Inx，vusedInx，v′哪里是一程序variable和notation（respectively，usedInx，v）表示x在节点v中定义（respectively，used）。语句节点之间的典型依赖关系是控制流cf和控制ct类型，后者将受保护的语句（例如循环或条件）或方法调用连接到它们可能的延续，并将方法签名节点（表示方法调用的入口点）连接到方法中不受另一语句控制的每个语句节点。形式上，这些条件将以下断言添加到类型Edge2的不变式：v，ct，g，vEdgevMStat，tmcall，cond，wloop vMStav，ct，，v′EdgevMSigv′ MSta其中g是未定义的或者是语句保护的评估结果另一方面，一个方法调用是由一个mc依赖来表示的，这个mc依赖来自调用语句wrt的方法签名节点。从形式上讲，v，mc，vis，v′边缘vMSta STypevmcallv′MSig2所有约束类型Edge和Edge的条件都被正式记录在[ 13 ]中给出的MSDG规范中与这些类型相关联的两个数据类型不变量中;这些不变量只是部分陈述在这篇论文中。194N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189--⟨⟨ − ⟩ ∈ ⇔ ∈ ∧∈–′′′′−′′⟨⟨−′ ⟩ ∈⇐∈∧=∧′∈（ε）♯♯⟨⟨−′ ⟩ ∈⇔′ ∈∧≠其中vis代表可见性修改器，设置为private、public、protected、internal。在表示形式参数和实际参数的节点之间也建立了特定的依赖关系此外，所有的前连接到相应的方法签名节点，而实际的参数节点连接到方法调用节点通过控制边缘。最后，形式参数节点之间的任何数据依赖关系都被镜像到相应的实际参数。总而言之，这些将以下断言添加到MSDG不变式：v，pi，，v 边vPaInvPfInv，po，，v EdgevPaOutvPfOutv，ct，，v 边缘vMSigvPaIn PaOutv，ct，，v EdgevMSta STypevmcallv PfIn PfOutv，dd，−，v′∈Edge<$v∈PaIn<$v′∈PaOut<$<$u，d d，−，u′<$. （u∈PfIn<$u′∈PfOut）类继承和类拥有特定方法的事实被记录下来 如下v，ci，，v Edgev，v Clsv vv，cl，vis，v′∈Edge惠v∈Cls <$v′∈MSig并且类似地，对于接口和名称空间节点也是如此。在现代编程语言中常见的其他程序实体和属性也在MSDG中捕获。它们包括，即，属性（C和其他基于. Net的语言中的特殊程序构造，旨在封装对类变量的访问。但也包括部分类和部分方法，后者需要在部分方法的声明与其实现之间以及委托，事件和λ表达式之间的mc依赖边缘。委托是一种函数，其值是对象，因此可能定义类成员类型。从订阅侧，即，具有调用订阅方法的委托定义的类，添加方法节点以表示委托类型，以及用于其参数和结果的参数节点。对订阅类内部委托的每个调用都由委托类型引入的MSig节点的方法调用边表示。这就像一个代理，将其调用分发给订阅委托的对象和方法。 在什么方面对于图形表示，委托和事件之间的区别在于，后者可以由多个方法订阅，而委托订阅则相互覆盖。因此，它们在MSDG中的表示与委托类似，但订阅的方法和订阅者中要调用的实际方法之间可能存在多个mc类似的方法也用于λ-表达式的表示，在C中，λ-表达式是有状态的，并且表现为匿名方法（更多细节请参见[13]N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189195∈=CDisc= {sync，dec}♯关于我们=++=×（ ××）CMSig=MSig ×（CType×CDisc ×CRole）3协调依赖图本文介绍的发现过程的第二阶段是CDG的重新构建，它基本上删除了MSDG中与应用协调层的重新构建不直接相关的所有信息。这个阶段由一组规则的规范指导，这些规则指定了源代码中使用的交互原语，这些原语实际上是任何协调方案的构建块这些规则规定如下：CRule RExp CT ypeCDiscCRoleCType={webservice，rmi，remoting，remote}CRole提供者、消费者其中RExp是正则表达式，CType是通信原语类型（可扩展到其他通信原语类），CDisc是调用模式（同步或异步），最后，CRole字符表示通信方向的代码片段角色。例如，在C中，对Web服务的调用的标识可以通过以下规则来捕获 ， 该 规 则 标 识 了 通 常 用 于 调 用 Web 服 务 的 原 始 同 步 框 架 方 法SoapHttpClientProtocol. socke：R =（“SoapHttpClientProtocol. configurerke（*）;"，（webservice，sync，consumer））给定一组规则，CDG计算首先根据规则中的正则表达式如果MSta或MSig类型的节点匹配这样的正则表达式之一，则它将使用规则的第二个组件中的信息进行标记因此，结果节点的类型是CMSta=MSta ×（CType×CDisc ×CRole）注意，由于这个标记过程，CDG节点的类型是CNode节点CMSta CMSig在完成该标记阶段时，该方法通过抽象掉图中不参与协调层的部分来进行。这是一个主要的抽象过程，通过删除所有未标记的节点来完成，但对于那些验证以下条件的节点：(i) 方法调用节点（即，节点v使得具有STypevmcall的vmSta），对于该节点存在控制流路径（即，CF依赖边的链）到标记的节点。(ii) 在程序的后向切片的并集中的顶点相对于每个标记的节点。196N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189NodeId=N<${△，<$}={}= ×（× × ×）请注意，第一个条件确保保留相关的过程调用嵌套结构。此信息将有助于以类似的方式在完成发现过程时嵌套生成的代码。第二个条件保留了程序中所有可能删除先前标记的节点的语句。 这包括，即，其语句包含谓词的MSta节点（例如，循环或条件），其可以检查用于执行通信原语的参数，并且因此在协调层中起作用这个阶段需要在MSDG上进行切片过程，为此我们采用了类似于[4]中提出的向后切片算法。它包括两个阶段。第一个阶段通过向后遍历MSDG来标记访问过的节点，从匹配切片标准的节点开始，并遵循ct，mc，pi和dd标记的边缘。第二阶段包括向后遍历整个图，从阶段1上标记的每个节点开始，然后是ct，po和dd标记的边。 在阶段2结束时，由所有标记节点的集合表示的程序相对于初始切片标准构成切片除了cf标记的边之外，原始MSDG中具有作为源或目标的移除节点的每一个其他边也从最终图中移除。 相同的对包含作为源或宿的修剪节点的任何CF另一方面，引入新的ct边缘来表示在原始MSDG中，即在移除操作之前，这种依赖性的链是什么。这确保了将来对这个图的遍历是以正确的语句控制顺序执行的。4协调模式发现4.1描述协调模式与MSDG（通常是一个庞大而复杂的结构）相比，从典型系统中提取的CDG要小得多，因为所有与协调层无关的代码都已被删除。然而，正确识别这样一个层的结构，通常是不平凡的。在我们的方法中，这个过程是由一系列预定义的协调模式驱动的，这些模式被编码为子图实例，这些子图实例将在CDG上被发现形式上，协调模式被定义为由匹配条件（类型为PCondition）和节点Id类型的图形成的对，如下所示模式PCondition NodeId ThreadId NodeIdPathPatternPCondition= NodeId2Gnode路径模式N匹配条件是映射（即，部分函数），其将（类型为NodeId的）每个模式节点与（类型为Gnode的）CDG节点上的谓词相关联。在实践中，一个常见的定义，如谓词诉诸于一个正则表达式，旨在测试与CDG上收集的程序信息的匹配N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189197∗+∥（）=（（））（）=====结符号用于表示处处为真的谓词。模式条件的示例将在本节后面显示模式的第二个组成部分是由线程标识符（ThreadId）标记的边序列，该线程标识符用于指定模式中的中间线程，以及限定符（类型为PathPattern），该限定符指定模式中的边的数量。 CDG可以在匹配源节点和目标节点的节点之间进行调解在模式中。 特别地，符号用于表示一个或多个边。请注意，此限定符始终大于0。我们还假设，所有节点的序列中的边缘的模式，不属于域的相应的条件，隐含标记的处处真谓词。基于上述数据规范，我们定义了一种小语言来表达协调模式。这种符号被称为协调依赖图模式语言（CDGPL），专门设计用于描述CDG图模式，并促进自动发现这种模式-见[13]，即为完整的说明。特别地，发现过程由我们称为搜索模式的东西指导，即简单地定义为模式（模式类型）或模式的合取（）或析取（）聚合的表达式。然而，为了说明的目的，我们在本文中诉诸于一个图形符号来呈现一些最典型的协调模式，如图所示二、 在每个模式中，符号vcx表示节点x的节点条件。4.1.1同步顺序模式这是一种最简单的模式，在这种模式中，顺序中的外部服务被一个接一个地调用。当多个服务调用之间存在依赖关系时，通常采用这种简单但经常使用的模式，即，当服务调用依赖于从前一个服务调用接收到的响应时在我们的符号中，这种模式如图2（a）所示，其中每个节点对应于要按顺序调用的一系列服务的服务调用。如果原始源代码通过访问Web服务实现协调，则这些顶点的条件可以由以下谓词模板定义PC xXMStat，s，cp，cm，cdmatch s，其中4.1.2循环查询模式此模式的特征是，在某个点上，新线程被派生出来，负责外部服务的持续调用。它通常用于必须监视某些外部资源的状态或必须不断更新依赖于外部服务的内部资源的实际上，这种模式有几种变化。 例如，它可以在-198N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189(a) 同步顺序模式（b）循环查询模式(c)异步查询模式（Asynchronous Query Pattern）客户端多线程(e) 异步顺序查询模式(f) 连接异步顺序模式图二. CDGPL模式在每个循环服务调用之间包括时间延迟，或者使用不同的策略来实现服务调用周期，例如，采用递归函数定义或迭代控制语句。 图2（b）中呈现的模式捕捉到了最通用的版本。 它基本上声明必须产生新线程y，并且在这些新线程的执行下，必须重复调用服务。同样，顶点1必须用谓词实例化，类似于前一个谓词，限制被调用的服务4.1.3异步查询模式.如果需要调用耗时的服务，通常使用异步查询模式，并且调用线程在返回响应之前不能挂起。为了克服这种情况，服务器组件提供了两种方法，一种用于请求服务器上的操作，另一种用于查询N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189199∗地图：联系我们从先前发布的请求中获得答案（如果可用）。这两个服务器方法都返回得非常快，因为它们不参与任何复杂操作的执行，而是参与复杂操作的执行和结果检索的控制。 从客户端来看，这种模式由以下定义来具体化： 在图2（c）中，编码服务的调用以请求执行某个操作执行（节点1）和另一服务的循环调用（节点2）以检索结果。再一次，在实践中，顶点1和2都可以进一步由清楚地标识操作请求和结果请求服务的谓词来表征。4.1.4异步查询模式（使用客户端多线程）这种经常使用的模式实际上是前一种模式的变体，在前一种模式中，客户端在一个线程中命令执行操作，然后启动第二个线程来检索结果。请注意，图2（d）中所示的模式也与循环模式非常相似，但对于一个额外的节点，标记为表示控制执行更多调用以检索操作结果4.1.5异步顺序模式这类似于异步顺序模式，除了它在专门为事件创建的新线程中调用每个服务。当系统必须调用一系列服务时，经常使用这种模式，调用的顺序以及返回的响应都无关紧要。请注意，在此前提下，在调用一系列服务时，此模式要比异步顺序模式快得多。这种模式在图2（e）中详细说明，其中每个服务调用节点（1和2）在不同的线程（分别为y和w）中被调用4.1.6连接异步顺序模式这与前面的模式类似，因为在这两种模式中，异步调用。 不同之处在于，在这种模式中，人们感兴趣的是控制每个被调用的服务完成执行并可能返回值的点。这种模式的具体情况见图11。2（f）其中，产生以调用服务的每个线程稍后加入在保证所有服务调用已完成执行的情况下，执行可以继续的点。4.2发现算法本节中介绍的算法检索符合给定图形模式的CDG的每个子图形。不言自明的符号。但是，让我们指出点的使用。作为记录中的字段选择器，以及采用Haskell语法用于列表（包括用于追加和用于连接）。 赋值由操作员;请注意它可以由一个声明被绑定变量类型的表达式来前缀200N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189v∶∶ Gnode}拜访过的：：B}att∶∶[Attribution]}={∶}VertexPattern=VP{id：：Int，♯该算法采用图3中的数据类型，也用Haskell语法表示数据类型声明。特别要注意的是，CDG和表示要发现的模式的图如何通过嵌入Graph和GraphPattern而对算法可用：在这两种情况下，节点都被选为作为搜索的起点图G root Gnode，G CDGGraphP attern=GP{root∶∶NodeId，G∶∶V ertexPattern}cdts∶∶[Gnode]属性=AT{vp ∶∶ V ertexPattern，扩展=E{g∶∶Graph，图三. 图模式发现算法发现算法1和2所使用的总体策略包括遍历图模式和递增地构建具有类型属性的节点的候选图的列表。 该算法使用此类型，因为它维护图形模式节点和CDG节点之间的映射。如果在图模式的遍历期间发现候选图不能被扩展以符合的模式，则从候选图列表中移除所讨论的图。另一方面，如果候选图可以用几个CDG候选节点中的一个来扩展，则它产生一系列新的候选图（一个对于每个CDG候选节点），并且从候选列表中移除原始（不完整的）候选。算法中使用的大多数辅助函数都是通过其恒等式自解释的， 文件名，可能的例外是函数GET SU ccC组合，它计算属性列表的列表，即，对于给定节点模式的可能属性的每个可能集合的列表。通过使用图模式发现算法，我们现在能够识别遗留代码中的协调模式。 此外，委员会认为，如果每个模式都与文献中可用的几种协调语言之一的模式“实现”相关联5例如作为所提出的协调模式发现方法的示例，考虑附录A中的C代码片段。代码中使用的类WeatherServer是Web服务代理类，由工具Microsoft.VSDesigner自动生成。示例代码旨在在客户端上运行，该客户端调用服务器以根据当前天气状况预测未来几天的天气由于天气预报是一项复杂和耗时的任务，客户端执行线程被保持，直到返回来自服务器的响应。因此，客户端将预测操作提交给服务器，服务器立即返回，从而产生用于客户端请求的操作标识符，然后，N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）1892014：Graph bg←emptyGraph（）17：b←b长度（dgel）> 0←29：map（λx→（x.g，vpa））凝胶23：r← []27：b←真[] ← [（（→（））]13：如果c1≠c2，则15：[Extension]r ←ge ∶r[] ←∶[] ←（）←（→（））11：c1←HAS SU ccESSORS（cdgp，datt.v）26：如果b为null，则←←（）3：cdgp←文件夹（cdg，cdgp）24：a← []21：gel←REMOVE（gel，r）rgel算法1模式发现-第一一曰： 函数D是 P模式上的c（Graph cdg，GraphPattern cdgp）2：cdgp← 文件备用文件（cdg、cdgp）5：延伸凝胶bg，映射λx cdgp.root，x cdgp.root.cdts6：重复7：Bb假8：对于凝胶中的所有延伸ge，9：对于所有属性datt在ge.att做10：datt.vp.visitedTrue12：c2！ 公司简介 通用电气公司副总裁14：延伸dgelE延伸碱基G通用电气公司16：延伸段a dgel a18：如果结束19：结束20：结束删除所有元素22：gel←gel ++r将所有a元素添加到gel25：不存在←NOT VISITED（cdgp）不存在获取第一个未访问的顶点模式28：vpa图λ x，x.cdts30：如果结束31：直到b== True32：返回凝胶三十三： end function请求应答的责任被传递给客户端，客户端必须对服务器执行多次查询，直到返回天气预测应答。一旦客户端从服务器收到带有预测的答案，它就会检查结果，如果结果似乎是错误的（方法CheckPrediction），它就会向服务器提交一个新的请求，以便重新评估预测。通过对客户行为的描述，或多或少可以清楚地看出，该客户端可能实现先前提出的异步查询模式的一个或多个实例。 更困难的是，要准确地识别代码中的哪些语句负责模式的实现。请注意，在现实世界的系统中，这种困难甚至更大，因为代码肯定会202N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189←（）第37章：一个人←（[]）（）下（）下（（））40：如果b为null，则算法2模式发现-第二三十四： 函数EEXTEND BASEG（Graph bg，Attribution att）35：tcsG ET S U ccC组合cdgp副总裁36：对于技合处的所有技合，38：凝胶GE，39：对于TC中的所有CV，四十一：ADD EEDGE（ng，att，cv）42：ge.DiscoveredAttributions.Add cv43：其他44：凝胶。去除凝胶第45章：分手46：如果结束第47章：结束第48章：结束49：返回凝胶五十： end function被由于空间限制，我们省略了一些代码细节，这些细节通过下划线注释清楚地标识。其中两个遗漏与传递给服务器操作的参数的构造有关（第15和31行），这相当于收集当前的天气状况。第二个遗漏（第52行）涉及设置Web服务代理类的代码，它包含控制所有简单对象访问协议（SOAP）通信以及所有对象编组操作的代码。发现异步查询模式实例的过程始于为所分析的代码构造MSDG。附录B中的图B.1给出了示例代码的MSDG。为了保持图的可读性，我们选择只包括控制、方法调用、控制流程、正式的输入和输出依赖。下一阶段包括基于以下内容计算CDG：构建的MSDG。在这个例子中 ， 我 们 感 兴 趣 的 是 识 别 对 Web 服 务 的 同 步 调 用 。 可 以 使 用 规 则“SoapHttpClientProtocol. Webke（*）;“、WebService、Sync、Consumer来执行此类标识，该规则标识Microsoft.VSDesigner工具进行的Web服务调用。计算CDG的过程，如第3节所述，导致代码行3、7、8、9、10、14、24、26、30、39和42的消除，或在图B.1中虚线顶点的图形化。请注意，删除的语句正是那些没有直接参与Web服务调用的语句，N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189203cp==webserviceweb cncm ==sync web cncd= =consumercd==消费者f（2）=23f（2）=3812（）=（）=这个小而高度协调的专用代码几乎完全对应于IO语句。然而，在一个真实世界的系统中，除了协调外部资源之外，还包含控制许多其他方面的逻辑，相对于整个系统，程序语句被切片的百分比肯定会高得多。接下来的阶段是在CDGPL中定义一个表达式，它描述了人们正在寻找的协调模式。对于这个例子，我们将使用4.1节中给出的异步查询模式CDGPL定义，并使用以下pc模式条件。这个模式条件使用了一个名为match的正则表达式匹配函数。pc（1）=λ（MSta（t，s），cp，cm，cd）→（match（s，pc（2）=λ（MSta（t，s），cp，cm，cd）→match（s，使用第4.2节中提出的图形模式发现算法，可以清楚地识别代码中使用的异步查询模式的两个实例，并通过顶点模式标识符和 示例代码行语句。为了便于识别协调模式实例中涉及的语句，附录A中的示例代码用红色和斜体字体突出显示了这些语句f1（1）= 16f2（1）= 32f1325f2 340请注意，虽然被发现为相同协调模式的实例，但实现彼此非常不同在第一种情况下，通过while循环来执行对答案的查询，而在第二种情况下，这是通过递归调用方法GetForecastOptimationResult来执行的。6结论和今后的工作本文介绍了一种结合依赖图、程序切片和图模式分析等多种程序分析技术从遗留系统源代码中提取协调逻辑的方法。 该过程是由 通过一系列预定义的协调模式，并通过一个特殊目的的图形结构来捕获，从该图形结构中，可以以许多不同的形式主义来生成协调规范。使用依赖图来表示不同种类的程序实体以及它们相互依赖的方式已经成为一种普遍的方法。在程序分析社区中有着悠久的历史-参见[10]作为早期参考。我们的贡献是扩展了以前的工作（即[5，8]），以收集204N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189提取应用程序的（通常隐藏得很深的）协调层所必需的所有信息。请注意，大多数为逆向工程开发的工作和工具都有有限的范围，通常旨在从遗留代码中获取模块、类图和方法调用依赖关系最相关的部分之一，如果这种方法是它的参数化的规则确定的通信原语之一是感兴趣的，从而使它适应各种协调分析和编程框架。鉴于语言的异质性，弥漫在大多数软件，这种用于实现这里所提出的技术的原型工具3目前正在开发中。该工具名为COORDI nspecTOR，目标是通用中间语言（CIL），因此能够处理任何Microsoft .Net语言。虽然目标是一种完全不同的语言，但COORD I nspecTOR的开发共享了[12，11，9]中讨论的许多直觉虽然这种方法和工具的最直接应用是协助通过对遗留系统的协调分析，它们还可以用于评估系统实现的正确性，这些正确性与其设计规范有关，甚至与不断增长的软件质量法规有关。 更重要的是，通过提供COM或RMI通信发现的规则，它可以用来帮助分布式对象系统向面向Web服务的系统（或反之亦然）的转换。未来工作的一个有趣的主题是协调模式的分类，如[1]，根据CDGPL中表达的图形模式表示。这些信息将允许创建一个协调模式库，该库不仅可用于反向，而且可用于正向系统工程。引用[1] W. M. P. 诉D. Aalst，A.H. M. T. 霍夫斯泰德湾Kiepuszewski和A.P. 巴罗斯 工作流程模式。分布量并行数据库，14（1）：5 -51 ， 2003 年。[2] L. Bass，P.Clements和R.卡兹曼软件架构实践艾迪森·韦斯利1998年[3] J. Ferrante，K. J. Ottern和J. D.沃伦程序依赖图及其在优化中的应用。ACM翻译计划。Lang.系统，9（3）：319[4] S. Horwitz，T. Reps和D.宾克利使用依赖图的过程间切片。PLDI '88：ACM SIGPLAN 1988会议记录。《编程的使用、设计和实现》，第35-46页。ACM Press，1988.[5] J·克林克并发程序的上下文敏感切片。SIGSOFT软件Eng. Notes，28（5）：178- 187 ，2003.[6] L.拉森和M。J·哈罗德面向对象软件的切片。在ICSEIEEE计算机协会。[7] D. Liang和M. J·哈罗德使用系统依赖图对对象进行切片。在ICSMIEEE计算机协会。3初稿可在作者网页上查阅N.F. Rodrigues/Electronic Notes in Theoretical Computer Science 260（2010）189205{}{}[8] M. G. Nanda和S.拉梅什切片并发程序。在ISSTAACM。[9] M. G. Nanda和S.拉梅什多线程程序的过程间切片及其在java中的应用。ACM翻译计划。Lang.系统，28（6）：1088[10] K. J. Ottern和L. M.奥特曼软件开发环境中的程序依赖图。2001年：第一届ACM SIGSOFT/SIGPLAN软件工程研讨会论文集，实用软件开发环境，第177ACM Press，1984.[11] V. P. Ranganath，T. Amtoft，A. Banerjee，J. Hatterykee，and M. B.德怀尔现代程序结构的控制依赖和切片 ACM Trans. 程序. 浪系统，29（5）：27，2007.[12] V. P. Ranganath和J. Hatanath。使用indus和kaveri对并发java程序进行切片。 国际软件杂志工具技术转移，9（5）：489[13] N. F.罗德里格斯通用软件切片应用于遗留系统的体系结构分析。博士论文，Dep。 Inform'atica，UniveradicadedoMinho，2008. （PhDThesis）。[14] P. Tonella，G.安东托河Fiutem和E.梅洛流不敏感的c++指针和多态性分析及其在切片中的应用。软件工程国际会议，第433-443页，1997年[15] J. Woo，J.- L. Gaudiot和A. L.文德尔博恩 用引用集表示法分