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 evasion problem: 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 Lp cost (for certain p) 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 CISO risk management problem 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.