运行时验证技术的研究进展

运行时验证是一种轻量级的验证方法,通过实时地监测系统的行为,验证系统的正确性,及时发现冲突,并发出警告或作出反应。运行时验证技术已经得到了越来越多的应用,以确保软件系统的正确性。总结了近年来运行时验证技术的研究进展,首先介绍了运行时验证的概念、原理和分类,接着深入分析了现有的几种解决方案,并对该领域中的研究热点进行了深入探讨,最后分析了运行时验证技术面临的主要挑战,并对未来该领域的研究方向进行了展望。     

基于交互信息的投机并行化方法*

针对投机并行化中如何权衡策略并确定合适的执行模型来获取理想性能的问题,提出了一种基于交互信息的投机并行化方法,利用交互信息来确定投机并行化的执行模型,建立相关评价模型,并着重从线程抽取创建角度提出了相应的策略及对应的性能评价。通过实验表明,基于交互信息进行“按需”并行化,可以达到所需的性能要求。     

基于事务性执行的投机并行多线程软件模拟

基于事务性执行的投机并行多线程是一种适合未来多核微处理器架构的新型并行程序设计和编译技术.但在此基础上的并行程序执行过程更为复杂,程序执行过程的模拟成为关键问题之一.本文提出利用二进制代码级动态插桩技术对投机并行多线程程序进行功能性模拟,设计并实现了完整的软件平台,可精确地模拟和监控并行程序的线程级投机执行过程,检测访存冲突,从而实现投机并行多线程的语义.该软件平台同时可以作为进一步研究投机多线程并行程序真实执行过程的基础,并有效支持投机并行多线程编译器的设计和分析.     

基于部件设计的运行时验证

研究软部件设计中的可靠性问题,对这一问题主要诉是,当一个已存软部件的正确性无法得到确认时,在具具体实现不可知的情况下,如何提高它的运行时可靠性？为解决这一问题,该文首先构造一个能够用于软部件动态语义检测的抽象模型;然后通过在设计中系统地引入一些运行时技术以保证基于部件软件的可靠性。这些运行时技术包括：（１）包裹部件。作为额外的一层设计,根据软部件的接口说明自动生成,用于检测运行时错误;（２）虚拟部     

数据流Java并行程序设计模型的设计、实现及运行时优化

提出了一种具有数据流特征的Java并行程序设计模型,并针对该模型提出了一种基于运行时信息反馈的自适应优化算法,使得运行时系统可以利用数据流程序所暴露出的数据并行性,加速程序的运行.此外,在该模型中加入了数据流多态的概念,扩展了该模型的面向对象特性.在一个实际的开放源码Java虚拟机中实现了上述程序设计模型及优化方法.在实际多核多线程机器上的实验结果表明,所提出的程序设计模型及优化能够充分利用硬件的并行处理能力,显著地提高了程序的性能.     

一种基于运行时交互约束的COTS构件集成测试用例生成方法

COTS(Commercial Off-The-Shelf)构件的源代码不可得,而且规约通常缺少交互语义信息,使得集成了COTS的构件软件系统无法采用基于源代码和基于规约的集成测试用例生成方法.提出基于运行时交互约束的COTS构件集成测试用例生成方法.方法在构件软件系统的初始功能测试用例执行过程中,获取COTS构件在系统上下文环境中的运行时接口交互约束信息,建立COTS构件与系统中其它构件的交互约束模型,根据建立的构件交互约束模型生成集成测试用例.当替换、更新集成的COTS构件时,采用生成的集成测试用例验证重新集成的COTS构件与系统其它构件交互的正确性.实现方法的自动化工具原型,并采用真实的系统实例对生成的测试用例的有效性进行了初步评估.     

一种分布式软件运行时监控机制

软件在信息社会生活中起着越来越重要的作用,而如何提高软件系统的可信性也成为研究的重要课题,而运行时监控技术是提升软件可信性的重要方法之一.针对当前软件网络化、分布化的发展趋势,提出了一种全新的分布式软件运行时监控机制,通过建立监控服务使得远程监控客户端能够实现对软件系统跨网络、跨平台、实时的监控,从而进一步增强原有软件系统的可信性.这种机制在实际软件系统中获得了有效的应用,具有可行性和合理性.     

面向SQLite3数据库API调用序列的并行运行时验证方法

