Found 47 results matching "widening operator" across all subforums.
Showing results 1–10 of 47 — sorted by relevance.
A widening operator ∇ must satisfy two conditions: (1) it over-approximates the join — i.e., a ⊔ b ⊑ a∇b — and (2) for any ascending chain, the sequence produced by iteratively applying ∇ eventually stabilizes. This ensures termination even on infinite-height lattices. See also the linked FAQ on interval widenings...
I'm implementing interval analysis and applying the standard widening operator on loop heads. On doubly-nested loops the result is just ⊤ after the first iteration. Is there a way to delay widening or apply thresholds? I've read about the "widening up to" technique from Cousot & Halbwachs...
The classic Cousot & Cousot 1992 paper "Comparing the Galois connection and widening/narrowing approaches" argues they're equivalent in power under certain conditions. But in practice the widening approach seems much more common for numerical domains. Does the Galois formulation have practical advantages?
For the interval domain, the classic widening sets a bound to −∞ if the lower bound decreases across iterations, and to +∞ if the upper bound increases. I've coded this up but I'm getting unsound results on the example from Dillig's slides. Sharing my OCaml snippet below — anyone spot the bug?
Bourdoncle's 1993 paper on "Efficient chaotic iteration strategies with widenings" proposes applying the widening only at certain control-flow vertices (loop heads identified via depth-first ordering). Has anyone compared this against naïve all-heads widening on real code?
Given two abstract domains A and B each with their own widening operators, can you always construct a sound widening for their cartesian product A×B? The paper by Arceri et al. discusses this — component-wise widening works but may lose relational information between the two components...
Playing with IKOS (NASA's static analysis framework) for a class project. It applies widening only after k iterations (delay widening). Setting k=3 vs k=5 makes a big difference in precision on my benchmarks. Is there any principled way to choose k, or is it just tuning?
After applying the widening operator to reach a post-fixpoint, we can apply narrowing to recover precision. But narrowing is not guaranteed to terminate in general — the standard solution is to apply it a fixed number of times. In practice, 2–3 narrowing iterations seem to recover most lost precision...
The recent PACMPL paper "Efficient Abstract Interpretation via Selective Widening" proposes applying widening only where necessary rather than at every loop head. The approach tracks which lattice elements are genuinely in an infinite ascending chain and widens only those. Big precision gains reported!
Looking for good references covering abstract domains and widening at a graduate level. So far I've read: Cousot & Cousot '77 (foundational), Nielson et al. "Principles of Program Analysis," and Dillig's lecture notes. Is there a textbook that covers modern abstract domain combinations?