Sampling and Filtering Techniques for IP Packet Selection
Extracted elements (27)
BOB was selected over CRC-32 and IPSX as the mandatory function because it showed the best overall uniformity and mixing properties in evaluations, especially when including payload bytes. IPSX is about an order of magnitude faster but is inherently limited to 16-byte input and has worse collision properties.
Cryptographically strong hash functions (e.g., AES in CBC mode, MD5/SHA1 with private initial vector) are the ideal choice for security but are 7-10 times slower than non-cryptographic functions. Because not all PSAMP Devices can apply them at line rate, the specification mandates the weaker BOB function while encouraging cryptographic functions where feasible.
Hash-based Selection is categorized as Filtering rather than Sampling because hashing is a deterministic operation on Packet Content. However, it can be used to emulate random Sampling and enables consistent selection of the same packets at multiple Observation Points, a property not achievable with true random Sampling.
Placing a Filter before a Sampler allows independent tuning of Sampling rates per filtered sub-population and more accurate control. Placing Sampling before Filtering reduces the packet rate to the filter, which is beneficial when the filter must access slow router state not available at full line rate.
OR operations are not supported in the basic Property Match Filtering model; only AND combinations (via cascaded filters) are defined. More sophisticated filter logic (bitmasks, ranges, OR) must be realized as vendor-specific schemes.
The Hash Domain for IPv4 BOB cannot include options fields, nor can an IPv6 Hash Domain include stacked extension headers. If the payload is shorter than the configured number of bytes N, the Hash Function cannot be applied; padding with zeros may be considered in the future.
Trajectory Sampling (consistent selection of the same packets at multiple Observation Points) requires all Observation Points to use the same Hash Function, Hash Domain, and Hash Selection Range. Hash Domain fields must be invariant along the packet path; TTL and header CRC are therefore excluded.
For packet digesting purposes, the BOB function SHOULD be used. Other functions such as CRC-32 MAY be used; IPSX is not recommended for digesting due to higher collision rate and fixed-length-only input.
If a Hash-based Selection with the BOB function is used with IPv6 traffic, the following input bytes MUST be used: payload length (2 bytes), bytes 10, 11, 14, 15, 16 of IPv6 source address, bytes 10, 11, 14, 15, 16 of IPv6 destination address, and at least 4 recommended bytes from the IP payload.
If Hash-based packet Selection is applied, the BOB function MUST be used for packet selection operations in order to be compliant with PSAMP. Both the parameter (init value) and the selection range should be kept private.
In order to be compliant with PSAMP, at least one of the proposed selection schemes MUST be implemented.
The initial vector of the Hash Function MUST be configurable out of band to prevent security breaches like exposure of the initial vector content.
A Hash Domain is a subset of the Packet Content viewed as an N-bit string; a Hash Range is the set of M-bit result strings; a Hash Function maps the Hash Domain deterministically onto the Hash Range; and a Hash Selection Range is the subset of the Hash Range that causes a packet to be selected.
A Selection Process takes the Observed Packet Stream as input and selects a subset as output. A Selector defines what kind of action a Selection Process performs on a single packet. A Composite Selector is an ordered composition of Selectors where the output of one forms the input to the next.
Hash-Based Selection is a Filtering method defined by a Hash Domain, Hash Function, Hash Range, and Hash Selection Range. A packet is selected if the hash result falls in the Hash Selection Range. It is classified as Filtering because hashing is a deterministic operation on Packet Content.
n-out-of-N Sampling selects exactly n elements from a population of N by generating n distinct random numbers in [1,N] and selecting packets at matching positions, yielding a fixed Sample Size.
Non-Uniform Flow State Dependent Sampling (e.g., 'sample and hold') selects packets based on whether they belong to an existing flow record: packets matching an existing flow record are always selected; new-flow packets are selected with probability p, creating a new flow record if selected.
Property Match Filtering selects a packet if specific IPFIX fields equal predefined values (Field=Value). AND operations are supported by cascading filters. OR operations are not supported in the basic model and require vendor-specific extensions.
Systematic count-based Sampling uses packet position counters: all packets in a Sampling interval defined by packet count are selected. Systematic time-based Sampling uses time-based start/stop triggers: all packets arriving within defined time intervals are selected. Both are content-independent.
The Selection Sequence is a unique value per Observation Domain describing the Observation Point and all Selector IDs through which packets are selected. Composite techniques chain multiple Selectors by combining their IDs in the Selection Sequence.
Uniform Probabilistic Sampling selects each packet independently with uniform probability p. Count-driven variant (geometric random Sampling) has geometrically distributed inter-sample distances; time-driven variant (exponential random Sampling) has exponentially distributed inter-trigger times.
A user can determine the start and stop triggers of time-based systematic Sampling by sending test packets, enabling them to modify their send schedule so their packets are disproportionately selected or avoided. A cryptographically strong PRNG should be used for random Sampling to prevent prediction of selection decisions.
An attacker who can observe selection outcomes (via billing reports, IDS feedback, or eavesdropping on export packets) can use trial streams to reconstruct hash parameters and craft disproportionately sampled packet sets. For the modular hash f(x) = ax+b mod k, roughly 2/p outcome observations suffice to succeed.
Because Hash-based Selection is deterministic, any packet set with known selection properties can be replayed with identical outcomes as long as the Hash Function and parameters are unchanged. Replay attacks may be mitigated by periodically changing Hash Function parameters across all Observation Points simultaneously.
Without a private hash parameter, an attacker knowing the Hash Function can precompute which packets will be selected regardless of hash strength. Even if the selection range is private, the attacker can construct arbitrarily large sets of packets with common selection properties.
A Filter description uses SELECTOR_ID, SELECTOR_TYPE (Matching, Hashing, Router_state), and SELECTOR_PARAMETERS. For Hashing: Hash Domain specified as IPv4 20-byte bitmask or IPv6 40-byte bitmask plus payload bitmask, Hash Function name with input key length, output bitmask, Hash Selection Range as list of non-overlapping [start, end] intervals.
A Sampler is described by SELECTOR_ID (unique identifier), SELECTOR_TYPE (algorithm: Systematic count-based, Systematic time-based, Random n-out-of-N, uniform probabilistic, Non-uniform probabilistic, Non-uniform flow state), and SELECTOR_PARAMETERS (type-specific inputs such as interval length, spacing, population/sample size, or probability).