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

The Bounded Pathwidth of control-flow graphs

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2023年第OOPSLA期7卷 292–317页

作者： Conrado, Giovanna Kobus Goharshady, Amir Kafshdar Lam, Chun Kit Hong Kong Univ Sci & Technol Dept Math Dept Comp Sci & Engn Clear Water Bay Hong Kong Peoples R China

Pathwidth and treewidth are standard and well-studied graph sparsity parameters which intuitively model the degree to which a given graph resembles a path or a tree, respectively. It is well-known that the control-flow graphs of structured goto-free programs have a tree-like shape and bounded treewidth. This fact has been exploited to design considerably more efficient algorithms for a wide variety of static analysis and compiler optimization problems, such as register allocation, mu-calculus model-checking and parity games, data-flow analysis, cache management, and liftetime-optimal redundancy elimination. However, there is no bound in the literature for the pathwidth of programs, except the general inequality that the pathwidth of a graph is at most O (lg n) times its treewidth, where n is the number of vertices of the graph. In this work, we prove that control-flow graphs of structured programs have bounded pathwidth and provide a linear-time algorithm to obtain a path decomposition of small width. Specifically, we establish a bound of 2 center dot d on the pathwidth of programs with nesting depth d. Since real-world programs have small nesting depth, they also have bounded pathwidth. This is significant for a number of reasons: (i) pathwidth is a strictly stronger parameter than treewidth, i.e. any graph family with bounded pathwidth has bounded treewidth, but the converse does not hold;(ii) any algorithm that is designed with treewidth in mind can be applied to bounded-pathwidth graphs with no change;(iii) there are problems that are fixed-parameter tractable with respect to pathwidth but not treewidth;(iv) verification algorithms that are designed based on treewidth would become significantly faster when using pathwidth as the parameter;and (v) it is easier to design algorithms based on bounded pathwidth since one does not have to consider the often-challenging case of merge nodes in treewidth-based dynamic programming. Thus, we invite the static analysis and

关键词： control-flow graphs Parameterized Algorithms Pathwidth Treewidth

来源：评论

学校读者我要写书评

暂无评论

Annotating control-flow graphs for Formalized Test Coverage Criteria

Annotating Control-Flow Graphs for Formalized Test Coverage ...

引用

17th IEEE International Conference on Software Testing, Verification, and Validation (ICST)

作者： Kauffman, Sean Moreno, Carlos Fischmeister, Sebastian Queens Univ Elect & Comp Engn Kingston ON Canada

ISBN: (纸本)9798350344806;9798350344790

control flow coverage criteria are an important part of the process of qualifying embedded software for safety-critical systems. Criteria such as modified condition/decision coverage (MC/DC) as defined by DO-178B are used by regulators to judge the adequacy of testing and by QA engineers to design tests when full path coverage is impossible. Despite their importance, these coverage criteria are often misunderstood. One problem is that their definitions are typically written in natural language specification documents, making them imprecise. Other works have proposed formal definitions using binary predicate logic, but these definitions are difficult to apply to the analysis of real programs. control-flow graphs (CFGs) are the most common model for analyzing program logic in compilers, and seem to be a good fit for defining and analyzing coverage criteria. However, CFGs discard the explicit concept of a decision, making their use for this task seem impossible. In this paper, we show how to annotate a CFG with decision information inferred from the graph itself. We call this annotated model a control-flow Decision Graph (CFDG) and we use it to formally define several common coverage criteria. We have implemented our algorithms in a tool which we show can be applied to automatically annotate CFGs output from popular compilers.

关键词： control-flow graphs Formalized Coverage Criteria Program Visualization

来源：评论

学校读者我要写书评

暂无评论

From source code to runtime behaviour: Software metrics help to select the computer architecture

引用

KNOWLEDGE-BASED SYSTEMS 2010年第4期23卷 343-349页

作者： Eichinger, Frank Kramer, David Boehm, Klemens Karl, Wolfgang KIT Inst Programme Struct & Data Org IPD D-76128 Karlsruhe Germany KIT Inst Comp Sci & Engn ITEC D-76128 Karlsruhe Germany

The decision which hardware platform to use for a certain application is an important problem in computer architecture This paper reports on a study where a data-mining approach is used for this decision It relies purely on source-code characteristics, to avoid potentially expensive programme executions. One challenge in this context is that one cannot infer how often functions that are part of the application are typically executed The main Insight of this study is twofold. (a) Source-code characteristics are sufficient nevertheless (b) Linking individual functions with the runtime behaviour of the programme as a whole yields good predictions In other words, while individual data objects from the training set may be quite inaccurate, the resulting model is not (C) 2009 Elsevier B V All rights reserved

