# US 2012/0084860 A1 · System and method for detection of domain-flux botnets and the like

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

- Number: US 2012/0084860 A1
- Document ID: US20120084860A1
- Status: Published application
- Kind: A1
- Application number: 12/897,494
- Filed: 2010-10-04
- Published: 2012-04-05
- Earliest claimed: 2010-10-01
- Assignees: Alcatel-Lucent USA Inc.
- Inventors: Jin Cao; Li Li; Nan Jiang
- Web page: https://patentgrep.com/patent/US20120084860A1

## CPC

- H04L 63/1441: {Countermeasures against malicious traffic (countermeasures against attacks on cryptographic mechanisms H04L9/002)}
- H04L 2463/144: Detection or countermeasures against botnets
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In one embodiment, a method for detecting malicious software agents, such as domain-flux botnets. The method applies a co-clustering algorithm on a domain-name query failure graph, to generate a hierarchical grouping of hosts based on similarities between domain names queried by those hosts, and divides that hierarchical structure into candidate clusters based on percentages of failed queries having at least first- and second-level domain names in common, thereby identifying hosts having correlated queries as possibly being infected with malicious software agents. A linking algorithm is used to correlate the co-clustering results generated at different time periods to differentiate actual domain-flux bots from other domain-name failure anomalies by identifying candidate clusters that persist for relatively long periods of time. Persistent candidate clusters are analyzed to identify which clusters have malicious software agents, based on a freshness metric that characterizes whether the candidate clusters continually generate failed queries having new domain names.

## Claims

### Claim 1

A computer-implemented method for detecting malicious software agents, the method comprising:
(a) constructing a graph based on a plurality of failed queries for domain names sent to one or more domain-name servers by a plurality of hosts during a time period;
(b) deriving, from the graph, one or more candidate clusters of hosts;
(c) determining, for each candidate cluster and for each of a plurality of time intervals during the time period, a number of new domain names appearing in the failed queries of the candidate cluster during the time interval;
(d) determining, for each candidate cluster, a freshness metric based on the numbers of new domain names for the plurality of time intervals in the time period; and
(e) detecting one or more malicious software agents on the hosts based on the one or more freshness metrics.

### Claim 2 (depends on 1)

The invention of claim 1, wherein each host in each candidate cluster has at least a specified percentage of failed queries having at least first and second levels of domain names in common with at least one other host in the candidate cluster.

### Claim 3 (depends on 1)

The invention of claim 1, wherein step (b) comprises:
(b1) generating multi-level hierarchical groupings of Internet Protocol (IP) addresses in the graph based on similarities between at least first and second levels of domain names in failed domain-name queries made by hosts corresponding to the IP addresses;
(b2) determining, for each hierarchical grouping, a highest percentage of failed domain-name queries for which a most recently added IP address in the hierarchical grouping has at least first and second levels of domain names in common with another IP address in the hierarchical grouping; and
(b3) identifying each highest-level hierarchical grouping having its determined percentage more than a specified percentage threshold as a candidate cluster of hosts.

### Claim 4 (depends on 3)

The invention of claim 3, wherein the specified percentage threshold is 40%.

### Claim 5 (depends on 1)

The invention of claim 1, wherein:
step (b) comprises:
(b1) linking candidate clusters in adjacent time intervals based on shared IP addresses to form one or more cluster chains; and
(b2) identifying one or more cluster chains that are longer than a specified length threshold; and
step (e) comprises determining that one or more of the identified cluster chains correspond to malicious software agents.

### Claim 6 (depends on 1)

The invention of claim 1, further comprising:
(f) constructing a graph based on a plurality of successful queries for domain names sent to one or more domain-name servers by hosts on which one or more malicious software agents are detected in step (e); and
(g) querying one or more domain-name servers to identify one or more registrants of domain names corresponding to the successful queries in the graph constructed in step (f).

### Claim 7

A computer-implemented method for detecting malicious software agents, the method comprising:
(a) constructing a graph based on a plurality of failed queries for domain names sent to one or more domain-name servers by a plurality of hosts during a time period;
(b) deriving, from the graph, one or more candidate clusters of hosts, wherein step (b) comprises:
(b1) generating multi-level hierarchical groupings of Internet Protocol (IP) addresses in the graph based on similarities between at least first and second levels of domain names in failed domain-name queries made by hosts corresponding to the IP addresses;
(b2) determining, for each hierarchical grouping, a highest percentage of failed domain-name queries for which a most recently added IP address in the hierarchical grouping has at least first and second levels of domain names in common with another IP address in the hierarchical grouping; and
(b3) identifying each highest-level hierarchical grouping having its determined percentage more than a specified percentage threshold as a candidate cluster of hosts; and
(c) determining that one or more of the candidate clusters correspond to malicious software agents.

### Claim 8 (depends on 7)

The invention of claim 7, wherein each host in each candidate cluster has at least a specified percentage of failed queries having at least first and second levels of domain names in common with at least one other host in the candidate cluster.

### Claim 9 (depends on 7)

The invention of claim 7, wherein the specified percentage threshold is 40%.

### Claim 10 (depends on 7)

