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

Bigdataflow: A Distributed interprocedural dataflow analysis Framework 2023

BigDataflow: A Distributed Interprocedural Dataflow Analysis...

31st ACM Joint Meeting of the European Software Engineering Conference / Symposium on the Foundations-of-Software-Engineering (ESEC/FSE)

作者： Sun, Zewen Xu, Duanchen Zhang, Yiyu Qi, Yun Wang, Yueyang Zuo, Zhiqiang Wang, Zhaokang Li, Yue Li, Xuandong Lu, Qingda Peng, Wenwen Guo, Shengjian Nanjing Univ Nanjing Peoples R China Alibaba Grp Sunnyvale CA USA Baidu Res Sunnyvale CA USA Nanjing Univ State Key Lab Novel Software Technol Nanjing Peoples R China

ISBN: (纸本)9798400703270

Apart from forming the backbone of compiler optimization, static dataflow analysis has been widely applied in a vast variety of applications, such as bug detection, privacy analysis, program comprehension, etc. Despite its importance, performing interprocedural dataflow analysis on large-scale programs is well known to be challenging. In this paper, we propose a novel distributed analysis framework supporting the general interprocedural dataflow analysis. Inspired by large-scale graph processing, we devise a dedicated distributed worklist algorithm tailored for interprocedural dataflow analysis. We implement the algorithm and develop a distributed framework called Bigdataflow running on a large-scale cluster. The experimental results validate the promising performance of Bigdataflow - it can finish analyzing the program of millions lines of code in minutes. Compared with the state-of-the-art, Bigdataflow achieves much more analysis efficiency.

关键词： interprocedural dataflow analysis distributed computing

来源：评论

学校读者我要写书评

暂无评论

Detecting interprocedural Infeasible Paths via Symbolic Propagation and dataflow analysis 10

Detecting Interprocedural Infeasible Paths via Symbolic Prop...

引用

10th IEEE International Conference on Software Engineering and Service Science (ICSESS)

作者： Gong, Huiquan Zhang, Yuwei Xing, Ying Jia, Wei Beijing Univ Technol Beijing Peoples R China Beijing Univ Posts & Telecommun Beijing Peoples R China

ISBN: (纸本)9781728109459

Experimental evidence indicates that a majority of paths generated by static analysis tools are found to be infeasible. As structural testing is an integral part of many software testing activities, detecting infeasible paths at an early phase can greatly improve the efficiency of many structural testing techniques. Since existing approaches commonly handle infeasible paths from the function units, a novel approach is proposed in this paper to detect infeasible paths interprocedurally. We use a map data structure, called interprocedural symbolic-propagation mapping, to model the value-passing process at each call site along the generated interprocedural paths, and then a hybrid method is utilized to determine the feasibility of each given path on the fly, which combines interprocedural dataflow analysis with the symbolic propagation technique without applying constraint solvers. Experimental results prove the effectiveness of the proposed approach.

关键词： static analysis interprocedural dataflow analysis symbolic propagation infeasible path detection

来源：评论

学校读者我要写书评

暂无评论

Generating Abstract Graph-Based Procedure Summaries for Pointer Programs

Generating Abstract Graph-Based Procedure Summaries for Poin...

引用

7th International Conference on Graph Transformation (ICGT) Held as Part of Conference on Software Technologies - Applications and Foundations (STAF)

作者： Jansen, Christina Noll, Thomas Rhein Westfal TH Aachen Software Modeling & Verificat Grp Aachen Germany

ISBN: (纸本)9783319091082;9783319091075

The automated analysis and verification of pointer-manipulating programs operating on a heap is a challenging task. It requires abstraction techniques for dealing with complex program behaviour and unbounded state spaces that arise from both dynamic data structures and recursive procedures. In previous work it was shown that hyperedge replacement grammars provide an intuitive and versatile concept for defining and implementing such abstractions. Here we extend this approach towards a modular way of reasoning about programs with (possibly recursive) procedures featuring local variables. We propose an interprocedural dataflow analysis to automatically derive procedure contracts, i.e., graph transformations that concisely capture the overall effect of a procedure. Besides its modularity, another advantage of this analysis is that it relieves us from explicitly modelling the call stack on the heap, i.e., heap and control abstraction are clearly separated. The former can now be specified by simple and intuitive hyperedge replacement grammars describing the data structures only, while the latter is realised by automatically generated procedure contracts.

