软件模型检测新技术研究

软件模型检测以其潜在的商业价值一直为学术界和工业界关注．本文通过剖析模型检测工具SLAM，探讨软件模型检测的机理、方法及若干核心技术，并总结出软件模型检测的一些新策略．     

基于双格的软件产品线模型检测

软件产品线在保留每个产品的可变性前提下通过最大化产品间的共性实现资源的再利用,从而提高生产效率和节约生产成本。近年来,基于特征的状态迁移系统应用于软件产品线的建模和验证中。然而现有的方法不能很好地支持软件产品线中存在的信息不确定和不一致的情况。为此,首先提出一种基于双格的特征迁移系统,用于软件产品线的行为建模,采用投影的方法定义产品的行为模型;然后采用动作计算树逻辑描述系统的时序属性,并且给出它在新系统上的语义,用于支持基于双格的模型检测;最后,采用多值模型检测工具χchek对方法的有效性进行实验分析。     

基于划分和凝聚层次聚类的无监督异常检测

将信息熵理论应用于入侵检测的聚类问题,给出在混合属性条件下数据之间距离、数据与簇之间距离、簇与簇之间距离的定义,以整体相似度的聚类质量评价标准作为聚类合并的策略,提出了一种基于划分和凝聚层次聚类的无监督的异常检测算法。算法分析和实验结果表明,该算法具有较好的检测性能并能有效检测出未知入侵行为。     

基于肤色模型和层次滤波技术的人脸检测

为了能够实现单幅彩色图像中的人脸检测,提出了基于肤色模型和层次滤波技术的人脸检测算法.它通过基于肤色的鲁帮性进行肤色建模,在图像中精确的提取出肤色区域,再经过方向校正后,检验出一系列的人脸特征、像素亮度的变化以及连通区域的空间排列,可以较好地检测出图像中的脸部区域.实验结果表明,该方法可以适用于不同光照条件下的人脸检测,即使在脸部特征没有被很好的检测出的情形下也可以较好完成人脸检测.     

并行软件模型检测

并行化是提高模型检测效率的重要手段。该文研究了基于标号迁移系统的C程序模型检测,提出一种软件模型检测并行化的方法。该方法利用软件模型检测工具模块化验证(MAGIC)的模块化特性对C程序进行组件分解,将各组件均衡地分发到若干计算节点,由节点调用MAGIC完成验证。由于保证节点间只有少量的通信与同步,该方法能达到较好的并行加速比,具有良好的可扩展性。实验结果显示,该方法大幅压缩了检测时间,有利于大规模软件的形式化验证。     

模型检测技术在软件并行缺陷检测中的应用

多线程并行运行的软件在提高性能的同时,其交互的组合随着程序规模增大变得更为复杂,给软件的设计与验证带来了挑战.本文从常见的并行缺陷入手,提出使用模型检测的方法对其进行检测和分析,实践表明,使用该方法可有效检测此类并行缺陷.     

基于特征切片的软件产品线模型检测

特征模型是一种描述软件产品线中共性和可变性特征的通用形式。特征模型象征着所有可能的应用程序配置空间,是实现个性化产品定制的基础。随着软件产品线的规模和复杂程度的增加,如何有效支持以用户需求为基础以及根据特定需求和利益相关者的目标进行个性定制开发是亟待解决的实际问题。提出一种根据用户需求对特征模型进行切片,进一步结合三值逻辑对行为模型进行抽象,最后利用模型检测技术对软件产品线进行验证的方法。实验结果证实了该方法的有效性。     

批量控制中单元划分原则

以某涂料工艺的生产过程为案例,采用定义的单元判断原则和划分原则,推断出批次生产过程的单元,进而明确整个工艺过程的结构。结合浙江中控技术股份有限公司自主开发的VxBatch批控软件的应用,实现录入的配方结构清晰且合理,降低配方维护难度,为批次化生产的企业实现配方管理信息化转型打下基础。     

Heuristics for model checking Java programs

Model checking of software programs has two goals – the verification of correct software and the discovery of errors in faulty software. Some techniques for dealing with the most crucial problem in model checking, the state space explosion problem, concentrate on the first of these goals. In this paper we present an array of heuristic model checking techniques for combating the state space explosion when searching for errors. Previous work on this topic has mostly focused on property-specific heuristics closely related to particular kinds of errors. We present structural heuristics that attempt to explore the structure (branching structure, thread interdependency structure, abstraction structure) of a program in a manner intended to expose errors efficiently. Experimental results show the utility of this class of heuristics. In contrast to these very general heuristics, we also present very lightweight techniques for introducing program-specific heuristic guidance.     

Combining search space partition and search Space partition and abstraction for LTL model checking

The state space explosion problem is still the key obstacle for applying model checking to systems of industrial size.Abstraction-based methods have been particularly successful in this regard.This paper presents an approach based on refinement of search space partition and abstraction which combines these two techniques for reducing the complexity of model checking.The refinement depends on the representation of each portion of search space. Especially, search space can be refined stepwise to get a better reduction. As reported in the case study, the Integration of search space partition and abstraction improves the efficiencyof verification with respect to the requirement of memory and obtains significant advantage over the use of each of them in isolation.     