关键词： Computer architecture Data mining Performance prediction Source-code metrics control-flow graphs

来源：评论

学校读者我要写书评

暂无评论

Permissive runtime information flow control in the presence of exceptions

引用

JOURNAL OF COMPUTER SECURITY 2021年第4期29卷 361-401页

作者： Bichhawat, Abhishek Rajani, Vineet Garg, Deepak Hammer, Christian IIT Gandhinagar Gandhinagar India Max Planck Inst Secur & Privacy Bochum Germany Max Planck Inst Software Syst Saarland Informat Campus Saarbrucken Germany Univ Potsdam Potsdam Germany Saarland Univ Saarbrucken Germany

Information flow control (IFC) has been extensively studied as an approach to mitigate information leaks in applications. A vast majority of existing work in this area is based on static analysis. However, some applications, especially on the Web, are developed using dynamic languages like JavaScript where static analyses for IFC do not scale well. As a result, there has been a growing interest in recent years to develop dynamic or runtime information flow analysis techniques. In spite of the advances in the field, runtime information flow analysis has not been at the helm of information flow security, one of the reasons being that the analysis techniques and the security property related to them (non-interference) over-approximate information flows (particularly implicit flows), generating many false positives. In this paper, we present a sound and precise approach for handling implicit leaks at runtime. In particular, we present an improvement and enhancement of the so-called permissive-upgrade strategy, which is widely used to tackle implicit leaks in dynamic information flow control. We improve the strategy's permissiveness and generalize it. Building on top of it, we present an approach to handle implicit leaks when dealing with complex features like unstructured control flow and exceptions in higher-order languages. We explain how we address the challenge of handling unstructured control flow using immediate post-dominator analysis. We prove that our approach is sound and precise.

关键词： Runtime information flow control permissive-upgrade control-flow graphs immediate post-dominator analysis exceptions

来源：评论

学校读者我要写书评

暂无评论

Learning Semantic Program Embeddings with Graph Interval Neural Network

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2020年第OOPSLA期4卷 1–27页

作者： Wang, Yu Wang, Ke Gao, Fengjuan Wang, Linzhang Nanjing Univ Dept Comp Sci & Technol State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Visa Res Secur Cryptog & Blockchain Palo Alto CA USA

Learning distributed representations of source code has been a challenging task for machine learning models. Earlier works treated programs as text so that natural language methods can be readily applied. Unfortunately, such approaches do not capitalize on the rich structural information possessed by source code. Of late, Graph Neural Network (GNN) was proposed to learn embeddings of programs from their graph representations. Due to the homogeneous (i.e. do not take advantage of the program-specific graph characteristics) and expensive (i.e. require heavy information exchange among nodes in the graph) message-passing procedure, GNN can suffer from precision issues, especially when dealing with programs rendered into large graphs. In this paper, we present a new graph neural architecture, called Graph Interval Neural Network (GINN), to tackle the weaknesses of the existing GNN. Unlike the standard GNN, GINN generalizes from a curated graph representation obtained through an abstraction method designed to aid models to learn. In particular, GINN focuses exclusively on intervals (generally manifested in looping construct) for mining the feature representation of a program, furthermore, GINN operates on a hierarchy of intervals for scaling the learning to large graphs. We evaluate GINN for two popular downstream applications: variable misuse prediction and method name prediction. Results show in both cases GINN outperforms the state-of-the-art models by a comfortable margin. We have also created a neural bug detector based on GINN to catch null pointer deference bugs in Java code. While learning from the same 9,000 methods extracted from 64 projects, GINN-based bug detector significantly outperforms GNN-based bug detector on 13 unseen test projects. Next, we deploy our trained GINN-based bug detector and Facebook Infer, arguably the state-of-the-art static analysis tool, to scan the codebase of 20 highly starred projects on GitHub. Through our manual inspection, we conf

关键词： Program embeddings control-flow graphs Intervals Graph neural networks Null pointer dereference detection

来源：评论

学校读者我要写书评

暂无评论

Automatic Extraction of Process control flow from I/O Operations

引用

6th International Conference on Business Process Management

