207 results on '"Steve Zdancewic"'
Search Results
102. Secure Information Flow and CPS.
- Author
-
Steve Zdancewic and Andrew C. Myers
- Published
- 2001
- Full Text
- View/download PDF
103. Robust Declassification.
- Author
-
Steve Zdancewic and Andrew C. Myers
- Published
- 2001
- Full Text
- View/download PDF
104. Principals in Programming Languages: A Syntactic Proof Technique.
- Author
-
Steve Zdancewic, Dan Grossman, and J. Gregory Morrisett
- Published
- 1999
- Full Text
- View/download PDF
105. Technical perspective: Building bug-free compilers.
- Author
-
Steve Zdancewic
- Published
- 2018
- Full Text
- View/download PDF
106. Arrows for secure information flow.
- Author
-
Peng Li and Steve Zdancewic
- Published
- 2010
- Full Text
- View/download PDF
107. Computation focusing
- Author
-
Steve Zdancewic and Nick Rioux
- Subjects
Theoretical computer science ,Computer science ,Existential quantification ,020207 software engineering ,Context (language use) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Divergence (computer science) ,Term (time) ,010201 computation theory & mathematics ,Proof theory ,Simple (abstract algebra) ,Completeness (order theory) ,0202 electrical engineering, electronic engineering, information engineering ,Safety, Risk, Reliability and Quality ,Software ,Abstraction (linguistics) - Abstract
Focusing is a technique from proof theory that exploits type information to prune inessential nondeterminism from proof search procedures. Viewed through the lens of the Curry-Howard correspondence, a focused typing derivation yields terms in normal form. This paper explores how to exploit focusing for reasoning about contextual equivalences and full abstraction. We present a focused polymorphic call-by-push-value calculus and prove a computational completeness result: for every well-typed term, there exists a focused term that is βη-equivalent to it. This completeness result yields a powerful way to refine the context lemmas for establishing contextual equivalences, cutting down the set that must be considered to just focused contexts. The paper demonstrates the application of focusing to establish program equivalences, including free theorems. It also uses focusing to prove full abstraction of a translation of the pure, total call-by-push-value language into a language with divergence and simple effect types, yielding a novel solution to a simple-to-state, but hitherto difficult to solve problem.
- Published
- 2020
108. Interaction trees: representing recursive and impure programs in Coq
- Author
-
Chung-Kil Hur, Benjamin C. Pierce, Steve Zdancewic, Li-yao Xia, Gregory Malecha, Yannick Zakowski, Paul He, Computer Science Department, University of Pennsylvania [Philadelphia], Seoul National University [Seoul] (SNU), and BedRock Systems Inc.
- Subjects
FOS: Computer and information sciences ,Computer science ,Semantics (computer science) ,monads ,02 engineering and technology ,computer.software_genre ,Operational semantics ,Denotational semantics ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Coq ,Safety, Risk, Reliability and Quality ,Formal verification ,compiler correctness ,ComputingMilieux_MISCELLANEOUS ,Compiler correctness ,Bisimulation ,Computer Science - Programming Languages ,[INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL] ,Programming language ,Coinduction ,020207 software engineering ,16. Peace & justice ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Structural induction ,coinduction ,computer ,Software ,Programming Languages (cs.PL) - Abstract
"Interaction trees" (ITrees) are a general-purpose data structure for representing the behaviors of recursive programs that interact with their environments. A coinductive variant of "free monads," ITrees are built out of uninterpreted events and their continuations. They support compositional construction of interpreters from "event handlers", which give meaning to events by defining their semantics as monadic actions. ITrees are expressive enough to represent impure and potentially nonterminating, mutually recursive computations, while admitting a rich equational theory of equivalence up to weak bisimulation. In contrast to other approaches such as relationally specified operational semantics, ITrees are executable via code extraction, making them suitable for debugging, testing, and implementing software artifacts that are amenable to formal verification. We have implemented ITrees and their associated theory as a Coq library, mechanizing classic domain- and category-theoretic results about program semantics, iteration, monadic structures, and equational reasoning. Although the internals of the library rely heavily on coinductive proofs, the interface hides these details so that clients can use and reason about ITrees without explicit use of Coq's coinduction tactics. To showcase the utility of our theory, we prove the termination-sensitive correctness of a compiler from a simple imperative source language to an assembly-like target whose meanings are given in an ITree-based denotational semantics. Unlike previous results using operational techniques, our bisimulation proof follows straightforwardly by structural induction and elementary rewriting via an equational theory of combinators for control-flow graphs., Comment: 28 pages, 4 pages references, published at POPL 2020
- Published
- 2019
109. Enforcing Robust Declassification and Qualified Robustness.
- Author
-
Andrew C. Myers, Andrei Sabelfeld, and Steve Zdancewic
- Published
- 2006
- Full Text
- View/download PDF
110. A type-theoretic interpretation of pointcuts and advice.
- Author
-
Jay Ligatti, David Walker 0001, and Steve Zdancewic
- Published
- 2006
- Full Text
- View/download PDF
111. Formalizing Java-MaC.
- Author
-
Usa Sammapun, Raman Sharykin, Margaret DeLap, Myong Kim, and Steve Zdancewic
- Published
- 2003
- Full Text
- View/download PDF
112. Secure program partitioning.
- Author
-
Steve Zdancewic, Lantian Zheng, Nathaniel Nystrom, and Andrew C. Myers
- Published
- 2002
- Full Text
- View/download PDF
113. Secure Information Flow via Linear Continuations.
- Author
-
Steve Zdancewic and Andrew C. Myers
- Published
- 2002
- Full Text
- View/download PDF
114. Syntactic type abstraction.
- Author
-
Dan Grossman, J. Gregory Morrisett, and Steve Zdancewic
- Published
- 2000
- Full Text
- View/download PDF
115. An overview of the Oregon programming languages summer school.
- Author
-
Jim Allen, Zena M. Ariola, Pierre-Louis Curien, Matthew Fluet, Jeffrey S. Foster, Dan Grossman, Robert Harper 0001, Hugo Herbelin, Yannis Smaragdakis, David Walker 0001, and Steve Zdancewic
- Published
- 2009
- Full Text
- View/download PDF
116. Synthesizing symmetric lenses
- Author
-
Kathleen Fisher, Anders Miltner, Steve Zdancewic, Solomon Maina, Benjamin C. Pierce, and David Walker
- Subjects
FOS: Computer and information sciences ,Computer Science - Programming Languages ,Computer science ,String (computer science) ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,ComputingMilieux_LEGALASPECTSOFCOMPUTING ,020207 software engineering ,Class (philosophy) ,Astrophysics::Cosmology and Extragalactic Astrophysics ,02 engineering and technology ,Information theory ,Data structure ,law.invention ,Lens (optics) ,law ,020204 information systems ,Physics::Space Physics ,0202 electrical engineering, electronic engineering, information engineering ,Bijection ,Regular expression ,Safety, Risk, Reliability and Quality ,Algorithm ,Software ,Programming Languages (cs.PL) ,Simple (philosophy) - Abstract
Lenses are programs that can be run both "front to back" and "back to front," allowing updates to either their source or their target data to be transferred in both directions. Lenses have been extensively studied, extended, and applied. Recent work has demonstrated how techniques from type-directed program synthesis can be used to efficiently synthesize a simple class of lenses---bijective lenses over string data---given a pair of types (regular expressions) and examples. We extend this synthesis algorithm to a broader class of lenses, called simple symmetric lenses, including all bijective lenses, all of the popular category of "asymmetric" lenses, and a subset of the "symmetric lenses" proposed by Hofmann et al. Intuitively, simple symmetric lenses allow some information to be present on one side but not the other and vice versa. They are of independent theoretical interest, being the largest class of symmetric lenses that do not use persistent internal state. Synthesizing simple symmetric lenses is more challenging than synthesizing bijective lenses: Since some of the information on each side can be "disconnected" from the other side, there will typically be many lenses that agree with a given example. To guide the search process, we use stochastic regular expressions and information theory to estimate the amount of information propagated by a candidate lens, preferring lenses that propagate more information, as well as user annotations marking parts of the source and target formats as either irrelevant or essential. We describe an implementation of simple symmetric lenses and our synthesis procedure as extensions to the Boomerang language. We evaluate its performance on 48 benchmark examples drawn from Flash Fill, Augeas, and the bidirectional programming literature. Our implementation can synthesize each of these lenses in under 30 seconds., Comment: ICFP 2019
- Published
- 2019
117. Verifying an HTTP Key-Value Server with Interaction Trees and VST
- Author
-
Hengchu Zhang and Wolf Honoré and Nicolas Koh and Yao Li and Yishuai Li and Li-Yao Xia and Lennart Beringer and William Mansky and Benjamin Pierce and Steve Zdancewic, Zhang, Hengchu, Honoré, Wolf, Koh, Nicolas, Li, Yao, Li, Yishuai, Xia, Li-Yao, Beringer, Lennart, Mansky, William, Pierce, Benjamin, Zdancewic, Steve, Hengchu Zhang and Wolf Honoré and Nicolas Koh and Yao Li and Yishuai Li and Li-Yao Xia and Lennart Beringer and William Mansky and Benjamin Pierce and Steve Zdancewic, Zhang, Hengchu, Honoré, Wolf, Koh, Nicolas, Li, Yao, Li, Yishuai, Xia, Li-Yao, Beringer, Lennart, Mansky, William, Pierce, Benjamin, and Zdancewic, Steve
- Abstract
We present a networked key-value server, implemented in C and formally verified in Coq. The server interacts with clients using a subset of the HTTP/1.1 protocol and is specified and verified using interaction trees and the Verified Software Toolchain. The codebase includes a reusable and fully verified C string library that provides 17 standard POSIX string functions and 17 general purpose non-POSIX string functions. For the KVServer socket system calls, we establish a refinement relation between specifications at user-space level and at CertiKOS kernel-space level.
- Published
- 2021
- Full Text
- View/download PDF
118. WatchdogLite: Hardware-Accelerated Compiler-Based Pointer Checking.
- Author
-
Santosh Nagarakatte, Milo M. K. Martin, and Steve Zdancewic
- Published
- 2014
119. Synthesizing quotient lenses
- Author
-
Steve Zdancewic, David Walker, Benjamin C. Pierce, Anders Miltner, Kathleen Fisher, and Solomon Maina
- Subjects
Correctness ,Computer science ,020207 software engineering ,Astrophysics::Cosmology and Extragalactic Astrophysics ,02 engineering and technology ,law.invention ,Algebra ,Lens (optics) ,Regular language ,law ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Bijection ,Equivalence relation ,Regular expression ,Safety, Risk, Reliability and Quality ,Software ,Program synthesis ,Quotient - Abstract
Quotient lenses are bidirectional transformations whose correctness laws are “loosened” by specified equivalence relations, allowing inessential details in concrete data formats to be suppressed. For example, a programmer could use a quotient lens to define a transformation that ignores the order of fields in XML data, so that two XML files with the same fields but in different orders would be considered the same, allowing a single, simple program to handle them both. Building on a recently published algorithm for synthesizing plain bijective lenses from high-level specifications, we show how to synthesize bijective quotient lenses in three steps. First, we introduce quotient regular expressions (QREs), annotated regular expressions that conveniently mark inessential aspects of string data formats; each QRE specifies, simulteneously, a regular language and an equivalence relation on it. Second, we introduce QRE lenses , i.e., lenses mapping between QREs. Our key technical result is a proof that every QRE lens can be transformed into a functionally equivalent lens that canonizes source and target data just at the “edges” and that uses a bijective lens to map between the respective canonical elements; no internal canonization occurs in a lens in this normal form. Third, we leverage this normalization theorem to synthesize QRE lenses from a pair of QREs and example input-output pairs, reusing earlier work on synthesizing plain bijective lenses. We have implemented QREs and QRE lens synthesis as an extension to the bidirectional programming language Boomerang. We evaluate the effectiveness of our approach by synthesizing QRE lenses between various real-world data formats in the Optician benchmark suite.
- Published
- 2018
120. QWIRE: a core language for quantum circuits
- Author
-
Robert Rand, Jennifer Paykin, and Steve Zdancewic
- Subjects
010302 applied physics ,Quantum programming ,Theoretical computer science ,Programming language ,Interface (Java) ,Computer science ,Model of computation ,020207 software engineering ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Operational semantics ,Denotational semantics ,010201 computation theory & mathematics ,0103 physical sciences ,0202 electrical engineering, electronic engineering, information engineering ,computer ,Host (network) ,Quantum ,Software ,computer.programming_language ,Quantum computer - Abstract
This paper introduces QWIRE (``choir''), a language for defining quantum circuits and an interface for manipulating them inside of an arbitrary classical host language. QWIRE is minimal---it contains only a few primitives---and sound with respect to the physical properties entailed by quantum mechanics. At the same time, QWIRE is expressive and highly modular due to its relationship with the host language, mirroring the QRAM model of computation that places a quantum computer (controlled by circuits) alongside a classical computer (controlled by the host language). We present QWIRE along with its type system and operational semantics, which we prove is safe and strongly normalizing whenever the host language is. We give circuits a denotational semantics in terms of density matrices. Throughout, we investigate examples that demonstrate the expressive power of QWIRE, including extensions to the host language that (1) expose a general analysis framework for circuits, and (2) provide dependent types.
- Published
- 2017
121. Application-level concurrency: combining events and treads: invited talk.
- Author
-
Steve Zdancewic
- Published
- 2007
- Full Text
- View/download PDF
122. Encoding Information Flow in Haskell.
- Author
-
Peng Li and Steve Zdancewic
- Published
- 2006
- Full Text
- View/download PDF
123. SoK: General Purpose Compilers for Secure Multi-Party Computation
- Author
-
Brett Hemenway, Daniel Noble, Steve Zdancewic, and Marcella Hastings
- Subjects
Computer science ,business.industry ,Computation ,Cryptography ,02 engineering and technology ,Cryptographic protocol ,computer.software_genre ,Virtual machine ,020204 information systems ,Container (abstract data type) ,0202 electrical engineering, electronic engineering, information engineering ,Secure multi-party computation ,020201 artificial intelligence & image processing ,Compiler ,State (computer science) ,business ,Software engineering ,computer - Abstract
Secure multi-party computation (MPC) allows a group of mutually distrustful parties to compute a joint function on their inputs without revealing any information beyond the result of the computation. This type of computation is extremely powerful and has wide-ranging applications in academia, industry, and government. Protocols for secure computation have existed for decades, but only recently have general-purpose compilers for executing MPC on arbitrary functions been developed. These projects rapidly improved the state of the art, and began to make MPC accessible to non-expert users. However, the field is changing so rapidly that it is difficult even for experts to keep track of the varied capabilities of modern frameworks. In this work, we survey general-purpose compilers for secure multi-party computation. These tools provide high-level abstractions to describe arbitrary functions and execute secure computation protocols. We consider eleven systems: EMP-toolkit, Obliv-C, ObliVM, TinyGarble, SCALE-MAMBA (formerly SPDZ), Wysteria, Sharemind, PICCO, ABY, Frigate and CBMC-GC. We evaluate these systems on a range of criteria, including language expressibility, capabilities of the cryptographic back-end, and accessibility to developers. We advocate for improved documentation of MPC frameworks, standardization within the community, and make recommendations for future directions in compiler development. Installing and running these systems can be challenging, and for each system, we also provide a complete virtual environment (Docker container) with all the necessary dependencies to run the compiler and our example programs.
- Published
- 2019
124. ReQWIRE: Reasoning about Reversible Quantum Circuits
- Author
-
Dong-Ho Lee, Jennifer Paykin, Robert Rand, and Steve Zdancewic
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Computer science ,Computer Science - Emerging Technologies ,computer.software_genre ,lcsh:QA75.5-76.95 ,Quantum circuit ,Computer Science::Emerging Technologies ,Quantum ,Electronic circuit ,Computer Science - Programming Languages ,Programming language ,lcsh:Mathematics ,D.2.4 ,lcsh:QA1-939 ,Logic in Computer Science (cs.LO) ,Range (mathematics) ,Emerging Technologies (cs.ET) ,F.3.1 ,Qubit ,Quantum algorithm ,lcsh:Electronic computers. Computer science ,Compiler ,State (computer science) ,computer ,Programming Languages (cs.PL) - Abstract
Common quantum algorithms make heavy use of ancillae: scratch qubits that are initialized at some state and later returned to that state and discarded. Existing quantum circuit languages let programmers assert that a qubit has been returned to the |0> state before it is discarded, allowing for a range of optimizations. However, existing languages do not provide the tools to verify these assertions, introducing a potential source of errors. In this paper we present methods for verifying that ancillae are discarded in the desired state, and use these methods to implement a verified compiler from classical functions to quantum oracles., In Proceedings QPL 2018, arXiv:1901.09476
- Published
- 2019
- Full Text
- View/download PDF
125. From C to Interaction Trees: Specifying, Verifying, and Testing a Networked Server
- Author
-
Yao Li, Yishuai Li, Li-yao Xia, William Mansky, Benjamin C. Pierce, Nicolas Koh, Wolf Honoré, Lennart Beringer, and Steve Zdancewic
- Subjects
Structure (mathematical logic) ,FOS: Computer and information sciences ,Computer Science - Programming Languages ,Programming language ,Computer science ,Semantics (computer science) ,020207 software engineering ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,01 natural sciences ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,computer ,Formal verification ,Programming Languages (cs.PL) - Abstract
We present the first formal verification of a networked server implemented in C. Interaction trees, a general structure for representing reactive computations, are used to tie together disparate verification and testing tools (Coq, VST, and QuickChick) and to axiomatize the behavior of the operating system on which the server runs (CertiKOS). The main theorem connects a specification of acceptable server behaviors, written in a straightforward "one client at a time" style, with the CompCert semantics of the C program. The variability introduced by low-level buffering of messages and interleaving of multiple TCP connections is captured using network refinement, a variant of observational refinement., 13 pages + references
- Published
- 2018
126. Observational Determinism for Concurrent Program Security.
- Author
-
Steve Zdancewic and Andrew C. Myers
- Published
- 2003
- Full Text
- View/download PDF
127. Joint workshop on foundations of computer security and automated reasoning for security protocol analysis (FCS-ARSPA '06).
- Author
-
Pierpaolo Degano, Ralf Küsters, Luca Viganò 0001, and Steve Zdancewic
- Published
- 2008
- Full Text
- View/download PDF
128. QWIRE Practice: Formal Verification of Quantum Circuits in Coq
- Author
-
Jennifer Paykin, Robert Rand, and Steve Zdancewic
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Correctness ,Computer science ,Computer Science - Emerging Technologies ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,01 natural sciences ,lcsh:QA75.5-76.95 ,Quantum circuit ,Computer Science::Hardware Architecture ,Denotational semantics ,Computer Science::Emerging Technologies ,Abstract syntax ,0202 electrical engineering, electronic engineering, information engineering ,Quantum ,Formal verification ,Computer Science - Programming Languages ,Programming language ,lcsh:Mathematics ,Proof assistant ,D.2.4 ,020207 software engineering ,lcsh:QA1-939 ,Logic in Computer Science (cs.LO) ,Automated theorem proving ,Emerging Technologies (cs.ET) ,F.3.1 ,010201 computation theory & mathematics ,Computer Science::Programming Languages ,lcsh:Electronic computers. Computer science ,computer ,Programming Languages (cs.PL) - Abstract
We describe an embedding of the QWIRE quantum circuit language in the Coq proof assistant. This allows programmers to write quantum circuits using high-level abstractions and to prove properties of those circuits using Coq's theorem proving features. The implementation uses higher-order abstract syntax to represent variable binding and provides a type-checking algorithm for linear wire types, ensuring that quantum circuits are well-formed. We formalize a denotational semantics that interprets QWIRE circuits as superoperators on density matrices, and prove the correctness of some simple quantum programs., Comment: In Proceedings QPL 2017, arXiv:1802.09737
- Published
- 2018
- Full Text
- View/download PDF
129. A Formal Equational Theory for Call-By-Push-Value
- Author
-
Dmitri Garbuzov, Christine Rizkallah, and Steve Zdancewic
- Subjects
Soundness ,Computer science ,Programming language ,Semantics (computer science) ,Call-by-push-value ,Optimizing compiler ,020207 software engineering ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,01 natural sciences ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,010201 computation theory & mathematics ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Computer Science::Logic in Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science::Programming Languages ,computer ,Equational theory - Abstract
Establishing that two programs are contextually equivalent is hard, yet essential for reasoning about semantics preserving program transformations such as compiler optimizations. We adapt Lassen’s normal form bisimulations technique to establish the soundness of equational theories for both an untyped call-by-value \(\lambda \)-calculus and a variant of Levy’s call-by-push-value language. We demonstrate that our equational theory significantly simplifies the verification of optimizations.
- Published
- 2018
130. Run-time principals in information-flow type systems.
- Author
-
Stephen Tse and Steve Zdancewic
- Published
- 2007
- Full Text
- View/download PDF
131. Modeling Simply-Typed Lambda Calculi in the Category of Finite Vector Spaces
- Author
-
Steve Zdancewic and Benoît Valiron
- Subjects
Pure mathematics ,General Computer Science ,Homotopy category ,Applied Mathematics ,Lambda ,lcsh:QA75.5-76.95 ,Closed monoidal category ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Computer Science::Logic in Computer Science ,Category of topological spaces ,Computer Science::Programming Languages ,lcsh:Electronic computers. Computer science ,Arithmetic ,Mathematics ,Vector space - Abstract
In this paper we use finite vector spaces (finite dimension, over finite fields) as a non-standard computational model of linear logic. We first define a simple, finite PCF-like lambda-calculus with booleans, and then we discuss two finite models, one based on finite sets and the other on finite vector spaces. The first model is shown to be fully complete with respect to the operational semantics of the language, while the second model is not. We then develop an algebraic extension of the finite lambda calculus and study two operational semantics: a call-by-name and a call-by-value. These operational semantics are matched with their corresponding natural denotational semantics based on finite vector spaces. The relationship between the various semantics is analyzed, and several examples based on Church numerals are presented.
- Published
- 2014
132. Synthesizing Bijective Lenses
- Author
-
David Walker, Anders Miltner, Benjamin C. Pierce, Steve Zdancewic, and Kathleen Fisher
- Subjects
FOS: Computer and information sciences ,Parsing ,Computer Science - Programming Languages ,View ,Computer science ,Programming language ,020207 software engineering ,02 engineering and technology ,Disjunctive normal form ,computer.software_genre ,Constructed language ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Software system ,Regular expression ,Safety, Risk, Reliability and Quality ,computer ,Software ,Program synthesis ,Programming Languages (cs.PL) ,Declarative programming - Abstract
Bidirectional transformations between different data representations occur frequently in modern software systems. They appear as serializers and deserializers, as database views and view updaters, and more. Manually building bidirectional transformations---by writing two separate functions that are intended to be inverses---is tedious and error prone. A better approach is to use a domain-specific language in which both directions can be written as a single expression. However, these domain-specific languages can be difficult to program in, requiring programmers to manage fiddly details while working in a complex type system. To solve this, we present Optician, a tool for type-directed synthesis of bijective string transformers. The inputs to Optician are two ordinary regular expressions representing two data formats and a few concrete examples for disambiguation. The output is a well-typed program in Boomerang (a bidirectional language based on the theory of lenses). The main technical challenge involves navigating the vast program search space efficiently enough. Unlike most prior work on type-directed synthesis, our system operates in the context of a language with a rich equivalence relation on types (the theory of regular expressions). We synthesize terms of a equivalent language and convert those generated terms into our lens language. We prove the correctness of our synthesis algorithm. We also demonstrate empirically that our new language changes the synthesis problem from one that admits intractable solutions to one that admits highly efficient solutions. We evaluate Optician on a benchmark suite of 39 examples including both microbenchmarks and realistic examples derived from other data management systems including Flash Fill, a tool for synthesizing string transformations in spreadsheets, and Augeas, a tool for bidirectional processing of Linux system configuration files., 127 Pages, Extended Version with Appendix
- Published
- 2017
133. Position paper: the science of deep specification
- Author
-
Zhong Shao, Steve Zdancewic, Stephanie Weirich, Adam Chlipala, Lennart Beringer, Benjamin C. Pierce, Andrew W. Appel, Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, and Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
- Subjects
business.industry ,General Mathematics ,General Engineering ,General Physics and Astronomy ,0102 computer and information sciences ,02 engineering and technology ,Articles ,Formal methods ,01 natural sciences ,Software ,Work (electrical) ,010201 computation theory & mathematics ,020204 information systems ,Formal specification ,0202 electrical engineering, electronic engineering, information engineering ,Key (cryptography) ,Position paper ,Software engineering ,business ,Mathematics - Abstract
We introduce our efforts within the project ‘The science of deep specification’ to work out the key formal underpinnings of industrial-scale formal specifications of software and hardware components, anticipating a world where large verified systems are routinely built out of smaller verified components that are also used by many other projects. We identify an important class of specification that has already been used in a few experiments that connect strong component-correctness theorems across the work of different teams. To help popularize the unique advantages of that style, we dub itdeep specification, and we say that it encompasses specifications that arerich,two-sided,formalandlive(terms that we define in the article). Our core team is developing a proof-of-concept system (based on the Coq proof assistant) whose specification and verification work is divided across largely decoupled subteams at our four institutions, encompassing hardware microarchitecture, compilers, operating systems and applications, along with cross-cutting principles and tools for effective specification. We also aim to catalyse interest in the approach, not just by basic researchers but also by users in industry.This article is part of the themed issue ‘Verified trustworthy software systems’.
- Published
- 2017
134. Hardware-Enforced Comprehensive Memory Safety
- Author
-
Milo M. K. Martin, Steve Zdancewic, and Santosh Nagarakatte
- Subjects
Computer science ,business.industry ,Register renaming ,Smart pointer ,computer.software_genre ,Microarchitecture ,Metadata ,Memory management ,Hardware and Architecture ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Pointer (computer programming) ,Operating system ,Cache ,Electrical and Electronic Engineering ,business ,computer ,Memory safety ,Software ,Computer hardware - Abstract
The lack of memory safety in languages such as C and C++ is a root source of exploitable security vulnerabilities. This article presents Watchdog, a hardware approach that eliminates such vulnerabilities by enforcing comprehensive memory safety. Inspired by prior software-only mechanisms, Watchdog maintains bounds and identifier metadata with pointers, propagates them on pointer operations, and checks them on pointer dereferences. Checking this bounds and identifier metadata provides both precise, byte-granularity buffer-overflow protection and protection from use-after-free errors, even in the presence of reallocations. Watchdog stores pointer metadata in a disjoint shadow space to provide comprehensive protection and ensure compatibility with existing code. To streamline implementation and reduce runtime overhead, Watchdog uses micro-operations to implement metadata access and checking, eliminates metadata copies via a register renaming scheme, and uses a dedicated identifier cache to reduce checking overhead.
- Published
- 2013
135. Linear $$ \lambda \mu $$ is $$ \textsc {CP} $$ (more or less)
- Author
-
Jennifer Paykin and Steve Zdancewic
- Subjects
Physics ,020207 software engineering ,0102 computer and information sciences ,02 engineering and technology ,Intuitionistic logic ,Computer Science::Computational Complexity ,Lambda ,01 natural sciences ,Combinatorics ,010201 computation theory & mathematics ,Computer Science::Logic in Computer Science ,Computer Science::Mathematical Software ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science::Symbolic Computation ,Computer Science::Data Structures and Algorithms - Abstract
In this paper we compare Wadler’s \( \textsc {CP} \) calculus for classical linear processes to a linear version of Parigot’s \( \lambda \mu \) calculus for classical logic. We conclude that linear \( \lambda \mu \) is “more or less” \( \textsc {CP} \), in that it equationally corresponds to a polarized version of \( \textsc {CP} \). The comparison is made by extending a technique from Mellies and Tabareau’s tensor logic that correlates negation with polarization. The polarized \( \textsc {CP} \), which is written \( \textsc {CP}^{\pm } \) and pronounced “\( \textsc {CP} \) more or less,” is an interesting bridge in the landscape of Curry-Howard interpretations of logic.
- Published
- 2016
136. Watchdog
- Author
-
Milo M. K. Martin, Steve Zdancewic, and Santosh Nagarakatte
- Subjects
Manual memory management ,business.industry ,Computer science ,Register renaming ,General Medicine ,computer.software_genre ,Metadata ,Memory management ,Pointer (computer programming) ,Operating system ,Cache ,business ,Memory safety ,computer ,Computer hardware - Abstract
Languages such as C and C++ use unsafe manual memory management, allowing simple bugs (i.e., accesses to an object after deallocation) to become the root cause of exploitable security vulnerabilities. This paper proposes Watchdog, a hardware-based approach for ensuring safe and secure manual memory management. Inspired by prior software-only proposals, Watchdog generates a unique identifier for each memory allocation, associates these identifiers with pointers, and checks to ensure that the identifier is still valid on every memory access. This use of identifiers and checks enables Watchdog to detect errors even in the presence of reallocations. Watchdog stores these pointer identifiers in a disjoint shadow space to provide comprehensive protection and ensure compatibility with existing code. To streamline the implementation and reduce runtime overhead: Watchdog (1) uses micro-ops to access metadata and perform checks, (2) eliminates metadata copies among registers via modified register renaming, and (3) uses a dedicated metadata cache to reduce checking overhead. Furthermore, this paper extends Watchdog's mechanisms to detect bounds errors, thereby providing full hardware-enforced memory safety at low overheads.
- Published
- 2012
137. Formalizing the LLVM intermediate representation for verified program transformations
- Author
-
Milo M. K. Martin, Santosh Nagarakatte, Steve Zdancewic, and Jianzhou Zhao
- Subjects
Intermediate language ,Theoretical computer science ,Static single assignment form ,Computer science ,Programming language ,Formal semantics (linguistics) ,Proof assistant ,computer.software_genre ,Computer Graphics and Computer-Aided Design ,Operational semantics ,Semantics of logic ,Test suite ,Software_PROGRAMMINGLANGUAGES ,computer ,Memory safety ,Implementation ,Software ,Interpreter - Abstract
This paper presents Vellvm (verified LLVM), a framework for reasoning about programs expressed in LLVM's intermediate representation and transformations that operate on it. Vellvm provides a mechanized formal semantics of LLVM's intermediate representation, its type system, and properties of its SSA form. The framework is built using the Coq interactive theorem prover. It includes multiple operational semantics and proves relations among them to facilitate different reasoning styles and proof techniques. To validate Vellvm's design, we extract an interpreter from the Coq formal semantics that can execute programs from LLVM test suite and thus be compared against LLVM reference implementations. To demonstrate Vellvm's practicality, we formalize and verify a previously proposed transformation that hardens C programs against spatial memory safety violations. Vellvm's tools allow us to extract a new, verified implementation of the transformation pass that plugs into the real LLVM infrastructure; its performance is competitive with the non-verified, ad-hoc original.
- Published
- 2012
138. Lolliproc
- Author
-
Karl Mazurak and Steve Zdancewic
- Subjects
Soundness ,Concurrent constraint logic programming ,Functional programming ,Computer science ,Programming language ,Concurrency ,Process calculus ,computer.software_genre ,Computer Graphics and Computer-Aided Design ,Linear logic ,Curry–Howard correspondence ,Concurrent object-oriented programming ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Confluence ,Concurrent computing ,computer ,Algorithm ,Logic programming ,Software - Abstract
While many type systems based on the intuitionistic fragment of linear logic have been proposed, applications in programming languages of the full power of linear logic - including double-negation elimination - have remained elusive. Meanwhile, linearity has been used in many type systems for concurrent programs - e.g., session types - which suggests applicability to the problems of concurrent programming, but the ways in which linearity has interacted with concurrency primitives in lambda calculi have remained somewhat ad-hoc. In this paper we connect classical linear logic and concurrent functional programming in the language Lolliproc, which provides simple primitives for concurrency that have a direct logical interpretation and that combine to provide the functionality of session types. Lolliproc features a simple process calculus "under the hood" but hides the machinery of processes from programmers. We illustrate Lolliproc by example and prove soundness, strong normalization, and confluence results, which, among other things, guarantees freedom from deadlocks and race conditions.
- Published
- 2010
139. CETS
- Author
-
Santosh Nagarakatte, Milo M. K. Martin, Jianzhou Zhao, and Steve Zdancewic
- Subjects
Programming language ,Computer science ,media_common.quotation_subject ,Optimizing compiler ,Memory corruption ,computer.software_genre ,Computer Graphics and Computer-Aided Design ,Debugging ,Dangling pointer ,Pointer (computer programming) ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Compiler ,computer ,Memory safety ,Software ,media_common - Abstract
Temporal memory safety errors, such as dangling pointer dereferences and double frees, are a prevalent source of software bugs in unmanaged languages such as C. Existing schemes that attempt to retrofit temporal safety for such languages have high runtime overheads and/or are incomplete, thereby limiting their effectiveness as debugging aids. This paper presents CETS, a compile-time transformation for detecting all violations of temporal safety in C programs. Inspired by existing approaches, CETS maintains a unique identifier with each object, associates this metadata with the pointers in a disjoint metadata space to retain memory layout compatibility, and checks that the object is still allocated on pointer dereferences. A formal proof shows that this is sufficient to provide temporal safety even in the presence of arbitrary casts if the program contains no spatial safety violations. Our CETS prototype employs both temporal check removal optimizations and traditional compiler optimizations to achieve a runtime overhead of just 48% on average. When combined with a spatial-checking system, the average overall overhead is 116% for complete memory safety
- Published
- 2010
140. AURA
- Author
-
Steve Zdancewic, Jianzhou Zhao, Karl Mazurak, Luke Zarko, Limin Jia, Jeffrey A. Vaughan, and Joseph Schorr
- Subjects
Soundness ,business.industry ,Programming language ,Computer science ,Assertion ,Access control ,computer.software_genre ,Mathematical proof ,Computer Graphics and Computer-Aided Design ,Data type ,Decidability ,Type theory ,Polymorphism (computer science) ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,business ,computer ,Software ,Interpreter - Abstract
This paper presents AURA, a programming language for access control that treats ordinary programming constructs (e.g., integers and recursive functions) and authorization logic constructs (e.g., principals and access control policies) in a uniform way. AURA is based on polymorphic DCC and uses dependent types to permit assertions that refer directly to AURA values while keeping computation out of the assertion level to ensure tractability. The main technical results of this paper include fully mechanically verified proofs of the decidability and soundness for AURA's type system, and a prototype typechecker and interpreter.
- Published
- 2008
141. Hardbound
- Author
-
Colin Blundell, Steve Zdancewic, Milo M. K. Martin, and Joseph Devietti
- Subjects
Pointer aliasing ,Programming language ,C dynamic memory allocation ,Computer science ,Opaque pointer ,Smart pointer ,General Medicine ,computer.software_genre ,Data type ,Computer Graphics and Computer-Aided Design ,Pointer swizzling ,Pointer (computer programming) ,Escape analysis ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Operating system ,General Earth and Planetary Sciences ,Compiler ,computer ,Memory safety ,Bounded pointer ,Software ,General Environmental Science - Abstract
The C programming language is at least as well known for its absence of spatial memory safety guarantees (i.e., lack of bounds checking) as it is for its high performance. C's unchecked pointer arithmetic and array indexing allow simple programming mistakes to lead to erroneous executions, silent data corruption, and security vulnerabilities. Many prior proposals have tackled enforcing spatial safety in C programs by checking pointer and array accesses. However, existing software-only proposals have significant drawbacks that may prevent wide adoption, including: unacceptably high run-time overheads, lack of completeness, incompatible pointer representations, or need for non-trivial changes to existing C source code and compiler infrastructure. Inspired by the promise of these software-only approaches, this paper proposes a hardware bounded pointer architectural primitive that supports cooperative hardware/software enforcement of spatial memory safety for C programs. This bounded pointer is a new hardware primitive datatype for pointers that leaves the standard C pointer representation intact, but augments it with bounds information maintained separately and invisibly by the hardware. The bounds are initialized by the software, and they are then propagated and enforced transparently by the hardware, which automatically checks a pointer's bounds before it is dereferenced. One mode of use requires instrumenting only malloc, which enables enforcement of perallocation spatial safety for heap-allocated objects for existing binaries. When combined with simple intraprocedural compiler instrumentation, hardware bounded pointers enable a low-overhead approach for enforcing complete spatial memory safety in unmodified C programs.
- Published
- 2008
142. A formal C memory model supporting integer-pointer casts
- Author
-
Viktor Vafeiadis, William Mansky, Chung-Kil Hur, Steve Zdancewic, Dmitri Garbuzov, and Jeehoon Kang
- Subjects
Theoretical computer science ,Integer ,Programming language ,Computer science ,Pointer (computer programming) ,Compiler ,Memory model ,computer.software_genre ,Implementation ,computer ,Formal verification - Abstract
The ISO C standard does not specify the semantics of many valid programs that use non-portable idioms such as integer-pointer casts. Recent efforts at formal definitions and verified implementation of the C language inherit this feature. By adopting high-level abstract memory models, they validate common optimizations. On the other hand, this prevents reasoning about much low-level code relying on the behavior of common implementations, where formal verification has many applications. We present the first formal memory model that allows many common optimizations and fully supports operations on the representation of pointers. All arithmetic operations are well-defined for pointers that have been cast to integers. Crucially, our model is also simple to understand and program with. All our results are fully formalized in Coq.
- Published
- 2015
143. A type-theoretic interpretation of pointcuts and advice
- Author
-
David Walker, Steve Zdancewic, and Jay Ligatti
- Subjects
Theoretical computer science ,Type theory ,Computer science ,Programming language ,Semantics (computer science) ,020207 software engineering ,02 engineering and technology ,Aspects ,computer.software_genre ,Aspect-oriented programming languages ,Operational semantics ,Language primitive ,High-level programming language ,020204 information systems ,Programming language specification ,0202 electrical engineering, electronic engineering, information engineering ,First-generation programming language ,Low-level programming language ,computer ,Software ,Programming language theory - Abstract
This article defines the semantics of MinAML, an idealized aspect-oriented programming language, by giving a type-directed translation from a user-friendly external language to a compact, well-defined core language. We argue that our framework is an effective way to give semantics to aspect-oriented programming languages in general because the translation eliminates shallow syntactic differences between related constructs and permits definition of an elegant and extensible core language.The core language extends the simply-typed lambda calculus with two central new abstractions: explicitly labeled program points and first-class advice. The labels serve both to trigger advice and to mark continuations that the advice may return to. These constructs are defined orthogonally to the other features of the language and we show that our abstractions can be used in both functional and object-oriented contexts. We prove Preservation and Progress lemmas for our core language and show that the translation from MinAML source into core is type-preserving. Together these two results imply that the source language is type safe. We also consider several extensions to our basic framework including a general mechanism for analyzing the current call stack.
- Published
- 2006
144. Enforcing Robust Declassification and Qualified Robustness
- Author
-
Steve Zdancewic, Andrew C. Myers, and Andrei Sabelfeld
- Subjects
Computer Networks and Communications ,Computer science ,Distributed computing ,Security policy ,Computer security ,computer.software_genre ,Information sensitivity ,Program analysis ,Hardware and Architecture ,Robustness (computer science) ,Data integrity ,Confidentiality ,Declassification ,Safety, Risk, Reliability and Quality ,computer ,Software - Abstract
Noninterference requires that there is no information flow from sensitive to public data in a given system. However, many systems release sensitive information as part of their intended function and therefore violate noninterference. To control information flow while permitting information release, some systems have a downgrading or declassification mechanism, but this creates the danger that it may cause unintentional information release. This paper shows that a robustness property can be used to characterize programs in which declassification mechanisms cannot be controlled by attackers to release more information than intended. It describes a simple way to provably enforce this robustness property through a type-based compile-time program analysis. The paper also presents a generalization of robustness that supports upgrading (endorsing) data integrity.
- Published
- 2006
145. Formalizing Java-MaC
- Author
-
Myong Kim, Usa Sammapun, Raman Sharykin, Margaret DeLap, and Steve Zdancewic
- Subjects
Correctness ,General Computer Science ,Java ,Computer science ,Programming language ,Scala ,strictfp ,Runtime verification ,computer.software_genre ,Java concurrency ,Operational semantics ,Theoretical Computer Science ,Real time Java ,Instrumentation (computer programming) ,computer ,Java Modeling Language ,computer.programming_language ,Computer Science(all) - Abstract
The Java-MaC framework is a run-time verification system for Java programs that can be used to dynamically test and enforce safety policies. This paper presents a formal model of the Java-MaC safety properties in terms of an operational semantics for Middleweight Java, a realistic subset of full Java. This model is intended to be used as a framework for studying the correctness of Java-MaC program instrumentation, optimizations, and future experimentation with run-time monitor expressiveness. As a preliminary demonstration of this model's applicability for these tasks, the paper sketches a correctness result for a simple program instrumentation scheme.
- Published
- 2003
- Full Text
- View/download PDF
146. [Untitled]
- Author
-
Andrew C. Myers and Steve Zdancewic
- Subjects
Structure (mathematical logic) ,Property (philosophy) ,Theoretical computer science ,Computer science ,Semantics (computer science) ,Programming language ,computer.software_genre ,Computer Science Applications ,Control flow ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Secrecy ,Continuation-passing style ,State (computer science) ,Information flow (information theory) ,computer ,Software - Abstract
Security-typed languages enforce secrecy or integrity policies by type-checking. This paper investigates continuation-passing style (CPS) as a means of proving that such languages enforce noninterference and as a first step towards understanding their compilation. We present a low-level, secure calculus with higher-order, imperative features and linear continuations. Linear continuations impose a stack discipline on the control flow of programs. This additional structure in the type system lets us establish a strong information-flow security property called noninterference. We prove that our CPS target language enjoys the noninterference property and we show how to translate secure high-level programs to this low-level language. This noninterference proof is the first of its kind for a language with higher-order functions and state.
- Published
- 2002
147. WatchdogLite
- Author
-
Milo M. K. Martin, Santosh Nagarakatte, and Steve Zdancewic
- Subjects
business.industry ,Computer science ,020207 software engineering ,Smart pointer ,02 engineering and technology ,computer.software_genre ,020202 computer hardware & architecture ,Metadata ,Bounds checking ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Escape analysis ,Pointer (computer programming) ,0202 electrical engineering, electronic engineering, information engineering ,Operating system ,Hardware acceleration ,Compiler ,business ,Memory safety ,computer ,Computer hardware - Abstract
Lack of memory safety in C is the root cause of a multitude of serious bugs and security vulnerabilities. Numerous software-only and hardware-based schemes have been proposed to enforce memory safety. Among these approaches, pointer-based checking, which maintains per-pointer metadata in a disjoint metadata space, has been recognized as providing comprehensive memory safety. Software approaches for pointer-based checking have high performance overheads. In contrast, hardware approaches introduce a myriad of hardware structures and widgets to mitigate those performance overheads.This paper proposes WatchdogLite, an ISA extension that provides hardware acceleration for a compiler implementation of pointer-based checking. This division of labor between the compiler and the hardware allows for hardware acceleration while using only preexisting architectural registers. By leveraging the compiler to identify pointers, perform check elimination, and insert the new instructions, this approach attains performance similar to prior hardware-intensive approaches without adding any hardware structures for tracking metadata.
- Published
- 2014
148. A Core Quantitative Coeffect Calculus
- Author
-
Marco Gaboardi, Aloïs Brunel, Steve Zdancewic, and Damiano Mazza
- Subjects
Pure mathematics ,Functional programming ,Computer science ,Mathematics::Category Theory ,Structure (category theory) ,Context (language use) ,Type (model theory) ,Element (category theory) ,Algorithm ,Linear logic ,Semiring ,Interpretation (model theory) - Abstract
Linear logic is well known for its resource-awareness, which has inspired the design of several resource management mechanisms in programming language design. Its resource-awareness arises from the distinction between linear, single-use data and non-linear, reusable data. The latter is marked by the so-called exponential modality, which, from the categorical viewpoint, is a monoidal comonad. Monadic notions of computation are well-established mechanisms used to express effects in pure functional languages. Less well-established is the notion of comonadic computation. However, recent works have shown the usefulness of comonads to structure context dependent computations. In this work, we present a language $\ell \mathcal{R}$ PCF inspired by a generalized interpretation of the exponential modality. In $\ell \mathcal{R}$ PCF the exponential modality carries a label--an element of a semiring $\mathcal{R}$ --that provides additional information on how a program uses its context. This additional structure is used to express comonadic type analysis.
- Published
- 2014
149. An overview of the Oregon programming languages summer school
- Author
-
David Walker, Dan Grossman, Robert Harper, Yannis Smaragdakis, Hugo Herbelin, Matthew Fluet, James G. Allen, Zena M. Ariola, Jeffrey S. Foster, Pierre-Louis Curien, and Steve Zdancewic
- Subjects
Programming language ,Computer science ,Steering committee ,computer.software_genre ,Computer Graphics and Computer-Aided Design ,computer ,Software ,Field (computer science) - Abstract
The Oregon Programming Languages Summer School (OPLSS) has been held at the University of Oregon each summer since 2002. We believe it has been an unqualified success in providing students and instructors a unique opportunity to study relevant background and cutting-edge results in the field of programming languages research. As the current steering committee and organizers for OPLSS, we appreciate the opportunity to provide an overview of the summer school. This short article describes the format, history, goals, and support for the OPLSS.
- Published
- 2010
150. Everything You Want to Know About Pointer-Based Checking
- Author
-
Santosh Nagarakatte and Milo M. K. Martin and Steve Zdancewic, Nagarakatte, Santosh, Martin, Milo M. K., Zdancewic, Steve, Santosh Nagarakatte and Milo M. K. Martin and Steve Zdancewic, Nagarakatte, Santosh, Martin, Milo M. K., and Zdancewic, Steve
- Abstract
Lack of memory safety in C/C++ has resulted in numerous security vulnerabilities and serious bugs in large software systems. This paper highlights the challenges in enforcing memory safety for C/C++ programs and progress made as part of the SoftBoundCETS project. We have been exploring memory safety enforcement at various levels - in hardware, in the compiler, and as a hardware-compiler hybrid - in this project. Our research has identified that maintaining metadata with pointers in a disjoint metadata space and performing bounds and use-after-free checking can provide comprehensive memory safety. We describe the rationale behind the design decisions and its ramifications on various dimensions, our experience with the various variants that we explored in this project, and the lessons learned in the process. We also describe and analyze the forthcoming Intel Memory Protection Extensions (MPX) that provides hardware acceleration for disjoint metadata and pointer checking in mainstream hardware, which is expected to be available later this year.
- Published
- 2015
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.