Measuring channel capacity to distinguish undue influence

James Newsome, Stephen Mccamant, Dawn Song

Research output: Chapter in Book/Report/Conference proceedingConference contribution

65 Scopus citations

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. 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. Copyrightc 2009.

Original languageEnglish (US)
Title of host publicationPLAS'09 - Proceedings of the ACM SIGPLAN 4th Workshop on Programming Languages and Analysis for Security
Pages73-85
Number of pages13
DOIs
StatePublished - 2009
EventACM SIGPLAN 4th Workshop on Programming Languages and Analysis for Security, PLAS 2009 - Dublin, Ireland
Duration: Jun 15 2009Jun 15 2009

Publication series

NamePLAS'09 - Proceedings of the ACM SIGPLAN 4th Workshop on Programming Languages and Analysis for Security

Other

OtherACM SIGPLAN 4th Workshop on Programming Languages and Analysis for Security, PLAS 2009
CountryIreland
CityDublin
Period6/15/096/15/09

Keywords

  • Channel capacity
  • Model counting
  • Quantitative information flow

Fingerprint Dive into the research topics of 'Measuring channel capacity to distinguish undue influence'. Together they form a unique fingerprint.

  • Cite this

    Newsome, J., Mccamant, S., & Song, D. (2009). Measuring channel capacity to distinguish undue influence. In PLAS'09 - Proceedings of the ACM SIGPLAN 4th Workshop on Programming Languages and Analysis for Security (pp. 73-85). (PLAS'09 - Proceedings of the ACM SIGPLAN 4th Workshop on Programming Languages and Analysis for Security). https://doi.org/10.1145/1554339.1554349