Sensitivity analysis using type-based constraints

Loris d'Antoni 1 Marco Gaboardi 1, 2, 3 Emilio Jesús Gallego Arias 1 Andreas Haeberlen 1 Benjamin Pierce 1
1 Computer Science Department
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
3 DISI - Department of Computer Science and Engineering [Bologna]
Abstract : Function sensitivity ―- how much the result of a function can change with respect to linear changes in the input ―- is a key concept in many research areas. For instance, in differential privacy, one of the most common mechanisms for turning a (possibly privacy-leaking) query into a differentially private one involves establishing a boundon its sensitivity. One approach to sensitivity analysis is to use a type-based approach, extending the Hindley-Milner type system with functional types capturing statically the sensitivity of a functional expression. This approach ―- based on affine logic ―- has been used in Fuzz, a language for differentially private queries. We describe an automatic typed-based analysis that infers and checks the sensitivity annotations for simple functional programs. We have implemented a prototype in Fuzz's compiler. The first component of the analysis extends the typechecker to generate nonlinear constraints over the positive real numbers extended with infinity, which are then checked by the Z3 SMT solver; a solution for them will provide an upper bound on the sensitivity annotations and ensure the correctness of the annotations. We also present a simple sensitivity minimization procedure and demonstrate the effectiveness of the approach by analyzing several examples.
Keywords : differential privacy linear types sensitivity analysis smt solver special purpose language
Document type :
Conference papers
Complete list of metadatas
https://hal.inria.fr/hal-00909341
Contributor : Davide Sangiogi <>
Submitted on : Tuesday, November 26, 2013 - 10:55:58 AM
Last modification on : Saturday, January 27, 2018 - 1:30:59 AM

Identifiers

Collections

INRIA

Citation

Loris d'Antoni, Marco Gaboardi, Emilio Jesús Gallego Arias, Andreas Haeberlen, Benjamin Pierce. Sensitivity analysis using type-based constraints. FPCDSL - 1st annual workshop on Functional programming concepts in domain-specific languages - 2013, 2013, Boston, BA, USA, United States. pp.43--50, ⟨10.1145/2505351.2505353⟩. ⟨hal-00909341⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

209

Contact


archive-ouverte@inria.fr