Differentially-Private Control-Flow Node Coverage for Software Usage Analysis


Hailong Zhang, Sufian Latif, Raef Bassily, and Atanas Rountev, The Ohio State University


There are significant privacy concerns about the collection of usage data from deployed software. We propose a novel privacy-preserving solution for a problem of central importance to software usage analysis: control-flow graph coverage analysis over many deployed software instances. Our solution employs the machinery of differential privacy and its generalizations, and develops the following technical contributions: (1) a new notion of privacy guarantees based on a neighbor relation between control-flow graphs that prevents causality-based inference, (2) a new differentially-private algorithm design based on a novel definition of sensitivity with respect to differences between neighbors, (3) an efficient implementation of the algorithm using dominator trees derived from control-flow graphs, (4) a pruning approach to reduce the noise level by tightening the sensitivity bound using restricted sensitivity, and (5) a refined notion of relaxed indistinguishability based on distances between neighbors. Our evaluation demonstrates that these techniques can achieve practical accuracy while providing principled privacy-by-design guarantees.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {255330,
author = {Hailong Zhang and Sufian Latif and Raef Bassily and Atanas Rountev},
title = {{Differentially-Private} {Control-Flow} Node Coverage for Software Usage Analysis},
booktitle = {29th USENIX Security Symposium (USENIX Security 20)},
year = {2020},
isbn = {978-1-939133-17-5},
pages = {1021--1038},
url = {https://www.usenix.org/conference/usenixsecurity20/presentation/zhang-hailong},
publisher = {USENIX Association},
month = aug
Zhang PDF

Presentation Video