![[2502.01160] Scalable Precise Computation of Shannon Entropy](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2502.01160] Scalable Precise Computation of Shannon Entropy
Summary
This paper presents a scalable tool, PSE, for precise computation of Shannon entropy, optimizing the process to enhance efficiency in quantitative information flow analyses.
Why It Matters
Understanding and quantifying information leakage is crucial in security and privacy contexts. This research improves the efficiency of entropy computation, which can significantly impact the development of secure systems and data protection methodologies.
Key Takeaways
- PSE tool significantly outperforms existing methods in entropy computation.
- Introduces a novel knowledge compilation language, DDAND, for efficient processing.
- Demonstrates a tenfold efficiency increase in solving benchmarks compared to previous tools.
Computer Science > Artificial Intelligence arXiv:2502.01160 (cs) [Submitted on 3 Feb 2025 (v1), last revised 18 Feb 2026 (this version, v3)] Title:Scalable Precise Computation of Shannon Entropy Authors:Yong Lai, Haolong Tong, Zhenghang Xu, Minghao Yin View a PDF of the paper titled Scalable Precise Computation of Shannon Entropy, by Yong Lai and 3 other authors View PDF HTML (experimental) Abstract:Quantitative information flow analyses (QIF) are a class of techniques for measuring the amount of confidential information leaked by a program to its public outputs. Shannon entropy is an important method to quantify the amount of leakage in QIF. This paper focuses on the programs modeled in Boolean constraints and optimizes the two stages of the Shannon entropy computation to implement a scalable precise tool PSE. In the first stage, we design a knowledge compilation language called \ADDAND that combines Algebraic Decision Diagrams and conjunctive decomposition. \ADDAND avoids enumerating possible outputs of a program and supports tractable entropy computation. In the second stage, we optimize the model counting queries that are used to compute the probabilities of outputs. We compare PSE with the state-of-the-art probabilistic approximately correct tool EntropyEstimation, which was shown to significantly outperform the previous precise tools. The experimental results demonstrate that PSE solved 56 more benchmarks compared to EntropyEstimation in a total of 459. For 98\% of t...