作者： Diniz, Pedro C. Ferreira, Diogo R. Univ Lisbon IST INESC ID Lisbon Portugal Univ Lisbon IST/INOV Tech Lisbon Portugal

ISBN: (纸本)9783540857570

Many end users will expect the output of process mining to be a model they can easily understand. On the other hand, knowing which objects were accessed in each operation can be a valuable input for process discovery. From these two trends it is possible to establish an analogy between process mining and the discovery of program structure. In this paper we present an approach for extracting process control-flow from a trace of read and write operations over a set of objects. The approach is divided in two independent phases. In the first phase, Fourier analysis is used to identify periodic behavior that can be represented with loop constructs. In the second phase, a match-and-merge technique is used to produce a control-flow graph capable of generating the input trace and thus representing the process that generated it. The combination of these techniques provides a structured and compact representation of the unknown process, with very good results in terms of conformance metrics.

关键词： Process mining control-flow graphs Fourier analysis

来源：评论

学校读者我要写书评

暂无评论

From source code to runtime behaviour: Software metrics help to select the computer architecture

引用

29th SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence

作者： Eichinger, Frank Kramer, David Boehm, Klemens Karl, Wolfgang KIT Inst Programme Struct & Data Org IPD D-76128 Karlsruhe Germany KIT Inst Comp Sci & Engn ITEC D-76128 Karlsruhe Germany

ISBN: (纸本)9781848829824

关键词： Computer architecture Data mining Performance prediction Source-code metrics control-flow graphs

来源：评论

学校读者我要写书评

暂无评论

Infeasible Paths Elimination by Symbolic Execution Techniques Proof of Correctness and Preservation of Paths 7th

Infeasible Paths Elimination by Symbolic Execution Technique...

引用

7th International Conference on Interactive Theorem Proving (ITP)

作者： Aissat, Romain Voisin, Frederic Wolff, Burkhart Univ Paris Saclay LRI Univ Paris Sud CNRSCent Supelec Orsay France

ISBN: (纸本)9783319431444

TRACER [8] is a tool for verifying safety properties of sequential C programs. TRACER attempts at building a finite symbolic execution graph which over-approximates the set of all concrete reachable states and the set of feasible paths. We present an abstract framework for TRACER and similar CEGAR-like systems [2,3,5,6,9]. The framework provides (1) a graph-transformation based method for reducing the feasible paths in control-flow graphs, (2) a model for symbolic execution, subsumption, predicate abstraction and invariant generation. In this framework we formally prove two key properties: correct construction of the symbolic states and preservation of feasible paths. The framework focuses on core operations, leaving to concrete prototypes to "fit in" heuristics for combining them.

关键词： TRACER CEGAR Symbolic execution Feasible paths control-flow graphs Graph transformation

来源：评论

学校读者我要写书评

暂无评论

CFG Construction Soundness in control-flow Integrity 12

CFG Construction Soundness in Control-Flow Integrity

引用

12th ACM SIGSAC Workshop on Programming Languages and Analysis for Security (PLAS)

作者： Tan, Gang Jaeger, Trent Penn State Univ University Pk PA 16802 USA

ISBN: (纸本)9781450350990

control-flow Integrity (CFI) is an intensively studied technique for hardening software security. It enforces a control-flow Graph (CFG) by inlining runtime checks into target programs. Many methods have been proposed to construct the enforced CFG, with different degrees of precision and sets of assumptions. However, past CFI work has not made attempt at justifying their CFG construction soundness using formal semantics and proofs. In this paper, we formalize the CFG construction in two major CFI systems, identify their assumptions, and prove their soundness;the soundness proof shows that their computed sets of targets for indirect calls are safe over-approximations.

关键词： control-flow integrity control-flow graphs type systems type soundness

来源：评论

学校读者我要写书评

暂无评论

An Applicative control-flow Graph Based on Huet's Zipper

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2006年第2期148卷 105-126页

作者： Ramsey, Norman Dias, Joao Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

We are using ML to build a compiler that does low-level optimization. To support optimizations in classic imperative style, we built a control-flow graph using mutable pointers and other mutable state in the nodes. This decision proved unfortunate: the mutable flow graph was big and complex, and it led to many bugs. We have replaced it by a smaller, simpler, applicative flow graph based on Huet's [6] zipper. The new flow graph is a success;this paper presents its design and shows how it leads to a gratifyingly simple implementation of the dataflow framework developed by [10].

关键词： compilers control-flow graphs applicative data structures dataflow analysis optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：