南京大学学报(自然科学版) ›› 2015, Vol. 51 ›› Issue (2): 453–457.

• • 上一篇    

抽象解释的部分等价逻辑关系模型

王蓁蓁1,2*   

  • 出版日期:2015-03-06 发布日期:2015-03-06
  • 作者简介:(1. 金陵科技学院软件工程学院,南京,211169; 2. 江苏省信息分析工程实验室,南京,211169)
  • 基金资助:
    国家自然科学基金(611170071),金陵科学学院科研基金(jit-n-201305)

A logical partial equivalencerelation model of abstract interpretation

Wang Zhen-zhen1,2*   

  • Online:2015-03-06 Published:2015-03-06
  • About author:(1.School of Software Engineering, Jinling Institute of Technology, Nanjing, 211169, China) (2. Information Analysis Engineering Laboratory of Jiangsu Province, Nanjing, 211169, China)

摘要: 抽象解释由CousotP和CousotR于1977年提出,随后许多作者做了大量工作。本文从不同的角度构造了基于部分等价关系和逻辑部分等价关系一个模型,它与传统抽象解释模型根本不同,该模型并不是对具体系统在“近似”意义上的抽象,而是对原系统上的一切关系(包括逻辑关系)的抽象,因此它不是原系统的“简化”,而是原系统的一个“深化”。从而在此模型上提出的问题具有另外的特征,例如我们提出了复杂性和多态性等问题。

Abstract: Abstract interpretation was presented by CousotP and CousotR in 1977. Subsequently many scholars have done a lot of studies on it. Generally speaking, the classic abstract interpretation theory is developing within two equivalent formal frameworks of Galois connections and closure operators. This paper constructs a model based on partial equivalence relations and logical partial equivalence relations from a different perspective. It considers the abstract domain as a collection of “partial equivalence relations” and the semantic operator as a collection of “logical partial equivalence relations”. So this model is totally different from the traditional abstract interpretation models. Except that it requires that the concrete or abstract semantic operators have certain logical relations, the model never requires some special properties such as the monotonicity, so in this point it is different from the classic model. Besides, it is not an abstraction of a concrete system in an “approximate” sense, but rather an abstraction of all relations (including logical relations) on the original system. Thus this model is not a “simplification” of the original system but rather a “complication” of the original system.In some sense, it disjoins the “quality” unit from the original system, and it may be more complex than the original system. The advantage of this model is that it embodies some logical relations concerned with the system functions, because itdoes not require that concrete or abstract semantic operations have any special properties (e.g. monotonicity). Therefore here the abstraction is not as the classic understanding. The classic way is to treat some approximation of states as an abstraction, and require that both concrete semantic domains and abstract semantic domains have certain special mathematical structure, for example, lattice or cpo, that is the result of treating “approximation” as the basic essence of abstraction. Whereas our model help structure a concrete system from the semantic domain and the semantic operation the two parts by using partial equivalence relations and logical partial equivalence relations, i.e., it extracts their components separately and finally forms the collection of equivalence classes to discuss the semantic domain and semantic operators. Also, based on such a model, we can discuss the issues that are different from the traditional models, such as the complexity problem and the polymorphism problems, so that it may deepen our understanding for the abstract interpretation theory

[1] CousotP,CousotR. Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximation of fixpoints. In:Proceedingsof the 4thAnnual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Los Angeles, California:ACM Press, 1977, 238~252.
[2] MitchellJC.程序设计语言理论基础. 许满武, 徐建,衷宜. 北京:电子工业出版社,2006,224~460
[3] He H, Gupta N. Automated debugging using path-based weakest preconditions. In: Michel W, Tiziana M. FASE, Lecture Notes in Computer Science: Springer –Verlag, 2004, 2984: 267~280.
[4] CousotP, CousotR.bstract interpretation frameworks.Journal of Logic and Computation, 1992, 2(4):511~547.
[5] CousotP,CousotR. Temporal abstract interpretation. In:Proceedings of the27thACM SIGACT-SIGMOD-SIGART Symposium on Principles of Programming Languages, Boston, MA, USA: ACM Press, 2000, 12~25.
[6] GiacobazziR,RanzatoF,ScozzariF. Making abstract interpretations complete. Journal of the ACM,2000, 47(2): 361~416.
[7] CousotP,CousotR. Systematic design of program analysis frameworks. In:Proceedings of the 6thACM Symposium on Principles of Programming Languages, San Antonio, TX:ACM Press, 1979, 269~282.
[8] RanzatoF,TapparoF. Generalized strong preservation by abstract interpretation.Journal of Logic and Computation, 2007, 17(1): 157~197.
[9] RanzatoF,TapparoF. Strong preservation of temporal fixpoint-based operators by abstract interpretation. In: Proceedings of the 7th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI). LNCS 3855. Charleston, SC, USA: Springer Verlag, 2006, 332~347.
[10] MayerW,StumptnerM. Abstract interpretation of programs for model-based debugging. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07), San Francisco, CA, USA: Morgan Kaufmann Publishers Inc, 2007, 471~476.
[11] 王蓁蓁. 模型检验综述. 计算机科学, 2013, 40(6A): 1~14
[12] 高鹰, 陈意云. 基于抽象解释的代码迷惑有效性比较框架. 计算机学报, 2007, 30(5): 806~814.
[13] 杨波, 张明义, 谢刚. 抽象解释理论框架及其应用. 计算机工程与应用, 2010, 46(8): 16~20.
[14] 王蓁蓁, 邢汉承. 逻辑马尔可夫决策过程的正则条件概率理论. 南京大学学报(自然科学), 2013, 49(4): 439~447.
[15] 李梦君, 李舟军, 陈火旺. 抽象解释理论的程序验证技术. 软件学报, 2008, 19(1): 17~26.
[16] 钱俊彦, 赵岭忠, 蔡国永. 基于完备抽象解释的性质强保留抽象研究. 计算机学报, 2014, 37(8): 1754~1766
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!