# US 8,789,176 B1 · Detecting scans using a bloom counter

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

- Number: US 8,789,176 B1
- Document ID: US8789176B1
- Status: Granted
- Kind: B1
- Application number: 13/041,772
- Filed: 2011-03-07
- Granted: 2014-07-22
- Earliest claimed: 2011-03-07
- Assignees: Amazon Technologies, Inc.
- Applicants: Eric J. Brandwine
- Inventors: Eric J. Brandwine
- Web page: https://patentgrep.com/patent/US8789176B1

## CPC

- H04L 63/02: {for separating internal from external traffic, e.g. firewalls}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In certain embodiments, detecting scans may include receiving packets, where each packet has a target. The number of distinct targets of the packets may be counted using one or more Bloom counters. The number of distinct targets may satisfy a scan threshold for detecting a scan. If the scan threshold is satisfied, it is determined a scan is present.

## Claims

### Claim 1

A system comprising:
one or more interfaces of an edge device of a computer network, the one or more interfaces operable to:
receive a plurality of packets, each packet of the plurality of packets having a target; and
one or more processing units of the edge device, the one or more processing units operable to:
access a Bloom filter comprising an array and associated with a plurality of hash functions, the plurality of hash functions mapping an element of a set of distinct targets to a plurality of element array positions;
perform the following for one or more packets of the plurality of packets using one or more Bloom counters, at least a subset of the one or more Bloom counters counting for a predetermined time period to yield a time period count:
determine whether a target of a packet is an element of the set of distinct targets recorded in the Bloom filter; and
if the target is not an element of the set of distinct targets, add the target to the set of distinct targets;
determine if a number of distinct targets in the set of distinct targets satisfies a scan threshold for detecting a scan; and
determine that a scan is present if the scan threshold is satisfied.

### Claim 2 (depends on 1)

The system of claim 1, the one or more processing units operable to:
determine whether a target of a packet is an element of the set of distinct targets by:
applying the hash functions to the target to yield a plurality of target array positions; and
determining if the plurality of target array positions are recorded by a plurality of element array positions; and
if the target is not an element of the set of distinct targets, add the target to the set of distinct targets by recording the plurality of target array positions as a plurality of element array positions.

### Claim 3 (depends on 1)

The system of claim 1, at least a subset of the one or more Bloom counters configured to:
count the number of elements added to the set of distinct targets.

### Claim 4 (depends on 1)

The system of claim 1, the packets comprising a packet selected from a group consisting of:
an outbound packet sent from the computer network; and
an inbound packet sent to the computer network.

### Claim 5

A computer-implemented method comprising:
receiving, by one or more processing units, a plurality of packets, each packet of the plurality of packets having a target;
counting, by the one or more processing units, a number of distinct targets of the plurality of packets using one or more Bloom counters, at least a subset of the one or more Bloom counters counting for a predetermined time period to yield a time period count;
determining, by the one or more processing units, if the number of distinct targets satisfies a scan threshold for detecting a scan; and
determining, by the one or more processing units, that a scan is present if the scan threshold is satisfied.

### Claim 6 (depends on 5)

The method of claim 5, the counting the number of distinct targets further comprising:
determining whether a target of a packet is an element of a set of distinct targets recorded in a Bloom filter; and
if the target is not an element of the set of distinct targets, adding the target to the set of distinct targets by recording the target in the Bloom filter.

### Claim 7 (depends on 5)

The method of claim 5, the counting the number of distinct targets further comprising:
accessing a Bloom filter comprising an array and associated with a plurality of hash functions, the plurality of hash functions mapping an element of a set of distinct targets to a plurality of element array positions;
determining whether a target of a packet is an element of the set of distinct targets by:
applying the hash functions to the target to yield a plurality of target array positions; and
determining if the plurality of target array positions are recorded by a plurality of element array positions; and
if the target is not an element of the set of distinct targets, adding the target to the set of distinct targets by recording the plurality of target array positions as a plurality of element array positions.

### Claim 8 (depends on 5)

The method of claim 5, the counting the number of distinct targets further comprising:
counting a number of elements added to a set of distinct targets recorded in a Bloom filter.

### Claim 9 (depends on 5)

The method of claim 5, further comprising:
receiving an initial plurality of packets; and
sampling the initial packets to yield the plurality of packets.

### Claim 10 (depends on 5)

The method of claim 5, further comprising confirming a scan detection by:
determining that the scan threshold has been satisfied;
increasing a sample rate to sample a plurality of additional packets; and
counting the number of distinct targets of the plurality of additional packets.

### Claim 11 (depends on 5)

The method of claim 5, the packets comprising a packet selected from a group consisting of:
a synchronize packet;
a packet sent from an instance;
a packet sent from a port;
an outbound packet sent from a network; and
an inbound packet sent to a network.

### Claim 12 (depends on 5)

