research-article

Measuring channel capacity to distinguish undue influence

Authors:

James Newsome,

Stephen McCamant,

Dawn SongAuthors Info & Claims

PLAS '09: Proceedings of the ACM SIGPLAN Fourth Workshop on Programming Languages and Analysis for Security

Pages 73 - 85

https://doi.org/10.1145/1554339.1554349

Published: 15 June 2009 Publication History

Get Access

Abstract

The channel capacity of a program is a quantitative measure of the amount of control that the inputs to a program have over its outputs. Because it corresponds to worst-case assumptions about the probability distribution over those inputs, it is particularly appropriate for security applications where the inputs are under the control of an adversary. We introduce a family of complementary techniques for measuring channel capacity automatically using a decision procedure (SAT or #SAT solver), which give either exact or narrow probabilistic bounds.

We then apply these techniques to the problem of analyzing false positives produced by dynamic taint analysis used to detect control-flow hijacking in commodity software. Dynamic taint analysis is based on the principle that an attacker should not be able to control values such as function pointers and return addresses, but it uses a simple binary approximation of control that commonly leads to both false positive and false negative errors. Based on channel capacity, we propose a more refined quantitative measure of influence, which can effectively distinguish between true attacks and false positives. We use a practical implementation of our influence measuring techniques, integrated with a dynamic taint analysis operating on x86 binaries, to classify tainting warnings produced by vulnerable network servers, such as those attacked by the Blaster and SQL Slammer worms. Influence measurement correctly distinguishes real attacks from tainting false positives, a task that would otherwise need to be done manually.

References

[1]

M. Backes, B. Köpf, and A. Rybalchenko. Automatic discovery and quantification of information leaks. In Proceedings of the 2009 IEEE Symposium on Security and Privacy, May 2009.

Digital Library

Google Scholar

[2]

K. J. Biba. Integrity considerations for secure computer systems. Technical Report MTR-3153, The Mitre Corporation, Apr. 1977.

Google Scholar

[3]

BitBlaze project. http://bitblaze.cs.berkeley.edu/.

Google Scholar

[4]

D. Brumley, J. Caballero, Z. Liang, J. Newsome, and D. Song. Towards automatic discovery of deviations in binary implementations with applications to error detection and fingerprint generation. In Proceedings of USENIX Security Symposium, Aug. 2007.

Digital Library

Google Scholar

[5]

M. Castro, M. Costa, and J.-P. Martin. Better bug reporting with better privacy. In 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 319--328, Mar. 2008.

Digital Library

Google Scholar

[6]

J. Chow, B. Pfaff, T. Garfinkel, K. Christopher, and M. Rosenblum. Understanding data lifetime via whole system simulation. In USENIX Security Symposium, August 2004.

Digital Library

Google Scholar

[7]

D. Clark, S. Hunt, and P. Malacaria. Quantitative analysis of the leakage of confidential data. In Proceedings of Quantitative Aspects of Programming Languages, 2001.

Google Scholar

[8]

D. Clark, S. Hunt, and P. Malacaria. Quantified interference for a while language. In Proceedings of Quantitative Aspects of Programming Languages, 2004.

Google Scholar

[9]

M. R. Clarkson, A. C. Myers, and F. B. Schneider. Belief in information flow. In 18th IEEE Computer Security Foundations Workshop, pages 31--45, June 2005.

Digital Library

Google Scholar

[10]

M. Costa, J. Crowcroft, M. Castro, A. Rowstron, L. Zhou, L. Zhang, and P. Barham. Vigilante: End-to-end containment of internet worms. In 20^th ACM Symposium on Operating System Principles (SOSP), 2005.

Digital Library

Google Scholar

[11]

J. R. Crandall and F. T. Chong. Minos: Control data attack prevention orthogonal to memory model. In Proceedings of the International Symposium on Microarchitecture, December 2004.

Digital Library

Google Scholar

[12]

J. R. Crandall, F. T. Chong, and S. F. Wu. Minos: Architectural support for protecting control data. Transactions on Architecture and Code Optimization (TACO), 3(4), Dec. 2006.

Digital Library

Google Scholar

[13]

D. E. Denning. Cryptography and Data Security. Addison-Wesley Publishing Company, Inc., 1982.

Digital Library

Google Scholar

[14]

E. Dijkstra. A Discipline of Programming. Prentice Hall, Englewood Cliffs, NJ, 1976.

Digital Library

Google Scholar

[15]

S. Dorai-Raj and S. Graves. Adjusting likelihood ratio confidence intervals for parameters near boundaries applied to the binomial. In Joint Statistical Meeting (JSM), Aug. 2006.

Google Scholar

[16]

M. Egele, C. Kruegel, E. Kirda, H. Yin, and D. Song. Dynamic spyware analysis. In Proceedings of USENIX Annual Technical Conference, June 2007.

Digital Library

Google Scholar

[17]

V. Ganesh and D. Dill. A decision procedure for bit-vectors and arrays. In Proceedings of the 19th International Conference on Computer Aided Verification, 2007.

Digital Library

Google Scholar

[18]

C. P. Gomes, A. Sabharwal, and B. Selman. Model counting: A new strategy for obtaining good bounds. In 21st AAAI Conference on Artificial Intelligence, 2006.

Digital Library

Google Scholar

[19]

J. W. Gray III. Toward a mathematical foundation for information flow security. In Proceedings of the 1991 IEEE Symposium on Security and Privacy, 1991.

Google Scholar

[20]

P. Malacaria. Assessing security threats of looping constructs. In Symposium on Principles of Programming Languages (POPL 2007), 2007.

Digital Library

Google Scholar

[21]

P. Malacaria and H. Chen. Lagrange multipliers and maximum information leakage in different observational models. In Workshop on Programming Languages and Analysis for Security, pages 135--146, June 2008.

Digital Library

Google Scholar

[22]

S. McCamant and M. D. Ernst. Quantitative information flow as network flow capacity. In Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation, 2008.

Digital Library

Google Scholar

[23]

J. K. Millen. Covert channel capacity. In Proceedings of the 1987 IEEE Symposium on Security and Privacy, 1987.

Crossref

Google Scholar

[24]

J. Newsome, D. Brumley, J. Franklin, and D. Song. Replayer: Automatic protocol replay by binary analysis. In Proceedings of the 13^th ACM Conference on Computer and and Communications Security (CCS), Oct. 2006.

Digital Library

Google Scholar

[25]

J. Newsome and D. Song. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In Proceedings of the 12th Annual Network and Distributed System Security Symposium (NDSS), Feb. 2005.

Google Scholar

[26]

G. Portokalidis, A. Slowinska, and H. Bos. Argos: an emulator for fingerprinting zero-day attacks. In Proceedings of the First European Conference on Systems (EuroSys), Apr. 2006.

Digital Library

Google Scholar

[27]

A. Sabelfeld and A. C. Myers. Language-based information-flow security. IEEE Journal on Selected Areas in Communications, 21(1):5--19, Jan. 2003.

Digital Library

Google Scholar

[28]

P. Saxena, P. Poosankam, S. McCamant, and D. Song. Loop-extended symbolic execution on binary programs. In International Symposium on Software Testing and Analysis (ISSTA), July 2009.

Digital Library

Google Scholar

[29]

D. Song, D. Brumley, H. Yin, J. Caballero, I. Jager, M. G. Kang, Z. Liang, J. Newsome, P. Poosankam, and P. Saxena. BitBlaze: A new approach to computer security via binary analysis. In International Conference on Information Systems Security, pages 1--25, Hyderabad, India, Dec. 2008. Keynote invited paper.

Digital Library

Google Scholar

[30]

G. E. Suh, J. Lee, and S. Devadas. Secure program execution via dynamic information flow tracking. In ASPLOS XI, Oct. 2004.

Digital Library

Google Scholar

[31]

N. Vachharajani, M. J. Bridges, J. Chang, R. Rangan, G. Ottoni, J. A. Blome, G. A. Reis, M. Vachharajani, and D. I. August. RIFLE: An architectural framework for user-centric information-flow security. In Proceedings of the 37th International Symposium on Microarchitecture, Dec. 2004.

Digital Library

Google Scholar

[32]

V. Venkatakrishnan, W. Xu, D. Du Varney, and R. Sekar. Provably correct runtime enforcement of non-interference properties. In 8th Internation Conference on Information and Communications Security (ICICS), Dec. 2006.

Digital Library

Google Scholar

[33]

W. Xu, S. Bhatkar, and R. Sekar. Taint-enhanced policy enforcement: a practical approach to defeat a wide range of attacks. In 15th USENIX Security Symposium, 2006.

Digital Library

Google Scholar

[34]

H. Yin, D. Song, M. Egele, C. Kruegel, and E. Kirda. Panorama: Capturing system-wide information flow for malware detection and analysis. In Proceedings of ACM Conference on Computer and Communication Security, Oct. 2007.

Digital Library

Google Scholar

Cited By

View all

Ma CWu DTan GKandemir MZhang D(2023)Quantifying and Mitigating Cache Side Channel Leakage with Differential SetProceedings of the ACM on Programming Languages10.1145/36228507:OOPSLA2(1470-1498)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622850
Saha SGhentiyala SLu SBang LBultan T(2023)Obtaining Information Leakage Bounds via Approximate Model CountingProceedings of the ACM on Programming Languages10.1145/35912817:PLDI(1488-1509)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591281
Cassel DWong WJia L(2023)NodeMedic: End-to-End Analysis of Node.js Vulnerabilities with Provenance Graphs2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP57164.2023.00068(1101-1127)Online publication date: Jul-2023
https://doi.org/10.1109/EuroSP57164.2023.00068
Show More Cited By

Index Terms

Recommendations

Measuring channel capacity to distinguish undue influence (abstract only)

The channel capacity of a program is a quantitative measure of the amount of control that the inputs to a program have over its outputs. Because it corresponds to worst-case assumptions about the probability distribution over those inputs, it is ...
Multiple-antenna capacity in correlated Rayleigh fading with channel covariance information

We analyze a mobile multiple input multiple output wireless link with M transmit and N receive antennas operating in a spatially correlated Rayleigh flat fading environment. Only the correlations between the channel coefficients are assumed to be known ...
Channel capacity of TAS/MRC system with adaptive transmission and channel estimation errors

This correspondence presents the impact of channel estimation error (CEE) on the channel capacity analysis of multiple-input multiple-output (MIMO) system employing transmit antenna selection and maximal ratio combining (TAS/MRC) under adaptive ...

Reviews

Reviewer: Bruce E. Litow

A taint analysis method for small program sections, based not on the size of the set of inputs to an output variable (numeric) but on the size of the set of possible output values of that variable, is introduced in this paper. More precisely, for a numeric variable V , the authors define its influence measure to be log2 Card( F ), where F is the set of values that can actually be obtained from any input. Newsome, McCamant, and Song regard the influence measure as a very simple channel capacity with the program section in the role of a channel. The main idea is to use the influence measure as a subtler indicator of tainting than the binary "taint/no-taint" approach that is widely used, which depends on input influence analysis. The paper's main claim is that influence measure significantly reduces both false positive and negative outcomes, relative to input taint methods. Obstacles to the application of the influence measure are carefully considered in the paper. A program section is converted (manually, it appears) to Boolean. Generally, this is possible if the section's behavior can be modeled in terms of a Turing machine running in a fixed time bound as a function of input length. The authors describe their technique, but do not state whether semi-automation has been attempted. If the behavior involves branching execution paths or quantifiers, then this simple conversion will not work. Given the Boolean for the section, a heuristic for estimating Card( F ) using a binary search-driven range analysis is described, but the more important idea of the paper is the application of #SAT solvers to compute Card( F ) as the number of satisfying truth assignments of the Boolean. Although there has been much work on #SAT solvers, since #SAT is P-complete, this approach seems to limit the section size. Much of the paper is given to experiments on program sections in terms of computation time to obtain log2 Card( F ) (so Card( F ) can vary over a range 2 k to 2 k +1 with only one bit variation in the influence measure) and resistance of the influence measure to false negatives and positives. There is much scope for further study of this approach to defending critical code. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PLAS '09: Proceedings of the ACM SIGPLAN Fourth Workshop on Programming Languages and Analysis for Security

June 2009

130 pages

ISBN:9781605586458

DOI:10.1145/1554339

Conference Chairs:
Stephen Chong
Harvard University
,
David Naumann
Stevens Institute of Technology

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

PLDI '09

Sponsor:

SIGPLAN

PLDI '09: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 15 - 21, 2009

Dublin, Ireland

Acceptance Rates

PLAS '09 Paper Acceptance Rate 8 of 19 submissions, 42%;

Overall Acceptance Rate 43 of 77 submissions, 56%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

99
Total Citations
View Citations
423
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)3

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ma CWu DTan GKandemir MZhang D(2023)Quantifying and Mitigating Cache Side Channel Leakage with Differential SetProceedings of the ACM on Programming Languages10.1145/36228507:OOPSLA2(1470-1498)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622850
Saha SGhentiyala SLu SBang LBultan T(2023)Obtaining Information Leakage Bounds via Approximate Model CountingProceedings of the ACM on Programming Languages10.1145/35912817:PLDI(1488-1509)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591281
Cassel DWong WJia L(2023)NodeMedic: End-to-End Analysis of Node.js Vulnerabilities with Provenance Graphs2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP57164.2023.00068(1101-1127)Online publication date: Jul-2023
https://doi.org/10.1109/EuroSP57164.2023.00068
Bechberger JWeigl A(2021)Upper Bound Computation of Information Leakages for Unbounded RecursionSoftware Engineering and Formal Methods10.1007/978-3-030-92124-8_10(160-177)Online publication date: 3-Dec-2021
https://doi.org/10.1007/978-3-030-92124-8_10
Biondi FKawamoto YLegay ATraonouez L(2019)Hybrid statistical estimation of mutual information and its application to information flowFormal Aspects of Computing10.1007/s00165-018-0469-z31:2(165-206)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00165-018-0469-z
FURUKAWA RISAWA RMORII MINOUE DNAKAO K(2018)FCReducer: Locating Symmetric Cryptographic Functions on the MemoryIEICE Transactions on Information and Systems10.1587/transinf.2017EDP7143E101.D:3(685-697)Online publication date: 2018
https://doi.org/10.1587/transinf.2017EDP7143
Chattopadhyay SRoychoudhury A(2018)Symbolic Verification of Cache Side-Channel FreedomIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.285840237:11(2812-2823)Online publication date: Nov-2018
https://doi.org/10.1109/TCAD.2018.2858402
Kim SMcCamant S(2018)Bit-Vector Model Counting Using Statistical EstimationTools and Algorithms for the Construction and Analysis of Systems10.1007/978-3-319-89960-2_8(133-151)Online publication date: 12-Apr-2018
https://doi.org/10.1007/978-3-319-89960-2_8
Fremont DRabe MSeshia SSingh SMarkovitch S(2017)Maximum model countingProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298023.3298133(3885-3892)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298023.3298133
Doychev GKöpf B(2017)Rigorous analysis of software countermeasures against cache attacksACM SIGPLAN Notices10.1145/3140587.306238852:6(406-421)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062388
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Measuring channel capacity to distinguish undue influence (abstract only)

Multiple-antenna capacity in correlated Rayleigh fading with channel covariance information

Channel capacity of TAS/MRC system with adaptive transmission and channel estimation errors

Reviews

Access critical reviews of Computing literature here