检索结果-内蒙古大学图书馆

An Efficient, Parametric fixpoint algorithm for Analysis of Java Bytecode

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2007年第1期190卷 51-66页

作者： Mendez, Mario Navas, Jorge Hermenegildo, Manuel V. Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA Tech Univ Madrid Madrid Spain

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.

关键词： fixpoint algorithm multivariance static analysis Java bytecode abstract interpretation

来源：评论

学校读者我要写书评

暂无评论

Combinator-Based fixpoint algorithms for Big-Step Abstract Interpreters

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2023年第ICFP期7卷 955–981页

作者： Keidel, Sven Erdweg, Sebastian Hombuecher, Tobias Tech Univ Darmstadt Darmstadt Germany JGU Mainz Mainz Germany

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.

关键词： Big-Step Abstract Interpretation Static Analysis fixpoint algorithm

来源：评论

学校读者我要写书评

暂无评论

GENERIC ABSTRACT INTERPRETATION algorithmS FOR PROLOG - 2 OPTIMIZATION TECHNIQUES AND THEIR EXPERIMENTAL EVALUATION

引用

SOFTWARE-PRACTICE & EXPERIENCE 1993年第4期23卷 419-459页

作者： ENGLEBERT, V LECHARLIER, B ROLAND, D VANHENTENRYCK, P BROWN UNIV BOX 1910PROVIDENCERI 02912 UNIV NAMUR B-5000 NAMURBELGIUM

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.

关键词： ABSTRACT INTERPRETATION PROLOG fixpoint algorithm EXPERIMENTATION LANGUAGES PERFORMANCE

来源：评论

学校读者我要写书评

暂无评论

An algorithmic mitigation of large spurious interprocedural cycles in static analysis

引用

SOFTWARE-PRACTICE & EXPERIENCE 2010年第8期40卷 585-603页

作者： Oh, Hakjoo Yi, Kwangkeun Seoul Natl Univ Sch Comp Sci & Engn Programming Res Lab Seoul 151742 South Korea

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.

关键词： static analysis interprocedural analysis abstract interpretation spurious cycles fixpoint algorithm

来源：评论

学校读者我要写书评

暂无评论

fixpoint COMPUTATION FOR POLYVARIANT STATIC ANALYSES OF HIGHER-ORDER APPLICATIVE PROGRAMS

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1994年第5期16卷 1431-1448页

作者： ASHLEY, JM CONSEL, C OREGON GRAD INST DEPT COMP SCIPORTLANDOR 97291

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 fixpoint algorithm PROGRAM ANALYSIS

来源：评论

学校读者我要写书评

暂无评论

Incrementalizing Graph algorithms 21

Incrementalizing Graph Algorithms

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Fan, Wenfei Tian, Chao Xu, Ruiqi Yin, Qiang Yu, Wenyuan Zhou, Jingren Univ Edinburgh Edinburgh Midlothian Scotland Shenzhen Inst Comp Sci Shenzhen Peoples R China Alibaba Grp Hangzhou Peoples R China

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.

关键词： incrementalization boundedness fixpoint algorithm

来源：评论

学校读者我要写书评

暂无评论

The Top-Down Solver Verified: Building Confidence in Static Analyzers 36th

The Top-Down Solver Verified: Building Confidence in Static ...

引用

36th International Conference on Computer-Aided Verification (CAV)

作者： Stade, Yannick Tilscher, Sarah Seidl, Helmut Tech Univ Munich TUM Sch Computat Informat & Technol Munich Germany Ludwig Maximilians Univ Munchen Dept Comp Sci Munich Germany

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.

关键词： fixpoint algorithm correctness proof static analysis

来源：评论

学校读者我要写书评

暂无评论

Maximally permissive state feedback logic for controlled time Petri nets

Maximally permissive state feedback logic for controlled tim...

引用

1997 American Control Conference

作者： Chen, HX Li, HF Systems Engineering Institute Xi'an Jiaotong University Xi'an China

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.

关键词： state feedback Petri nets invariance discrete event systems control system synthesis maximally permissive state feedback logic controlled time Petri nets timed discrete event system invariance fixpoint algorithm extremal invariant predicate

来源：评论

学校读者我要写书评

暂无评论

EXPERIMENTAL EVALUATION OF A GENERIC ABSTRACT INTERPRETATION algorithm FOR PROLOG

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1994年第1期16卷 35-101页

作者： LECHARLIER, B VANHENTENRYCK, P BROWN UNIV DEPT COMP SCIPROVIDENCERI 02912

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].

关键词： ABSTRACT INTERPRETATION fixpoint algorithm PROLOG

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：