Back to search

University of British Columbia

COMET : tractable reactive program synthesis

Abstract

dc:description

Reactive programs are programs that process external events, such as signals and messages. Device drivers and cloud microservices are examples of reactive programs. Systems built from reactive programs are concurrent and exhibit a high degree of nondeterminism, making non-exhaustive testing inadequate. A higher-level language can be used to write a specification: a formal definition of a program’s desired behaviour. Such specifications may be easier to reason about, but proofs of the specification say nothing of a low-level implementation. Program synthesis is one way to bridge this gap. A synthesizer searches a space of candidate programs for an implementation that satisfies the specification. In general, the number of candidate programs is infinite, making synthesis undecidable. Even a bounded search, e.g., on program length, soon becomes intractable as that search space grows exponentially. This work introduces COMET, a system for synthesizing reactive programs from unbounded nondeterministic iterative transformations (UNITY) specifications. Recent work in symbolic execution and solver-aided synthesis has advanced the state of the art, but symbolic techniques also lead to exponential blowup. COMET seeks to avoid exponential blowup by constraining the search space and synthesizing in small steps. COMET synthesizes non-trivial programs for sequential and concurrent languages by applying three techniques: symbolic execution of the specification into guarded traces, intermediate target trace synthesis, and recursive synthesis of target expressions. To evaluate this approach, I synthesize Arduino and Verilog programs from UNITY specifications of the Paxos consensus proposer and acceptor roles.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Christopher

Rights

dc:rights
Statement dc:rights
  • Attribution-ShareAlike 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/77177

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Chen, Christopher. COMET : tractable reactive program synthesis. master's thesis, University of British Columbia, 2021. http://hdl.handle.net/2429/77177