Plan Discovery

Chain patterns reflect causality relations according to background knowledge. Discovering chain patterns can have important applications. Particularly, chain patterns can be used to find the motives (i.e., goals) from a collection of intrusion logs. These patterns can be used to detect security flaws in a system. Since chain patterns describe structural patterns reflecting causal relations, inter-related actions can be rapidly identified. As a result, we believe that chain patterns can be computed efficiently for large collections of input data. To support this claim, we recently performed experiments with Greenberg's UNIX command traces, which consists of thousands of commands. We were able to compute chain patterns on this large, real-world data collection in less than a minute even though we ran our experiments on a PC (1.6GHz machine, 512MBytes RAM). This in-itself is a surprising result since our algorithm for learning chain patterns is knowledge-intensive, using a variation of Golden & Etzioni representation of actions.

Here are a few resources used in this project:

Last updated: Tue Jan 28 14:49:51 EST 2003