一种获得有限自动机状态间关系的高效算法

正则表达式匹配在网络安全应用中发挥着重要的作用.确定有限自动机(deterministic finite automaton,DFA)具有高速稳健的性能,因而更适合于在骨干网络环境下执行正则表达式匹配.然而,DFA存在状态膨胀的问题.很多研究工作基于状态关系来解决DFA的状态膨胀问题.然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法.提出了一个通过有限自动机(finite automaton,FA)的活跃状态集来准确计算状态关系的算法,并给出了一个高效的获取所有活跃状态集的方法.实验结果证明,该方法不仅能准确地得到状态关系,而且其空间占用和时间消耗仅是已有方法的1?256和15%左右.     

基于反馈机制的网格动态授权新模型

网格现有的授权系统存在静态性问题,表现为没有提供机制来反馈用户对授予的权限的使用情况.当一个本来可信的用户或服务变成不可信时,授权系统不能及时发现,对其权限进行调整可能导致恶意用户对网格系统的破坏.因此,在授权系统中建立反馈机制,根据用户的行为动态地调整用户角色,对于网格系统的安全具有重大意义.文中分析了网格中现有的授权系统及信任模型的特点,指出它们存在的不足.在此基础上提出一种基于反馈机制的动态授权新模型,很好地解决了现有授权系统的静态性的缺点.该模型是对CAS授权系统的改进,增加了反馈机制和信任度计算机制.其中,信任度计算机制中提出的基于行为的分层信任新模型较以往的信任模型相比,使用服务权值来区分重要服务和普通服务,从而保护了网格中的重要服务并且能有效地抑制恶意节点的行为;文中提出了一种新的更加精确地计算域间推荐信任度的方法,从而解决了不诚实反馈的问题.反馈机制则利用基于行为分层信任模型给出的用户信任度的变化,实现了根据用户的行为动态调整他的角色.文中还设计了三组模型实验,分别验证新模型的特点、对网格中恶意实体行为的抑制情况,从不同的角度对模型进行了实验,对基于行为的分层信任模型对行为的敏感性、收敛性、有效性及合理性加以了证明.     

基于多值决策图的动态故障树分析方法

针对具有动态故障模式的复杂系统,动态故障树分析一直是很重要的可靠性分析技术。为了提升可靠性分析效率,已有研究提出了各种模块化方法,但是对于实际动态故障树模型中由于事件关联导致的大型动态子树,这些模块化方法的状态空间爆炸问题仍然很突出。因此介绍了一种基于多值决策图(Multiple-valued Decision Diagrams,MDD)来分析动态故障树的方法,通过多值变量编码动态门,利用单一系统MDD模型刻画各种动态和静态可靠性行为,有效地缓解了状态爆炸问题。通过一个具体的实例说明了多值决策图方法的应用和优势。     

基于聚态资源的P2P搜索技术模型

搜索技术是目前互联网应用的核心,为了提高搜索的效率和流量控制,从P2P技术在实际应用过程中所产生的问题出发,阐述了如今动态P2P资源网络自身一些特征和结构,分析了一些聚态特征的网络模型及其性能,比较了一些在复杂网络中提出的搜索模型.提出了一种基于分布式哈希表搜索的多局域聚态系统模型(multi-resouce-world,MRW),最后用数理分析对其搜索性能进行了证明,表明无论在静态网络还是在动态网络环境中,搜索性能都能有良好的表现,并且在一定程度上解决了网络拥塞问题.     

高精度汽车安全气囊最佳点火时刻预测算法

作为一种汽车的标准配备,安全气囊得到广泛使用.但是,由于安全气囊的误爆或漏爆所造成的事故却时有发生,造成不必要的人员伤亡和财产损失.为了确定汽车安全气囊的最佳点火时刻,论文将反向传播(BP)神经网络的泛化学习能力与自回归滑动平均(ARMA)模型的精确性相结合,提出了基于BP神经网络与ARMA模型的预测算法.论文给出了主要的设计及其仿真,从仿真结果看,所设计的控制算法能够很好的实现最佳点火时刻的精确预测,有助于提高汽车安全气囊的安全性能.     

嵌入式实时系统的软件需求检测

以需求描述模型HRFSM(hierarchical finite state machines based on rules)为基础,提出了一个嵌入式实时系统软件的动态执行模型(dynamic execution model,简称DEM)和基于该模型的检测方法.由于DEM能将控制流、数据流和时间有效地集成为一体,故提出的检测方法能检测嵌入式实时系统的软件需求的一致性和完全性.该检测方法由3种侧重点不同的检测形式组成,并能在检测过程中提供一些重要的检测信息.分析员可以利用基于该检测方法的工具灵活地对嵌入式实时系统的软件需求进行检测,以提高分析和检测软件需求的效率.     

一种快速精确的人脸三维形状重构新方法

