Skip to Main content Skip to Navigation
Reports

Widening with Thresholds for Programs with Complex Control Graphs

Lies Lakhdar-Chaouch 1 Bertrand Jeannet 1 Alain Girault 1
1 POP ART - Programming languages, Operating Systems, Parallelism, and Aspects for Real-Time
Inria Grenoble - Rhône-Alpes, LIG [2007-2015] - Laboratoire d'Informatique de Grenoble [2007-2015]
Abstract : The precision of an analysis based on abstract interpretation does not only depend on the expressiveness of the abstract domain, but also on the way fixpoint equations are solved: exact solving is often not possible. The traditional solution is to solve iteratively abstract fixpoint equations, using extrapolation with a widening operator to make the iterations converge. Unfortunately, the extrapolation too often loses crucial information for the analysis goal. A classical technique for improving the precision is ''widening with thresholds'', which bounds the extrapolation. Its benefit strongly depends on the choice of relevant thresholds. In this paper we propose a semantic-based technique for automatically inferring such thresholds, which applies to any control graph, be it intraprocedural, interprocedural or concurrent, without specific assumptions on the abstract domain. Despite its technical simplicity, our technique is able to infer the relevant thresholds in many practical cases.
Document type :
Reports
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00606961
Contributor : Bertrand Jeannet <>
Submitted on : Thursday, July 7, 2011 - 6:48:59 PM
Last modification on : Friday, July 17, 2020 - 11:10:25 AM
Long-term archiving on: : Saturday, October 8, 2011 - 2:35:06 AM

File

RR-7673.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00606961, version 1

Collections

Citation

Lies Lakhdar-Chaouch, Bertrand Jeannet, Alain Girault. Widening with Thresholds for Programs with Complex Control Graphs. [Research Report] RR-7673, INRIA. 2011, pp.17. ⟨inria-00606961⟩

Share

Metrics

Record views

553

Files downloads

285