基于活性顺序图的形式化验证方法及工具研究

近年来,形式化验证方法在软件开发过程的作用越来越大;如何充分利用形式化验证方法提高软件系统的可靠性已成为软件开发者及使用者主要关注的问题;总结了近年来基于活性顺序图的形式化验证方法的研究进展,首先介绍活性顺序图的语言及其表达能力与复杂性,然后深入分析现有的基于活性顺序图的形式化验证的关键技术及其典型应用,最后实现一种基于活性顺序图的运行时验证工具,实验证明使用本验证工具进行形式化验证的可行性。     

一种基于场景的嵌入式软件设计方法

UML顺序图是一种常用的在软件开发早期阶段用来描述系统基于场景的需求规约的一种可视化建模语言。通过在UML顺序图中加入带时间区间标志的时间约束,得到时间顺序图模板TSDT（Timed Sequence Diagram Template）,用来建立嵌入式软件基于场景的需求规约模型。对消息传递自动机进行实时扩展,得到时间消息传递自动机TMPA（Timed Message Passing Automata）,TMPA以自动机的形式刻画了所建立的需求规约模型,为在需求阶段验证所建立的模型是否满足用户需求奠定了基础。     

SDT：一个面向场景规约的运行时测试工具

利用设计模型信息，提高测试自动化程度是测试领域的重要课题。UML顺序图是广泛使用的场景规约语言。本文研究了面向场案规约的运行时测试方法，并应用该方法实现了一个基于UML顺序图场景规约的测试工具SDT；它从Ration Rose的规约文件中提取顺序图信息，生成表示预期行为属性的事件有向无环图，对代码进行插装，并利用随机测试用例执行代码，最后将反向工程得到的运行时轨迹与有向无环图进行比较，对实现和设计的一致性进行自动化验证。     

从活性顺序图到时态逻辑的转化方法

为了将活性顺序图用于模型检测,方便描述系统的场景需求,提出了一种将活性顺序图转换成时态逻辑的转化方法.分析活性顺序图语言并且定义一种基于路径的语义,用活性顺序图表述系统的场景需求.根据提出的语义,给出了一个将场景需求显式转化为时态逻辑的一般方法,针对并发消息较多的系统扩展和优化此方法,以得到更简短的时态逻辑公式.通过实例说明活性顺序图到线性时态逻辑的转化过程.     

位置不确定移动对象的连续概率反Skyline查询

为了确保包括非功能属性在内的服务规约与服务实际运行行为之间的一致性,提出一种Web服务运行时行为验证方法。首先对UML 2.0序列图进行扩展,将QoS属性和功能属性的描述统一起来,以精确表达Web服务的需求规约。然后,提出利用确定有限自动机构造出扩展序列图(Extended Sequence Diagrams,ESD)的语义模型的方法。最后,给出验证准则,根据Web服务的交互消息和规约建模的结果来验证Web服务运行时行为与需求规约之间的一致性。基于上述研究,设计开发了Web服务运行时验证工具(Runtime Verification Tool for Web Services,RVT4WS),以支持对Web服务运行时行为的验证。     

基于设计演算的形式化用例分析建模框架

提出一种形式化用例分析建模框架,引入类图、用例顺序图、用例状态图、功能规约函数和系统不变式从多个角度为需求建模.通过定义这些视图的形式化语义,为需求的各个方面定义了准确的形式化描述.利用该框架,可以从方法的交互行为规约和功能规约合成描述方法全部行为的全规约;也可以定义用例模型的性质,并通过设计演算中的证明来分析验证这些性质.作为应用,研究了检查用例模型一致性的规则.给出一个实例说明建模框架的可行性.     

面向基于场景规约的Web服务消息流分析与验证

采用UML顺序图构成基于场景的规约、WS-BPEL作为Web服务的描述语言,提出了一种面向基于场景规约对Web服务消息流进行分析与验证的方法:首先,对WS-BPEL消息流进行分析并将其自动抽象为基于Petri网的模型;同时,为了缩小状态空间、提高验证效率,在不影响消息交互顺序的前提下,对WS-BPEL源码和基于Petri网的模型分别进行化简,即面向基于场景规约将与验证无关的活动和元素删除;最后,通过遍历基于Petri网的模型以验证WS-BPEL消息流与基于场景的规约之间的一致性(消息交互顺序的存在/强制一致性).文中通过一个贯穿整个分析与验证过程的实例加以说明.该方法已经实现成为一个原型工具.     

