Léo Stefanesco
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Léo Stefanesco has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Siddharth Bhat
University of Cambridge, Cambridge, United Kingdom
3 shared publications - Tobias Grosser
University of Cambridge, Cambridge, United Kingdom
3 shared publications - Giovanni Bernardi
Université Paris Cité CNRS IRIF Paris France
2 shared publications - Ilaria Castellani
Inria, Université Côte d’Azur, France
2 shared publications - Paul Laforgue
Nomadic Labs, France
2 shared publications - Abdalrhman Mohamed
Stanford University, Stanford, USA
1 shared publication
Latest Publications
- Open Access
- 1 October 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 1794-1819
Sound and Complete Solving for Multi-width Parametric Bitvectors via Principled Reductions
Bitvectors are foundational for automated reasoning about programs, and fixed-width bitvector solvers (QF_BV) are fast and ubiquitous. However, the theory of parametric bitvectors (PBV), where widths are symbolic, is much less well understood. The theory of multi-width PBV, where expressions may involve n distinct symbolic widths (PBV_n), is particularly challenging. The only existing complete approach for bounded PBV (where all widths have a concrete upper bound) is exhaustive enumeration, requiring one call to a QF_BV solver for each of the exponentially many possible width assignments. This is a significant bottleneck in tools, such as Alive2 and Hydra, that formally reason about compiler optimizations. To address this problem, we first prove that any PBV_n formula can be reduced to an equisatisfiable mono-width (PBV_1) formula with only a linear increase in formula size. The key idea is to encode symbolic widths as bitmasks. This reduction lets us create two solvers for flavors of multi-width PBV. (1) A sound and complete bounded PBV solver, which instantiates the width variable in the PBV_1 formula to a concrete bound, and therefore requires only a single QF_BV solver call. In practice, this solver proves LLVM rewrites in seconds that enumeration fails to prove in hours. (2) By composing our reduction with existing automata-theoretic decision procedures for PBV_1, we obtain a new sound and complete decision procedure for a fragment of PBV_n with parametric widths. This new decidable fragment subsumes the prior state-of-the-art fragment of linear and bitwise operations, by adding support for zero and sign extension. All our solvers are implemented in Lean, with mechanized proofs of soundness and completeness for the unbounded solver. Empirically, we find that our equisatisfiable reduction from PBV_n to PBV_1 turns exponential enumeration into a single QF_BV query that nearly saturates standard PBV benchmarks (506 of 528 problems across all datasets), while our unbounded solvers solve 1.5x as many problems as the state of the art CVC5-based solver for all bitwidths.
- 1 October 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 1794-1819
Open AccessSound and Complete Solving for Multi-width Parametric Bitvectors via Principled Reductions
Bitvectors are foundational for automated reasoning about programs, and fixed-width bitvector solvers (QF_BV) are fast and ubiquitous. However, the theory of parametric bitvectors (PBV), where widths are symbolic, is much less well understood. The theory of multi-width PBV, where expressions may involve n distinct symbolic widths (PBV_n), is particularly challenging. The only existing complete approach for bounded PBV (where all widths have a concrete upper bound) is exhaustive enumeration, requiring one call to a QF_BV solver for each of the exponentially many possible width assignments. This is a significant bottleneck in tools, such as Alive2 and Hydra, that formally reason about compiler optimizations. To address this problem, we first prove that any PBV_n formula can be reduced to an equisatisfiable mono-width (PBV_1) formula with only a linear increase in formula size. The key idea is to encode symbolic widths as bitmasks. This reduction lets us create two solvers for flavors of multi-width PBV. (1) A sound and complete bounded PBV solver, which instantiates the width variable in the PBV_1 formula to a concrete bound, and therefore requires only a single QF_BV solver call. In practice, this solver proves LLVM rewrites in seconds that enumeration fails to prove in hours. (2) By composing our reduction with existing automata-theoretic decision procedures for PBV_1, we obtain a new sound and complete decision procedure for a fragment of PBV_n with parametric widths. This new decidable fragment subsumes the prior state-of-the-art fragment of linear and bitwise operations, by adding support for zero and sign extension. All our solvers are implemented in Lean, with mechanized proofs of soundness and completeness for the unbounded solver. Empirically, we find that our equisatisfiable reduction from PBV_n to PBV_1 turns exponential enumeration into a single QF_BV query that nearly saturates standard PBV benchmarks (506 of 528 problems across all datasets), while our unbounded solvers solve 1.5x as many problems as the state of the art CVC5-based solver for all bitwidths.
- Open Access
- 22 August 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
Constructive characterisations of the must -preorder for asynchrony
De Nicola and Hennessy's must -preorder is a liveness preserving refinement which states that a server q refines a server p if all clients satisfied by p are also satisfied by q . Owing to the universal quantification over clients, this definition does not yield a practical proof method, and alternative characterisations are necessary to reason over it. Finding these characterisations for asynchronous semantics, i.e. where outputs are non-blocking, has thus far proven to be a challenge, usually tackled via ad-hoc definitions. We show that the standard characterisations of the must -preorder carry over as they stand to asynchronous communication, if servers are enhanced to act as forwarders, ie they can input any message as long as they store it back into the shared buffer. Our development is constructive, is completely mechanised in Rocq, and is independent of any calculus: our results pertain to Selinger output-buffered agents with feedback. This is a class of Labelled Transition Systems that represents programs that communicate via a shared unordered buffer, as in asynchronous CCS or the asynchronous \(\pi\) -calculus. We show that the standard coinductive characterisation lets us prove in Rocq that such Labelled Transition Systems are related by the must -preorder. Finally, our proofs show that Brouwer's bar induction principle is a useful technique to reason on liveness preserving program transformations.- 22 August 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
Open AccessConstructive characterisations of the must -preorder for asynchrony
De Nicola and Hennessy's must -preorder is a liveness preserving refinement which states that a server q refines a server p if all clients satisfied by p are also satisfied by q . Owing to the universal quantification over clients, this definition does not yield a practical proof method, and alternative characterisations are necessary to reason over it. Finding these characterisations for asynchronous semantics, i.e. where outputs are non-blocking, has thus far proven to be a challenge, usually tackled via ad-hoc definitions. We show that the standard characterisations of the must -preorder carry over as they stand to asynchronous communication, if servers are enhanced to act as forwarders, ie they can input any message as long as they store it back into the shared buffer. Our development is constructive, is completely mechanised in Rocq, and is independent of any calculus: our results pertain to Selinger output-buffered agents with feedback. This is a class of Labelled Transition Systems that represents programs that communicate via a shared unordered buffer, as in asynchronous CCS or the asynchronous \(\pi\) -calculus. We show that the standard coinductive characterisation lets us prove in Rocq that such Labelled Transition Systems are related by the must -preorder. Finally, our proofs show that Brouwer's bar induction principle is a useful technique to reason on liveness preserving program transformations. - 6 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Asynchronous and relational soundness theorems for concurrent separation logic
Théorèmes de correction asynchrone et relationnelle de la logique de séparation concurrente: L'objet de cette thèse est la logique de séparation asynchrone, une logique de programme pour les langages de programmation concurrents et à mémoire partagée. Le lien entre une preuve d'un programme dans une logique de séparation concurrente et la sémantique de ce programme est exprimée par le théorème de correction de cette logique. Cette thèse introduit deux théorèmes de corrections. Le premier, le théorème de correction asynchrone, exprime dans le langage des jeux de gabarits sur des graphes asynchrones l'absence de courses des programmes bien spécifiés. L'autre étend la logique de séparation concurrente Iris avec un théorème de correction relationnel qui permet d'établir des simulations entre un programme concurrent concret et un modèle abstrait, formalisé comme un système de transition. Une application de ce théorème est la preuve de terminaison de programmes concurrent sous l'hypothèse d'un ordonnanceur équitable.
- 6 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Asynchronous and relational soundness theorems for concurrent separation logic
Théorèmes de correction asynchrone et relationnelle de la logique de séparation concurrente: L'objet de cette thèse est la logique de séparation asynchrone, une logique de programme pour les langages de programmation concurrents et à mémoire partagée. Le lien entre une preuve d'un programme dans une logique de séparation concurrente et la sémantique de ce programme est exprimée par le théorème de correction de cette logique. Cette thèse introduit deux théorèmes de corrections. Le premier, le théorème de correction asynchrone, exprime dans le langage des jeux de gabarits sur des graphes asynchrones l'absence de courses des programmes bien spécifiés. L'autre étend la logique de séparation concurrente Iris avec un théorème de correction relationnel qui permet d'établir des simulations entre un programme concurrent concret et un modèle abstrait, formalisé comme un système de transition. Une application de ce théorème est la preuve de terminaison de programmes concurrent sous l'hypothèse d'un ordonnanceur équitable.
- Open Access
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (OOPSLA2) , 2736-2758
Certified Decision Procedures for Width-Independent Bitvector Predicates
Bitvectors are foundational for automated reasoning. A few interactive theorem provers (ITP), such as Lean, have strong support for deciding fixed-width bitvector predicates by means of bitblasting. However, even these ITPs provide little automation for width-independent bitvector predicates. To fill this gap, we contribute novel, mechanized decision procedures for width-independent bitvector predicates in Lean. Classical algorithms to decide fragments of width-independent bitvector theory can be viewed from the lens of model checking, where the formula corresponds to an automaton and the correctness of the formula is a safety property. However, we cannot currently use this lens in mechanized proofs, as there are no executable, fast, and formally verified model checking algorithms that can be used interactively from within ITPs. To fill this gap, we mechanize key algorithms in the model checking literature: k -induction, automata reachability, automata emptiness checking, and automata minimization. Using these mechanized algorithms, we contribute scalable, mechanized, decision procedures for width-independent bitvector predicates. Furthermore, for controlled fragments of mixtures of arithmetic and bitwise operations which occur in the deobfuscation literature, we mechanize a recent fast algorithm (MBA-Blast), which outperforms the more general procedures on this fragment. Finally, we evaluate our decision procedures on benchmarks from classical compiler problems such as Hacker’s Delight and the LLVM peephole optimizer, as well as on equivalence checking problems for program obfuscation. Our tools solve 100% of Hacker’s Delight, two of our tools solve 100% of the deobfuscation dataset, and up to 27% of peephole rewrites extracted from LLVM’s peephole rewriting test suite. Our new decision procedures provide a push-button experience for width-independent bitvector reasoning in interactive theorem provers, and, more broadly, pave the way for foundational algorithms for fast, formally verified model checking.
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (OOPSLA2) , 2736-2758
Open AccessCertified Decision Procedures for Width-Independent Bitvector Predicates
Bitvectors are foundational for automated reasoning. A few interactive theorem provers (ITP), such as Lean, have strong support for deciding fixed-width bitvector predicates by means of bitblasting. However, even these ITPs provide little automation for width-independent bitvector predicates. To fill this gap, we contribute novel, mechanized decision procedures for width-independent bitvector predicates in Lean. Classical algorithms to decide fragments of width-independent bitvector theory can be viewed from the lens of model checking, where the formula corresponds to an automaton and the correctness of the formula is a safety property. However, we cannot currently use this lens in mechanized proofs, as there are no executable, fast, and formally verified model checking algorithms that can be used interactively from within ITPs. To fill this gap, we mechanize key algorithms in the model checking literature: k -induction, automata reachability, automata emptiness checking, and automata minimization. Using these mechanized algorithms, we contribute scalable, mechanized, decision procedures for width-independent bitvector predicates. Furthermore, for controlled fragments of mixtures of arithmetic and bitwise operations which occur in the deobfuscation literature, we mechanize a recent fast algorithm (MBA-Blast), which outperforms the more general procedures on this fragment. Finally, we evaluate our decision procedures on benchmarks from classical compiler problems such as Hacker’s Delight and the LLVM peephole optimizer, as well as on equivalence checking problems for program obfuscation. Our tools solve 100% of Hacker’s Delight, two of our tools solve 100% of the deobfuscation dataset, and up to 27% of peephole rewrites extracted from LLVM’s peephole rewriting test suite. Our new decision procedures provide a push-button experience for width-independent bitvector reasoning in interactive theorem provers, and, more broadly, pave the way for foundational algorithms for fast, formally verified model checking.
- Open Access
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (OOPSLA2) , 3259-3285
Interactive Bitvector Reasoning using Verified Bit-Blasting
Bit-blasting SMT solvers enable efficient automatic reasoning about bitvectors, which are fundamental for the verification of compiler backends, cryptographic algorithms, hardware designs and other soft- or hardware tasks. Despite the clear demand for efficient bitvector reasoning infrastructure and the impressive advancements in state-of-the-art bit-blasting SMT solvers such as Bitwuzla, effective bitvector reasoning within interactive theorem provers (ITPs) remains a challenge, hindering their use for mechanized proofs. Incomplete bitvector libraries, unavailable or only partially integrated decision procedures, complex and hard-to-bitblast operations, and limited integration with the host language prevent the wide adoption of bitvector reasoning in proving contexts. We introduce bv_decide: the first end-to-end verified bitblaster designed for interactive bitvector reasoning in a dependently-typed ITP . Our verified bitblaster is scalable, comes with a complete end-to-end proof (trusting only the Lean compiler and kernel), and is available as a proof tactic that allows interactive reasoning right from within a programming language, in our case Lean. We use Lean’s Functional But In-Place (FBIP) paradigm to efficiently encode our core data structures (e.g., AIGs), demonstrating that fast execution of an SMT solver need not come at the expense of rigorous formalization. We enable dependable interactive verification of user-written-code by basing Lean’s C-Style standard dataypes UInt/SInt on our bitvector type, adding a lowering from enums and structs to bitvectors to enable transparent bit-blasting support for composed types, and by offering an interactive tactic that either solves a goal or provides a counter-example. Moreover, we present the design of Lean’s canonical bitvector library, which supports all operations (with reasoning principles) for the SMT-LIB 2.7 standard (including overflow modeling), is fast-to-execute, and offers a comprehensive API and automation for bit-width-independent reasoning. We thoroughly evaluate our bit-blaster on a comprehensive set of benchmarks, including the full SMT-LIB dataset, where bv_decide solves more theorems than the state-of-the-art in verified bit-blasting, CoqQFBV. We also verify over 7000 SMT statements extracted from LLVM, providing the largest mechanized verification of LLVM rewrites to date, to our knowledge. By making bit-blasting bitvector reasoning a polished, well-supported, and interactive feature of modern ITPs, we enable effective, dependable white-box reasoning for bitvector-level verification.
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (OOPSLA2) , 3259-3285
Open AccessInteractive Bitvector Reasoning using Verified Bit-Blasting
Bit-blasting SMT solvers enable efficient automatic reasoning about bitvectors, which are fundamental for the verification of compiler backends, cryptographic algorithms, hardware designs and other soft- or hardware tasks. Despite the clear demand for efficient bitvector reasoning infrastructure and the impressive advancements in state-of-the-art bit-blasting SMT solvers such as Bitwuzla, effective bitvector reasoning within interactive theorem provers (ITPs) remains a challenge, hindering their use for mechanized proofs. Incomplete bitvector libraries, unavailable or only partially integrated decision procedures, complex and hard-to-bitblast operations, and limited integration with the host language prevent the wide adoption of bitvector reasoning in proving contexts. We introduce bv_decide: the first end-to-end verified bitblaster designed for interactive bitvector reasoning in a dependently-typed ITP . Our verified bitblaster is scalable, comes with a complete end-to-end proof (trusting only the Lean compiler and kernel), and is available as a proof tactic that allows interactive reasoning right from within a programming language, in our case Lean. We use Lean’s Functional But In-Place (FBIP) paradigm to efficiently encode our core data structures (e.g., AIGs), demonstrating that fast execution of an SMT solver need not come at the expense of rigorous formalization. We enable dependable interactive verification of user-written-code by basing Lean’s C-Style standard dataypes UInt/SInt on our bitvector type, adding a lowering from enums and structs to bitvectors to enable transparent bit-blasting support for composed types, and by offering an interactive tactic that either solves a goal or provides a counter-example. Moreover, we present the design of Lean’s canonical bitvector library, which supports all operations (with reasoning principles) for the SMT-LIB 2.7 standard (including overflow modeling), is fast-to-execute, and offers a comprehensive API and automation for bit-width-independent reasoning. We thoroughly evaluate our bit-blaster on a comprehensive set of benchmarks, including the full SMT-LIB dataset, where bv_decide solves more theorems than the state-of-the-art in verified bit-blasting, CoqQFBV. We also verify over 7000 SMT statements extracted from LLVM, providing the largest mechanized verification of LLVM rewrites to date, to our knowledge. By making bit-blasting bitvector reasoning a polished, well-supported, and interactive feature of modern ITPs, we enable effective, dependable white-box reasoning for bitvector-level verification.
- Open Access
- 1 May 2025
- Published by Springer Nature
- p. 88-116
Constructive characterisations of the MUST-preorder for asynchrony
De Nicola and Hennessy’s $$\textsc {must}$$ -preorder is a liveness preserving refinement which states that a server $$q$$ refines a server $$p$$ if all clients satisfied by $$p$$ are also satisfied by $$q$$ . Owing to the universal quantification over clients, this definition does not yield a practical proof method, and alternative characterisations are necessary to reason over it. Finding these characterisations for asynchronous semantics, i.e. where outputs are non-blocking, has thus far proven to be a challenge, usually tackled via ad-hoc definitions. We show that the standard characterisations of the $$\textsc {must}$$ -preorder carry over as they stand to asynchronous communication, if servers are enhanced to act as forwarders, i.e. they can input any message as long as they store it back into the shared buffer. Our development is constructive, is completely mechanised in Coq, and is independent of any calculus: our results pertain to Selinger output-buffered agents with feedback. This is a class of Labelled Transition Systems that captures programs that communicate via a shared unordered buffer, as in asynchronous CCS or the asynchronous $$\pi $$ -calculus. We show that the standard coinductive characterisation lets us prove in Coq that concrete programs are related by the $$\textsc {must}$$ -preorder. Finally, our proofs show that Brouwer’s bar induction principle is a useful technique to reason on liveness preserving program transformations.- 1 May 2025
- Published by Springer Nature
- p. 88-116
Open AccessConstructive characterisations of the MUST-preorder for asynchrony
De Nicola and Hennessy’s $$\textsc {must}$$ -preorder is a liveness preserving refinement which states that a server $$q$$ refines a server $$p$$ if all clients satisfied by $$p$$ are also satisfied by $$q$$ . Owing to the universal quantification over clients, this definition does not yield a practical proof method, and alternative characterisations are necessary to reason over it. Finding these characterisations for asynchronous semantics, i.e. where outputs are non-blocking, has thus far proven to be a challenge, usually tackled via ad-hoc definitions. We show that the standard characterisations of the $$\textsc {must}$$ -preorder carry over as they stand to asynchronous communication, if servers are enhanced to act as forwarders, i.e. they can input any message as long as they store it back into the shared buffer. Our development is constructive, is completely mechanised in Coq, and is independent of any calculus: our results pertain to Selinger output-buffered agents with feedback. This is a class of Labelled Transition Systems that captures programs that communicate via a shared unordered buffer, as in asynchronous CCS or the asynchronous $$\pi $$ -calculus. We show that the standard coinductive characterisation lets us prove in Coq that concrete programs are related by the $$\textsc {must}$$ -preorder. Finally, our proofs show that Brouwer’s bar induction principle is a useful technique to reason on liveness preserving program transformations. - Open Access
- 2 January 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 241-272
Trillium: Higher-Order Concurrent and Distributed Separation Logic for Intensional Refinement
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.
- 2 January 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 241-272
Open AccessTrillium: Higher-Order Concurrent and Distributed Separation Logic for Intensional Refinement
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.
- Open Access
- 12 January 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (POPL) , 1-32
Layered and object-based game semantics
Large-scale software verification relies critically on the use of compositional languages, semantic models, specifications, and verification techniques. Recent work on certified abstraction layers synthesizes game semantics, the refinement calculus, and algebraic effects to enable the composition of heterogeneous components into larger certified systems. However, in existing models of certified abstraction layers, compositionality is restricted by the lack of encapsulation of state. In this paper, we present a novel game model for certified abstraction layers where the semantics of layer interfaces and implementations are defined solely based on their observable behaviors. Our key idea is to leverage Reddy's pioneer work on modeling the semantics of imperative languages not as functions on global states but as objects with their observable behaviors. We show that a layer interface can be modeled as an object type (i.e., a layer signature) plus an object strategy. A layer implementation is then essentially a regular map, in the sense of Reddy, from an object with the underlay signature to that with the overlay signature. A layer implementation is certified when its composition with the underlay object strategy implements the overlay object strategy. We also describe an extension that allows for non-determinism in layer interfaces. After formulating layer implementations as regular maps between object spaces, we move to concurrency and design a notion of concurrent object space, where sequential traces may be identified modulo permutation of independent operations. We show how to express protected shared object concurrency, and a ticket lock implementation, in a simple model based on regular maps between concurrent object spaces.
- 12 January 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (POPL) , 1-32
Open AccessLayered and object-based game semantics
Large-scale software verification relies critically on the use of compositional languages, semantic models, specifications, and verification techniques. Recent work on certified abstraction layers synthesizes game semantics, the refinement calculus, and algebraic effects to enable the composition of heterogeneous components into larger certified systems. However, in existing models of certified abstraction layers, compositionality is restricted by the lack of encapsulation of state. In this paper, we present a novel game model for certified abstraction layers where the semantics of layer interfaces and implementations are defined solely based on their observable behaviors. Our key idea is to leverage Reddy's pioneer work on modeling the semantics of imperative languages not as functions on global states but as objects with their observable behaviors. We show that a layer interface can be modeled as an object type (i.e., a layer signature) plus an object strategy. A layer implementation is then essentially a regular map, in the sense of Reddy, from an object with the underlay signature to that with the overlay signature. A layer implementation is certified when its composition with the underlay object strategy implements the overlay object strategy. We also describe an extension that allows for non-determinism in layer interfaces. After formulating layer implementations as regular maps between object spaces, we move to concurrency and design a notion of concurrent object space, where sequential traces may be identified modulo permutation of independent operations. We show how to express protected shared object concurrency, and a ticket lock implementation, in a simple model based on regular maps between concurrent object spaces.