软硬件功能测试用例半形式化生成方法*

邓 辉，石竑松，张宝峰

（中国信息安全测评中心，北京 100085）

软硬件功能测试用例半形式化生成方法*

邓 辉，石竑松，张宝峰

（中国信息安全测评中心，北京 100085）

功能测试旨在保证软硬件正确性，降低生产成本。已有的功能测试均为黑盒测试，无法最大化地发现功能正确性问题。而半形式化方法可为最大化分析、验证软硬件正确性提供框架。因此，围绕功能入口，混合有限状态机、Petri网、顺序图，共同建模软硬件动静态特征及其功能属性，并建立模型简化规则。模型由功能入口使用方式、功能入口、功能入口触发迁移三部分组成，覆盖所有功能入口模拟测试场景，并最大化生成测试用例。最终，基于模型等价性，检查实现功能测试的描述。

软硬件功能测试；有限状态机；Petri网；顺序图；等价性检查

0　引 言

软硬件功能测试是软硬件开发过程中的重要组成部分［1］。为发现软硬件开发可能带来的错误，测试根据软硬件全生命周期中需求分析、设计、开发等过程的文档说明，设计确定测试点、测试用例及测试方法，验证和确认软硬件功能，确定软硬件功能的正确性和一致性，实现在软硬件交付前，尽快及尽早发现软硬件可能存在的与预定义、用户需求等的不一致性，以降低改进成本，减小因软硬件开发错误造成的破坏，最终确保软硬件的质量［2-3］。

一般来说，软硬件测试有着规范的处理流程，包括测试计划、方案以及规范的制订，制订后的实施和对实施所做的详细记录，以及基于记录撰写测试报告。

具体来说，软硬件功能测试的内容［4-5］包括：

（1）确认软硬件功能的正确性：一方面指确定软硬件实现了预期的功能需求；另一方面指为达到此功能需求，软硬件使用了正确的方式。

（2）确认开发过程的可行性：一旦软硬件功能测试发现某一功能存在错误，则说明开发过程存在问题，因此需确认软硬件开发过程是否可行，若不可行，需及时做出更改。从这个角度来讲，软硬件测试可促进提高整个开发过程的质量。

近年来，功能测试作为提高软硬件功能及开发质量的重要手段，在软硬件开发过程中越来越受到开发人员的重视［6］。据统计，目前针对软硬件功能测试的工作量已约占据整个软硬件开发工作量的40%左右，而测试成本占据软硬件开发成本的45%左右。但是，在已有的测试过程中，从开发人员的角度出发，针对大部分测试点设计的测试用例均为抽样方式。因此，存在测试用例设计的不完整或者说是存在完备性问题，使得功能测试的全过程可以发现软硬件在功能上存在的错误，而不能确保软硬件功能完全没有错误。这也是大多数软硬件在交付后投入使用时会出现很多bug的主要原因。因此，针对软硬件设计完整的测试点及测试用例生成方法是开发人员需要解决的问题［7-8］。

对于该问题，研究人员已经投入了大量时间和精力，企图从理论角度解决完备性问题。对于软件功能测试来说，目前已有的测试点主要分为单元测试、集成测试以及系统测试［9-10］。单元测试指在软件开发过程中，将软件的每一个最小单位模块作为测试点，设计测试用例；集成测试指将已测试的模块进行组装，将每一个组装作为一个测试点，设计测试用例；而系统测试指将整个软件作为一个测试点，进行黑盒测试。

设置测试点后，对应已有的测试用例生成方法主要包括因果图分析法、边界值分析法、等价类划分法以及错误推测法。其中，因果图分析法指利用图解法分析输入的各种组合情况设计测试用例；边界分析法指通过输入和输出的边界值设计测试用例；等价类划分法指为减低测试数目同时实现合理覆盖，通过选择适当的数据子集来代表整个数据集来设置测试用例；错误推测法指根据经验和直觉推测程序中可能存在的各种错误，并针对性地编写检查错误的测试用例。这四种方法均为黑盒测试，对于软硬件来说，均不利于实现问题的有效定位。

为建立通用的软硬件测试用例生成方法，本文首先抽取有限状态机、Petri网、顺序图的优点混合后，对软硬件功能的动静态特征及其功能属性进行抽象建模，并进行特征优化，为测试用例生成提供基础框架。然后，分别将软硬件每一个功能入口作为测试点。利用软硬件功能策略图分别描述该测试点在软硬件模型及其功能属性模型中的功能特征。如果后者蕴含前者，则证明功能属性被满足，意味该项功能测试通过。

1　软硬件功能策略半形式化建模