The method of claim 5, the target comprising a target selected from a group consisting of:
a destination Internet Protocol address;
a source Internet Protocol address;
a destination User Datagram Protocol port;
a source User Datagram Protocol port;
a destination Transmission Control Protocol port; and
a source Transmission Control Protocol port.

### Claim 13 (depends on 5)

The method of claim 5, the target comprising a destination from a given source.

### Claim 14 (depends on 5)

The method of claim 5, the counting the number of distinct targets further comprising:
starting a second Bloom counter to count the number of distinct targets after a first Bloom counter has been started.

### Claim 15 (depends on 5)

The method of claim 5, the counting the number of distinct targets further comprising:
starting a second Bloom counter to count the number of distinct targets after a first Bloom counter has reached a threshold.

### Claim 16 (depends on 5)

The method of claim 5, the counting the number of distinct targets of the plurality of packets using the one or more Bloom counters further comprising starting one or more of the one or more Bloom counters.

### Claim 17 (depends on 5)

The method of claim 5, the counting the number of distinct targets of the plurality of packets using the one or more Bloom counters further comprising:
starting one or more of the one or more Bloom counters; and applying a statistical function to the time period counts.

### Claim 18 (depends on 5)

The method of claim 5, the counting the number of distinct targets further comprising:
starting a first Bloom counter to count the distinct targets; and
starting a second Bloom counter to count a plurality of other distinct targets.

### Claim 19 (depends on 5)

The method of claim 5, the determining if the number of distinct targets satisfies a scan threshold further comprising:
counting a number of packets; and
if a ratio of the number of packets to a number of distinct targets satisfies a scan ratio threshold, determining that the scan is present.

### Claim 20

One or more non-transitory computer-readable media comprising logic, the logic when executed by one or more processing units operable to perform operations comprising:
receiving a plurality of packets, each packet of the plurality of packets having a target;
accessing a Bloom filter comprising an array and associated with a plurality of hash functions, the plurality of hash functions mapping an element of a set of distinct targets to a plurality of element array positions;
determining whether a target of a packet is an element of the set of distinct targets by:
applying the hash functions to the target to yield a plurality of target array positions; and
determining if the plurality of target array positions are recorded by a plurality of element array positions;
if the target is not an element of the set of distinct targets, adding the target to the set of distinct targets by recording the plurality of target array positions as a plurality of element array positions;
counting a number of distinct targets of the set of distinct targets using one or more Bloom counters, at least a subset of the one or more Bloom counters counting the number of distinct targets for a predetermined time period to yield a time period count;
determining if the number of distinct targets satisfies a scan threshold for detecting a scan; and
determining that a scan is present if the scan threshold is satisfied.

### Claim 21 (depends on 20)

The media of claim 20, the operations further comprising:
counting the number of distinct targets of the set of distinct targets;
determining if the number of distinct targets satisfies an anomalous behavior threshold for detecting anomalous behavior; and
determining that anomalous behavior is present if the anomalous behavior threshold is satisfied.

### Claim 22 (depends on 20)

The media of claim 20, the operations further comprising:
starting a second Bloom counter to count the number of distinct targets after a first Bloom counter has been started.

### Claim 23 (depends on 20)

The media of claim 20, the operations further comprising:
starting a second Bloom counter to count the number of distinct targets after a first Bloom counter has reached a threshold.

### Claim 24 (depends on 20)

The media of claim 20, the operations further comprising:
starting one or more Bloom counters, at least a subset of the one or more Bloom counters counting the number of distinct targets for a predetermined time period.

### Claim 25

One or more non-transitory computer-readable media comprising logic, the logic when executed by one or more processing units operable to perform operations comprising:
receiving a plurality of packets, each packet of the plurality of packets having a target;
accessing a Bloom filter comprising an array and associated with a plurality of hash functions, the plurality of hash functions mapping an element of a set of distinct targets to a plurality of element array positions;
determining whether a target of a packet is an element of the set of distinct targets by:
applying the hash functions to the target to yield a plurality of target array positions; and
determining if the plurality of target array positions are recorded by a plurality of element array positions;
if the target is not an element of the set of distinct targets, adding the target to the set of distinct targets by recording the plurality of target array positions as a plurality of element array positions;
starting one or more Bloom counters, at least a subset of the one or more Bloom counters counting a number of distinct targets for a predetermined time period to yield a time period count; and
applying a statistical function the time period counts.

### Claim 26 (depends on 20)

The media of claim 20, the counting the number of distinct targets using one or more Bloom counters further comprising:
starting a first Bloom counter to count the distinct targets; and
starting a second Bloom counter to count a plurality of other distinct targets.

### Claim 27 (depends on 20)

The media of claim 20:
the counting the number of distinct targets using one or more Bloom counters further comprising:
configuring at least a subset of the one or more Bloom counters to count a particular type of target; and
detecting anomalous behavior associated with the particular type of target using one or more of the subset of the one or more Bloom counters.