A Scalable Shannon Entropy Estimator
A Scalable Shannon Entropy Estimator
复制标题
可扩展的香农熵估计器
DOI：
10.1007/978-3-031-13185-1_18
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Meel, K.S.
中科院分区：
文献类型：
--
作者：
Golia, P.;Juba, B.;Meel, K.S.
量化信息流（QIF）已经成为一种严格的方法来定量测量机密性; QIF的信息理论基础允许最终用户将计算的数量与对手获得所需机密信息所需的计算工作联系起来。在这项工作中，我们专注于一个给定的程序的香农熵的估计。作为第一步，我们专注于布尔公式捕捉inputsX和outputYof之间的关系的情况。这样的公式具有这样的性质，即对于X的每一个赋值，恰好存在一个满足的对Y的赋值。现有的技术需要model计数查询，其中。我们提出了第一个有效的算法技术，称为估计的香农熵与PAC风格的保证，即，所计算的估计被保证至少置信地位于基本事实的A因子内。此外，只进行计数和采样查询，其中，和，从而实现了模型计数查询数量的显着减少。我们证明了我们的算法框架的实际效率，通过详细的实验评估。我们的评估表明，所提出的框架规模的公式超出了以前已知的方法。
Quantified information flow (QIF) has emerged as a rigorous approach to quantitatively measure confidentiality; the information-theoretic underpinning of QIF allows the end-users to link the computed quantities with the computational effort required on the part of the adversary to gain access to desired confidential information. In this work, we focus on the estimation of Shannon entropy for a given program. As a first step, we focus on the case wherein a Boolean formulacaptures the relationship between inputsXand outputYof. Such formulashave the property that for every valuation toX, there exists exactly one valuation toYsuch thatis satisfied. The existing techniques requiremodel counting queries, where.We propose the first efficient algorithmic technique, calledto estimate the Shannon entropy ofwith PAC-style guarantees, i.e., the computed estimate is guaranteed to lie within a-factor of the ground truth with confidence at least. Furthermore,makes onlycounting and sampling queries, where, and, thereby achieving a significant reduction in the number of model counting queries. We demonstrate the practical efficiency of our algorithmic framework via a detailed experimental evaluation. Our evaluation demonstrates that the proposed framework scales to the formulas beyond the reach of the previously known approaches.
登录
查看更多内容
DOI：
10.1137/130945508
发表时间：
2012
期刊：
SIAM J. Comput.
影响因子：
--
作者：
C. Canonne;D. Ron;R. Servedio
通讯作者：
R. Servedio
用于模型计数和定量程序分析的子公式缓存
DOI：
10.1109/ase.2019.00050
发表时间：
2019
期刊：
2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE
影响因子：
--
作者：
Eiers, William;Saha, Seemanta;Brennan, Tegan;Bultan, Tevfik
通讯作者：
Bultan, Tevfik
DOI：
10.1109/sp.2018.00052
发表时间：
2018
期刊：
IEEE Symposium on Security and Privacy
影响因子：
--
作者：
Zhou, Ziqiao;Qian, Zhiyun;Reiter, Michael K.;Zhang, Yinqian
通讯作者：
Zhang, Yinqian
影响因子：
1.2
作者：
Clark, David;Hunt, Sebastian;Malacaria, Pasquale
通讯作者：
Malacaria, Pasquale
DOI：
10.1109/csf.2011.21
发表时间：
2011
期刊：
2011 IEEE 24th Computer Security Foundations Symposium
影响因子：
--
作者：
Pavol Cerný;K. Chatterjee;T. Henzinger
通讯作者：
T. Henzinger