Pavel Panchekha

Pavel Panchekha

Auto-generated profile, based on publicly available information

Pavel Panchekha

University of Utah, Salt Lake City, USA

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

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

Representative Publications

View All Publications
3 June 2015 in ACM SIGPLAN Notices
Verified
Journal Article
Open access
PPPavel Panchekha
Pavel Panchekha
ASAlex Sanchez-Stern
Alex Sanchez-Stern
JWJames R. Wilcox
James R. Wilcox
ZTZachary Tatlock
Zachary Tatlock
Scientific and engineering applications depend on floating point arithmetic to approximate real arithmetic. This approximation introduces rounding error, which can accumulate to produce unacceptable results. While the numerical methods literature provides techniques to mitigate rounding error, applying these techniques requires manually rearranging expressions and understanding the finer details of floating point arithmetic. We introduce Herbie, a tool which automatically discovers the rewrites experts perform to improve accuracy. Herbie's heuristic search estimates and localizes rounding error using sampled points (rather than static error analysis), applies a database of rules to generate improvements, takes series expansions, and combines improvements for different input regions. We evaluated Herbie on examples from a classic numerical methods textbook, and found that Herbie was able to improve accuracy on each example, some by up to 60 bits, while imposing a median performance overhead of 40%. Colleagues in machine learning have used Herbie to significantly improve the results of a clustering algorithm, and a mathematical library has accepted two patches generated using Herbie.

3 June 2015 in ACM SIGPLAN Notices
Verified
Journal Article
Open access
JWJames R. Wilcox
James R. Wilcox
DWDoug Woos
Doug Woos
PPPavel Panchekha
Pavel Panchekha
ZTZachary Tatlock
Zachary Tatlock
XWXi Wang
Xi Wang
TAThomas Anderson
Thomas Anderson
Distributed systems are difficult to implement correctly because they must handle both concurrency and failures: machines may crash at arbitrary points and networks may reorder, drop, or duplicate packets. Further, their behavior is often too complex to permit exhaustive testing. Bugs in these systems have led to the loss of critical data and unacceptable service outages. We present Verdi, a framework for implementing and formally verifying distributed systems in Coq. Verdi formalizes various network semantics with different faults, and the developer chooses the most appropriate fault model when verifying their implementation. Furthermore, Verdi eases the verification burden by enabling the developer to first verify their system under an idealized fault model, then transfer the resulting correctness guarantees to a more realistic fault model without any additional proof burden. To demonstrate Verdi's utility, we present the first mechanically checked proof of linearizability of the Raft state machine replication algorithm, as well as verified implementations of a primary-backup replication system and a key-value store. These verified systems provide similar performance to unverified equivalents.

30 July 2018 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
PDF file
CNChandrakana Nandi
Chandrakana Nandi
JWJames R. Wilcox
James R. Wilcox
PPPavel Panchekha
Pavel Panchekha
TBTaylor Blau
Taylor Blau
DGDan Grossman
Dan Grossman
ZTZachary Tatlock
Zachary Tatlock
Desktop-manufacturing techniques like 3D printing are increasingly popular because they reduce the cost and complexity of producing customized objects on demand. Unfortunately, the vibrant communities of early adopters, often referred to as "makers," are not well-served by currently available software pipelines. Users today must compose idiosyncratic sequences of tools which are typically repurposed variants of proprietary software originally designed for expert specialists. This paper proposes fundamental programming-languages techniques to bring improved rigor, reduced complexity, and new functionality to the computer-aided design (CAD) software pipeline for applications like 3D-printing. Compositionality, denotational semantics, compiler correctness, and program synthesis all play key roles in our approach, starting from the perspective that solid geometry is a programming language. Specifically, we define a purely functional language for CAD called LambdaCAD and a polygon surface-mesh intermediate representation. We then define denotational semantics of both languages to 3D solids and a compiler from CAD to mesh accompanied by a proof of semantics preservation. We illustrate the utility of this foundation by developing a novel synthesis algorithm based on evaluation contexts to "reverse compile" difficult-to-edit meshes downloaded from online maker communities back to more-editable CAD programs. All our prototypes have been implemented in OCaml to enable further exploration of functional programming for desktop manufacturing.

