Simon Oddershede Gregersen

Simon Oddershede Gregersen

Auto-generated profile, based on publicly available information

Simon Oddershede Gregersen

New York University, New York, USA

Research Focus & Metrics

Academic Career Length

8Years (2019-Present)

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

Representative Publications

View All Publications
18 April 2020
Verified
Book Chapter
Open access
PDF file
MKMorten Krogh-Jespersen
Morten Krogh-Jespersen
ATAmin Timany
Amin Timany
MOMarit Edna Ohlenbusch
Marit Edna Ohlenbusch
SGSimon Oddershede Gregersen
Simon Oddershede Gregersen
LBLars Birkedal
Lars Birkedal
Building network-connected programs and distributed systems is a powerful way to provide scalability and availability in a digital, always-connected era. However, with great power comes great complexity. Reasoning about distributed systems is well-known to be difficult. In this paper we present , a novel framework based on separation logic supporting modular, node-local reasoning about concurrent and distributed systems. The logic is higher-order, concurrent, with higher-order store and network sockets, and is fully mechanized in the Coq proof assistant. We use our framework to verify an implementation of a load balancer that uses multi-threading to distribute load amongst multiple servers and an implementation of the two-phase-commit protocol with a replicated logging service as a client. The two examples certify that is well-suited for both horizontal and vertical modular reasoning.

2 January 2024 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
SGSimon Oddershede Gregersen
Simon Oddershede Gregersen
AAAlejandro Aguirre
Alejandro Aguirre
PHPhilipp G. Haselwarter
Philipp G. Haselwarter
JTJoseph Tassarotti
Joseph Tassarotti
LBLars Birkedal
Lars Birkedal
Probabilistic couplings are the foundation for many probabilistic relational program logics and arise when relating random sampling statements across two programs. In relational program logics, this manifests as dedicated coupling rules that, e.g ., say we may reason as if two sampling statements return the same value. However, this approach fundamentally requires aligning or “synchronizing” the sampling statements of the two programs which is not always possible. In this paper, we develop Clutch, a higher-order probabilistic relational separation logic that addresses this issue by supporting asynchronous probabilistic couplings. We use Clutch to develop a logical step-indexed logical relation to reason about contextual refinement and equivalence of higher-order programs written in a rich language with a probabilistic choice operator, higher-order local state, and impredicative polymorphism. Finally, we demonstrate our approach on a number of case studies. All the results that appear in the paper have been formalized in the Coq proof assistant using the Coquelicot library and the Iris separation logic framework.

4 January 2021 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
SGSimon Oddershede Gregersen
Simon Oddershede Gregersen
JBJohan Bay
Johan Bay
ATAmin Timany
Amin Timany
LBLars Birkedal
Lars Birkedal
We present an expressive information-flow control type system with recursive types, existential types, label polymorphism, and impredicative type polymorphism for a higher-order programming language with higher-order state. We give a novel semantic model of this type system and show that well-typed programs satisfy termination-insensitive noninterference. Our semantic approach supports compositional integration of syntactically well-typed and syntactically ill-typed---but semantically sound---components, which we demonstrate through several interesting examples. We define our model using logical relations on top of the Iris program logic framework; to capture termination-insensitivity, we develop a novel language-agnostic theory of Modal Weakest Preconditions. We formalize all of our theory and examples in the Coq proof assistant.

4 January 2021 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
LGLéon Gondelman
Léon Gondelman
SGSimon Oddershede Gregersen
Simon Oddershede Gregersen
ANAbel Nieto
Abel Nieto
ATAmin Timany
Amin Timany
LBLars Birkedal
Lars Birkedal
We present the first specification and verification of an implementation of a causally-consistent distributed database that supports modular verification of full functional correctness properties of clients and servers. We specify and reason about the causally-consistent distributed database in Aneris, a higher-order distributed separation logic for an ML-like programming language with network primitives for programming distributed systems. We demonstrate that our specifications are useful, by proving the correctness of small, but tricky, synthetic examples involving causal dependency and by verifying a session manager library implemented on top of the distributed database. We use Aneris's facilities for modular specification and verification to obtain a highly modular development, where each component is verified in isolation, relying only on the specifications (not the implementations) of other components. We have used the Coq formalization of the Aneris logic to formalize all the results presented in the paper in the Coq proof assistant.

2 January 2024 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
ATAmin Timany
Amin Timany
SGSimon Oddershede Gregersen
Simon Oddershede Gregersen
LSLéo Stefanesco
Léo Stefanesco
JHJonas Kastberg Hinrichsen
Jonas Kastberg Hinrichsen
LGLéon Gondelman
Léon Gondelman
LBLars Birkedal
Lars Birkedal
Expressive state-of-the-art separation logics rely on step-indexing to model semantically complex features and to support modular reasoning about imperative higher-order concurrent and distributed programs. Stepindexing comes, however, with an inherent cost: it restricts the adequacy theorem of program logics to a fairly simple class of safety properties. In this paper, we explore if and how intensional refinement is a viable methodology for strengthening higher-order concurrent (and distributed) separation logic to prove non-trivial safety and liveness properties. Specifically, we introduce Trillium, a language-agnostic separation logic framework for showing intensional refinement relations between traces of a program and a model. We instantiate Trillium with a concurrent language and develop Fairis, a concurrent separation logic, that we use to show liveness properties of concurrent programs under fair scheduling assumptions through a fair liveness-preserving refinement of a model. We also instantiate Trillium with a distributed language and obtain an extension of Aneris, a distributed separation logic, which we use to show refinement relations between distributed systems and TLA + models.

15 August 2024 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
AAAlejandro Aguirre
Alejandro Aguirre
PHPhilipp G. Haselwarter
Philipp G. Haselwarter
MMMarkus de Medeiros
Markus de Medeiros
KLKwing Hei Li
Kwing Hei Li
SGSimon Oddershede Gregersen
Simon Oddershede Gregersen
LBLars Birkedal
Lars Birkedal
Probabilistic programs often trade accuracy for efficiency, and thus may, with a small probability, return an incorrect result. It is important to obtain precise bounds for the probability of these errors, but existing verification approaches have limitations that lead to error probability bounds that are excessively coarse, or only apply to first-order programs. In this paper we present Eris, a higher-order separation logic for proving error probability bounds for probabilistic programs written in an expressive higher-order language. Our key novelty is the introduction of error credits , a separation logic resource that tracks an upper bound on the probability that a program returns an erroneous result. By representing error bounds as a resource, we recover the benefits of separation logic, including compositionality, modularity, and dependency between errors and program terms, allowing for more precise specifications. Moreover, we enable novel reasoning principles such as expectation-preserving error composition, amortized error reasoning, and error induction. We illustrate the advantages of our approach by proving amortized error bounds on a range of examples, including collision probabilities in hash functions, which allow us to write more modular specifications for data structures that use them as clients. We also use our logic to prove correctness and almost-sure termination of rejection sampling algorithms. All of our results have been mechanized in the Coq proof assistant using the Iris separation logic framework and the Coquelicot real analysis library.