Granularity-Driven Dynamic Predicate Slicing Algorithms for Message Passing Systems

Program Slicing is a well-known decomposition technique that transforms a large program into a smaller one that contains only statements relevant to the computation of a selected function. In this paper, we present two novel predicate-based dynamic slicing algorithms for message passing programs. Unlike more traditional slicing criteria that focus only on parts of the program that influence a variable of interest at a specific position in the program, a predicate focuses on those parts of the program that influence the predicate. The dynamic predicate slices capture some global requirements or suspected error properties of a distributed program and computes all statements that are relevant. The presented algorithms differ from each other in their computational approaches (forward versus backward) and in the granularity of information they provide. A proof of correctness of these algorithms is provided. Through the introduction of dominant states and dominant events, critical statement executions are identified that change the value of the global predicate. Under this formulation, optimizing dynamic predicate slicing becomes a meaningful goal as well. Finally, we present how predicate slices can be applied to support comprehension tasks for analyzing and maintaining distributed programs.     

基于谓词动态切片技术的AOP测试用例生成方法研究

面向方面程序设计是面向对象程序设计技术的补充和完善,高效的面向方面程序测试方法是面向方面程序的质量保证.提出一个基于谓词动态切片技术的测试方法.首先,构造完整的AOP语句控制流图,它包含AOP的方面、切入点、连接点、建议等因素.然后,根据完整的AOP语句控制流图生成所有路径,针对每条路径,构造其分支函数,计算得到相应的测试数据,若路径不可执行,则不再计算其测试数据.在这个过程中,通过构建简化动态依赖图来生成谓词动态切片,再用谓词动态切片来帮助调整测试数据.最后,将各路径的实际输出数据与期望输出数据相比较,即可判断该程序是否有错误.经实例分析和实验验证,此方法可以系统地测试一个完整的面向方面程序,提高了测试数据的生成效率,并产生有效的测试用例.     

用Z形式化描述程序切片

程序切片是一种重要技术,已广泛地应用于软件工程的各个领域,如程序理解、维护、调试、测试、复用、度量等.虽然,越来越多的研究者致力于程序切片工作,然而由于缺少形式化方面的工作导致程序切片可能存在不一致性和模糊性.本文尝试着用Z语言来形式化描述程序切片,考虑了程序切片中诸如程序依赖图和程序切片算法等常用的方面.该形式化描述不仅能帮助人们正确地理解程序切片的含义,而且还能够从比较严格的意义上明确程序切片的应用领域.     

利用谓词/变迁网证明的一阶谓词逻辑命题

研究了证明一般的一阶谓词逻辑命题的方法,根据网逻辑的思想,利用谓词/变迁网对一般形式的一阶谓词逻辑命题进行了图形表示,提出了2种一阶谓词逻辑命题的证明方法：图形证明法和矩阵证明法。举出一个实际的例子来说明证明思路。     

求解TSP问题的思维进化算法

针对一类非数值问题──TSP的特点,在基本思维进化算法(MEC)框架的基础上,提出了求解TSP的趋同和异化策略,从而实现了MEC在求解非数值问题的一个应用,并对其收敛性进行了简要证明。同某些遗传算法(IENS和GESA)比较的仿真实验结果表明:MEC在收敛速度、解的优良性等方面要优于这些遗传算法。     

Predicate Abstraction of ANSI-C Programs Using SAT

Predicate abstraction is a major method for verification of software. However, the generation of the abstract Boolean program from the set of predicates and the original program suffers from an exponential number of theorem prover calls as well as from soundness issues. This paper presents a novel technique that uses an efficient SAT solver for generating the abstract transition relations of ANSI-C programs. The SAT-based approach computes a more precise and safe abstraction compared to existing predicate abstraction techniques.     

使用XML的一阶谓词逻辑归结原理

归结原理(resolution principle)是计算机自动推理的重要原理之一.将XML加入到使用归结原理的证明过程中,利用XML结构与语义自描述的特性,简化归结过程的计算机实现,并给出相应基于XML的算法.     

使用XML的一阶谓词逻辑归结原理

