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

Towards Trustworthy Automated Program Verifiers: Formally Validating Translations into an Intermediate Verification language

引用

proceedings OF THE acm ON programming languageS-PacmPL 2024年第PLDI期8卷 1510-1534页

作者： Parthasarathy, Gaurav Dardinier, Thibault Bonneau, Benjamin Muller, Peter Summers, Alexander J. Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Univ Grenoble Alpes CNRS Grenoble INP VERIMAG Grenoble France Univ British Columbia Vancouver BC Canada

Automated program verifiers are typically implemented using an intermediate verification language (IVL), such as Boogie or Why3. A verifier front-end translates the input program and specification into an IVL program, while the back-end generates proof obligations for the IVL program and employs an SMT solver to discharge them. Soundness of such verifiers therefore requires that the front-end translation faithfully captures the semantics of the input program and specification in the IVL program, and that the back-end reports success only if the IVL program is actually correct. For a verification tool to be trustworthy, these soundness conditions must be satisfied by its actual implementation, not just the program logic it uses. In this paper, we present a novel validation methodology that, given a formal semantics for the input language and IVL, provides formal soundness guarantees for front-end implementations. For each run of the verifier, we automatically generate a proof in Isabelle showing that the correctness of the produced IVL program implies the correctness of the input program. This proof can be checked independently from the verifier, in Isabelle, and can be combined with existing work on validating back-ends to obtain an end-to-end soundness result. Our methodology based on forward simulation employs several modularisation strategies to handle the large semantic gap between the input language and the IVL, as well as the intricacies of practical, optimised translations. We present our methodology for the widely-used Viper and Boogie languages. Our evaluation shows that it is effective in validating the translations performed by the existing Viper implementation.

关键词： Software Verification Intermediate Verification languages Formal Semantics Proof Certification

来源：评论

学校读者我要写书评

暂无评论

A Principled Approach to REPL Interpreters

A Principled Approach to REPL Interpreters

引用

acm sigplan International Symposium on New Ideas, New Paradigms, and Reflections on programming and Software (Onward) Part of part of SPLASH conference

作者： van Binsbergen, L. Thomas Merino, Mauricio Verano Jeanjean, Pierre van der Storm, Tijs Combemale, Benoit Barais, Olivier Ctr Wiskunde & Informat Amsterdam Netherlands Eindhoven Univ Technol Eindhoven Netherlands Univ Rennes INRIA CRNS IRISA Rennes France Univ Groningen Groningen Netherlands

ISBN: (纸本)9781450381789

Read-eval-print-loops (REPLs) allow programmers to test out snippets of code, explore APIs, or even incrementally construct code, and get immediate feedback on their actions. However, even though many languages provide a REPL, the relation between the language as is and what is accepted at the REPL prompt is not always well-defined. Furthermore, implementing a REPL for new languages, such as DSLs, may incur significant language engineering cost. In this paper we survey the domain of REPLs and investigate the (formal) principles underlying REPLs. We identify and define the class of sequential languages, which admit a sound REPL implementation based on a definitional interpreter, and present design guidelines for extending existing language implementations to support REPL-style interfaces (including computational notebooks). The obtained REPLs can then be generically turned into an exploring interpreter, to allow exploration of the user's interaction. The approach is illustrated using three case studies, based on MiniJava, QL (a DSL for questionnaires), and eFLINT (a DSL for normative rules). We expect sequential languages, and the consequent design principles, to be stepping stones towards a better understanding of the essence of REPLs.

关键词： interpreters REPLs software language engineering notebooks meta-languages language workbenches

来源：评论

学校读者我要写书评

暂无评论

Acute: High-level programming language design for distributed computation 05

Acute: High-level programming language design for distribute...

引用

10th acm sigplan International conference on Functional programming (ICFP)

作者： Sewell, Peter Leifer, James J. Wansbrough, Keith Nardelli, Francesco Zappa Allen-Williams, Mair Habouzit, Pierre Vafeiadis, Viktor Univ Cambridge Cambridge England INRIA Rocquencourt Le Chesnay France

ISBN: (纸本)9781595930644

