# US 8,474,041 B2 · Autonomous diagnosis and mitigation of network anomalies

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,474,041 B2
- Document ID: US8474041B2
- Status: Granted
- Kind: B2
- Application number: 12/765,772
- Filed: 2010-04-22
- Published: 2010-10-28
- Granted: 2013-06-25
- Earliest claimed: 2009-04-22
- Assignees: Hewlett-Packard Development Company, L.P.
- Applicants: Anand Eswaran; Chivukula Koundinya
- Inventors: Anand Eswaran; Chivukula Koundinya
- Web page: https://patentgrep.com/patent/US8474041B2

## CPC

- H04L 63/1416: {Event detection, e.g. attack signature detection}
- H04L 41/0213: Standardised network management protocols, e.g. simple network management protocol [SNMP]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Autonomous diagnosis and mitigation of network anomalies may include creating a plurality of sketch matrices wherein each sketch matrix corresponds to an individual hashing function and each row in each sketch matrix corresponds to an array of hashed parameters of interest from multiple network devices for a given period of time, the parameters of interest being configurable by an administrator. A principal components analysis (PCA) input matrix is created for each of the sketch matrices by computing an entropy value for each element in the sketch matrices, and principal components analysis (PCA) is performed on each of the PCA input matrices to heuristically detect a network anomaly in real time.

## Claims

### Claim 1

A method, comprising, with a network management device comprising a processor and memory, performing each of the following:
creating a plurality of sketch matrices wherein each said sketch matrix corresponds to an individual hashing function and each row in said sketch matrix corresponds to an array of hashed parameters of interest from a plurality of network devices for a given period of time, said parameters of interest being configurable by an administrator;
creating a principal components analysis (PCA) input matrix in at least one physical computer readable medium for each of said sketch matrices by computing an entropy value for each element in said sketch matrices;
performing principal components analysis (PCA) on each of said PCA input matrices to heuristically detect a network anomaly in real time.

### Claim 2 (depends on 1)

The method of claim 1, wherein each of said hashed parameters of interest further comprises a pointer to a corresponding unhashed parameter of interest.

### Claim 3 (depends on 2)

The method of claim 2, wherein said performing principal components analysis on each of said PCA input matrices to heuristically detect a network anomaly in real time further comprises:
identifying anomalous columns in said PCA input matrices; and
identifying a cause of said network anomaly using said pointers to said corresponding unhashed parameters of interest in columns of said sketching matrices associated with said anomalous columns in said PCA input matrices.

### Claim 4 (depends on 1)

The method of claim 1, further comprising automatically taking action to counteract said detected network anomaly.

### Claim 5 (depends on 4)

The method of claim 4, wherein said action to counteract said detected network anomaly comprises:
transmitting an anomalous signature to routers in said network by using an interior gateway protocol message of said network; and
installing said anomalous signature into ternary content-addressable memory of said routers such that said routers are configured to filter network communications corresponding to said anomalous signature.

### Claim 6 (depends on 4)

The method of claim 4, further comprising border routers in said network transmitting said anomalous signature to border routers outside of a domain of said network using an exterior protocol.

### Claim 7

A network management device, comprising:
a processor; and
memory communicatively coupled to said processor; wherein said memory comprises computer-executable code embodied therewith, said computer-executable code being configured to cause said processor to implement:
a parameter monitoring module configured to monitor parameters of interest set by a network administrator from a plurality of network devices communicatively coupled to said network management device;
a sketching module configured to hash said monitored parameters of interest;
a principal components analysis (PCA) engine module configured to perform principal components analysis on computed entropy values of said hashed monitored parameters of interest to detect a network anomaly in real time; and
an anomaly resolution module configured to autonomously identify a source of said network anomaly and take action to mitigate said anomaly.

### Claim 8 (depends on 7)

The network management device of claim 7, wherein said sketching module is configured to:
create a plurality of sketch matrices wherein each said sketch matrix corresponds to an individual hashing function and each row in said sketch matrix corresponds to an array of said hashed parameters of interest for a given period of time; and
create a principal components analysis (PCA) input matrix for each of said sketch matrices by computing an entropy value for each element in said sketch matrices.

### Claim 9 (depends on 8)

The network management device of claim 8, wherein said PCA engine module is configured to perform said principal components analysis on said PCA input matrices.

### Claim 10 (depends on 7)

The network management device of claim 7, wherein said computer-executable code is further configured to cause said processor to implement a user interface that allows said administrator to select the parameters of interest to be monitored.

### Claim 11 (depends on 7)

The network management device of claim 7, wherein said anomaly resolution module is configured to:
transmit an anomalous signature to routers in said network by using an interior gateway protocol message of said network; and
cause said anomalous signature to be installed into ternary content-addressable memory of said routers such that said routers are configured to filter network communications corresponding to said anomalous signature.

### Claim 12 (depends on 7)

The network management device of claim 7, wherein said anomaly resolution module is configured to cause border routers in said network to transmit said anomalous signature to border routers outside of a domain of said network using an exterior protocol.

### Claim 13

A computer program product for identifying and mitigating network anomalies, said computer program product comprising:
a non-transitory, computer usable medium having computer usable program code embodied therewith, said computer usable program code comprising:
computer usable program code configured to cause a computer to create a plurality of sketch matrices wherein each said sketch matrix corresponds to an individual hashing function and each row in said sketch matrix corresponds to an array of hashed parameters of interest from a plurality of network devices for a given period of time, said parameters of interest being configurable by an administrator;
computer usable program code configured to cause said computer to create a principal components analysis (PCA) input matrix for each of said sketch matrices by computing an entropy value for each element in said sketch matrices; and
computer usable program code configured to cause said computer to perform principal components analysis (PCA) on each of said PCA input matrices to heuristically detect a network anomaly in real time.

### Claim 14 (depends on 13)

The computer program product of claim 13, wherein said computer usable program code further comprises:
computer usable program code configured to cause said computer to transmit an anomalous signature to routers in said network by using an interior gateway protocol message of said network; and
computer usable program code configured to cause said computer to cause said anomalous signature to be installed into ternary content-addressable memory of said routers such that said routers are configured to filter network communications corresponding to said anomalous signature.

### Claim 15 (depends on 13)

The computer program product of claim 13, wherein said computer usable program code further comprises:
computer usable program code configured to cause said computer to cause border routers in said network to transmit said anomalous signature to border routers outside of a domain of said network using an exterior protocol.

### Claim 16 (depends on 7)

The network management device of claim 7, further comprising said PCA engine module to identify an anomaly when a square prediction error exceeds a static threshold.

### Claim 17 (depends on 7)

The network management device of claim 7, wherein each element of the hashed monitored parameters of interest comprises two components including a counter and a pointer, wherein said computed entropy values are computed from said counter component of the elements of the hashed monitored parameters of interest.

### Claim 18 (depends on 7)

The network management device of claim 7, further comprising said sketching module to prepare said hashed monitored parameters of interest as PCA input matrices.

### Claim 19 (depends on 18)

The network management device of claim 18, wherein, after a PCA input matrix reaches a predetermined size, that PCA input matrix is submitted to said PCA engine module.

### Claim 20 (depends on 7)

The network management device of claim 7, further comprising said anomaly resolution module to install an anomaly signature corresponding to said anomaly on other network devices to mitigate said anomaly.