David Walker

David Walker

Auto-generated profile, based on publicly available information

David Walker

Princeton University, Princeton, USA

Research Focus & Metrics

Academic Career Length

22Years (2005-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 February 2005 in International Journal of Information Security
Verified
Journal Article
Closed access
PDF file
JLJay Ligatti
Jay Ligatti
LBLujo Bauer
Lujo Bauer
DWDavid Walker
David Walker

21 February 2006
Verified
Book Chapter
Closed access
PDF file
XOXinming Ou
Xinming Ou
GTGang Tan
Gang Tan
YMYitzhak Mandelbaum
Yitzhak Mandelbaum
DWDavid Walker
David Walker

27 December 2017 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
PDF file
AMAnders Miltner
Anders Miltner
KFKathleen Fisher
Kathleen Fisher
BPBenjamin C. Pierce
Benjamin C. Pierce
DWDavid Walker
David Walker
SZSteve Zdancewic
Steve Zdancewic
Bidirectional transformations between different data representations occur frequently in modern software systems. They appear as serializers and deserializers, as parsers and pretty printers, as database views and view updaters, and as a multitude of different kinds of ad hoc data converters. 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. We present an alternative approach. Instead of coding transformations manually, we synthesize them from declarative format descriptions and examples. Specifically, we present Optician, a tool for type-directed synthesis of bijective string transformers. The inputs to Optician are a pair of 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. In particular, and 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). Consequently, program synthesis requires search in two dimensions: First, our synthesis algorithm must find a pair of "syntactically compatible types," and second, using the structure of those types, it must find a type- and example-compliant term. Our key insight is that it is possible to reduce the size of this search space without losing any computational power by defining a new language of lenses designed specifically for synthesis. The new language is free from arbitrary function composition and operates only over types and terms in a new disjunctive normal form. We prove (1) our new language is just as powerful as a more natural, compositional, and declarative language and (2) our synthesis algorithm is sound and complete with respect to the new language. 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, able to synthesize intricate lenses between complex file formats in seconds. We evaluate Optician on a benchmark suite of 39 examples that includes 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.

1 July 2014 in Journal of Network and Systems Management
Verified
Journal Article
Closed access
PDF file
PSPeng Sun
Peng Sun
MYMinlan Yu
Minlan Yu
MFMichael J. Freedman
Michael J. Freedman
JRJennifer Rexford
Jennifer Rexford
DWDavid Walker
David Walker

6 June 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
TTTimothy Alberdingk Thijm
Timothy Alberdingk Thijm
RBRyan Beckett
Ryan Beckett
AGAarti Gupta
Aarti Gupta
DWDavid Walker
David Walker
Monolithic control plane verification cannot scale to hyperscale network architectures with tens of thousands of nodes, heterogeneous network policies and thousands of network changes a day. Instead, modular verification offers improved scalability, reasoning over diverse behaviors, and robustness following policy updates. We introduce Timepiece, a new modular control plane verification system. While one class of verifiers, starting with Minesweeper, were based on analysis of stable paths, we show that such models, when deployed naïvely for modular verification, are unsound. To rectify the situation, we adopt a routing model based around a logical notion of time and develop a sound, expressive, and scalable verification engine. Our system requires that a user specifies interfaces between module components. We develop methods for defining these interfaces using predicates inspired by temporal logic, and show how to use those interfaces to verify a range of network-wide properties such as reachability or access control. Verifying a prefix-filtering policy using a non-modular verification engine times out on an 80-node fattree network after 2 hours. However, Timepiece verifies a 2,000-node fattree in 2.37 minutes on a 96-core virtual machine. Modular verification of individual routers is embarrassingly parallel and completes in seconds, which allows verification to scale beyond non-modular engines, while still allowing the full power of SMT-based symbolic reasoning.

4 August 2024
Verified
Conference Paper
Open access
XXXieyang Xu
Xieyang Xu
YYYifei Yuan
Yifei Yuan
ZKZachary Kincaid
Zachary Kincaid
AKArvind Krishnamurthy
Arvind Krishnamurthy
RMRatul Mahajan
Ratul Mahajan
EZEnnan Zhai
Ennan Zhai
Relational network verification is a new approach for validating network changes. In contrast to traditional network verification, which analyzes specifications for a single network snapshot, it analyzes specifications that capture similarities and differences between two network snapshots (e.g., pre- and post-change snapshots). Relational specifications are compact and precise because they focus on the flows and paths that change between snapshots and then simply mandate that all other network behaviors "stay the same", without enumerating them. To achieve similar guarantees, single-snapshot specifications would need to enumerate all flow and path behaviors that are not expected to change in order to enable checking that nothing has accidentally changed. Such specifications are proportional to network size, which makes them impractical to generate for many real-world networks. We demonstrate the value of relational reasoning by developing Rela, a high-level relational specification language and verification tool for network changes. Rela compiles input specifications and network snapshot representations to finite state automata, and it then verifies compliance by checking automaton equivalence. Our experiments using data from a global backbone with over 103 routers find that Rela specifications need fewer than 10 terms for 93% of the complex, high-risk changes. Rela validates 80% of the changes within 20 minutes.