在半形式化方法中，有限状态图着重刻画对象的状态以及迁移关系，刻画方式直观且可读性高，但未对迁移关系进行细化。Petri网对迁移关系的顺序、并发、冲突进行了详细定义，但引入符号过多，操作复杂度较大。为解决此问题，本节将以有限状态图作为软硬件功能基础刻画框架，并将Petri网的迁移关系分类添加到有限状态图中。

对于软硬件来说，外界与其功能进行交互时均通过功能入口。功能入口可以是一个函数，称为逻辑入口；也可以是一个硬件入口，如一个硬件引脚，称为物理入口。其中，软件功能入口均为逻辑入口；硬件功能入口包括逻辑入口（如命令和函数）和物理入口（如硬件表面等）。基于功能入口的分类，软硬件功能正确，表明外界通过功能入口所执行的功能策略正确。某项具体功能策略的执行，可描述为处于某一状态下，基于某种正常的入口使用方式成功使用该入口，可执行此项功能，触发一个正确的入口迁移。

为描述此过程，对有限状态图、Petri网、顺序图的状态及迁移关系进行重新定义，称为软硬件功能策略图，如图1所示。

软硬件功能策略图是四元组（S，R，U，A）：S是有限状态的集合，用圆形表示，对应入口使用方式所涉及的参数；R是有限功能入口的集合，用圆形方框表示；U是有限功能入口使用方式的集合，用指向R的箭头表示；A是有限功能迁移的集合，用R指出的箭头表示；功能迁移指通过正常使用方式，使用功能入口后触发的一个入口动作迁移。

图1中，重定义的操作符号包括：

（1）竖线表示并发迁移的分叉连接符，或者合并迁移的合并连接符；

（2）状态下的矩形条表示此状态将先后触发多功能入口；入口下虚线表示该入口的生命线；生命线上的矩形条表示通过此入口触发的一个动作；多个入口的生命线上的矩形条由上往下代表动作触发的先后顺序；

（3）每一条迁移路径均代表软硬件的一条功能策略。

图1　软硬件功能策略

下面详细论述四种迁移：顺序迁移、并发迁移、冲突迁移和合并迁移。

（1）顺序迁移，如图2所示。此功能策略表示软硬件在状态S1下，基于使用方式U1使用该策略入口R1，执行迁移A1+S5。

图2　顺序迁移

（2）并发迁移，如图3所示。此功能策略表示软硬件在状态S2下，基于使用方式U2使用该策略入口R2，执行并发迁移A3+S3或A4+S4。

图3　并发迁移

（3）冲突迁移，如图4所示。此功能策略表示软硬件在状态S1下，基于使用方式U2使用该策略入口R2，可能执行迁移A3+S3或A4+S4或A5+S5。此过程造成非确定性，可能引发冲突。

图4　冲突迁移

（4）合并迁移，如图5所示。该功能策略表示软硬件在状态S1下，基于使用方式U2使用该策略入口R2，或基于使用方式U3使用该策略入口R3，执行迁移A5+S5；同时，在状态S2下，基于使用方式U4使用策略入口R3，同样可执行迁移A5+S5。

图5　合并迁移

2　模型结构化简

在描述并发、冲突及合并迁移时发现，假设触发同一个迁移的状态和功能入口使用方式相同，则可将它们进行合并，化简软硬件功能策略图的整体结构。如果假设成立，则约简到复杂的使用方式及功能入口，图1可能存在如下化简。

（1）并发迁移结构的化简，如图6所示。

图6　并发迁移结构化简

（2）冲突迁移结构的化简，如图7所示。

图7　冲突迁移结构化简

（3）合并迁移结构的化简，如图8所示。

图8　合并迁移结构化简

于是，图1最终可化简为图9。

图9　功能策略图的化简

3　软硬件功能测试用例生成

软硬件功能策略图完整描述了为实现软硬件功能，具体设计和实现的策略，同时实现了策略的完整梳理。其中，功能入口是执行该策略的媒介。在确保软硬件功能完整性描述的前提下，若要证明软硬件功能的正确性，需首先基于本文建立的半形式化方法描述软硬件功能策略需求及具体实现，然后判断此两模型间是否存在状态一一映射关系，若存在，则表明功能设计正确，过程如图10所示。

图10　一致性验证框架

在实现功能需求与设计的一致性分析验证后，需要验证软硬件确实按照设计进行了安全实现。此时，需证明下述两个要素均得到了满足：

（1）功能入口使用方式是正确的；

（2）由功能入口触发的功能迁移是正确的。

为证明满足了上述两个要素，软硬件功能实现正确的测试用例的生成及验证步骤。软硬件功能策略图中的每一条迁移路径，均对应一个测试用例。具体的测试用例可设计为，首先基于软硬件功能策略图等同建模软硬件功能需求，然后基于等价性检查验证软硬件功能需求模型，其均等价对应一个测试用例的迁移路径。如果验证通过，则证明软硬件功能实现正确。验证基本原理图将在下一节实例分析中给出。

