一种对程序故障行为和失效行为的聚类有效性验证方法

分析软件自身故障在软件运行过程中的行为规律是分析＂故障—错误—失效＂链式效应的基础.但在研究软件故障行为特征时面临的关键问题是故障行为集合的庞大与复杂.因此,如何约简故障行为集合是研究故障行为规律的基本前提.＂当两个程序具有相似的基本属性时,其故障行为和失效行为也具有相似性＂这一推断为约简故障集提供了良好的依据,但尚未得到验证.本文核心工作即验证该推断的正确性.为此,首先提出一种针对程序基准行为、故障行为和失效行为的表征方法;其次提出一种考虑最佳聚类数的程序行为聚类方法;最后设计一组基于故障注入的程序行为聚类实验,用以验证前述推断的正确性.其中,实验分别以计算密集型程序（SPEC CPU2000和SPEC CPU2006基准程序）和I/O密集型程序（IOZONE、DEBENCH等）作为目标程序集.实验结果表明,（1）程序行为的表征方法和聚类方法具有合理性和有效性;（2）以程序基准行为聚类结果为依据的故障行为和失效行为的聚类质量良好,以此验证了推断的正确性.     

面向数据流的加权聚类及演化分析研究

为解决无限数据流在有限内存空间中的聚类分析问题，本文提出了一种加权聚类及演化分析框架。为简要地描述此框架，给出了聚类、聚类簇的概念及其数据结构定义，接着对聚类、聚类簇的加法运算和差运算给出了清晰的描述和相应的实现算法。本框架与CluStream框架有较大的差别，这里采用聚类簇的加法运算来实现更大时间跨度内的聚类簇融合，采用聚类簇的差运算来进行聚类簇的演化分析。最后通过第一个例子来说明本框架是如何对数据流进行加权聚类及演化分析的，采用第二个例子来验证为实现本框架所需的十五个算法的正确性及有效性。     

带信息反馈的凝聚层次聚类算法

本文针对传统的基于相似性的层次聚类算法存在的两个问题(相似性度量中方向信息的丢失和算法的适应能力弱)提出了一种带有信息反馈的凝聚层次聚类算法.首先将无法预知的复杂数据结构描述成3个基本的结构特征单元,并对其进行建模构建一种相似性度量定义的泛型和一种凝聚的层次聚类算法.在凝聚的层次聚类算法中加入类信息的反馈机制,并在不同阶段对相似性定义的泛型进行具体化,充分利用数据点对之间的方向信息和距离信息进行聚类.该聚类算法主要有两大优势:(i)算法的适应能力较强,不需要假设的前提下可以处理无法预知的复杂数据结构;(ii)算法对噪声具有较强的鲁棒性,在不需要对数据集进行预处理的情况下能够在聚类的过程中识别噪声点或者噪声类.从人工数据和真实数据的试验结果可以看出新算法的优越性能.     

基于鸽群智能行为的大规模无人机集群聚类优化算法

未来空中战场,大规模无人机集群系统将成为主导力量.而对大规模无人机集群系统进行分组聚类是完成作战任务规划的必要步骤.在实际战场中无人机受到有限通信约束,无法得到全面而有效的全局作战信息.因此本文提出一种基于鸽群智能行为的大规模无人机集群聚类优化算法.根据聚类模型设计鸽群优化算法,研究分析导航能力优异的鸽群智能行为,将鸽群飞行过程中的层级网络机制映射到鸽群优化算法中,解决有限交互环境下的信息不完整问题.一方面,依据鸽群在飞行过程中来自临近个体的引导更为有效直接,因而在有限交互环境下,基本鸽群优化算法中的全局最优信息由交互范围内的最优个体信息替代;另一方面,鸽群的中心位置更新包括三部分:增量惯性部分、模仿部分、环境影响部分.为验证改进后鸽群优化算法在有限交互范围下的有效性,本文采用三种算法针对三个数据集进行聚类分组,仿真结果表明改进后的鸽群优化算法在最优解与平均最优解上均有改善,为实际作战环境下的无人机集群系统聚类分组提供了有效的解决方法.     

一种基于扩展有限状态机的自动化测试用例生成方法

