摘要:从需求的角度对测试用例的优先级进行排序,定义了一个多目标的测试用例优化排序问题,引入关注需求覆盖率、测试用例重要度和测试用例失效率这3个测试用例优先级影响因子,分别定义权重因子α,β,γ用于权衡3个因子.设计了关注需求覆盖率和测试用例失效率的在线估计方法及算法,在此基础上,设计了一种基于多目标优化的测试用例优先级在线调整策略,该策略可利用测试过程中收集到的反馈信息,对测试用例优先级进行在线调整,实现在尽早达到测试覆盖率标准的同时,尽早覆盖重要的和具有较高失效率的测试需求,从而解决尽早检测到更多的、严重等级较高的软件缺陷这一多目标测试用例优化问题.实验结果表明:与随机测试、传统的单目标优先级排序方法和确定性排序方法相比,所提出的策略能够在更短的时间内完成同等质量的软件测试,从而提高了测试效率.

摘要:传统的NHPP(non-homogeneous Poisson process)模型在实际的测试当中被证明是成功的.但是,由于传统的NHPP模型用的是理想的假设,例如,假设故障检测率是常数、平稳变化和规律变化,模型的性能在实际的测试环境中总是受到损害.因此,提出一个基于NHPP的软件可靠增长模型,并且考虑故障检测率的不规则变化情况,这种变化符合故障检测率在实际的软件测试过程中的变化.通过相关的实验验证了所提出的NHPP模型的拟合和预测能力.实验结果表明:在用实际的故障数据进行拟合和预测的过程中,所提出的模型与传统的NHPP模型相比,有更好的拟合和预测性能.同时,也给出了所提出模型相应的置信区间.

摘要:针对一类中断驱动的航天控制系统,给出了有界模型检验的算法.这类系统由中断处理程序和操作系统调度的任务组成.当中断发生时,对应的中断处理程序响应中断事件,并可以修改控制变量值,以便在系统任务中完成后续工作.操作系统周期性地调度任务序列处理日常事务以及中断事件的后续工作.使用了带中断标记的时间自动机对中断事件和任务调度事件进行建模,并使用中断向量表和中断处理程序的伪代码模型共同描述中断的处理过程.控制变量将中断处理过程和系统任务相关联,中断处理程序可以设定某个控制变量,而系统任务则通过检查该控制变量来确定是否需要进行后续处理.对于这样的形式化模型,给出了检验关键时序性质的有界模型检验算法.该算法使用深度优先的方式遍历所有长度小于等于K的可行路径,并使用SMT Z3实现了对时间约束和规约的处理.

摘要:为数众多的变异体产生的高昂测试代价严重影响了变异测试技术在实际程序中的应用.为了大幅度减少弱变异测试中变异体的数量,提出基于统计占优分析的变异体约简方法.该方法首先利用变异前后的语句构造变异分支,并将所有变异分支集成到原程序中,形成新的被测程序;然后,通过统计测试用例对各个变异分支的覆盖信息,确定变异分支之间的占优关系;最后得到非被占优分支集,其对应的变异体就是约简后的变异体.将该方法用于8个程序的测试,结果表明:该方法能够约简平均90%的变异体,从而显著提高了变异测试的效率.

摘要:模型检测是通信顺序进程(communicating sequential processes,简称CSP)形式化验证的重要手段.当前, CSP模型检测方法基于操作语义,需将进程转化为迁移系统,进而提取语义模型,但转化过程较为复杂;待验证性质采用CSP语言进行描述,虽然有利于精炼检测(refinement checking),但描述能力较弱,通用性不强.鉴于此,提出了一种新的CSP指称语义模型——关键迹模型(critical-trace model)及基于该指称语义模型的CSP模型检测方法,并证明了其验证的可靠性,避免了上述问题.关键迹模型采用递归策略计算,待验证性质采用线性时态逻辑(linear temporal logic,简称LTL)描述.基于回答集程序设计(answer set programming,简称ASP)实现了关键迹模型的自动生成及LTL的自动验证,并开发了一个CSP模型检测原型系统——T_ASP.实验结果表明:与类似系统相比,该系统的描述能力更强,验证结果的准确性更高,且可同时验证多条性质,在性质不满足时还可提供多条反例.