4　实例

以智能卡产品为例，模式控制是其典型的安全功能。该功能要求产品测试模式、BOOT模式、COS模式之间仅为单向转换关系，以确保产品在功能测试结束后，下级模式用户使用时无法再进入上级模式修改产品安全配置。COS模式无法调用正常的操作BOOT模式的指令接口返回BOOT模式，但BOOT模式常为COS模式用户提供部分函数功能入口，使COS模式可再次返回BOOT模式进行相关安全操作。

此过程涉及的功能需求基于本文的混合半形式化方法建模，可描述为如图11所示。

图11　功能需求半形式化

具体设计的半形式化描述，如图12所示。

图12　功能设计半形式化

通过分析发现，图11与图12策略相同。基于图12获得此功能策略正确性测试用例，如图13所示。

图13　功能测试用例生成

5　结 语

本文提出了一种软硬件功能测试用例生成的半形式化框架。该框架具备通用性，适用于所有的软硬件，实现了软硬件功能策略描述。未来将寻求形式化的方法，表征攻击入口的使用方式及触发迁移，以实现软硬件功能正确性的形式化推导。

［1］ Swain R，Panthi V，Behera P K，et al.Automatic Test Case Generation from UML State Chart Diagram［J］.International Journal of Computer Applications，2012，42（07）：26-36.

［2］ Wang Y，Zheng M.Test Case Generation from UML Models［C］.45th Annual Midwest Instruction and Computing Sympos-ium，2012.

［3］ Francisco M A，Castro L M.Automatic Generation of Test Models and Properties from UML Models with OCL Constraints［C］.Proceedings of the 12th Workshop on OCL and Textual Modelling，2012：49-54.

［4］ Hemmati H，Arcuri A，Briand L.Achieving Scalable Model-based Testing through Test Case Diversity［J］. ACM Transactions on Software Engineering and Methodology，2013，22（01）：6.

［5］ Shirole M，Kumar R.UML Behavioral Model based Test Case Generation：A Survey［J］.ACM SIGSOFT Software Engineering Notes，2013，38（04）：1-13.

［6］ 孙莉.基于构件的软件测试中测试用例分配优化研究［J］.通信技术，2008，41（10）：193-195. SUN Li.Optimization of Test Case Allocation in Component-based Software Testing［J］.Communications Technology，2008，41（10）：193-195.

［7］ Jorgensen P C.Software Testing：A Craftsman's Approach［M］. Boca Raton：CRC press，2013.

［8］ Živkovič A，Rozman I，Heričko M.Automated Software Size Estimation based on Function Points Using UML models［J］. Information and Software Technology，2005，47（13）：881-890.

［9］ 杨波，吴际，徐珞等.一种软件测试需求建模及测试用例生成方法［J］.计算机学报，2014，37（03）：522-538. YANG Bo，WU Ji，XU Luo，et al.An Approuch of Modeling Software Testing Requirements and Generating Test Case［J］. Chinese Journal of Computers，2014，37（03）：522-538.

［10］ 包晓安，姚澜，张娜等.基于受控Markov链的软件自适应测试策略［J］.计算机研究与发展，2012，49（06）：1332-1338. BAO Xiao-an，YAO Lan，ZHANG Na，et al.Adaptive Software Testing based on Controlled Markov Chain［J］.Journal of Computer Research and Development，2012，49（06）：1332-1338.

Software and Hardware Functional Test Case based on Semi-formal Generating Method

DENG Hui， SHI Hong-song， ZHANG Bao-feng
（China Information Technology Security Evaluation Center， Beijing 100085， China）

Functional test is for the purpose of ensuring the correctness and reducing the cost of software and hardware. The existing function tests are usually the so-called balck-box test， which could not find out all problems in correctness verification. Semi-formal method could provide a framework to deal with this problem. This paper， around functional interface， describes the dynamic and static characteristics of software and hardware based on finite-state machine， Petri net and sequence diagram. And the description model containing interface， behavior and action of the interface is also established. Then， a depth traversal is applied to covering all of the test scenarios around interface so that the maximal test cases can be acquired. Finally， based on equivalence of the model， The description of functional test implementation is examined.

software and hardware functional test； finite-state machine； petri net； sequence diagram；equivalence verification

National Natural Science Foundation of China（No.61472448）

TP311.52

A

1002-0802（2016）-10-1364-05

10.3969/j.issn.1002-0802.2016.10.019

2016-06-07；

2016-09-23

data：2016-06-07；Revised data：2016-09-23

国家自然科学基金（No.61472448）

邓 辉（1985—），女，博士，助理研究员，主要研究方向为信息安全；

石竑松（1978—），男，博士，副研究员，主要研究方向为信息安全；

张宝峰（1983—），男，硕士，副研究员，主要研究方向为信息安全。