扩展有限状态机(EFSM)是使用最广泛的测试模型之一.由于不可行路径的存在,运用EFSM模型生成测试用例仍然是个难题.本文提出了一种基于EFSM模型的自动化测试用例生成方法 (ATGEM).为解决不可行路径问题,首先提出一种基于数据流分析的路径可行性度量方法来预测路径的可行性,以尽可能避开不可行路径,提高测试用例自动化生成的效率.然后通过建立动态可执行模型来获取运行时反馈信息作为搜索算法的适应度函数(fitness function),实现测试数据和预言信息的自动生成.该方法结合静态分析和动态分析技术生成一个较优可行路径子集和对应测试用例来达到指定的覆盖准则,能够应用于多种数据类型的测试用例生成,适用范围较广.通过实验在多个EFSM模型上验证了ATGEM方法中测试用例生成和路径可行性度量方法的有效性,实验结果表明,利用路径可行性度量方法可以大幅度提高测试用例生成效率,与现有方法相比,ATGEM中的测试用例生成方法具有更高的效率.     

一种基于同步动力学模型的层次聚类方法

本文基于建模同步动力学行为的Kuramoto模型提出了一种新的有效层次聚类方法.本文提出的方法基于局部邻域的概念,能够实现稳定的局部同步聚类.通过不断扩大对象同步的邻域半径,所提出的方法能够实现层次化的同步聚类.此外,提出对象邻域闭包的概念,在对象间到达完全同步之前就能预测出聚类的形成,从而减少对象动态交互的时间.本文的方法不依赖于任何数据分布假设,无需任何手工参数设置,可以检测出任意数量、形状和大小的聚类.由于同步过程能够有效地规避离群点,该方法有较强的噪声数据抑制能力.在大量真实数据集和人工合成数据集上的实验结果表明本文的方法聚类准确率高,且运行时间较同类基准算法显著缩短.     

一种基于P/T网的低级并发程序验证模型

随着片上多处理器/多核技术的不断发展,采用机器级语言的并发程序(低级并发程序)有了更加广阔的应用前景.然而,低级并发程序的验证问题也成为程序语言领域一种新的挑战.并发程序安全性验证领域现有的工作多数是针对高级语言、规范或者演算,而针对机器级语言的甚少。这种情况的主要原因之一是缺少低级抽象模型.文中描述一种可验证的低级并发编程模型P-PMCC.P-PMCC程序是一个扩展的P/T网系统,其网结构用来刻画低级并发线程(原子的顺序汇编级代码)之间的并发关系.P-PMCC程序的验证采取模型检查和定理证明相结合的方法,分开考虑并发行为与顺序线程的规范和验证:前者借助于Petri网领域已有的方法,后者则借助现有的顺序程序的正确性证明方法。P-PMCC程序也可以看作并发程序的一种可验证的低级中间表示.     

一种基于一阶逻辑的软件代码安全性缺陷静态检测技术

软件代码安全性缺陷是可能引发软件系统高危后果的一类重要缺陷,针对该类缺陷的自动化检测和定位技术在软件维护和演化研究领域具有重要意义.本文提出并实现了一种形式化检测方法——基于一阶逻辑的软件代码安全性缺陷静态检测方法,利用命题逻辑和谓词逻辑定义模式路径公式,引入多个与依赖关系相关的谓词构造逻辑函数表达式,作为模式路径节点产生的制导条件,实现了对多类软件代码安全性缺陷的形式化描述,把安全性缺陷检测问题转化成在中间代码对应的有限状态空间中是否存在相应模式路径公式的判定问题.实验结果表明,该方法能适用于大多数类型的软件代码安全性缺陷检测,在对openssl,wu-ftpd等13个开源程序的测试中,准确重现了10个已公开安全漏洞,发现2个未公开安全漏洞.并且,与现有的模型检验等形式化静态分析方法相比,该方法的测试时间和代码规模成渐近线性关系.     

一种考虑摩擦与排斥的人员疏散元胞自动机模行

在人员疏散过程中, 人与人之间、人与环境(如建筑物)之间存在相互作用力, 包括吸引力、排斥力和摩擦力. 3种力对人员疏散的行为、速度和效率起着关键作用. 在以往的模型中, 吸引力可以得到较好地描述, 但对排斥力和摩擦力的定量描述还不完善. 近年来提出的多粒子自驱动模型(社会力模型)可以较好地体现3种力的作用, 但由于它是一种连续型模型, 运算的速度较慢并很难得到改善. 目前研究较多的离散型模型, 如元胞自动机模型和格子气模型等, 可以达到较高的运算速度, 但很难考虑到摩擦力与排斥力的作用, 造成运算结果误差较大. 针对这种情况, 本文在经典元胞自动机模型的基础上, 量化确定了摩擦力和排斥力的运算规则, 提出了一种新的元胞自动机模型. 通过将模型的运算结果与多粒子自驱动模型进行比较表明, 新模型在人员行为、疏散速度以及"快即是慢"效应等方面都可以得到与后者相同的结果, 而运算速度则与普通的元胞自动机及格子气模型相当, 比社会力模型大为提高.     