摘要:可信软件的可信性由其功能需求和非功能需求共同来体现,其中,非功能需求的实现是可信软件获得用户对其行为实现预期目标能力的信任程度的客观依据.针对可信软件的重要性以及对可信软件的迫切需求,在可信软件的早期需求工程阶段,提出可信软件非功能需求驱动的过程策略选取方法.首先,对可信软件需求进行定义,提出由功能需求和非功能需求中的可信关注点构成可信需求,非可信关注点的非功能需求则定义为软目标,用于表达质量需求,基于模糊集合论和信息熵对可信软件非功能需求进行排序并获取可信关注点和软目标.在此基础上,提出可信软件非功能需求驱动的过程策略选取方法.传统的软件早期需求工程阶段的目标是为了获取满足需求的技术及设计决策,与此不同,本文对可信软件非功能需求进行分析的目标是获取过程策略,从过程角度解决可信软件生产问题.由于非功能需求间复杂的相关关系,尤其是因为存在冲突关系,故提出了基于可满足性问题求解方法推理过程策略的方法,选取满足可信软件非功能需求的过程策略.最后,通过第三方可信认证中心软件的案例,说明所提出方法的可行性.

摘要:集成式数据流挖掘是对存在概念漂移的数据流进行学习的重要方法.针对传统集成式数据流挖掘存在的缺陷,将人类的回忆和遗忘机制引入到数据流挖掘中,提出基于记忆的数据流挖掘模型MDSM(memorizing based data stream mining).该模型将基分类器看作是系统获得的知识,通过"回忆与遗忘"机制,不仅使历史上有用的基分类器因记忆强度高而保存在"记忆库"中,提高预测的稳定性,而且从"记忆库"中选取当前分类效果好的基分类器参与集成预测,以提高对概念变化的适应能力.基于MDSM模型,提出了一种集成式数据流挖掘算法MAE(memorizing based adaptive ensemble),该算法利用Ebbinghaus遗忘曲线对系统的遗忘机制进行设计,并利用选择性集成来模拟人类的"回忆"机制.与4种典型的数据流挖掘算法进行比较,结果表明:MAE算法分类精度高,对概念漂移的整体适应能力强,尤其对重复出现的概念漂移以及实际应用中存在的复杂概念漂移具有很好的适应能力.不仅能够快速适应新的概念变化,并且能够有效抵御随机的概念波动对系统性能的影响.

摘要:通过大量的实验分析发现:在云桌面场景下,数据拥有者之间的工作相关度越大,则该用户之间存在重复数据的概率越大.基于该实验结果,提出了用户感知的重复数据删除算法.该算法打破了数据空间局部性特征的限制,实现了以用户为单位的更粗粒度的查重计算,可以在不影响重删率的前提下,减少5~10倍常驻内存指纹的数量,并可将每次查重计算的指纹检索范围控制在一个常数范围内,不随数据总量的增加而线性增加,从而有效避免了因为数据总量增加而导致内存不足的问题.除此之外,该算法还能根据存储系统的负载情况自动调整重复指纹检索范围,在性能与重删率之间加以平衡,从而更好地满足主存储场景的需要.原型验证表明,该算法可以很好地解决云计算场景下海量数据的重复数据删除性能问题.与OpenDedup算法相比,当数据指纹总量超出内存可用空间时,该算法可以表现出巨大的优势,减少200%以上的读磁盘操作,响应速度提升3倍以上.