归结原理（resolution principle)是计算机自动推理的重要原理之一。将XML加入到使用归结原理的证明过程中，利用XML结构与语义自描述的特性，简化归结过程的计算机实现，并给出相应基于XML的算法。     

谓词逻辑中前束范式的求解方法研究

《离散数学》谓词逻辑中前柬范式的求解一直是一个难点。对前柬范式求解步骤进行分析和总结,对两种换名规则和换名情况进行分类和研究．结合实例帮助学生更好地掌握整个前束范式的求解过程,并在实际教学过程中起到很好的教学效果。     

Verification of Knowledge-Based Systems Using Predicate/Transition Nets

As expert-system technology gains broader acceptance, the need to build and maintain large-scale knowledge-based systems (KBSs) will assume greater importance. Traditional approaches to KBS verification generally contain no predicate/transition (PrT) net models, thus making them slow for the large-scale KBS with chained errors. This paper proposes an attractive alternative to KBS verification, in which the KBS is modeled as a PrT-net model. Then, the least fixpoint semantics of the PrT-net model can be introduced into the KBS for the purpose of speeding up the computations of the KBSs. The significance of this paper is that seven propositions are formulated to detect errors of redundancy, subsumption, unnecessary condition, circularity, inconsistency, dead end, and unreachable goal. Thus, the performance of a computer-aided-design tool for KBSs can be improved to some extent. Meanwhile, specification languages, including Programming in Logic, Frame-and-Rule-Oriented Requirements Specification Language, and the like, are suitable to this approach.     

Manufacturing-Oriented Discrete Process Modeling Approach Using the Predicate Logic

Part machining is a discrete manufacturing process. In order to evaluate the manufacturing process, an intelligent modeling method based on the first-order predicate logic is proposed. First, the basic predicate formula is defined according to the machining method, and the predicate and variables are illustrated in detail. Thus, the process representation is completed. Second, to construct the process model, the modeling element is put forward, which includes three nodes. Components of modeling element are, respectively, discussed, as well as the mapping relationship between modeling element and predicate. After the definition of modeling predicate formula, five basic inference rules are established. Consequently, the manufacturing process model is constructed. Third, on the basis of the process model, the process simulation is carried out to evaluate the manufacturing performances, such as the production efficiency, the utilization rate of machining equipment, the production bottleneck, etc. Finally, a case study is conducted to explain this modeling method.     

Using Predicate/Transition-Nets to Model and Analyze Distributed Database Systems

In this paper, a net model for decentralized control of user accesses to a distributed database is proposed. It is developed in detail for the restricted case of updating distributed copies of a single database. Predicate/transition-nets, a first-order extension of Petri nets, are shown to provide suitable means for concise representation of complex decentralized systems and for their rigorous formal analysis. It will be demonstrated in the present paper how these net models can be constructed and interpreted in a quite natural manner and how they can be analyzed by linear algebraic methods. By this, it will be shown that the modeled distributed database system is deadlock-free and guarantees a consistent database as well as a fair and effective service to the users.     

用转换表和通信表解决不规则问题的方案

目前,在分布式存储机制上,程序是被设计成为帮助用户有效地解决不规则问题（如求解偏微分方程、稀疏矩阵等）。其关键是描述全局下标与独立处理器的地址空间关系的算法。为此,本文介绍了采用转换表、通信表的解决方式,以及它们作为Ｒｕｎｔｉｍｅ库的一个工具,是如何由库函数在独立的局部下标空间组成的全局下标空间调用运行。     

Using Dynamic Information in the Interprocedural Static Slicing of Binary Executables

