java.lang.Object
net.i2p.router.tunnel.BloomFilterIVValidator
All Implemented Interfaces:
IVValidator
public class BloomFilterIVValidatorextends Object implements IVValidator
Manage the IV validation for all of the router's tunnels by way of a big decaying bloom filter.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    BloomFilterIVValidator.IVFilterSizer
    Chooses the filter exponent from measured load and the heap budget.

  • Field Summary

    Modifier and Type
    Field
    Description
    private final RouterContext
    _context
    The router doing the validating.
    private DecayingBloomFilter
    _filter
    Remembers the initialization vectors already seen.
    private final Log
    _log
    Logger for this class.
    private BloomFilterIVValidator.IVFilterSizer
    _sizer
    Manages the filter's size.
    static final int
    DEFAULT_FILTER_M
    Default exponent when nothing is configured: 2^23 bits per buffer, a 2 MB pair, which holds roughly 600k entries at a 1.5E-3 false positive rate.
    (package private) static final double
    FILTER_HEAP_FRACTION
    Fraction of max heap the filter may claim.
    private static final int
    HALFLIFE_MS
    After 2*halflife, an entry is completely forgotten from the bloom filter.
    (package private) static final long
    MIN_FILTER_BUDGET
    Hard floor on the filter's byte budget, so a tiny heap still gets one.
    static final int
    MIN_FILTER_M
    Floor for the exponent: 2^20 is a 0.5 MB pair.
    private static final long
    MIN_MEM_TO_USE_BLOOM
    Least free heap for which the bloom filter is worth using.
    private static final int
    MIN_SHARE_KBPS_TO_USE_BLOOM
    Share bandwidth at or above which the fixed-memory filter is always worth using.
    private static final String
    PROP_DISABLE
    For testing.
    static final String
    PROP_FILTER_M
    Property the Tuner drives the filter exponent through.
    private static final String
    PROP_FORCE
    For testing.

  • Constructor Summary

    Constructors
    Constructor
    Description
    BloomFilterIVValidator(RouterContext ctx, int KBps)
    Construct the validator, choosing a starting filter size from the configured share and the heap, then leaving the size to be retuned from measured load.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    destroy()
    Stop the decaying filter.
    static long
    filterBudgetBytes()
    Memory this filter may claim, as a fraction of the heap, with a floor so a small heap still gets a usable filter.
    int
    getFilterM()
    The filter's size exponent, or 0 when the set is in use.
    int
    getLastWindowCount()
    Entries seen in the most recently completed decay window, which is what the size has to be chosen against.
    double
    getMeasuredFalsePositiveRate()
    The live false positive rate, or 0 for the set, which is exact.
    BloomFilterIVValidator.IVFilterSizer
    getSizer()
    The retuning policy for this validator, or null when the filter is off.
    boolean
    receiveIV(byte[] ivData, int ivOffset, byte[] payload, int payloadOffset)
    Receive the IV for the tunnel message, returning true if it is valid, or false if it has already been used (or is otherwise invalid).
    void
    reconfigure(int m, int KBps)
    Replace the filter with one of a different size, or with the set.
    private void
    warn(long maxMemory, int KBps, long recMaxMem, int threshKBps)
    Log a one-time WARN when the IV filter may be too small.

    Methods inherited from class Object

    clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • _context

      private final RouterContext _context
      The router doing the validating.

    • _log

      private final Log _log
      Logger for this class.

    • _filter

      private volatile DecayingBloomFilter _filter
      Remembers the initialization vectors already seen.

    • _sizer

      private volatile BloomFilterIVValidator.IVFilterSizer _sizer
      Manages the filter's size. Kept behind a field so the router can hold the filter for the low-memory case and still retune it later.

    • HALFLIFE_MS

      private static final int HALFLIFE_MS
      After 2*halflife, an entry is completely forgotten from the bloom filter. To avoid the issue of overlap within different tunnels, this is set higher than it needs to be.
      See Also:

    • PROP_FILTER_M

      public static final String PROP_FILTER_M
      Property the Tuner drives the filter exponent through. The starting value is a property rather than a constant so an operator can pin it before the first tuning cycle.
      See Also:

    • DEFAULT_FILTER_M

      public static final int DEFAULT_FILTER_M
      Default exponent when nothing is configured: 2^23 bits per buffer, a 2 MB pair, which holds roughly 600k entries at a 1.5E-3 false positive rate. That covers a 1 MBps share with a wide margin.
      See Also:

    • MIN_FILTER_M

      public static final int MIN_FILTER_M
      Floor for the exponent: 2^20 is a 0.5 MB pair.
      See Also:

    • FILTER_HEAP_FRACTION

      static final double FILTER_HEAP_FRACTION
      Fraction of max heap the filter may claim. The rest is left for transport buffers, the netdb, and the collector.
      See Also:

    • MIN_FILTER_BUDGET

      static final long MIN_FILTER_BUDGET
      Hard floor on the filter's byte budget, so a tiny heap still gets one.
      See Also:

    • MIN_SHARE_KBPS_TO_USE_BLOOM

      private static final int MIN_SHARE_KBPS_TO_USE_BLOOM
      Share bandwidth at or above which the fixed-memory filter is always worth using. Below it the set is only kept when memory is genuinely tight.
      See Also:

    • MIN_MEM_TO_USE_BLOOM

      private static final long MIN_MEM_TO_USE_BLOOM
      Least free heap for which the bloom filter is worth using.
      See Also:

    • PROP_FORCE

      private static final String PROP_FORCE
      For testing.
      See Also:

    • PROP_DISABLE

      private static final String PROP_DISABLE
      For testing.
      See Also:

  • Constructor Details

    • BloomFilterIVValidator

      public BloomFilterIVValidator(RouterContext ctx, int KBps)
      Construct the validator, choosing a starting filter size from the configured share and the heap, then leaving the size to be retuned from measured load.

      The initial choice deliberately favours the fixed-memory filter over the set: a pair of 2^23 bit arrays is 2 MB whatever the traffic, whereas the set costs about 72 bytes per entry and is unbounded until its cap. So the set is used only when both the share is small and the heap is small, and it is replaced by a filter as soon as the budget allows.

      Parameters:
      ctx - the router context
      KBps - the share bandwidth in KBps

  • Method Details

    • filterBudgetBytes

      public static long filterBudgetBytes()
      Memory this filter may claim, as a fraction of the heap, with a floor so a small heap still gets a usable filter.
      Returns:
      the budget in bytes, never below the 1 MB floor

    • getFilterM

      public int getFilterM()
      The filter's size exponent, or 0 when the set is in use.
      Returns:
      the exponent, or 0 for the set or when disabled

    • getLastWindowCount

      public int getLastWindowCount()
      Entries seen in the most recently completed decay window, which is what the size has to be chosen against. Zero until the first decay.
      Returns:
      entries in the last window

    • getMeasuredFalsePositiveRate

      public double getMeasuredFalsePositiveRate()
      The live false positive rate, or 0 for the set, which is exact.
      Returns:
      the current false positive rate

    • reconfigure

      public void reconfigure(int m, int KBps)
      Replace the filter with one of a different size, or with the set. A resize discards the buffered IVs, so for a short window a repeated IV could go unnoticed; the caller is expected to only do this on a decay boundary and at most one step at a time.
      Parameters:
      m - the new exponent, 0 to switch to the memory-proportional set
      KBps - the configured share in KBps, not consulted here; the set's cap comes from the heap budget

    • getSizer

      public BloomFilterIVValidator.IVFilterSizer getSizer()
      The retuning policy for this validator, or null when the filter is off.
      Returns:
      the sizer, or null

    • receiveIV

      public boolean receiveIV(byte[] ivData, int ivOffset, byte[] payload, int payloadOffset)
      Description copied from interface: IVValidator
      Receive the IV for the tunnel message, returning true if it is valid, or false if it has already been used (or is otherwise invalid). To prevent colluding attackers from successfully tagging the tunnel by switching the IV and the first block of the message, the validator should treat the XOR of the IV and the first block as the unique identifier, not the IV alone (since the tunnel is encrypted via AES/CBC). Thanks to dvorak for pointing out that tagging!
      Specified by:
      receiveIV in interface IVValidator
      Parameters:
      ivData - data will not be modified
      ivOffset - offset of the IV in the iv array
      payload - will not be modified
      payloadOffset - offset of the payload in the payload array
      Returns:
      true if valid, false if already used or otherwise invalid

    • destroy

      public void destroy()
      Stop the decaying filter.

    • warn

      private void warn(long maxMemory, int KBps, long recMaxMem, int threshKBps)
      Log a one-time WARN when the IV filter may be too small.
      Parameters:
      maxMemory - the maximum memory available to the JVM, in bytes
      KBps - the configured share bandwidth in KBps
      recMaxMem - the recommended minimum memory in bytes, the amount to raise the setting to
      threshKBps - the share bandwidth in KBps above which the memory recommendation applies