场景驱动的服务行为调控

提出了一个场景驱动的服务行为调控途径.首先,用UML顺序图模型作为场景规约以描述用户对服务行为的需求,并且基于目标服务的BPEL行为规约,构造表示服务行为的BPEL-Petri网模型(简称BPN模型);其次,基于并发变迁分析BPN模型上表示服务行为的路径,并通过遍历BPN模型获取包含UML顺序图描绘场景的服务行为集合;最后,根据行为分析的结果构建了调控服务,通过在运行时监听、检查并过滤用户与目标服务的消息交互,从目标服务中抽取或过滤顺序图描绘的场景.在此基础上,开发了原型工具BASIS,以支撑场景驱动的服务行为调控途径,并通过实例研究展示了该方法的可行性.     

基于UML顺序图的测试用例生成

为生成覆盖测试需求的测试用例集,提出一种基于UML顺序图自动生成测试用例的方法。通过分析待测系统的功能用例,对其进行顺序图建模。在基于该顺序图生成测试用例的过程中,对顺序图添加规约条件,解析顺序图,得到场景测试树,再遍历该树,得到场景的输入、预期输出、约束条件以及场景环境,这4部分组成了测试用例,同时对如何处理复杂的顺序图及如何满足测试用例充分性等问题进行分析总结,提出有效的解决策略。     

安全苛求软件需求规格中的安全特性验证方法

针对自然语言描述的安全苛求软件需求规格中安全特性不准确、不一致等问题,提出一种基于UMLsec安全特性验证方法。该方法在UML需求模型类图和顺序图的基础上,为核心类的安全特性自定义构造型、标记和约束,完成UMLsec模型构建;之后,使用设计实现的UMLsec支持工具对安全特性进行自动验证。实验结果表明,该方法能准确描述安全苛求软件需求规格的安全特性,同时可以自动验证安全特性是否满足安全需求。     

Provable Protection against Web Application Vulnerabilities Related to Session Data Dependencies

Web applications are widely adopted and their correct functioning is mission critical for many businesses. At the same time, Web applications tend to be error prone and implementation vulnerabilities are readily and commonly exploited by attackers. The design of countermeasures that detect or prevent such vulnerabilities or protect against their exploitation is an important research challenge for the fields of software engineering and security engineering. In this paper, we focus on one specific type of implementation vulnerability, namely, broken dependencies on session data. This vulnerability can lead to a variety of erroneous behavior at runtime and can easily be triggered by a malicious user by applying attack techniques such as forceful browsing. This paper shows how to guarantee the absence of runtime errors due to broken dependencies on session data in Web applications. The proposed solution combines development-time program annotation, static verification, and runtime checking to provably protect against broken data dependencies. We have developed a prototype implementation of our approach, building on the JML annotation language and the existing static verification tool ESC/Java2, and we successfully applied our approach to a representative J2EE-based e-commerce application. We show that the annotation overhead is very small, that the performance of the fully automatic static verification is acceptable, and that the performance overhead of the runtime checking is limited.     

一种基于预测的运行时验证开销控制方法

  针对运行时验证中,监控模块对软件系统运行效率产生影响的问题,提出一种基于预测的控制运行时验证开销的方法。该方法主要是通过建立马尔可夫链（Markov Chain）和隐马尔可夫模型（Hidden Markov Model, HMM）对软件行为进行有限步的预测,并判断被验证的性质约束被违反的风险,依此对软件监控行为进行调整,从而实现将运行时验证所产生的额外开销控制在一定范围内的目标。这种方法能够有效地控制监控开销,但仍然需要进一步的研究。     

运行时验证中的减少监控开销方法研究

运行时验证中的一个重要研究内容就是减少监控开销,以达到运行时开销对系统影响最小化的目标。总结了近年来运行时验证中减少监控开销技术的研究发展,首先介绍了运行时开销控制的研究现状;然后详细介绍了运行时开销减少的具体方法;最后分析了运行时开销控制技术面临的主要挑战,并对该领域未来的研究方向进行了展望。     

基于隔离逻辑的并行程序可靠性验证方法

