Sensitivity analysis using type-based constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Sensitivity analysis using type-based constraints

Résumé

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.
Fichier non déposé

Dates et versions

hal-00909341 , version 1 (26-11-2013)

Identifiants

Citer

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⟩

Collections

INRIA INRIA2
104 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More