随着社会对于软件产品的需求量越来越大，软件产品的规模在不断增大，软件质量变得越来越难以保证。目前的大型软件开发过程中，软件测试已成为一个不可或缺的环节。

结构化测试是软件测试中常用的技术，它是根据软件的结构知识和实现知识导出测试的测试数据设计方法，它的核心任务是产生一组检错能力较高的测试数据。路径测试是结构化测试的一种常用测试策略。它的主要思想是将程序转换成一个中间结构，然后在此基础上对程序进行测试。在路径测试中，常用的中间结构是控制流图（CFG）。由于程序的测试数据通常是无限的，因此在结构化测试中定义了许多基于控制流的覆盖准则（如语句覆盖，分支覆盖等），用于衡量测试数据集的质量。基于控制流的覆盖准则要求测试数据集能够覆盖控制流图中的某些节点和边，比如分支覆盖要求测试数据集合覆盖控制流图的所有边。目前已有许多技术和工具针对这些覆盖准则来自动化地生成测试数据。但有研究表明，这些简单的覆盖准则的检错能力远远不能满足现代软件质量的需求。因此有科研人员提出了逻辑覆盖准则，如判断覆盖，条件覆盖等。其中修改的条件/判断覆盖（MC/DC）准则是检错能力较强且测试数据规模小的准则。虽然MC/DC被提出了很长时间，但还没有专门的工具能够针对它进行测试生成。同时，针对控制流覆盖准则的工具生成的测试数据对MC/DC的覆盖率不高。

目前的软件测试已经渗透到整个软件开发过程中，比如系统设计阶段需要测试，用于确保设计与需求的一致性。与传统的测试不同，系统设计阶段的测试的对象是软件模型。所谓的软件模型是指对软件行为和软件结构的一种抽象描述。扩展有限状态机（EFSM）模型是一种常用的软件模型。EFSM模型是有限状态机（FSM） 模型的一个扩展，它在FSM模型的基础上增加了变量集合、操作和谓词。它拥有较强的描述能力，通常被用于软件通讯协议，嵌入式系统等软件系统的交互行为的建模。目前也有许多关于EFSM模型的测试方法，其中一部分工作只提出了测试数据需要满足的覆盖准则，没有给出生成测试数据的具体方法；另一部分工作虽然给出了测试数据生成的方法，但并不是对任意EFSM都有效，且效率不高。

本文主要研究了软件测试中结构化测试和基于EFSM模型的测试中相关技术，目标是解决上述现有工作中存在的问题。具体来讲，考虑到结构化测试中用到的CFG模型能够使用EFSM模型来表示，我们设计了一套统一的结构化测试框架。该框架以EFSM模型作为中间结构，能够同时支持程序和系统设计模型的测试数据自动化生成。同时，本文在该框架上实现了针对一些常用的基于控制流的覆盖准则的测试数据生成策略。另外，我们尝试将结构化测试框架应用于EFSM模型的测试数据生成中。针对MC/DC，我们设计了一种高效的算法，能够在较短的时间内产生较高MC/DC覆盖率的测试数据集合。最后通过一些实验验证了我们方法的有效性。

With a growing demand of software products and constantly increasing size of software products, it has become more difficult to guarantee software quality. Currently, software testing has become an essential part in the large-scale software development process.

Structural testing is a commonly used technique in software testing, which is based on the knowledge of software structure and implementation. The core mission of structural testing is to produce a set of test data, which has high fault detection capability. Path testing is a widely used strategy in structural testing. Its main idea is to convert the program into an intermediate structure, and then test the program under this structure. In path testing, Control Flow Graph (CFG) is a commonly used intermediate structure. Since the test space of the program is usually infinite, a lot of coverage criteria based on control flow are defined in structural testing to measure the quality of test data sets, such as Statement Coverage and Branch Coverage. These coverage criteria based on control flow often require that the test data set must cover some nodes or edges in CFG. For instance, Branch Coverage demands that the test data set must cover all of edges in CFG. At present, there are many techniques and tools to generate test data for achieving these coverage criteria. However, recent studies have shown that the ability to detect faults of branch coverage is far from meeting the needs of modern software quality. Therefore, researchers have proposed several logical coverage criteria, such as Decision Coverage and Condition Coverage. Among those logical coverage criteria, Modified Condition/Decision Coverage is an important criterion, since it has stronger ability to detect faults and the size of test data achieving it is very small. Although MC/DC was presented for a long time, there is no specific tool for test generation aiming at MC/DC. The existing tools almost aim at achieving statement and branch coverage, and the test data set generated by them can not achieve high MC/DC coverage ratio.

Software testing has penetrated into the whole software development process. For instance, in the system design phase, we need software testing to ensure the consistency of system design and requirements. Different with conventional testing, the test objects in system design phase are some models, which depicts software behavior. Extended Finite State Machine (EFSM) is a commonly used software model. It is an extension of Finite State Machine (FSM) augmented with additional variables, operations and predicates. Since EFSM has strong ability to describe the interaction behavior of software, it is often used to model the software behavior in communication protocols and embedded systems. Many techniques have been developed to generate test cases from the EFSM model. However, some of them only raised the coverage criteria without test generation method while the other of them are not effective for arbitrary EFSM.

This paper mainly studies test generation techniques for structural testing and EFSM model and solves some existing drawbacks in the previous works. A unified framework for structural testing and EFSM model is presented in this paper. Since a CFG can be represented as an EFSM, EFSM can be regarded as the intermediate structure to support test generation for source code and EFSM at the same time. In addition, we implement several coverage criterion under this framework and use this framework to generate test data for source codes and EFSM models. For MC/DC, an efficient algorithm is proposed to generate adequate test data in acceptable time. Several experimental results show that our approach is effective.