ForNet: A Distributed Forensics Network - Computer Network Security - page 10

10 − 5 uses only 42 bits (or
about 5 bytes) of storage per connection. In comparison, a connection record
uses 26 bytes to store a connection. Note, however, to use the Bloom filters we
need the information about connection headers and these headers can only be
obtained where connection records are maintained. The inherent hierarchy of
the network plays a vital role in solving this problem. In the ForNet hierar-
chy (See Fig 1) SynApps closer to the end hosts maintain connection records
whereas SynApps closer to the network edge maintain the Bloom filters. With
such an arrangement we can also identify spoofing as the connections can now
be confirmed not only at the subnets but also closer to the core of the network.
Besides, the space-eciency of Bloom filters is suitable to represent numerous
connections succinctly at network edges.
Another adaptation of a Bloom filter is to represent a histogram succinctly. A
counting Bloom filter uses an array of counters instead of an array of bits to keep
a count of distinct elements in a set. Instead of flipping a bit, counting Bloom
filters increment the corresponding counter by one. The counting Bloom filter
can be used to count various properties of network trac, like packet arrival rate
per host per port. This information can be used to determine various patterns
in network trac.

A Bloom filter with a false positive rate of 4 . 27 ×

Hierarchical Bloom Filters: Although connection records and Bloom filters are
very useful in tracking and tracing network connections, they do not help in
monitoring packet payloads. Monitoring and recording payload of network trac
is a challenging task for two reasons:

- Lack of structure: Packet headers have a pre-defined structure and semantics
are interpreted uniformly across the network. The data payload on the other
hand is application dependent and its interpretation varies across various
applications.
- Amount of data: Packet headers are relatively small compared to payload
hence compact storage of packet headers is feasible even at higher network
speeds. The payload of a packet, on the other hand, can be several hundred
bytes long and keeping up with the amount of data is a challenging task.

In order to monitor payloads, we propose an ecient method, called Hier-
archical Bloom Filters, that supports limited wild-card queries on payloads and
allows for space-accuracy trade-offs. Hierarchical Bloom filters can support wild
card queries of the form “

S 0 S 1 ∗S 3 ”. A detailed description of Hierarchical Bloom
Filters is beyond the scope of this paper. A detailed description can be found
in [34]

Sampling & Histograms: In addition to connection records and Bloom filters it
is useful to sample the tra c to extract higher level features. High-level syn-
opses provide trends which may be useful to guide the search while investigating
a crime, which may later be confirmed with other synopsis techniques that re-
member all the connections and can recall with high probability if a packet was