Existing languages provide good support for typeful programming of stand-alone programs. In a distributed system, however, there may be interaction between multiple instances of many distinct programs, sharing some (but not necessarily all) of their module structure, and with some instances rebuilt with new versions of certain modules as time goes on. In this paper, we discuss programming-language support for such systems, focussing on their typing and naming issues. We describe an experimental language, Acute, which extends an ML core to support distributed development, deployment, and execution, allowing type-safe interaction between separately built programs. The main features are (1) type-safe marshalling of arbitrary values;(2) type names that are generated (freshly and by hashing) to ensure that type equality tests suffice to protect the invariants of abstract types, across the entire distributed system;(3) expression-level names generated to ensure that name equality tests suffice for type safety of associated values, for example, values carried on named channels;(4) controlled dynamic rebinding of marshalled values to local resources;and (5) thunkification of threads and mutexes to support computation mobility. These features are a large part of what is needed for typeful distributed programming. They are a relatively lightweight extension of ML, should be efficiently implementable, and are expressive enough to enable a wide variety of distributed infrastructure layers to be written as simple library code above the byte-string network and persistent store APIs. This disentangles the language run-time from communication intricacies. This paper highlights the main design choices in Acute. It is supported by a full language definition (of typing, compilation, and operational semantics), by a prototype implementation, and by example distribution libraries.

关键词： modules distributed programming programming languages marshalling version control serialisation ML abstract types type theory rebinding

来源：评论

学校读者我要写书评

暂无评论

Slicing Probabilistic Programs 14

Slicing Probabilistic Programs

引用

35th acm sigplan conference on programming language design and implementation (PLDI)

作者： Hur, Chung-Kil Nori, Aditya V. Rajamani, Sriram K. Samuel, Selva Seoul Natl Univ Seoul 151 South Korea

ISBN: (纸本)9781450327848

Probabilistic programs use familiar notation of programming languages to specify probabilistic models. Suppose we are interested in estimating the distribution of the return expression r of a probabilistic program P. We are interested in slicing the probabilistic program P and obtaining a simpler program SLI (P) which retains only those parts of P that are relevant to estimating r, and elides those parts of P that are not relevant to estimating r. We desire that the SLI transformation be both correct and efficient. By correct, we mean that P and SLI (P) have identical estimates on r. By efficient, we mean that estimation over SLI (P) be as fast as possible. We show that the usual notion of program slicing, which traverses control and data dependencies backward from the return expression r, is unsatisfactory for probabilistic programs, since it produces incorrect slices on some programs and sub-optimal ones on others. Our key insight is that in addition to the usual notions of control dependence and data dependence that are used to slice non-probabilistic programs, a new kind of dependence called observe dependence arises naturally due to observe statements in probabilistic programs. We propose a new definition of SLI (P) which is both correct and efficient for probabilistic programs, by including observe dependence in addition to control and data dependences for computing slices. We prove correctness mathematically, and we demonstrate efficiency empirically. We show that by applying the SLI transformation as a pre-pass, we can improve the efficiency of probabilistic inference, not only in our own inference tool R2, but also in other systems for performing inference such as Church and Infer. NET.

关键词： Probabilistic programming Program Slicing Bayesian Reasoning

来源：评论

学校读者我要写书评

暂无评论

Modular Hardware design of Pipelined Circuits with Hazards

引用

proceedings OF THE acm ON programming languageS-PacmPL 2024年第PLDI期8卷 28-51页

作者： Jang, Minseong Rhee, Jungin Lee, Woojin Zhao, Shuangshuang Kang, Jeehoon Korea Adv Inst Sci & Technol Daejeon South Korea

