一种包含异常传播的类间数据依赖分析方法

类间数据依赖分析是类间数据流测试的基础。本文通过分析类簇级测试中的异常传播对程序数据依赖的影响,提出一种包括异常结构在内的类间C++程序数据依赖分析方法,根据类间关系增量式地构造类间数据依赖图,并给出类间数据依赖图的构造算法。最后,在程序切片中应用了该数据依赖分析方法。结果证明,该方法通过分析异常传播对数据依赖的影响能够带来切片精度的提高。     

一种基于异常传播分析的数据流分析方法

异常处理是一种用来检测异常并对其进行处理的技术.异常传播改变了程序原来的执行路线,从而改变了程序中的数据流.在进行数据流分析时,如果不考虑异常传播对其造成的影响,则得到的信息将是不准确的.在分析C++异常传播机制和异常传播对数据流分析影响的基础上,提出一种包含异常传播信息的函数间控制流图的构建方法.该控制流图可以清晰地表示出异常的隐式控制流和异常的传播路径;然后提出了基于异常传播分析的数据流分析方法,并给出相应的算法.该方法既克服了因忽略异常传播对数据流影响而造成分析结果不准确的不足,又有助于实现异常传播数据流分析的自动处理;最后用一个实例验证了该方法的可用性.该方法可以为结构测试、回归测试、程序切片等软件工程任务提供相关信息.     

面向对象程序的异常传播分析方法

现有异常传播分析方法大多局限于单个类内部,不能满足现实软件开发的需求。为此,提出一种面向对象程序的异常传播分析方法,在类控制流图的基础上构建面向对象异常传播分析(OEPAG)图,通过得到异常在类间的传播路径并确定类间关系,从而对控制流和数据流进行有效分析。应用结果表明,将OEPAG图用于含异常处理结构的程序切片时的结果比传统程序切片结果更准确。     

控制流图上支配关系计算方法的分析与实现

支配关系在数据流分析和静态单赋值等程序分析和优化中应用很广泛.采用位向量表示支配结点集合,描述了采用迭代法计算控制流图上支配结点集合的算法,在支配结点集合的基础上讨论了对直接支配结点、支配边界结点的计算方法,并在NPB和SPEC2000测试集上进行了测试.测试结果表明:控制流图的构建占用了过程内支配关系计算的几乎一半时间;对于不包含goto语句的结构化程序,迭代算法一般只需迭代2次.     

一种结构测试数据自动生成的框架

针对结构测试中控制流和数据流覆盖测试数据的生成都可以归结为面向路径的测试数据生成的问题,提出了一个通用的基于控制流和数据流的结构测试数据自动生成的框架。该框架根据控制流和数据流测试中所采用的覆盖标准优化选取测试路径,并以改进后的迭代松弛法为核心,对所选取的路径生成测试数据。以基于路径覆盖、分支覆盖和数据流覆盖测试数据自动生成这3种算法为核心,开发了一个测试数据自动生成的框架原型。实验结果表明该框架是可行的。     

一种工作流的控制流距离度量方法

为准确计算工作流中的控制流距离,提出一种工作流的控制流距离度量方法.介绍从工作流中分离控制节点生成控制流图的过程.在控制节点间距离基础上,建立通过控制流图进行工作流控制流距离度量的模型,并从理论上证明距离度量模型满足自反、对称及三角不等式性质.案例分析结果表明,该方法能更真实、准确地反映工作流间的距离.     

基于控制流切片的代码安全缺陷检测方法

为轻松获得程序的可能执行路径,进而实现程序变量的状态跟踪,提出了一种C/C++源代码控制流提取算法,通过该模型获取控制流切片,产生局部控制流图,将数据流异常检测与安全子集检测相结合,弥补了单独使用安全子集方法无法跟踪数据流的不足,增强代码安全隐患的挖掘能力.利用控制流图化简,排除部分不可达控制流信息,提高跟踪效率.通过对3个Linux内核源文件的检测,验证了该方法不仅可以检测出违反安全子集的代码安全隐患,同时对代码数据流异常检测提供支持,准确率达94.9％.     

基于动态数据流分析的虚拟机保护破解技术

由于虚拟机采用虚拟化技术和代码混淆技术,采用传统的逆向分析方法还原被虚拟机保护的算法时存在较大困难。为此,提出一种基于动态数据流分析的虚拟机保护破解方法。以动态二进制插桩平台Pin作为支撑,跟踪记录被虚拟机保护的算法在动态执行过程中的数据流信息,对记录的数据流信息进行整理分析,获取虚拟机指令的解释执行轨迹,还原程序的控制流图,根据轨迹信息对数据生成过程进行分层次、分阶段还原,并由分析人员结合控制流图和数据生成过程进行算法重构。实验结果证明,该方法能够正确还原程序的控制流和数据生成过程,辅助分析人员完成被保护算法的重构。     

针对共享内存SPMD程序的通信流依赖分析方法

传统数据流依赖分析方法在处理共享内存单指令多数据(SPMD)程序时,不能识别共享数据访问语句所属的处理节点,也不能消除执行顺序不定的控制流对共享数据流依赖造成的影响,从而在分析共享数据依赖时产生精度较低的结果。根据共享内存SPMD程序的共享数据别名特性,提出了一种可扩展的共享数据通信流依赖分析方法,并将其应用于一个编译后端分析器原型中。实验表明,该方法较传统分析方法可发现更多精确的共享数据通信流依赖。     

综合控制流与数据流分析的主机异常检测新方法

