一种基于模块单子语义的动态程序切片方法

提出一种基于程序模块单子语义的新动态切片方法--模块单子动态切片.首先通过单子转换器,将切片这一类计算抽象成独立于具体语言的实体：切片单子转换器.然后,将该切片转换器作为模块加载到实际程序中,并给出相应的模块单子动态切片算法.据此,可直接在抽象语法结构上计算动态切片,不必记录程序执行历史;相应单子切片器也无需显式地构造诸如依赖图的中间结构.这种模块化抽象机制使得文中的动态切片算法具有很强的可扩展性和重用性.     

Uniform Closures: Order-Theoretically Reconstructing Logic Program Semantics and Abstract Domain Refinements

The notion of uniform closure operator is introduced, and it is shown how this concept surfaces in two different areas of application of abstract interpretation, notably in semantics design for logic programs and in the theory of abstract domain refinements. In logic programming, uniform closures permit generalization, from an order-theoretic perspective, of the standard hierarchy of declarative semantics. In particular, we show how to reconstruct the model-theoretic characterization of the well-known s-semantics using pure order-theoretic concepts only. As far as the systematic refinement operators on abstract domains are concerned, we show that uniform closures capture precisely the property of a refinement of being invertible, namely of admitting a related operator that simplifies as much as possible a given abstract domain of input for that refinement. Exploiting the same argument used to reconstruct the s-semantics of logic programming, we yield a precise relationship between refinements and their inverse operators: we demonstrate that they form an adjunction with respect to a conveniently modified complete order among abstract domains.     

一种面向对象程序的过程间切片算法

程序切片是一种程序分析技术，它通过把程序减少到只包含与某个特定计算相关的那些语句来分析程序，过程间切片作为图形可达性问题时，需要扩展过程内切片所用的程序依赖图（PDG）成系统依赖图（SDG），然后利用两阶段图形可达性算法计算比较精确的切片，目前程序切片技术的研究以面向对象程序切片为主，文中讨论了一种合适面向对象程序的分层切片方法，并综合分层切片方法和两阶段图形可达性算法提出了一种简化的计算面向对象程序过程间切片的算法。     

用Z形式化描述程序切片

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

Trace-Based Abstract Interpretation of Operational Semantics

We present trace-based abstract interpretation, a unification of severallines of research on applying Cousot-Cousot-style abstract interpretation a.i. tooperational semantics definitions (such as flowchart, big-step, and small-step semantics)that express a programs semantics as a concrete computation tree of trace paths. Aprograms trace-based a.i. is also a computation tree whose nodes contain abstractions ofstate and whose paths simulate the paths in the programs concrete computation tree.Using such computation trees, we provide a simple explanation of the central concept of collecting semantics, and we distinguish concrete from abstract collectingsemantics and state-based from path-based collecting semantics. We also expose therelationship between collecting semantics extraction and results garnered from flow-analytic and model-checking-based analysis techniques. We adapt concepts fromconcurrency theory to formalize safe and live a.i.s for computation trees; in particular, coinduction techniques help extend fundamental results to infinite computation trees.Problems specific to the various operational semantics methodologies are discussed: Big-step semantics cannot express divergence, so we employ a mixture of induction andcoinduction in response; small-step semantics generate sequences of programconfigurations unbounded in size, so we abstractly interpret source language syntax.Applications of trace-based a.i. to data-flow analysis, model checking, closure analysis,and concurrency theory are demonstrated.     

基于程序切片技术的回归测试方法研究

软件测试是软件开发过程的一个重要组成部分，是进行软件有效性检查、提高软件质量的重要手段。随着软件规模的不断增大、复杂度的不断提高，传统的软件测试技术在处理大规模复杂软件系统时会出现许多问题。程序切片是一种程序分解术，主要是通过寻找程序内部的相关性来分解程序，从而达到快速错误定位或理解程序的目的。主要探讨将程序切片技术引入到软件测试中，尤其是分析在回归测试中切片方法是如何提高效率的。     

含指针程序的单子切片方法

传统的含指针程序切片方法将指向分析与切片计算分开,增加了一定系统开销,为此文中提出一种可同时进行切片计算和指向分析的单子切片算法.该算法将程序正向切片思想与数据流迭代分析相结合,它是流敏感的,具有一定的精度,而且因指向分析和切片计算同时进行,故不需要像一般的流敏感分析方法那样记录每一个程序点的指向信息,而只需记录当前所分析的程序点处指向信息,从而节省了存储空间.此外,它还继承了原有单子切片方法所具有的强语言适应性和组合性.     

基于程序切片技术的回归测试方法研究

软件测试是软件开发过程的一个重要组成部分,是进行软件有效性检查、提高软件质量的重要手段。随着软件规模的不断增大、复杂度的不断提高,传统的软件测试技术在处理大规模复杂软件系统时会出现许多问题。程序切片是一种程序分解术,主要是通过寻找程序内部的相关性来分解程序,从而达到快速错误定位或理解程序的目的。主要探讨将程序切片技术引入到软件测试中,尤其是分析在回归测试中切片方法是如何提高效率的。     

一种C++程序切片系统的设计与实现

程序切片是一种程序分析技术,它主要应用在程序的调试和逆向工程。文中介绍了笔者设计并实现的一个C 程序切片系统。其中包括系统的总体框架,系统中使用的数据结构以及切片生成算法。本系统已经成功应用到了X型导弹指挥软件的故障诊断中。     

