From 730f4bd72f111da13dd7d68fb350aea98f4c19bf Mon Sep 17 00:00:00 2001 From: Brandon Wiley Date: Tue, 15 Nov 2016 15:09:06 -0600 Subject: Fixed import paths to use shapeshifter-dispatcher/shapeshifter-transports instead of obfs4 --- common/replayfilter/replay_filter.go | 147 ------------------------------ common/replayfilter/replay_filter_test.go | 95 ------------------- 2 files changed, 242 deletions(-) delete mode 100644 common/replayfilter/replay_filter.go delete mode 100644 common/replayfilter/replay_filter_test.go (limited to 'common/replayfilter') diff --git a/common/replayfilter/replay_filter.go b/common/replayfilter/replay_filter.go deleted file mode 100644 index 5513361..0000000 --- a/common/replayfilter/replay_filter.go +++ /dev/null @@ -1,147 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright notice, - * this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright notice, - * this list of conditions and the following disclaimer in the documentation - * and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -// Package replayfilter implements a generic replay detection filter with a -// caller specifiable time-to-live. It only detects if a given byte sequence -// has been seen before based on the SipHash-2-4 digest of the sequence. -// Collisions are treated as positive matches, though the probability of this -// happening is negligible. -package replayfilter - -import ( - "container/list" - "encoding/binary" - "sync" - "time" - - "github.com/dchest/siphash" - - "github.com/OperatorFoundation/obfs4/common/csrand" -) - -// maxFilterSize is the maximum capacity of a replay filter. This value is -// more as a safeguard to prevent runaway filter growth, and is sized to be -// serveral orders of magnitude greater than the number of connections a busy -// bridge sees in one day, so in practice should never be reached. -const maxFilterSize = 100 * 1024 - -type entry struct { - digest uint64 - firstSeen time.Time - element *list.Element -} - -// ReplayFilter is a simple filter designed only to detect if a given byte -// sequence has been seen before. -type ReplayFilter struct { - sync.Mutex - - filter map[uint64]*entry - fifo *list.List - - key [2]uint64 - ttl time.Duration -} - -// New creates a new ReplayFilter instance. -func New(ttl time.Duration) (filter *ReplayFilter, err error) { - // Initialize the SipHash-2-4 instance with a random key. - var key [16]byte - if err = csrand.Bytes(key[:]); err != nil { - return - } - - filter = new(ReplayFilter) - filter.filter = make(map[uint64]*entry) - filter.fifo = list.New() - filter.key[0] = binary.BigEndian.Uint64(key[0:8]) - filter.key[1] = binary.BigEndian.Uint64(key[8:16]) - filter.ttl = ttl - - return -} - -// TestAndSet queries the filter for a given byte sequence, inserts the -// sequence, and returns if it was present before the insertion operation. -func (f *ReplayFilter) TestAndSet(now time.Time, buf []byte) bool { - digest := siphash.Hash(f.key[0], f.key[1], buf) - - f.Lock() - defer f.Unlock() - - f.compactFilter(now) - - if e := f.filter[digest]; e != nil { - // Hit. Just return. - return true - } - - // Miss. Add a new entry. - e := new(entry) - e.digest = digest - e.firstSeen = now - e.element = f.fifo.PushBack(e) - f.filter[digest] = e - - return false -} - -func (f *ReplayFilter) compactFilter(now time.Time) { - e := f.fifo.Front() - for e != nil { - ent, _ := e.Value.(*entry) - - // If the filter is not full, only purge entries that exceed the TTL, - // otherwise purge at least one entry, then revert to TTL based - // compaction. - if f.fifo.Len() < maxFilterSize && f.ttl > 0 { - deltaT := now.Sub(ent.firstSeen) - if deltaT < 0 { - // Aeeeeeee, the system time jumped backwards, potentially by - // a lot. This will eventually self-correct, but "eventually" - // could be a long time. As much as this sucks, jettison the - // entire filter. - f.reset() - return - } else if deltaT < f.ttl { - return - } - } - - // Remove the eldest entry. - eNext := e.Next() - delete(f.filter, ent.digest) - f.fifo.Remove(ent.element) - ent.element = nil - e = eNext - } -} - -func (f *ReplayFilter) reset() { - f.filter = make(map[uint64]*entry) - f.fifo = list.New() -} diff --git a/common/replayfilter/replay_filter_test.go b/common/replayfilter/replay_filter_test.go deleted file mode 100644 index 884e4fb..0000000 --- a/common/replayfilter/replay_filter_test.go +++ /dev/null @@ -1,95 +0,0 @@ -/* - * Copyright (c) 2014, Yawning Angel - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright notice, - * this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright notice, - * this list of conditions and the following disclaimer in the documentation - * and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -package replayfilter - -import ( - "testing" - "time" -) - -func TestReplayFilter(t *testing.T) { - ttl := 10 * time.Second - - f, err := New(ttl) - if err != nil { - t.Fatal("newReplayFilter failed:", err) - } - - buf := []byte("This is a test of the Emergency Broadcast System.") - now := time.Now() - - // testAndSet into empty filter, returns false (not present). - set := f.TestAndSet(now, buf) - if set { - t.Fatal("TestAndSet empty filter returned true") - } - - // testAndSet into filter containing entry, should return true(present). - set = f.TestAndSet(now, buf) - if !set { - t.Fatal("testAndSet populated filter (replayed) returned false") - } - - buf2 := []byte("This concludes this test of the Emergency Broadcast System.") - now = now.Add(ttl) - - // testAndSet with time advanced. - set = f.TestAndSet(now, buf2) - if set { - t.Fatal("testAndSet populated filter, 2nd entry returned true") - } - set = f.TestAndSet(now, buf2) - if !set { - t.Fatal("testAndSet populated filter, 2nd entry (replayed) returned false") - } - - // Ensure that the first entry has been removed by compact. - set = f.TestAndSet(now, buf) - if set { - t.Fatal("testAndSet populated filter, compact check returned true") - } - - // Ensure that the filter gets reaped if the clock jumps backwards. - now = time.Time{} - set = f.TestAndSet(now, buf) - if set { - t.Fatal("testAndSet populated filter, backward time jump returned true") - } - if len(f.filter) != 1 { - t.Fatal("filter map has a unexpected number of entries:", len(f.filter)) - } - if f.fifo.Len() != 1 { - t.Fatal("filter fifo has a unexpected number of entries:", f.fifo.Len()) - } - - // Ensure that the entry is properly added after reaping. - set = f.TestAndSet(now, buf) - if !set { - t.Fatal("testAndSet populated filter, post-backward clock jump (replayed) returned false") - } -} -- cgit v1.2.3