摘要:随机模型检验是经典模型检验理论的延伸和推广,由于其结合了经典模型检验算法和线性方程组求解或线性规划算法等,并且运算处理的是关于状态的概率向量而非经典模型检验中的位向量,所以状态爆炸问题在随机模型检验中更为严重.抽象作为缓解状态空间爆炸问题的重要技术之一,已经开始被应用到随机模型检验领域并取得了一定的进展.以面向随机模型检验的模型抽象技术为研究对象,首先给出了模型抽象技术的问题描述,然后按抽象模型构造技术分类归纳了其研究方向及目前的研究进展,最后对比了目前的模型抽象技术及其关系,总结出其还未能给出模型抽象问题的满意答案,并指出了有效解决模型抽象问题未来的研究方向.

摘要:GUI测试用例集约简是降低GUI软件测试成本的有效手段.GUI软件的消息循环机制以及事件驱动特性,导致传统的基于控制流和数据流的测试用例集约简技术难以直接应用于GUI测试用例集约简.如何在尽可能保持原有测试用例集缺陷发现能力的基础上,尽可能地降低GUI测试用例集规模,是GUI测试用例集约简的一个挑战.以事件处理函数为核心,结合控制流和数据流技术,根据事件处理函数代码结构特征以及事件处理函数之间的数据依赖关系定义测试冗余规则,制定并实现了3种测试用例集约简技术.实验结果表明:与已有技术相比,其中两种根据事件处理函数之间的数据依赖关系制定的测试用例集约简技术达到了较好的约简效果.

摘要:服务因其灵活的应用机制,逐渐成为软件开发过程中的主要载体.面对网络中涌现出的大量功能相同或相似而QoS(quality of service)不同的服务群体,如何快速、准确地定位到所需要的服务个体,仍是一项十分具有挑战性的工作.基于服务对功能的封装特性,提出一种基于服务功能规约的服务选择方法,将功能相关的抽象服务规约为一个粒度更大的服务级的抽象服务;然后,针对规约后的大粒度抽象服务完成服务发现和组合优化的过程.由于规约操作能够有效减少参与服务组合优化的抽象服务的个数以及相应的候选服务的个数,从而使算法的执行效率得到有效提升.实验结果表明:该算法与传统的启发式算法相比执行效率更高,并且对服务组合规模及候选服务规模表现出更好的扩展性.

摘要:服务器系统最无法忍受的就是因为频繁出错甚至崩溃影响正常用户的运行,因此需要系统具有自恢复能力.目前研究应用较多的自恢复策略即回滚检查点策略,并不适用于多用户服务器程序的恢复.针对多用户服务器程序的特点,设计了一种基于虚拟机的自恢复系统VMSRS(virtual machine monitor-self recovery of service program).VMSRS的基本思想是以虚拟机监控器为恢复主体,充分利用虚拟机作为第三方底层系统以及硬件资源的管理监控者这些特点所带来的优势,严格保证用户数据一致性、数据元数据操作原子性、恢复数据安全隔离性等;同时应用改进的SRS(self recovery of service program)思想,在错误发生时不进行回滚,控制错误不让其影响正常用户,并保证正常用户和服务器可以顺利地向前运行,就像没有错误发生一样;并利用系统本身和VMSRS的清理机来避免回滚.研究工作设计实现了包括抑制错误、请求恢复、监控、存储管理等模块在内的自恢复系统VMSRS,主要针对多用户服务器系统中的内存错误来进行恢复.通过对基本功能、基本性能、整体功能的实验分析表明,VMSRS在不进行回滚、保证性能的前提下,提供了良好的恢复数据安全性以及完善的用户状态数据一致性保证,可以很好地恢复多线程程序,不需要对线程进行任何限制.同时,该研究工作也为在虚拟化技术条件下研究设计自恢复系统进行了很好的实践和探索.