并行程序验证的复杂性在于执行流程的不确定性以及由此导致的执行规模变大,使得验证的内容和目标之间的关系不明确。为解决该问题,提出一种基于隔离逻辑的并行程序可靠性验证方法。通过变量的执行关系图,描述变量相关的语句及执行关系,将所需验证的程序性质逻辑式转换为变量并行语句序列的逻辑组合式,使得性质表达式与并发程序的语句相关联。根据逻辑组合式确定语句执行序列和前后件逻辑表达式,基于并发隔离逻辑的公理系统对语句执行序列进行验证,并根据验证结果对并发程序进行修改和完善。通过对银行柜台业务办理的功能模块验证结果表明该方法是有效的。     

基于部分调用图的线程敏感Profiling技术

Profiling技术能提供程序实际执行时的相关信息。在动态编译环境中,Profiling的运行时开销导致难以收集较为复杂的运行时信息。该文提出一种基于部分调用图的Profiling技术,在收集多线程程序中线程相关的各种执行信息时,能有效减少运行时开销。在开放源码的虚拟机上实现了该Profiling技术。实验表明,其运行时开销只有原来的2%~4%。     

Efficient monitoring of parametric context-free patterns

Recent developments in runtime verification and monitoring show that parametric regular and temporal logic specifications can be efficiently monitored against large programs. However, these logics reduce to ordinary finite automata, limiting their expressivity. For example, neither can specify structured properties that refer to the call stack of the program. While context-free grammars (CFGs) are expressive and well-understood, existing techniques for monitoring CFGs generate large runtime overhead in real-life applications. This paper demonstrates that monitoring parametric CFGs is practical (with overhead on the order of 12% or lower in most cases). We present a monitor synthesis algorithm for CFGs based on an LR(1) parsing algorithm, modified to account for good prefix matching. In addition, a logic-independent mechanism is introduced to support matching against the suffixes of execution traces.     

Optimized temporal monitors for SystemC

SystemC is a modeling language built as an extension of C++. Its growing popularity and the increasing complexity of designs have motivated research efforts aimed at the verification of SystemC models using assertion-based verification (ABV), where the designer asserts properties that capture the design intent in a formal language such as PSL or SVA. The model then can be verified against the properties using runtime or formal verification techniques. In this paper we focus on automated generation of runtime monitors from temporal properties. Our focus is on minimizing runtime overhead, rather than monitor size or monitor-generation time. We identify four issues in monitor generation: state minimization, alphabet representation, alphabet minimization, and monitor encoding. We conduct extensive experimentation and identify a combination of settings that offers the best performance in terms of runtime overhead.     

一种利用PHP防御SQL注入攻击的方法

PHP在Web应用程序开发中的广泛运用使得PHP Web应用程序成为众多恶意攻击者的攻击对象。基于此,通过对PHP解释器和运行时库的修改,使PHP Web应用程序无需修改便能够防御SQL注入攻击。与传统的利用动态着色方法防御漏洞不同,使用基于可信任输入的着色机制,采用SQL方言感知的检查方法,可解决传统方法防御Web漏洞的诸多问题,提高防御的准确率,消除误报。实验结果表明,该方法准确有效,对应用程序执行造成的负载较低。     

参数化运行时监控研究

随着计算机软件广泛应用于各类安全关键系统以及软件日趋复杂,软件可靠性变得越来越重要。作为一种广泛使用于各种平台的软件解决方案,运行时监控是提高软件可靠性的最灵活的解决方案之一。但随着运行时监控技术以及软件技术的发展,人们希望通过运行时监控技术来验证系统的动态属性,从而提出参数化性质的运行时监控技术。由于其在面向对象系统中的适用性,参数化性质的运行时监控已经受到了越来越多的关注。综述了参数化运行时监控的研究进展,提出了参数化运行时监控的问题定义,介绍了这一领域的主要研究内容:参数化运行时监控方法、减少参数化监控开销的技术、多属性规约的参数化运行时监控。     

基于插桩和布尔逻辑的运行时程序验证框架

针对软件测试和静态程序验证中存在的连续性程序执行验证和推理问题,提出一个基于程序插桩和布尔逻辑的运行时程序验证框架——RPA。定义一种用于描述运行时程序性质和规范的动态逻辑语言RPAL,实现自动化插桩以收集运行时程序状态信息,设计一个支持高效验证的句子调度算法。实验结果表明,结合合适的谓词扩展,RPA可以有效地验证和分析软件逻辑,发现潜在的软件错误。