Modular design is critical in reducing hardware designer's cognitive load and development cost. However, it is challenging to modularize high-performance pipelined circuits with structural, data, and control hazards because their resolution-stalling, and bypassing, and discard-and-restarting-introduce cross-stage dependencies. The dependencies could potentially mandate monolithic control logic and create combinational loops, hindering modular design. An effective method to modularize pipelined circuits is valid-ready interfaces, but they apply to a relatively simple form of pipelined circuits only with structural hazards. We propose hazard interfaces, a generalization of valid-ready interfaces that can modularize pipelined circuits not only with structural but also with data and control hazards. The key idea is enveloping the cross-stage dependencies within interfaces. We also design combinators for hazard interfaces in the style of map-reduce that facilitate decomposition of control logic. We implement a compiler (to synthesizable Verilog) for a prototype language supporting hazard interfaces and combinators, and design a sound and efficient type checker that proves the absence of combinational loops. With case studies on 5-stage RISC-V CPU core and 100 Gbps Ethernet NIC, we demonstrate that hazard interfaces indeed facilitate modular design while incurring no noticeable cost in performance, power, and area over reference designs in Chisel and Verilog.

关键词： hardware description language functional programming pipelining hazard combinator

来源：评论

学校读者我要写书评

暂无评论

Practical dynamic software updating for C 06

Practical dynamic software updating for C

引用

acm sigplan conference on programming language design and implementation, PLDI 2006 - PLAS 2006: 2006 programming languages and Analysis for Security Workshop

作者： Neamtiu, Iulian Hicks, Michael Stoyle, Gareth Oriol, Manuel University of Maryland United States University of Cambridge United Kingdom ETH Zurich Switzerland

ISBN: (纸本)1595933743

Software updates typically require stopping and restarting an application, but many systems cannot afford to halt service, or would prefer not to. Dynamic software updating (DSU) addresses this difficulty by permitting programs to be updated while they run. DSU is appealing compared to other approaches for on-line upgrades because it is quite general and requires no redundant hardware. The challenge is in making DSU practical: it should be flexible, and yet safe, efficient, and easy to *** this paper, we present Ginseng, a DSU implementation for C that aims to meet this challenge. We compile programs specially so that they can be dynamically patched, and generate most of a dynamic patch automatically. Ginseng performs a series of analyses that when combined with some simple runtime support ensure that an update will not violate type-safety while guaranteeing that data is kept up-to-date. We have used Ginseng to construct and dynamically apply patches to three substantial open-source server programs - -Very Secure FTP daemon, OpenSSH sshd daemon, and GNU Zebra. In total, we dynamically patched each program with three years' worth of releases. Though the programs changed substantially, the majority of updates were easy to generate. Performance experiments show that all patches could be applied in less than 5 ms, and that the overhead on application throughput due to updating support ranged from 0 to at most 32%. Copyright © 2006 acm.

关键词： C (programming language)

来源：评论

学校读者我要写书评

暂无评论

From Simulink to SCADE/Lustre to TTA: a layered approach for distributed embedded applications 03

From Simulink to SCADE/Lustre to TTA: a layered approach for...

引用

Association-for-Computing-Machinery sigplan conference on languages Compilers and Tools for Embedded Systems (LCTES 03)

作者： Caspi, P Curic, A Maignan, A Sofronis, C Tripakis, S Niebert, P VERIMAG Ctr Equat F-38610 Gieres France CMI Lab Informat Fondament F-13453 Marseille France

ISBN: (纸本)9781581136470

We present a layered end-to-end approach for the design and implementation of embedded software on a distributed platform. The approach comprises a high-level modeling and simulation layer (Simulink), a middle-level programming and validation layer (SCADE/Lustre) and a low-level execution layer (TTA). We provide algorithms and tools to pass from one layer to the next. First, a translator from Simulink to Lustre. Second, a set of real-time and code-distribution extensions to Lustre. Third, implementation techniques for decomposing a Lustre program into tasks and messages, scheduling the tasks and messages on the processors and the bus, distributing the Lustre code on the execution platform, and generating the necessary "glue" code.

关键词： design languages embedded software Simulink synchronous languages Lustre code distribution scheduling

来源：评论

学校读者我要写书评

暂无评论

Dynamic feedback: An effective technique for adapting computing

Dynamic feedback: An effective technique for adapting comput...

引用

proceedings of the 1997 acm SIGPLAM conference on programming language design and implementation, PLDI

作者： Diniz, Pedro Rinard, Martin Univ of California Santa Barbara Santa Barbara United States

