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.     

抽象解释理论框架及其应用

在高度依赖计算机的现代社会,软件（特别是大型实时安全攸关软件）的可靠性成为计算机界和整个社会都非常关注的问题。现有的形式化软件验证工具都不得不通过近似来处理复杂问题中的计算,P.Cousot和R.Cousot提出的抽象解释作为一种在数学模型间进行可靠近似的理论,为各类自动验证工具中不同的近似方法建立起一个统一的形式化框架。抽象解释理论在程序分析和验证研究领域得到了广泛的关注与应用,其应用范围涵盖了程序静态分析、程序变换、程序调试、程序水印等方面。描述了基于程序不动点语义的抽象解释理论框架,并对其近年来的应用现状进行了较为全面的介绍,最后给出了抽象解释理论中尚存在的一些问题及可能的研究方向。     

基于抽象解释的C程序信息保密性研究

在分析程序具体语义的基础上,提出一种信息保密性检测方法。构造具体语义和抽象语义的对应关系,根据待测程序性质构建抽象语义,同时在抽象基础上,采用限界思想来优化检测的效率。通过该方法降低程序检测的复杂性,减少时间和空间的浪费,提高了检测的效率和准确度。     

基于抽象解释的可执行代码值范围分析

阐述可执行代码抽象存储空间模型的概念并给出程序运行时刻环境抽象表示技术。通过抽象解释静态逼近程序不动点语义的理论保证二进制代码数据流分析的正确性以及可计算性。基于抽象解释和单调数据流框架提出一种自动分析可执行代码变量取值范围的方法及自动获取程序循环最大迭代次数和不可执行路径,并给出数据流分析实例。