一种基于切片技术度量Java耦合性的框架

在研究面向对象的度量问题时,人们通过简单的统计方法和基于信息源的方法来度量其中的一些特征,例如基本度量、CK度量和AoKi度量等。文中采用一种基于程序切片的方法来度量Java的耦合性问题,通过对J ava源程序中存在的耦合关系的度量,得到了一种比传统方法更精确的耦合度量方法。     

程序切片技术在并发程序模型检查中的应用

模型检查技术在硬件和协议设计方面已经取得很大成功,但在软件验证方面仍存在很多困难。其主要问题是如何从源代码中自动抽取验证所要模型并精简其状态空间。文中通过对程序切片技术的研究,来解决并发程序验证的建模问题,包括把验证公式映射到切片准则．并把得到的程序切片转化为验证所需的模型。经程序切片处理后,软件模型检查效率得到提高。     

并发程序的切片模型检验方法

提出了一种对并发程序进行切片以缩减模型检验状态空间的方法,首先针对并发程序中的同步与通信定义了一组依赖关系,包括并发分支与接合．非确定性,信道,共享变量等特征,对于从要验证的时态逻辑性质中提取的关于多个程序点的切片标准,文中给出算法根据相应的依赖关系通过不动点运算得到并发程序切片,可以证明得到的切片与原程序对于该性质具有相同的可满足性。     

抽象解释及其应用研究进展

抽象解释是一种对用于形式描述复杂系统行为的数学结构进行抽象和近似并推导或验证其性质的理论. 抽象解释自20世纪70年代提出以来,在语义模型、程序分析验证、混成系统验证、程序转换、系统生物学模型分析等领域取得了广泛应用. 近年来,抽象解释在程序分析、神经网络验证、完备性推理、抽象域改进等方面取得较大进展. 基于此,系统综述了抽象解释及其应用的研究进展. 首先概述了抽象解释理论的基本概念,介绍了抽象解释理论、抽象域的研究进展;然后概述了基于抽象解释的程序分析方面的研究进展; 之后概述了基于抽象解释的神经网络模型验证、神经网络模型鲁棒训练、深度学习程序的分析等方面的研究进展;又对抽象解释在智能合约可信保证、信息安全保证、量子计算可信保证等方面的应用进展进行了介绍;最后指明了抽象解释未来可能的研究方向.

     

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.     

Slicing Software for Model Construction

Applying finite-state verification techniques (e.g., model checking) to software requires that program source code be translated to a finite-state transition system that safely models program behavior. Automatically checking such a transition system for a correctness property is typically very costly, thus it is necessary to reduce the size of the transition system as much as possible. In fact, it is often the case that much of a program's source code is irrelevant for verifying a given correctness property.In this paper, we apply program slicing techniques to remove automatically such irrelevant code and thus reduce the size of the corresponding transition system models. We give a simple extension of the classical slicing definition, and prove its safety with respect to model checking of linear temporal logic (LTL) formulae. We discuss how this slicing strategy fits into a general methodology for deriving effective software models using abstraction-based program specialization.     

Lightweight Reasoning about Program Correctness

Automated verification tools vary widely in the types of properties they are able to analyze, the complexity of their algorithms, and the amount of necessary user involvement. In this paper we propose a framework for step-wise automatic verification and describe a lightweight scalable program analysis tool that combines abstraction and model checking. The tool guarantees that its True and False answers are sound with respect to the original system. We also check the effectiveness of the tool on an implementation of the Safety-Injection System.     

Slicing, Chopping, and Path Conditions with Barriers

One of the critiques on program slicing is that slices presented to the user are hard to understand. This is mainly related to the problem that slicing dumps the results onto the user without any explanation. This work will present an approach that can be used to filter slices. This approach basically introduces barriers which are not allowed to be passed during slice computation. An earlier filtering approach is chopping which is also extended to obey such a barrier. The barrier variants of slicing and chopping provide filtering possibilities for smaller slices and better comprehensibility. The concept of barriers is then applied to path conditions, which provide necessary conditions under which an influence between the source and target criterion exists. Barriers make those conditions more precise.     

并发程序切片原型系统的设计与实现

并发程序切片是并发程序分析的一种重要手段。针对多线程共享变量通信机制,在通过程序分析工具CodeSurfer获取程序基本信息的基础上构造程序可达图,生成以程序状态和语句二元组为节点的并发程序依赖图,实现了基于程序可达图的并发程序切片原型系统。初步实验结果表明,与传统的切片方法相比,采用基于程序可达图的并发程序切片方法,可有效地解决依赖关系不可传递问题,获得高精度的并发程序切片。     

基于ISDG的面向对象程序分片技术研究

程序分片是一种有效的程序分析技术,它能根据给定的分片准则从源程序中提取出所需部分进行分析,如进行程序调试、测试、程序重构分析等.程序分片技术在结构化程序中已有较广泛的应用,但对于面向对象语言程序,其研究与应用还存在一些待解决的问题. 针对面向对象语言程序,提出了一种改进后的系统依赖图:ISDG,用来更好地表示面向对象程序中的依赖关系,从而解决了对象类型参数和属性的表示问题,使分片更加准确.