Skip to main content

Applying Computational Learning Theory

Researcher: Avrim Blum


Applying Computational Learning Theory to Computer Security and Anomaly Detection

Many tasks in computer security require quickly detecting when inappropriate behavior is occurring, ideally from just a few observations and before an attacker has had a chance to do much harm. On the other hand, one also does not want to produce too many false positives, or constantly bother a user asking “do you really want to do that," since users will then either not trust or not want to use the system. Computational Learning Theory has developed a number of analysis techniques well-suited to these types of constraints, that can help produce tight bounds on the number of observations needed to achieve a given maximum false-positive rate. In addition, Computational Learning Theory has produced a number of adaptive algorithms that we believe can be applied to limit the number of times a user needs to be bothered in learning the appropriate set of actions to allow or disallow the user to perform.

The goals of this project are to use techniques from Computational Learning Theory more directly for problems of anomaly detection and “boundary setting". As one concrete example of a problem we are exploring, consider the problem of dynamically setting a 1-dimensional parameter, where larger values correspond to allowing more dangerous behavior, and smaller values correspond to restricting to less dangerous behavior on the part of a user. For example, this could be the number of ports connected to in a window of time, or different security settings of one's browser, etc. If the system is too conservative, then the user is constantly annoyed with “are you sure you want to do this?" requests; but if the system allows too much, then security is compromised. Learning techniques can potentially allow one to determine good settings based on a user's observed behavior, or to dynamically adjust settings in a way that achieves a good tradeoff between the security level and annoyance of the user. A related, more difficult setting would be the case of a tree-valued parameter, such as a set of allowed IP addresses. Here the problem of how to generalize from past observations is more difficult, but there are a number of techniques from machine learning theory that we think may be useful. These are some of the problems we intend to work on in this project.