The invention of claim 7, wherein:
step (b) further comprises:
(b4) linking candidate clusters in adjacent time intervals based on shared IP addresses to form one or more cluster chains; and
(b5) identifying one or more cluster chains that are longer than a specified length threshold; and
step (c) comprises determining that one or more of the identified cluster chains correspond to malicious software agents.

### Claim 11 (depends on 7)

The invention of claim 7, further comprising:
(d) constructing a graph based on a plurality of successful queries for domain names sent to one or more domain-name servers by hosts on which one or more malicious software agents are detected in step (c); and
(e) querying one or more domain-name servers to identify one or more registrants of domain names corresponding to the successful queries in the graph constructed in step (d).

### Claim 12

A computer-implemented method for detecting malicious software agents, the method comprising:
(a) constructing a graph based on a plurality of failed queries for domain names sent to one or more domain-name servers by a plurality of hosts during a time period;
(b) deriving, from the graph, one or more candidate clusters of hosts for each of a plurality of time intervals in the time period;
(c) linking candidate clusters in adjacent time intervals based on shared IP addresses to form one or more cluster chains;
(d) identifying one or more cluster chains that are longer than a specified length threshold; and
(e) determining that one or more of the identified cluster chains correspond to malicious software agents.

### Claim 13 (depends on 12)

The invention of claim 12, wherein each host in each candidate cluster has at least a specified percentage of failed queries having at least first and second levels of domain names in common with at least one other host in the candidate cluster.

### Claim 14 (depends on 12)

The invention of claim 12, wherein:
step (b) comprises:
(b1) generating multi-level hierarchical groupings of Internet Protocol (IP) addresses in the graph based on similarities between at least first and second levels of domain names in failed domain-name queries made by hosts corresponding to the IP addresses;
(b2) determining, for each hierarchical grouping, a highest percentage of failed domain-name queries for which a most recently added IP address in the hierarchical grouping has at least first and second levels of domain names in common with another IP address in the hierarchical grouping; and
(b3) identifying each highest-level hierarchical grouping having its determined percentage more than a specified percentage threshold as a candidate cluster of hosts; and
step (e) comprises:
(e1) determining, for each cluster chain identified in step (d) and for each of a plurality of time intervals during the time period, a number of new domain names appearing in the failed queries of the cluster chain during the time interval;
(e2) determining, for each cluster chain, a freshness metric based on the numbers of new domain names for the plurality of time intervals in the time period; and
(e3) detecting one or more malicious software agents on the hosts based on the one or more freshness metrics.

### Claim 15 (depends on 14)

The invention of claim 14, wherein the specified percentage threshold is 40%.

### Claim 16 (depends on 12)

The invention of claim 12, further comprising:
(f) constructing a graph based on a plurality of successful queries for domain names sent to one or more domain-name servers by hosts on which one or more malicious software agents are detected in step (e); and
(g) querying one or more domain-name servers to identify one or more registrants of domain names corresponding to the successful queries in the graph constructed in step (f).

### Claim 17

Apparatus for detecting malicious software agents, comprising:
a query pre-processor adapted to construct a graph based on a plurality of failed queries for domain names sent to one or more domain-name servers by a plurality of hosts during a time period;
a malicious software agent detector adapted to:
(i) derive, from the graph, one or more candidate clusters of hosts;
(ii) determine, for each candidate cluster and for each of a plurality of time intervals during the time period, a number of new domain names appearing in the failed queries of the candidate cluster during the time interval; and
(iii) determine, for each candidate cluster, a freshness metric based on the numbers of new domain names for the plurality of time intervals in the time period; and
a malicious software agent server tracker adapted to detect one or more malicious software agents on the hosts based on the one or more freshness metrics.

### Claim 18

Apparatus for detecting malicious software agents, comprising:
a query pre-processor adapted to construct a graph based on a plurality of failed queries for domain names sent to one or more domain-name servers by a plurality of hosts during a time period;
a malicious software agent detector adapted to derive, from the graph, one or more candidate clusters of hosts, wherein the deriving comprises:
(i) generating multi-level hierarchical groupings of Internet Protocol (IP) addresses in the graph based on similarities between at least first and second levels of domain names in failed domain-name queries made by hosts corresponding to the IP addresses;
(ii) determining, for each hierarchical grouping, a highest percentage of failed domain-name queries for which a most recently added IP address in the hierarchical grouping has at least first and second levels of domain names in common with another IP address in the hierarchical grouping; and
(iii) identifying each highest-level hierarchical grouping having its determined percentage more than a specified percentage threshold as a candidate cluster of hosts; and
a malicious software agent server tracker adapted to determine that one or more of the candidate clusters correspond to malicious software agents.

### Claim 19

Apparatus for detecting malicious software agents, comprising:
a query pre-processor adapted to construct a graph based on a plurality of failed queries for domain names sent to one or more domain-name servers by a plurality of hosts during a time period;
a malicious software agent detector adapted to:
(i) derive, from the graph, one or more candidate clusters of hosts for each of a plurality of time intervals in the time period;
(ii) link candidate clusters in adjacent time intervals based on shared IP addresses to form one or more cluster chains; and
(iv) identify one or more cluster chains that are longer than a specified length threshold; and
a malicious software agent server tracker adapted to determine that one or more of the identified cluster chains correspond to malicious software agents.
