Dynamic slicing of object-oriented programs

Program slice has many applications such as program debugging, testing, maintenance, and complexity measurement. A static slice consists of all statements in programP that may effect the value of variablev at some pointp, and a dynamic slice consists only of statements that influence the value of variable occurrence for specific program inputs. In this paper, we concern the problem of dynamic slicing of object-oriented programs which, to our knowledge, has not been addressed in the literatures. To solve this problem, we present the dynamic object-oriented dependence graph (DODG) which is an arc-classified digraph to explicitly represent various dynamic dependence between statement instances for a particular execution of an object-oriented program. Based on the DODG, we present a two-phase backward algorithm for computing a dynamic slice of an object-oriented program.     

并发程序内部表示及静态切片算法的改进

通过分析Krinke切片算法对程序循环体内嵌套一个或多个线程结构会产生切片不精确现象,得出Krinke算法所基于的程序依赖图对线程间数据的依赖关系定义得过于粗糙,且对并发程序执行行为的合法性约束不够严格的结果.据此,提出一种新的并发程序依赖图,引入跨线程边界循环-承载数据依赖关系,并在此数据结构上改进了切片算法;引入区域化执行证据概念,进一步约束程序执行行为的合法性,并给出了添加跨线程边界循环-承载数据依赖关系的算法及新的并发程序切片算法的伪代码.实例分析与算法性能测试表明,改进的切片算法克服了Krinke算法的不精确现象,降低了时间开销,改善了算法的可伸缩性.     

Dependence analysis for C programs with combinability of dataflow facts under consideration

To avoid the precision loss caused by combining dataflow facts impossible to occur in the same execution path in dependence analysis for C programs, this paper first proposes a flow-sensitive and context-insensitive points-to analysis algorithm and then presents a new dependence analysis approach based on it. The approach makes more sufficient consideration on the executable path problem and can avoid invalid combination between points-to relations and between points-to relations and reaching definitions. The results of which are therefore more precise than those of the ordinary dependence analysis approaches. Biography: QIAN Ju (1981–), male, Ph.D., research direction: program analysis and software testing.     

A generic design model for evolutionary algorithms

A generic design model for evolutionary algorithms is proposed in this paper. The model, which was described by UML in details, focuses on the key concepts and mechanisms in evolutionary algorithms. The model not only achieves separation of concerns and encapsulation of implementations by classification and abstraction of those concepts, it also has a flexible architecture due to the application of design patterns. As a result, the model is reusable, extendible, easy to understand, easy to use, and easy to test. A large number of experiments applying the model to solve many different problems adequately illustrate the generality and effectivity of the model. Foundation item: Supported by the National Natural Science Foundatron of China (70071042, 60073043, 60133010) Biography: He Feng (1974-), male, Ph. D candidate, research direction evolutionary computation, software engineering.     

基于构件的若干图算法开发和生成

软件构件技术可显著提高程序的可靠性和开发效率,极大减少开发成本.泛型程序设计有助于降低编程的复杂度,为重用构件开发提供有效支持.介绍了生成式程序设计思想及泛型程序设计技术,分析了图算法领域的关键特征及领域共性问题,并对广度优先搜索、单源最短路径、所有顶点对最短路径等一类问题进行抽象,设计出相应的泛型图算法构件,进一步借助PAR方法中的泛型机制进行描述,并在PAR平台程序生成系统上进行构件组装生成具体的算法程序.     

STL文件毗邻关系的建立与切片算法研究

通过对ＳＴＬ文件结构的分析,引入无向图数据结构,建立了三角形网格之间的毗邻关系,以顺利进行三角形网格的查寻,实现分层切片,对分层切片算法进行了研究,讨论了切片过程中可能出现的问题,提出了相应的解决办法,最后建立了双向链表来表示切片后的ＣＡＤ模型截面轮廓。     

Complexity measure based on program slicing and its validation

The popular single-factor complexity measure cannot comprehensively reflect program complexity and the existing hybrid complexity measure cannot express the interactive behaviors of programs. To treat these problems, in this paper, we propose a complexity measure based on program slicing（CMBPS）. CMPBS not only can evaluate factors which affect program complexity such as the length of the program, control flow, data flow and data types of output variables, but also can give expression of the interactive relation between programs. And we also prove that CMBPS satisfies all of Weyuker properties. Compared with the popular complexity measures, CMBPS is a well-structured complexity measure.     

An Improved Genetic Algorithm for Problem of Genome Rearrangement

In view of the fact that the problem of sorting unsigned permutation by reversal is NP-hard, while the problem of sorting signed permutation by reversal can be solved easily, in this paper, we first transform an unsigned permutation of length n,π （π1 ,… ,πn）, into a set S（π） containing 2^n signed permutations, so that the reversal distance of π is equal to the reversal distance of the optimal signed permutation in S（π）. Then analyze the structural features of S（π） by creating a directed graph and induce a new computing model of this question. Finally, an improved genetic algorithm for solving the new model is proposed. Experimental results show that the proposed model and algorithm is very efficient in practice.     

Dependence analysis based on dynamic slicing for debugging

Dynamic program slicing is an effective technique for narrowing the errors to the relevant parts of a program when debugging. Given a slicing criterion, the dynamic slice contains only those statements that actually affect the variables in the slicing criterion. This paper proposes a dynamic slicing method based on static dependence analysis. It uses the program dependence graph and other static information to reduce the information needed to be traced during program execution. Thus, the efficiency is dramatically improved while the precision is not depressed. The slicing criterion is modified to fit for debugging. It consists of filename and the line number at which the statement is.     

