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
Type de document :
Communication dans un congrès
FPCDSL - 1st annual workshop on Functional programming concepts in domain-specific languages - 2013, 2013, Boston, BA, USA, United States. ACM, pp.43--50, 2013, Proceedings of the 1st annual workshop on Functional programming concepts in domain-specific languages. 〈10.1145/2505351.2505353〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00909341
Contributeur : Davide Sangiogi <>
Soumis le : mardi 26 novembre 2013 - 10:55:58
Dernière modification le : samedi 27 janvier 2018 - 01:30:59

Identifiants

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. ACM, pp.43--50, 2013, Proceedings of the 1st annual workshop on Functional programming concepts in domain-specific languages. 〈10.1145/2505351.2505353〉. 〈hal-00909341〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

183

Contact


archive-ouverte@inria.fr