17 February 2017
Verified
Book Chapter
Closed access
PDF file
NDNasrine Damouche
Nasrine Damouche
MMMatthieu Martel
Matthieu Martel
PPPavel Panchekha
Pavel Panchekha
CQChen Qiu
Chen Qiu
ASAlexander Sanchez-Stern
Alexander Sanchez-Stern
ZTZachary Tatlock
Zachary Tatlock

5 June 2014 in ACM SIGPLAN Notices
Verified
Journal Article
Open access
ASAdrian Sampson
Adrian Sampson
PPPavel Panchekha
Pavel Panchekha
TMTodd Mytkowicz
Todd Mytkowicz
KMKathryn S. McKinley
Kathryn S. McKinley
DGDan Grossman
Dan Grossman
LCLuis Ceze
Luis Ceze
Traditional assertions express correctness properties that must hold on every program execution. However, many applications have probabilistic outcomes and consequently their correctness properties are also probabilistic (e.g., they identify faces in images, consume sensor data, or run on unreliable hardware). Traditional assertions do not capture these correctness properties. This paper proposes that programmers express probabilistic correctness properties with probabilistic assertions and describes a new probabilistic evaluation approach to efficiently verify these assertions. Probabilistic assertions are Boolean expressions that express the probability that a property will be true in a given execution rather than asserting that the property must always be true. Given either specific inputs or distributions on the input space, probabilistic evaluation verifies probabilistic assertions by first performing distribution extraction to represent the program as a Bayesian network. Probabilistic evaluation then uses statistical properties to simplify this representation to efficiently compute assertion probabilities directly or with sampling. Our approach is a mix of both static and dynamic analysis: distribution extraction statically builds and optimizes the Bayesian network representation and sampling dynamically interprets this representation. We implement our approach in a tool called Mayhap for C and C++ programs. We evaluate expressiveness, correctness, and performance of Mayhap on programs that use sensors, perform approximate computation, and obfuscate data for privacy. Our case studies demonstrate that probabilistic assertions describe useful correctness properties and that Mayhap efficiently verifies them.

10 October 2019 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
PDF file
PPPavel Panchekha
Pavel Panchekha
MEMichael D. Ernst
Michael D. Ernst
ZTZachary Tatlock
Zachary Tatlock
SKShoaib Kamil
Shoaib Kamil
Automated verification can ensure that a web page satisfies accessibility, usability, and design properties regardless of the end user's device, preferences, and assistive technologies. However, state-of-the-art verification tools for layout properties do not scale to large pages because they rely on whole-page analyses and must reason about the entire page using the complex semantics of the browser layout algorithm. This paper introduces and formalizes modular layout proofs. A modular layout proof splits a monolithic verification problem into smaller verification problems, one for each component of a web page. Each component specification can use rely/guarantee-style preconditions to make it verifiable independently of the rest of the page and enabling reuse across multiple pages. Modular layout proofs scale verification to pages an order of magnitude larger than those supported by previous approaches. We prototyped these techniques in a new proof assistant, Troika. In Troika, a proof author partitions a page into components and writes specifications for them. Troika then verifies the specifications, and uses those specifications to verify whole-page properties. Troika also enables the proof author to verify different component specifications with different verification tools, leveraging the strengths of each. In a case study, we use Troika to verify a large web page and demonstrate a speed-up of 13--1469x over existing tools, taking verification time from hours to seconds. We develop a systematic approach to writing Troika proofs and demonstrate it on 8 proofs of properties from prior work to show that modular layout proofs are short, easy to write, and provide benefits over existing tools.