Sensitivity analysis using type-based constraints - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

Sensitivity analysis using type-based constraints

(1) , (1, 2, 3) , (1) , (1) , (1)


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

Dates and versions

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



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⟩


103 View
0 Download



Gmail Facebook Twitter LinkedIn More