摘要:结构信息是模式匹配的重要辅助信息,当模式中出现多个自身信息相似的元素时,结构信息是正确区分其匹配关系最有效的依据,这在匹配大型模式时显得尤为重要.已有的研究成果对结构信息的使用存在信息不够准确、缺少有效的描述形式、处理耗时等缺点,极大地阻碍了结构信息的使用.为了充分利用结构信息,提出一种基于信息元的模式匹配方法(IU_Based),该方法首先将模式元素按照描述实体的不同划分为不同的信息元,然后计算信息元间的相似度并获取其匹配关系,最后在相互匹配的信息元之间选择元素匹配关系.实验结果表明,IU_Based方法能够有效地解决结构信息使用中的相关问题,提高匹配准确率.

摘要:在大数据时代,数据流是一种常见的数据模型,具有有序、海量、时变等特点.分形是许多复杂系统的重要特征,分形维数是度量系统分形特征的重要指标量.数据流作为动态的复杂系统,其上的分形维数应具有动态、时变、多粒度等特性.提出了多粒度时变分形维数的概念,并设计了基于小波变换技术的数据流多粒度时变分形维数算法.该算法通过对数据流进行离散小波变换,并利用多粒度小波变换树结构在内存中保存数据流的概要信息,可以同时在不同的时间粒度上实时地计算数据流时变分形维数.该方法具有较低的计算复杂度,实验结果表明:该方法可以有效地监控数据流分形维数在不同粒度上的时变特征,深刻地揭示数据流的演化规律.

摘要:随着位置感知移动设备的出现及通信技术和GPS系统的不断发展,基于位置的查询在数据库领域得到了广泛的关注.研究了基于快照的空间范围查询,即,查询在某个时间段位于某个查询范围内的移动对象.范围查询是其他空间查询的基础,例如KNN查询和反KNN查询等,很容易在范围查询的基础上得到.国内外的研究者针对移动对象的范围查询问题提出了一系列的算法,然而这些算法要么关注于解决移动对象的快速更新问题,要么关注于解决范围查询的快速处理问题.在大数据的背景下,查询和更新大量涌入时,不仅要求查询算法有较快的响应速度,还要求它们能够实现较高的吞吐量,但已有算法不能很好地解决高吞吐量的问题.针对移动对象更新数据流和查询数据流,提出一种基于内存的高吞吐量移动对象范围查询算法——双向流连接(DSJ)算法.双向流连接算法采用基于快照的模式,通过在每个快照中重新构建索引的方式,以避免复杂的索引维护操作,充分发挥了硬件的性能;通过每次执行一组查询的方式,增加了数据的局部性,提高了算法的效率;在执行过程中,通过使用SIMD技术以加速查询处理过程.基于以上几点,双向流连接算法能够确保整个系统具有很高的吞吐量.在基于德国路网生成的数据集上对算法进行了测试,实验结果表明,双向流连接算法具有很好的性能表现.

摘要:调度算法一直是交换系统中不可或缺的研究内容.为满足新型高速路由及交换系统的研究需求,提出一种主动授权并发轮询调度算法——CRRD-AG算法.多级交换结构Clos交换网络以其良好的可扩展性作为高速交换结构倍受关注,但与之相适应的调度算法却并不多.目前主流算法,如并发分派算法(CD)和基于轮询的并发分派算法(CRRD),不是吞吐率较低就是所处理的业务流单一.CRRD-AG算法以CRRD为基础,将经典的"请求-授权-接受"的匹配计算模式改进为"主动授权-接受"的匹配模式,不仅能够降低CRRD算法在第1阶段的仲裁信息量,而且充分利用了中间级链路带宽,从而降低了整个系统的平均延迟,提高了吞吐率.进行充分的实验后,其结果表明,无论是在均匀业务,还是在突发业务环境中,CRRD-AG算法都能保证100%的吞吐率,更为重要的是,在不降低吞吐率的情况下能够显著改善分组的平均延迟.

摘要:研究了SPS模型中的扩散变换为二元域上n-MDS矩阵对应的仿射变换构造时,差分概率的估计问题.首先给出任意给定一个差分对时,差分概率上界的估算公式,然后给出该类SPS模型差分概率的一个新上界.模拟实验结果表明,该上界比目前最好的上界更紧致.

