Alejandro Aguirre

Alejandro Aguirre

Auto-generated profile, based on publicly available information

Alejandro Aguirre

Aarhus University, Aarhus, Denmark

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

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

Representative Publications

View All Publications
29 August 2017 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
PDF file
AAAlejandro Aguirre
Alejandro Aguirre
GBGilles Barthe
Gilles Barthe
MGMarco Gaboardi
Marco Gaboardi
DGDeepak Garg
Deepak Garg
PSPierre-Yves Strub
Pierre-Yves Strub
Relational program verification is a variant of program verification where one can reason about two programs and as a special case about two executions of a single program on different inputs. Relational program verification can be used for reasoning about a broad range of properties, including equivalence and refinement, and specialized notions such as continuity, information flow security or relative cost. In a higher-order setting, relational program verification can be achieved using relational refinement type systems, a form of refinement types where assertions have a relational interpretation. Relational refinement type systems excel at relating structurally equivalent terms but provide limited support for relating terms with very different structures. We present a logic, called Relational Higher Order Logic (RHOL), for proving relational properties of a simply typed λ-calculus with inductive types and recursive definitions. RHOL retains the type-directed flavour of relational refinement type systems but achieves greater expressivity through rules which simultaneously reason about the two terms as well as rules which only contemplate one of the two terms. We show that RHOL has strong foundations, by proving an equivalence with higher-order logic (HOL), and leverage this equivalence to derive key meta-theoretical properties: subject reduction, admissibility of a transitivity rule and set-theoretical soundness. Moreover, we define sound embeddings for several existing relational type systems such as relational refinement types and type systems for dependency analysis and relative cost, and we verify examples that were out of reach of prior work.

2 January 2019 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
PDF file
TSTetsuya Sato
Tetsuya Sato
AAAlejandro Aguirre
Alejandro Aguirre
GBGilles Barthe
Gilles Barthe
MGMarco Gaboardi
Marco Gaboardi
DGDeepak Garg
Deepak Garg
JHJustin Hsu
Justin Hsu
Probabilistic programming provides a convenient lingua franca for writing succinct and rigorous descriptions of probabilistic models and inference tasks. Several probabilistic programming languages, including Anglican, Church or Hakaru, derive their expressiveness from a powerful combination of continuous distributions, conditioning, and higher-order functions. Although very important for practical applications, these features raise fundamental challenges for program semantics and verification. Several recent works offer promising answers to these challenges, but their primary focus is on foundational semantics issues. In this paper, we take a step further by developing a suite of logics, collectively named PPV for proving properties of programs written in an expressive probabilistic higher-order language with continuous sampling operations and primitives for conditioning distributions. Our logics mimic the comfortable reasoning style of informal proofs using carefully selected axiomatizations of key results from probability theory. The versatility of our logics is illustrated through the formal verification of several intricate examples from statistics, probabilistic inference, and machine learning. We further show expressiveness by giving sound embeddings of existing logics. In particular, we do this in a parametric way by showing how the semantics idea of (unary and relational) ⊤⊤-lifting can be internalized in our logics. The soundness of PPV follows by interpreting programs and assertions in quasi-Borel spaces (QBS), a recently proposed variant of Borel spaces with a good structure for interpreting higher order probabilistic programs.

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
AAAlejandro Aguirre
Alejandro Aguirre
GBGilles Barthe
Gilles Barthe
JHJustin Hsu
Justin Hsu
BKBenjamin Lucien Kaminski
Benjamin Lucien Kaminski
JKJoost-Pieter Katoen
Joost-Pieter Katoen
CMChristoph Matheja
Christoph Matheja
Sensitivity properties describe how changes to the input of a program affect the output, typically by upper bounding the distance between the outputs of two runs by a monotone function of the distance between the corresponding inputs. When programs are probabilistic, the distance between outputs is a distance between distributions. The Kantorovich lifting provides a general way of defining a distance between distributions by lifting the distance of the underlying sample space; by choosing an appropriate distance on the base space, one can recover other usual probabilistic distances, such as the Total Variation distance. We develop a relational pre-expectation calculus to upper bound the Kantorovich distance between two executions of a probabilistic program. We illustrate our methods by proving algorithmic stability of a machine learning algorithm, convergence of a reinforcement learning algorithm, and fast mixing for card shuffling algorithms. We also consider some extensions: using our calculus to show convergence of Markov chains to the uniform distribution over states and an asynchronous extension to reason about pairs of program executions with different control flow.

19 August 2021 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
AAAlejandro Aguirre
Alejandro Aguirre
GBGilles Barthe
Gilles Barthe
MGMarco Gaboardi
Marco Gaboardi
DGDeepak Garg
Deepak Garg
SKShin-Ya Katsumata
Shin-Ya Katsumata
TSTetsuya Sato
Tetsuya Sato
Adversarial computations are a widely studied class of computations where resource-bounded probabilistic adversaries have access to oracles, i.e., probabilistic procedures with private state. These computations arise routinely in several domains, including security, privacy and machine learning. In this paper, we develop program logics for reasoning about adversarial computations in a higher-order setting. Our logics are built on top of a simply typed λ-calculus extended with a graded monad for probabilities and state. The grading is used to model and restrict the memory footprint and the cost (in terms of oracle calls) of computations. Under this view, an adversary is a higher-order expression that expects as arguments the code of its oracles. We develop unary program logics for reasoning about error probabilities and expected values, and a relational logic for reasoning about coupling-based properties. All logics feature rules for adversarial computations, and yield guarantees that are valid for all adversaries that satisfy a fixed resource policy. We prove the soundness of the logics in the category of quasi-Borel spaces, using a general notion of graded predicate liftings, and we use logical relations over graded predicate liftings to establish the soundness of proof rules for adversaries. We illustrate the working of our logics with simple but illustrative examples.

14 April 2018
Verified
Book Chapter
Open access
PDF file
AAAlejandro Aguirre
Alejandro Aguirre
GBGilles Barthe
Gilles Barthe
LBLars Birkedal
Lars Birkedal
ABAleš Bizjak
Aleš Bizjak
MGMarco Gaboardi
Marco Gaboardi
DGDeepak Garg
Deepak Garg
We extend the simply-typed guarded \(\lambda \)-calculus with discrete probabilities and endow it with a program logic for reasoning about relational properties of guarded probabilistic computations. This provides a framework for programming and reasoning about infinite stochastic processes like Markov chains. We demonstrate the logic sound by interpreting its judgements in the topos of trees and by using probabilistic couplings for the semantics of relational assertions over distributions on discrete types. The program logic is designed to support syntax-directed proofs in the style of relational refinement types, but retains the expressiveness of higher-order logic extended with discrete distributions, and the ability to reason relationally about expressions that have different types or syntactic structure. In addition, our proof system leverages a well-known theorem from the coupling literature to justify better proof rules for relational reasoning about probabilistic expressions. We illustrate these benefits with a broad range of examples that were beyond the scope of previous systems, including shift couplings and lump couplings between random walks.