扩展的语义分析的WAP协议缺陷测试

首先介绍了一种基于语义分析的缺陷测试技术.该测试方法利用语义测试及软件错误注入来进行测试.它比传统测试的成本要小,同时能达到很好的效果.但该方法只能检测协议实现级别的漏洞,而不能检测协议设计中可能存在的缺陷.本文结合了Petri网在协议测试方面的优点提出了一种扩展的语义分析的协议缺陷测试方法.它能通过对协议Petri网模型的分析来捕获协议层面的缺陷,而为此所需的额外开销是很小的.这弥补了原缺陷测试在协议层面的不足.之后对该方法各个阶段进行了介绍.对WAP-WSP协议的进行了缺陷测试,并对结果进行了分析,证明其可行性.     

基于GMM的压电驱动器磁滞特性建模及高精度抗扰跟踪控制

包含压电驱动器的微定位平台可以用于减小飞切加工中的低频误差.本文针对该平台中的压电驱动单元,提出了一种新的系统建模方法,并基于此建立了完整的高性能抗扰跟踪控制策略.首先,利用高斯混合模型(Gaussian mixture model, GMM)对压电驱动器固有的磁滞特性建模,并根据该模型进行前馈补偿,以消除磁滞非线性对控制精度的影响.其次,建立扩张状态观测器,对所有外部扰动及未建模误差进行观测与补偿,以提高系统的抗扰能力.为了进一步提高系统的跟踪精度与控制带宽,建立状态反馈与零相跟踪前馈控制策略,以优化闭环系统特性.实验结果验证了基于所提磁滞模型建立的抗扰跟踪控制方法的有效性.在0～50 Hz输入信号频率范围内,在给定的测试集内该控制策略下的系统跟踪误差小于2.2%,能够满足目标控制带宽下的高精度跟踪要求.     

一种形式化的实时协议互操作性测试方法

协议互操作性测试是一种保证网络通信协议实现质量的重要技术．下一代互联网协议需要提供对实时应用的有效支持，然而已有互操作性测试相关研究中并没有考虑协议中的时间约束，现有互操作性测试技术很难应用于实时协议互操作性测试中．文中提出了一种形式化的实时协议互操作性测试方法．首先提出了一个用于描述实时协议互操作性测试被测系统的形式化模型CMpTIOA（通信多端口时间输入输出自动机），基于该模型定义了时间互操作性关系；然后提出一种以时间互操作性关系为指导的测试生成方法，根据被测系统模型生成参数化测试行为树，在该方法中还集成了可执行性预判决机制，在一定程度上缓解了状态空间爆炸问题；最后将提出的理论和方法应用于IPv6邻居发现协议的互操作性测试中，验证了该方法的可行性．     

多无人机协同搜索的模糊认知决策方法研究

搜索决策方法是影响多无人机协同搜索效能的关键.传统的搜索决策方法关注于使多架无人机形成对任务区域的协同全覆盖,采用基于概率搜索图和滚动时域控制的搜索决策方法,对复杂搜索任务的适应性有限.本文借鉴人类实施搜索行为的认知决策方式,提出面向多无人机协同搜索的三层结构的认知控制模型.基于该模型和模糊聚类思想对任务区进行认知匹配和约简划分;之后,应用二次模糊聚类对各架无人机进行面向协同搜索的任务区域分配,在此基础上,再应用滚动时域控制方法完成对无人机的搜索控制.从任务区域覆盖模式和目标发现能力两个方面,通过仿真实验分析了本文提出的协同搜索模糊认知决策方法的性能.     

锂硼合金反应合成机制研究

提出了锂硼合金反应合成的物理模型, 反应过程中有两次放热反应, 第1次放热反应可以分成3个阶段, 第1阶段是Li与B粒在界面(~330℃)的瞬时反应, 此放热量与B粒的半径成反比关系. 第2阶段是Li液通过B粒表面反应生成的LiB₃向内扩散并与内核的B反应, 此过程可用固体反应中的Johnston模型来描述. 其反应速率常数与B粒的半径平方成反比. 第3阶段是在425℃以上LiB₃溶解到Li液体之中, 但与此同时, 第2次放热反应也开始进行. 第2次放热反应通过Li-B化合物的形核和长大来完成, 它可以分成形核孕育和爆发反应两个阶段. 有足够形核数目时, 产生爆发性反应. 温度越低, 产生爆发性反应所需时间越长. 运用该模型解释了合成实验中出现的相关现象.     

网络蠕虫扩散中蠕虫和良性蠕虫交互过程建模与分析

