数据流软件的可测试性分析

理论计算机科学电子笔记116（2005）213-225www.elsevier.com/locate/entcs数据流软件Thanh Binh Nguyen，Michel Delaunay，ChantalRobach1LCIS-ESISAR，50，rueBarth'el'emydeLaemas，Valence，26902，France摘要本文是关于数据流软件的可测试性分析. 我们描述了一个应用程序，SATAN方法允许测量数据流设计的可测试性，用于分析关键数据流软件（如航空电子软件）源代码的可测试性。首先提出了将数据流设计生成的源代码转换为静态单分配（SSA）形式，然后描述了将SSA形式自动转换为可测性模型的算法因此，分析可测试性模型可以允许检测引起可测试性弱点的软件部分。关键词：程序分析，可测试性措施，数据流软件.1介绍在软件开发过程中，确认和验证阶段发挥着重要作用，其中测试是一项至关重要的任务。在这项任务中，必须揭露错误。然而，测试增加了软件的可靠性，它永远不能确保软件中没有错误。此外，当软件相当复杂时，测试任务是耗时且成本高的。这就是为什么在过去的几年里，人们研究了一些可测试性度量，以帮助评估测试软件的易用性/困难性在本文中，我们专注于从数据流设计生成的源代码的可测试性分析。该分析可用于：• 为了识别设计/代码中导致缺乏可测试性的部分1电子邮件：{Binh.Nguyen-Thanh，Michel.Delaunay，Chantal.Robach} @ esisar.inpg.fr1571-0661 © 2005由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2004.02.078214T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213• 为了帮助设计人员和测试人员在设计阶段和测试阶段分配资源• 为了比较设计可测试性和生成的代码可测试性以便评估编码过程，• 提高软件的可靠性。为了降低测试成本和保证软件质量，对关键软件进行可测试性分析是非常必要的Le Traon和Robach [6]在以前的工作中提出了一个可测性模型，该模型在SATAN（系统自动可测性分析）工具中实现，所提出的可测性模型是一个二分图，它被证明是适用于模型数据流设计。但是，它不能应用于分析这些设计或这些设计中使用的组件代码生成的源代码：因为源代码通常是用命令式语言（如C或ADA）生成或描述的。因此，我们最近提出了使用静态单一分配（SSA）形式来应用该模型进行组件代码的可测试性分析[8]。从数据流设计生成的代码实际上是设计中使用的组件的代码的集成。因此，可以使用SSA形式作为源代码的中间表示来分析代码的可测试性。然后，我们提出了一个算法，自动转换的SSA形式的可测试性模型，这是用来计算源代码的可测试性措施。本文的结构如下。第二部分是相关的工作。第3节简要介绍了SATAN工具的原理，该工具允许对数据流设计进行可测性分析。第4节介绍了SATAN工具的扩展，以分析代码的可测试性。第5节描述了自动计算可测性度量的算法。 第6节介绍了一个案例研究。最后，我们在第7节给出了我们的结论。2相关工作关于软件可测试性的研究已经有了一些成果。每一个都进行了研究，以分析特定应用领域内的可测试性。Freedman [3]通过定义可观测性和可控性概念，提出了非确定性软件组件的可测试性度量;这些可测试性度量仅通过检查T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213215输入和输出域。Voas和Miller [13]还提出了基于软件组件的输入和输出域的可测试性度量。 这两种方法都允许通过分析功能规范来测量组件级别的可测试性;它们可以用于根据可测试性对组件进行排名。Voas和Miller在[14]中提出了PIE（Propagation，Infection andExecution）技术来分析软件可测试性;该技术通过动态分析（即在运行软件时）来测量 一些软件复杂性度量也被认为是可测试性度量的替代品，例如McCabeVoas和Miller、McCabe和Nejmeh提出的所有这些方法都只能应用于源代码。Jungmayr [4]提出了面向对象软件中静态依赖的可测试性度量。在通信软件领域，Petrenko和al。[11]研究了通信软件的可测试性，该软件由有限状态机的组合建模，然后Karoui和al。[5]提出了一种基于关系模型的通信软件可测性度量方法。Le Traon和Robach [6]提出了特别针对数据流设计的可测试性度量，这些设计由组件图以图形方式表示。3SATAN工具在本节中，我们介绍了SATAN工具的一些原理，用于分析数据流设计的可测试性[6]。在SATAN工具中，软件的可测试性是基于软件组件的可控性和可观性。可控性被定义为将数据从软件的输入端转发到组件的输入端的容易程度。可观察性被定义为将数据从组件的输出传播到软件的可观察输出的容易程度可测试性分析建立在功能模型的基础上，功能模型是表示软件内信息传递的有向图。然后，通过关联图对信息量进行评价，计算出该模型的可测性测度。我们以图1中的数据流设计为例来说明功能模型的表示。在该图中，o1和o2是一对输出，o1是一个布尔输出，用于验证o2是否是有效输出;i 1、i2、i3、i4、i5和i6是输入;comp 1和comp 2是比较组件;或者是逻辑组件;switch是选择组件;prec是存储组件216T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213i1comp1i2或O1I1i3组件2I1开关O2I4precI5I6成分Fig. 1. 数据流设计3.1功能模型通过软件对信息传输进行建模的原理包括在称为信息传输图（ITG）的同一图上表示控制和数据流方面。它是一个没有圈的二部有向该模型由位置、过渡和边缘定义。这些地方是：• 模块，它是运算符或组件;• 输入，这是软件的输入;• 输出，这是软件的可观察结果。输入和输出是终端节点。 转换表示位置之间的信息传递模式。数据流设计建模考虑了三种基本的信息传输模式（图2）：结归因选择图二.信息传递模式• 连接模式：当目的地需要来自两个来源地的信息时;• 归属模式：当目的地需要来自多个来源地之一的信息时;• 选择模式：当相同的信息从源地到多个目的地时。边缘连接地点和过渡。在图形表示中，模块用圆圈表示;输入和输出用圆表示;转换用条表示。T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213217I1I6I2T14I1T15I3T12comp1comp2T13precI5I4T10T11或T9then.prelse.prT8O1T6 T7res.pr开关I1T4T5then.sw else.swT2T3res.swT1O2图3给出了上述示例的ITG。图三.信息传递图请注意，在ITG中，假设一个周期（如果存在）执行一次。3.2流动ITG用于识别贯穿软件的信息路径，称为数据数据流是从一些输入到一个或一些输出的信息路径。它包含一组地点、过渡和边。因此，一个子图可以被认为是一个子图;它是一个基本函数，可以独立于软件的其余部分，因为它从输入变量计算输出变量。在上图中，确定了四个箭头。为简单起见，每个子流程的特征在于它包含的模块集和它计算的输出Fi ={modules|输出}：F 1={or，comp1，comp2|o 1}F 2={res.sw，else.sw，sw，or，comp1，comp2|o 2} F 3={res.sw，then.sw，res.pr，sw，then.pr，or，prec，comp1，comp2|氧F 4={res.sw，then.sw，res.pr，sw，else.pr，or，prec，comp1，comp2|氧例如，在图3中以粗体显示了流程F2.3.3测试策略一旦确定了一组测试流，就可以根据测试策略来确定一组测试目标。测试策略是一组有序的流程，必须通过软件来执行。测试策略对应于测试数据选择标准。选择标准是通过执行选定的流程来覆盖模型中的每个模块至少一次218T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213模块SATAN中使用了两种测试策略：渐进结构策略（小起点）和交叉检查策略（多线索）。交叉检查策略是基于选择一个子集的故障流，满足覆盖所有的模块：所有选择的故障流的行使，收集可能的信息的故障，并对这些信息进行诊断分析。这种策略在简单故障（只有一个模块有缺陷）的情况下是有效的。渐进的结构策略是基于一个逐渐覆盖的模块，通过选择一个越来越复杂的覆盖模块的数量方面，和一个新的流程进行测试，只有当在以前的流程中检测到的故障被纠正;一个最小的子集的流程被选择，以便所有的模块都被覆盖。该策略在多个故障（多个模块有缺陷）的情况下有效。此外，我们最近在[9]中提出了通过使用一些可访问性措施来改善这两种策略的有效性。因此，应用测试策略可以在确保ITG中的所有模块都被覆盖的同时，降低成本3.4可测试性措施可测试性是基于软件的每个流程的模块的可控性和可观性。可控性度量通过所考虑的流程从软件的输入估计模块的输入上可用的信息量。可观测性度量分别从模块的输出该原理如图4所示。数据流设计见图4。模的能控性与能观性此外，为了计算通过数据流的信息损失，我们需要引入模块容量的概念。模块容量是模块输出端从其输入端获得的信息量：这表示通过模块的信息损失。让IF是表示流程F的输入的变量; OF是表示流程F的输出的变量;表示模块M的输入的变量;表示模块M的输出的变量。T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213219M←M模M在连续流F中的可控性度量由下式给出CO（M）=T（IF;IM）FC（I）其中，T（IF;IM）是模块M从流F的输入IF接收的最大信息量，C（IM）是模块M在被隔离的情况下将接收的总信息量。类似地，模M在模流F中的可观测性度量由下式给出OB（M）=T（OM;OF）FC（O）其中T（OF;OM）是模块M的输出O M可以接收的最大信息量，C（OM）是模块M可以在其输出上产生的总信息量模M的可测性度量在模F中是可控性度量和可观测性度量的函数，定义为两个值：T EF（M）=（COF（M），OBF（M））可测试性测量计算在[12]中有更详细的描述。4代码可测试性分析由于我们的目标是应用SATAN工具来分析代码源的可测试性，因此我们使用SSA形式（静态单一分配）[2]将代码转换为数据流表示。这种SSA形式主要用作编译技术中各种经典代码优化算法的平台测试性分析基于SSA形式。在本节中，我们首先介绍SSA形式，然后描述允许对源代码进行自动可测试性分析的过程。4.1SSA形式实际上，SSA形式允许从程序（软件）的控制流程图来表示数据流程方面。将一个程序转换成SSA形式分两步实现。在第一步中，在程序控制流程图的每个连接节点处引入一些特殊的Φ-函数。在节点X处的Φ-函数具有形式V Φ（R，S，.），其中V、R、S、.是变量和操作数R，S，.是X的控制流前导的数量。此Φ函数根据控制流程合并变量的不同值以生成新值。在第二步骤中，变量R、S、.都被新的变量V1，V2，V3代替了使得每个220T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213仅通过对Vi的一次赋值来实现对Vi的使用。事实上，在整个程序中只有一个赋值给Vi。在[1]中更详细地描述了SSA构造。它在GCC 3.x编译器中实现。例如，将下面的函数delta转换为SSA形式如图5所示。图五. Delta函数及其SSA形式在这个例子中，两个Φ函数被插入到连接节点上，以确定变量a和b的值;然后变量被重命名。此外，当将程序翻译成SSA形式时，GCC编译器不考虑指针。因此，我们提出了一些扩展的程序，而不会失去其语义。 对于一个程序来说，扩展由两个附加部分组成：一个“序言”和一个“尾声”。在程序的开头，插入的序言允许用局部变量替换指针。同样，在程序结束时，插入的尾声允许用指针替换插入的局部变量。SSA形式有一些重要的性质：变量的每一次使用只依赖于这个变量的唯一定义;原始程序和它的SSA形式有相同的控制流程图;原始程序和它的SSA形式有相同的语义。4.2分析过程从SSA形式，我们可以构造相应的ITG。然后，为了使用SATAN工具来计算可测试性度量，即可控性和可测试性度量，我们必须将ITG的每个模块与容量相关联。该模块容量允许评估通过模块的信息损失。具有模块能力的ITG被称为信息传输网（ITN）。我们提出了一个测试性分析的过程，如图6所示。在这个过程中，一个C程序首先被GCC编译器翻译成SSA形式。然后，SSA表格被翻译成ITG。ITG的每个模块都与其生产ITN的能力相关联最后，SATAN工具从ITN计算可测试性度量。T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213221C程序SSA形式测试人员和设计人员指南ITG可测试性措施撒旦ITN翻译ITG -> ITNGCC翻译SSA -> ITG见图6。测试性分析过程5功能模型在本节中，我们简要介绍如何将SSA格式转换为ITG，然后转换为ITN。5.1翻译成ITGGCC生成的SSA格式用一种低级语言RTL（RegisterTransferLanguage）表示为了便于翻译成一个ITG，我们建议的SSA形式转换成一些中间表示。 首先，SSA形式被转换成一个四元组的列表，其中只包含ITG所需的信息。然后，四元组的列表被转换成一个操作符的图表，这是接近ITG，然后被翻译成ITG。这个翻译器以Pascal伪代码给出，如下所示：翻译员-SSA-ITG（SSA-表格）四元组列表←转换成四元组（SSA形式）运算符的转换←转换成运算符（四元组列表）ITG ←构造ITG（运算符的转换）5.2翻译成ITN一旦我们从SSA表格中获得ITG，我们需要通过添加所有模块容量将ITG转换为ITN。正如我们上面所说的，模块容量是模块输出端从其输入端获得的信息量。因此，我们首先确定ITG中每个模块的输入和输出的类型。然后，将评估所有模块的能力。最后，由ITG和模块容量构建ITN。该翻译器如下所示：ITG-ITN（SSA-form，ITG）输入输出类型←确定输入输出类型（SSA形式）模块容量←计算容量（输入输出类型）ITN←构造ITN（ITG，模块容量）222T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213计数1输入陀螺仪1.0BARYC_2版权1SUB1 MULT1MULT2 SUB2PREC10.0 b_init温度m陀螺输出m陀螺输入科詹k1can g_tds_k1acq_g g_tds_k0acq_gD5.1D2.1b_tgyro_non-v最大温度特格PREC20.0 b_inittgyro_v_intgyro_v_outtgyro_non_vD6COPY3COPY2开关COMP2或COMP1它们是用Lisp语言实现的，并集成在SATAN工具中。6为例在本节中，我们展示了THALES航空电子公司提供的数据流图上的应用程序，然后我们还将我们的方法应用于GALA工具2从该图生成的代码图7中给出了称为sub-THT的图。见图7。 案例研究的子THT图在该图中，BARY C是计算组件;COPYi是将值分配给输出;COMPi是比较组件;OR是逻辑组件;MULTi和MULTj分别是减法和乘法组件;SW ITCH是选择组件;PRECi是存储组件。该图有多个输入和输出。特别地，两个输出b tgyro non v和tgyro non v形成一对：b tgyro non v的布尔值确定tgyro non v的值是否有效。这个图是为THALES航空电子公司使用的一个航空电子软件设计的。我们首先分析图，然后分析从这个图生成的代码。6.1图分析ITG直接从图中构造。 它在图8中给出。2GALA工具由THALES航空电子公司开发，用于指定和生成航空电子软件T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213223b_initcount1cn14红外陀螺仪CN17PREC1m陀螺输入BARYC然后1其他1res.BARYCres.PREC1COPY3m陀螺输出res.COPY3科詹SUB1K1canres.SUB1滕帕明MULT1g_tds_k1acq_gyrores.MULT1坦帕麦斯MULT2g_tds_k0acq_gyrores.MULT2COMP1 COMP2分辨率COMP1分辨率COMP2SUB2res.SUB2或b_initres.ORtgyro_v_inCN104PREC2Switb_tgyro_non-v然后2其他2然后3 else3res.PREC2res.SWITCOPY2tgyro_v_out版权1res.COPY2res.COPY1tgyro_non_v特格里见图8。 图子THT在这个ITG中，SATAN工具确定了12个流。然后计算每个流程中每个模块的可测性度量。一个模块在不同的流程中可以具有不同的可测试性值。因此，可以通过检查每个流程中每个模块的可测试性来进行精细分析，然后识别出所有可测试性低的模块。这种模块的可测试性应该得到改善，或者必须仔细测试。然而，在本文中，我们只给出了最小可测模块在每个队列中的可测性，因为这个模块是最难测试的队列。该模块的可测性（可控性、可观性）可以代表该流程的可测性。在这种情况下，在12个连续流中，6个连续流具有最大的可测性（1.0，1.0），另外6个连续流具有最大的可控性但具有低的可观测性（1.0，0.0833）。因此，在最后6个流程中的一些模块的可观测性需要改进。6.2代码分析我们现在分析GALA工具从图子THT生成的代码。由于代码比图包含更多的细节，因此从代码获得的ITG比从图获得的ITG包含更多的元素（模块，转换，边缘）。在此，由于篇幅有限，我们不介绍国际贸易小组。SATAN工具在ITG中识别出42个流。来自代码分析的数据流的数量相对于224T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213从图表分析中得到的图表。随着ITG的详细化，图表的数量也越来越多。表1给出了两个分析水平的信息。表1两个层次分析分析数量的模块的转变数量图3610412代码4813442在度量方面，42个样本流中有20个样本流具有可测性（1.0，1.0），22个样本流具有可测性（1.0，0.0833）。比较从两个层次的分析得到的措施，我们说，他们是非常相似的。因此，我们可以说编码过程对可测试性没有影响。然而，一些模块应该被审查，以改善可观测性措施。7结论本文提出了一种生成代码源和数据流设计的可测试性分析方法。SSA形式的使用允许用我们的SATAN工具来分析代码的可测试性，该工具已成功地用于分析数据流设计的可测试性。代码级的分析比设计级的分析复杂，但它给出了更详细的可测试性度量。特别是，这种方法有助于在使用前分析航空电子软件的可测试性，这是认证机构所要求的。此外，代码的可测试性分析可以帮助识别软件再工程中的低测试性部分。由于SATAN方法可以在设计级和代码级分析数据流软件的可测试性，因此可测试性分析可以贯穿于整个软件开发项目。引用[1] Briggs，P.，T. Harvey和T.李明，静态单一作业建构，技术报告，国立台湾大学，1995年。[2] 塞隆河，J. 费兰特湾K. 罗森，M。N. Wergman和F.K.陈文，静态单赋值形式与控制依赖图的计算机辅助设计，北京大学出版社，1991。[3] 弗里德曼河美国，软件组件的可测试性，IEEE软件工程学报，17（1991），553[4] Jungmayr，S.，可测试性度量与软件开发，第12届国际软件度量研讨会论文集，德国马格德堡，2002年。T.B. Nguyen等人/理论计算机科学电子笔记116（2005）213225[5] Karoui，K.，和R.张文，通信协议的可测试性分析，北京：北京科技出版社，2001。 1050，Départ em entd ' In form a t i q ue et de R e c h e r c h e O p é era t io n ne lle，Facul t e d es A r t e t e s Science nces，Universit e m n t re al，1996.[6] Le Traon，Y.，和C.陈文辉，资料流设计之可测性量测，第四届国际软体设计研讨会论文集，台北，1997。[7] McCabe，T. J.，复杂性度量，IEEE软件工程汇刊，SE-2（1976），308[8] 阮氏T. B、M. Delaunay和C.陈晓，软件构件的可测试性分析，软件工程学报，2002年，第1期，第422-429页[9] 阮氏T. B、M. Delaunay和C. Robach，数据流软件的测试标准，第10届亚太软件工程会议论文集，泰国清迈，2003年，332[10] 奈杰梅湾一、Npath：执行路径复杂性的复杂性度量及其应用，ACM通信，31（1988），188[11] Petrenko，A.，R. Dssouli和H.张文，《协议测试系统的可测试性评价》，国际协议测试系统研讨会论文集，法国，1993。[12] 罗巴赫角，和S.李文，基于信息的可测试性度量，《硅设计会议论文集》，第429[13] Voas ， J.M. ， 和 K. W. Miller ， Semantic Testability for Software Testability ， Journal ofSystems and Software，20（1993），207[14] Voas，J.M.，和K. W.米勒，软件可测试性：新的验证，IEEE软件，12（1995），17