Projects/Replay cache improvements - Revision history

Ghudson: /* Hash-based file format */

2019-02-21T06:31:19Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-02-21T01:31:10Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-02-20T21:41:43Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-02-20T21:26:45Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-02-20T20:50:38Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-02-20T20:15:46Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-02-20T20:11:15Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-02-20T19:47:42Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-02-20T19:21:26Z

‎Hash-based file format

Ghudson: /* Hash-based file format */

2019-01-31T19:41:51Z

‎Hash-based file format

@@ Line 76: / Line 76: @@
 * With the basic implementation, the nominal file size after the test was 126MB, or 132 bytes (8.2 table slots) per record.  On a filesystem supporting holes, the space used was 59MB, or 61 bytes (3.8 table slots) per record.  The test took about 32s on a Linux VM running on unknown hardware, or about 15us per store operation (with half the store operations writing records and the other half finding replays).
-* With 2-slot linear open addressing added (each table size is reduced by one; a record hashes to its index and the next index in each table), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots) and the space used to 35M (36 bytes per record, 2.2 table slots).  The runtime was reduced to about 30s.  For larger amounts of open addressing, the amount of space used declined as far as 32MB, and the nominal size to 32MB as well at 5-slot open addressing (by fitting all of the records in eleven tables instead of twelve).  The runtime remained at 29-30s for any reasonably small amount of open addressing.
+* With 2-slot linear open addressing (each tag is hashed modulo the table size minus one, and the record can be located either in the slot indexed by the hash value or the next slot), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots) and the space used to 35M (36 bytes per record, 2.2 table slots).  The runtime was reduced to about 30s.  For larger amounts of open addressing, the amount of space used declined as far as 32MB, and the nominal size to 32MB as well at 5-slot open addressing (by fitting all of the records in eleven tables instead of twelve).  The runtime remained at 29-30s for any reasonably small amount of open addressing.
 * With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant still had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.  (2-slot open addressing was also present for this test.)

@@ Line 76: / Line 76: @@
 * With the basic implementation, the nominal file size after the test was 126MB, or 132 bytes (8.2 table slots) per record.  On a filesystem supporting holes, the space used was 59MB, or 61 bytes (3.8 table slots) per record.  The test took about 32s on a Linux VM running on unknown hardware, or about 15us per store operation (with half the store operations writing records and the other half finding replays).
-* With basic open addressing added (each table size is reduced by one, and a record hashes to its index and the next index in each table), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots) and the space used to 35M (36 bytes per record, 2.2 table slots).  The runtime was reduced to about 30s.
+* With 2-slot linear open addressing added (each table size is reduced by one; a record hashes to its index and the next index in each table), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots) and the space used to 35M (36 bytes per record, 2.2 table slots).  The runtime was reduced to about 30s.  For larger amounts of open addressing, the amount of space used declined as far as 32MB, and the nominal size to 32MB as well at 5-slot open addressing (by fitting all of the records in eleven tables instead of twelve).  The runtime remained at 29-30s for any reasonably small amount of open addressing.
-* With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant still had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.  (Basic open addressing was also present for this test.)
+* With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant still had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.  (2-slot open addressing was also present for this test.)
-* With the record size reduced to 8 bytes (56 bits for the tag, one for the timestamp divided by the clockskew modulo 256) and the initial table size increased to 2048, the nominal file size was reduced to 32MB (33 bytes per record, 4.2 table slots) and the space used to 19MB (19 bytes per record, 2.4 table slots).  The runtime was reduced to about 29s.  (Basic open addressing was also present for this test, but per-record locking was not.)
+* With the record size reduced to 8 bytes (56 bits for the tag, one for the timestamp divided by the clockskew modulo 256) and the initial table size increased to 2048, the nominal file size was reduced to 32MB (33 bytes per record, 4.2 table slots) and the space used to 19MB (19 bytes per record, 2.4 table slots).  The runtime was reduced to about 29s.  (2-slot open addressing was also present for this test, but per-record locking was not.)
 ===Transition to a new format===

@@ Line 78: / Line 78: @@
 * With basic open addressing added (each table size is reduced by one, and a record hashes to its index and the next index in each table), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots) and the space used to 35M (36 bytes per record, 2.2 table slots).  The runtime was reduced to about 30s.
-* With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant still had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.
+* With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant still had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.  (Basic open addressing was also present for this test.)
 ===Transition to a new format===

@@ Line 78: / Line 78: @@
 * With basic open addressing added (each table size is reduced by one, and a record hashes to its index and the next index in each table), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots) and the space used to 35M (36 bytes per record, 2.2 table slots).  The runtime was reduced to about 30s.
-* With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.
+* With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant still had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.
 ===Transition to a new format===

@@ Line 76: / Line 76: @@
 * With the basic implementation, the nominal file size after the test was 126MB, or 132 bytes (8.2 table slots) per record.  On a filesystem supporting holes, the space used was 59MB, or 61 bytes (3.8 table slots) per record.  The test took about 32s on a Linux VM running on unknown hardware, or about 15us per store operation (with half the store operations writing records and the other half finding replays).