传统主机异常检测方法只针对控制流信息或数据流信息进行分析,在两个研究方向上产生了很大的分化,不能很好地吸取彼此的成果。基于这种情况,提出一种新的综合控制流与数据流分析的新方法。该方法首先使用系统调用定长序列构建模式库,再用关联规则挖掘方法挖掘同一模式或不同模式下属性间的关联规则,构建用于检测评估的两种规则集。实验结果表明,基于控制流上下文的数据流分析新方法能够发现先前数据流分析所不能发现的更精准更有用的规则从而检测出更多的异常行为。     

基于面向对象程序代码的类测试技术

面向对象软件的基本测试单元是类，文中提出了用一种基于代码的测试技术－数据流测试来全面地测试类。对类测试分为３级：单个成员函数的测试；公有成员函数的测试；公有成员函数接口的测试。     

程序控制流图自动生成的算法

运用程序控制流图,可以方便地度量程序的逻辑复杂度,确定软件测试中控制结构独立路径的基本集合。文章提出了根据程序设计的伪码,自动生成程序控制流图的数据结构和详细的算法,为进行控制优化、软件基本路径测试以及程序控制相关性分析提供了良好的基础。     

并行性挖掘的图文法方法

并行性分析技术一般通过对程序的控制与数据流图或相关依赖图的分析来实现,因而需要从程序中抽取出相应依赖图的算法的支持.本文基于上下文相关图文法RGG形式框架,定义了一种任务级的并行编程图语言GPPL来直接描述顺序或并行程序的控制与数据流图,而且设计了相应的并行性分析算法以挖掘GPPL图程序的并行性特征.GPPL图语言可视为并行程序设计与程序代码生成之间的协同语言,从而使并行性挖掘避免了从程序中抽取出相应依赖图的过程.与已有的描述顺序或并行程序的图语言及其分析算法相比,GPPL图程序形式更为简洁和直观,易于设计,描述能力也更强;基于GPPL图的并行性分析算法的分析能力更强,而且具有可扩展性.     

函数库中过程间数据流预分析

过程间数据流分析在软件优化,软件维护,软件测试中均有大量的应用。在编写使用可重用组件的软件时,对整个程序进行数据流分析的方法效率低下甚至由于没有库的源代码而不能直接分析。本文是在已有的组件库上构建新组件时进行数据流分析,通过计算新建库的概要信息,并使用这些概要信息分析新的组件,这样使用库中预先计算的概要函数能够在较小的分析成本下构建可扩展的大的库组件。     

利用控制依赖关系算法分析BPEL4 WS

IBM、Microsoft和BEA联合提出的服务组合描述语言BPEL4WS是现有的主要工业标准。本文在分析BPEL4WS控制流程的基础上提出了控制依赖关系概念,并设计了一个复杂度为0（N^2）的控制依赖关系图生成算法。最后,基于控制依赖关系图,讨论了如何进行BPEL4WS的控制冲突检查和执行优化。     

Abstract interpretation of logic programs using magic transformations

In dataflow analysis of logic programs, information must be propagated according to the control strategy of the language under consideration. However, for languages with top-down control flow, naive top-down dataflow analyses may have problems guaranteeing completeness and/or termination. What is required in the dataflow analysis is a bottom-up fixpoint computation, guided by the (possibly top-down) control strategy of the language. This paper describes the application of the magic templates algorithm, originally devised as a technique for efficient bottom-up computation of logic programs, to dataflow analysis of logic programs. It turns out that a direct application of the magic templates algorithm can result in an undesirable loss in precision, because connections between “calling patterns” and the corresponding “success patterns” may be lost. We show how the original magic templates algorithm can be modified to avoid this problem, and prove that the resulting analysis algorithm is at least as precise as any other abstract interpretation that uses the same abstract domain and abstract operations.     

一种使用控制块消除流图中回边的算法

引入控制块分解流图来构建控制流树,确定流图中的回边及循环路径中包含的节点,通过消去原流图中的回边,构建无环流图,简化流图的数据流分析。控制块将流图的控制关系转移到新构建的控制流树的内部控制节点上。使用控制块分解算法将流图转换到控制流树过程中,所创建节点数目不超过n,使用控制流树求解路径表达式和确定回边的时间复杂度不超过O(nlogn)。     

Parallel processing system -Harray-

The parallel processing system -Harray- for scientific computations is introduced. The special features of the -Harray- system described are (1) the Controlled Dataflow (CD flow) mechanism, (2) the preceding activation scheme with graph unfolding, and (3) the visual environment for dataflow program development.The CD flow mechanism, controlling the sequence of execution in two levels—dataflow execution in each processor and control flow execution between processors—is adapted in the -Harray- system. Though dataflow computers are expected to extract parallelism fully from a program, they have many problems, such as the difficulty of controlling the sequence of execution. To solve these problems, the CD flow mechanism is adopted.The preceding activation scheme makes it possible to bypass control dependencies in a program, such as IF-GOTO statements which decrease the parallelism in a program. The flow graph of a program is unfolded to decrease the control dependency and to increase the parallelism.The visual environment helps programmers in the writing and debugging of a dataflow program. The environment consists of a graphical editor of a dataflow graph, and a debugger.These special features of the -Harray- system and its execution mechanism are described.     

基于GCC关键变量数据流分析算法的程序切片技术

随着程序的规模的扩大和复杂度的提高,通过直接分析源码进行程序切片,变得十分困难。在现有的利用编译优化技术来优化程序切片的方法中,存在无法有效利用程序的编译时信息和编译器的优化技术,以及对语言的支持不完善的问题。为此,分析了GCC编译器在编译时的中间表示,首次提出了基于GCC关键变量数据流分析算法的程序切片技术,以程序的GIMPLE中间表示为基础,以程序基本块为单位,通过迭代求解数据流方程,分析程序基本块内和不同基本块间的关键变量数据流信息。该程序切片技术可以获取源程序中仅与预设目标函数相关的关键变量和关键语句,缩减程序规模。最后通过实验,证明了该算法的可行性。