Sensitivity analysis using type-based constraints

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.
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

Lien texte intégral

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

173