-* With basic open addressing added (each table size is reduced by one, and a record hashes to its index and the next index in each table), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots).  The runtime was reduced to about 30s.
+* With basic open addressing added (each table size is reduced by one, and a record hashes to its index and the next index in each table), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots) and the space used to 35M (36 bytes per record, 2.2 table slots).  The runtime was reduced to about 30s.
 * With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.

@@ Line 70: / Line 70: @@
 An authenticated attacker could potentially provoke collisions must faster than we would expect with an even distribution of integrity tags, using offline computation to find valid integrity tags (by varying the confounder) which all hash to the same value for each modulus.  A seeded hash function could mitigate this attack, at the expense of having to allocate some space in the file to store the seed.
-Some care must be taken to avoid races between looking up a record and storing it, or else two processes could store the same record without detecting that one of them is a replay.  The simplest strategy is to exclusively lock the whole file before lookup and release the lock after storing the new entry.  Byte-range locks can be used to improve concurrency, at a complexity cost.  If records are 64-bits, it might be possible to use mmap() and compare-and-swap instructions to avoid locks entirely, at a cost in both portability and complexity.
+Some care must be taken to avoid races between looking up a record and storing it, or else two processes could store the same record without detecting that one of them is a replay.  The simplest strategy is to exclusively lock the whole file before lookup and release the lock after storing the new entry.  Byte-range locks can be used to improve concurrency, at a cost in complexity and system call overhead.  Migrating the implementation from whole-file locking to per-record locking or vice-versa is safe, as a whole-file lock will contend with all per-record locks.  If records are 64 bits, it might be possible to use mmap() and compare-and-swap instructions to avoid locks entirely, at a cost in both portability and complexity.
 To produce some experimental test results, a harness was created which spawns 1000 processes to each store 1000 unique tags at the same timestamp.  As each process completes, the master process stores the same 1000 tags to verify that they are all detected as replays.  The basic implementation used 128-bit records, hash table sizes beginning at 1024 slots and doubling with each new hash table, no open addressing, and whole-file locking.
@@ Line 78: / Line 78: @@
 * With basic open addressing added (each table size is reduced by one, and a record hashes to its index and the next index in each table), the nominal file size was reduced to 64MB (67 bytes per record, 4.2 table slots).  The runtime was reduced to about 30s.
-* With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s--any advantages in concurrency appeared to be outweighed by the increase in system call overhead.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant still had increased runtime versus whole-file locking.
+* With the whole-file locks replaced with per-record (byte range) locking, the runtime was increased to about 38s.  The VM reported only having one CPU, so the tests were re-run on a bare-metal machine with four cores; the record-locking variant had a proportionally simliar runtime increase versus whole-file locking.  It appears that the concurrency advantages of per-record locking are outweighed by the increased system call overhead.
 ===Transition to a new format===

@@ Line 64: / Line 64: @@
 Replay records can be made small and fixed-size.  All we need is a tag to determine a replay match, and a timestamp to determine if a record is expired.  We can optionally discard some of the low-order and high-order timestamp bits, as it is not harmful to occasionally mistreat an expired record as current.  The tag bytes can be taken from the integrity tag of the ciphertext (for authenticators or mk_priv messages), or from the MIC of a mk_safe message.  If the tag is N bits long, we expect false positives to occur when around 2^(N/2) replay records are live during the replay window.  For practical purposes, a 96-bit or longer tag is unlikely to create any issues with false positives; a 56-bit tag (in order to produce a 64-bit record when combined with 8 timestamp bits) is more aggressive, but still probably okay.
-With fixed-sized records, we can store a hash table in a file by hashing the tag down to an index modulo some value, and seeking to the record size times the index.  If the record we find there matches the tag, we report a replay.  If the record there is empty or expired, we can story the new record there.
+With fixed-sized records, we can store a hash table in a file by hashing the tag down to an index modulo some value, and seeking to the record size times the index.  If the record we find there matches the tag, we report a replay.  If the record there is empty or expired, we can store the new record there.
 If the modulus is M, we expect a collision when approximately sqrt(M) records are simultaneously current.  We could handle a small number of collision using some kind of open-addressing scheme, but the fundamental strategy is to create a new hash table at the end of the current one.  The file size can be used to detect the number of hash tables in the file.  Once multiple tables are present in the file, we must check all of the tables when looking up records.  If we don't find a match, we can store the new record in the first empty or expired slot.  If all of the slots are filled with unexpired records, we can create a new hash table.
@@ Line 71: / Line 71: @@
 Some care must be taken to avoid races between looking up a record and storing it, or else two processes could store the same record without detecting that one of them is a replay.  The simplest strategy is to exclusively lock the whole file before lookup and release the lock after storing the new entry.  Byte-range locks can be used to improve concurrency, at a complexity cost.  If records are 64-bits, it might be possible to use mmap() and compare-and-swap instructions to avoid locks entirely, at a cost in both portability and complexity.
 ===Transition to a new format===

@@ Line 60: / Line 60: @@
 ===Hash-based file format===
-See http://mailman.mit.edu/pipermail/krbdev/2014-September/012166.html for now
+See http://mailman.mit.edu/pipermail/krbdev/2014-September/012166.html for initial notes.
 ===Transition to a new format===