geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants

ISCAS OpenIR

	geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants
	Kapur Deepak; Zhang Zhihai; Horbach Matthias; Zhao Hengjun; Lu Qi; Nguyen ThanhVu
	2013
发表期刊	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN	0302-9743
卷号	7788 页码:189-228
摘要	Geometric heuristics for the quantifier elimination approach presented by Kapur (2004) are investigated to automatically derive loop invariants expressing weakly relational numerical properties (such as l &le x &le h or l &le ±x ±y &le h) for imperative programs. Such properties have been successfully used to analyze commercial software consisting of hundreds of thousands of lines of code (using for example, the Astre´e tool based on abstract interpretation framework proposed by Cousot and his group). The main attraction of the proposed approach is its much lower complexity in contrast to the abstract interpretation approach (O(n ²) in contrast to O(n ⁴), where n is the number of variables) with the ability to still generate invariants of comparable strength. This approach has been generalized to consider disjunctive invariants of the similar form, expressed using maximum function (such as max (x + a,y + b,z + c,d) &le max (x + e,y + f,z + g,h)), thus enabling automatic generation of a subclass of disjunctive invariants for imperative programs as well. © Springer-Verlag Berlin Heidelberg 2013.; Geometric heuristics for the quantifier elimination approach presented by Kapur (2004) are investigated to automatically derive loop invariants expressing weakly relational numerical properties (such as l &le x &le h or l &le ±x ±y &le h) for imperative programs. Such properties have been successfully used to analyze commercial software consisting of hundreds of thousands of lines of code (using for example, the Astre´e tool based on abstract interpretation framework proposed by Cousot and his group). The main attraction of the proposed approach is its much lower complexity in contrast to the abstract interpretation approach (O(n ²) in contrast to O(n ⁴), where n is the number of variables) with the ability to still generate invariants of comparable strength. This approach has been generalized to consider disjunctive invariants of the similar form, expressed using maximum function (such as max (x + a,y + b,z + c,d) &le max (x + e,y + f,z + g,h)), thus enabling automatic generation of a subclass of disjunctive invariants for imperative programs as well. © Springer-Verlag Berlin Heidelberg 2013.
收录类别	EI
关键词	Abstracting
部门归属	(1) Department of Computer Science University of New Mexico Albuquerque NM United States; (2) School of Mathematical Sciences Peking University Beijing China; (3) Institute of Software Chinese Academy of Sciences Beijing China
语种	英语
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15627
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Kapur Deepak,Zhang Zhihai,Horbach Matthias,et al. geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants[J]. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2013,7788:189-228.
APA	Kapur Deepak,Zhang Zhihai,Horbach Matthias,Zhao Hengjun,Lu Qi,&Nguyen ThanhVu.(2013).geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants.Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),7788,189-228.
MLA	Kapur Deepak,et al."geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants".Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7788(2013):189-228.