关键词： Hypergraphs Hyperedge Replacement Grammars Heap Abstraction Procedure Contracts interprocedural dataflow analysis

来源：评论

学校读者我要写书评

暂无评论

A Relational Approach to interprocedural Shape analysis

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2010年第2期32卷 5-5:52页

作者： Jeannet, Bertrand Loginov, Alexey Reps, Thomas Sagiv, Mooly INRIA Sophia Antipolis France Univ Wisconsin Dept Comp Sci Madison WI 53706 USA Tel Aviv Univ Sch Comp Sci Tel Aviv Israel

This article addresses the verification of properties of imperative programs with recursive procedure calls, heap-allocated storage, and destructive updating of pointer-valued fields, that is, interprocedural shape analysis. The article makes three contributions. -It introduces a new method for abstracting relations over memory configurations for use in abstract interpretation. -It shows how this method furnishes the elements needed for a compositional approach to shape analysis. In particular, abstracted relations are used to represent the shape transformation performed by a sequence of operations, and an overapproximation to relational composition can be performed using the meet operation of the domain of abstracted relations. -It applies these ideas in a new algorithm for context-sensitive interprocedural shape analysis. The algorithm creates procedure summaries using abstracted relations over memory configurations, and the meet-based composition operation provides a way to apply the summary transformer for a procedure P at each call site from which P is called. The algorithm has been applied successfully to establish properties of both (i) recursive programs that manipulate lists and (ii) recursive programs that manipulate binary trees.

关键词： Algorithms Languages Theory Verification Abstract interpretation context-sensitive analysis interprocedural dataflow analysis destructive updating pointer analysis shape analysis static analysis 3-valued logic

来源：评论

学校读者我要写书评

暂无评论

WYSINWYX: What You See Is Not What You eXecute

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2010年第6期32卷 23-23:84页

作者： Balakrishnan, Gogul Reps, Thomas NEC Labs Amer Inc Princeton NJ 08540 USA Univ Wisconsin Dept Comp Sci Madison WI 53703 USA GrammaTech Inc Ithaca NY 14850 USA

Over the last seven years, we have developed static-analysis methods to recover a good approximation to the variables and dynamically allocated memory objects of a stripped executable, and to track the flow of values through them. The article presents the algorithms that we developed, explains how they are used to recover Intermediate Representations (IRs) from executables that are similar to the IRs that would be available if one started from source code, and describes their application in the context of program understanding and automated bug hunting. Unlike algorithms for analyzing executables that existed prior to our work, the ones presented in this article provide useful information about memory accesses, even in the absence of debugging information. The ideas described in the article are incorporated in a tool for analyzing Intel x86 executables, called CodeSurfer/x86. CodeSurfer/x86 builds a system dependence graph for the program, and provides a GUI for exploring the graph by (i) navigating its edges, and (ii) invoking operations, such as forward slicing, backward slicing, and chopping, to discover how parts of the program can impact other parts. To assess the usefulness of the IRs recovered by CodeSurfer/x86 in the context of automated bug hunting, we built a tool on top of CodeSurfer/x86, called Device-Driver Analyzer for x86 (DDA/x86), which analyzes device-driver executables for bugs. Without the benefit of either source code or symbol-table/debugging information, DDA/x86 was able to find known bugs (that had been discovered previously by source-code analysis tools), along with useful error traces, while having a low false-positive rate. DDA/x86 is the first known application of program analysis/verification techniques to industrial executables.

关键词： Algorithms Security Theory Verification Abstract interpretation context-sensitive analysis data structure recovery interprocedural dataflow analysis pointer analysis reverse engineering static analysis

来源：评论

学校读者我要写书评

暂无评论

Weighted pushdown systems and their application to interprocedural dataflow analysis

引用

SCIENCE OF COMPUTER PROGRAMMING 2005年第1-2期58卷 206-263页

作者： Reps, T Schwoon, S Jha, S Melski, D Univ Wisconsin Comp Sci Dept Madison WI 53706 USA Univ Stuttgart Inst Formale Methoden Informat Stuttgart Germany

Recently, pushdown systems (PDSs) have been extended to weighted PDSs, in which each transition is labeled with a value, and the goal is to determine the meet-over-all-paths value (for paths that meet a certain criterion). This paper shows how weighted PDSs yield new algorithms for certain classes of interprocedural dataflow-analysis problems. (c) 2005 Elsevier B.V. All rights reserved.