Combining search space partition and abstraction for LTL model checking

The state space explosion problem is still the key obstacle for applying model checking to systems of industrial size. Abstraction-based methods have been particularly successful in this regard. This paper presents an approach based on refinement of search space partition and abstraction which combines these two techniques for reducing the complexity of model checking. The refinement depends on the representation of each portion of search space. Especially, search space can be refined stepwise to get a better reduction. As reported in the case study, the integration of search space partition and abstraction improves the efficiency of verification with respect to the requirement of memory and obtains significant advantage over the use of each of them in isolation.     

基于模型检测技术的XML乐观并发控制协议

XML并发控制协议可用于保证多个用户同时访问XML文档时的事务隔离性,由于XML数据的半结构化特点和访问接口的特殊性,现有XML并发控制协议随着文件规模的增大、并发客户的增多,系统事务性能大幅下降。基于模型检测技术提出了一种新的乐观并发控制协议XOCC-MC。通过将XML文档对应的DTD文档转换为系统模型,将事务操作中的XPath转为了CTL公式,利用模型求值判断节点间是否存在A/D关系,进而根据冲突矩阵判断事务之间的冲突关系。与现有乐观并发控制协议相比,XOCC-MC协议在文件规模大、并发客户数多的情况下,表现出较好的事务性能。     

Partial-order reduction and trail improvement in directed model checking

In this paper we present work on trail improvement and partial-order reduction in the context of directed explicit-state model checking. Directed explicit-state model checking employs directed heuristic search algorithms such as A* or best-first search to improve the error-detection capabilities of explicit-state model checking. We first present the use of directed explicit-state model checking to improve the length of already established error trails. Second, we show that partial-order reduction, which aims at reducing the size of the state space by exploiting the commutativity of concurrent transitions in asynchronous systems, can coexist well with directed explicit-state model checking. Finally, we illustrate how to mitigate the excessive length of error trails produced by partial-order reduction in explicit-state model checking. In this context we also propose a combination of heuristic search and partial-order reduction to improve the length to already provided counterexamples.     

基于自适应递阶遗传算法的洪水预报模型

基于递阶结构的遗传算法可以同时对BP神经网络进行结构优化和权重求解。采用收缩解空间的方法可以有效提高算法的收敛速度和精度。采用先进行自适应递阶遗传算法获得最优网络结构及参数,再用BP算法对网络进行训练,并应用于洪水预报模型,可以获得较高的精度。     

基于MDA的嵌入式软件开发平台设计

针对如何快速开发高质量的嵌入式软件的问题,实现了一种基于MDA的嵌入式软件开发平台EUP。该平台根据模型驱动的软件开发方法,集成UML建模、模型验证、模拟和自动代码生成技术等,为嵌入式软件的开发提供了一个统一的开发环境。分析了铁道交叉路口系统的实例,试验结果表明EUP平台能够方便、高效地实现模型模拟和验证,为快速开发高质量的嵌入式软件提供了一种可行的途径。     

A classification and comparison of model checking software architecture techniques

Software architecture specifications are used for many different purposes, such as documenting architectural decisions, predicting architectural qualities before the system is implemented, and guiding the design and coding process. In these contexts, assessing the architectural model as early as possible becomes a relevant challenge. Various analysis techniques have been proposed for testing, model checking, and evaluating performance based on architectural models. Among them, model checking is an exhaustive and automatic verification technique, used to verify whether an architectural specification conforms to expected properties. While model checking is being extensively applied to software architectures, little work has been done to comprehensively enumerate and classify these different techniques.The goal of this paper is to investigate the state-of-the-art in model checking software architectures. For this purpose, we first define the main activities in a model checking software architecture process. Then, we define a classification and comparison framework and compare model checking software architecture techniques according to it.     

基于分等级公平竞争模型的可持续模拟退火算法的应用

通过改进可持续模拟退火算法(HFCSA)算法的个体定义与编码方式、种群的生成方式以及设计新的算子,成功解决了医学实验安排这种带约束的优化问题。设计的最优实验方案所需时间是某医学院所使用方案的77%,拓宽了算法的应用领域,为带约束优化问题的求解找到了新的途径。     

Software modeling and analysis using a hierarchical object-oriented Petri net

Petri net is used widely to analyze and model various systems formally. Recently, many Petri nets mania devote their efforts to enhancing and extending the expressive power of Petri nets. One such effort is to extend Petri nets with object-oriented concepts. An object-oriented paradigm provides excellent concepts to model real-world problems. Object-oriented concepts allow us to build software systems easily, intuitively, and naturally. Although several high-level Petri nets with the concept of objects are suggested, these nets do not fully support the object-oriented concepts. In this paper, we propose a hierarchical object-oriented Petri net (HOONet). The formal syntax and semantics of HOONet are explained in detail. HOONet supports a wide range of object-oriented features including abstract, encapsulated and modularized objects, object interaction by message passing, inheritance, and ploymorphism. HOONet also supports a variety of modeling and analysis mechanisms such as incremental modeling of evolving systems, unfolding the HOONet to lower level Petri net, and incremental reachability analysis for HOONet models. We demonstrate the usefulness of HOONet by applying it to modeling and analysis with an example.