作为轻量级的高可靠嵌入式数据库, SQLite3已被广泛应用于航空航天和操作系统等多个安全攸关领域, 其提供了丰富灵活API函数以支持用户快速实现项目构建.然而, 不正确的API函数调用序列会导致严重后果, 包括运行错误、内存泄露和程序崩溃等.为了高效准确地监控SQLite3数据库API函数的正确调用情况, 本文提出了基于多核系统的并行运行时验证方法.该方法首先分析API函数文档, 自动挖掘相关API调用序列规约描述, 辅助人工将其形式化表达为具有完全正则表达能力的命题投影时序逻辑公式; 然后在程序运行时, 采用多任务调度策略, 将程序执行产生的状态序列分割并对不同片段并行验证.实验结果表明, 该方法能够发现调用SQLite3数据库API函数的30个被验证C程序中, 违背API函数调用序列规约的达16个.另外, 与传统串行运行时验证方法的对比实验表明, 本文提出的并行运行时验证方法能够有效提高多核系统的验证效率.     

基于值-剖面的OpenMP运行时优化系统

本文设计并实现了一个基于值一剖面的OpenMP运行时优化系统CCRG OpenMP。它能够根据常见的值的组合优化并行区域，并且在运行时只有并行区代码需要重编译和管理。CCRG OpenMP基于动态重编译技术，避免了目前静态多版本技术的不足。同时，值-剖面的收集和分析由独立的动态优化器线程完成，降低了动态重编译引入的开销。SPEC OMP2001基准测试表明，我们基于值一剖面的Open MP优化系统能够较大地提高程序性能。     

一种基于路径优化的推测多线程划分算法

