Recognition: unknown
Compositional security definitions for higher-order where declassification
Pith reviewed 2026-05-10 03:20 UTC · model grok-4.3
The pith
Logical relations model where-declassification security for higher-order programs by halting indistinguishability after relevant releases.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We use logical relations to build a model of where declassification in which we stop enforcing indistinguishability once a relevant declassification has occurred. The resulting definition is compositional for higher-order programs and provides more security than the most closely related prior definition from the lower-order setting.
What carries the argument
Logical relations model for where declassification that stops enforcing indistinguishability after a relevant declassification occurs.
If this is right
- The definition is compositional, so secure higher-order components can be combined without losing the security guarantee.
- It applies to intensional information-flow properties that restrict declassification to specific program locations.
- It is strictly stronger than the best existing definition for the lower-order case.
- The model directly supplies a security definition rather than only a type system or enforcement mechanism.
Where Pith is reading between the lines
- The same stop-after-relevant-release idea could be adapted to other declassification dimensions such as what or when policies.
- Static analysis tools for higher-order languages might incorporate similar logical-relation checks to verify declassification locations.
- Language designers could expose explicit declassification annotations so that the relevant points are syntactically clear to both programmers and verifiers.
Load-bearing premise
Logical relations correctly capture the intended intensional security property for higher-order programs and relevant declassifications can be identified without circularity.
What would settle it
A higher-order program that satisfies the logical-relations definition yet leaks information via a non-relevant declassification point, or an intuitively secure program that the definition rejects.
Figures
read the original abstract
To ensure programs do not leak private data, we often want to be able to provide formal guarantees ensuring such data is handled correctly. Often, we cannot keep such data secret entirely; instead programmers specify how private data may be declassified. While security definitions for declassification exist, they mostly do not handle higher-order programs. In fact, in the higher-order setting no compositional security definition exists for intensional information-flow properties such as where declassification, which allows declassification in specific parts of a program. We use logical relations to build a model (and thus security definition) of where declassification. The key insight required for our model is that we must stop enforcing indistinguishability once a \emph{relevant declassification} has occurred. We show that the resulting security definition provides more security than the most related previous definition, which is for the lower-order setting. This paper is an extended version of the paper of the same name published at OOPSLA 2023 ([21]).
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a compositional security definition for where-declassification in higher-order programs by means of a logical-relations model. The central modeling decision is to stop enforcing indistinguishability between executions once a relevant declassification has occurred; the resulting predicate is claimed to be strictly stronger than the closest prior (first-order) definition while remaining compositional for intensional information-flow properties.
Significance. If the logical-relation construction is free of circularity and the accompanying proofs are correct, the result would be a useful advance for language-based security. It supplies the first compositional intensional declassification policy that scales to higher-order languages, which is a prerequisite for modular verification of secure functional programs. The explicit use of logical relations and the post-declassification relaxation of indistinguishability are the technically novel elements.
major comments (2)
- [§4.2] §4.2 (Definition of the logical relation, especially the clause for the declassify primitive and the function case): the predicate that decides whether a declassification is 'relevant' must be shown to be defined independently of the indistinguishability relation being constructed. In the higher-order setting a declassification inside a function body is reached only after an application whose argument may itself be protected; if relevance is resolved by consulting the final security predicate, the definition is circular and the claimed compositionality and strict strengthening relative to the first-order baseline do not follow. Please supply an explicit lemma or syntactic characterisation establishing independence.
- [Theorem 5.3] Theorem 5.3 (comparison with the lower-order baseline): the proof that every program secure under the new definition is also secure under the prior definition (and that the converse fails) rests on the non-circularity of the relevance predicate. If relevance can depend on which pairs of terms are deemed indistinguishable, the inclusion may not hold. A concrete counter-example or a separate well-foundedness argument is required.
minor comments (2)
- [Abstract / §1] The abstract and introduction repeatedly use the phrase 'more security' without stating the precise preorder (e.g., 'every program secure under the new definition is secure under the old one, but not conversely'). A one-sentence clarification would help readers.
- [§2] Notation for the logical relation (e.g., the use of Γ ⊢ e1 ~ e2 : τ) is introduced without an explicit table of all metavariables; a small glossary or table in §2 would improve readability.
Simulated Author's Rebuttal
We thank the referee for the careful and constructive review. The points raised about potential circularity in the logical-relation definition are substantive and we address each one directly below. We will incorporate an explicit independence lemma and a strengthened well-foundedness argument in the revised manuscript.
read point-by-point responses
-
Referee: [§4.2] §4.2 (Definition of the logical relation, especially the clause for the declassify primitive and the function case): the predicate that decides whether a declassification is 'relevant' must be shown to be defined independently of the indistinguishability relation being constructed. In the higher-order setting a declassification inside a function body is reached only after an application whose argument may itself be protected; if relevance is resolved by consulting the final security predicate, the definition is circular and the claimed compositionality and strict strengthening relative to the first-order baseline do not follow. Please supply an explicit lemma or syntactic characterisation establishing independence.
Authors: The relevance predicate in Definition 4.2 is defined purely syntactically: a declassification occurrence is relevant precisely when its label appears in the where-clause of the enclosing declassify term and the declassified value is used in a position that can affect subsequent observable outputs according to the program syntax and label lattice. This characterisation makes no reference to the indistinguishability relation being constructed. Function applications are handled by the standard logical-relation clause for arrow types, which applies the relation to the argument and then evaluates the body; relevance is checked only after the application has been performed, but the check itself remains syntactic. We will add an explicit lemma (Lemma 4.5 in the revision) that proves independence by induction on term structure, together with a syntactic characterisation that lists the conditions under which a declassify is deemed relevant without consulting any semantic relation. This removes any possibility of circularity while preserving the higher-order compositionality result. revision: yes
-
Referee: [Theorem 5.3] Theorem 5.3 (comparison with the lower-order baseline): the proof that every program secure under the new definition is also secure under the prior definition (and that the converse fails) rests on the non-circularity of the relevance predicate. If relevance can depend on which pairs of terms are deemed indistinguishable, the inclusion may not hold. A concrete counter-example or a separate well-foundedness argument is required.
Authors: Because the relevance predicate is syntactic (as established by the new Lemma 4.5), the inclusion direction of Theorem 5.3 holds by a straightforward simulation argument: any pair of terms related by our higher-order relation is also related by the first-order baseline once the same declassifications are recognised as relevant. The converse fails because our definition stops enforcing indistinguishability after a relevant declassification, which is a strictly stronger policy. We will augment the proof of Theorem 5.3 with an explicit well-foundedness argument (by induction on the derivation of the logical relation) that confirms the construction never consults the final indistinguishability predicate when deciding relevance. No counter-example is possible under the syntactic definition; we will include a short paragraph explaining why any attempt to construct a circular dependence would violate the syntactic characterisation. revision: partial
Circularity Check
No circularity: logical-relations model is independently constructed
full rationale
The paper defines a security predicate for higher-order where-declassification via a logical relation that ceases to enforce indistinguishability after a relevant declassification. This modeling choice is introduced as an explicit insight rather than derived from or equated to any fitted parameter, prior self-citation, or the final predicate itself. No equations reduce the relevance predicate to the indistinguishability relation being defined, and the claimed improvement over the first-order baseline follows from direct comparison of the two relations. The OOPSLA 2023 self-citation is only for the extended version and carries no load-bearing uniqueness theorem or ansatz. The construction therefore remains self-contained against external logical-relations machinery.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Logical relations can be used to define security properties compositionally in higher-order languages
Reference graph
Works this paper leans on
-
[1]
2004.Semantics of Types for Mutable State
Amal Ahmed. 2004.Semantics of Types for Mutable State. Ph.D. Dissertation. Princeton University. https://www.ccs.neu.edu/home/amal/ahmedthesis.pdf
2004
-
[2]
Amal Ahmed, Derek Dreyer, and Andreas Rossberg. 2009. State-dependent representation independence. InProceedings of the 36th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2009, Savannah, GA, USA, January 21-23, 2009, Zhong Shao and Benjamin C. Pierce (Eds.). ACM, 340–353. doi:10.1145/1480881.1480925
-
[3]
Andrew W. Appel and David A. McAllester. 2001. An indexed model of recursive types for foundational proof-carrying code.ACM Trans. Program. Lang. Syst.23, 5 (2001), 657–683. doi:10.1145/504709.504712
-
[4]
Aslan Askarov and Andrei Sabelfeld. 2007A. Localized delimited release: combining the what and where dimensions of information release. InProceedings of the 2007 Workshop on Programming Languages and Analysis for Security, PLAS 2007, San Diego, California, USA, June 14, 2007, Michael W. Hicks (Ed.). ACM, 53–60. doi:10.1145/1255329.1255339
-
[5]
Aslan Askarov and Andrei Sabelfeld. 2007B. Gradual Release: Unifying Declassification, Encryption and Key Release Policies. In2007 IEEE Symposium on Security and Privacy (S&P 2007), 20-23 May 2007, Oakland, California, USA. IEEE Computer Society, 207–221. doi:10.1109/SP.2007.22
-
[6]
Anindya Banerjee, David A. Naumann, and Stan Rosenberg. 2008. Expressive Declassification Policies and Modular Static Enforcement. In2008 IEEE Symposium on Security and Privacy (S&P 2008), 18-21 May 2008, Oakland, California, USA. IEEE Computer Society, 339–353. doi:10.1109/SP.2008.20
-
[7]
Niklas Broberg and David Sands. 2006. Flow Locks: Towards a Core Calculus for Dynamic Flow Policies. In Programming Languages and Systems, 15th European Symposium on Programming, ESOP 2006, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006, Vienna, Austria, 38 Jan Menz, Andrew K. Hirsch, Peixuan Li, and Deepak G...
-
[8]
Niklas Broberg and David Sands. 2009. Flow-sensitive semantics for dynamic information flow policies. In Proceedings of the 2009 Workshop on Programming Languages and Analysis for Security, PLAS 2009, Dublin, Ireland, 15-21 June, 2009, Stephen Chong and David A. Naumann (Eds.). ACM, 101–112. doi:10.1145/ 1554339.1554352
-
[9]
Niklas Broberg and David Sands. 2010. Paralocks: role-based information flow control and beyond. In Proceedings of the 37th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2010, Madrid, Spain, January 17-23, 2010, Manuel V. Hermenegildo and Jens Palsberg (Eds.). ACM, 431–444. doi:10.1145/1706299.1706349
-
[10]
Raimil Cruz, Tamara Rezk, Bernard P. Serpette, and Éric Tanter. 2017. Type Abstraction for Relaxed Noninterference. In31st European Conference on Object-Oriented Programming, ECOOP 2017, June 19- 23, 2017, Barcelona, Spain (LIPIcs, Vol. 74), Peter Müller (Ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 7:1–7:27. doi:10.4230/LIPIcs.ECOOP.2017.7
-
[11]
Dan Frumin, Robbert Krebbers, and Lars Birkedal. 2021. Compositional Non-Interference for Fine-Grained Concurrent Programs. In42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021. IEEE, 1416–1433. doi:10.1109/SP40001.2021.00003
-
[12]
Lennard Gäher, Michael Sammler, Simon Spies, Ralf Jung, Hoang-Hai Dang, Robbert Krebbers, Jeehoon Kang, and Derek Dreyer. 2022. Simuliris: a separation logic framework for verifying concurrent program optimizations.Proc. ACM Program. Lang.6, POPL (2022), 1–31. doi:10.1145/3498689
-
[13]
Simon Oddershede Gregersen, Johan Bay, Amin Timany, and Lars Birkedal. 2021. Mechanized logical relations for termination-insensitive noninterference.Proc. ACM Program. Lang.5, POPL (2021), 1–29. doi:10.1145/3434291
-
[14]
Chung-Kil Hur, Derek Dreyer, Georg Neis, and Viktor Vafeiadis. 2012. The marriage of bisimulations and Kripke logical relations. InProceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA, January 22-28, 2012, John Field and Michael Hicks (Eds.). ACM, 59–72. doi:10.1145/2103656.2103666
-
[15]
Ralf Jung, Robbert Krebbers, Jacques-Henri Jourdan, Ales Bizjak, Lars Birkedal, and Derek Dreyer. 2018. Iris from the ground up: A modular foundation for higher-order concurrent separation logic.J. Funct. Program.28 (2018), e20. doi:10.1017/S0956796818000151
-
[16]
Ralf Jung, David Swasey, Filip Sieczkowski, Kasper Svendsen, Aaron Turon, Lars Birkedal, and Derek Dreyer
-
[17]
Iris: Monoids and Invariants as an Orthogonal Basis for Concurrent Reasoning. InProceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, January 15-17, 2015, Sriram K. Rajamani and David Walker (Eds.). ACM, 637–650. doi:10.1145/2676726.2676980
-
[18]
Elisavet Kozyri and Fred B. Schneider. 2020. RIF: Reactive information flow labels.J. Comput. Secur.28, 2 (2020), 191–228. doi:10.3233/JCS-191316
-
[19]
Peng Li and Steve Zdancewic. 2005. Downgrading policies and relaxed noninterference. InProceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2005, Long Beach, California, USA, January 12-14, 2005, Jens Palsberg and Martín Abadi (Eds.). ACM, 158–170. doi:10.1145/1040305.1040319
-
[20]
Heiko Mantel and David Sands. 2004. Controlled Declassification Based on Intransitive Noninterference. In ProgrammingLanguages andSystems: SecondAsian Symposium,APLAS2004, Taipei, Taiwan,November 4-6,
2004
-
[21]
Proceedings (Lecture Notes in Computer Science, Vol. 3302), Wei-Ngan Chin (Ed.). Springer, 129–145. doi:10.1007/978-3-540-30477-7_9
-
[22]
Ana Almeida Matos and Gérard Boudol. 2005. On Declassification and the Non-Disclosure Policy. In18th IEEEComputerSecurityFoundationsWorkshop,(CSFW-182005),20-22June2005,Aix-en-Provence,France. IEEE Computer Society, 226–240. doi:10.1109/CSFW.2005.21
-
[23]
2025.Compositional Security Definitions for Higher-Order Where Declassification - Technical Appendix
Jan Menz, Andrew Hirsch, Peixuan Li, and Deepak Garg. 2025.Compositional Security Definitions for Higher-Order Where Declassification - Technical Appendix. Technical Report. https://gitlab.mpi- sws.org/Quarkbeast/lambda-where-fullproofs/-/raw/main/Technical_Appendix.pdf
2025
-
[24]
Hirsch, Peixuan Li, and Deepak Garg
Jan Menz, Andrew K. Hirsch, Peixuan Li, and Deepak Garg. 2023. Compositional Security Definitions for Higher-Order Where Declassification.Proc. ACM Program. Lang.7, OOPSLA1, Article 89 (April 2023), 28 pages. doi:10.1145/3586041 Compositional security definitions for higher-order where declassification 39
-
[25]
Minh Ngo, David A. Naumann, and Tamara Rezk. 2020. Type-Based Declassification for Free. InFormal Methods and Software Engineering - 22nd International Conference on Formal Engineering Methods, ICFEM 2020, Singapore, Singapore, March 1-3, 2021, Proceedings (Lecture Notes in Computer Science, Vol. 12531), Shang-Wei Lin, Zhe Hou, and Brendan P. Mahony (Eds....
-
[26]
In38st IEEE Computer Security Foundations Symposium, CSF 2025, Santa Cruz, CA, USA, June 16-20, 2025
VineetRajani,AlexColeman,andHrutvikKanabar.2025.Agradedmodalapproachtosemanticdeclassification. In38st IEEE Computer Security Foundations Symposium, CSF 2025, Santa Cruz, CA, USA, June 16-20, 2025. IEEE Computer Society
2025
-
[27]
VineetRajaniandDeepakGarg.2018. TypesforInformationFlowControl:LabelingGranularityandSemantic Models. In31st IEEE Computer Security Foundations Symposium, CSF 2018, Oxford, United Kingdom, July 9-12, 2018. IEEE Computer Society, 233–246. doi:10.1109/CSF.2018.00024
-
[28]
Andrei Sabelfeld and Andrew C. Myers. 2003. A Model for Delimited Information Release. InSoftware Security - Theories and Systems, Second Mext-NSF-JSPS International Symposium, ISSS 2003, Tokyo, Japan, November 4-6, 2003, Revised Papers (Lecture Notes in Computer Science, Vol. 3233), Kokichi Futatsugi, Fumio Mizoguchi, and Naoki Yonezaki (Eds.). Springer,...
-
[29]
The Coq Development Team. 2022. The Coq Proof Assistant. doi:10.5281/zenodo.5846982
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.