UML活动图模型中错误的定位工具开题报告

学士学位论文开题报告论文题目：UML 活动图模型中错误的定位工具专 业：计算机科学与技术本 科 生：学 号：指导教师：北京航空航天大学计算机学院2013 年 3 月 8 日学士学位论文开题报告北京航空航天大学计算机学院 I目录1 题目背景与意义 .11.1 课题来源 .11.2 选题的背景与意义 .12 研究现状 .22.1UML 模型的一致性检查 .22.2 模型检查 .22.3UML 测试调试工具 .32.4 小结 .33 研究内容与解决方案 .33.1 研究目标 .33.2 研究内容 .43.2.1UML 活动图的处理 .43.2.2 错误定位的算法 .43.3 解决方案 .44 关键技术及难点 .54.1UML 活动图的读取及元素的处理 .54.2 语义错误的检查定位的算法 .75 进度安排 .96 参考文献 .10学士学位论文开题报告北京航空航天大学计算机学院 11 题目背景与意义1.1 课题来源课题来源于实验室在软件的自动化调试方面的科学研究。1.2 选题的背景与意义众所周知，软件工程主要包括了需求获取、项目策划、建模分析设计、编码、测试以及部署交付等过程。研究成果表明，70%的错误是在软件工程生命周期中的早期被引入（即在模型设计中引入）；而错误中的80%只有到了系统开发后期的测试阶段之后才被发现，而错误的修改成本大大增加。惠普、IBM、以及其他组织的研究人员发现，在构建软件模型阶段清除一个错误，其成本仅仅是在开发过程的最后阶段做同样事情的十分之一到百分之一12。因此针对于设计模型的错误检查研究，有着非常重要的意义，可以大大降低错误检查的成本，有效保障软件质量。随着各种系统和软件的规模与复杂度增加，模型驱动技术被广泛的应用于系统的构建、静态和动态行为刻画与分析等方面，模型作为对系统行为的刻画发挥着越来越重要的作用。统一建模语言（UML）作为一种描述能力强大、涵义直观且被工业界广泛使用的可视化建模语言，提供了多种图形元素，从静态结构和动态行为等多角度及不同层次刻画系统特征和运行环境3。活动图是UML2.0中动态行为建模中的重要模型之一，可以对系统功能过程实现进行刻画，是一种流程刻画的图形建模语言，它结合了Jim Odell 的事件图、SDL(规约和描述语言)状态建模技术、工作流建模以及Petri网等。活动图的应用领域广泛，且可以对于不同层次的过程模型进行刻画，包括对于工作流建模、执行算法建模以及代码层次模型等4。学士学位论文开题报告北京航空航天大学计算机学院 2随着活动图在系统建模中的应用越来越多，活动图模型的正确性检测与错误定位也为复杂系统的错误检查和定位提供了一种方式，即利用活动图作为系统功能的过程模型，结合实际观测或者需求期望来判定该模型是否存在错误，如果存在错误，并进一步自动化进行错误定位。选题具有一定的意义。如果能在建模阶段就自动化的查找包括语法和语义的错误，那么我们就可以大量的减少在后期编程阶段或者测试阶段再次发现错误所需要的工作量并减轻修改这些 bug 所需要的精力财力物力。2 研究现状统一建模语言（UML）作为一种描述能力强大、涵义直观且被工业界广泛使用的可视化建模语言，提供了多种图形元素，从静态结构和动态行为等多角度及不同层次刻画系统特征和运行环境。当前针对于UML 错误检查的相关研究主要集中在UML一致性研究、基于模型检查技术的UML 模型错误检查以及UML测试调试工具。2.1UML 模型的一致性检查UML模型的一致性检查是最常见的错误检查，它包含了语法检查和语义检查等，对于语法检查是将模型看作一组相互关联的元素，通过把元素之间的关系限定到一定模式，防止模型中产生某些类型的矛盾，这类方法的基本特征是以模型的语法结构为基础，定义元素之间的一致性约束。通常利用模型间语法结构等建立一致性约束，进一步执行模型检查。语义检查则通过形式化语义模型，包括进程代数、Petri网、R-演算等理论，实现语义层面一致性的判定。2.2 模型检查针对于UML的模型检查，通常将模型检查的成果应用到 UML错误检查中，学士学位论文开题报告北京航空航天大学计算机学院 3通常的方式是将UML模型转化为常用的模型检查工具输入模型，并建立属性检查期望。模型检查是针对于UML模型错误检查中最常见、也是应用最广泛的，通常将UML模型转化为SMV、SPIN 等主流的模型检查工具所支持的中间语言5，然后利用模型检查工具，来判定UML模型是否满足指定的性质。模型检查主要用于检查功能属性，例如无死锁性、活性、安全性等，缺点除了状态空间爆炸问题外，对于检查过程的推理过程缺乏直观的刻画，对于度量模型不统一的检验无法有效处理。2.3UML 测试调试工具UML能够允许开发者在一个较高的抽象层次，利用活动图、状态机和顺序图等来对系统行为进行描述。为了进一步便于模型驱动开发，开发者需要增加对于UML模型的调试和测试。UML测试调试工具则是在UML建模环境中，实现针对于模型的虚拟执行环境，加入测试和调试的功能, 常见的工具如IBM在以色列的Haifa研究室提供的 Model debugger，基于Eclipse的代码调试器，提供了相似的视图：调试、变量和断点67。2.4 小结通过以上的总结，我们可以发现，目前主流的几种UML 错误检查的方法都各自存在优缺点。UML模型的一致性检查多用于进行语法的检测；而模型检查主要用于检查功能属性，对于检查过程的推理过程缺乏直观的刻画，对于度量模型不统一的检验无法有效处理；UML测试调试工具则主要是针对于人工的手动调试8。选题则是主要针对于语义错误的自动化检测和定位，通过对实际运行状态和期望状态的比较来进行进一步的相对精确的错误定位。学士学位论文开题报告北京航空航天大学计算机学院 43 研究内容与解决方案3.1 研究目标众所周知，现在有很多的错误自动检测系统，但是对于错误的定位方面仍然不是很好。我们的主要研究目标是在软件工程的建模阶段能够自动化的发现并定位出模型中所存在的错误，这样我们就能更多的减少测试阶段发现的错误数量，并进一步减少改正错误时所需要花费的代价。而随着面向对象编程的越来越广泛的应用和推广，UML 建模语言也在众多领域有广泛的使用，而这门语言本身也是一种描述能力强、涵义直观的可视化建模语言。因此我们的选题主要是针对于 UML 活动图，通过对活动图的解析、对其中元素和对象的处理，能够自动的检测并定位其中的语义错误以及产生错误的原因，从而在建模阶段就能发现更多的错误，减少后期测试时发现并改正错误的代价。3.2 研究内容3.2.1UML 活动图的处理UML 活动图中有许多的元素和对象包括了：活动、状态、转移（动作流） 、分支与合并、分叉与汇合以及泳道等等。在这里我们主要讨论的是比较简单的活动图（只含有活动、状态、转移、分支与合并） 。接下来需要研究的是怎样读入一个 UML 文件，并怎么样对这个文件进行操作，读取出其中的元素和对象，供下一步的使用。3.2.2 错误定位的算法如果我们要在一个 UML 活动图中进行错误的定位，那么就必须要有一个高效的错误定位算法。目前我们已经有了一个形式化错误定位算法，但是这个算法的提出是针对于所 C-kernel 语言，它是 C 语言的一个子集，这一语言所有变量和常量都是整型的。而我们的研究的对象是 UML 活动图，这其中有很学士学位论文开题报告北京航空航天大学计算机学院 5多不同之处，那么我们就需要对读取出来的 UML 活动图元素对象以及错误定位算法进行进一步的修改和转化，从而能够使我们的研究对象适应这个成型的算法。3.3 解决方案首先，对于 UML 活动图的读取，我们可以使用 starUML 的 export 功能将活动图导出成 XMI 格式或者使用可以直接操作 UML 的库。然而 XMI 的优点是使用扩展标记语言（XML） ，为程序员和其它用户提供元数据信息交换的标准方法。XMI 的目的在于帮助使用 UML 以及不同语言和开发工具的程序员彼此交换数据模型。XMI 也可用于交换数据仓库信息。正如我们都知道的，XML格式的文件中，定义了很有规律的标签，我们可以用高级程序语言（如 C+）对 XML 文件进行操作，从而得到了系统的活动图的结构，从而进行下一步的基于 XML 结构化的形式化的文件的操作 9。接着，我们将对象元素使用高级程序语言转换成错误定位算法所需要的格式从而进行下一步的操作。这其中，从 UML 活动图中读取的结构我们可以对应到编程语言中的某些结构，比如：UML 活动图中的活动就可以看成普通的顺序执行的操作语句；UML 活动图中的分支与合并就可以转换成编程语言中的判定、循环等等。最后，对于语义错误的检测和定位，我们将使用课题组提出的错误形式化定位算法。这个算法的提出是针对于所C-kernel 语言，它是C 语言的一个子集，这一语言所有变量和常量都是整型的。所以我们需要将活动图转换成的XMI中的元素的格式更改并对算法进行适当的调整，使双方能够进行匹配，从而能够使用这个成型的定位算法完成错误的定位。学士学位论文开题报告北京航空航天大学计算机学院 64 关键技术及难点4.1UML 活动图的读取及元素的处理首先，我们使用 UML 建模工具 starUML 来将已有的 UML 活动图导出成为 XMI（XML）格式的文件，在这个 UML 文件中，活动图中的各个元素都有对应的标签，如下：对于活动图中的活动：Activity图 4. 1UML 活动图中活动的表示Name 属性表示该活动的名称Outgoing 和 incoming 属性表示从这个活动出去的“转移”的 id 和进入这个活动的“转移”的 id。此外，可以在活动中加入操作，它表明是更加详细的步骤，操作是活动中执行的更小的步骤。分别在以下时刻可以产生操作，为某些变量进行赋值：在进入活动时发生的操作,entry；在活动进行时发生的操作,do；在离开活动时发生的操作,exit；这几个标签嵌套于该 ActionState 标签之中：进入活动时发生的操作：在活动进行时发生的操作：学士学位论文开题报告北京航空航天大学计算机学院 7在离开活动时发生的操作： Name 属性表示该操作的行为，由用户定义。对于活动图中的转移：图 4. 2UML 活动图中转移的表示Name 属性表示转移的名字。Source 和 target 属性分别表示源动作和目的动作。这其中还可以嵌套一个子标签，用来表示该转移所需要的条件。对于活动图中的分支与合并，它们的排列组合就类似于高级程序语言的条件选择语句和各种循环语句：ActivityActivityActivity图 4. 3UML 活动图中分支与合并的表示学士学位论文开题报告北京航空航天大学计算机学院 8这其中属性的意义同上，kind 属性为“branch”表示是分支合并。接下来是对于 XML 的操作，我们使用高级程序语言 C+来操作。但是，C+的标准库中并没有直接操作 XML 文件的方法，我们可以通过使用 C+的boost 库等方法来操作 XML 文件。4.2 语义错误的检查定位的算法选题的错误定位选择函数内调试形式化的错误定位算法1011，它在UML 活动图中应用的基本思路是：当活动图测试出现了一个失败的测试用例时，根据用户预期的程序输入和输出，从活动图中找出与用户预期矛盾的极小片段，比如：几个活动和转移流组成的一个片段。若此片段仍然较大，则通过不断的与用户交互，让用户标记其中正确的活动、转移，或者让用户进一步给出片段中变量在某些状态下的预期值，利用这些新的信息缩小片段的范围，直到最终定位到活动图中的一个错误。它的大概过程是：通过活动图的执行轨迹，根据用例的输入进行执行，每执行到一个状态（在某一条语句执行完毕后所有的变量的值） ，则用实际状态与期望状态相比较，从而一步步的定位错误的位置。与用户预期矛盾的极小片段的确定方法具体如下：符号执行，记录轨迹：根据失败的测试用例的输入，对活动图进行符号执行，记录每个变量在这一输入下的执行轨迹以及各个变量的状态。定位方程组生成：根据活动图的执行轨迹，从活动图中变量的值与预期值不一致的断点处，反向对执行轨迹中的每一个语句生成定位方程组。求解方程，定位错误：通过二分法反向找到使得定位方程组无解的第一个语句，由断点到此语句之间的与断点变元相关的语句构成了一个极小片段。学士学位论文开题报告北京航空航天大学计算机学院 9用户交互，缩小范围：一次定位到的片段通常范围较大，需要用户再次输入片段中变量在某个状态下的预期值，在此片段中再次定位错误所在的片段，不断重复这一交互过程，直到得到的片段足够的小，能够精确的定位到错误。算法所执行过程的活动图如下：互 互bug互 互 互 互 互 互 互 互 互 互 互 互 互 互 互 互 互互 互 互 互 互互 互 互 互 互 互 互 互 互 互 互 互 互 互 互 互 互互 互 互 互 互 互 互 互 互互 互 互 互 互 互 互 互 互互 互 互 互 互 互 互 互 互 ,互 互 互 互 互 互 互 互 互 互 互 互图 4. 4 形式化错误定位算法活动图5 进度安排2013 年 3 月 9 日2013 年 3 月 15 日 熟练掌握 UML 活动图的各个对象元素，以及它们在 XML 格式中标签标学士学位论文开题报告北京航空航天大学计算机学院 10示形式。2013 年 3 月 16 日2013 年 3 月 25 日 学习形式化错误定位的相关算法知识，并将 UML 活动图的元素转化到错误定位系统需要的对象的格式。2013 年 3 月 26 日2013 年 4 月 20 日 编写形式化错误定位系统部分的代码。2013 年 4 月 21 日2013 年 5 月 10 日 将 UML 活动图的解析与形式化错误定位系统结合完善系统，并进行测试。2013 年 5 月 11 日2013 年 5 月 25 日 撰写毕业设计论文并完成翻译工作。6 参考文献1 Roger S.Pressman. Software Engineering A Practitioners Approach. China Machine Press, 2007.2 D Galin. Software Quality Assurance: From Theory to Implementation. Pearson/ Addson-Wesley, 2004.3 C Lange, M Chaudron, J Muskens. In practice: UML software architecture and design description.Software, IEEE, 2006, 23(2): 4046.4 Booch. UML 用户指南. 人民邮电出版社, 2006.5 T Schafer, A Knapp, S Merz. Model checking UML state machines and collaborations. Electronic Notes