Youngju Song

Youngju Song

Auto-generated profile, based on publicly available information

Youngju Song

MPI-SWS, Saarbrücken, Germany

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

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

Representative Publications

View All Publications
9 January 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
YSYoungju Song
Youngju Song
MCMinki Cho
Minki Cho
DLDongjae Lee
Dongjae Lee
CHChung-Kil Hur
Chung-Kil Hur
MSMichael Sammler
Michael Sammler
DDDerek Dreyer
Derek Dreyer
Much work in formal verification of low-level systems is based on one of two approaches: refinement or separation logic. These two approaches have complementary benefits: refinement supports the use of programs as specifications, as well as transitive composition of proofs, whereas separation logic supports conditional specifications, as well as modular ownership reasoning about shared state. A number of verification frameworks employ these techniques in tandem, but in all such cases the benefits of the two techniques remain separate. For example, in frameworks that use relational separation logic to prove contextual refinement, the relational separation logic judgment does not support transitive composition of proofs, while the contextual refinement judgment does not support conditional specifications. In this paper, we propose Conditional Contextual Refinement (or CCR, for short), the first verification system to not only combine refinement and separation logic in a single framework but also to truly marry them together into a unified mechanism enjoying all the benefits of refinement and separation logic simultaneously. Specifically, unlike in prior work, CCR’s refinement specifications are both conditional (with separation logic pre- and post-conditions) and transitively composable. We implement CCR in Coq and evaluate its effectiveness on a range of interesting examples.

9 January 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
MSMichael Sammler
Michael Sammler
SSSimon Spies
Simon Spies
YSYoungju Song
Youngju Song
EDEmanuele D'OSualdo
Emanuele D'OSualdo
RKRobbert Krebbers
Robbert Krebbers
DDDerek Dreyer
Derek Dreyer
Prior work on multi-language program verification has achieved impressive results, including the compositional verification of complex compilers. But the existing approaches to this problem impose a variety of restrictions on the overall structure of multi-language programs (e.g. fixing the source language, fixing the set of involved languages, fixing the memory model, or fixing the semantics of interoperation). In this paper, we explore the problem of how to avoid such global restrictions. Concretely, we present DimSum : a new, decentralized approach to multi-language semantics and verification, which we have implemented in the Coq proof assistant. Decentralization means that we can define and reason about languages independently from each other (as independent modules communicating via events), but also combine and translate between them when necessary (via a library of combinators). We apply DimSum to a high-level imperative language Rec (with an abstract memory model and function calls), a low-level assembly language Asm (with a concrete memory model, arbitrary jumps, and syscalls), and a mathematical specification language Spec. We evaluate DimSum on two case studies: an Asm library extending Rec with support for pointer comparison, and a coroutine library for Rec written in Asm. In both cases, we show how DimSum allows the Asm libraries to be abstracted to Rec-level specifications, despite the behavior of the Asm libraries not being syntactically expressible in Rec itself. We also verify an optimizing multi-pass compiler from Rec to Asm, showing that it is compatible with these Asm libraries.

16 October 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
MCMinki Cho
Minki Cho
YSYoungju Song
Youngju Song
DLDongjae Lee
Dongjae Lee
LGLennard Gäher
Lennard Gäher
DDDerek Dreyer
Derek Dreyer
One of the most common tools for proving behavioral refinements between transition systems is the method of simulation proofs, which has been explored extensively over the past several decades. Stuttering simulations are an extension of traditional simulations—used, for example, in CompCert—in which either the source or target of the simulation is permitted to “stutter” (stay in place) while the other side steps forward. In the interest of ensuring soundness, however, existing stuttering simulations restrict proofs to only perform a finite number of stuttering steps before making synchronous progress —a step of reasoning in which both sides of the simulation progress forward together. This restriction guarantees that a terminating program cannot be proven to simulate a non-terminating one. In this paper, we observe that the requirement to eventually achieve synchronous progress is burdensome and, what’s more, unnecessary: it is possible to ensure soundness of stuttering simulations while only requiring asynchronous progress (progress on both sides of the simulation that may be achieved with only stuttering steps). Building on this observation, we develop a new simulation technique we call FreeSim (short for “freely-stuttering simulations”), mechanized in Coq, and we demonstrate its effectiveness on a range of interesting case studies. These include a simplification of the meta-theory of CompCert, as well as the DTrees library, which enriches the ITrees (Interaction Trees) library with dual non-determinism.

6 June 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
DLDongjae Lee
Dongjae Lee
MCMinki Cho
Minki Cho
JKJinwoo Kim
Jinwoo Kim
SMSoonwon Moon
Soonwon Moon
YSYoungju Song
Youngju Song
CHChung-Kil Hur
Chung-Kil Hur
Fairness properties, which state that a sequence of bad events cannot happen infinitely before a good event takes place, are often crucial in program verification. However, general methods for expressing and reasoning about various kinds of fairness properties are relatively underdeveloped compared to those for safety properties. This paper proposes FOS (Fair Operational Semantics), a theory capable of expressing arbitrary notions of fairness as an operational semantics and reasoning about these notions of fairness. In addition, FOS enables thread-local reasoning about fairness by providing thread-local simulation relations equipped with separation- logic-style resource algebras. We verify a ticket lock implementation and a client of the ticket lock under weak memory concurrency as an example, which requires reasoning about different notions of fairness including fairness of a scheduler, fairness of the ticket lock implementation, and even fairness of weak memory. The theory of FOS, as well as the examples in the paper, are fully formalized in Coq.

15 August 2024 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
YSYoungju Song
Youngju Song
DLDongjae Lee
Dongjae Lee
One successful approach to verifying programs is refinement, where one establishes that the implementation ( e.g. , in C) behaves as specified in its mathematical specification. In this approach, the end result (a whole implementation refines a whole specification) is often established via composing multiple “small” refinements. In this paper, we focus on the task of composing refinements. Our key observation is a novel correspondence between the task of composing refinements and the task of proving entailments in modern separation logic. This correspondence is useful. First, it unlocks tools and abstract constructs developed for separation logic, greatly streamlining the composition proof. Second, it uncovers a fundamentally new verification strategy. We address the key challenge in establishing the correspondence with a novel use of angelic non-determinism . Guided by the correspondence, we develop RCL (Refinement Composition Logic) , a logic dedicated to composing refinements. All our results are formalized in Coq.

7 January 2025 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
YKYonghyun Kim
Yonghyun Kim
MCMinki Cho
Minki Cho
JLJaehyung Lee
Jaehyung Lee
JKJinwoo Kim
Jinwoo Kim
TYTaeyoung Yoon
Taeyoung Yoon
CHChung-Kil Hur
Chung-Kil Hur
Although there have been many approaches for developing formal memory models that support integerpointer casts, previous approaches share the drawback that they are not designed for end-to-end verification ,failing to support some important source-level coding patterns, justify some backend optimizations, or lack a source-level logic for program verification. This paper presents Archmage, a framework for integer-pointer casting designed for end-to-end verification,supporting a wide range of source-level coding patterns, backend optimizations, and a formal notion of out-ofmemory. To facilitate end-to-end verification via Archmage, we also present two systems based on Archmage: CompCertCast, an extension of CompCert with Archmage to bring a full verified compilation chain to integer-pointer casting programs, and Archmage logic, a source-level logic for reasoning about integerpointer casts. We design CompCertCast such that the overhead from formally supporting integer-pointer casts is mitigated, and illustrate the effectiveness of Archmage logic by verifying an xor-based linked-list implementation, Together, our paper presents the first practical end-to-end verification chain for programs containing integer-pointer casts.