摘要:基于占优关系的可测试性转化,是将目标语句覆盖问题转化为位于该语句之前的占优语句(集)覆盖问题,能够对含有标志变量的程序进行测试.但是当占优语句(集)不止一个时,如何从这些语句(集)中选择最容易覆盖的作为新的目标语句(集),至今没有有效的方法,从而限制了可测试性转化的应用范围.研究了占优语句(集)选择问题,提出了基于覆盖难度的占优语句(集)选择方法.首先,提出评价语句覆盖难度的4个指标,并给出这些指标的计算方法;然后,基于上述指标,利用Topsis方法排序,选择最容易覆盖的占优语句(集);最后,将所提出的方法应用于多个基准与工业程序测试,实验结果表明,覆盖基于该方法选择的占优语句(集)能够显著提高测试数据生成的效率.

摘要:溯因推理为归纳与演绎推理之外的另一种重要的推理形式,在人工智能等领域有着广泛的应用.通俗地讲,溯因推理是从观察(结果)去推断原因的推理过程.不同于以往的研究思路,通过使用本原蕴含式和素蕴含,证明了可以把命题逻辑和命题模态逻辑系统S5中求溯因问题的极小解释转化为求对应集合的极小碰集问题.给出了求解溯因问题的一种新方法.

摘要:C2C电子商务交易具有匿名性、随机性、动态性的特点,交易双方仅通过虚拟网络交换信息,缺乏基本的信任基础,交易存在较大的风险.构造科学的信任计算模型、客观度量卖家的可信度、辅助买家(消费者)做出正确的购买决策,是降低交易风险的有效手段之一.为此,从买家的角度出发,详细讨论了信任网络的基本概念及其相关属性,并以信任的时间敏感性、不对称性、可传递性和可选择性为基础,建立了C2C电子商务环境下的动态信任算法(C2C dynamic trust algorithm,简称CDTA).该算法首先通过买家自身的交易经验计算买家对卖家的直接信任度,然后计算来自信任网络中买家的朋友对卖家的推荐信任度,最后通过信任调节因子集成直接信任度和推荐信任度来获得买家对卖家的信任度.仿真实验分析结果表明:一方面,该算法考虑了交易的多属性及其相关性,信任评价的粒度更加细化,使得信任计算的结果更加客观;另一方面,评价相似度可以很好地筛选出符合买家“个性”的推荐节点,使推荐信任度更准确,可以进一步抑制恶意节点对信任算法的影响.

摘要:稀疏编码理论应用于信号处理的各个领域,为了获取优化的稀疏编码,需要通过训练获取数据词典.提出了一种复数域数据词典的快速训练方法,将词典训练问题转化为最优化问题并交替地对词典原子和编码进行最优化而得到最终训练词典.在对词典原子的最优化过程中,采用具有记忆性的在线训练算法;而在对编码进行最优化的过程中,采用交换乘子方向方法进行实现.通过实验得出:所提出的算法能够有效地提高数据词典的训练效率,在保证收敛值的同时缩短训练时间,并且对于训练样本中的噪声具有鲁棒性.

摘要:现有模型检测工具的形式化规范语言,如计算树逻辑(computation tree logic,简称CTL)和线性时序逻辑(linear temporal logic,简称LTL)等的描述能力不足,无法验证ω正则性质.提出了一个命题投影时序逻辑(propositional projection temporal logic,简称PPTL)符号模型检测工具——PLSMC(PPTL symbolic model checker)的设计与实现过程.该工具基于著名的符号模型检测系统NuSMV,实现了PPTL的符号模型检测算法.PLSMC的规范语言PPTL具有完全正则表达能力,这使得定性性质和定量性质均可被验证.此外,PLSMC可以有效地缓解模型检测工具中容易发生的状态空间爆炸问题.最后,利用PLSMC对铁路公路交叉道口护栏控制系统的安全性质和周期性性质进行验证.实验结果表明,PPTL符号模型检测工具扩充了NuSMV系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证.

