开放环境特性感知技术

软件学报ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],2011,22(5):865−876[doi:10.3724/SP.J.1001.2011.03800]©中国科学院软件研究所版权所有.Tel/Fax:[phone]开放环境特性感知技术∗黄宇1,2+,余建平1,2,马晓星1,2,陶先平1,2,吕建1,21(计算机软件新技术国家重点实验室(南京大学),江苏南京210093)2(南京大学计算机软件研究所,江苏南京210093)MonitoringPropertiesofOpenEnvironmentsHUANGYu1,2+,YUJian-Ping1,2,MAXiao-Xing1,2,TAOXian-Ping1,2,LÜJian1,21(StateKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),Nanjing210093,China)2(InstituteofComputerSoftware,NanjingUniversity,Nanjing210093,China)+Correspondingauthor:E-mail:[e-mail],üJ.Monitoringpropertiesofopenenvironments.JournalofSoftware,2011,22(5):865−876.:Thispaperproposesaframeworkforthespecificationofopenenvironmentproperties.Thisframeworkenablesconvenientandformalspecificationofpropertiesofasynchronousenvironments,includingtemporalpropertieswhichcannotbehandledintheexistingwork.Thisframeworkalsosupportsimplementationofeffectiveschemesformonitoringenvironmentpropertiesbasedondistributedpredicatedetection.Amiddlewareinfrastructureisdesignedandimplemented,whichsupportsefficientmonitoringofenvironmentpropertiesforbuildinghigh-confidencesystemsinopenenvironments.Thispaperalsoevaluatesdesignoftheproposedinfrastructurewithacasestudy.Keywords:predicatedetection;environmentproperty;high-confidencesoftware;openenvironment摘要:提出了一个开放环境特性描述框架.该框架支持便捷地、形式化地描述异步环境的各种特性,包括那些既有技术不能处理的时序特性.该框架还引入了谓词检测技术,支持高效的环境特性感知机制的实现.开发了一个开放环境特性感知中间件平台,并通过详细的案例分析展示了如何基于所提出的环境特性描述框架与中间件平台,高效地感知环境特性,支持可信软件系统的构建.关键词:谓词检测;环境特性;高可信软件;开放环境中图法分类号:TP311文献标识码:A一般说来,软件系统总是在一定的环境中运行.软件系统利用环境中的各种资源,也通过自身的行为改变环境.Internet的出现和普及,使计算机软件所面临的运行环境从封闭、静态、可控逐步走向开放、动态、难控,在此开放环境下构建行为可理解、结果可预期的可信软件系统的一个基本要求是准确感知并恰当应对环境状态及其变化[1,2].∗基金项目:国家自然科学基金(60903024,60736015,60721002);国家重点基础研究发展计划(973)(2009CB320702);江苏省攀登计划(BK2008017)收稿时间:2009-06-15;修改时间:2009-09-11;定稿时间:2009-12-07;jos在线出版时间:2010-05-28866JournalofSoftware软件学报Vol.22,No.5,May2011在传统软件开发技术中,环境设定通常被当作一个固定的、全局性的假设体现在软件的需求分析、设计实现、部署运行等各个阶段[3].在此过程中的各种验证和确认(verificationandvalidation)技术也以此环境设定为隐含前提.环境设定的遵循主要通过对软件过程,特别是部署过程的管理来实现.这种技术在封闭环境中是可行的,但若要应用于开放环境,则只能将环境状态当作输入的一部分,并在应用逻辑之中予以特别的处理.由于开放环境所固有的复杂性和多变性,这种处理方式往往使得应用逻辑复杂凌乱、难以形式地验证、难以适应环境的变化,最终损害系统的可信性.因而,我们需要遵循“关注分离”这一软件工程基本原则,将对环境的感知和应对从应用逻辑中尽可能地分离出来,予以显式地、系统地处理.即将隐式为主的环境和静态为主的应变转变成显式化环境与动态化应变[2].本文的工作主要研究如何准确感知环境的状态及其变化,虽然这方面的已有许多研究工作[4,5],但其对于构建开放环境下具有容变能力的可信软件尚有一些重要的不足:•缺乏通用、高效而又可靠的环境感知技术框架.从软件技术的角度看,对环境感知就是在基本的环境探测器所给出的原始信息的基础上,通过环境特性建模来建立这些原始信息与高层环境特性语义的联系,进而自动地从原始信息获知环境特性,亦即环境特性感知.尽管人们已提出多种环境模型,但要么形式化程度较弱,难以支持可靠的环境特性感知,如用简单名-值对来刻画环境;要么过于复杂,导致使用困难,实际运行效率低下,如各种环境本体模型[2].•既有环境特性感知技术未充分考虑开放环境固有的分布性.开放环境本质上是一个“真”分布环境,环境设施间的协同是异步的,环境设施之间往往没有同步的全局时钟.环境设施间的通信会面临不确定的延迟[6],并且受资源的限制,环境收集设备经常需要将收集到的环境数据缓存一定的时间再作分发[7].因而,在开放环境下时间的概念需要被重新审视,基于统一全局时钟假设的传统技术难以感知开放环境的时序特性,例如并发、先后等.针对开放环境对构建可信软件系统提出的挑战与已有环境感知技术的不足,本文提出一种基于形式逻辑的环境特性描述与感知方法,其核心是谓词检测技术.具体而言,本文的贡献在于:•提出了一个开放环境特性描述框架,该框架可以便捷地、形式化地描述“真”分布环境的各种特性,包括那些既有技术不能处理的时序特性.引入谓词检测技术以支持高效的环境特性感知机制的实现,有效应对开放环境动态、难控的特点.•开发了一个支持可信应用构建与运行的开放环境特性感知中间件平台MiddlewareInfrastructureforPredicateDetectioninAsynchronousEnvironments(MIPA),通过MIPA平台提供的谓词检测服务,应用可自动感知其关注的环境特性.•通过一个案例分析展示了如何基于所提出的环境特性描述框架与MIPA平台,有效地感知用户任意指定的环境特性.本文第1节介绍环境特性描述框架.第2节介绍MIPA中间件平台的设计.第3节是案例分析.第4节回顾相关工作.第5节总结全文并展望未来的工作.1面向异步环境的特性描述框架本节提出一个基于形式逻辑的开放环境特性描述框架.在描述能力方面,该描述框架支持异步环境下时序特性的描述,有效地弥补了传统环境规约技术在“真”分布开放环境下的不足;在效率方面,该描述框架以谓词作为环境特性规约的基础,较好地保留了传统非形式化环境规约技术的简洁易用性;同时,基于该描述框架的环境特性感知机制具有较高的实际运行效率.我们的描述框架的核心是产生于分布程序调试的谓词检测技术[8−10],并将该技术运用到开放环境特性感知中来.下面,我们首先给出系统模型,然后给出描述框架.在第2节与第3节中,我们将详细讨论如何基于我们的描述框架构建环境感知应用.1.1系统模型为了实现显式化环境与动态化应变,开放环境下有多个环境设施负责环境信息的收集、分发与处理,其间通过异步的消息传递进行通信.我们将环境设施建模成一个松耦合的基于消息传递的分布式系统,其间没有统黄宇等:开放环境特性感知技术867一的全局时钟,并且通信面临不确定的延迟.每个环境设施被抽象成一个进程Pi,1≤i≤n,每个Pi的执行过程可以表示为该进程的状态(state)sij经过操作(action)aij后不断转换的过程,即Trace(Pi)=si0ai0,si1ai1,…,siuaiu.Pi上的操作aij可分为3类:i)本地操作:仅涉及一个进程的本地信息而不与外界交互的操作.ii)消息发送操作send(i,j,ω):进程Pi向进程Pj发送消息ω.iii)消息接收操作receive(i,j,ω):进程Pj从进程Pi接收消息ω.Happen-Before关系:异步环境特性描述的核心是不同状态/操作间的因果联系(causality)所蕴含的happen-before关系(记为→)[6],其定义为(为了表述方便,下面的讨论中仅考虑进程的状态sik,省略其操作aik):•对给定的i和任意kl,sik→sil;•消息发送操作send(i,j,ω)前后,进程Pi和Pj的状态分别为sit和sjr,则sit→sjr;•对于任意两个状态s1和s3,如果存在状态s2满足:s1→s2且s2→s3,则s1→s3.我们可以通过逻辑向量时钟来记录并方便地判断系统中状态间的happen-before关系[10].1.1.1一致全局状态系统的一次执行(记为RUN)由每个进程的Trace(Pi),1≤i≤n组成,每个进程的本地状态si组成的向量记为一个全局状态(globalstate),g=[s1,s2,…,sn],我们定义一个全局状态是一致的(consistentglobalstate,简称CGS),当且仅当:任取si与sj属于g,si→sj与sj→si均不成立.全局状态的一致性的直观物理含义是:一个CGS是在系统执行过程中可能出现的全局状态;相反,一个不一致的全局状态则是在实际系统执行过程中不可能出现的.1.1.2全局序列基于CGS的定义,一个系统的执行则可以看成是系统从一个CGS推进到下一个CGS,系统执行过程中先后经历的若干CGS形成的序列,我们定义为一个全局序列(globalsequence,简称GSE).一个GSE中的CGS之间满足偏序关系≺:对于全局状态g=(s1,s2,…,sn),12(,,...,)ngsss′′′′=,我们定义g≺g′当且仅当g≠g′,且对任意1≤i≤n,si=is′或者si→is′.对于异步系统的一次执行,往往由于缺乏充分的消息传递,系统中部分状态之间并不能建立happen-before关系.对于没有建立happen-before关系的两个状态,它们的两种相对执行顺序都是可能的.系统的一次执行RUN中所有的CGS,在≺关系下形成一个格[9,10],其几何表示如图1所示.我们观察到的系统执行并不是一条确定的GSE,而是一组可能的GSE组成的集合.1.2环境特性谓词环境特性描述框架的核心是环境特性谓词的定义,环境特性谓词的结构与上述系统模型是密切对应的.具体而言,我们可以采用自顶向下的方式来看待一个异步系统的构成