法律状态公告日
法律状态信息
法律状态
2017-04-12
授权
授权
2014-07-09
实质审查的生效 IPC(主分类):G06F9/44 申请日:20140312
实质审查的生效
2014-06-11
公开
公开
技术领域
本发明涉及一种语义Web服务组合的自动验证方法及其系统。
背景技术
随着Web服务标准的持续完善和支持Web服务的企业级软件平台的不断 成熟，越来越多的企业和商业组织参与到软件服务化(Software as a Service)的 行列中来，纷纷将其业务功能和组件包装成标准的Web服务发布出去，实现 快速便捷的寻求合作伙伴、挖掘潜在客户和达到业务增值的目的。然而由于 用户需求呈现复杂化趋势，单个Web服务已经难以提供用户所需的功能。但 如果将分布于Web上的多个功能有限的简单Web服务按照共享上下文策略进 行通信与协作，形成更大粒度、功能更强的复杂服务，就可能满足更多更复 杂的用户需求。Web服务组合问题就是在这样的背景下被提出来的，它是指 通过服务查找和服务之间的接口集成，将多个自治的Web服务根据用户需求 进行连接，从而形成提供新的或增值功能的Web服务。
虽然通过服务组合，能够获得功能更强的组合服务，但也会使得服务之 间的交互流程变得频繁和复杂，这导致组合服务难免会存在一些错误。因此 对于Web服务组合的验证是必不可少的，主要原因有以下两点：
（1）Web服务组合是把功能不同的自治的Web服务连接起来，这需要通 过定义和设计控制流及数据流来进行组织。通过控制流和数据流，就定义了 Web服务之间的交互协议。交互协议是否是具有良定义性(Well-Formed)、活 性(Live)和安全性(Safety)，取决于组合服务设计人员的水平或者组合服务设 计工具的能力。然而面对越来越复杂的Web服务组合，组合服务设计人员的 水平和组合服务设计工具的能力显得愈加不足，很难保证服务的组合不会出 错。
（2）用户只能对所需服务行远程调用，并不能控制其执行过程。所以存 在错误的组合服务流程一旦投入运行，就可能产生无法弥补的损失，这是用 户所不能接受的。因此对组合服务进行正确性验证，能够尽早地发现和解决 问题，减少经济和时间成本的不必要消耗。
由于组合服务日趋复杂，采用人工分析的方式效率低下。同时其本身所 具有的动态性特征，也大大增加了验证分析的工作量。而建立自动化的分析 技术与工具，则必须要以形式化模型为基础，也是势在必行的工作。目前， 国内外针对Web服务组合验证这一问题展开了广泛的研究，且均是以形式化 方法为基础，如Petri网、自动机理论或进程代数，基本上可以分为两类：
1，直接验证
直接验证方法是指对组合服务进行形式化建模后，可以直接对模型进行 分析和验证，例如Pi演算、通信系统演算CCS和Petri网。Pi演算适用于验证 Web服务间的兼容性，能够对服务的行为和服务间的交互进行建模，通过Pi 演算的操作、自动推演等理论判断服务间交互的兼容性。但它只能对两个服 务间的兼容性进行验证，而无法验证一个服务与多个服务间的兼容性。通信 系统演算CCS可以与Web服务编排协议WSCI进行直接的映射和转换，从而建 立起Web服务组合的形式化模型，通过CCS的推理功能可验证两个或多个Web 服务之间的兼容性，同时还可以验证服务之间的可替换性。Petri网是一种重 要的分布式系统的建模和分析工具，适合于验证Web服务组合的流程正确性、 操作兼容性和语义正确性。Petri网有多种形式的扩展与变种，可以表达Web 服务的丰富语义，例如时间Petri网、有色Petri网、模糊Petri网等。同时Petri 网还带有自动化验证工具，对模型的分析与验证提供了很大的便利。
2，间接验证
间接验证方法是指在建立起Web服务组合的形式化模型后，由于该种形 式化模型没有直接的验证工具，必须将其转换成其它的形式化描述形式，才 能进行验证。这类方法主要是一些专门的组合服务或流程的描述工具，设计 的初衷就是为了对单一对象进行描述，通用描述能力往往不强，因此也就缺 乏对它的分析和验证方面的研究。例如XLANG、WSFL、BPEL4WS等。
XLANG是由Microsoft提出的一种Web服务组合描述语言，它将工作流描 述成有状态的长周期交互行为，用WSDL语言描述业务流程中各参与者的 Web服务接口，并通过消息交换产生服务间的交互。它实际上是WSDL的一 种扩展。
WSFL即Web服务流语言，是由IBM提出的一种基于XML的Web服务组合 描述语言，由流模型和全局模型组成，前者用于描述如何使用组件Web服务 提供的功能实现一个组合Web服务，并通过定义控制流和数据流的方向指定 组件服务的执行顺序；后者用于描述各组件Web服务之间的交互情况。目前 已有将WSFL描述的组合流程转换成Promela规范语言的算法，从而可以用对 应的模型检测工具SPIN进行自动验证。
BPEL4WS是由IBM、Microsoft和BEA公司联合推出的，汲取了XLANG 和WSFL的优点，结合了图形化和块结构的特点，是一个用于描述基于Web 服务的可执行业务流程描述语言，已得到多种开源和商业引擎的支持。 BPEL4WS将Web服务组合描述成一个有向图，顶点代表Web服务，边表示服 务之间的依赖关系。依赖关系的运行语义可以在BPEL4WS的文档中指定。通 过相应的进程代数编译器，可对Web服务组合进行验证。
与本发明最相似的技术方案是将OWL-S描述的语义Web服务转换为有色 Petri网，然后通过对有色Petri网的性质分析（关联矩阵、活性、可达性等）， 完成对组合服务的验证。
OWL-S与语义Web服务：OWL-S是以OWL语言描述的Web服务本体，它 是机器可理解并且显式而无歧义的标记语言(Markup Language)，可以完整地 描述服务的功能和属性。它是一种成熟且被广泛应用的技术规范，具有坚实 的理论基础和强大的工业应用支持。OWL-S的顶层本体视图，如图1所示。
OWL-S通过三个部分来对一个Web服务进行描述：Service Profile、Service Grounding和Service Model。并且有如下规定：一个Web服务最多只能关联一 个Service Model，但可以缺少；一个Service Grounding必须且只能与一个Web 服务关联，而一个Web服务可以关联多个Service Grounding；一个Web服务可 以关联零个或多个Service Profile。
1.Service Profile
Service Profile的作用是描述服务的概貌，包括三个部分的信息：
服务提供者：包括提供者的名称、文本描述和联系信息。
服务功能：提供服务的IOPEs(Input、Output、Precondition、Effect)，分 别从信息和状态两个角度来描述服务的功能。Service Profile并不单独描述 IOPE，而是链接到Service Model中的IOPEs实例。
服务分类与质量：服务所属的类别，以及成本、响应时间、可靠度等用 于衡量服务质量的信息。
服务提供者可以通过Service Profile来描述要发布的服务，而用户也可 以通过它来描述对服务的需求，主要用于支持Web服务发现。此外，Service Profile是独立的技术，因此支持各种服务注册方式。
2.Service Model
Service Model包含服务的内部数据及控制流程，从而描述服务的具体 执行过程。这种描述是基于过程(Process)的概念来实现的，如图2所示。
过程分为三类：原子过程(Atomic Process)、组合过程(Composite Process) 和简单过程(Simple Process)。分别解释如下：
（1）原子过程：原子过程是不可再分的过程，对应一个可以被直接调 用的Web服务，其内部执行是透明的。每个原子过程都必须关联一个 Grounding文件，提调用该原子过程的必要信息。
（2）组合过程：组合过程由若干原子过程或其它组合过程复合构成， 构件之间通过控制结构连接起来。OWL-S定义了8种控制结构：Sequence、 Split、Split+Join、Unordered、Choice、If-Then-Else、Iterate、Repeat-Until。
（3）简单过程：简单过程是一个抽象概念，不能被直接调用，因此不 需要也不能与Grounding文件绑定。简单过程不描述服务的内部细节，而只 关心服务的输入和输出信息，是一种从外部视角观察服务的方式。原子过程 是对简单过程的实现(Realizes)，而组合过程则可以通过折叠(CollapseTo)成 为简单过程。
服务的接口通过IOPEs来描述，分别是服务的输入和输出信息，服务 的执行前提条件和执行后的效果。前者是从数据变换的角度、后者是从状态 改变的角度来分别描述服务。Service Model主要用于支持服务的组合与验 证。
3.Service Grounding
Service Grounding描述服务的调用信息和规范，包括访问服务的协议、消 息格式、端口等信息。OWL-S并没有单独定义描述调用信息的语法，而是引 入了已经成熟和完善的WSDL规范。OWL-S与WSDL之间存在两个部分的映 射关系：
OWL-S中的原子过程映射到WSDL中的操作(Operation)。
OWL-S中的输入和输出信息映射到WSDL中的消息(Message)。 其中，Service Grounding支持服务的实际运行，与验证工作无关。
在OWL-S所描述的各类语义要素中，与服务组合验证相关的包括：服务 的输入(Input)、输出(Output)、执行前提(Preconditon)、执行效果(Effect)、控 制结构、服务质量信息。其中，IOPEs与控制结构用于进行功能性验证，即服 务是否能够正确性执行，并满足预期的功能性需求；而服务质量信息则是用 于非功能性验证，即服务的质量是否达到了预期要求。已有的技术方案实现 的都是功能性的验证。
映射转换分为三个部分：
（1）一个变迁对应一个原子服务。
（2）用一个变迁的前置库所中，不同颜色的令牌及令牌的数量来表示服 务的输入与执行前提；后置库所中的令牌表示输出；前置与后置库所的令牌 数量的变化表示执行效果。
（3）通过组合原子服务的Petri网模型来表示控制结构。
验证方法：利用Petri网模型的各类矩阵及相应的算法，可判定组合服务 能否正常运行，以及能否到达到预期的目标。
上述的现有技术方案存在以下缺点：
（1）只能够描述先输入后输出的两类消息传输模式，而不能描述另外先 输出后输入的另两类消息传输模式。
（2）没有系统给出将执行前提转化为有色令牌的方法。
（3）所描述的执行效果只涉及消息数量的变化，对于其它类型的执行效 果(例如对环境的改变)则无法描述。
（4）验证过程需要人工参与，容易引入新的错误。
（5）组合运算的对象都是原子服务，而没有给出对内部具有多个控制结 构的复合服务进行组合的方法。
（6）没有对组合服务运行所需的良好性质进行分析，只是简单地归结到 其所用技术的安全性或活性分析上，不仅其合理性值得商榷，也无法根据实 际需求设定安全性的强度，增大了服务组合的难度。
发明内容
本发明要解决的技术问题，在于提供一种语义Web服务组合的自动验证 方法及其系统，对OWL-S中的原子过程与组合过程的描述更具体完整，并保 持了两者的形式一致，可以无差异地参加组合运算，支持逻辑公式和表达式， 描述能力更强，尤其是对执行前提、执行效果与组合服务性质的描述，并且 验证过程自动化，不仅降低了验证技术的应用门槛，也能够避免在验证过程 中引入新的错误。
本发明方案一是这样实现的：一种语义Web服务组合的自动验证方法， 包括如下步骤：
步骤10、将OWL-S描述的Web服务即原子过程转化为一台原子过程 自动机，然后根据不同的控制结构，将原子过程自动机组合为组合过程自动 机；
步骤20、消除组合过程自动机的冗余并发和同步迁移，获得优化模型；
步骤30、依据用户限定的相容性要求，确定组合过程自动机的可接受 位置集合；
步骤40、依据用户限定的有效性要求，确定有效的逻辑公式CSV；
步骤50、将所述获得优化模型转换为UPPAAL的建模语言；
步骤60、将可接受位置集合和逻辑公式CSV表示为CTL公式；
步骤70、将建模语言描述的组合服务模型与CTL公式输入UPPAAL 进行验证；若验证结果为完全相容且有效，则该组合服务满足用户需求；若 验证结果为部分相容且有效，则可根据验证结果生成信息交互引擎，引导组 合服务的运行轨迹，达到用户要求；若验证结果是不满足相容且有效，则该 组合服务无法满足用户需求。
进一步地，所述步骤10进一步具体为：
步骤11，若控制结构为Sequence控制结构，则进行Sequence组合运算， 即将所有的所述原子过程自动机按照排列的先后顺序依次将前一个原子过 程自动机的终止位置连接后一个原子过程自动机的起始位置转化为组合过 程自动机；
步骤12，若控制结构为AnyOrder控制结构，则进行AnyOrder组合运 算，即构造一组逻辑公式初始时的值为true，其中表示将第1到第n个逻辑公式合取，与不含相同命题 变元，之后将所有原子过程自动机的起始位置合并为一个新的起始位置ls， 从原起始位置出发的迁移都改为从新起始位置出发，并且迁移标号的Pre 部分并入一个从所有原终止位置引出一条到达ls的迁移，该迁移使得假，从而保证该组合过程不会被重复执行；增加一个新的位置le并作为终止 位置，同时增加一个从ls到le的单步迁移e，其执行前提是公式为真，只 有当所有的组合过程都被执行完后，才能到达le；
步骤13，若控制结构为Choice控制结构，则进行Choice组合运算，即 将所有组合过程的起始位置合并为一个新的起始位置ls1，之后将所有组合 过程的终止位置合并为一个新的终止位置le1；
步骤14，若控制结构为If-then-Else控制结构，则进行If-then-Else组合 运算，即将选择条件表示成逻辑公式而后将所有组合过程的起始位置 合并为一个新的起始位置ls2，从原起始位置出发的迁移改为从新起始位置 出发，并用和修改迁移标号的Pre部分，最后将所有组合过程的终 止位置合并为一个新的终止位置le2；
步骤15，若控制结构为Repeat-Until控制结构，则进行Repeat-Until组 合运算，即将终止条件用逻辑公式表示，之后修改从起始位置出发的迁 移，将并入迁移标号的Pre部分，使该组合过程只有在终止条件为假时 可进行，增加一个新的位置le3作为终止位置，并从起始位置引出一个新的 单步迁移e3到达le3，其执行前提是表示终止条件的逻辑公式为真；
步骤16，若控制结构为Repeat-while控制结构，则进行Repeat-while组 合运算，即将终止条件用逻辑公式表示，修改从起始位置出发的迁移， 将并入迁移标号的Pre部分，使该组合过程只有在终止条件为假时可进 行，增加一个新的位置le4作为终止位置，并从起始位置引出一个新的单步 迁移e4到达le4，其执行前提是表示终止条件的逻辑公式为真；
步骤17，若控制结构为Split-Join控制结构，则进行Split-Join组合运算， 即将并发条件和汇合条件分别表示为逻辑公式和增加一个新的位置 ls5并作为起始位置，从它引出一个并发迁移到达所有组合过程的起始位置， 其执行前提为并发条件增加一个新的位置le5并作为终止位置，从所有 组合过程的终止位置引出一个到达le5的同步迁移，其执行前提为同步条件
进一步地，所述Sequence组合运算、所述AnyOrder组合运算、所述 Choice组合运算及所述If-then-Else组合运算为因果约束，所述Repeat-Unti 组合运算及所述Repeat-while组合运算为重复约束，所述Split-Join组合运 算为分支约束，所述因果约束、所述重复约束及所述分支约束为组合约束。
进一步地，所述步骤30进一步具体为：
步骤31，第一可接受位置集合WFL：其中原子服务的WFL为其起始位 置和终止位置为该原子服务的第一可接受位置，对n台组合过程自动机 CPAi，进行组合运算后得到的新组合过程自动机CPA，其第一可接受位置集 合WFL为各CPAi的第一可接受位置集合WFLi的并集，并且从WFL中移除 组合过程中被剔除的位置，若组合过程中增加了新的位置，且该位置为起始 位置或终止位置，则应添加到WFL中；
步骤32，组合过程自动机CPAi的第一可接受位置为WFLi，当在组合过 程中出现组合约束时，获得的可接受位置组成第二可接受位置集合：
对n台组合过程自动机CPAi进行Sequence组合运算得到新的组合过程 自动机CPASeq，若出现组合约束语义：若CPAi执行则CPAj也必须执行，其 中i<j，则普通可接受位置集合OFLSeq为CPA1～CPAi-1，及CPAj+1～CPAn的 第一可接受位置的并集，再加上CPAi的起始位置sLoci和CPAj的终止位置 eLocj；
或者对n台组合过程自动机CPAi进行AnyOrder组合运算得到新的组合 过程自动机CPAAO，若出现组合约束语义：组合服务的运行不能停止在CPAj， 则普通可接受位置集合OFLAO是在其第一可接受位置集合WFLAO的基础上， 去除CPAj的第一可接受位置集合WFLj，即OFLAO=WFLAO-WFLj；
或者对于n台组合过程自动机CPAi进行Choice组合运算得到新的组合 过程自动机CPACho，若出现组合约束语义：若CPAj被选中执行则必须执行 完成，则普通可接受位置集合OFLCho是在其第一可接受位置集合WFLCho基础上，去除CPAj的第一可接受位置集合WFLj，即OFLCho=WFLCho-WFLj；
或者对于两台组合过程自动机CPA1和CPA2进行If-then-Else组合运算 得到新的组合过程CPAItE，若出现组合约束语义：若CPAj被选中执行则必 须执行完成，则普通可接受位置集合OFLItE是在其第一可接受位置集合 WFLItE中去除CPAj的第一可接受位置集合WFLj，即OFLItE=WFLAO-WFLj；
或者对于组合过程自动机CPA进行Repeat-Until组合运算得到新组合过 程自动机CPARU，若出现组合约束语义：CPA必须重复执行直到终止条件成 立，则普通可接受位置集合OFLRU={le}，即只有终止位置可接受；
或者对于组合过程自动机CPA进行Repeat-while组合运算得到新组合过 程自动机CPARW，若出现组合约束语义：CPA必须重复执行直到循环条件不 成立，则普通可接受位置集合OFLRW={le}，即只有终止位置可接受；
或者对于n台组合过程自动机CPAi进行Split-Join组合运算得到新的组 合过程自动机CPASJ，若出现组合约束语义：分支组件CPAj必须执行完成， 则普通可接受位置集合OFLSJ是在其第一可接受位置集合WFLSJ的基础上， 去除CPAj的第一可接受位置集合WFLj，即OFLSJ=WFLSJ-WFLj；
当组合过程中不存在组合约束语义时，第二可接受位置集合即等于第一 可接受位置集合；
步骤33，组合过程自动机的第三可接受位置集合为SFL为组合过程自 动机的起始位置和终止位置，或者是组合过程自动机的终止位置。
进一步地，所述相容性为：
若组合服务由n台组合过程自动机组成，si为第i台组合过程自动机的 位置集合，则组合服务的全局状态向量gsv=(s1,s2,...,sn)，若有全局状态向 量gsv=(s1,s2,...,sn)和gsv′=(s1′,s2′,...,sn′)，其中一台组合过程自动机发生 迁移，使得gsv中的某个si变化为gsv′中的si′，而其它的sj保持即则称gsv发生迁移到达gsv′，记为gsv→gsv′；对于全局状态向量gsv： 若满足则称gsv为起始全局状态向量，记为gsv0；若 不存在gsv′，使得gsv→gsv′成立，则称gsv为终止全局状态向量，记为gsve；
将组合服务从起始全局状态向量开始的一系列迁移称为组合服务的一 次运行：gsv0→gsv1→gsv2→...→gsv，简记为gsv0[→]tr gsv，对于组合服 务的一次运行gsv0[→]tr gsv：若则称该次运行满足弱 相容性，记为WC(gsv0[→]tr gsv)；若则称该次运行满 足普通/自定义相容性，记为OC(gsv0[→]tr gsv)；若则 称该次运行满足强相容性，记为SC(gsv0[→]tr gsv)；将gsv0[→]tr gsve称为组 合服务的一次完整运行；
一个组合服务CS是完全强/普通/弱相容的，当且仅当任意gsv0[→]tr gsve都是强/普通/弱相容的；一个组合服务CS是部分强/普通/弱相容的，当且仅 当至少存在一个gsv0[→]tr gsve是强/普通/弱相容的。
进一步地，所述步骤20进一步具体为：
步骤21，若对于一个并发迁移e(l,slt)=tL={l1,...,ln}，其源位置l属于另 一个并发迁移e′(l′,slt′)=tL′={l1′,...,ln′}的目标位置集合，且两个并发迁移的 并发条件相同，同时不存在以l为源位置或目标位置的单步迁移，则l是冗余位 置，econ(l,slt)=tL={l1,...,ln}为冗余并发迁移，此时将冗余并发迁移e(l,slt) 的目标位置集合tL并入另一并发迁移e′(l′,slt′)的目标位置集合tL′，同时移除冗 余位置l和冗余并发迁移e(l,slt)；否则位置l不是冗余位置，并发迁移e(l,slt)不 是冗余并发迁移；
步骤22，若对于一个同步迁移e(sL={l1,...,ln},jn)=l，其目标位置l 属于另一个同步迁移e′(sL′={l1′,...,ln′},jn′)=l′的源位置集合，且两个同步 迁移的同步条件相同，同时不存在以l为源位置或目标位置的单步迁移，则 l是冗余位置，e(sL={l1,...,ln},jn)=l为冗余并发迁；此时将冗余同步迁移 e(sL={l1,...,ln},jn)的源位置集合sL并入另一同步迁移e′(sL′={l1′,...,ln′}, jn)的源位置集合sL′，同时移除冗余位置l和冗余同步迁移e(sL={l1,...,ln}, jn)；否则位置l不是冗余位置，并发迁移e(l,slt)不是冗余并发迁移。
进一步地，所述步骤50进一步具体为：
步骤51，组合过程自动机CPA中的单步迁移esin(l,a)=l'直接转换为一 台符合UPPAAL语法的时间自动机UTA的迁移离散迁移迁移标号a=(In,Out,Pre,Eft)转换为a'，其中g是由时钟变量表示的 约束条件，r是需要被重置为0的时钟变量集合；
步骤52，CPA中的并发迁移esin(l,jlt)={l1,...,ln}转换为n台UTA和一 个迁移其中：当UTA处于sli位置时，说明它进 入了并发执行的分支；a包含并发条件及一个广播通道的发射动作conChni!；
步骤53，而与并发迁移对应的同步迁移esin({l1,...,ln},jn)=l'，则转换 为迁移b中包含广播通道的发射动作synChni!， 使得多个分支能在同一时刻终结，同时，为了保证同步迁移在所有分支都执 行各自的操作后才能发生，增加一个同步变量synVari，初值为0，并将“synVari==n”并入迁移标号b的Guard部分，其中n为分支数量，每个分支执行所 有操作后都使其值加1；
步骤54，新创建的n台UTAi是用于述n个并发执行的分支，在首尾各 增加一个新的位置bl和el，当UTAi处于bl时，说明还没有进入该分支；当 UTAi处于el时，说明该分支已执行完毕；bl到对应分支的第一个状态的迁 移标号包含广播通道的接收动作conChni?；而对应分支的最后一个状态到达 el的迁移标号包含表达式synChni?；每个分支的最后一个迁移标号的Update 部分，增加一个表达式synVari++，使同步变量的值加1。
进一步地，所述步骤51进一步具体为：
组合过程自动机CPA中的单步迁移esin(l,a)=l'直接转换为一台符合 UPPAAL语法的时间自动机UTA的迁移离散迁移迁移标号其中，Guard是一个逻辑表达式，表 示迁移执行的条件；Sync是一组通道的发射或接受动作，用于实现同步迁 移；Update是一组表达式或用户函数，用于表达迁移的效果；语义信息缓 冲区SIB=(SI,V,f)，SI是语义信息集合，V是整型变量集合，映射f:SI→V， f是双射的；迁移标号被扩展为一个四元组(In,Out,Pre,Eft)，其中Pre和Eft 表示执行前提和执行效果，逻辑公式和表达式组成，直接并入到建模语言迁 移标号的Guard和Update的部分；In是输入信息的集合，将其表示为：一 个合取公式∧f(ci)并且并入迁移标号的Guard部分，合取项的数量与In的元 素数量相等，其中f是信息缓冲区中的映射，ci∈In；将其表示为一组表达 式{f(ci)--|ci∈In}，并且并入迁移标号的Update部分；Out是输入信息的集 合，将其表示为一组表达式{f(ci)++|ci∈Out}}并且并入迁移标号的Update 部分。
进一步地，所述有效性逻辑公式CSV=(INFOS,EFFECTS)，其中：INFOS为一组要求组合服务产生的语义信息集合；EFFECTS为一组逻辑公式，该 逻辑公式描述要求组合服务必须达到的限定效果。
进一步地，所述步骤60进一步具体为：
相容性变量cptyVari∈{unconcerned,incompatible,weak,ordinary,strong}， 表示UTAi当前的相容性：unconcerned表示该UPAi所描述的并行分支还未 被激活或已经结束，incompatible表示不相容，weak表示弱相容，ordinary 表示普通/自定义相容，strong表示强相容，可以用取值范围为[0,3]的整型 变量来表示相容性变量，数值0～4依次代表incompatible、weak、ordinary、 strong、unconcerned，三种相容性在UPPAAL中可描述为：
当组合服务完成一次完整运行后没有迁移再发生，组合服务进入死锁状 态，在UPPAAL中以deadlock关键字表示，故可将完全/部分相容性表示为 CTL公式F1，如下：
n∈{1,2,3}；
n∈{1,2,3}，其中cptyVari为 相容性变量；
对于有效性CSV=(INFOS,EFFECTS)，完全/部分有效且强/普通/弱相容 表示为CTL公式F2，如下：
进一步地，所述信息交互引擎为一台信息交互引擎 IEE=<excFac1,excFac2,...,excFacn>，excFaci=(type,obj,{ci})称为是一个交 互因子，其中：type∈{!,?}，表示交互的类型，“!”表示由IEE向Service 发送信息，“?”表示由IEE接收Service发送的信息；obj∈{Servicei}称为 交互对象是一个组件服务；{ci}是交互的信息集合。
本发明方案二是这样实现的：一种语义Web服务组合的自动验证系统， 包括如下模块：
原子过程转换模块，将OWL-S描述的Web服务即原子过程转化为一台 原子过程自动机，然后根据不同的控制结构，将原子过程自动机组合为组合 过程自动机；
优化模型模块，消除组合过程自动机的冗余并发和同步迁移，获得优化 模型；
可接受位置集合模块，依据用户限定的相容性要求，确定组合过程自动 机的可接受位置集合；
逻辑公式模块，依据用户限定的有效性要求，确定有效的逻辑公式CSV；
转换建模语言模块，将所述获得优化模型转换为UPPAAL的建模语言；
CTL模块，将可接受位置集合和逻辑公式CSV表示为CTL公式；
验证模块，将建模语言描述的组合服务模型与CTL公式输入UPPAAL 进行验证；若验证结果为完全相容且有效，则该组合服务满足用户需求；若 验证结果为部分相容且有效，则可根据验证结果生成信息交互引擎，引导组 合服务的运行轨迹，达到用户要求；若验证结果是不满足相容且有效，则该 组合服务无法满足用户需求。
进一步地，所述原子过程转换模块进一步具体为：
Sequence组合运算单元，若控制结构为Sequence控制结构，则进行 Sequence组合运算，即将所有的所述原子过程自动机按照排列的先后顺序 依次将前一个原子过程自动机的终止位置连接后一个原子过程自动机的起 始位置转化为组合过程自动机；
AnyOrder组合运算单元，若控制结构为AnyOrder控制结构，则进行 AnyOrder组合运算，即构造一组逻辑公式初始时的值为 true，其中表示将第1到第n个逻辑公式合取，与 不含相同命题变元，之后将所有原子过程自动机的起始位置合并为一个新 的起始位置ls，从原起始位置出发的迁移都改为从新起始位置出发，并且迁 移标号的Pre部分并入一个从所有原终止位置引出一条到达ls的迁移， 该迁移使得假，从而保证该组合过程不会被重复执行；增加一个新的位 置le并作为终止位置，同时增加一个从ls到le的单步迁移e，其执行前提是 公式为真，只有当所有的组合过程都被执行完后，才能到达le；
Choice组合运算单元，若控制结构为Choice控制结构，则进行Choice 组合运算，即将所有组合过程的起始位置合并为一个新的起始位置ls1，之 后将所有组合过程的终止位置合并为一个新的终止位置le1；
If-then-Else组合运算单元，若控制结构为If-then-Else控制结构，则进 行If-then-Else组合运算，即将选择条件表示成逻辑公式而后将所有组 合过程的起始位置合并为一个新的起始位置ls2，从原起始位置出发的迁移 改为从新起始位置出发，并用和修改迁移标号的Pre部分，最后将 所有组合过程的终止位置合并为一个新的终止位置le2；
Repeat-Until组合运算单元，若控制结构为Repeat-Until控制结构，则 进行Repeat-Until组合运算，即将终止条件用逻辑公式表示，之后修改 从起始位置出发的迁移，将并入迁移标号的Pre部分，使该组合过程只 有在终止条件为假时可进行，增加一个新的位置le3作为终止位置，并从起 始位置引出一个新的单步迁移e3到达le3，其执行前提是表示终止条件的逻 辑公式为真；
Repeat-while组合运算单元，若控制结构为Repeat-while控制结构，则 进行Repeat-while组合运算，即将终止条件用逻辑公式表示，修改从起 始位置出发的迁移，将并入迁移标号的Pre部分，使该组合过程只有在 终止条件为假时可进行，增加一个新的位置le4作为终止位置，并从起始位 置引出一个新的单步迁移e4到达le4，其执行前提是表示终止条件的逻辑公 式为真；
Split-Join组合运算单元，若控制结构为Split-Join控制结构，则进行 Split-Join组合运算，即将并发条件和汇合条件分别表示为逻辑公式和增加一个新的位置ls5并作为起始位置，从它引出一个并发迁移到达所有组 合过程的起始位置，其执行前提为并发条件增加一个新的位置le5并作 为终止位置，从所有组合过程的终止位置引出一个到达le5的同步迁移，其 执行前提为同步条件
进一步地，所述Sequence组合运算、所述AnyOrder组合运算、所述 Choice组合运算及所述If-then-Else组合运算为因果约束，所述Repeat-Unti 组合运算及所述Repeat-while组合运算为重复约束，所述Split-Join组合运 算为分支约束，所述因果约束、所述重复约束及所述分支约束为组合约束。
进一步地，所述可接受位置集合模块进一步具体为：
第一可接受位置集合单元，第一可接受位置集合WFL：其中原子服务 的WFL为其起始位置和终止位置为该原子服务的第一可接受位置，对n台 组合过程自动机CPAi，进行组合运算后得到的新组合过程自动机CPA，其 第一可接受位置集合WFL为各CPAi的第一可接受位置集合WFLi的并集， 并且从WFL中移除组合过程中被剔除的位置，若组合过程中增加了新的位 置，且该位置为起始位置或终止位置，则应添加到WFL中；
第二可接受位置集合单元，组合过程自动机CPAi的第一可接受位置为 WFLi，当在组合过程中出现组合约束时，获得的可接受位置组成第二可接 受位置集合：
对n台组合过程自动机CPAi进行Sequence组合运算得到新的组合过程 自动机CPASeq，若出现组合约束语义：若CPAi执行则CPAj也必须执行，其 中i<j，则普通可接受位置集合OFLSeq为CPA1～CPAi-1，及CPAj+1～CPAn的 第一可接受位置的并集，再加上CPAi的起始位置sLoci和CPAj的终止位置 eLocj；
或者对n台组合过程自动机CPAi进行AnyOrder组合运算得到新的组合 过程自动机CPAAO，若出现组合约束语义：组合服务的运行不能停止在CPAj， 则普通可接受位置集合OFLAO是在其第一可接受位置集合WFLAO的基础上， 去除CPAj的第一可接受位置集合WFLj，即OFLAO=WFLAO-WFLj；
或者对于n台组合过程自动机CPAi进行Choice组合运算得到新的组合 过程自动机CPACho，若出现组合约束语义：若CPAj被选中执行则必须执行 完成，则普通可接受位置集合OFLCho是在其第一可接受位置集合WFLCho基础上，去除CPAj的第一可接受位置集合WFLj，即OFLCho=WFLCho-WFLj；
或者对于两台组合过程自动机CPA1和CPA2进行If-then-Else组合运算 得到新的组合过程CPAItE，若出现组合约束语义：若CPAj被选中执行则必 须执行完成，则普通可接受位置集合OFLItE是在其第一可接受位置集合 WFLItE中去除CPAj的第一可接受位置集合WFLj，即OFLItE=WFLAO-WFLj；
或者对于组合过程自动机CPA进行Repeat-Until组合运算得到新组合过 程自动机CPARU，若出现组合约束语义：CPA必须重复执行直到终止条件成 立，则普通可接受位置集合OFLRU={le}，即只有终止位置可接受；
或者对于组合过程自动机CPA进行Repeat-while组合运算得到新组合过 程自动机CPARW，若出现组合约束语义：CPA必须重复执行直到循环条件不 成立，则普通可接受位置集合OFLRW={le}，即只有终止位置可接受；
或者对于n台组合过程自动机CPAi进行Split-Join组合运算得到新的组 合过程自动机CPASJ，若出现组合约束语义：分支组件CPAj必须执行完成， 则普通可接受位置集合OFLSJ是在其第一可接受位置集合WFLSJ的基础上， 去除CPAj的第一可接受位置集合WFLj，即OFLSJ=WFLSJ-WFLj；
当组合过程中不存在组合约束语义时，第二可接受位置集合即等于第一 可接受位置集合；
第三可接受位置集合单元，组合过程自动机的第三可接受位置集合为 SFL为组合过程自动机的起始位置和终止位置，或者是组合过程自动机的终 止位置。
进一步地，所述相容性为：
若组合服务由n台组合过程自动机组成，si为第i台组合过程自动机的 位置集合，则组合服务的全局状态向量gsv=(s1,s2,...,sn)，若有全局状态向 量gsv=(s1,s2,...,sn)和gsv′=(s1′,s2′,...,sn′)，其中一台组合过程自动机发生 迁移，使得gsv中的某个si变化为gsv′中的si′，而其它的sj保持即则称gsv发生迁移到达gsv′，记为gsv→gsv′；对于全局状态向量gsv： 若满足则称gsv为起始全局状态向量，记为gsv0；若 不存在gsv′，使得gsv→gsv′成立，则称gsv为终止全局状态向量，记为gsve；
将组合服务从起始全局状态向量开始的一系列迁移称为组合服务的一 次运行：gsv0→gsv1→gsv2→...→gsv，简记为gsv0[→]tr gsv，对于组合服 务的一次运行gsv0[→]tr gsv：若则称该次运行满足弱 相容性，记为WC(gsv0[→]tr gsv)；若则称该次运行满 足普通/自定义相容性，记为OC(gsv0[→]tr gsv)；若则 称该次运行满足强相容性，记为SC(gsv0[→]tr gsv)；将gsv0[→]tr gsve称为组 合服务的一次完整运行；
一个组合服务CS是完全强/普通/弱相容的，当且仅当任意gsv0[→]tr gsve都是强/普通/弱相容的；一个组合服务CS是部分强/普通/弱相容的，当且仅 当至少存在一个gsv0[→]tr gsve是强/普通/弱相容的。
进一步地，所述优化模型模块进一步具体为：
并发迁移优化单元，若对于一个并发迁移e(l,slt)=tL={l1,...,ln}，其源 位置l属于另一个并发迁移e′(l′,slt′)=tL′={l1′,...,ln′}的目标位置集合，且两 个并发迁移的并发条件相同，同时不存在以l为源位置或目标位置的单步迁 移，则l是冗余位置，econ(l,slt)=tL={l1,...,ln}为冗余并发迁移，此时将冗余 并发迁移e(l,slt)的目标位置集合tL并入另一并发迁移e′(l′,slt′)的目标位置集 合tL′，同时移除冗余位置l和冗余并发迁移e(l,slt)；否则位置l不是冗余位置， 并发迁移e(l,slt)不是冗余并发迁移；
同步迁移优化单元，若对于一个同步迁移e(sL={l1,...,ln},jn)=l，其 目标位置l属于另一个同步迁移e′(sL′={l1′,...,ln′},jn′)=l′的源位置集合， 且两个同步迁移的同步条件相同，同时不存在以l为源位置或目标位置的单 步迁移，则l是冗余位置，e(sL={l1,...,ln},jn)=l为冗余并发迁；此时将冗 余同步迁移e(sL={l1,...,ln},jn)的源位置集合sL并入另一同步迁移e′(sL′= {l1′,...,ln′},jn)的源位置集合sL′，同时移除冗余位置l和冗余同步迁移e(sL= {l1,...,ln},jn)；否则位置l不是冗余位置，并发迁移e(l,slt)不是冗余并发迁 移。
进一步地，所述转换建模语言模块进一步具体为：
单步迁移转换单元，组合过程自动机CPA中的单步迁移esin(l,a)=l'直 接转换为一台符合UPPAAL语法的时间自动机UTA的迁移离散迁移迁移标号a=(In,Out,Pre,Eft)转换为a'，其中g是由时钟 变量表示的约束条件，r是需要被重置为0的时钟变量集合；
并发迁移转换单元，CPA中的并发迁移esin(l,jlt)={l1,...,ln}转换为n 台UTA和一个迁移其中：当UTA处于sli位置时， 说明它进入了并发执行的分支；a包含并发条件及一个广播通道的发射动 作conChni!；
同步迁移转换单元，与并发迁移对应的同步迁移esin({l1,...,ln},jn)=l'， 则转换为迁移b中包含广播通道的发射动作 synChni!，使得多个分支能在同一时刻终结，同时，为了保证同步迁移在所 有分支都执行各自的操作后才能发生，增加一个同步变量synVari，初值为0， 并将“synVari==n”并入迁移标号b的Guard部分，其中n为分支数量， 每个分支执行所有操作后都使其值加1；
分支过程单元，新创建的n台UTAi是用于述n个并发执行的分支，在 首尾各增加一个新的位置bl和el，当UTAi处于bl时，说明还没有进入该分 支；当UTAi处于el时，说明该分支已执行完毕；bl到对应分支的第一个状 态的迁移标号包含广播通道的接收动作conChni?；而对应分支的最后一个状 态到达el的迁移标号包含表达式synChni?；每个分支的最后一个迁移标号 的Update部分，增加一个表达式synVari++，使同步变量的值加1。
进一步地，所述单步迁移转换单元进一步具体为：
组合过程自动机CPA中的单步迁移esin(l,a)=l'直接转换为一台符合 UPPAAL语法的时间自动机UTA的迁移离散迁移迁移标号其中，Guard是一个逻辑表达式，表 示迁移执行的条件；Sync是一组通道的发射或接受动作，用于实现同步迁 移；Update是一组表达式或用户函数，用于表达迁移的效果；语义信息缓 冲区SIB=(SI,V,f)，SI是语义信息集合，V是整型变量集合，映射f:SI→V， f是双射的；迁移标号被扩展为一个四元组(In,Out,Pre,Eft)，其中Pre和Eft 表示执行前提和执行效果，逻辑公式和表达式组成，直接并入到建模语言迁 移标号的Guard和Update的部分；In是输入信息的集合，将其表示为：一 个合取公式∧f(ci)并且并入迁移标号的Guard部分，合取项的数量与In的元 素数量相等，其中f是信息缓冲区中的映射，ci∈In；将其表示为一组表达 式{f(ci)--|ci∈In}，并且并入迁移标号的Update部分；Out是输入信息的集 合，将其表示为一组表达式{f(ci)++|ci∈Out}}并且并入迁移标号的Update 部分。
进一步地，所述有效性逻辑公式CSV=(INFOS,EFFECTS)，其中：INFOS为一组要求组合服务产生的语义信息集合；EFFECTS为一组逻辑公式，该 逻辑公式描述要求组合服务必须达到的限定效果。
进一步地，所述CTL模块进一步具体为：
相容性变量cptyVari∈{unconcerned,incompatible,weak,ordinary,strong}， 表示UTAi当前的相容性：unconcerned表示该UPAi所描述的并行分支还未 被激活或已经结束，incompatible表示不相容，weak表示弱相容，ordinary 表示普通/自定义相容，strong表示强相容，可以用取值范围为[0,3]的整型 变量来表示相容性变量，数值0～4依次代表incompatible、weak、ordinary、 strong、unconcerned，三种相容性在UPPAAL中可描述为：
当组合服务完成一次完整运行后没有迁移再发生，组合服务进入死锁状 态，在UPPAAL中以deadlock关键字表示，故将完全/部分相容性表示为 CTL公式F1，如下：
n∈{1,2,3}；
n∈{1,2,3}，其中cptyVari为 相容性变量；
对于有效性CSV=(INFOS,EFFECTS)，完全/部分有效且强/普通/弱相容 表示为CTL公式F2，如下：
进一步地，所述信息交互引擎为一台信息交互引擎 IEE=<excFac1,excFac2,...,excFacn>，excFaci=(type,obj,{ci})称为是一个交 互因子，其中：type∈{!,?}，表示交互的类型，“!”表示由IEE向Service 发送信息，“?”表示由IEE接收Service发送的信息；obj∈{Servicei}称为 交互对象是一个组件服务；{ci}是交互的信息集合。
本发明具有如下优点：对OWL-S中的原子过程与组合过程的描述更具 体完整，并保持了两者的形式一致，可以无差异地参加组合运算，支持逻辑 公式和表达式，描述能力更强，尤其是对执行前提、执行效果与组合服务性 质的描述；通过验证过程自动化，不仅降低了验证技术的应用门槛，也能够 避免在验证过程中引入新的错误；将有效性与相容性相结合，对组合服务的 验证更全面；划分了相容性的强度等级，可避免因过强的相容性要求，而造 成一些可用的组合服务被排除，其验证结果可用于错误定位，或引导组合服 务正确执行，所使用的验证技术与工具在空间表示与维持上具有显著的优 势，能够通过增加时钟、迁移概率等要素进行扩展，并且都有相应的模型检 测工具支持。
附图说明
下面参照附图结合实施例对本发明作进一步的说明。
图1为OWL-S的顶层本体视图。
图2为Process的结构视图。
图3为本发明系统原理框图。
图4为本发明方法执行流程图。
图5a为原子过程自动机示意一图。
图5b为原子过程自动机示意二图。
图5c为原子过程自动机示意三图。
图5d为原子过程自动机示意四图。
图6为原子过程自动机示意五图。
图7为sequence组合运算示意图。
图8为AnyOrder组合运算示意图。
图9为Choice组合运算示意图。
图10为If-Then-Else组合运算示意图。
图11为Repeat-Until组合运算示意图。
图12为Repeat-while组合运算示意图。
图13为Repeat-while组合运算示意图。
图14为冗余并发/同步迁移的产生示意图。
图15为优化后的组合过程自动机示意图。
图16为信息交互引擎示意图。
图17为并发/同步迁移转换示意图。
图18为本发明赋值规则示意图。
具体实施方式
如图4所示，一种语义Web服务组合的自动验证方法，其特征在于： 包括如下步骤：
步骤10、将OWL-S描述的Web服务即原子过程转化为一台原子过程 自动机，然后根据不同的控制结构，将原子过程自动机组合为组合过程自动 机：步骤11，若控制结构为Sequence控制结构，则进行Sequence组合运算， 即将所有的所述原子过程自动机按照排列的先后顺序依次将前一个原子过 程自动机的终止位置连接后一个原子过程自动机的起始位置转化为组合过 程自动机；
步骤12，若控制结构为AnyOrder控制结构，则进行AnyOrder组合运 算，即构造一组逻辑公式初始时的值为true，其中表示将第1到第n个逻辑公式合取，与不含相同命题 变元，之后将所有原子过程自动机的起始位置合并为一个新的起始位置ls， 从原起始位置出发的迁移都改为从新起始位置出发，并且迁移标号的Pre 部分并入一个从所有原终止位置引出一条到达ls的迁移，该迁移使得假，从而保证该组合过程不会被重复执行；增加一个新的位置le并作为终止 位置，同时增加一个从ls到le的单步迁移e，其执行前提是公式为真，只 有当所有的组合过程都被执行完后，才能到达le；
步骤13，若控制结构为Choice控制结构，则进行Choice组合运算，即 将所有组合过程的起始位置合并为一个新的起始位置ls1，之后将所有组合 过程的终止位置合并为一个新的终止位置le1；
步骤14，若控制结构为If-then-Else控制结构，则进行If-then-Else组合 运算，即将选择条件表示成逻辑公式而后将所有组合过程的起始位置 合并为一个新的起始位置ls2，从原起始位置出发的迁移改为从新起始位置 出发，并用和修改迁移标号的Pre部分，最后将所有组合过程的终 止位置合并为一个新的终止位置le2；
步骤15，若控制结构为Repeat-Until控制结构，则进行Repeat-Until组 合运算，即将终止条件用逻辑公式表示，之后修改从起始位置出发的迁 移，将并入迁移标号的Pre部分，使该组合过程只有在终止条件为假时 可进行，增加一个新的位置le3作为终止位置，并从起始位置引出一个新的 单步迁移e3到达le3，其执行前提是表示终止条件的逻辑公式为真；
步骤16，若控制结构为Repeat-while控制结构，则进行Repeat-while组 合运算，即将终止条件用逻辑公式表示，修改从起始位置出发的迁移， 将并入迁移标号的Pre部分，使该组合过程只有在终止条件为假时可进 行，增加一个新的位置le4作为终止位置，并从起始位置引出一个新的单步 迁移e4到达le4，其执行前提是表示终止条件的逻辑公式为真；
步骤17，若控制结构为Split-Join控制结构，则进行Split-Join组合运算， 即将并发条件和汇合条件分别表示为逻辑公式和增加一个新的位置 ls5并作为起始位置，从它引出一个并发迁移到达所有组合过程的起始位置， 其执行前提为并发条件增加一个新的位置le5并作为终止位置，从所有 组合过程的终止位置引出一个到达le5的同步迁移，其执行前提为同步条件 所述Sequence组合运算、所述AnyOrder组合运算、所述Choice组合 运算及所述If-then-Else组合运算为因果约束，所述Repeat-Unti组合运算及 所述Repeat-while组合运算为重复约束，所述Split-Join组合运算为分支约 束，所述因果约束、所述重复约束及所述分支约束为组合约束；
步骤20、消除组合过程自动机的冗余并发和同步迁移，获得优化模型： 步骤21，若对于一个并发迁移e(l,slt)=tL={l1,...,ln}，其源位置l属于另一个 并发迁移e′(l′,slt′)=tL′={l1′,...,ln′}的目标位置集合，且两个并发迁移的并发 条件相同，同时不存在以l为源位置或目标位置的单步迁移，则l是冗余位置， econ(l,slt)=tL={l1,...,ln}为冗余并发迁移，此时将冗余并发迁移e(l,slt)的目 标位置集合tL并入另一并发迁移e′(l′,slt′)的目标位置集合tL′，同时移除冗余位 置l和冗余并发迁移e(l,slt)；否则位置l不是冗余位置，并发迁移e(l,slt)不是冗 余并发迁移；
步骤22，若对于一个同步迁移e(sL={l1,...,ln},jn)=l，其目标位置l 属于另一个同步迁移e′(sL′={l1′,...,ln′},jn′)=l′的源位置集合，且两个同步 迁移的同步条件相同，同时不存在以l为源位置或目标位置的单步迁移，则 l是冗余位置，e(sL={l1,...,ln},jn)=l为冗余并发迁；此时将冗余同步迁移 e(sL={l1,...,ln},jn)的源位置集合sL并入另一同步迁移e′(sL′={l1′,...,ln′}, jn)的源位置集合sL′，同时移除冗余位置l和冗余同步迁移e(sL={l1,...,ln}, jn)；否则位置l不是冗余位置，并发迁移e(l,slt)不是冗余并发迁移；
步骤30、依据用户限定的相容性要求，确定组合过程自动机的可接受 位置集合：步骤31，第一可接受位置集合WFL：其中原子服务的WFL为 其起始位置和终止位置为该原子服务的第一可接受位置，对n台组合过程自 动机CPAi，进行组合运算后得到的新组合过程自动机CPA，其第一可接受 位置集合WFL为各CPAi的第一可接受位置集合WFLi的并集，并且从WFL 中移除组合过程中被剔除的位置，若组合过程中增加了新的位置，且该位置 为起始位置或终止位置，则应添加到WFL中；
步骤32，组合过程自动机CPAi的第一可接受位置为WFLi，当在组合过 程中出现组合约束时，获得的可接受位置组成第二可接受位置集合：
对n台组合过程自动机CPAi进行Sequence组合运算得到新的组合过程 自动机CPASeq，若出现组合约束语义：若CPAi执行则CPAj也必须执行，其 中i<j，则普通可接受位置集合OFLSeq为CPA1～CPAi-1，及CPAj+1～CPAn的 第一可接受位置的并集，再加上CPAi的起始位置sLoci和CPAj的终止位置 eLocj；
或者对n台组合过程自动机CPAi进行AnyOrder组合运算得到新的组合 过程自动机CPAAO，若出现组合约束语义：组合服务的运行不能停止在CPAj， 则普通可接受位置集合OFLAO是在其第一可接受位置集合WFLAO的基础上， 去除CPAj的第一可接受位置集合WFLj，即OFLAO=WFLAO-WFLj；
或者对于n台组合过程自动机CPAi进行Choice组合运算得到新的组合 过程自动机CPACho，若出现组合约束语义：若CPAj被选中执行则必须执行 完成，则普通可接受位置集合OFLCho是在其第一可接受位置集合WFLCho基础上，去除CPAj的第一可接受位置集合WFLj，即OFLCho=WFLCho-WFLj；
或者对于两台组合过程自动机CPA1和CPA2进行If-then-Else组合运算 得到新的组合过程CPAItE，若出现组合约束语义：若CPAj被选中执行则必 须执行完成，则普通可接受位置集合OFLItE是在其第一可接受位置集合 WFLItE中去除CPAj的第一可接受位置集合WFLj，即OFLItE=WFLAO-WFLj；
或者对于组合过程自动机CPA进行Repeat-Until组合运算得到新组合过 程自动机CPARU，若出现组合约束语义：CPA必须重复执行直到终止条件成 立，则普通可接受位置集合OFLRU={le}，即只有终止位置可接受；
或者对于组合过程自动机CPA进行Repeat-while组合运算得到新组合过 程自动机CPARW，若出现组合约束语义：CPA必须重复执行直到循环条件不 成立，则普通可接受位置集合OFLRW={le}，即只有终止位置可接受；
或者对于n台组合过程自动机CPAi进行Split-Join组合运算得到新的组 合过程自动机CPASJ，若出现组合约束语义：分支组件CPAj必须执行完成， 则普通可接受位置集合OFLSJ是在其第一可接受位置集合WFLSJ的基础上， 去除CPAj的第一可接受位置集合WFLj，即OFLSJ=WFLSJ-WFLj；
当组合过程中不存在组合约束语义时，第二可接受位置集合即等于第一 可接受位置集合；
步骤33，组合过程自动机的第三可接受位置集合为SFL为组合过程自 动机的起始位置和终止位置，或者是组合过程自动机的终止位置；
所述相容性为：若组合服务由n台组合过程自动机组成，si为第i台组 合过程自动机的位置集合，则组合服务的全局状态向量gsv=(s1,s2,...,sn)， 若有全局状态向量gsv=(s1,s2,...,sn)和gsv′=(s1′,s2′,...,sn′)，其中一台组合 过程自动机发生迁移，使得gsv中的某个si变化为gsv′中的si′，而其它的sj保持即则称gsv发生迁移到达gsv′，记为gsv→gsv′；对于全 局状态向量gsv：若满足则称gsv为起始全局状态向 量，记为gsv0；若不存在gsv′，使得gsv→gsv′成立，则称gsv为终止全局 状态向量，记为gsve；将组合服务从起始全局状态向量开始的一系列迁移称 为组合服务的一次运行：gsv0→gsv1→gsv2→...→gsv，简记为gsv0[→]trgsv，对于组合服务的一次运行gsv0[→]tr gsv：若则称 该次运行满足弱相容性，记为WC(gsv0[→]tr gsv)；若则称该次运行满足普通/自定义相容性，记为OC(gsv0[→]tr gsv)；若则称该次运行满足强相容性，记为SC(gsv0[→]tr gsv)；将gsv0[→]trgsve称为组合服务的一次完整运行；一个组合服务CS是完全强/普通/弱相容 的，当且仅当任意gsv0[→]tr gsve都是强/普通/弱相容的；一个组合服务CS 是部分强/普通/弱相容的，当且仅当至少存在一个gsv0[→]tr gsve是强/普通/ 弱相容的；
步骤40、依据用户限定的有效性要求，确定有效的逻辑公式CSV，所 述有效性逻辑公式CSV=(INFOS,EFFECTS)，其中：INFOS为一组要求组合 服务产生的语义信息集合；EFFECTS为一组逻辑公式，该逻辑公式描述要 求组合服务必须达到的限定效果；
步骤50、将所述获得优化模型转换为UPPAAL的建模语言：步骤51， 组合过程自动机CPA中的单步迁移esin(l,a)=l'直接转换为一台符合 UPPAAL语法的时间自动机UTA的迁移离散迁移迁移标号a=(In,Out,Pre,Eft)转换为a'，其中g是由时钟变量表示的约束条 件，r是需要被重置为0的时钟变量集合；
组合过程自动机CPA中的单步迁移esin(l,a)=l'直接转换为一台符合 UPPAAL语法的时间自动机UTA的迁移离散迁移迁移标号其中，Guard是一个逻辑表达式，表 示迁移执行的条件；Sync是一组通道的发射或接受动作，用于实现同步迁 移；Update是一组表达式或用户函数，用于表达迁移的效果；语义信息缓 冲区SIB=(SI,V,f)，SI是语义信息集合，V是整型变量集合，映射f:SI→V， f是双射的；迁移标号被扩展为一个四元组(In,Out,Pre,Eft)，其中Pre和Eft 表示执行前提和执行效果，逻辑公式和表达式组成，直接并入到建模语言迁 移标号的Guard和Update的部分；In是输入信息的集合，将其表示为：一 个合取公式∧f(ci)并且并入迁移标号的Guard部分，合取项的数量与In的元 素数量相等，其中f是信息缓冲区中的映射，ci∈In；将其表示为一组表达 式{f(ci)--|ci∈In}，并且并入迁移标号的Update部分；Out是输入信息的集 合，将其表示为一组表达式{f(ci)++|ci∈Out}}并且并入迁移标号的Update 部分；
步骤52，CPA中的并发迁移esin(l,jlt)={l1,...,ln}转换为n台UTA和一 个迁移其中：当UTA处于sli位置时，说明它进 入了并发执行的分支；a包含并发条件及一个广播通道的发射动作conChni!；
步骤53，而与并发迁移对应的同步迁移esin({l1,...,ln},jn)=l'，则转换 为迁移b中包含广播通道的发射动作synChni!， 使得多个分支能在同一时刻终结，同时，为了保证同步迁移在所有分支都执 行各自的操作后才能发生，增加一个同步变量synVari，初值为0，并将“synVari==n”并入迁移标号b的Guard部分，其中n为分支数量，每个分支执行所 有操作后都使其值加1；
步骤54，新创建的n台UTAi是用于述n个并发执行的分支，在首尾各 增加一个新的位置bl和el，当UTAi处于bl时，说明还没有进入该分支；当 UTAi处于el时，说明该分支已执行完毕；bl到对应分支的第一个状态的迁 移标号包含广播通道的接收动作conChni?；而对应分支的最后一个状态到达 el的迁移标号包含表达式synChni?；每个分支的最后一个迁移标号的Update 部分，增加一个表达式synVari++，使同步变量的值加1；
步骤60、将可接受位置集合和逻辑公式CSV表示为CTL公式；
相容性变量cptyVari∈{unconcerned,incompatible,weak,ordinary,strong}， 表示UTAi当前的相容性：unconcerned表示该UPAi所描述的并行分支还未 被激活或已经结束，incompatible表示不相容，weak表示弱相容，ordinary 表示普通/自定义相容，strong表示强相容，可以用取值范围为[0,3]的整型 变量来表示相容性变量，数值0～4依次代表incompatible、weak、ordinary、 strong、unconcerned，三种相容性在UPPAAL中可描述为：
当组合服务完成一次完整运行后没有迁移再发生，组合服务进入死锁状 态，在UPPAAL中以deadlock关键字表示，故可将完全/部分相容性表示为 CTL公式F1，如下：
n∈{1,2,3}；
n∈{1,2,3}，其中cptyVari为 相容性变量；
对于有效性CSV=(INFOS,EFFECTS)，完全/部分有效且强/普通/弱相 容，表示为CTL公式F2，如下：
步骤70、将建模语言描述的组合服务模型与CTL公式输入UPPAAL 进行验证；若验证结果为完全相容且有效，则该组合服务满足用户需求；若 验证结果为部分相容且有效，则可根据验证结果生成信息交互引擎，引导组 合服务的运行轨迹，达到用户要求；若验证结果是不满足相容且有效，则该 组合服务无法满足用户需求，所述信息交互引擎为一台信息交互引擎 IEE=<excFac1,excFac2,...,excFacn>，excFaci=(type,obj,{ci})称为是一个交 互因子，其中：type∈{!,?}，表示交互的类型，“!”表示由IEE向Service 发送信息，“?”表示由IEE接收Service发送的信息；obj∈{Servicei}称为交 互对象是一个组件服务；{ci}是交互的信息集合。
如图3所示，一种语义Web服务组合的自动验证系统，包括如下模块：
原子过程转换模块，将OWL-S描述的Web服务即原子过程转化为一台 原子过程自动机，然后根据不同的控制结构，将原子过程自动机组合为组合 过程自动机，所述原子过程转换模块进一步具体为：
Sequence组合运算单元，若控制结构为Sequence控制结构，则进行 Sequence组合运算，即将所有的所述原子过程自动机按照排列的先后顺序 依次将前一个原子过程自动机的终止位置连接后一个原子过程自动机的起 始位置转化为组合过程自动机；
AnyOrder组合运算单元，若控制结构为AnyOrder控制结构，则进行 AnyOrder组合运算，即构造一组逻辑公式初始时的值为 true，其中表示将第1到第n个逻辑公式合取，与 不含相同命题变元，之后将所有原子过程自动机的起始位置合并为一个新 的起始位置ls，从原起始位置出发的迁移都改为从新起始位置出发，并且迁 移标号的Pre部分并入一个从所有原终止位置引出一条到达ls的迁移， 该迁移使得假，从而保证该组合过程不会被重复执行；增加一个新的位 置le并作为终止位置，同时增加一个从ls到le的单步迁移e，其执行前提是 公式为真，只有当所有的组合过程都被执行完后，才能到达le；
Choice组合运算单元，若控制结构为Choice控制结构，则进行Choice 组合运算，即将所有组合过程的起始位置合并为一个新的起始位置ls1，之 后将所有组合过程的终止位置合并为一个新的终止位置le1；
If-then-Else组合运算单元，若控制结构为If-then-Else控制结构，则进 行If-then-Else组合运算，即将选择条件表示成逻辑公式而后将所有组 合过程的起始位置合并为一个新的起始位置ls2，从原起始位置出发的迁移 改为从新起始位置出发，并用和修改迁移标号的Pre部分，最后将 所有组合过程的终止位置合并为一个新的终止位置le2；
Repeat-Until组合运算单元，若控制结构为Repeat-Until控制结构，则 进行Repeat-Until组合运算，即将终止条件用逻辑公式表示，之后修改 从起始位置出发的迁移，将并入迁移标号的Pre部分，使该组合过程只 有在终止条件为假时可进行，增加一个新的位置le3作为终止位置，并从起 始位置引出一个新的单步迁移e3到达le3，其执行前提是表示终止条件的逻 辑公式为真；
Repeat-while组合运算单元，若控制结构为Repeat-while控制结构，则 进行Repeat-while组合运算，即将终止条件用逻辑公式表示，修改从起 始位置出发的迁移，将并入迁移标号的Pre部分，使该组合过程只有在 终止条件为假时可进行，增加一个新的位置le4作为终止位置，并从起始位 置引出一个新的单步迁移e4到达le4，其执行前提是表示终止条件的逻辑公 式为真；
Split-Join组合运算单元，若控制结构为Split-Join控制结构，则进行 Split-Join组合运算，即将并发条件和汇合条件分别表示为逻辑公式和增加一个新的位置ls5并作为起始位置，从它引出一个并发迁移到达所有组 合过程的起始位置，其执行前提为并发条件增加一个新的位置le5并作 为终止位置，从所有组合过程的终止位置引出一个到达le5的同步迁移，其 执行前提为同步条件
所述Sequence组合运算、所述AnyOrder组合运算、所述Choice组合 运算及所述If-then-Else组合运算为因果约束，所述Repeat-Unti组合运算及 所述Repeat-while组合运算为重复约束，所述Split-Join组合运算为分支约 束，所述因果约束、所述重复约束及所述分支约束为组合约束。
优化模型模块，消除组合过程自动机的冗余并发和同步迁移，获得优化 模型；所述优化模型模块进一步具体为：
并发迁移优化单元，若对于一个并发迁移e(l,slt)=tL={l1,...,ln}，其源 位置l属于另一个并发迁移e′(l′,slt′)=tL′={l1′,...,ln′}的目标位置集合，且两 个并发迁移的并发条件相同，同时不存在以l为源位置或目标位置的单步迁 移，则l是冗余位置，econ(l,slt)=tL={l1,...,ln}为冗余并发迁移，此时将冗余 并发迁移e(l,slt)的目标位置集合tL并入另一并发迁移e′(l′,slt′)的目标位置集 合tL′，同时移除冗余位置l和冗余并发迁移e(l,slt)；否则位置l不是冗余位置， 并发迁移e(l,slt)不是冗余并发迁移；
同步迁移优化单元，若对于一个同步迁移e(sL={l1,...,ln},jn)=l，其 目标位置l属于另一个同步迁移e′(sL′={l1′,...,ln′},jn′)=l′的源位置集合， 且两个同步迁移的同步条件相同，同时不存在以l为源位置或目标位置的单 步迁移，则l是冗余位置，e(sL={l1,...,ln},jn)=l为冗余并发迁；此时将冗 余同步迁移e(sL={l1,...,ln},jn)的源位置集合sL并入另一同步迁移e′(sL′= {l1′,...,ln′},jn)的源位置集合sL′，同时移除冗余位置l和冗余同步迁移e(sL= {l1,...,ln},jn)；否则位置l不是冗余位置，并发迁移e(l,slt)不是冗余并发迁 移。
可接受位置集合模块，依据用户限定的相容性要求，确定组合过程自动 机的可接受位置集合，所述可接受位置集合模块进一步具体为：
第一可接受位置集合单元，第一可接受位置集合WFL：其中原子服务 的WFL为其起始位置和终止位置为该原子服务的第一可接受位置，对n台 组合过程自动机CPAi，进行组合运算后得到的新组合过程自动机CPA，其 第一可接受位置集合WFL为各CPAi的第一可接受位置集合WFLi的并集， 并且从WFL中移除组合过程中被剔除的位置，若组合过程中增加了新的位 置，且该位置为起始位置或终止位置，则应添加到WFL中；
第二可接受位置集合单元，组合过程自动机CPAi的第一可接受位置为 WFLi，当在组合过程中出现组合约束时，获得的可接受位置组成第二可接 受位置集合：
对n台组合过程自动机CPAi进行Sequence组合运算得到新的组合过程 自动机CPASeq，若出现组合约束语义：若CPAi执行则CPAj也必须执行，其 中i<j，则普通可接受位置集合OFLSeq为CPA1～CPAi-1，及CPAj+1～CPAn的 第一可接受位置的并集，再加上CPAi的起始位置sLoci和CPAj的终止位置 eLocj；
或者对n台组合过程自动机CPAi进行AnyOrder组合运算得到新的组合 过程自动机CPAAO，若出现组合约束语义：组合服务的运行不能停止在CPAj， 则普通可接受位置集合OFLAO是在其第一可接受位置集合WFLAO的基础上， 去除CPAj的第一可接受位置集合WFLj，即OFLAO=WFLAO-WFLj；
或者对于n台组合过程自动机CPAi进行Choice组合运算得到新的组合 过程自动机CPACho，若出现组合约束语义：若CPAj被选中执行则必须执行 完成，则普通可接受位置集合OFLCho是在其第一可接受位置集合WFLCho 基础上，去除CPAj的第一可接受位置集合WFLj，即OFLCho=WFLCho-WFLj；
或者对于两台组合过程自动机CPA1和CPA2进行If-then-Else组合运算 得到新的组合过程CPAItE，若出现组合约束语义：若CPAj被选中执行则必 须执行完成，则普通可接受位置集合OFLItE是在其第一可接受位置集合 WFLItE中去除CPAj的第一可接受位置集合WFLj，即OFLItE=WFLAO-WFLj；
或者对于组合过程自动机CPA进行Repeat-Until组合运算得到新组合过 程自动机CPARU，若出现组合约束语义：CPA必须重复执行直到终止条件成 立，则普通可接受位置集合OFLRU={le}，即只有终止位置可接受；
或者对于组合过程自动机CPA进行Repeat-while组合运算得到新组合过 程自动机CPARW，若出现组合约束语义：CPA必须重复执行直到循环条件不 成立，则普通可接受位置集合OFLRW={le}，即只有终止位置可接受；
或者对于n台组合过程自动机CPAi进行Split-Join组合运算得到新的组 合过程自动机CPASJ，若出现组合约束语义：分支组件CPAj必须执行完成， 则普通可接受位置集合OFLSJ是在其第一可接受位置集合WFLSJ的基础上， 去除CPAj的第一可接受位置集合WFLj，即OFLSJ=WFLSJ-WFLj；
当组合过程中不存在组合约束语义时，第二可接受位置集合即等于第一 可接受位置集合；
第三可接受位置集合单元，组合过程自动机的第三可接受位置集合为 SFL为组合过程自动机的起始位置和终止位置，或者是组合过程自动机的终 止位置;
所述相容性为：若组合服务由n台组合过程自动机组成，si为第i台组 合过程自动机的位置集合，则组合服务的全局状态向量gsv=(s1,s2,...,sn)， 若有全局状态向量gsv=(s1,s2,...,sn)和gsv′=(s1′,s2′,...,sn′)，其中一台组合 过程自动机发生迁移，使得gsv中的某个si变化为gsv′中的si′，而其它的sj保持即则称gsv发生迁移到达gsv′，记为gsv→gsv′；对于全 局状态向量gsv：若满足则称gsv为起始全局状态向 量，记为gsv0；若不存在gsv′，使得gsv→gsv′成立，则称gsv为终止全局 状态向量，记为gsve；
将组合服务从起始全局状态向量开始的一系列迁移称为组合服务的一 次运行：gsv0→gsv1→gsv2→...→gsv，简记为gsv0[→]tr gsv，对于组合服 务的一次运行gsv0[→]tr gsv：若则称该次运行满足弱 相容性，记为WC(gsv0[→]tr gsv)；若则称该次运行满 足普通/自定义相容性，记为OC(gsv0[→]tr gsv)；若则 称该次运行满足强相容性，记为SC(gsv0[→]tr gsv)；将gsv0[→]tr gsve称为组 合服务的一次完整运行；
一个组合服务CS是完全强/普通/弱相容的，当且仅当任意gsv0[→]tr gsve都是强/普通/弱相容的；一个组合服务CS是部分强/普通/弱相容的，当且仅 当至少存在一个gsv0[→]tr gsve是强/普通/弱相容的。
逻辑公式模块，依据用户限定的有效性要求，确定有效的逻辑公式CSV； 所述有效性逻辑公式CSV=(INFOS,EFFECTS)，其中：INFOS为一组要求组 合服务产生的语义信息集合；EFFECTS为一组逻辑公式，该逻辑公式描述 要求组合服务必须达到的限定效果。
转换建模语言模块，将所述获得优化模型转换为UPPAAL的建模语言； 所述转换建模语言模块进一步具体为：
单步迁移转换单元，组合过程自动机CPA中的单步迁移esin(l,a)=l'直 接转换为一台符合UPPAAL语法的时间自动机UTA的迁移离散迁移迁移标号a=(In,Out,Pre,Eft)转换为a'，其中g是由时钟 变量表示的约束条件，r是需要被重置为0的时钟变量集合；所述单步迁移 转换单元进一步具体为：
组合过程自动机CPA中的单步迁移esin(l,a)=l'直接转换为一台符合 UPPAAL语法的时间自动机UTA的迁移离散迁移迁移标号其中，Guard是一个逻辑表达式，表 示迁移执行的条件；Sync是一组通道的发射或接受动作，用于实现同步迁 移；Update是一组表达式或用户函数，用于表达迁移的效果；语义信息缓 冲区SIB=(SI,V,f)，SI是语义信息集合，V是整型变量集合，映射f:SI→V， f是双射的；迁移标号被扩展为一个四元组(In,Out,Pre,Eft)，其中Pre和Eft 表示执行前提和执行效果，逻辑公式和表达式组成，直接并入到建模语言迁 移标号的Guard和Update的部分；In是输入信息的集合，将其表示为：一 个合取公式∧f(ci)并且并入迁移标号的Guard部分，合取项的数量与In的元 素数量相等，其中f是信息缓冲区中的映射，ci∈In；将其表示为一组表达 式{f(ci)--|ci∈In}，并且并入迁移标号的Update部分；Out是输入信息的集 合，将其表示为一组表达式{f(ci)++|ci∈Out}}并且并入迁移标号的Update 部分；
并发迁移转换单元，CPA中的并发迁移esin(l,jlt)={l1,...,ln}转换为n 台UTA和一个迁移其中：当UTA处于sli位置时， 说明它进入了并发执行的分支；a包含并发条件及一个广播通道的发射动 作conChni!；
同步迁移转换单元，与并发迁移对应的同步迁移esin({l1,...,ln},jn)=l'， 则转换为迁移b中包含广播通道的发射动作 synChni!，使得多个分支能在同一时刻终结，同时，为了保证同步迁移在所 有分支都执行各自的操作后才能发生，增加一个同步变量synVari，初值为0， 并将“synVari==n”并入迁移标号b的Guard部分，其中n为分支数量， 每个分支执行所有操作后都使其值加1；
分支过程单元，新创建的n台UTAi是用于述n个并发执行的分支，在 首尾各增加一个新的位置bl和el，当UTAi处于bl时，说明还没有进入该分 支；当UTAi处于el时，说明该分支已执行完毕；bl到对应分支的第一个状 态的迁移标号包含广播通道的接收动作conChni?；而对应分支的最后一个状 态到达el的迁移标号包含表达式synChni?；每个分支的最后一个迁移标号 的Update部分，增加一个表达式synVari++，使同步变量的值加1。
CTL模块，将可接受位置集合和逻辑公式CSV表示为CTL公式；所述 CTL模块进一步具体为：
相容性变量cptyVari∈{unconcerned,incompatible,weak,ordinary,strong}， 表示UTAi当前的相容性：unconcerned表示该UPAi所描述的并行分支还未 被激活或已经结束，incompatible表示不相容，weak表示弱相容，ordinary 表示普通/自定义相容，strong表示强相容，可以用取值范围为[0,3]的整型 变量来表示相容性变量，数值0～4依次代表incompatible、weak、ordinary、 strong、unconcerned，三种相容性在UPPAAL中可描述为：
当组合服务完成一次完整运行后没有迁移再发生，组合服务进入死锁状 态，在UPPAAL中以deadlock关键字表示，故可将完全/部分相容性表示为 CTL公式F1，如下：
n∈{1,2,3}；
n∈{1,2,3}，其中cptyVari为 相容性变量；
对于有效性CSV=(INFOS,EFFECTS)，完全/部分有效且强/普通/弱相 容，CTL公式F2如下：
验证模块，将建模语言描述的组合服务模型与CTL表达式输入 UPPAAL进行验证；若验证结果为完全相容且有效，则该组合服务满足用 户需求；若验证结果为部分相容且有效，则可根据验证结果生成信息交互引 擎，引导组合服务的运行轨迹，达到用户要求；若验证结果是不满足相容且 有效，则该组合服务无法满足用户需求，所述信息交互引擎为一台信息交互 引擎IEE=<excFac1,excFac2,...,excFacn>，excFaci=(type,obj,{ci})称为是一 个交互因子，其中：type∈{!,?}，表示交互的类型，“!”表示由IEE向Service 发送信息，“?”表示由IEE接收Service发送的信息；obj∈{Servicei}称为交 互对象是一个组件服务；{ci}是交互的信息集合。
验证框架的前端是一种服务描述语言(标准)，这可以让研究工作始终处在 标准的约束下，使得验证方法具有通用性，而不是局限于某个具体的实例。 本发明选择的是目前业界最为认可的服务描述语言OWL-S。
由于模型检测工具并不是为验证Web服务而设计的，因此通常不适合直 接描述Web服务，因此需要一个转换中介。通过对服务描述语言的研究与分 析，将其转化为一种合适的形式化模型，为使用建模语言描述Web服务提供 基础。
在建立了形式化模型之后，需要进一步进行分析，保证它的正确性。在 此前提下，还可以进行改进和优化，使其更精简高效。通过性质分析技术， 将组合服务的相关性质映射到形式化模型上，得到待验证的系统性质。
最后，使用模型检测工具的建模语言对形式化模型进行描述，并将待验 证的组合服务的性质转换为模型检测工具的性质描述语言。将两者输入到模 型检测器，即可进行自动验证。
原子过程的模型在OWL-S描述的Web服务中，最小的单位是原子过程， 可视为一个不可再分的原子服务，用一个IOPEs来描述。而若干个原子过程或 组合过程通过控制结构组合在一起形成新的组合过程。对于一个原子过程， 很自然地可以把它表示成自动机的一个迁移，组合过程就可以表示成一台具 有多个迁移的自动机。但是，OWL-S中原子过程或组合过程是按一定的控制 结构组合在一起的，并不只是简单的顺序组合。传统的自动机并不能很好地 表达这些控制结构，尤其是OWL-S中的Split和Join控制结构。因此，需要将 传统的自动机扩展为并发有限自动机：
定义1(并发有限自动机)一台并发有限自动机CFA=(L,IL,FL,Σ,E)， 其中：L为位置集合，IL∈L为初始位置集合，为可接受位置；Σ为迁 移标号集合；迁移边集合E={esin}∪{econ}∪{esyn}，分为单步、并发和同步 三类：
esin:L×Σ→L.
econ:L×Σ→2L.
esyn:2L×Σ→L.
并发迁移从一个位置迁移到多个位置(即确定型有限自动机中的状态)，而 同步迁移从多个位置迁移到一个位置。因此，并发有限自动机的迁移是位置 集合之间的转换。
在并发有限自动机的基础上，扩展起始位置和终止位置，就成为了一台 组合过程自动机(Composite Process Automata)。
定义2(组合过程自动机)一台组合过程自动机是一台扩展的并发有限 自动机CPA=(L,IL,FL,sLoc,eLoc,Σ,E)，其中：sLoc记录CPA的起始位置， eLoc记录CPA的终止位置。且规定IL={sLoc}，eLoc∈FL。
从接口的角度，WSDL1.1规范为Web服务定义了四种类型的消息传输 模式：
One-Way：仅接收一条消息，如图5a所示。
Notification：仅发送一条消息，如图5b所示。
Request-Respone：先接收一条消息，再发送一条消息，如图5c所示。
Solicit-Respone：先发送一条消息，再接收一条消息，如图5d所示。
显然，原子过程可能有发送和接收两个动作，且有先后顺序之后，对应 的也应有四种原子过程。如图5a、图5b、图5c及图5d所示，其中，起始位置 用被一个独立的箭头指向(如l0)，终止位置用双圆表示(如l2)。
在OWL-S中，用IOPEs来描述接口，这可以通过扩展迁移标号来实现：
定义3(迁移标号的扩展)一台组合过程自动机的迁移标号集合Σ= {(In,Out,Pre,Eft)}，其中：In、out是输入和输出信息的集合，由OWL本 体概念描述；Pre、Eft是执行前提和执行效果集合，由逻辑公式和表达式描 述。
组合方法
OWL-S提供了九种控制结构用于流程描述：
Sequence：一组原子或组合过程按先后顺序连接在一起。
Anyorder：一组原子或组合过程以任意的次序执行，但一个过程结束前， 另一个过程不能开始执行，即多个过程的执行不可交错。
Choice：从一组原子或组合过程中选择一个执行，但没有明确定义选择 条件，可以用于实现随机选择。
If-then-else：从两个原子或组合过程中选择一个执行，其选择条件是明 确定义的。
Repeat-until：重复执行一个原子或组合过程，直到(until)终止条件成立。
Repeat-while：当(until)循环条件成立，重复执行一个原子或组合过程。
Iterate：是一个抽象概念，但在OWL-S过程模型中不能被实例化，因 此不予分析和使用。
Split：一组原子或组合过程并发执行，即将一组过程激活。所有过程的 激活条件都是相同的，但可以为空。
Split+Join：同样是激活一组原子或组合过程，使它们并发执行，但还 要求这些组合过程执行结束。所有过程的激活条件和结束都是相同的，但可 以为空。
在实际应用中，组合通常是对多个组合过程，虽然可以通过多次的两两 组合来实现，但这样会造成一些不便。因此，以下介绍的组合运算，其运算 对象可以有多个，但不包括对运算对象个数有限制(如If-then-Else)的组合运 算。由于Split实际上就是Split+Join的一部分，因此没有另外定义Split组合运 算。介绍组合运算时所使用的示例，将以图6中的两台原子过程自动机作为运 算对象，其中a、b、c及d为迁移事件。
1、Sequence
Sequence组合运算是将多个组合过程，按照排列的先后顺序连接在一起。 如图7所示。组合方法如下：将CPA1的终止位置(l12)，与CPA2的起始位置(l20) 合并。
2、AnyOrder
AnyOrder组合运算将多个组合过程以任意次序不重叠地组合在一起。如 图8所示。组合方法如下：
（1）构造一组逻辑公式初始时的值为true，其中表示将第1到第n个逻辑公式合取，与不含相同命题变元。
（2）将所有的起始位置(l10、l20)合并为一个新的起始位置(ls)，从原起始 位置出发的迁移都改为从新起始位置出发，并且迁移标号的Pre部分并入一个 即为和这样能够保证每次随机选取一个为真的迁移执行，即随机执行一个组合过程。
（3）从所有原终止位置(l12、l22)以出一条到达ls的迁移，该迁移的作用是 使得为假，从而保证该组合过程不会被重复执行。
（4）增加一个新的位置le并作为终止位置，同时增加一个从ls到le的单步 迁移e，其执行前提是公式为真，从而保证，只有当所有的组合过程都被执 行完后，才能到达le。
3、Choice
Choice组合运算将多个组合过程并行连接，但只会有一个组合过程会被 执行。如图9所示。组合方法如下：
（1）将所有组合过程的起始位置(l10、l20)合并为一个新的起始位置(ls)。
（2）将所有组合过程的终止位置(l12、l22)合并为一个新的终止位置(le)。
4、If-then-Else
f-then-Else组合运算的运算对象只有两个，只有其中一个组合过程会被执 行。选择条件是明确定义的，用逻辑公式表示。如图10所示。组合方法如下：
（1）将选择条件表示成逻辑公式
（2）将所有组合过程的起始位置(l10、l20)合并为一个新的起始位置(ls)， 从原起始位置出发的迁移改为从新起始位置出发，并用和修改迁移标号 的Pre部分,即为和保证只会有一个组合过程被 执行。
（3）将所有组合过程的终止位置(l12、l22)合并为一个新的终止位置(le)。
5、Repeat-Until
Repeat-Until组合运算的运算对象只有一个，它将被反复执行，直到终止 条件为真。如图11所示。组合方法如下：
（1）将终止条件用逻辑公式表示。
（2）修改从起始位置l10出发的迁移，将并入迁移标号的Pre部分 即为使该组合过程只有在终止条件为假时可进行。
（3）增加一个新的位置le作为终止位置，并从起始位置l10引出一个新 的单步迁移e到达le，其执行前提是表示终止条件的逻辑公式为真，这样 可以保证该迁移在终止条件成立以前不会被执行。
6、Repeat-while
Repeat-While组合运算的运算对象只有一个，当循环条件成立时，它将 被反复执行。如图12所示。其组合方法与Repeat-Until类似，只是将终止 条件即为替换为循环条件。
7、Split-Join
Split-Join组合运算激活多个组合过程，使它们并发执行，并在所有进 程都结束后汇合终止。如图13所示。组合方法如下：
（1）将并发条件和汇合条件分别表示为逻辑公式和但这两个条 件都不是必需的。
（2）增加一个新的位置ls并作为起始位置，从它引出一个并发迁移到 达所有组合过程的起始位置(l10、l20)，其执行前提为并发条件
（3）增加一个新的位置le并作为终止位置，从所有组合过程的终止位 置(l12、l22)引出一个到达le的同步迁移，其执行前提为同步条件
由以上7个组合运算可知，组合过程都是对组合过程自动机的起始位置和 终止位置所进行的连接，而且组合运算产生的结果依然是组合过程自动机(有 起始位置和终止位置)，这就保证了无论具有怎样复杂结构的组合服务，都能 够参与新的组合运算。
模型改进：在建立Web服务的形式化模型的过程中，可能会因为描述 或组织的不当，导致模型不够精炼简洁。因此需要对模型进一步的分析，在 不影响其正确性的前提下，进行改进和优化，也就是验证框架中的模型改进 的部分。本发明主要研究在组合过程中所产生的冗余并发/同步迁移，并给 出改进方法。
当两个以Split-Join结构连接、且并发/同步条件相同的组合过程自动机， 再以相同的并发/同步条件按照Split-Join结构连接，则会产生冗余的迁移和 位置，如图13所示。位置l10、l20、l17、l27及对应的并发/同步迁移都是冗余 的，l11、l12、l21、l22都可以直接与ls连接，而l15、l16、l25、l26则可以直接与 le连接。在实际的Web服务中，Split和Split-Join控制结构的并发和同步条 件经常为空，因此在建立形式化模型的过程中，很容易出现冗余的并发/同 步迁移。
1.冗余并发迁移的判定及消除
对于一个并发迁移e(l,slt)=tL={l1,...,ln}，其源位置l若属于另一个并发 迁移e′(l′,slt′)=tL′={l1′,...,ln′}的目标位置集合，且两个并发迁移的并发条件 相同，同时不存在以l为源位置或目标位置的单步迁移，则l是冗余位置，econ(l, slt)=tL={l1,...,ln}为冗余并发迁移。
消除的方法是：将冗余并发迁移e(l,slt)的目标位置集合tL并入另一并发迁 移e′(l′,slt′)的目标位置集合tL′，同时移除冗余位置l和冗余并发迁移e(l,slt)。
2.冗余同步迁移的判定及消除
对于一个同步迁移e(sL={l1,...,ln},jn)=l，其目标位置l若属于另一个 同步迁移e′(sL′={l1′,...,ln′},jn′)=l′的源位置集合，且两个同步迁移的同步 条件相同，同时不存在以l为源位置或目标位置的单步迁移，则l是冗余位 置，e(sL={l1,...,ln},jn)=l为冗余并发迁移。
消除的方法是：将冗余同步迁移e(sL={l1,...,ln},jn)的源位置集合sL并入 另一同步迁移e′(sL′={l1′,...,ln′},jn)的源位置集合sL′，同时移除冗余位置l和 冗余同步迁移e(sL={l1,...,ln},jn)。
按照上述方法，对图14所示的组合过程自动机进行优化，结果如图15 所示。
组合服务的相容性与有效性分析：在前面所建立的组合过程自动机模型 的基础上，可以依据可接受位置来分析组合服务的相容性，并分为三个等级。 由于Web服务的自治性及独立性，很难保证能够实现完全的融合。但实际 上，当用户的应用需求完成后，若组合服务能够处于相容状态，则该组合服 务即是可用的，即使后面的交互会出现不相容的问题，也可以通过在相容状 态时终止服务的运行来避免。
可接受位置及其分级：本节给出了可接受位置的明确定义，以及在组合 运算中可接受位置的变化，并依据可接受位置的重要程度，将相容性分为了 三个等级。
可接受位置是一个抽象概念，可以是任意良好的性质。当自动机处于可 接受位置，认为它处于一种可接受的状态。为了适应不同程度的相容性需求， 将其分为三个等级：强可接受位置(Strong Acceptable Locaiton)即为第三可接 受位置、普通/自定义可接受位置(Ordinary Acceptable Locaiton)即为第二可接 受位置、弱可接受位置(Weak Acceptable Locaiton)即为第一可接受位置。
定义4(可接受位置的分级)一台组合过程自动机CPA=(L,IL,FL, sLoc,eLoc,Σ,E)的可接受位置集合FL=WFL∪OFL∪SFL，WFL是弱可 接受位置集合、OFL是普通/自定义可接受位置集合、SFL是强可接受位置 集合。
弱可接受位置保障了最基本的相容性需求，它从原子过程开始定义，在 组合运算中被逐步扩充。它认为：若服务处于任意原子操作的可接受位置， 则整个服务就是可接受的。
定义5(弱可接受位置集合)一台原子过程自动机APA=(L,IL,FL, sLoc,eLoc,Σ,E)的弱可接受位置记为WFL。通常情况下，认为原子服务的 WFL={sLoc,eLoc}，即起始位置和终止位置。但在实际应用中，可以根据 具体的应用背景增加或减少。组合过程自动机的可接受位置集合，在原子服 务的可接受位置的基础上定义：对n台组合过程自动机CPAi，进行组合运 算后得到的新组合过程自动机CPA，其弱可接受位置集合WFL为各CPAi的弱可接受位置集合WFLi的并集，并做如下修正：
（1）从WFL中移除组合过程中被剔除的位置。
（2）若组合过程中增加了新的位置，且该位置为起始位置或终止位置， 则应添加到WFL中。
普通/自定义可接受位置在弱可接受位置的基础上增加了更强的约束， 它在弱可接受位置的基础上，根据组合约束，剔除了一些可接受位置。
定义6(组合约束)当一台组合过程自动机参与组合运算时，由于与其 它的组合过程自动机产生了上下文关联，从而产生了对组件服务执行状况的 要求，称为组合约束语义。组合约束语义可以分为三类：
●因果约束：当某种情况发生时，某个组件服务必须要完成。
●分支约束：并发执行的某个分支组件服务必须完成。
●重复约束：某个组件服务必须重复执行，直到循环条件不成立。
在弱可接受位置的基础上，加入组合约束而获得可接受位置集合，称为 普通可接受位置。是否要使用组合约束语义可以根据实际的应用背景来决 定，同时也可以加入新的组合约束语义类型，因此普通可接受位置也称为自 定义可接受位置。它认为：服务只有处于某些特定原子操作的可接受位置， 整个服务才是可接受的。
本发明为每种组合运算给出了一个组合约束，从而获得普通普通/自定义 可接受位置集合。其中：Sequence、Choice、If-then-Else、AnyOrder组合运 算中的组合约束属于因果约束；Repeat-Until、Repeat-While组合运算中的组 合约束属于重复约束；Split-Join组合运算中的组合约束属于分支约束。
定义7(普通/自定义可接受位置集合)组合过程自动机CPAi的弱可接 受位置为WFLi，当在组合过程中出现组合约束时，获得的可接受位置组成 普通/自定义可接受位置集合：
●对n台组合过程自动机CPAi进行Sequence组合运算得到新的组合过 程自动机CPASeq，若出现组合约束语义：若CPAi执行则CPAj也必须 执行(i<j)，则普通可接受位置集合OFLSeq为CPA1～CPAi-1，及 CPAj+1～CPAn的弱可接受位置的并集，再加上CPAi的起始位置sLoci和CPAj的终止位置eLocj。
●对n台组合过程自动机CPAi进行AnyOrder组合运算得到新的组合过 程自动机CPAAO，若出现组合约束语义：组合服务的运行不能停止 在CPAj，则普通可接受位置集合OFLAO是在其弱可接受位置集合 WFLAO的基础上，去除CPAj的弱可接受位置集合WFLj，即 OFLAO=WFLAO-WFLj。
●对于n台组合过程自动机CPAi进行Choice组合运算得到新的组合过 程自动机CPACho，若出现组合约束语义：若CPAj被选中执行则必须 执行完成，则普通可接受位置集合OFLCho是在其弱可接受位置集合 WFLCho基础上，去除CPAj的弱可接受位置集合WFLj，即 OFLCho=WFLCho-WFLj。
●对于两台组合过程自动机CPA1和CPA2进行If-then-Else组合运算得 到新的组合过程CPAItE，若出现组合约束语义：若CPAj被选中执行 则必须执行完成(j∈{1,2})，则普通可接受位置集合OFLItE是在其弱 可接受位置集合WFLItE的基础上，去除CPAj的弱可接受位置集合 WFLj，即OFLItE=WFLAO-WFLj。
●对于组合过程自动机CPA进行Repeat-Until组合运算得到新组合过 程自动机CPARU，若出现组合约束语义：CPA必须重复执行直到终 止条件成立，则普通可接受位置集合OFLRU={le}，即只有终止位置 可接受。
●对于组合过程自动机CPA进行Repeat-while组合运算得到新组合过 程自动机CPARW，若出现组合约束语义：CPA必须重复执行直到循 环条件不成立，则普通可接受位置集合OFLRW={le}，即只有终止位 置可接受。
●对于n台组合过程自动机CPAi进行Split-Join组合运算得到新的组合 过程自动机CPASJ，若出现组合约束语义：分支组件CPAj必须执行 完成，则普通可接受位置集合OFLSJ是在其弱可接受位置集合WFLSJ的基础上，去除CPAj的弱可接受位置集合WFLj，即OFLSJ=WFLSJ- WFLj。
显然，当组合过程中不存在组合约束语义时，普通/自定义可接受位置集 合即等于若可接受位置集合。
强可接受位置保证了最强的相容性，它规定一个服务如果开始执行，就 必须执行完成，而不能停止在某个原子操作上。而一个服务如果能够顺利执 行完成，那么显然与整个组合服务是相容的。
定义8(强可接受位置集合)组合过程自动机CPA的强可接受位置为 SFL={sLoc,eLoc}或{eLoc}，前者表示该组合服务可以不执行，后者表示 该组合服务必须执行(如增加了重复约束时).
通过定义5、定义7和定义8，可以确定一台组合过程自动机的三种等 级的可接受位置，从而满足不同程度相容性的验证需求。需要说明的是，组 合服务在没有运行时也满足强相容性，但这种相容性显然是没有意义的，因 此在后面的验证中排除掉了这种情况。
4.2组合服务的相容性分析
一个组合服务是由多个子服务构成，而这多个子服务本身也可能是组合 服务。区别在于，子服务本身所含的组件服务之间具有固定的控制结构和流 程，具有定义良好的交互协议，通常不会出现不相容的情况；而子服务之间 则是通过信息的交换进行协作，具有不确定性，因此在交互过程中可能会导 致子服务无法到达可接受的状态。
为了分析和定义组合服务的相容性，需要定义组合服务的全局状态向量 (Global State Vector)：
定义9(全局状态向量)若组合服务由n台组合过程自动机组成，si为 第i台组合过程自动机的位置集合，则组合服务的全局状态向量gsv=(s1, s2,...,sn)。
定义10(全局状态向量的迁移)若有全局状态向量gsv=(s1,s2,...,sn) 和gsv′=(s1′,s2′,...,sn′)，若其中一台组合过程自动机发生迁移，使得gsv中 的某个si变化为gsv′中的si′，而其它的sj保持(即则称gsv发 生迁移到达gsv′，记为gsv→gsv′。
定义11(起始与终止全局状态向量)对于全局状态向量gsv：若满足则称gsv为起始全局状态向量，记为gsv0；若不存在gsv′， 使得gsv→gsv′成立，则称gsv为终止全局状态向量，记为gsve。
将组合服务从起始全局状态向量开始的一系列迁移称为组合服务的一 次运行：gsv0→gsv1→gsv2→...→gsv，简记为gsv0[→]tr gsv。其相容性定 义如下：
定义12(组合服务运行的相容性)对于组合服务的一次运行gsv0[→]tr gsv：若则称该次运行满足弱相容性，记为WC(gsv0[→]trgsv)；若则称该次运行满足普通/自定义相容性，记为 OC(gsv0[→]tr gsv)；若则称该次运行满足强相容性，记 为SC(gsv0[→]tr gsv)。
将gsv0[→]tr gsve称为组合服务的一次完整运行，并定义组合服务的相容 性：
定义13(组合服务的相容性)一个组合服务CS是完全强/普通/弱相容 的，当且仅当任意gsv0[→]tr gsve都是强/普通/弱相容的；一个组合服务CS 是部分强/普通/弱相容的，当且仅当至少存在一个gsv0[→]tr gsve是强/普通/ 弱相容的。
显然，无论是组合服务运行的相容性，还是组合服务的相容性，都满足： 强相容性普通/自定义相容性弱相容性。
组合服务的有效性分析：组合服务的有效性即组合需要满足的用户的应用 需求，包括两个方面：一是能够获得用户所需的信息；二是能够满足用户所 要求的效果或性质。因此，组合服务的有效性(Validity of Composition Service) 可定义如下：
定义14(组合服务的有效性)组合服务的有效性CSV=(INFOS, EFFECTS)，其中：INFOS为一组要求组合服务产生的语义信息集合；EFFECTS为一组逻辑公式，描述要求组合服务必须达到的效果。当INFOS和EFFECTS被同时满足时，认为组合服务达到有了有效性要求。
对于组合服务的一个全局状态向量gsv=(s1,s2,...,sn)，以及一个性质 若在s1∪s2∪...∪sn下是可以满足的，则称gsv满足记为若将有效性记为并将(强/普通/弱)相容性记为ψ，对于组合服务的一次运 行gsv0[→]tr gsv，若有则称gsv0[→]tr gsv是有效且(强/普通/ 弱)相容的。
对于Web服务而言，主要是通过编配(Orchestration)和编排(Choreography) 来定义组合服务的交互协议。编配与编排之间存在着重要的差别，目前对于 两者之间的定义还没有形成统一，存在着多种观点，认可度较高的一种解释 是：编配指的是自动执行一个工作流，即用一种执行语言(如BPELP)定义好 工作流，同时让编配引擎在运行时执行这一工作流；而编排指的是，对两个 或两个以上参与方之间的协调交互的描述。
通过对相容性和有效性的分析可知，强相容性是一种过高的相容性要 求，而即使组合服务达到了相容性要求，也未必能够满足有效性。组合服务 所应该达到的要求即有效且普通/自定义相容，但并非所有路径都可满足， 即是部分的。满足部分有效且相容的组合服务实际上已经可以达到应用需 求，因此达到完全相容并非是必要的。关键在于，能够让组合服务按照能够 满足有效且相容的轨迹执行。因此可以通过编排的方式生成信息交互引擎 (Information Exchange Engine)，作为控制器，通过信息的交互来驱动和引导 组合服务，使其按照预期的轨迹执行，如图16所示。
显然，信息交互引擎通过一系列有序的信息交互动作，来完成对组合服 务的控制。下面给出其形式化定义：
定义15(信息交互引擎)一台信息交互引擎IEE=<excFac1,excFac2,..., excFacn)>，excFaci=(type,obj,{ci})称为是一个交互因子，其中：type∈ {!,?}，表示交互的类型，“!”表示由IEE向Service发送信息，“?”表示 由IEE接收Service发送的信息；obj∈{Servicei}称为交互对象，是一个组件 服务；{ci}是交互的信息集合。
恰当的信息交互引擎能够引导服务按照可以达到预期的目标的轨迹执 行，而不恰当的信息交互引擎则会使组合服务达不到预期的目标。本发明所 采用的验证工具UPPAAL给出的检测结果就是一系列的迁移，因此可以很 自然地转换为信息交互引擎。
模型/性质向建模语言/性质描述语言的转换：在建立了Web服务的并发 自动机模型后，需要将其转化为UPPAAL的建模语言，从而能够输入到验 证器中进行自动验证。转换包括：语义信息的抽象、输入/输出动作的描述、 迁移的转换、性质的描述以及模型的合成。
依据UPPAAL4.0的语法[4,5]，其建模语言是扩展时间自动机，增加了 丰富的数据类型、表达式和运算，并且对迁移标号进行了扩展：迁移标号a =(Select,Guard,Sync,Update)。本文的工作只用到后三个部分，因此Select 总是为空：Guard是一个逻辑表达式，表示迁移执行的条件；Sync是一组通 道的发射或接受动作，用于实现同步迁移；Update是一组表达式或用户函 数，用于表达迁移的效果。
语义信息的抽象：在组合服务的验证中，由于Web服务采用的是异步交 互的方式，所以必须考虑语义信息的数量。因此，需要设立一个语义信息缓 冲区(Semantic Information Buffer)，它由一组语义信息、一组整型变量和一 个映射组成：
定义16(语义信息缓冲区)一个语义信息缓冲区SIB=(SI,V,f)，SI是 语义信息集合，V是整型变量集合，映射f:SI→V(f是双射的)。
语义信息所对应的整型变量，用于记录该语义信息的数量。相应的，当 服务操作输入或输出语义信息时，需要变更对应的变量：当输入一个语义信 息c时，要执行f(c)--；当输出一个语义信息c时，要执行f(c)++。
输入输出动作的描述：在Web服务的并发自动机模型中，迁移标号被扩 展为一个四元组(In,Out,Pre,Eft)，用建模语言描述如下：
●Pre和Eft表示执行前提和执行效果，逻辑公式和表达式组成，因此 可直接并入到建模语言迁移标号的Guard和Update的部分。
●In是输入信息的集合，将其表示为：一个合取公式∧f(ci)并且并入(合 取)迁移标号的Guard部分，合取项的数量与In的元素数量相等，其 中f是信息缓冲区中的映射，ci∈In；一组表达式{f(ci)--|ci∈In}，并 且并入迁移标号的Update部分。
●Out是输入信息的集合，将其表示为一组表达式{f(ci)++|ci∈Out}} 并且并入迁移标号的Update部分。
迁移的转换：对于并发自动机的三类迁移，UPPAAL的建模语言只能直 接描述其中的单步迁移，而对于并发迁移和同步迁移则无法直接表达，但可 以通过其中的广播通道来间接描述。对于一台组合过程自动机CPA=(L,IL, FL,sLoc,eLoc,Σ,E)，可以转换为一个UPPAAL的时间自动机集合{UTAi}(不 会为空)，转换方法如下：
（1）CPA中的单步迁移esin(l,a)=l'可直接转换为UTA的迁移离散迁移 迁移标号a=(In,Out,Pre,Eft)按照前面所述的方 法转换为a'。
（2）CPA中的并发迁移esin(l,jlt)={l1,...,ln}需要转换为n台UTA，和 一个迁移其中：sli是特殊的位置，当UTA处于该 位置时，说明它进入了并发执行的分支；a包含并发条件，以及一个广播通 道的发射动作conChni!。
（3）而与并发迁移对应的同步迁移esin({l1,...,ln},jn)=l'，则转换为迁 移迁移b中包含广播通道的发射动作synChni!， 使得多个分支能在同一时刻终结。同时，为了保证同步迁移在所有分支都执 行各自的操作后才能发生，增加一个同步变量synVari，初值为0，并将“synVari==n”(n为分支数量)并入(合取)迁移标号b的Guard部分，每个分支执行所 有操作后都使其值加1。
（4）新创建的n台UTAi是用于述n个并发执行的分支，除了分支本身 所具有的状态和迁移外，在首尾各增加一个新的位置bl和el。当UTAi处于 bl时，说明还没有进入该分支；当UTAi处于el时，说明该分支已执行完毕。 bl到对应分支的第一个状态的迁移标号包含广播通道的接收动作conChni?； 而对应分支的最后一个状态到达el的迁移标号包含表达式synChni?；每个 分支的最后一个迁移标号的Update部分，增加一个表达式synVari++，使同 步变量的值加1。
图17是并发/同步迁移转换的示例。需要注意的是，在UPPAAL的建模 语言中，用双圆形(如UTA0中的l0)代表起始位置，并且没有定义明确的可接 受位置，这与并发有限自动机是不同的。
此外，其中的迁移标号“b'∧(synVar++)”和“c'∧(synVar++)是不规范 的表达，表示迁移发生除了要满足和执行迁移标号后，还要执行synVar++。
性质的描述：从上述的分析中可知，因此即强相容性普通/自定义相容性弱相容性。而 Web服务运行的相容性是对组合过程自动机的位置集合整体而言的，以强相 容性为例：若一台CPA在运行中某个时刻的位置集合中，只要有一个不是 强可接受位置，则该CPA在此时就不满足强相容性。
显然，当组合过程自动机进入位置l时：若则CPA一定不满 足强相容性；若则CPA一定不满足普通/自定义相容性； 若则CPA一定不满足弱相容性。
从前面的迁移转换方法可知，组合过程自动机被划分为若干台并行的 UTAi，在同一时刻，每台UTAi只会处于一个位置，因此当每次迁移发生时， 都可以立刻知道该台UTAi是否满足相容性以及满足何种相容性。
而对于整个Web服务而言：只要有一个UTAi不满足相容性，则整个Web 服务就不满足相容性；若所有的UTAi都满足相容性，则整个Web服务的相 容性取决于所有UTAi中最弱的相容性。
为了记录每台UPAi的相容性状况，为每台UTAi分配一个相容性变量 (Compatible Variable)：
定义17(相容性变量)相容性变量cptyVari∈{unconcerned, incompatible,weak,ordinary,strong}，表示UTAi当前的相容性：unconcerned 表示该UPAi所描述的并行分支还未被激活或已经结束，incompatible表示不 相容，weak表示弱相容，ordinary表示普通/自定义相容，strong表示强相容。
因此，若有一个组合过程自动机CPA，转换为一组对应的{UTAi}，及一 组相容性变量{cptyVari}，其相容性可描述为：
●满足强 相容性。
●满足 普通/自定义相容性。
●满足弱 相容性。
相应的，需要为UTAi的每个迁移发生时，都要相应改变cptyVari的值， 依据目标位置l，赋值规则如图18所示；
在UPPAAL中，可以用取值范围为[0,4]的整型变量来表示相容性变量， 数值0～3依次代表incompatible、weak、ordinary、strong、unconcerned。从 上文对相容性的描述和分析，可知有strongordinaryweak，且 unconcerned对服务的相容性不会产生影响，故三种相容性在UPPAAL中可 描述为：
●
●
●
当组合服务完成一次完整运行，因为没有迁移再发生，组合服务进入死 锁状态(在UPPAAL中以deadlock关键字表示)，故可用CTL公式将完全/ 部分相容性表示为：
●n∈{1,2,3}。
●n∈{1,2,3}。
对于有效性CSV=(INFOS,EFFECTS)，完全/部分有效且(强/普通/弱)相 容，可以表示为：
其中CTL逻辑把系统的运行视为状态序列，而一个系统可能会有多个不 同的运行(状态序列)。例如，一个有12个小时的时钟系统，它最常见的运 行是：1->2->3->4->…->12（这里只用时间这一个变量来描述系统状态）， 这个运行有12个状态。另一个运行可能是：1->2->3->3->3（时钟出现了停 顿，可以理解为时钟有故障了）。实际上，时钟的运行有无限多个，每个运 行的状态数量可能是不同的。
A的语义是“所有运行”，E的语义是“存在至少一个运行”，□的语义是 “所有状态”，◇的语义是“存在至少一个状态”。用F代表一个逻辑公式， 解释如下：
A□F：在系统的所有运行中的所有状态，公式F都是成立的。
A◇F：在系统的所有运行中，都至少存在一个状态，使得公式F成立。
E□F：在系统的至少一个运行中的所有状态，公式F都是成立的。
E◇F：在系统的至少一个运行中，存在至少一个状态，使得公式F成立。
多个模型的合成：综上所述，一台组合过程自动机CPA，可转换为一个 UPPAAL的模型WSUPL=(SIB,{UTAi},{cptyVari})。
若有n个CPAi构成组合服务，则对应有n个WSUPLi=(SIBi,{UTAj}i, {cptyVarj}i)，则组合服务的UPPAAL模型CSUPL=(SIB,{UTAk}, {cptyVark})，其中各个元素的合成方法如下：
（1）SIB.SI=SIB1.SI∪…∪SIBn.SI，SIB.SI=SIB1.V∪…∪SIBn.V，SIB.f =SIB1.f∪…∪SIBn.f(映射规则的并)。
（2）{UTAk}={UTAj}1∪…∪{UTAj}n。
（3）{cptyVark}={cptyVark}1∪…∪{cptyVark}n。
生成信息交互引擎：UPPAAL的验证结果由一系列的迁移构成，迁移分 为三种：用于表示单步的迁移，用于并发的迁移，用于表示同步的迁移。后 两种迁移不涉及信息的交互，而第一种迁移分为发送信息和接收信息两种。 显然，除服务组合自动机SCA外，对于每个单步迁移e(即不含广播通道)， 都可以将其转换为一个交互因子excFaci=(type,obj,{ci})：
迁移e若是接收操作(f(ci)--)，则type=!；迁移e若是发送操作(f(ci)++)， 则type=?。
迁移e所属的服务Service，即为交互对象。
迁移e所包含的信息，即为交互的信息集合。
本发明具有如下优点：对OWL-S中的原子过程与组合过程的描述更具 体完整，并保持了两者的形式一致，可以无差异地参加组合运算，支持逻辑 公式和表达式，描述能力更强，尤其是对执行前提、执行效果与组合服务性 质的描述；通过验证过程自动化，不仅降低了验证技术的应用门槛，也能够 避免在验证过程中引入新的错误；将有效性与相容性相结合，对组合服务的 验证更全面；划分了相容性的强度等级，可避免因过强的相容性要求，而造 成一些可用的组合服务被排除，其验证结果可用于错误定位，或引导组合服 务正确执行，所使用的验证技术与工具在空间表示与维持上具有显著的优 势，能够通过增加时钟、迁移概率等要素进行扩展，并且都有相应的模型检 测工具支持。
虽然以上描述了本发明的具体实施方式，但是熟悉本技术领域的技术人 员应当理解，我们所描述的具体的实施例只是说明性的，而不是用于对本发 明的范围的限定，熟悉本领域的技术人员在依照本发明的精神所作的等效的 修饰以及变化，都应当涵盖在本发明的权利要求所保护的范围内。
机译： 基于人工智能计划的面向消息的语义Web服务组合的方法和系统
机译： 基于人工智能计划的面向消息的语义Web服务组合的方法和系统
机译： 基于模型的Web服务组合安全策略验证方法
