142《理论计算机科学电子札记》65卷第4期（2002）网址：http://www.elsevier.nl/locate/entcs/volume65.html13页Composition and Correctness组成和正确性ller1;2InstitutfurProgrammstrukturenundDatenorganisationUniversit卡尔斯鲁厄D-76128 Karlsruhe，Germany摘要本文提出了一种保证组合系统正确性的方法。它考虑到正确性通常只能达到一定程度（除了一些小型和非常关键的应用程序），完整的规范通常是不可行的。通过对零件、组合活动和需求规范进行建模，我们使用模型检查来自动化检查过程。因此，一个重要的问题是，我们的方法允许部分建模和规范。1介绍和问题组件和组件组合的目标是从更大的可重用单元生成软件系统，从而提高系统开发的生产率和质量[22]。研究表明，对象和组件不足以组成系统。揭示这一事实的症状是，例如，所谓的横切代码[12]，即不能在一个对象或一个组件中干净地捕获的代码。在方法论和分解策略方面有很多研究。随着被称为方面的新单元捕获横切代码，面向方面设计领域的研究正在发展。在实现层面上也存在一系列的合成技术这些方法的范围从新粒度（例如继承、mixins、函数调用）到粗粒度（例如元编程[14]、CORBA、RMI），从黑盒到1 这项工作由欧盟委员会在IST计划的FET开放领域根据合同号IST-1999-14191（EASYCOMP -未来一代组件系统的简单组成）提供部分本材料中表达的任何意见，结论，结论或建议均为作者，不一定反映赞助商的观点。2 电子邮件地址：pulvermueller@acm.org2002年由ElsevierScienceB出版。 诉操作访问根据C CB Y-NC-N D许可证进行。PuLvermuller143灰盒或白盒。它们中的一些已经作为商业产品提供，另一些仍然只存在于研究中（例如Piccola [1]，基于监控的AOP [6]）。然而，组合建模和组合中的正确性问题还没有得到太多的探讨，无论是对象还是组件，还是这些新出现的这与Bertrand Meyer [16]的观察相反，他说，正确性是首要的品质。如果一个系统没有做它应该做的事情，那么它的其他一切（无论它是快速的，有一个很好的用户界面......）“小事”。在这方面缺乏研究是由于巨大的问题，以确保正确性和问题，以确定究竟是什么正确性在一定的情况下，即。以精确的形式指定系统要求[16]。处理正确性的一些方法是内置检查，适当的语言机制，如静态类型，断言，自动内存管理和纪律异常处理。这些都是众所周知的技术，但主要是在非常低的语言水平上操作。组件和组合对系统正确性提出了进一步的挑战。在下文中，我们定义并解释一些基本术语。我们给出一个概述（cf.第3节）关于我们的方法，以提供一种对组合进行建模的方法，并提供一定程度的正确性，然后详细说明这些正确性保持技术（cf.第3.1和3.2节）适用于合成领域。2正确性在本节中，我们考虑一些关于正确性的基本术语和支持正确性的方法的要求。为了在我们的方法中定义最基本的术语，我们参考[16]：定义：正确性正确性是软件产品执行其特定任务的能力。因此，我们可以将组合的正确性定义为组合系统执行其规范所定义的确切任务的能力。因此，组合的正确性等同于该组合的结果的正确性。因此，需要一个定义组合系统任务的规范。主要的问题是，一个规范不能在一般情况下被证明。虽然我们的软件产品可能是正确的，因为它根据给定的规范执行其任务，但结果可能是不正确的，因为规范包含错误和/或不完整。正确性方法应该满足哪些标准？PuLvermuller144(i) 广泛的检查支持检查可以分为预构建检查（例如断言，键入）和后构建检查（例如测试，调试）。支持正确性的方法应该在任何时候都是适用和有用的(ii) 明确的建模和规范组件和组合必须在适当的抽象级别上建模。将实现作为模型通常过于详细，并且不是用于检查目的的适当表示。除了对组件和组成进行建模外，我们还需要详细说明什么是正确的，因此应该检查什么。适当的语言是必要的。(iii) 部分物种和零碎的增长[4]正确性领域的主要问题之一是缺乏和无法完成。这是由于问题的复杂性，随着时间的推移和人类在理解问题方面的局限性。因此，在正确性方法中的一个重要问题是，它能够根据需要和可用情况（零碎增长）扩展模型和规范。该方法必须产生有用的结果，虽然问题没有完全建模，只有部分规格。(iv) 分层、细节级别更改、压缩B. Meyer [16]已经指出，通常不可能在单个级别上处理所有组件和属性，并推荐分层方法（或条件方法）。假设较低的层次是正确的（条件），我们可以保证某一层的正确性。这在计算机科学中已经很常见了。例如，在操作系统和编译器之间有一个清晰的分离是标准的我们可以将这种条件方法映射到组件域。组件由子组件组成。因此，这些子组件形成了组合系统层的子层。组成的正确性意味着每个单元相对于给定的规范（子层）是规范和正确的。根据条件方法，组件正确性的前提条件是其子组件正确。我们把这种分层称为组件系统压缩。定义：压缩 （J.O.）Coplien in [7]）压缩是使用别名来保留压缩表达式中的信息，这意味着编码或其他补充上下文。这与抽象不同，抽象是有选择地删除或隐藏被认为对特定观点，关注或焦点重要性降低的信息。PuLvermuller145构成部分2组合物(v) 高效处理正确性及其证明的主要问题是它的复杂性。一个实用的解决方案必须包含智能机制来处理这种复杂性。(vi) 独立正确性的方法应该分别独立于关于编程语言和组合技术或语言的具体工具。3基于模型的正确性我们的方法的主要目标是支持自动化的软件单元和它们的组成的正确性检查。每个部分包含由代码中的一些静态和动态元素和序列所反映的任务。为此，我们必须分析现有的代码（以可重用组件的形式），用某种语言对基本部分进行建模（因此从详细代码中抽象出来），并根据用某种特定语言编写的定义的语义要求检查这个模型。该模型可以从现有代码中导出。因此，我们可以区分四个步骤：(i) 单个部件的建模和验证（参见 第3.1节）。(ii) 组合建模（单个模型的扩展）（参见第3.2节）。(iii) 对组合系统的规范进行建模（参见 第3.2节）。(iv) 根据本规范验证组合系统（参见第3.2节）。ABSTRACTIONFig. 1. 我们的正确性构成部分1模型1LocalVerificati on当地规格1+模型2LocalVerificati on本地规范2+模型构图模型VerificationSpecPuLvermuller146Component第1M1M2出口1R1第二部分M3第3c1m4|c2m4OutPort2R2R3R4[condition1]C1R5[condition2]c2r6OutPort3trdObjectsndObjectfstObject3.1组件在我们开始验证组合系统的正确性之前，我们首先必须分别检查每个组件，将其规格与相应的实现模型进行比较。为了描述组件的功能，我们区分组件的输入（由InPorts表示），其输出（OutPorts）和其内部的端口（参见图2）。InPorts和OutPorts的接口规范的概念是基于模块接口概念[9]。它的应用在各种论文中有描述[13]。InPorts 和 OutPorts 是 代 表 组 件 的 输 入 和 输 出 通 信 协 议 的 nite statemachines。有几种替代方案来描述端口之间的内部控制流：像CoCoNut[10]中的nite状态自动机，其基于nite状态自动机在网络通信协议[11]的设计和验证中的应用经验，或者UML序列图[24]。由于UML序列图的自动生成是由各种工具支持的，第二种选择具有优势，因此我们集中在这个选择。我们从组件的InPort中的每个状态开始，并将它们与结果OutPort状态连接起来。图二、具有InPorts、OutPorts和InPorts与OutPorts之间的通信序列的组件为了压缩组件的内部通信（参见图3），可以仅考虑由传入消息触发的状态转换（在InPort和OutPort中）的顺序来直接连接InPort和OutPort这种内部信息的压缩导致更好地理解组件功能和组件功能的概述，而不会被内部细节淹没。能力的存在或不存在可以用与组合系统相同的方式来检查（参见第3.2节）。PuLvermuller147...组分B组分A输入端出口A1平方米2M25R16R2r2 −> m34387组分C输入端口C9m31011通胀组件输入端口1fstObjectsndObjectM1组件输出端口1输入端口1M1输出端口R1R1M2M2OutPort2R2R3OutPort 2R2R3压缩图三. 压缩内部通信3.2构图的建模与验证除了单个组件与其质量标准的验证外，我们还专注于组件组成的描述和验证。在这一节中，我们首先介绍了组件组合的模型，然后提出了我们的方法来验证这样的组合。通过应用模型检查可以自动验证的一些重要问题如下：有没有可能两个特定的成分会相互作用？特定组件需要哪个环境？可 以指定路径（例如，组件对象的方法）或InPort或OutPort状态在组合系统中到达？我们给出一个简单的例子（cf。图4）用于演示所提出的基于模型检查的方法的使用。我们考虑图4的组分A和C的组成。 首先，我们从组件A和C的具体代码中抽象出来，用模型检查语言SMV [15]生成一个模型。然后，我们组合模型并插入表示组合的模型。在规范（SPEC）中，给出了一些规范，这些规范可以在组合模型中由模型检查器进行检查见图4。 组件A、B和CPuLvermuller148组分A的型号：模块主VAR状态01：boolean; ack01：boolean;状态02：boolean; ack02：boolean;state03a：boolean; state03b：boolean; ack03a：boolean; ack03b：boolean;状态04：boolean; ack04：boolean;状态05：boolean; ack05：boolean; state06a：boolean; state06b：boolean; ack06a：boolean;ack06b：boolean; state07：boolean; ack07：boolean; state08：boolean;ack08：boolean;m1：boolean; m2：boolean; r1：boolean; r2：boolean;confirm1：boolean; confirm2：boolean;return boolean;分配初始化（状态01）：= 0; init（state02）public int findDuplicate（nums）：= 0;init（state03b）：=0的整数;初始化（状态04）：= 0; init（state05）：= 0;init（state06a）：=0的整数;init（state06b）：=0的整数;初始化（状态07）：= 0;初始化（状态08）：= 0;初始化（ack01）：= 0; init（0）：=0; init（ack03a）：= 0;初始化（ack03b）：= 0; init（ack04）：=0; init（ack05）：= 0;初始化（ack06a）：= 0; init（ack06b）：=0; init（ack07）：= 0;int count = 0;--由于组成而分配（测试台）：m1：= 1;--假设方法 m1将被调用 m2：= 1;--假设方法 m2将被调用--连接点1：r1：= ack 05;--发送r1确认1：=r1;--返回--连接点2：r2：= ack 06 b;--发送r2确认2：= r2;--返回--*下一个（状态01）：=开始|state01&！ack01;下一个（ack01）：=state01;下一个（状态02）：=状态01&ack 01&m1|state02&！ack02; next（ack02）：=state02;下一个（状态05）：=状态02&ack 02|state05&！ack05; next（ack05）：=state05;--连接点1下一个（state06a）：=状态05&确认1|state06a&！ack06a; next（ack06a）：=state06a;下一个（state03a）：=state06a&ack06a& m2 |state03a&！ack03a; next（ack03a）：=state03a;下一个（state06b）：=状态03 a&ack 03 a|state06b&！ack06b; next（ack06b）：=state06b;--连接点2：下一个（状态07）：=状态06 b&确认2|state07&！ack07; next（ack07）：=state07;下一个（状态08）：=状态07&ack 07|state08&！ack08; next（ack08）：=state08;PuLvermuller149下一个（状态03b）：=状态07&ack 07|state03b&！ack03b; next（ack03b）：=state03b;下一个（状态04）：=状态03 b&ack 03 b|state04&！ack04; next（ack04）：=state04;定义阿滕德：= state04;SPECAG（AF（开始->结束））组件C的型号：模块主VARstate09：boolean; ack09：boolean; state10：boolean; ack10：boolean;state11：boolean; ack11：boolean;m3：boolean; confirm3：boolean;start： boolean;ASSIGN初始化（状态09）：=0的整数;init（state）：=0的整数;init（state11）：= 0;init（ack09）：= 0; init（ack10）：= 0; init（ack11）：= 0;--由于组成而分配：m3：= 1; --假设方法 m3将被调用confirm 3：= ack 10;--return--*下一个（状态09）：=开始|state09&！ack09;下一个（ack09）：=state09;下一个（状态10）：=state09&ack09&m3|state10&！ack10; next（ack10）：=state10;下一个（状态11）：=状态10&ack 10|state11&！ack11; next（ack11）：=state11;定义state11;SPECAG（AF（start -> atendC））组合模型：（扩展SMV语言）--A --> C：--REPLACEinC：--start--> startCatend --> atendC--分配：--分配m3：= r2;confirm2：= confirm3;startC：= m3;SPECAG（AF（start -> r2 -> r1 -> atend））PuLvermuller150建模图4所需的每个状态都被定义（VAR）和初始化（ASSIGN）。方法调用也由状态表示（m3：= 1表示方法m1被调用）。基于时序逻辑，我们通过定义必须满足的条件来表示状态转换。比如说，next（state01）：= start|state01&！ack01;意味着如果start为真，则到达state01，或者state01为真，但ack01为假。连接点指示组件可以与另一个组件组合的位置组合模型描述了状态机（表示组件）如何在这些连接点连接根据组合模型组合A和C的模型导致组合系统的模型。可以使用模型检查工具SMV针对组合模型中给出的规范来检查该模型。示例规范AG（AF（start-> atendC）这意味着它总是为真（总是全局的，AG），总是在未来（AF），状态atendC将达到时，在状态开始。模型检查器可以检查此规范是否已满。4相关工作本文提出的方法是早期工作的扩展，该工作定义了静态版本模型[17]，该模型基于贝尔实验室和[19]的先前工作。在[25]中也可以找到通过版本对系统配置进行形式化描述的基础。在[3]中可以找到一种使用逻辑来描述方面依赖性的替代方法。与所提出的基于模型检查的方法的逻辑方法扩展与时序逻辑考虑到动态组件的行为。处理文件和规格的方法是相关的。基于模型检查的方法中的模型和规范可以被视为计算机可读文档。特别地，代数规范[21]的目标是提供一种允许完全自动化地转换为可执行程序的规范。与我们的方法相反，预计将有一个完整和正式的规范，该规范已被证明仅在一些高度专业化的领域是可行的。生成式编程[5]已经包含了检查系统单元的组成的思想但对混凝土成分检查不集中.一个有趣的例外是D.巴托里[2]。在GenVoca模型中，组合物用类型方程描述。设计规则检查机制检测与语义正确性相关的非法组件组合。这是一种分层的方法，因此限制了组合的可能性。此外，没有考虑动态行为。PuLvermuller151例如，德累斯顿大学[20]目前在描述和处理非功能性质方面的研究可能是一个有前途的补充。他们的目标是明确指定（甚至量化）系统属性，从而正确性，因此，可能是我们的方法的一个重要输入。所提出的基于模型检查的方法旨在支持特征交互问题。在现有系统中插入新功能可能会导致系统中出现非预期的影响。这种情况被称为“特征交互问题”，并且主要在电信领域进行了探索[23]。处理电信以外的特征干扰的第一种方法已经开始[18]。在[18]中，可以找到定义、指定和建模特征的方法以及探索关于干扰检测的现有代码特文特大学目前正在进行可合成性和合成学的研究[8]。启发式的组合信息可以作为输入到我们的方法，然后，能够检查他们在一个具体的组成系统。我们的方法有类似的方法验证的pro-toconstructions，但集中在内部，而不是外部行为。协议检查是保证组合正确性的一个重要问题。因此，这项工作是对我们方法的补充然而，尽管我们的方法支持协议的验证，但这个问题并没有得到关注。使用模型检查一般协议验证将意味着模型发送协议和检查它对指定的协议，这是预期的。我们的方法并没有将发送协议映射到协议内，而是集中在组件的内部问题上。我们将组件的入协议映射到它的出协议，允许我们检查某个组件是否完成了其接口中定义的任务。 它可以与功能性相比较， 一个试验台。此外，虽然一般的协议检查veri es语法结构，我们的方法的目的是在语义水平。5总结和结论应用模型检查，可以检查组件和组成的正确性。虽然一个完整的证明通常是不切实际的，我们的方法允许开发人员决定的规格和实施细节的水平考虑。系统单元及其组成被转换（抽象）为模型。该组合物是通过组合模型来实现的，这些模型可以针对给定的规格进行检查在第2节中，我们列出了一组正确性方法的要求。我们的基于模型检查的方法允许在实现组合之前和之后进行广泛的检查我们抽象的具体实现提供明确的模型和规格。虽然，模型检查语言是使用未来的工作将集中在更合适的局域网，PuLvermuller152这些语言可以转换为模型检验语言。由于不需要提供完整的模型或规格，并且在系统寿命期间可以随时插入额外的详细信息，因此满足了部分规格和零碎增长的要求。 支持系统单位的本地验证以及压缩。检查过程的效率取决于工具。基于模型检查的方法自动利用模型检查概念和工具的改进。由于我们的方法的主要思想是概念性的，我们依赖于具体的工具。可以使用不同的模型检查器实现。该方法是基于时间逻辑的原则。在未来的工作中，我们将专注于进一步适应更面向硬件的模型检测领域的组合。例如，必须详细说明软件特定的参数传递在规范级别上，[17]中的静态版本控制方法将通过时间条件进行扩展。这允许简洁和一致的表达所有可用的条件来定义一个正确的版本。通过将代码中的特定功能描述为模型和规范，基于模型检查的方法可以用于功能交互问题领域，这将在未来的工作中进行探索我们的方法将是欧盟EASYCOMP项目[7]所谓的“组合机”。引用[1] Achermann，F.，和O. Nierstrasz，应用=组件+编程-Piccola之旅，，in：M. Aksit，编辑，软件架构和组件技术（2001）。[2] Batory，D.，和B.Geraci，GenVoca生成器中的组合验证和主观性，在：IEEE软件工程学报，1997年，pp.67 {82.[3] Brichau，J.，声明性可组合方面。高级关注点分离研讨会论文集，OOPSLA，2000年。[4] Coplien，J.，重新评估建筑隐喻：走向零碎的增长。IEEE Software SpecialIssue 的 客 座 编 辑 介 绍 。 IEEE Software Special Issue on ArchitectureDesign16（1999），pp.40 {44.[5] Czarnecki，K.，和联合Eisenecker，\Generative Programming - Principle andApplications，Addison-Wesley，Heidelberg，2000。[6] 杜昂斯河O. Motelet和M. Sudholt，从监测角度看，作为一个方向和P rogramming，技术报告（2001年）。[7] EASYCOMP IST-1999-14191http://www.easycomp.org，（2001）.[8] Glandelia，M.和A.林志玲，复合式推理的形式基础，OOPSLA 2001 ASoC研讨会，（2001）。PuLvermuller153[9] Gouthier，P.，和S.桥，《设计系统程序》，Prentice Hall，EnglewoodClifs，1970年。[10] Heuzeroth， D.， 和R. Reussner， 二进制组件的动态耦合及其技术支持 。 ， in ： Proceedings of GCSE'99 Young Researchers Workshop ，Ergoman，1999.http://www-pu.informatik.uni-tuebingen.de/users/speck/GCSE99青年研究/[11] Holzmann，G.，计算机协议的设计和验证，”Prentice Hall，EnglewoodClis，1990年。[12] Kiczales，G.，J. Lamping，A.门德赫卡尔角前田角Lopes，J. M. Loingtier和J. Irwin，面向对象编程，在：LNCS 1241，ECOOP'97会议记录，欧洲面向对象编程会议（1997），pp. 220 {241.[13] Lauder，A.和S. Kent，EventPorts：Preventing Legacy Entware. 第三届国际企业分布式对象计算会议（EDOC 99）（1999年），pp. 224 {232.[14] Ludwig，A.和D.何志华，元程序设计，2000年，第二届国际软件工程研讨会论文集，北京，北京（2000）。[15] McMillan，K.， \Symbolic Model Checking，”Kluwer Academic Publishers，1993.[16] 迈耶湾，《面向对象的软件构造》，Prentice Hall PTR，Upper SaddleRiver，NJ，1997，第二版。[17] 普武鲁Ller，E.，A.Speck和J.Coplien，AVersionModelforAspectDependency Management. 2001年国际软件工程研讨会论文集（GCSE 2001），LNCS 1241（2001），pp. 70 {79.[18] 普武鲁Ller，E.，A. S pe ck，M. D'Hondt，W. DeMeuter和J. Coplien，WorkshoponFeatureInteractioninComposedSystems ， ECOOP2001（2001）。[19] Rochkind，M.，源代码控制系统，IEEE软件工程学报SE-1（1975年），pp。364 {370.[20] Schill，A.，H. Hartig，H.Hussmann，K.迈斯纳K.迈耶-韦格纳和A. 张文，《量子力学与自适应性》，清华大学出版社，2001年。[21] Schmitz，C.，Spezi kation objektorientierter Systeme（2000），wSI-2000-14.[22] Szyperski，C.，\组件软件。Addison-Wesley，ACM出版社，纽约，1997年。[23] 滑铁卢大学，http://se.uwaterloo.ca/~s4siddiq/fi/fip.html，\Feature Interaction Problem，”（2001）.PuLvermuller154[24] Vanderperren，W.，和B. Wydaeghe Towards a new Component CompositionProcess ， in ： Proceedings of IEEE ECBS 2001 ， Eighth Annual IEEEInternational Conference and Workshop on Engineering of Computer BasedSystems（ECBS）（2001），pp. 322 {329.[25] Zeller，A.，和G. Snelting，Uni ed Versioning through Feature Logic，ACMTransactions on Software Engineering and Methodology6 （ 1997 ） ， pp.398 { 441.
我的内容管理
展开
