Declassification Policy for Program Complexity Analysis
Emmanuel Hainry, Bruce M. Kapron, Jean-Yves Marion, Romain Péchoux
Abstract
In automated complexity analysis, noninterference-based type systems statically guarantee, via soundness, the property that well-typed programs compute functions of a given complexity class, e.g., the class FP of functions computable in polynomial time. These characterizations are also extensionally complete - they capture all functions - but are not intensionally complete as some polytime algorithms are rejected. This impact on expressive power is an unavoidable cost of achieving a tractable characterization. To circumvent this issue, an avenue arising from security applications is to find a relaxation of noninterference based on a declassification mechanism that allows critical data to be released in a safe and controlled manner. Following this path, we present a new and intuitive declassification policy preserving FP-soundness and capturing strictly more programs than existing noninterference-based systems. We show the versatility of the approach: it also provides a new characterization of the class BFF of second-order polynomial time computable functions in a second-order imperative language, with first-order procedure calls. Type inference is tractable: it can be done in polynomial time.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
Related papers
- Compositional Security Definitions for Higher-Order Where DeclassificationJan Menz, Andrew K. Hirsch, Peixuan Li, Deepak GargOOPSLA 2023 · 3 citations
- ANOSY: approximated knowledge synthesis with refinement types for declassificationSankha Narayan Guria, Niki Vazou, Marco Guarnieri, James ParkerPLDI 2022 · 2 citations
- Assume but Verify: Deductive Verification of Leaked Information in Concurrent ApplicationsToby Murray, Mukesh Tiwari, Gidon Ernst, David A. NaumannCCS 2023
- Nonmalleable Information Flow ControlEthan Cecchetti, Andrew C. Myers, Owen ArdenCCS 2017 · 49 citations
- Program-mandering: Quantitative Privilege SeparationShen Liu, Dongrui Zeng, Yongzhe Huang, Frank Capobianco et al.CCS 2019 · 30 citations
