Big-step abstract interpreters are an approach to build static analyzers based on big-step interpretation. While big-step interpretation provides a number of benefits for the definition of an analysis, it also require...
详细信息
Big-step abstract interpreters are an approach to build static analyzers based on big-step interpretation. While big-step interpretation provides a number of benefits for the definition of an analysis, it also requires particularly complicated fixpoint algorithms because the analysis definition is a recursive function whose termination is uncertain. This is in contrast to other analysis approaches, such as small-step reduction, abstract machines, or graph reachability, where the analysis essentially forms a finite transition system between widened analysis states. We show how to systematically develop sophisticated fixpoint algorithms for big-step abstract interpreters and how to ensure their soundness. Our approach is based on small and reusable fixpoint combinators that can be composed to yield fixpoint algorithms. For example, these combinators describe the order in which the program is analyzed, how deep recursive functions are unfolded and loops unrolled, or they record auxiliary data such as a (context-sensitive) call graph. Importantly, each combinator can be developed separately, reused across analyses, and can be verified sound independently. Consequently, analysis developers can freely compose combinators to obtain sound fixpoint algorithms that work best for their use case. We provide a formal metatheory that guarantees a fixpoint algorithm is sound if its composed from sound combinators only. We experimentally validate our combinator-based approach by describing sophisticated fixpoint algorithms for analyses of Stratego, Scheme, and WebAssembly.
The top-down solver (TD) is a local fixpoint algorithm for arbitrary equation systems. It considers the right-hand sides as black boxes and detects dependencies between unknowns on the fly-features that significantly ...
详细信息
ISBN:
(纸本)9783031656262;9783031656279
The top-down solver (TD) is a local fixpoint algorithm for arbitrary equation systems. It considers the right-hand sides as black boxes and detects dependencies between unknowns on the fly-features that significantly increase both its usability and practical efficiency. At the same time, the recursive evaluation strategy of the TD, combined with the non-local destabilization mechanism, obfuscates the correctness of the computed solution. To strengthen the confidence in tools relying on the TD as their fixpoint engine, we provide a first machine-checked proof of the partial correctness of the TD. Our proof builds on the observation that the TD can be obtained from a considerably simpler recursive fixpoint algorithm, the plain TD, by applying an optimization that neither affects the termination behavior nor the computed result. Accordingly, we break down the proof into a partial correctness proof of the plain TD, which is only then extended to include the optimization. The backbone of our proof is a mutual induction following the solver's computation trace. We establish sufficient invariants about the solver state to conclude the correctness of its optimization, i.e., the plain TD terminates if and only if the TD terminates, and they return the identical result. The proof is written using Isabelle/HOL and is available in the archive of formal proofs.
Incremental algorithms are important to dynamic graph analyses, but are hard to write and analyze. Few incremental graph algorithms are in place, and even fewer offer performance guarantees. This paper approaches this...
详细信息
ISBN:
(纸本)9781450383431
Incremental algorithms are important to dynamic graph analyses, but are hard to write and analyze. Few incremental graph algorithms are in place, and even fewer offer performance guarantees. This paper approaches this by proposing to incrementalize existing batch algorithms. We identify a class of incrementalizable algorithms abstracted in a fixpoint model. We show how to deduce an incremental algorithm A(Delta) from such an algorithm A. Moreover, A(Delta) can be made bounded relative to 5i, i.e., its cost is determined by the sizes of changes to graphs and changes to the affected area that is necessarily checked by batch algorithm A. We provide generic conditions under which a deduced algorithm A(Delta) warrants to be correct and relatively bounded, by adopting the same logic and data structures of 5i, at most using timestamps as an additional auxiliary structure. Based on these, we show that a variety of graph-centric algorithms can be incrementalized with relative boundedness. Using real-life and synthetic graphs, we experimentally verify the scalability and efficiency of the incrementalized algorithms.
interpretation has been widely used for the analysis of object-oriented languages and, in particular, Java source and bytecode. However, while most existing work deals with the problem of finding expressive abstract d...
详细信息
interpretation has been widely used for the analysis of object-oriented languages and, in particular, Java source and bytecode. However, while most existing work deals with the problem of finding expressive abstract domains that track accurately the characteristics of a particular concrete property, the underlying fixpoint algorithms have received comparatively less attention. In fact, many existing (abstract interpretation based-) fixpoint algorithms rely on relatively inefficient techniques for solving inter-procedural call graphs or are specific and tied to particular analyses. We also argue that the design of an efficient fixpoint algorithm is pivotal to supporting the analysis of large programs. In this paper we introduce a novel algorithm for analysis of Java bytecode which includes a number of optimizations in order to reduce the number of iterations. The algorithm is parametric - in the sense that it is independent of the abstract domain used and it can be applied to different domains as "plug-ins"-, multivariant, and flow-sensitive. Also, is based on a program transformation, prior to the analysis, that results in a highly uniform representation of all the features in the language and therefore simplifies analysis. Detailed descriptions of decompilation solutions are given and discussed with an example. We also provide some performance data from a preliminary implementation of the analysis.
We present a simple algorithmic extension of the approximate call-strings approach to mitigate substantial performance degradation caused by spurious interprocedural cycles. Spurious interprocedural cycles are, in a r...
详细信息
We present a simple algorithmic extension of the approximate call-strings approach to mitigate substantial performance degradation caused by spurious interprocedural cycles. Spurious interprocedural cycles are, in a realistic setting, the key reasons for why approximate call-return semantics in both context-sensitive and -insensitive static analysis can make the analysis much slower than expected. In the approximate call-strings-based context-sensitive static analysis, because the number of distinguished contexts is finite, multiple call-contexts are inevitably joined at the entry of a procedure and the output at the exit is propagated to multiple return-sites. We found that these multiple returns frequently create a single large cycle (we call it 'butterfly cycle') covering almost all parts of the program and such a spurious cycle makes analyses very slow and inaccurate. Our simple algorithmic technique (within the fixpoint iteration algorithm) identifies and prunes these spurious interprocedural flows. The technique's effectiveness is proven by experiments with a realistic C analyzer to reduce the analysis time by 7-96%. As the technique is algorithmic, it can be easily applicable to existing analyses without changing the underlying abstract semantics, it is orthogonal to the underlying abstract semantics' context-sensitivity, and its correctness is obvious. Copyright (C) 2010 John Wiley & Sons, Ltd.
The synthesis of state feedback logic for the control problem of maintaining a predicate on the state set of a timed discrete event system is considered in the setting of controlled time Petri nets. We introduce a kin...
详细信息
ISBN:
(纸本)0780338332
The synthesis of state feedback logic for the control problem of maintaining a predicate on the state set of a timed discrete event system is considered in the setting of controlled time Petri nets. We introduce a kind of invariance for predicates and propose a fixpoint algorithm for computing the extremal invariant predicate. On the basis of this, maximally permissive state feedback logic can be characterized and systematically synthesized.
This paper presents an optimized general-purpose algorithm for polyvariant, static analyses of higher-order applicative programs. A polyvariant analysis is a very accurate form of analysis that produces many more abst...
详细信息
This paper presents an optimized general-purpose algorithm for polyvariant, static analyses of higher-order applicative programs. A polyvariant analysis is a very accurate form of analysis that produces many more abstract descriptions for a program than does a conventional analysis. It may also compute intermediate abstract descriptions that are irrelevant to the final result of the analysis. The optimized algorithm addresses this overhead while preserving the accuracy of the analysis. The algorithm is also parameterized over both the abstract domain and degree of polyvariance. We have implemented an instance of our algorithm and evaluated its performance compared to the unoptimized algorithm. Our implementation runs significantly faster on average than the other algorithm for benchmarks reported here.
Abstract interpretation of PROLOG programs has attracted many researchers in recent years, partly because of the potential for optimization in PROLOG compilers and partly because of the declarative nature of logic pro...
详细信息
Abstract interpretation of PROLOG programs has attracted many researchers in recent years, partly because of the potential for optimization in PROLOG compilers and partly because of the declarative nature of logic programming languages that make them more amenable to optimization than procedural languages. Most of the work, however, has remained at the theoretical level, focusing on the developments of frameworks and the definition of abstract domains. This paper reports our effort to verify experimentally the practical value of this area of research. It describes the design and implementation of the generic abstract interpretation algorithm GAIA that we originally proposed in Le Charlier et al. [1991], its instantiation to a sophisticated abstract domain (derived from Bruynooghe and Janssens [1988]) containing modes, types, sharing, and aliasing, and its evaluation both in terms of performance and accuracy. The overall implementation (over 5000 lines of Pascal) has been systematically analyzed on a variety of programs and compared with the complexity analysis of Le Charlier et al. [19911 and the specific analysis systems of Hickey and Mudambi [1989], Taylor [1989;1990], Van Roy and Despain [1990], and Warren et al. [1988].
The efficient implementation of generic abstract interpretation algorithms for Prolog is reconsidered after References 1 and 2. Two new optimization techniques are proposed and applied to the original algorithm of Ref...
详细信息
The efficient implementation of generic abstract interpretation algorithms for Prolog is reconsidered after References 1 and 2. Two new optimization techniques are proposed and applied to the original algorithm of Reference 1: dependency on clause prefixes and caching of operations. The first improvement avoids re-evaluating a clause prefix when no abstract value which it depends on has been updated. The second improvement consists of caching all operations on substitutions and reusing the results whenever possible. The algorithm and the two optimization techniques have been implemented in C (about 8000 lines of code each), tested on a large number of Prolog programs, and compared with the original implementation on an abstract domain containing modes, types and sharing. In conjunction with refinements of the domain algorithms, they produce an average reduction of more than 58 per cent in computation time. Extensive experimental results on the programs are given, including computation times, memory consumption, hit ratios for the caches, the number of operations performed, and the time distribution. As a main result, the improved algorithms exhibit the same efficiency as the specific tools of References 3 and 4, despite the fact that our abstract domain is more sophisticated and accurate. The abstract operations also take 90 per cent of the computation time, indicating that the overhead of the control is very limited. Results on a simpler domain are also given and show that even extremely basic domains can benefit from the optimizations. The general-purpose character of the optimizations is also discussed.
暂无评论