Secure Learning and Learning for Security: Research in the Intersection
Benjamin I. P. Rubinstein
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2010-71
May 13, 2010
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-71.pdf
Statistical Machine Learning is used in many real-world systems in which adversaries are incentivized to attack the learner, motivating the urgent need for a better understanding of the security vulnerabilities of adaptive systems. Conversely, research in Computer Security stands to reap great benefits by leveraging learning for building adaptive defenses and even designing intelligent attacks on existing systems. This dissertation contributes new results in the intersection of Machine Learning and Security, relating to both of these complementary research agendas.
The first part of this dissertation considers Machine Learning under the lens of Computer Security, where the goal is to learn in the presence of an adversary. Two large case-studies on email spam filtering and network-wide anomaly detection explore adversaries that manipulate a learner by poisoning its training data. In both cases the effects of increasing the information or the control available to the adversary are explored; and effective counter-measures are thoroughly evaluated, including a method based on Robust Statistics for the network anomaly detection domain.
The second class of attack explored on learning systems, studies the <i>evasion problem</i>: an attacker searches for a negative instance of almost-minimal distance to some target positive, by submitting a small number of queries to the classifier. Efficient query algorithms are developed for almost-minimizing <i>L<sub>p</sub></i> cost (for certain <i>p</i>) over any classifier partitioning feature space into two classes, one of which is convex. The results show that learning the decision boundary is sufficient, but not necessary for evasion, and can require much greater query complexity.
The third class of attack aims to violate the confidentiality of the learner's training data given access to a learned hypothesis. Mechanisms for releasing Support Vector Machine (SVM) classifiers are developed. Stability of the SVM is used to prove differential privacy; bounds on utility are established for the mechanisms. In the case of learning with translation-invariant kernels corresponding to infinite-dimensional feature spaces, a result from large-scale learning enables a finite encoding of the SVM while maintaining utility and privacy. Finally lower bounds on achievable differential privacy are derived for any mechanism that well-approximates the SVM.
The second part of this dissertation considers Security under the lens of Machine Learning. The first application of Machine Learning is to a learning-based reactive defense. The <i>CISO risk management problem</i> is modeled as a repeated game in which the defender must allocate security budget to the edges of a graph in order to minimize the additive profit or return on attack (ROA) enjoyed by an attacker. By reducing to results from Online Learning, it is shown that the profit/ROA from attacking the reactive strategy approaches that of attacking the best fixed proactive strategy over time. Moreover in many cases, it is shown that the reactive defender greatly outperforms proactive approaches.
The second application of Machine Learning to Security is for an attack on open-source software. When an open-source project releases a new version, vulnerabilities in previous versions are disclosed. Using features of diffs in the project's repository, labeled by such disclosures, an attacker can train a model for discriminating between security patches and non-security patches. As new patches land in the repository, the attacker can use the model to rank patches according to likelihood of being a security fix, and examine the ordered patches until finding a security patch. For an 8 month period of Firefox 3's development history it is shown that an SVM-assisted attacker need only examine 1-2 patches per day to increase the aggregate window of vulnerability by 5 months.
Advisors: Peter Bartlett
BibTeX citation:
@phdthesis{Rubinstein:EECS-2010-71,
Author= {Rubinstein, Benjamin I. P.},
Title= {Secure Learning and Learning for Security: Research in the Intersection},
School= {EECS Department, University of California, Berkeley},
Year= {2010},
Month= {May},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-71.html},
Number= {UCB/EECS-2010-71},
Abstract= {Statistical Machine Learning is used in many real-world systems in which adversaries are incentivized to attack the learner, motivating the urgent need for a better understanding of the security vulnerabilities of adaptive systems. Conversely, research in Computer Security stands to reap great benefits by leveraging learning for building adaptive defenses and even designing intelligent attacks on existing systems. This dissertation contributes new results in the intersection of Machine Learning and Security, relating to both of these complementary research agendas.
The first part of this dissertation considers Machine Learning under the lens of Computer Security, where the goal is to learn in the presence of an adversary. Two large case-studies on email spam filtering and network-wide anomaly detection explore adversaries that manipulate a learner by poisoning its training data. In both cases the effects of increasing the information or the control available to the adversary are explored; and effective counter-measures are thoroughly evaluated, including a method based on Robust Statistics for the network anomaly detection domain.
The second class of attack explored on learning systems, studies the <i>evasion problem</i>: an attacker searches for a negative instance of almost-minimal distance to some target positive, by submitting a small number of queries to the classifier. Efficient query algorithms are developed for almost-minimizing <i>L<sub>p</sub></i> cost (for certain <i>p</i>) over any classifier partitioning feature space into two classes, one of which is convex. The results show that learning the decision boundary is sufficient, but not necessary for evasion, and can require much greater query complexity.
The third class of attack aims to violate the confidentiality of the learner's training data given access to a learned hypothesis. Mechanisms for releasing Support Vector Machine (SVM) classifiers are developed. Stability of the SVM is used to prove differential privacy; bounds on utility are established for the mechanisms. In the case of learning with translation-invariant kernels corresponding to infinite-dimensional feature spaces, a result from large-scale learning enables a finite encoding of the SVM while maintaining utility and privacy. Finally lower bounds on achievable differential privacy are derived for any mechanism that well-approximates the SVM.
The second part of this dissertation considers Security under the lens of Machine Learning. The first application of Machine Learning is to a learning-based reactive defense. The <i>CISO risk management problem</i> is modeled as a repeated game in which the defender must allocate security budget to the edges of a graph in order to minimize the additive profit or return on attack (ROA) enjoyed by an attacker. By reducing to results from Online Learning, it is shown that the profit/ROA from attacking the reactive strategy approaches that of attacking the best fixed proactive strategy over time. Moreover in many cases, it is shown that the reactive defender greatly outperforms proactive approaches.
The second application of Machine Learning to Security is for an attack on open-source software. When an open-source project releases a new version, vulnerabilities in previous versions are disclosed. Using features of diffs in the project's repository, labeled by such disclosures, an attacker can train a model for discriminating between security patches and non-security patches. As new patches land in the repository, the attacker can use the model to rank patches according to likelihood of being a security fix, and examine the ordered patches until finding a security patch. For an 8 month period of Firefox 3's development history it is shown that an SVM-assisted attacker need only examine 1-2 patches per day to increase the aggregate window of vulnerability by 5 months.},
}
EndNote citation:
%0 Thesis %A Rubinstein, Benjamin I. P. %T Secure Learning and Learning for Security: Research in the Intersection %I EECS Department, University of California, Berkeley %D 2010 %8 May 13 %@ UCB/EECS-2010-71 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-71.html %F Rubinstein:EECS-2010-71