This paper presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code;each version uses a different optimization policy. The generated code alternately performs sampling phases and production phases. Each sampling phase measures the overhead of each version in the current environment. Each production phase uses the version with the least overhead in the previous sampling phase. The computation periodically resamples to adjust dynamically to changes in the environment. We have implemented dynamic feedback in the context of a parallelizing compiler for object-based programs. The generated code uses dynamic feedback to automatically choose the best synchronization optimization policy. Our experimental results show that the synchronization optimization policy has a significant impact on the overall performance of the computation, that the best policy varies from program to program, that the compiler is unable to statically choose the best policy, and that dynamic feedback enables the generated code to exhibit performance that is comparable to that of code that has been manually tuned to use the best policy. We have also performed a theoretical analysis which provides, under certain assumptions, a guaranteed optimality bound for dynamic feedback relative to a hypothetical (and unrealizable) optimal algorithm that uses the best policy at every point during the execution.

关键词： Computer programming languages

来源：评论

学校读者我要写书评

暂无评论

MORBIG: A Static Parser for POSIX Shell 11

MORBIG: A Static Parser for POSIX Shell

引用

11th acm sigplan International conference on Software language Engineering (SLE) part of SPLASH conference

作者： Regis-Gianas, Yann Jeannerod, Nicolas Treinen, Ralf Univ Paris Diderot CNRS INRIA IRIFPI R2 Paris France Univ Paris Diderot CNRS IRIF Ecole Normale Super Paris France Univ Paris Diderot CNRS IRIF Paris France

ISBN: (纸本)9781450360296

The POSIX shell language defies conventional wisdom of compiler construction on several levels: The shell language was not designed for static parsing, but with an intertwining of syntactic analysis and execution by expansion in mind. Token recognition cannot be specified by regular expressions, lexical analysis depends on the parsing context and the evaluation context, and the shell grammar given in the specification is ambiguous. Besides, the unorthodox design choices of the shell language fit badly in the usual specification languages used to describe other programming languages. This makes the standard usage of LEX and YACC as a pipeline inadequate for the implementation of a parser for POSIX shell. The existing implementations of shell parsers are complex and use low-level character-level parsing code which is difficult to relate to the POSIX specification. We find it hard to trust such parsers, especially when using them for writing automatic verification tools for shell scripts. This paper offers an overview of the technical difficulties related to the syntactic analysis of the POSIX shell language. It also describes how we have resolved these difficulties using advanced parsing techniques (namely speculative parsing, parser state introspection, context-dependent lexical analysis and longest-prefix parsing) while keeping the implementation at a sufficiently high level of abstraction so that experts can check that the POSIX standard is respected. The resulting tool, called MORBIG, is an open-source static parser for a well-defined and realistic subset of the POSIX shell language.

关键词： Parsing POSIX shell functional programming

来源：评论

学校读者我要写书评

暂无评论

Exploiting hardware performance counters with flow and context sensitive profiling 97

Exploiting hardware performance counters with flow and conte...

引用

proceedings of the 1997 acm SIGPLAM conference on programming language design and implementation, PLDI

作者： Ammons, Glenn Ball, Thomas Larus, James R. Univ of Wisconsin-Madison Madison WI United States

ISBN: (纸本)9780897919074

A program profile attributes run-time costs to portions of a program's execution. Most profiling systems suffer from two major deficiencies: first, they only apportion simple metrics, such as execution frequency or elapsed time to static, syntactic units, such as procedures or statements;second, they aggressively reduce the volume of information collected and reported, although aggregation can hide striking differences in program behavior. This paper addresses both concerns by exploiting the hardware counters available in most modern processors and by incorporating two concepts from data flow analysis-flow and context sensitivity-to report more context for measurements. This paper extends our previous work on efficient path profiling to flow sensitive profiling, which associates hardware performance metrics with a path through a procedure. In addition, it describes a data structure, the calling context tree, that efficiently captures calling contexts for procedure-level measurements. Our measurements show that the SPEC95 benchmarks execute a small number (3-28) of hot paths that account for 9-98% of their L1 data cache misses. Moreover, these hot paths are concentrated in a few routines, which have complex dynamic behavior.

关键词： Computer programming languages

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：