推测多线程(speculative multithreading,简称SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,基于控制流图和分支预测技术的线程划分方法,不可避免地会受到划分路径上所存在的控制依赖和数据依赖的制约.目前,在传统的线程划分算法中存在的一个重要问题是,在对划分路径进行选取时只考虑了控制依赖影响却不能有效地综合考虑数据依赖的影响,进而导致不能选取最佳的划分路径.因此,针对传统方法中这种依赖评估方法效率低下的问题,设计并实现了一种基于路径优化的线程划分算法.该算法通过引入基于程序切片技术的预计算方法,建立一种路径评估方法来评估程序间的控制和数据依赖.同时,引入控制线程体大小的启发式规则,以便有效地解决负载不平衡的问题.基于Olden测试集的测试结果表明,所提出的算法可以有效地对非规则程序进行划分,其平均加速比可以达到1.83.     

Speculative Parallelization of Sequential Loops on Multicores

The advent of multicores presents a promising opportunity for speeding up the execution of sequential programs through their parallelization. In this paper we present a novel solution for efficiently supporting software-based speculative parallelization of sequential loops on multicore processors. The execution model we employ is based upon state separation, an approach for separately maintaining the speculative state of parallel threads and non-speculative state of the computation. If speculation is successful, the results produced by parallel threads in speculative state are committed by copying them into the computation’s non-speculative state. If misspeculation is detected, no costly state recovery mechanisms are needed as the speculative state can be simply discarded. Techniques are proposed to reduce the cost of data copying between non-speculative and speculative state and efficiently carrying out misspeculation detection. We apply the above approach to speculative parallelization of loops in several sequential programs which results in significant speedups on a Dell PowerEdge 1900 server with two Intel Xeon quad-core processors.     

Towards Software Architecture and Mechanisms for Improving Runtime Variability of Internetware System

As an emerging software paradigm, Internetware is proposed to handle openness, dynamism of software systems in the context of Internet, which implies that such software systems typically have runtime variability that can be improved dynamically to handle various or even unexpected changes of requirements and open environment. Though many progresses of Internetware software technologies have been made to support the adaptation, evolution, context-awareness, etc. of Internetware, how to construct Internetware systems with the ability to improve their runtime variability is still a great challenge in the literature of software engineering. In this paper, we propose software architecture and mechanisms for Internetware systems to support the improvement of their runtime variability by combining software variability and autonomic computing techniques. The Internetware system is organized as three levels that are consist of variable autonomic elements and Internetware entities, and architecture of these software entities is defined and discussed respectively. Moreover, we put forward a series of runtime mechanisms based on these levels, including module selection, intermediator and horizontal management, to realize operations upon the variation points and variants in software architectures and thus achieve the improvement of runtime variability. We develop a sample of Personal Data Resource Network to depict the requirements and scenario of improving runtime variability, and further study the case based on our proposed approach to show its effectiveness and applicability.     

Runtime analysis of search heuristics on software engineering problems

Many software engineering tasks can potentially be automated using search heuristics. However, much work is needed in designing and evaluating search heuristics before this approach can be routinely applied to a software engineering problem. Experimental methodology should be complemented with theoretical analysis to achieve this goal. Recently, there have been significant theoretical advances in the runtime analysis of evolutionary algorithms (EAs) and other search heuristics in other problem domains. We suggest that these methods could be transferred and adapted to gain insight into the behaviour of search heuristics on software engineering problems while automating software engineering.     

Smith-Waterman算法的若干优化及并行实现

Smith-Waterman算法是目前被使用最广泛的序列相似性比较算法之一,它适用于寻找局部相似序列对。该算法精确度较高,一直沿用到现在。目前,使Smith-Waterman算法提速,寻找该算法的优化方法,是世界各地的科学家们正花费大量心血研究的课题。该文从算法并行化着手,充分利用近期蓬勃发展的高性能计算机系统,提出了若干Smith-Waterman算法的优化思想,并在cluster机上实现。     

基于运行时模型的无线传感网管理方法

无线传感网是物联网的核心,主要解决物联网中的信息感知问题,通过散布在特定区域的成千上万的传感器节点,采集环境中各种信息并连接到互联网上.然而,传感设备所采集到的数据是实时的、数量庞大且无良好结构的,要将采集到的数据映射到应用系统的问题域空间,就不得不编写大量的映射代码.为了快速定制和开发物联网系统,提出一种基于运行时模型的无线传感网管理方法：首先,在传感设备管理接口基础上构造运行时模型,并维护运行时模型与采集到信息的数据同步;其次,基于运行时模型,对不同传感设备采集到的数据进行定制、抽取和合并,实现通过组合模型对场景中不同的传感设备进行统一管理;最后,通过模型转换,实现组合模型到应用场景模型的映射,从而能够面向应用场景进行物联网系统的开发.还实现了基于运行时模型的智慧社区原型系统,并对方法的可行性和有效性进行了验证.     

多处理部件并行优化方法研究

针对多处理单元(PE)并行优化中运行时间和资源消耗随PE数量变化而增加的问题,分析多PE并行中运行时间和资源消耗随PE数量的变化规律,建立基于运行时间和资源消耗的优化目标函数,并从理论上证明优化目标函数最小值的存在性和唯一性,提出基于运行时间与资源消耗的多PE并行优化方法。该优化方法可在最小资源消耗的情况下实现运行时间的最优化。利用灰度共生矩阵和单精度浮点矩阵乘法的多PE优化方法进行验证。实验结果表明,多PE并行的优化方法实现了运行时间和资源消耗的优化,在运行时间上该方法比已有方法最高快6.79倍,在运行时间和资源消耗的综合对比上该方法最高为已有方法的3.3倍,能够实现基于运行时间和资源消耗的优化。     

智能家居情境感知服务的运行时建模与执行方法

随着智能家居基础设施的不断发展,智能家居逐渐进入以智能服务为特征的新时期.大量复杂、异构的智能设备相互协同,构成海量、智能、集成的智能家居应用.其中,情境感知服务根据服务对象所处情境的变化为其提供准确的服务,是智能家居应用的典型代表.目前,情境感知服务往往面向场景进行构建,其设备多样性和服务随需性给应用开发带来极大的挑战.开发者需要熟悉设备管理接口、进行接口调用和交互,同时,理解服务功能和质量需求,进行管理逻辑的编写.为了快速定制和开发情境感知服务,将知识图谱引入开发过程,提出一种智能家居情境感知服务的运行时建模与执行方法：首先,提出智能家居情境感知服务知识图谱概念模型,定义其情境中各种概念和关系;其次,提出智能家居情境感知服务知识图谱实例模型的构造与维护机制,通过运行时概念、关系实例表示情境知识;最后,提出基于知识推理的智能家居情境感知服务执行方法,通过知识推理自动执行设备功能.面向实际场景,构建智能家居原型系统.实验结果显示,该方法能够实现情境感知服务运行时建模与执行,其代码减少量超过90%.