摘要:无线传感器网络的固有通信特征会引发能耗不均衡现象,进而产生能量空洞问题;混合数据传输是新近提出的一种能量空洞避免策略,其能量均衡性能主要取决于各节点的传输概率.然而,传输概率的设置还缺乏相关理论模型的指导,而且在节点传输距离受限的条件下能否通过混合传输策略实现全网能量均衡,还有待进一步研究.将一维网络中混合传输策略的能量均衡问题转化为传输概率的优化分配问题,通过相应的形式化模型,推导传输概率的精确表达.研究中发现:传输概率主要取决于节点的位置,但当网络片段的个数超过某一阈值时,传输概率的取值非法,无法应用混合传输策略均衡网络能耗.在此基础上,从理论上给出了全网能量均衡的条件,证明仅当网络片段数不超过n₀时全网能量均衡才能实现,n₀仅取决于一个文中新发现的系数α,α是通信系统的能耗溢价率.还分析了传输距离设置对能量均衡的影响,给出了一般情况下混合传输策略的能量均衡上限.通过仿真实验对所给出的能量均衡条件进行了验证,实验结果与理论分析表明:该条件下,基于所提方法设置传输概率,能够均衡所有节点的能耗.

摘要:针对典型复杂网络模型仅描述了复杂系统中同一类个体及其间一种相互关系且对问题的讨论仅局限于同一个系统的问题,基于能够描述复杂系统中异类个体间多种关系的多子网复合复杂网络模型,导入多维向量空间,将网络节点间的关系映射为多维向量,定义了向量复合网.在此基础上,将该模型的动态组网运算(加载与退缩)转化为向量空间的基变换,给出了加载运算与退缩运算的形式描述,实现了多子网复合复杂网络的可计算.建立并分析了我国铁路客运复合网,通过网络动态重组运算,基于高速铁路子网与低速铁路子网的拓扑性质,给出了我国铁路发展现状分析.

摘要:基于无线传感网的物联网感知层传统的“全网”、“周期性”重新成簇的簇维护模式因超范围过度维护,存在维护成本高、能量浪费严重、服务全面中断、响应不及时等缺点.局域按需簇维护方法(local and on-demand maintenance of clusters,简称LDMC)将簇维护操作控制在簇受损的时间和空间范围内,通过设置触发源、预处理和维护动作分别解决簇维护启动、簇维护方式和簇维护范围问题,不仅能够克服簇更新周期确定的困难,而且可在节点失效和新节点加入时对网络拓扑和路由变化及时进行响应,减小突发事件对网络功能的影响,改善网络的稳定性并降低其维护开销.基于NS2仿真平台,分别从能量消耗、数据传输、负载平衡和突发事件响应等角度对该方法进行了测试对比,仿真结果表明,该方法能够明显减少簇维护的能量消耗、延长网络生存时间,并增加传输数据包的 总量.

摘要:针对多路径并发传输模型的整体性能在路径性能存在差异时会急剧下降的原因进行分析,给出了获取通信路径传输时延的有效评估方案,并在此基础上提出了一种基于传输时延预测的多路径并发传输数据分配算法.该算法通过获取和预测数据块在各条路径上引入的传输时延,以按序到达为目标对多路径并发传输模型发送回合内和发送回合间的数据分配过程进行优化,能够有效地减少路径传输性能差异对多路径并发传输模型整体性能带来的影响.分析和实验结果表明,该算法相对于默认的轮询数据分配算法能够取得较好的运行性能.

摘要:MapReduce是一种适用于大规模数据密集型应用的有效编程模型,具有编程简单、易于扩展、容错性好等特点,已在并行和分布式计算领域得到了广泛且成功的应用.由于MapReduce将计算扩展到大规模的机器集群上,处理数据的合理放置成为影响MapReduce集群系统性能(包括能耗、资源利用率、通信和I/O代价、响应时间、系统的可靠性和吞吐率等)的关键因素之一.首先,对MapReduce编程模型的典型实现——Hadoop缺省的数据放置策略进行分析,并进一步讨论了MapReduce框架下,设计数据放置策略时需考虑的关键问题和衡量数据放置策略的标准;其次,对目前MapReduce集群环境下的数据放置策略优化方法的研究与进展进行了综述和分析;最后,分析和归纳了MapReduce集群环境下数据放置策略的下一步研究工作.