关键词： interprocedural dataflow analysis generalized pushdown reachability meet-over-all-paths problem weighted pushdown system

来源：评论

学校读者我要写书评

暂无评论

Weighted pushdown systems and their application to interprocedural dataflow analysis

Weighted pushdown systems and their application to interproc...

引用

10th International Static analysis Symposium (SAS 2003)

作者： Reps, T Schwoon, S Jha, S Melski, D Univ Wisconsin Comp Sci Dept Madison WI 53706 USA Univ Stuttgart Inst Formale Methoden Informat Stuttgart Germany

关键词： interprocedural dataflow analysis generalized pushdown reachability meet-over-all-paths problem weighted pushdown system

来源：评论

学校读者我要写书评

暂无评论

Error Propagation analysis for File Systems 09

Error Propagation Analysis for File Systems

引用

ACM SIGPLAN Conference on Programming Language Design and Implementation

作者： Rubio-Gonzalez, Cindy Gunawi, Haryadi S. Liblit, Ben Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, Andrea C. Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

ISBN: (纸本)9781605583921

Unchecked errors are especially pernicious in operating system file management code. Transient or permanent hardware failures are inevitable, and error-management bugs at the file system layer can cause silent, unrecoverable data corruption. We propose an interprocedural static analysis that tracks errors as they propagate through file system code. Our implementation detects overwritten, out-of-scope, and unsaved unchecked errors. analysis of four widely-used Linux file system implementations (CIFS, ext3, IBM JFS and ReiserFS), a relatively new file system implementation (ext4), and shared virtual file system (VFS) code uncovers 312 error propagation bugs. Our flow-and context-sensitive approach produces more precise results than related techniques while providing better diagnostic information, including possible execution paths that demonstrate each bug found.

关键词： Algorithms Languages Reliability Verification static program analysis interprocedural dataflow analysis weighted pushdown systems copy constant propagation binary decision diagrams

来源：评论

学校读者我要写书评

暂无评论

Summarizing procedures in concurrent programs 04

Summarizing procedures in concurrent programs

引用

31st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

作者： Qadeer, S Rajamani, SK Rehof, J Microsoft Res Redmond WA 98052 USA

ISBN: (纸本)9781581137293

The ability to summarize procedures is fundamental to building scalable interprocedural analyses. For sequential programs, procedure summarization is well-understood and used routinely in a variety of compiler optimizations and software defect-detection tools. However, the benefit of summarization is not available to multithreaded programs, for which a clear notion of summaries has so far remained unarticulated in the research literature. In this paper, we present an intuitive and novel notion of procedure summaries for multithreaded programs. We also present a model checking algorithm for these programs that uses procedure summarization as an essential component. Our algorithm can also be viewed as a precise interprocedural dataflow analysis for multithreaded programs. Our method for procedure summarization is based on the insight that in well-synchronized programs, any computation of a thread can be viewed as a sequence of transactions, each of which appears to execute atomically to other threads. We summarize within each transaction;the summary of a procedure comprises the summaries of all transactions within the procedure. We leverage the theory of reduction [17] to infer boundaries of these transactions. The procedure summaries computed by our algorithm allow reuse of analysis results across different call sites in a multithreaded program, a benefit that has hitherto been available only to sequential programs. Although our algorithm is not guaranteed to terminate on multithreaded programs that use recursion (reachability analysis for multithreaded programs with recursive procedures is undecidable [181), there is a large class of programs for which our algorithm does terminate. We give a formal characterization of this class, which includes programs that use shared variables, synchronization, and recursion.

关键词： concurrent programs pushdown systems model checking interprocedural dataflow analysis procedure summaries transactions reduction

来源：评论

学校读者我要写书评

暂无评论

An automata-theoretic approach to interprocedural data-flow analysis 2

引用

2nd International Conference on Foundations of Software Science and Computation Structures (FOSSACS99) Held as Part of the Joint European Conference on Theory and Practice of Software

作者： Esparza, J Knoop, J Tech Univ Munich D-80290 Munich Germany Univ Dortmund D-44221 Dortmund Germany

We show that recent progress in extending the automatatheoretic approach to model-checking beyond the class of finite-state processes finds a natural application in the area of interprocedural dataflow analysis.

ISBN: (纸本)3540657193

关键词： interprocedural dataflow analysis model-checking automata theory program optimisation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：