# US 8,544,087 B1 · Methods of unsupervised anomaly detection using a geometric framework > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,544,087 B1 - Document ID: US8544087B1 - Status: Granted - Kind: B1 - Application number: 12/022,425 - Filed: 2008-01-30 - Granted: 2013-09-24 - Earliest claimed: 2001-12-14 - Assignees: The Trustess of Columbia University in the City of New York - Applicants: Eleazar Eskin; Andrew Oliver Arnold; Michael Prerau; Leonid Portnoy; Salvatore J. Stolfo - Inventors: Eleazar Eskin; Andrew Oliver Arnold; Michael Prerau; Leonid Portnoy; Salvatore J. Stolfo - Web page: https://patentgrep.com/patent/US8544087B1 ## CPC - H04L 41/06: Management of faults, events, alarms or notifications - G06F 21/552: {involving long-term monitoring or reporting} - H04L 41/142: using statistical or mathematical methods - H04L 63/1416: {Event detection, e.g. attack signature detection} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for unsupervised anomaly detection, which are algorithms that are designed to process unlabeled data. Data elements are mapped to a feature space which is typically a vector space . Anomalies are detected by determining which points lies in sparse regions of the feature space. Two feature maps are used for mapping data elements to a feature apace. A first map is a data-dependent normalization feature map which we apply to network connections. A second feature map is a spectrum kernel which we apply to system call traces. ## Claims ### Claim 1 A method for unsupervised detection of an anomaly in the operation of a computer system comprising the steps of: (a) receiving a set of unlabeled data instances which do not indicate any anomaly occurrence, the set of unlabeled data instances corresponding to a computer operation and having features; (b) implicitly mapping the set of unlabeled data instances to a feature space; (c) calculating one or more sparse regions in the feature space; and (d) designating one or more data instances from the set of unlabeled data instances as an anomaly if said one or more data instances is located in said one or more sparse regions of the feature space. ### Claim 2 (depends on 1) The method of claim 1, wherein receiving the set of unlabeled data instances comprises receiving the set of unlabeled data instances from an audit stream. ### Claim 3 (depends on 2) The method of claim 2, wherein receiving the set of unlabeled data instances comprises receiving a set of system call trace data. ### Claim 4 (depends on 2) The method of claim 2, wherein receiving the set of unlabeled data instances comprises receiving a set of network connections records data. ### Claim 5 (depends on 4) The method of claim 4, wherein receiving the set of unlabeled data instances comprises receiving a sequence of TCP packets. ### Claim 6 (depends on 5) The method of claim 5, wherein the features of the TCP packets comprise at least one of a duration of the network connection, a protocol type, and number of byte transferred by the connection, and an indication of the status of the connection. ### Claim 7 (depends on 1) The method of claim 1, wherein implicitly mapping the set of unlabeled data instances comprises implicitly mapping the set of unlabeled data instances to a vector space. ### Claim 8 (depends on 1) The method of claim 1, wherein implicitly mapping the set of unlabeled data instances comprises normalizing the set of unlabeled data instances based on respective values of features of the set of unlabeled data instances. ### Claim 9 (depends on 8) The method of claim 8, further comprising normalizing each data instance in the set of unlabeled data instances based on a corresponding number of standard deviations of each data instance from a mean of the set of unlabeled data instances. ### Claim 10 (depends on 1) The method of claim 1, wherein implicitly mapping the set of unlabeled data instances comprises applying a convolution kernel to the set of unlabeled data instances. ### Claim 11 (depends on 10) The method of claim 10, wherein applying a convolution kernel comprises applying a spectrum kernel to the set of unlabeled data instances. ### Claim 12 (depends on 1) The method of claim 1, further comprising, after implicitly mapping the set of unlabeled data instances to a feature space, associating each data instance in the set of unlabeled data instances with one of a plurality of clusters. ### Claim 13 (depends on 12) The method of claim 12, further comprising, determining a distance between a selected data instance and a nearest cluster in the plurality of clusters. ### Claim 14 (depends on 13) The method of claim 13, further comprising, if the distance between the selected data instance and the nearest cluster is less than or equal to a predetermined cluster width, associating the selected data instance with the selected cluster. ### Claim 15 (depends on 13) The method of claim 13, further comprising, if the distance between the selected data instance and the selected cluster is greater than the cluster width, creating a new cluster and associating the selected data instance with the new cluster. ### Claim 16 (depends on 12) The method of claim 12, further comprising, determining a percentage of clusters having the greatest number of data instances respectively associated therewith. ### Claim 17 (depends on 16) The method of claim 16, wherein the percentage of clusters having the greatest number of data instances are labeled as dense regions in the feature space and wherein the remaining clusters are labeled as sparse regions in the feature space. ### Claim 18 (depends on 17) The method of claim 17, wherein designating one or more data instances as an anomaly comprises associating each data instance in the set of unlabeled data instances with a respective cluster. ### Claim 19 (depends on 1) The method of claim 1, further comprising, determining a sum of distances between a selected data instance and k nearest data instances to the selected data instance, wherein k is a predetermined value. ### Claim 20 (depends on 19) The method of claim 19, wherein determining the sum of the distances comprises determining a nearest cluster as a cluster corresponding to a shortest distance between the respective center of the cluster and the selected data instance. ### Claim 21 (depends on 20) The method of claim 20, further comprising, if a distance between the selected data instance and each data instance in the nearest cluster is less than a predetermined minimum distance, designating the point the cluster as one of the k nearest neighbors. ### Claim 22 (depends on 21) The method of claim 21, wherein designating one or more data instances as an anomaly comprises determining whether sum of the distances to the k nearest neighbors exceeds a predetermined threshold. ### Claim 23 (depends on 1) The method of claim 1, wherein designating one or more data instances as an anomaly comprises determining a decision function to separate the set of data instances from an origin and computing the decision function. ### Claim 24 A method for unsupervised detection of an anomaly in the operation of a computer system based on a set of unlabeled data instances corresponding to computer operation and having features, comprising the steps of (a) receiving a set of unlabeled data instances which do not indicate any anomaly occurrence; (b) implicitly mapping the set of unlabeled data instances to a feature space comprising normalizing the set of unlabeled data instances based on respective values of the features; (c) calculating one or more sparse regions in the feature space; and (d) designating one or more data instances from the set of unlabeled data instances as an anomaly if said one or more data instances is located in said one or more sparse regions of the feature space. ### Claim 25 (depends on 24) The method of claim 24, wherein receiving the set of unlabeled data instances comprises receiving the set of unlabeled data instances from an audit stream. ### Claim 26 (depends on 25) The method of claim 25, wherein receiving the set of unlabeled data instances comprises receiving a set of network connections records data. ### Claim 27 (depends on 26) The method of claim 26, wherein receiving a set of unlabeled data instances comprises receiving a sequence of TCP packets. ### Claim 28 (depends on 27) The method of claim 27, wherein the features of the TCP packets comprise at least one of a duration of the network connection, a protocol type, and number of byte transferred by the connection, and an indication of the status of the connection. ### Claim 29 (depends on 24) The method of claim 24, wherein normalizing the set of unlabeled data instances comprises implicitly mapping the set of unlabeled data instances to a vector space. ### Claim 30 (depends on 29) The method of claim 29, wherein normalizing the set of unlabeled data instances comprises normalizing each data instance in the set of unlabeled data instances based on a corresponding number of standard deviations of each data instance from a mean of the set of unlabeled data instances. ### Claim 31 (depends on 24) The method of claim 24, further comprising, after normalizing the set of unlabeled data instances, associating each data instance in the set of unlabeled data instances with a plurality of clusters. ### Claim 32 (depends on 31) The method of claim 31, further comprising, determining a distance between a selected data instance and a nearest cluster in the plurality of clusters. ### Claim 33 (depends on 32) The method of claim 32, further comprising, if the distance between the selected data instance and the nearest cluster is less than or equal to a predetermined cluster width, associating the selected data instance with the selected cluster. ### Claim 34 (depends on 32) The method of claim 32, further comprising, if the distance between the selected data instance and the selected cluster is greater than the cluster width, creating a new cluster and associating the selected data instance with the new cluster. ### Claim 35 (depends on 31) The method of claim 31, further comprising, determining a percentage of clusters having the greatest number of data instances respectively associated therewith. ### Claim 36 (depends on 35) The method of claim 35, wherein the percentage of clusters having the greatest number of data instances are labeled as dense regions in the feature space and wherein the remaining clusters are labeled as sparse regions in the feature space. ### Claim 37 (depends on 36) The method of claim 36, wherein designating one or more data instances as an anomaly comprises associating each data instance in the set of unlabeled data instances with a respective cluster. ### Claim 38 (depends on 24) The method of claim 24, further comprising, determining a sum of distances between a selected data instance and k nearest data instances to the selected data instance, wherein k is a predetermined value. ### Claim 39 (depends on 38) The method of claim 38, wherein determining the sum of the distances comprises determining a nearest cluster as a cluster corresponding to a shortest distance between the respective center of the cluster and the selected data instance. ### Claim 40 (depends on 39) The method of claim 39, further comprising, if a distance between the selected data instance and each data instance in the nearest cluster is less than a predetermined minimum distance, designating the point the cluster as one of the k nearest neighbors. ### Claim 41 (depends on 40) The method of claim 40, wherein designating one or more data instances as an anomaly comprises determining whether sum of the distances to the k nearest neighbors exceeds a predetermined threshold. ### Claim 42 (depends on 24) The method of claim 24, wherein designating one or more data instances as an anomaly comprises determining a decision function to separate the set of data instances from an origin, and computing the decision function. ### Claim 43 A method for unsupervised detection of an anomaly in the operation of a computer system based on a set of unlabeled data instances corresponding to computer operation and having features, comprising the step of: (a) receiving a set of unlabeled data instances which do not indicate any anomaly occurrence, the set of unlabeled data instances corresponding to a computer operation and having features; (b) implicitly mapping the set of unlabeled data instances to a feature space comprising applying a string kernel to the set of unlabeled data instances; (c) calculating one or more sparse regions in the feature space; and (d) designating one or more data instances from the set of unlabeled data instances as an anomaly if said one or more data instances is located in said one or more sparse regions of the feature space. ### Claim 44 (depends on 43) The method of claim 43, wherein receiving the set of unlabeled data instances comprises receiving the set of unlabeled data instances from an audit stream. ### Claim 45 (depends on 44) The method of claim 44, wherein receiving a set of unlabeled data instances comprises receiving a set of system call trace data. ### Claim 46 (depends on 44) The method of claim 44, wherein applying a string kernel to the set of unlabeled data instances comprises applying a spectrum kernel to the set of unlabeled data instances. ### Claim 47 (depends on 43) The method of claim 43, further comprising, after applying a string kernel to the set of unlabeled data instances, associating each data instance in the set of unlabeled data instances with a plurality of clusters. ### Claim 48 (depends on 47) The method of claim 47, further comprising, determining a distance between a selected data instance and a nearest cluster in the plurality of clusters. ### Claim 49 (depends on 48) The method of claim 48, further comprising, if the distance between the selected data instance and the nearest cluster is less than or equal to a predetermined cluster width, associating the selected data instance with the selected cluster. ### Claim 50 (depends on 48) The method of claim 48, further comprising, if the distance between the selected data instance and the selected cluster is greater than the cluster width, creating a new cluster and associating the selected data instance with the new cluster. ### Claim 51 (depends on 47) The method of claim 47, further comprising, determining a percentage of clusters having the greatest number of data instances respectively associated therewith. ### Claim 52 (depends on 51) The method of claim 51, wherein the percentage of clusters having the greatest number of data instances are labeled as dense regions in the feature space and wherein the remaining clusters are labeled as sparse regions in the feature space. ### Claim 53 (depends on 52) The method of claim 52, wherein designating one or more data instances as an anomaly comprises associating each data instance in the set of unlabeled data instances with a respective cluster. ### Claim 54 (depends on 43) The method of claim 43, further comprising, determining a sum of distances between a selected data instance and k nearest data instances to the selected data instance, wherein k is a predetermined value. ### Claim 55 (depends on 54) The method of claim 54, wherein determining the sum of the distances comprises determining a nearest cluster as a cluster corresponding to a shortest distance between the respective center of the cluster and the selected data instance. ### Claim 56 (depends on 55) The method of claim 55, further comprising, if a distance between the selected data instance and each data instance in the nearest cluster is less than a predetermined minimum distance, designating the point the cluster as one of the k nearest neighbors. ### Claim 57 (depends on 56) The method of claim 56, wherein designating one or more data instances as an anomaly comprises determining whether sum of the distances to the k nearest neighbors exceeds a predetermined threshold. ### Claim 58 (depends on 43) The method of claim 43, wherein designating one or more data instances as an anomaly comprises determining a decision function to separate the set of data instances from an origin, and computing the decision function.