implementations of many data structures use several correlated fields to improve their performance;however, inconsistencies between these fields can be a source of serious program errors. To address this problem, we p...
详细信息
ISBN:
(纸本)9781450383912
implementations of many data structures use several correlated fields to improve their performance;however, inconsistencies between these fields can be a source of serious program errors. To address this problem, we propose a new technique for automatically refining data structures from integrity constraints. In particular, consider a data structure D with fields F and methods M, as well as a new set of auxiliary fields F' that should be added to D. Given this input and an integrity constraint Phi relating F and F', our method automatically generates a refinement of.. that satisfies the provided integrity constraint. Our method is based on a modular instantiation of the CEGIS paradigm and uses a novel inductive synthesizer that augments top-down search with three key ideas. First, it computes necessary preconditions of partial programs to dramatically prune its search space. Second, it augments the grammar with promising new productions by leveraging the computed preconditions. Third, it guides top-down search using a probabilistic context-free grammar obtained by statically analyzing the integrity checking function and the original code base. We evaluated our method on 25 data structures from popular Java projects and show that our method can successfully refine 23 of them. We also compare our method against two state-of-the-art synthesis tools and perform an ablation study to justify our design choices. Our evaluation shows that (1) our method is successful at refining many data structure implementations in the wild, (2) it advances the state-of-the-art in synthesis, and (3) our proposed ideas are crucial for making this technique practical.
Creating an application-specific processor is an effective and popular way to solve many problems in embedded hardware design using FPGAs, ASICs, or custom silicon. programming these processors is complicated by the l...
详细信息
ISBN:
(纸本)9781450389860
Creating an application-specific processor is an effective and popular way to solve many problems in embedded hardware design using FPGAs, ASICs, or custom silicon. programming these processors is complicated by the lack of toolchain support for creating the necessary binary code as part of hardware design, implementation, and evaluation. Hardware developers who cannot create their own ad-hoc assembler are left to hand-assemble their code into binary instructions which is both painful and error prone. We present a tool that supports the rapid creation of assemblers for application-specific processors. A single language is used to specify both instruction formats as collections of bit fields and the instantiation of those formats into sequences of binary instructions as a single, homogeneous activity that is designed to be as familiar and accessible to hardware designers as possible. The output from the tool can be used directly by hardware synthesis tools to initialise the program memory of an application-specific processor.
design by Contract represents an established, lightweight paradigm for engineering reliable and robust software systems by specifying verifiable expectations and obligations between software components. Due to its lab...
详细信息
ISBN:
(纸本)9798400712111
design by Contract represents an established, lightweight paradigm for engineering reliable and robust software systems by specifying verifiable expectations and obligations between software components. Due to its laborious nature, developers hardly adopt design by Contract in practice. A plethora of research on (semi-)-automated inference to reduce the manual burden has not improved the adoption of so-called code contracts in practice. This paper examines the potential of Generative AI to automatically generate code contracts in terms of pre- and postconditions for any Java project without requiring any additional auxiliary artifact. To fine-tune two state-of-the-art Large language Models, CodeT5 and CodeT5+, we derive a dataset of more than 14k Java methods comprising contracts in form of Java Modeling language (JML) annotations, and train the models on the task of generating contracts. We examine the syntactic and semantic validity of the contracts generated for software projects not used in the fine-tuning and find that more than 95% of the generated contracts are syntactically correct and exhibit remarkably high completeness and semantic correctness. To this end, our fully automated method sets the stage for future research and eventual broader adoption of design by Contract in software development practice.
The proceedings contain 47 papers. The topics discussed include: cache locality optimization for recursive programs;generalizations of the theory and deployment of triangular inequality for compiler-based strength red...
ISBN:
(纸本)9781450349888
The proceedings contain 47 papers. The topics discussed include: cache locality optimization for recursive programs;generalizations of the theory and deployment of triangular inequality for compiler-based strength reduction;DemoMatch: API discovery from demonstrations;similarity of binaries through re-optimization;BARRACUDA: binary-level analysis of runtime races in CUDA programs;bringing the web up to speed with WebAssembly;proactive and adaptive energy-aware programming with mixed typechecking;simple, fast, and safe manual memory management;efficient and precise points-to analysis: modeling the heap by merging equivalent automata;static deadlock detection for asynchronous c# programs;achieving high coverage for floating-point code via unconstrained programming;skeletal program enumeration for rigorous compiler testing;decomposition instead of self-composition for proving the absence of timing channels;automatic program inversion using symbolic transducers;rigorous analysis of software countermeasures against cache attacks;component-based synthesis of table consolidation and transformation tasks from examples;and network configuration synthesis with abstract topologies.
Cryptographic techniques have the potential to enable distrusting parties to collaborate in fundamentally new ways, but their practical implementation poses numerous challenges. An important class of such cryptographi...
详细信息
ISBN:
(纸本)9781450391122
Cryptographic techniques have the potential to enable distrusting parties to collaborate in fundamentally new ways, but their practical implementation poses numerous challenges. An important class of such cryptographic techniques is known as Secure Multi-Party Computation (MPC). Developing Secure MPC applications in realistic scenarios requires extensive knowledge spanning multiple areas of cryptography and systems. And while the steps to arrive at a solution for a particular application are often straightforward, it remains difficult to make the implementation efficient, and tedious to apply those same steps to a slightly different application from scratch. Hence, it is an important problem to design platforms for implementing Secure MPC applications with minimum effort and using techniques accessible to non-experts in cryptography. In this paper, we present the HACCLE (High Assurance Compositional Cryptography: languages and Environments) toolchain, specifically targeted to MPC applications. HACCLE contains an embedded domain-specific language Harpoon, for software developers without cryptographic expertise to write MPC-based programs, and uses Lightweight Modular Staging (LMS) for code generation. Harpoon programs are compiled into acyclic circuits represented in HACCLE's Intermediate Representation (HIR) that serves as an abstraction over different cryptographic protocols such as secret sharing, homomorphic encryption, or garbled circuits. implementations of different cryptographic protocols serve as different backends of our toolchain. The extensible design of HIR allows cryptographic experts to plug in new primitives and protocols to realize computation. And the use of standard metaprogramming techniques lowers the development effort significantly. We have implemented Harpoon and HACCLE, and used them to program interesting applications (e.g., secure auction) and key computation components of Secure MPC applications (e.g., matrix-vector multiplication and merg
We present ***, a synchronous reactive language that adds synchronous concurrency and preemption to JavaScript. Inspired from Esterel, *** simplifies the programming of non-trivial temporal behaviors as found in compl...
详细信息
ISBN:
(纸本)9781450376136
We present ***, a synchronous reactive language that adds synchronous concurrency and preemption to JavaScript. Inspired from Esterel, *** simplifies the programming of non-trivial temporal behaviors as found in complex web interfaces or IoT controllers and the cooperation between synchronous and asynchronous activities. *** is compiled into plain sequential JavaScript and executes on unmodified runtime environments. We use three examples to present and discuss ***: a simple web login form to introduce the language and show how it differs from JavaScript, and two real life examples, a medical prescription pillbox and an interactive music system that show why concurrency and preemption help programming such temporal applications.
We present lambda PSI, the first probabilistic programminglanguage and system that supports higher-order exact inference for probabilistic programs with first-class functions, nested inference and discrete, continuou...
详细信息
ISBN:
(纸本)9781450376136
We present lambda PSI, the first probabilistic programminglanguage and system that supports higher-order exact inference for probabilistic programs with first-class functions, nested inference and discrete, continuous and mixed random variables. lambda PSI's solver is based on symbolic reasoning and computes the exact distribution represented by a program. We show that lambda PSI is practically effective-it automatically computes exact distributions for a number of interesting applications, from rational agents to information theory, many of which could so far only be handled approximately.
Synchronous modeling is at the heart of programminglanguages like Lustre, Esterel, or SCADE used routinely for implementing safety critical control software, e.g., fly-by-wire and engine control in planes. However, t...
详细信息
ISBN:
(纸本)9781450376136
Synchronous modeling is at the heart of programminglanguages like Lustre, Esterel, or SCADE used routinely for implementing safety critical control software, e.g., fly-by-wire and engine control in planes. However, to date these languages have had limited modern support for modeling uncertainty - probabilistic aspects of the software's environment or behavior - even though modeling uncertainty is a primary activity when designing a control system. In this paper we present ProbZelus the first synchronous probabilistic programminglanguage. ProbZelus conservatively provides the facilities of a synchronous language to write control software, with probabilistic constructs to model uncertainties and perform inference-in-the-loop. We present the design and implementation of the language. We propose a measure-theoretic semantics of probabilistic stream functions and a simple type discipline to separate deterministic and probabilistic expressions. We demonstrate a semantics-preserving compilation into a first-order functional language that lends itself to a simple presentation of inference algorithms for streaming models. We also redesign the delayed sampling inference algorithm to provide efficient streaming inference. Together with an evaluation on several reactive applications, our results demonstrate that ProbZelus enables the design of reactive probabilistic applications and efficient, bounded memory inference.
Existing quantum languages force the programmer to work at a low level of abstraction leading to unintuitive and cluttered code. A fundamental reason is that dropping temporary values from the program state requires e...
详细信息
ISBN:
(纸本)9781450376136
Existing quantum languages force the programmer to work at a low level of abstraction leading to unintuitive and cluttered code. A fundamental reason is that dropping temporary values from the program state requires explicitly applying quantum operations that safely uncompute these values. We present Silq, the first quantum language that addresses this challenge by supporting safe, automatic uncomputation. This enables an intuitive semantics that implicitly drops temporary values, as in classical computation. To ensure physicality of Silq's semantics, its type system leverages novel annotations to reject unphysical programs. Our experimental evaluation demonstrates that Silq programs are not only easier to read and write, but also significantly shorter than equivalent programs in other quantum languages (on average -46% for Q#, -38% for Quipper), while using only half the number of quantum primitives.
The Bluespec hardware-description language presents a significantly higher-level view than hardware engineers are used to, exposing a simpler concurrency model that promotes formal proof, without compromising on perfo...
详细信息
ISBN:
(纸本)9781450376136
The Bluespec hardware-description language presents a significantly higher-level view than hardware engineers are used to, exposing a simpler concurrency model that promotes formal proof, without compromising on performance of compiled circuits. Unfortunately, the cost model of Bluespec has been unclear, with performance details depending on a mix of user hints and opaque static analysis of potential concurrency conflicts within a design. In this paper we present Koika, a derivative of Bluespec that preserves its desirable properties and yet gives direct control over the scheduling decisions that determine performance. Koika has a novel and deterministic operational semantics that uses dynamic analysis to avoid concurrency anomalies. Our implementation includes Coq definitions of syntax, semantics, key metatheorems, and a verified compiler to circuits. We argue that most of the extra circuitry required for dynamic analysis can be eliminated by compile-time BSV-style static analysis.
暂无评论