Deviation inequality for the number of k -cycles in a random graph

We study the number of k-cycles in a random graph G(n, p). We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference is not effective. By constructing a variable that approximates to the number of k-cycles in a random graph and using a new and extensive martingale inequality, we get the results in this paper. Foundation item: Supported by the National Natural Science Foundation of China (10571139)     

面向对象软件的程序级FMEA方法

软件失效模式及影响分析（FMEA）是一种提高软件安全性和可靠性的有效方法。本文提出基于程序依赖关系的面向对象软件程序级FMEA方法,在详细设计及代码实现阶段,通过构造系统依赖图描述代码间存在的复杂的依赖关系,并采用切片技术提高失效原因和影响分析的效率。     

改进的基于逆向流分析的C程序切片算法

为解决切片算法时空开销太大的问题, 提出一种改进的基于逆向流的静态切片算法。只需通过分析控制依赖, 获得程序整体框架, 再从切片点开始基于逆向控制流从里向外扩张式扫描,在扫描中不断获得只与切片相关的数据依赖, 以此得到程序切片。该算法减少了计算控制流的工作量, 避免计算谓词依赖集的过程, 减少了存储资源开销, 提高了切片的效率。     

基于改进ADPP的多变量时间序列异常检测

针对多变量时间序列异常检测问题进行研究,提出基于改进ADPP的多变量时间序列异常检测算法IADPP.IADPP算法引入适用于多变量时间序列的张量相似性度量SSOTPCA,并以此相似性度量构造序列集的k-近邻图,在构造的k-近邻图上计算多变量时间序列的异常系数.研究结果表明,IADPP算法克服了原有ADPP算法不支持多变量时间序列和要求密度均匀的缺陷,取得了较好的检测结果.     

System Dependence Graph Construction for Aspect Oriented C＋＋

This paper proposes an extended system dependence graph called AspectSDG to represent control and data dependences for AspeetC＋＋ programs, and presents an approach for the construction of AspectSDG. This approach decomposes aspect-oriented programs into three parts： component codes, aspect codes, and weaving codes. It constructs program dependence graphs （PDGs） for each part, and then connects the PDGs at call sites to form the complete AspectSDG. The AspectSDG can deal with advice precedence correctly, and represent the additional dependences caused by aspect codes. Based on this model, we introduce how to compute a static slice of an AspectC＋ ＋ program.     

A Note on the Multifractal Decomposition of Directed Graph Self Similar Sets

We investigated the directed graph self similar sets under some weak overlapping condition. We get the multifractal decomposition formulas for these sets, i. e.,dim Ku^a DimKu^a =f(a), where fis the multifractal spectral function of the directed graph self similar measure. Especially, the results improve that of Edgar and Mauldin to the case which allows certain overlapping.     

Double-Talk Detection Algorithm Based on the Ι2 Norm

Echo canceller generally needs a double-talk detector which is used to keep the adaptive filter from diverging in the appearance of near-end speech. In this paper we adopt a new double-talk detection algorithm based on ι2 norm to detect the existence of near-end speech in an acoustic echo canceller. We analyze this algorithm from the point of view of functional analysis and point out that the proposed double-talk detection algorithm has the same performance as the classic one in a finite Banach space. The remarkable feature of this algorithm is its higher accuracy and better computation complexity. The fine properties of this algorithm are confirmed by computer simulation and the application in a multimedia communication system.     

Motif Finding问题的分布式参数算法

基于从DNA序列形成k分图的图理论算法和查找k-clique的理论算法,设计与实现了对Motif Finding问题求解的分布式参数算法。该算法的主要特点是:采用新的1-3树分枝算法并实现分布式计算机制,即任务可以随着计算过程的展开在每一阶段不断地分解并分布到不确定数量的申请参与计算的客户机上,服务器端负责任务均衡与结果整合。实验结果表明:分布式参数算法充分利用多台机器协同计算,能够正确、高效地得到计算结果,为求解生物计算中难解的Motif Finding问题提供了有效的解决手段。     

Genetic Algorithm-Based Approaches for Optimizing S-Boxes

0 Introduction Being as unique nonlinear components of block ci- pher algorithms, S-boxes provide the most important confusion effect, and directly influence the security of the algorithms. There are many ways to construct S-boxes[1-5]. On one hand, diffe…     

异构任务图的实现模型

任意异构程序映射到任意异松系统上执行,是并行程序计算最复杂的情况,为此提出了异构任务图的定义,它是异构程度直观和有效描述方法,还研究了异构任务图的实现模型,它是异构计算环境中软件和硬件的桥梁,分别给出了任务图的分簇算法、系统图的分簇算法和映射算法及应用实例,利用该模型可设计出可移植的并行程序,然后调度到可动态配置的异构计算机组织上运行。     

Genetic algorithm for Chinese postman problems

Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It could be extended to solve Chinese postman problem in directed graph. We make these efforts for exploring in optimizing the mixed Chinese postman problem. Foundation item: Supported by the National Natural Science Foundation of China (60133010, 70071042) Biography: Jiang Hua(1974-), male, Master candidate, research direction: Evolutionary computation.