Polyhedron over-approximation for complexity reduction in static analysis. Issue 4 (2nd October 2018)

• Record Type: Journal Article
• Authors: Seladji, Yassamine; Qu, Zheng
• Is Part Of: International journal of computer mathematics. Volume 3:Issue 4(2018)
• Page Start: 215
• Page End: 229
• Publication Date: 2018-10-02
• Subjects: Optimization problem -- formal verification -- polyhedral representation -- static analysis; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2018.1535525
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: Polyhedra are widely used in the verification of numerical programs. Specially, in the field of static analysis by abstract interpretation to express the program invariants. Polyhedra make the analysis very expressive but also very time consuming. That cost is mostly due to the minimization function, which is used to maintain polyhedra in their minimal representation without redundant constraints or generators. In this article, we propose method to over-approximate a polyhedron by minimizing the loss of accuracy. The idea is to find a good trade off between accuracy and execution time. The proposed method is applied as an alternative to the minimization function for the template polyhedra abstract domain.