摘要:虚拟化技术已成为云计算平台中的关键性支撑技术.它极大地提高了数据中心的资源利用率,降低了管理成本和能源消耗,但同时也为数据中心带来了新的问题——性能干扰.同一平台上的多虚拟机过度竞争某一底层硬件资源(如CPU,Cache等),会造成虚拟机性能严重下降;而出于安全性和可移植性的考虑,底层平台管理者需要尽量避免侵入式监测上层虚拟机,因而,如何透明而有效地从底层估算虚拟机性能干扰,成为虚拟化平台管理者必须面临的一个挑战.为应对以上挑战,提出了一种基于硬件计数器的虚拟机性能干扰估算方法.硬件计数器是程序运行期间产生的硬件事件信息(如CPU时间片、缓存失效次数等),已有工作主要利用大规模分布式系统任务相似性查找产生异常硬件计数器数据的节点,而没有探究硬件事件变化与性能干扰之间的直接关系.通过实验研究发现,硬件计数器(last level cache misses rates,简称LLC misses rates)与不同资源需求的应用性能干扰存在不同的关联关系;以此建立虚拟机性能干扰估算模型,估算虚拟机性能.实验结果表明:该方法可以有效地预测CPU密集型应用和网络密集型应用的性能干扰大小,并仅为系统带来小于10%的开销.

摘要:在云计算技术和大数据技术的推动下,IT资源的规模不断扩大,其能耗问题日益显著.研究表明:节点资源利用率不高、资源空闲导致的能源浪费,是目前大规模分布式系统的主要问题之一.研究了MapReduce系统的能耗优化.传统的基于软件技术的能耗优化方法多采用负载集中和节点开关算法,但由于MapReduce任务的特点,集群节点不仅要完成运算,还需要存储数据,因此,传统方法难以应用到MapReduce集群.提出了良好的数据布局可以优化集群能耗.基于此,首先定义了数据布局的能耗优化目标,并提出相应的数据布局算法;接着,从理论上证明该算法能够实现数据布局的能耗优化目标;最后,在异构集群中部署3种数据布局不同的MapReduce系统,通过对比三者在执行CPU密集型、I/O密集型和交互型这3种典型运算时的集群能耗,验证了所提出的数据布局算法的能耗优化效果.理论和实验结果均表明,所提出的布局算法能够有效地降低MapReduce集群的能耗.上述工作都将促进高能耗计算和大数据分析的应用.

摘要:目前,节能已成为云数据中心的研究热点.建设节能的云数据中心不仅可以减少用电消耗,而且可以提高系统的可靠性.现有的云中心节能调度算法缺乏在任务调度级别的考虑,使得任务执行效果受到较大影响.为此,首先给出了一种基于滚动优化的实时任务调度器结构,然后详细分析和构建了任务能量消耗模型.在此基础上提出了一种实时非周期任务节能调度算法EARH(energy-aware scheduling algorithm).EARH采用的滚动优化策略能够被拓展并集成其他节能调度算法.此外,提出了资源动态增加与缩减策略,用于在系统可调度性与节能两方面进行权衡.最后,通过大量的模拟实验验证了EARH的性能.与其他3种基准算法相比,其实验结果表明,EARH的调度质量优于其他算法,可有效提高系统性能.

摘要:操作系统漏洞经常被攻击者利用,从而以内核权限执行任意代码(返回用户态攻击,ret2user)以及窃取用户隐私数据.使用虚拟机监控器构建了一个对操作系统及应用程序透明的内存访问审查机制,提出了一种低性能开销并且无法被绕过的内存页面使用信息实时跟踪策略;结合安全加载器,保证了动态链接库以及应用程序的代码完整性.能够确保即使操作系统内核被攻击,应用程序的内存隐私数据依然无法被窃取.在Linux操作系统上进行了原型实现及验证,实验结果表明,该隐私保护机制对大多数应用只带来6%~10%的性能负载.

摘要:近几年来,互联网上出现了一类称为Mashup的新型应用,它使最终用户能够个性化地聚合和操作分布在互联网上的数据源.然而,关于Mashup在动态环境下运行时的性能研究还比较缺乏.为此,利用缓存技术提出了Mashup运行时的性能优化方法——POMO.POMO具有以下3个主要创新点:首先,POMO通过算子序列的缓存点的成本和收益模型实现了动态缓存点选取;其次,POMO通过缓存点的B+树索引实现了缓存点重用;第三,POMO通过两阶段切换数据传输协议实现了缓存点更新.实验分析结果表明:POMO减少了Mashup在动态环境下的运行成本,提高了Mashup运行时的性能