针对传统 SFS(Shap from Shading)的不足 ,提出了一种新的基于 BP神经网络的明暗恢复形状的方法 ,该方法是基于兰伯特 (L am bertian)反射模型的改进算法 ,利用了 BP神经网络强的非线性映射能力 ,将 L ambertian表面反射模型与光滑表面模型相结合 ,然后再利用一些已知条件 ,构成 SFS问题的正则化模型 ;变换不同的照明条件 ,将模型平移或旋转获得多幅图象 ,以增加约束条件 ;计算出误差补偿参数去修正邻域内的三维误差 .由于考虑了邻域的平均值 ,使算法的稳定性和精确性都得到了加强 .实例表明 ,该算法较传统的算法更快和更精确     

一种基于安全状态跟踪检查的漏洞静态检测方法

现有的采用基于源代码分析的漏洞静态检测方法中存在的主要问题是误报率和漏报率较高.主要原因之一是缺乏对数据合法性检查与非可信数据源等程序安全相关元素的精确有效的识别分析.文中提出了一种基于数据安全状态跟踪和检查的安全漏洞静态检测方法.该方法对漏洞状态机模型的状态空间进行了扩展,使用对应多个安全相关属性的向量标识变量安全状态,细化了状态转换的粒度以提供更为精确的程序安全行为识别;在漏洞状态机中引入了对合法性检查的识别,有效降低了误报的发生;建立了系统化的非可信数据鉴别方法,可防止由于 遗漏非可信数据源而产生的漏报.基于此方法的原型系统的检测实验表明:文中方法能够有效检测出软件系统中存在的缓冲区溢出等安全漏洞,误报率明显降低,并能避免现有主流静态检测方法中存在的一些严重漏报.     

建模与仿真的动态V&V技术综述

校核与验证(V&V)技术包括非正规、静态、动态和正规四类技术,是保证建模与仿真(M&S)的可信度的重要手段.动态V&V技术是其中应用范围较广、数学和逻辑上比较正规的技术.它要求模型转化为应用并被执行,根据模型的执行行为来评价模型的精确性.首先简要介绍了M&S的VV&A和校核与验证技术的分类情况,然后论述了动态校核与验证技术并分析了各自的特点,最后介绍了在建模与仿真过程中动态V&V技术的适用范围.对用于校核与验证的动态测试技术和统计技术作了重点介绍.     

大规模分布式环境下动态信任模型研究

随着网格计算、普适计算、P2P计算、Ad Hoc等大规模的分布式应用系统的深入研究,系统表现为由多个软件服务组成的动态协作模型.在这种动态和不确定的环境下,PKI(pubic key infrastructure)中基于CA(certificate authority)的静态信任机制不能适应这种需求,动态信任模型是新的研究热点.分析了动态信任关系的相关概念、主要问题和研究方法;选取新的、典型的动态信任模型及其使用的数学方法进行评述,并进行了各种算法的比较性总结;分析了目前研究中的问题,并展望了其未来的发展方向.研究表明,动态性是信任关系量化与预测的最大挑战.今后的工作重点是对信任动态性的本质属性作进一步的理论研究,为实际应用提供坚实的理论基础.     

基于系统调用属性的程序行为监控

程序的行为轨迹常采用基于系统调用的程序行为自动机来表示.针对传统的程序行为自动机中控制流和数据流描述的程序行为轨迹准确性较低、获取系统调用上下文时间开销大、无法监控程序运行时相邻系统调用间的程序执行轨迹等问题,提出了基于系统调用属性的程序行为自动机.引入了多个系统调用属性,综合系统调用各属性的偏离程度,对系统调用序列描述的程序行为轨迹进行更准确地监控;提出了基于上下文的系统调用参数策略,检测针对系统调用控制流及数据流的行为轨迹偏离;提出了系统调用时间间距属性,使得通过系统调用及其参数无法监控的相邻系统调用间的程序行为轨迹在一定程度上得到了监控.实验表明基于系统调用属性的程序行为自动机能够更准确地刻画程序行为轨迹,较传统模型有更强的行为偏离检测能力.     

Efficient exception handling in Java bytecode-to-C ahead-of-time compiler for embedded systems

One of the most promising approaches to Java acceleration in embedded systems is a bytecode-to-C ahead-of-time compiler (AOTC). It improves the performance of a Java virtual machine (JVM) by translating bytecode into C code, which is then compiled into machine code via an existing C compiler. One important design issue in AOTC is efficient exception handling. Since the excepting point and the exception handler may locate in different methods on a call stack, control transfer between them should be streamlined, while an exception would be an “exceptional” event, so it should not slow down normal execution paths. Previous AOTCs often employed a technique called stack cutting based on a setjmp()/longjmp() pair, which we found is involved with too much performance overheads. Also, when the AOTC and the interpreter are employed concurrently (e.g., some methods are AOTCed while other methods are interpreted), the performance of normal execution paths is affected more seriously. This paper proposes a simpler solution based on an exception check after each method call, merged with garbage collection check for reducing its overhead. Our evaluation results on SPECjvm98 on Sun's CVM indicate that our technique can improve the performance of stack cutting by more than 25%. A similar performance benefit can be noted on a hybrid execution environment of both the AOTC and the interpreter.     