Although the slicing of programs written in a high-level language has been widely studied in the literature, relatively few papers have been published on the slicing of binary executable programs. The lack of existing solutions for the latter is really hard to understand since the application domain for slicing binaries is similar to that for slicing high-level languages. Furthermore, there are special applications of the slicing of programs without source code like source code recovery, code transformation and the detection of security critical code fragments. In this paper, in addition to describing the method of interprocedural static slicing of binaries, we discuss how the set of the possible targets of indirect call sites can be reduced by dynamically gathered information. Our evaluation of the slicing method shows that, if indirect function calls are extensively used, both the number of edges in the call graph and the size of the slices can be significantly reduced.Ákos Kiss obtained his M.Sc. in Computer Science from the University of Szeged in 2000. He is currently working on his Ph.D. thesis and his chosen field of research is the analysis and optimization of binary executables. He was the chief programmer of a code compaction project which sought to reduce ARM binaries. He is also interested in GCC and in open source developmentJudit Jász obtained her M.Sc. in Computer Science recently from the University of Szeged and is currently a Ph.D student. Her main research interest is adapting slicing methods—originally intended for high-level languages—to binary executables. She is also actively working on improving the GCC compiler.Tibor Gyimóthy is the head of the Software Engineering Department at the University of Szeged in Hungary. His research interests include program comprehension, slicing, reverse engineering and compiler optimization. He has published over 60 papers in these areas and was the leader of several software engineering R&D projects. He is the Program Co-Chair of the 21th International Conference on Software Maintenance, which will be held in Budapest, Hungary in 2005.     

一种使用简化预排序的k-支配Skyline查询算法

近年来,Skyline查询在多目标决策、数据挖掘、数据库可视化等方面得到广泛应用.然而在高维空间环境下,skyline查询因为返回的结果集过大而不能提供有用的信息.因此,学术界提出了七-支配skyline查询的概念.它通过弱化数据点之间的支配关系,使数据点间更容易产生支配关系,从而使结果集的大小保持在一个合适的范围内.现有七-支配skyline查询算法分为建立索引和不建立索引两种类型.其中不建立索引的算法在高维空间,反相关数据和渐近输出等方面表现比较差,而基于索引的算法花费大量时间去建立索引,整体性能都不高.本文提出一种基于简化预排序的七-支配skyline查询算法(SPA),实现用O(n)的时间复杂度对数据进行简化预排序.理论论证和实验数据都显示了SPA算法远比国内外现有的最好算法更加高效.     

Program Slicing

Program slicing is a method for automatically decomposing programs by analyzing their data flow and control flow. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program, called a ``slice,' is an independent program guaranteed to represent faithfully the original program within the domain of the specified subset of behavior. Some properties of slices are presented. In particular, finding statement-minimal slices is in general unsolvable, but using data flow analysis is sufficient to find approximate slices. Potential applications include automatic slicing tools for debuggng and parallel processing of slices.     

基于符号模拟和约束逻辑编程的RTL级Verilog谓词抽象方法

利用人工智能最新研究成果--约束逻辑编程对Verilog描述进行谓词抽象,并与目前基于SAT的方法进行了比较.首先通过符号模拟建立Verilog的形式化模型,然后结合要抽象的谓词,将谓词抽象问题转化为约束逻辑编程问题并进行求解.该方法的优点是在计算抽象系统时,不需要像基于SAT的方法那样将字级约束打散成位级约束,求解效率显著提高;提供了一个统一的框架用于描述各种约束.实验结果表明,与基于SAT的抽象技术相比,基于约束逻辑编程的抽象方法的求解速度有显著提高.     

基于遗传算法求解时间表问题

基于遗传算法求解时间表问题,通过具体时间表问题的描述和分析,定义了一个新颖的染色体编码方式,然后基于该编码,进一步分析并设计了遗传操作—交叉和变异。算法运行结果显示该方法是可行的。     

Bounded Model Checking Using Satisfiability Solving

The phrase model checking refers to algorithms for exploring the state space of a transition system to determine if it obeys a specification of its intended behavior. These algorithms can perform exhaustive verification in a highly automatic manner, and, thus, have attracted much interest in industry. Model checking programs are now being commercially marketed. However, model checking has been held back by the state explosion problem, which is the problem that the number of states in a system grows exponentially in the number of system components. Much research has been devoted to ameliorating this problem.In this tutorial, we first give a brief overview of the history of model checking to date, and then focus on recent techniques that combine model checking with satisfiability solving. These techniques, known as bounded model checking, do a very fast exploration of the state space, and for some types of problems seem to offer large performance improvements over previous approaches. We review experiments with bounded model checking on both public domain and industrial designs, and propose a methodology for applying the technique in industry for invariance checking. We then summarize the pros and cons of this new technology and discuss future research efforts to extend its capabilities.