良性蠕虫(Antiworm)和蠕虫(Worm)的交互过程应当被看作一个动态过程. 文中首次尝试研究良性蠕虫的引入是如何影响蠕虫的扩散过程的, 并使用常微分方程建立了一个SIAR模型来描述蠕虫和良性蠕虫的交互过程. 虽然模型是一种理想情况下的, 但它演示了蠕虫和良性蠕虫间的一些非线性交互而产生的多种不同的响应. 以Blaster/Nachi为例, 给出了对实用的良性蠕虫系统的一些设计分析. 就目前知识而言, 尚未发现有相关的模型能描述良性蠕虫在网络蠕虫扩散中的动态特征, 这是了解蠕虫和良性蠕虫交互过程的首次尝试.     

一种考虑摩擦与排斥的人员疏散元胞自动机模型

在人员疏散过程中, 人与人之间、人与环境(如建筑物)之间存在相互作用力, 包括吸引力、排斥力和摩擦力. 3种力对人员疏散的行为、速度和效率起着关键作用. 在以往的模型中, 吸引力可以得到较好地描述, 但对排斥力和摩擦力的定量描述还不完善. 近年来提出的多粒子自驱动模型(社会力模型)可以较好地体现3种力的作用, 但由于它是一种连续型模型, 运算的速度较慢并很难得到改善. 目前研究较多的离散型模型, 如元胞自动机模型和格子气模型等, 可以达到较高的运算速度, 但很难考虑到摩擦力与排斥力的作用, 造成运算结果误差较大. 针对这种情况, 本文在经典元胞自动机模型的基础上, 量化确定了摩擦力和排斥力的运算规则, 提出了一种新的元胞自动机模型. 通过将模型的运算结果与多粒子自驱动模型进行比较表明, 新模型在人员行为、疏散速度以及“快即是慢”效应等方面都可以得到与后者相同的结果, 而运算速度则与普通的元胞自动机及格子气模型相当, 比社会力模型大为提高.     

面向多租户Web应用的性能隔离方法

提出一种面向应用级共享的多租户Web应用性能隔离方法．首先建立基于事务处理链的应用级资源管理模型，基于信号量机制给出了模型的并发控制算法，支持事务级、分阶段的多租户Web应用资源管理，并在一次事务处理的各阶段实现线程复用，避免因修改交互协议而产生的再工程代价．基于上述工作，给出多租户性能隔离算法及策略，并利用TPC—W电子商务应用验证方法的系统开销及有效性．实验结果表明，该方法可以有效降低租户资源侵占行为的影响，并避免系统过载．     

移动机器人软故障检测与补偿的自适应粒子滤波算法

软故障泛指系统性能偏离正常水平。软故障补偿对于移动机器人定位、建图、导航以及安全至关重要。机器人是计算和存储资源受限的高度非线性、非Gauss系统，使得软故障诊断与补偿具有很大难度。文中提出一种自适应粒子滤波器算法，利用激光雷达测量信息对两类软故障（航迹推算传感器故障以及车轮被卡或打滑异常）进行补偿。首先分析了移动机器人系统的运动学模型、测量模型以及故障模型，提取了5个残差特征，故障检测通过残差特征超过给定的阈值实时地获得。其次，设计一个自适应粒子滤波器用于故障补偿，自适应体现在相互联系的两个方面：（1）根据残差特征自适应地调整线速度和偏航率的噪声方差；（2）在重采样阶段抽取粒子数目不同的两个粒子集（代表同一分布的两种近似），根据两个近似分布的Kullback-Leibler（KL）距离自适应地调整粒子数目。若KL距离较大，则增加粒子数目，反之则减少粒子数目。从理论上证明了算法的正确性，并通过故障情形下移动机器人位姿跟踪问题验证了算法的效率与精度。     

差分代换的一些几何性质

文中从一种新的视角,即从几何上来研究差分代换,给出了差分代换的几何意义,引入代换收敛性概念,证明了逐次差分代换是不收敛的;得到了一个有趣结果:给定一个k维有理超平面,则用有限次差分代换总能把该k维有理超平面变为新变量所在坐标系的k维坐标面;给出了半正定型在逐次差分代换下不能终止的一个充分条件.     

模糊综合评判法在城市交叉口综合质量评价中的应用

为了全面评价城市交叉口综合质量,选择了交叉口混合交通运行状态评价指标,并通过指标隶属度函数研究建立了相应的模糊综合评判模型.结合实例对其综合运行质量进行了评价分析和聚类排序,从而为评估城市交通拥堵、制定相应的交通管理和控制策略提供了一种有效的定量分析方法.