一种基于模型检测的二进制程序脆弱性分析框架

针对二进制程序脆弱性分析的实际需求,提出了一种基于模型检测的二进制程序脆弱性分析框架。首先定义了二进制程序的抽象模型,描述了基于有限状态自动机的软件脆弱性形式化表示和基于事件系统的软件安全属性表示方法。在此基础上,提出了基于模型检测的脆弱性分析过程和算法。根据该分析框架,设计并实现了二进制程序脆弱性分析工具原型。通过脆弱性分析实验,详细说明了该框架的工作原理,验证了该分析方法的有效性。     

程序时序属性的自动测试

测试预言是一种用来检测被测系统的测试执行是否正确的方法。文中，作者设计并实现了一种根据程序的线性时序逻辑(LTL)的性质产生测试预言的方法。首先，作者将一线性时序逻辑公式转换为一个有限状态自动机，然后，管理源代码，以便抽取与线性时序逻辑性质有关的状态序列。最后，用谊信息来模拟状态自动机，并决定程序执行是否满足线性时序逻辑的性质。     

汉字双向有穷自动机的研究

汉字的计算机输入是中文信息处理的关键问题之一,而汉字计算机输入的数学模型对汉字的计算机输入的研究有重要的意义。本文从自动机理论的角度对汉字输入的数学模型进行了研究,把控制操作引入了输入模型,并给出确定汉字双向有穷自动机和不确定汉字双向有穷自动机的模型。新的模型较之以前的数学模型,能刻画出汉字输入的控制操作,表达能力进一步增强,是对以前汉字键盘输入数学模型的推广。     

Program Graphs and Execution Behavior

This paper describes a technique for predicting the execution behavior of a source program or a software design specification. As a by-product of syntactic analysis, a program graph is constructed which can subsequently be treated as the graph of a finite automaton. The expression for execution behavior is the regular expression of the graph. Several simplification techniques for these expressions are discussed and exemplified. In particular, the substitution of known values for program segments followed by constant folding cannot be done indiscriminately; the allowable situations are characterized. Applications include the prediction of execution time for a program or a software design, other forms of language analysis, and program restructuring.     

使用事件自动机规约的C语言有界模型检测

提出使用事件自动机对 C 程序的安全属性进行规约,并给出了基于有界模型检测的形式化验证方法。事件自动机可以规约程序中基于事件的安全属性,且可以描述无限状态的安全属性。事件自动机将属性规约与C程序本身隔离,不会改变程序的结构。在事件自动机的基础上,提出了自动机可达树的概念。结合自动机可达树和有界模型检测技术,给出将事件自动机和C程序转化为可满足性模理论SMT(satisfiability modulo theory)模型的算法。最后,使用SMT求解器对生成的SMT模型求解,并根据求解结果给出反例路径分析算法。实例分析和实验结果表明,该方法可以有效验证软件系统中针对事件的属性规约。     

Security policies enforcement using finite and pushdown edit automata

Edit automata have been introduced by J.Ligatti et al. as a model for security enforcement mechanisms which work at run time. In a distributed interacting system, they play a role of a monitor that runs in parallel with a target program and transforms its execution sequence into a sequence that obeys the security property. In this paper, we characterize security properties which are enforceable by finite edit automata (i.e. edit automata with a finite set of states) and deterministic context-free edit automata (i.e. finite edit automata extended with a stack). We prove that the properties enforceable by finite edit automata are a sub-class of regular sets. Moreover, given a regular set $P$ , one can decide in time $O(n^2)$ , whether $P$ is enforceable by a finite edit automaton (where $n$ is the number of states of the finite automaton recognizing $P$ ) and we give an algorithm to synthesize the controller. Moreover, we prove that safety policies are always enforced by a deterministic context-free edit automaton. We also prove that it is possible to check if a policy is a safety policy in $O(n^4)$ . Finally, we give a topological condition on the deterministic automaton expressing a regular policy enforceable by a deterministic context-free edit automaton.     

A three-dimensional shape optimization system—shop3D

A modular approach for shape optimization of three-dimensional solid structures is described. A major consideration in the development of this capability is the desire to use a commercially available finite element program, such as NASTRAN, for analysis. Since NASTRAN cannot be called as a subroutine, a system architecture was developed of independently executable modules in which sequential execution is controlled by job control language. Also, shape sensitivities are not commonly available in commercial programs. A hybrid approach which is based on the material derivative concept is developed to obtain shape sensitivities by post processing finite element results stored on files. A quick generation of a good optimization model combined with an efficient optimization system will result in a drastic design time saving. In this paper, different modeling approaches for shape optimization are discussed. Emphasis will be placed upon a special modeling technique which overlays the design model onto an already existing finite element model. Several automotive related examples are used to evaluate the program's effectiveness.     

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.