摘要:无线传感器网络节点中的廉价晶振极易受到温度、电压、湿度等工作环境因素的影响.节点晶振的这一特性,为室外大规模无线传感器网络时间同步技术带来了两方面的挑战:(1) 过高的通信开销;(2) 精度与能耗之间的不平衡.针对以上问题,提出了一种基于温度感知的、自适应的无线传感器网络时间同步算法.该算法能够依赖本地温度信息对节点时间频偏进行估计及补偿,在保证算法同步精度的同时,降低了网络通信开销.除此之外,提出一种动态同步周期调节机制,使得算法能够根据当前环境温度变化情况对节点同步周期进行动态调节,从而达到了能耗与精度之间的平衡.大量仿真实验结果表明:所提出的时间同步算法可将通信能耗降低至传统同步算法的10%;且在环境温度不断变化的情况下,80%的频偏估计值其误差小于0.5ppm.故,所提出的时间同步方法能够有效地适用于室外环境下部署的大规模无线传感器网络.

摘要:将Biclique初始结构与标准的三子集中间相遇攻击相结合,给出了一种普遍的中间相遇攻击模式.与Biclique分析相比,该模式下的攻击作为算法抗中间相遇攻击的结果更为合理.进一步地,评估了算法TWINE抗中间相遇攻击的能力,通过合理选择中立比特位置以及部分匹配位置,给出了18轮TWINE-80以及22轮TWINE-128算法的中间相遇攻击结果.到目前为止,这是TWINE算法分析中数据复杂度最小的攻击结果.

摘要:构造高效、安全的全同态加密方案目前仍然是一个公开问题.通过扩展近似GCD到近似理想格的方法,首先构造一个基于整数上部分近似理想格问题(PAILP)的有点同态加密方案,并使用Gentry的引导技术将其转换到全同态加密方案.归约有点同态加密方案的安全性到求解部分近似理想格问题;其次,构造基于PAILP的批全同态加密方案和基于近似理想格(AILP)的全同态加密方案;最后,实现基于PAILP/AILP的全同态加密方案,并通过计算实验,其结果表明,所提方案比已有方案性能更好.

摘要:3D模型摆正方向的确定,有利于模型对齐、功能恢复等应用.但已有方法只关注于人造模型的处理,且不少方法还需人工干预,工作效率不高.提出一种可处理任意模型的方法,具有很好的适应性.这主要是基于以下的观察:无论是人造模型还是自然模型,其底部往往是表面内容很贫乏的区域;而主要能观察到这些区域的视点,其视点评分一般很低.因此,根据视点评分,就能有效地寻找到模型的底部朝向,即,模型的摆正方向.为了提高计算的可靠性,进一步引入了物体摆放稳定性和人们观察物体习惯性的度量.实验结果表明:新方法能够高效地处理不同种类的模型,包括一些已有方法中难以处理的情况,并具有很好的计算效率.

摘要:因受遮挡、运动模糊、剧烈形变等因素的影响,稳定且准确的目标跟踪是当前计算机视觉研究领域重要挑战之一.首先采用中层视觉线索的超像素描述目标/背景的部件,以部件颜色直方图作为其特征,并通过聚类部件库的特征集构建初始表观模型,部件表达的局部性和灵活性使该模型能够准确描述目标/背景;然后,利用贝叶斯滤波模型计算目标框的初始状态,并提出相似物体干扰的检测和处理算法以避免跟踪漂移,得到更健壮的结果;最后,为了减弱形变、遮挡、模糊对表观模型的影响以更好地保持目标特征,提出一种基于部件库的特征补集的在线表观模型更新算法,根据部件变化实时反映目标/背景的变化情况.在多个具有跟踪挑战的视频序列上的实验结果表明(共12个视频序列):与现有跟踪方法相比,该算法跟踪结果的中心误差更小,成功帧数更多,能够更准确并稳定、有效地跟踪目标物体.