diff options
10 files changed, 1323 insertions, 0 deletions
diff --git a/services/backup/java/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunker.java b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunker.java new file mode 100644 index 000000000000..18011f620b24 --- /dev/null +++ b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunker.java @@ -0,0 +1,136 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.android.internal.util.Preconditions.checkArgument; + +import com.android.server.backup.encryption.chunking.Chunker; + +import java.io.IOException; +import java.io.InputStream; +import java.security.GeneralSecurityException; +import java.util.Arrays; + +/** Splits a stream of bytes into variable-sized chunks, using content-defined chunking. */ +public class ContentDefinedChunker implements Chunker { + private static final int WINDOW_SIZE = 31; + private static final byte DEFAULT_OUT_BYTE = (byte) 0; + + private final byte[] mChunkBuffer; + private final RabinFingerprint64 mRabinFingerprint64; + private final FingerprintMixer mFingerprintMixer; + private final BreakpointPredicate mBreakpointPredicate; + private final int mMinChunkSize; + private final int mMaxChunkSize; + + /** + * Constructor. + * + * @param minChunkSize The minimum size of a chunk. No chunk will be produced of a size smaller + * than this except possibly at the very end of the stream. + * @param maxChunkSize The maximum size of a chunk. No chunk will be produced of a larger size. + * @param rabinFingerprint64 Calculates fingerprints, with which to determine breakpoints. + * @param breakpointPredicate Given a Rabin fingerprint, returns whether this ought to be a + * breakpoint. + */ + public ContentDefinedChunker( + int minChunkSize, + int maxChunkSize, + RabinFingerprint64 rabinFingerprint64, + FingerprintMixer fingerprintMixer, + BreakpointPredicate breakpointPredicate) { + checkArgument( + minChunkSize >= WINDOW_SIZE, + "Minimum chunk size must be greater than window size."); + checkArgument( + maxChunkSize >= minChunkSize, + "Maximum chunk size cannot be smaller than minimum chunk size."); + mChunkBuffer = new byte[maxChunkSize]; + mRabinFingerprint64 = rabinFingerprint64; + mBreakpointPredicate = breakpointPredicate; + mFingerprintMixer = fingerprintMixer; + mMinChunkSize = minChunkSize; + mMaxChunkSize = maxChunkSize; + } + + /** + * Breaks the input stream into variable-sized chunks. + * + * @param inputStream The input bytes to break into chunks. + * @param chunkConsumer A function to process each chunk as it's generated. + * @throws IOException Thrown if there is an issue reading from the input stream. + * @throws GeneralSecurityException Thrown if the {@link ChunkConsumer} throws it. + */ + @Override + public void chunkify(InputStream inputStream, ChunkConsumer chunkConsumer) + throws IOException, GeneralSecurityException { + int chunkLength; + int initialReadLength = mMinChunkSize - WINDOW_SIZE; + + // Performance optimization - there is no reason to calculate fingerprints for windows + // ending before the minimum chunk size. + while ((chunkLength = + inputStream.read(mChunkBuffer, /*off=*/ 0, /*len=*/ initialReadLength)) + != -1) { + int b; + long fingerprint = 0L; + + while ((b = inputStream.read()) != -1) { + byte inByte = (byte) b; + byte outByte = getCurrentWindowStartByte(chunkLength); + mChunkBuffer[chunkLength++] = inByte; + + fingerprint = + mRabinFingerprint64.computeFingerprint64(inByte, outByte, fingerprint); + + if (chunkLength >= mMaxChunkSize + || (chunkLength >= mMinChunkSize + && mBreakpointPredicate.isBreakpoint( + mFingerprintMixer.mix(fingerprint)))) { + chunkConsumer.accept(Arrays.copyOf(mChunkBuffer, chunkLength)); + chunkLength = 0; + break; + } + } + + if (chunkLength > 0) { + chunkConsumer.accept(Arrays.copyOf(mChunkBuffer, chunkLength)); + } + } + } + + private byte getCurrentWindowStartByte(int chunkLength) { + if (chunkLength < mMinChunkSize) { + return DEFAULT_OUT_BYTE; + } else { + return mChunkBuffer[chunkLength - WINDOW_SIZE]; + } + } + + /** Whether the current fingerprint indicates the end of a chunk. */ + public interface BreakpointPredicate { + + /** + * Returns {@code true} if the fingerprint of the last {@code WINDOW_SIZE} bytes indicates + * the chunk ought to end at this position. + * + * @param fingerprint Fingerprint of the last {@code WINDOW_SIZE} bytes. + * @return Whether this ought to be a chunk breakpoint. + */ + boolean isBreakpoint(long fingerprint); + } +} diff --git a/services/backup/java/com/android/server/backup/encryption/chunking/cdc/FingerprintMixer.java b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/FingerprintMixer.java new file mode 100644 index 000000000000..e9f30505c112 --- /dev/null +++ b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/FingerprintMixer.java @@ -0,0 +1,95 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.android.internal.util.Preconditions.checkArgument; + +import java.nio.ByteBuffer; +import java.nio.charset.StandardCharsets; +import java.security.InvalidKeyException; + +import javax.crypto.SecretKey; + +/** + * Helper for mixing fingerprint with key material. + * + * <p>We do this as otherwise the Rabin fingerprint leaks information about the plaintext. i.e., if + * two users have the same file, it will be partitioned by Rabin in the same way, allowing us to + * infer that it is the same as another user's file. + * + * <p>By mixing the fingerprint with the user's secret key, the chunking method is different on a + * per key basis. Each application has its own {@link SecretKey}, so we cannot infer that a file is + * the same even across multiple applications owned by the same user, never mind across multiple + * users. + * + * <p>Instead of directly mixing the fingerprint with the user's secret, we first securely and + * deterministically derive a secondary chunking key. As Rabin is not a cryptographically secure + * hash, it might otherwise leak information about the user's secret. This prevents that from + * happening. + */ +public class FingerprintMixer { + public static final int SALT_LENGTH_BYTES = 256 / Byte.SIZE; + private static final String DERIVED_KEY_NAME = "RabinFingerprint64Mixer"; + + private final long mAddend; + private final long mMultiplicand; + + /** + * A new instance from a given secret key and salt. Salt must be the same across incremental + * backups, or a different chunking strategy will be used each time, defeating the dedup. + * + * @param secretKey The application-specific secret. + * @param salt The salt. + * @throws InvalidKeyException If the encoded form of {@code secretKey} is inaccessible. + */ + public FingerprintMixer(SecretKey secretKey, byte[] salt) throws InvalidKeyException { + checkArgument(salt.length == SALT_LENGTH_BYTES, "Requires a 256-bit salt."); + byte[] keyBytes = secretKey.getEncoded(); + if (keyBytes == null) { + throw new InvalidKeyException("SecretKey must support encoding for FingerprintMixer."); + } + byte[] derivedKey = + Hkdf.hkdf(keyBytes, salt, DERIVED_KEY_NAME.getBytes(StandardCharsets.UTF_8)); + ByteBuffer buffer = ByteBuffer.wrap(derivedKey); + mAddend = buffer.getLong(); + // Multiplicand must be odd - otherwise we lose some bits of the Rabin fingerprint when + // mixing + mMultiplicand = buffer.getLong() | 1; + } + + /** + * Mixes the fingerprint with the derived key material. This is performed by adding part of the + * derived key and multiplying by another part of the derived key (which is forced to be odd, so + * that the operation is reversible). + * + * @param fingerprint A 64-bit Rabin fingerprint. + * @return The mixed fingerprint. + */ + long mix(long fingerprint) { + return ((fingerprint + mAddend) * mMultiplicand); + } + + /** The addend part of the derived key. */ + long getAddend() { + return mAddend; + } + + /** The multiplicand part of the derived key. */ + long getMultiplicand() { + return mMultiplicand; + } +} diff --git a/services/backup/java/com/android/server/backup/encryption/chunking/cdc/Hkdf.java b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/Hkdf.java new file mode 100644 index 000000000000..6f4f549ab2d7 --- /dev/null +++ b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/Hkdf.java @@ -0,0 +1,115 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.android.internal.util.Preconditions.checkNotNull; + +import java.security.InvalidKeyException; +import java.security.NoSuchAlgorithmException; + +import javax.crypto.Mac; +import javax.crypto.spec.SecretKeySpec; + +/** + * Secure HKDF utils. Allows client to deterministically derive additional key material from a base + * secret. If the derived key material is compromised, this does not in of itself compromise the + * root secret. + * + * <p>TODO(b/116575321): After all code is ported, rename this class to HkdfUtils. + */ +public final class Hkdf { + private static final byte[] CONSTANT_01 = {0x01}; + private static final String HmacSHA256 = "HmacSHA256"; + private static final String AES = "AES"; + + /** + * Implements HKDF (RFC 5869) with the SHA-256 hash and a 256-bit output key length. + * + * <p>IMPORTANT: The use or edit of this method requires a security review. + * + * @param masterKey Master key from which to derive sub-keys. + * @param salt A randomly generated 256-bit byte string. + * @param data Arbitrary information that is bound to the derived key (i.e., used in its + * creation). + * @return Raw derived key bytes = HKDF-SHA256(masterKey, salt, data). + * @throws InvalidKeyException If the salt can not be used as a valid key. + */ + static byte[] hkdf(byte[] masterKey, byte[] salt, byte[] data) throws InvalidKeyException { + checkNotNull(masterKey, "HKDF requires master key to be set."); + checkNotNull(salt, "HKDF requires a salt."); + checkNotNull(data, "No data provided to HKDF."); + return hkdfSha256Expand(hkdfSha256Extract(masterKey, salt), data); + } + + private Hkdf() {} + + /** + * The HKDF (RFC 5869) extraction function, using the SHA-256 hash function. This function is + * used to pre-process the {@code inputKeyMaterial} and mix it with the {@code salt}, producing + * output suitable for use with HKDF expansion function (which produces the actual derived key). + * + * <p>IMPORTANT: The use or edit of this method requires a security review. + * + * @see #hkdfSha256Expand(byte[], byte[]) + * @return HMAC-SHA256(salt, inputKeyMaterial) (salt is the "key" for the HMAC) + * @throws InvalidKeyException If the salt can not be used as a valid key. + */ + private static byte[] hkdfSha256Extract(byte[] inputKeyMaterial, byte[] salt) + throws InvalidKeyException { + // Note that the SecretKey encoding format is defined to be RAW, so the encoded form should + // be consistent across implementations. + Mac sha256; + try { + sha256 = Mac.getInstance(HmacSHA256); + } catch (NoSuchAlgorithmException e) { + // This can not happen - HmacSHA256 is supported by the platform. + throw new AssertionError(e); + } + sha256.init(new SecretKeySpec(salt, AES)); + + return sha256.doFinal(inputKeyMaterial); + } + + /** + * Special case of HKDF (RFC 5869) expansion function, using the SHA-256 hash function and + * allowing for a maximum output length of 256 bits. + * + * <p>IMPORTANT: The use or edit of this method requires a security review. + * + * @param pseudoRandomKey Generated by {@link #hkdfSha256Extract(byte[], byte[])}. + * @param info Arbitrary information the derived key should be bound to. + * @return Raw derived key bytes = HMAC-SHA256(pseudoRandomKey, info | 0x01). + * @throws InvalidKeyException If the salt can not be used as a valid key. + */ + private static byte[] hkdfSha256Expand(byte[] pseudoRandomKey, byte[] info) + throws InvalidKeyException { + // Note that RFC 5869 computes number of blocks N = ceil(hash length / output length), but + // here we only deal with a 256 bit hash up to a 256 bit output, yielding N=1. + Mac sha256; + try { + sha256 = Mac.getInstance(HmacSHA256); + } catch (NoSuchAlgorithmException e) { + // This can not happen - HmacSHA256 is supported by the platform. + throw new AssertionError(e); + } + sha256.init(new SecretKeySpec(pseudoRandomKey, AES)); + + sha256.update(info); + sha256.update(CONSTANT_01); + return sha256.doFinal(); + } +} diff --git a/services/backup/java/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpoint.java b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpoint.java new file mode 100644 index 000000000000..e867e7c1b801 --- /dev/null +++ b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpoint.java @@ -0,0 +1,78 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.android.internal.util.Preconditions.checkArgument; + +import com.android.server.backup.encryption.chunking.cdc.ContentDefinedChunker.BreakpointPredicate; + +/** + * Function to determine whether a 64-bit fingerprint ought to be a chunk breakpoint. + * + * <p>This works by checking whether there are at least n leading zeros in the fingerprint. n is + * calculated to on average cause a breakpoint after a given number of trials (provided in the + * constructor). This allows us to choose a number of trials that gives a desired average chunk + * size. This works because the fingerprint is pseudo-randomly distributed. + */ +public class IsChunkBreakpoint implements BreakpointPredicate { + private final int mLeadingZeros; + private final long mBitmask; + + /** + * A new instance that causes a breakpoint after a given number of trials on average. + * + * @param averageNumberOfTrialsUntilBreakpoint The number of trials after which on average to + * create a new chunk. If this is not a power of 2, some precision is sacrificed (i.e., on + * average, breaks will actually happen after the nearest power of 2 to the average number + * of trials passed in). + */ + public IsChunkBreakpoint(long averageNumberOfTrialsUntilBreakpoint) { + checkArgument( + averageNumberOfTrialsUntilBreakpoint >= 0, + "Average number of trials must be non-negative"); + + // Want n leading zeros after t trials. + // P(leading zeros = n) = 1/2^n + // Expected num trials to get n leading zeros = 1/2^-n + // t = 1/2^-n + // n = log2(t) + mLeadingZeros = (int) Math.round(log2(averageNumberOfTrialsUntilBreakpoint)); + mBitmask = ~(~0L >>> mLeadingZeros); + } + + /** + * Returns {@code true} if {@code fingerprint} indicates that there should be a chunk + * breakpoint. + */ + @Override + public boolean isBreakpoint(long fingerprint) { + return (fingerprint & mBitmask) == 0; + } + + /** Returns the number of leading zeros in the fingerprint that causes a breakpoint. */ + public int getLeadingZeros() { + return mLeadingZeros; + } + + /** + * Calculates log base 2 of x. Not the most efficient possible implementation, but it's simple, + * obviously correct, and is only invoked on object construction. + */ + private static double log2(double x) { + return Math.log(x) / Math.log(2); + } +} diff --git a/services/backup/java/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64.java b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64.java new file mode 100644 index 000000000000..1e14ffa5ad77 --- /dev/null +++ b/services/backup/java/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64.java @@ -0,0 +1,113 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +/** Helper to calculate a 64-bit Rabin fingerprint over a 31-byte window. */ +public class RabinFingerprint64 { + private static final long DEFAULT_IRREDUCIBLE_POLYNOMIAL_64 = 0x000000000000001BL; + private static final int POLYNOMIAL_DEGREE = 64; + private static final int SLIDING_WINDOW_SIZE_BYTES = 31; + + private final long mPoly64; + // Auxiliary tables to speed up the computation of Rabin fingerprints. + private final long[] mTableFP64 = new long[256]; + private final long[] mTableOutByte = new long[256]; + + /** + * Constructs a new instance over the given irreducible 64-degree polynomial. It is up to the + * caller to determine that the polynomial is irreducible. If it is not the fingerprinting will + * not behave as expected. + * + * @param poly64 The polynomial. + */ + public RabinFingerprint64(long poly64) { + mPoly64 = poly64; + } + + /** Constructs a new instance using {@code x^64 + x^4 + x + 1} as the irreducible polynomial. */ + public RabinFingerprint64() { + this(DEFAULT_IRREDUCIBLE_POLYNOMIAL_64); + computeFingerprintTables64(); + computeFingerprintTables64Windowed(); + } + + /** + * Computes the fingerprint for the new sliding window given the fingerprint of the previous + * sliding window, the byte sliding in, and the byte sliding out. + * + * @param inChar The new char coming into the sliding window. + * @param outChar The left most char sliding out of the window. + * @param fingerPrint Fingerprint for previous window. + * @return New fingerprint for the new sliding window. + */ + public long computeFingerprint64(byte inChar, byte outChar, long fingerPrint) { + return (fingerPrint << 8) + ^ (inChar & 0xFF) + ^ mTableFP64[(int) (fingerPrint >>> 56)] + ^ mTableOutByte[outChar & 0xFF]; + } + + /** Compute auxiliary tables to speed up the fingerprint computation. */ + private void computeFingerprintTables64() { + long[] degreesRes64 = new long[POLYNOMIAL_DEGREE]; + degreesRes64[0] = mPoly64; + for (int i = 1; i < POLYNOMIAL_DEGREE; i++) { + if ((degreesRes64[i - 1] & (1L << 63)) == 0) { + degreesRes64[i] = degreesRes64[i - 1] << 1; + } else { + degreesRes64[i] = (degreesRes64[i - 1] << 1) ^ mPoly64; + } + } + for (int i = 0; i < 256; i++) { + int currIndex = i; + for (int j = 0; (currIndex > 0) && (j < 8); j++) { + if ((currIndex & 0x1) == 1) { + mTableFP64[i] ^= degreesRes64[j]; + } + currIndex >>>= 1; + } + } + } + + /** + * Compute auxiliary table {@code mTableOutByte} to facilitate the computing of fingerprints for + * sliding windows. This table is to take care of the effect on the fingerprint when the + * leftmost byte in the window slides out. + */ + private void computeFingerprintTables64Windowed() { + // Auxiliary array degsRes64[8] defined by: <code>degsRes64[i] = x^(8 * + // SLIDING_WINDOW_SIZE_BYTES + i) mod this.mPoly64.</code> + long[] degsRes64 = new long[8]; + degsRes64[0] = mPoly64; + for (int i = 65; i < 8 * (SLIDING_WINDOW_SIZE_BYTES + 1); i++) { + if ((degsRes64[(i - 1) % 8] & (1L << 63)) == 0) { + degsRes64[i % 8] = degsRes64[(i - 1) % 8] << 1; + } else { + degsRes64[i % 8] = (degsRes64[(i - 1) % 8] << 1) ^ mPoly64; + } + } + for (int i = 0; i < 256; i++) { + int currIndex = i; + for (int j = 0; (currIndex > 0) && (j < 8); j++) { + if ((currIndex & 0x1) == 1) { + mTableOutByte[i] ^= degsRes64[j]; + } + currIndex >>>= 1; + } + } + } +} diff --git a/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunkerTest.java b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunkerTest.java new file mode 100644 index 000000000000..77b734785424 --- /dev/null +++ b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunkerTest.java @@ -0,0 +1,232 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.android.server.backup.testing.CryptoTestUtils.generateAesKey; + +import static com.google.common.truth.Truth.assertThat; + +import static org.testng.Assert.assertThrows; + +import static java.nio.charset.StandardCharsets.UTF_8; + +import android.platform.test.annotations.Presubmit; + +import org.junit.Before; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.robolectric.RobolectricTestRunner; + +import java.io.ByteArrayInputStream; +import java.io.InputStream; +import java.security.GeneralSecurityException; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Random; + +import javax.crypto.SecretKey; + +/** Tests for {@link ContentDefinedChunker}. */ +@RunWith(RobolectricTestRunner.class) +@Presubmit +public class ContentDefinedChunkerTest { + private static final int WINDOW_SIZE_BYTES = 31; + private static final int MIN_SIZE_BYTES = 40; + private static final int MAX_SIZE_BYTES = 300; + private static final String CHUNK_BOUNDARY = "<----------BOUNDARY----------->"; + private static final byte[] CHUNK_BOUNDARY_BYTES = CHUNK_BOUNDARY.getBytes(UTF_8); + private static final String CHUNK_1 = "This is the first chunk"; + private static final String CHUNK_2 = "And this is the second chunk"; + private static final String CHUNK_3 = "And finally here is the third chunk"; + private static final String SMALL_CHUNK = "12345678"; + + private FingerprintMixer mFingerprintMixer; + private RabinFingerprint64 mRabinFingerprint64; + private ContentDefinedChunker mChunker; + + /** Set up a {@link ContentDefinedChunker} and dependencies for use in the tests. */ + @Before + public void setUp() throws Exception { + SecretKey secretKey = generateAesKey(); + byte[] salt = new byte[FingerprintMixer.SALT_LENGTH_BYTES]; + Random random = new Random(); + random.nextBytes(salt); + mFingerprintMixer = new FingerprintMixer(secretKey, salt); + + mRabinFingerprint64 = new RabinFingerprint64(); + long chunkBoundaryFingerprint = calculateFingerprint(CHUNK_BOUNDARY_BYTES); + mChunker = + new ContentDefinedChunker( + MIN_SIZE_BYTES, + MAX_SIZE_BYTES, + mRabinFingerprint64, + mFingerprintMixer, + (fingerprint) -> fingerprint == chunkBoundaryFingerprint); + } + + /** + * Creating a {@link ContentDefinedChunker} with a minimum chunk size that is smaller than the + * window size should throw an {@link IllegalArgumentException}. + */ + @Test + public void create_withMinChunkSizeSmallerThanWindowSize_throwsIllegalArgumentException() { + assertThrows( + IllegalArgumentException.class, + () -> + new ContentDefinedChunker( + WINDOW_SIZE_BYTES - 1, + MAX_SIZE_BYTES, + mRabinFingerprint64, + mFingerprintMixer, + null)); + } + + /** + * Creating a {@link ContentDefinedChunker} with a maximum chunk size that is smaller than the + * minimum chunk size should throw an {@link IllegalArgumentException}. + */ + @Test + public void create_withMaxChunkSizeSmallerThanMinChunkSize_throwsIllegalArgumentException() { + assertThrows( + IllegalArgumentException.class, + () -> + new ContentDefinedChunker( + MIN_SIZE_BYTES, + MIN_SIZE_BYTES - 1, + mRabinFingerprint64, + mFingerprintMixer, + null)); + } + + /** + * {@link ContentDefinedChunker#chunkify(InputStream, Chunker.ChunkConsumer)} should split the + * input stream across chunk boundaries by default. + */ + @Test + public void chunkify_withLargeChunks_splitsIntoChunksAcrossBoundaries() throws Exception { + byte[] input = + (CHUNK_1 + CHUNK_BOUNDARY + CHUNK_2 + CHUNK_BOUNDARY + CHUNK_3).getBytes(UTF_8); + ByteArrayInputStream inputStream = new ByteArrayInputStream(input); + ArrayList<String> result = new ArrayList<>(); + + mChunker.chunkify(inputStream, (chunk) -> result.add(new String(chunk, UTF_8))); + + assertThat(result) + .containsExactly(CHUNK_1 + CHUNK_BOUNDARY, CHUNK_2 + CHUNK_BOUNDARY, CHUNK_3) + .inOrder(); + } + + /** Chunks should be combined across boundaries until they reach the minimum chunk size. */ + @Test + public void chunkify_withSmallChunks_combinesChunksUntilMinSize() throws Exception { + byte[] input = + (SMALL_CHUNK + CHUNK_BOUNDARY + CHUNK_2 + CHUNK_BOUNDARY + CHUNK_3).getBytes(UTF_8); + ByteArrayInputStream inputStream = new ByteArrayInputStream(input); + ArrayList<String> result = new ArrayList<>(); + + mChunker.chunkify(inputStream, (chunk) -> result.add(new String(chunk, UTF_8))); + + assertThat(result) + .containsExactly(SMALL_CHUNK + CHUNK_BOUNDARY + CHUNK_2 + CHUNK_BOUNDARY, CHUNK_3) + .inOrder(); + assertThat(result.get(0).length()).isAtLeast(MIN_SIZE_BYTES); + } + + /** Chunks can not be larger than the maximum chunk size. */ + @Test + public void chunkify_doesNotProduceChunksLargerThanMaxSize() throws Exception { + byte[] largeInput = new byte[MAX_SIZE_BYTES * 10]; + Arrays.fill(largeInput, "a".getBytes(UTF_8)[0]); + ByteArrayInputStream inputStream = new ByteArrayInputStream(largeInput); + ArrayList<String> result = new ArrayList<>(); + + mChunker.chunkify(inputStream, (chunk) -> result.add(new String(chunk, UTF_8))); + + byte[] expectedChunkBytes = new byte[MAX_SIZE_BYTES]; + Arrays.fill(expectedChunkBytes, "a".getBytes(UTF_8)[0]); + String expectedChunk = new String(expectedChunkBytes, UTF_8); + assertThat(result) + .containsExactly( + expectedChunk, + expectedChunk, + expectedChunk, + expectedChunk, + expectedChunk, + expectedChunk, + expectedChunk, + expectedChunk, + expectedChunk, + expectedChunk) + .inOrder(); + } + + /** + * If the input stream signals zero availablility, {@link + * ContentDefinedChunker#chunkify(InputStream, Chunker.ChunkConsumer)} should still work. + */ + @Test + public void chunkify_withInputStreamReturningZeroAvailability_returnsChunks() throws Exception { + byte[] input = (SMALL_CHUNK + CHUNK_BOUNDARY + CHUNK_2).getBytes(UTF_8); + ZeroAvailabilityInputStream zeroAvailabilityInputStream = + new ZeroAvailabilityInputStream(input); + ArrayList<String> result = new ArrayList<>(); + + mChunker.chunkify( + zeroAvailabilityInputStream, (chunk) -> result.add(new String(chunk, UTF_8))); + + assertThat(result).containsExactly(SMALL_CHUNK + CHUNK_BOUNDARY + CHUNK_2).inOrder(); + } + + /** + * {@link ContentDefinedChunker#chunkify(InputStream, Chunker.ChunkConsumer)} should rethrow any + * exception thrown by its consumer. + */ + @Test + public void chunkify_whenConsumerThrowsException_rethrowsException() throws Exception { + ByteArrayInputStream inputStream = new ByteArrayInputStream(new byte[] {1}); + + assertThrows( + GeneralSecurityException.class, + () -> + mChunker.chunkify( + inputStream, + (chunk) -> { + throw new GeneralSecurityException(); + })); + } + + private long calculateFingerprint(byte[] bytes) { + long fingerprint = 0; + for (byte inByte : bytes) { + fingerprint = + mRabinFingerprint64.computeFingerprint64( + /*inChar=*/ inByte, /*outChar=*/ (byte) 0, fingerprint); + } + return mFingerprintMixer.mix(fingerprint); + } + + private static class ZeroAvailabilityInputStream extends ByteArrayInputStream { + ZeroAvailabilityInputStream(byte[] wrapped) { + super(wrapped); + } + + @Override + public synchronized int available() { + return 0; + } + } +} diff --git a/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/FingerprintMixerTest.java b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/FingerprintMixerTest.java new file mode 100644 index 000000000000..936b5dca033d --- /dev/null +++ b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/FingerprintMixerTest.java @@ -0,0 +1,205 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.google.common.truth.Truth.assertThat; + +import static org.testng.Assert.assertThrows; + +import android.platform.test.annotations.Presubmit; + +import org.junit.Before; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.robolectric.RobolectricTestRunner; + +import java.security.InvalidKeyException; +import java.security.Key; +import java.util.HashSet; +import java.util.Random; + +import javax.crypto.SecretKey; +import javax.crypto.spec.SecretKeySpec; + +/** Tests for {@link FingerprintMixer}. */ +@RunWith(RobolectricTestRunner.class) +@Presubmit +public class FingerprintMixerTest { + private static final String KEY_ALGORITHM = "AES"; + private static final int SEED = 42; + private static final int SALT_LENGTH_BYTES = 256 / 8; + private static final int KEY_SIZE_BITS = 256; + + private Random mSeededRandom; + private FingerprintMixer mFingerprintMixer; + + /** Set up a {@link FingerprintMixer} with deterministic key and salt generation. */ + @Before + public void setUp() throws Exception { + // Seed so that the tests are deterministic. + mSeededRandom = new Random(SEED); + mFingerprintMixer = new FingerprintMixer(randomKey(), randomSalt()); + } + + /** + * Construcing a {@link FingerprintMixer} with a salt that is too small should throw an {@link + * IllegalArgumentException}. + */ + @Test + public void create_withIncorrectSaltSize_throwsIllegalArgumentException() { + byte[] tooSmallSalt = new byte[SALT_LENGTH_BYTES - 1]; + + assertThrows( + IllegalArgumentException.class, + () -> new FingerprintMixer(randomKey(), tooSmallSalt)); + } + + /** + * Constructing a {@link FingerprintMixer} with a secret key that can't be encoded should throw + * an {@link InvalidKeyException}. + */ + @Test + public void create_withUnencodableSecretKey_throwsInvalidKeyException() { + byte[] keyBytes = new byte[KEY_SIZE_BITS / 8]; + UnencodableSecretKeySpec keySpec = + new UnencodableSecretKeySpec(keyBytes, 0, keyBytes.length, KEY_ALGORITHM); + + assertThrows(InvalidKeyException.class, () -> new FingerprintMixer(keySpec, randomSalt())); + } + + /** + * {@link FingerprintMixer#getAddend()} should not return the same addend for two different + * keys. + */ + @Test + public void getAddend_withDifferentKey_returnsDifferentResult() throws Exception { + int iterations = 100_000; + HashSet<Long> returnedAddends = new HashSet<>(); + byte[] salt = randomSalt(); + + for (int i = 0; i < iterations; i++) { + FingerprintMixer fingerprintMixer = new FingerprintMixer(randomKey(), salt); + long addend = fingerprintMixer.getAddend(); + returnedAddends.add(addend); + } + + assertThat(returnedAddends).containsNoDuplicates(); + } + + /** + * {@link FingerprintMixer#getMultiplicand()} should not return the same multiplicand for two + * different keys. + */ + @Test + public void getMultiplicand_withDifferentKey_returnsDifferentResult() throws Exception { + int iterations = 100_000; + HashSet<Long> returnedMultiplicands = new HashSet<>(); + byte[] salt = randomSalt(); + + for (int i = 0; i < iterations; i++) { + FingerprintMixer fingerprintMixer = new FingerprintMixer(randomKey(), salt); + long multiplicand = fingerprintMixer.getMultiplicand(); + returnedMultiplicands.add(multiplicand); + } + + assertThat(returnedMultiplicands).containsNoDuplicates(); + } + + /** The multiplicant returned by {@link FingerprintMixer} should always be odd. */ + @Test + public void getMultiplicand_isOdd() throws Exception { + int iterations = 100_000; + + for (int i = 0; i < iterations; i++) { + FingerprintMixer fingerprintMixer = new FingerprintMixer(randomKey(), randomSalt()); + + long multiplicand = fingerprintMixer.getMultiplicand(); + + assertThat(isOdd(multiplicand)).isTrue(); + } + } + + /** {@link FingerprintMixer#mix(long)} should have a random distribution. */ + @Test + public void mix_randomlyDistributesBits() throws Exception { + int iterations = 100_000; + float tolerance = 0.1f; + int[] totals = new int[64]; + + for (int i = 0; i < iterations; i++) { + long n = mFingerprintMixer.mix(mSeededRandom.nextLong()); + for (int j = 0; j < 64; j++) { + int bit = (int) (n >> j & 1); + totals[j] += bit; + } + } + + for (int i = 0; i < 64; i++) { + float mean = ((float) totals[i]) / iterations; + float diff = Math.abs(mean - 0.5f); + assertThat(diff).isLessThan(tolerance); + } + } + + /** + * {@link FingerprintMixer#mix(long)} should always produce a number that's different from the + * input. + */ + @Test + public void mix_doesNotProduceSameNumberAsInput() { + int iterations = 100_000; + + for (int i = 0; i < iterations; i++) { + assertThat(mFingerprintMixer.mix(i)).isNotEqualTo(i); + } + } + + private byte[] randomSalt() { + byte[] salt = new byte[SALT_LENGTH_BYTES]; + mSeededRandom.nextBytes(salt); + return salt; + } + + /** + * Not a secure way of generating keys. We want to deterministically generate the same keys for + * each test run, though, to ensure the test is deterministic. + */ + private SecretKey randomKey() { + byte[] keyBytes = new byte[KEY_SIZE_BITS / 8]; + mSeededRandom.nextBytes(keyBytes); + return new SecretKeySpec(keyBytes, 0, keyBytes.length, KEY_ALGORITHM); + } + + private static boolean isOdd(long n) { + return Math.abs(n % 2) == 1; + } + + /** + * Subclass of {@link SecretKeySpec} that does not provide an encoded version. As per its + * contract in {@link Key}, that means {@code getEncoded()} always returns null. + */ + private class UnencodableSecretKeySpec extends SecretKeySpec { + UnencodableSecretKeySpec(byte[] key, int offset, int len, String algorithm) { + super(key, offset, len, algorithm); + } + + @Override + public byte[] getEncoded() { + return null; + } + } +} diff --git a/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/HkdfTest.java b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/HkdfTest.java new file mode 100644 index 000000000000..549437454e9c --- /dev/null +++ b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/HkdfTest.java @@ -0,0 +1,95 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.google.common.truth.Truth.assertThat; + +import static org.testng.Assert.assertThrows; + +import android.platform.test.annotations.Presubmit; + +import org.junit.Test; +import org.junit.runner.RunWith; +import org.robolectric.RobolectricTestRunner; + +/** Tests for {@link Hkdf}. */ +@RunWith(RobolectricTestRunner.class) +@Presubmit +public class HkdfTest { + /** HKDF Test Case 1 IKM from RFC 5869 */ + private static final byte[] HKDF_CASE1_IKM = { + 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, + 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, + 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, + 0x0b, 0x0b, 0x0b, 0x0b, 0x0b, + 0x0b, 0x0b + }; + + /** HKDF Test Case 1 salt from RFC 5869 */ + private static final byte[] HKDF_CASE1_SALT = { + 0x00, 0x01, 0x02, 0x03, 0x04, + 0x05, 0x06, 0x07, 0x08, 0x09, + 0x0a, 0x0b, 0x0c + }; + + /** HKDF Test Case 1 info from RFC 5869 */ + private static final byte[] HKDF_CASE1_INFO = { + (byte) 0xf0, (byte) 0xf1, (byte) 0xf2, (byte) 0xf3, (byte) 0xf4, + (byte) 0xf5, (byte) 0xf6, (byte) 0xf7, (byte) 0xf8, (byte) 0xf9 + }; + + /** First 32 bytes of HKDF Test Case 1 OKM (output) from RFC 5869 */ + private static final byte[] HKDF_CASE1_OKM = { + (byte) 0x3c, (byte) 0xb2, (byte) 0x5f, (byte) 0x25, (byte) 0xfa, + (byte) 0xac, (byte) 0xd5, (byte) 0x7a, (byte) 0x90, (byte) 0x43, + (byte) 0x4f, (byte) 0x64, (byte) 0xd0, (byte) 0x36, (byte) 0x2f, + (byte) 0x2a, (byte) 0x2d, (byte) 0x2d, (byte) 0x0a, (byte) 0x90, + (byte) 0xcf, (byte) 0x1a, (byte) 0x5a, (byte) 0x4c, (byte) 0x5d, + (byte) 0xb0, (byte) 0x2d, (byte) 0x56, (byte) 0xec, (byte) 0xc4, + (byte) 0xc5, (byte) 0xbf + }; + + /** Test the example from RFC 5869. */ + @Test + public void hkdf_derivesKeyMaterial() throws Exception { + byte[] result = Hkdf.hkdf(HKDF_CASE1_IKM, HKDF_CASE1_SALT, HKDF_CASE1_INFO); + + assertThat(result).isEqualTo(HKDF_CASE1_OKM); + } + + /** Providing a key that is null should throw a {@link java.lang.NullPointerException}. */ + @Test + public void hkdf_withNullKey_throwsNullPointerException() throws Exception { + assertThrows( + NullPointerException.class, + () -> Hkdf.hkdf(null, HKDF_CASE1_SALT, HKDF_CASE1_INFO)); + } + + /** Providing a salt that is null should throw a {@link java.lang.NullPointerException}. */ + @Test + public void hkdf_withNullSalt_throwsNullPointerException() throws Exception { + assertThrows( + NullPointerException.class, () -> Hkdf.hkdf(HKDF_CASE1_IKM, null, HKDF_CASE1_INFO)); + } + + /** Providing data that is null should throw a {@link java.lang.NullPointerException}. */ + @Test + public void hkdf_withNullData_throwsNullPointerException() throws Exception { + assertThrows( + NullPointerException.class, () -> Hkdf.hkdf(HKDF_CASE1_IKM, HKDF_CASE1_SALT, null)); + } +} diff --git a/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpointTest.java b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpointTest.java new file mode 100644 index 000000000000..277dc372e73c --- /dev/null +++ b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpointTest.java @@ -0,0 +1,122 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.google.common.truth.Truth.assertThat; + +import static org.testng.Assert.assertThrows; + +import android.platform.test.annotations.Presubmit; + +import org.junit.Before; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.robolectric.RobolectricTestRunner; + +import java.util.Random; + +/** Tests for {@link IsChunkBreakpoint}. */ +@RunWith(RobolectricTestRunner.class) +@Presubmit +public class IsChunkBreakpointTest { + private static final int RANDOM_SEED = 42; + private static final double TOLERANCE = 0.01; + private static final int NUMBER_OF_TESTS = 10000; + private static final int BITS_PER_LONG = 64; + + private Random mRandom; + + /** Make sure that tests are deterministic. */ + @Before + public void setUp() { + mRandom = new Random(RANDOM_SEED); + } + + /** + * Providing a negative average number of trials should throw an {@link + * IllegalArgumentException}. + */ + @Test + public void create_withNegativeAverageNumberOfTrials_throwsIllegalArgumentException() { + assertThrows(IllegalArgumentException.class, () -> new IsChunkBreakpoint(-1)); + } + + // Note: the following three tests are compute-intensive, so be cautious adding more. + + /** + * If the provided average number of trials is zero, a breakpoint should be expected after one + * trial on average. + */ + @Test + public void + isBreakpoint_withZeroAverageNumberOfTrials_isTrueOnAverageAfterOneTrial() { + assertExpectedTrials(new IsChunkBreakpoint(0), /*expectedTrials=*/ 1); + } + + /** + * If the provided average number of trials is 512, a breakpoint should be expected after 512 + * trials on average. + */ + @Test + public void + isBreakpoint_with512AverageNumberOfTrials_isTrueOnAverageAfter512Trials() { + assertExpectedTrials(new IsChunkBreakpoint(512), /*expectedTrials=*/ 512); + } + + /** + * If the provided average number of trials is 1024, a breakpoint should be expected after 1024 + * trials on average. + */ + @Test + public void + isBreakpoint_with1024AverageNumberOfTrials_isTrueOnAverageAfter1024Trials() { + assertExpectedTrials(new IsChunkBreakpoint(1024), /*expectedTrials=*/ 1024); + } + + /** The number of leading zeros should be the logarithm of the average number of trials. */ + @Test + public void getLeadingZeros_squaredIsAverageNumberOfTrials() { + for (int i = 0; i < BITS_PER_LONG; i++) { + long averageNumberOfTrials = (long) Math.pow(2, i); + + int leadingZeros = new IsChunkBreakpoint(averageNumberOfTrials).getLeadingZeros(); + + assertThat(leadingZeros).isEqualTo(i); + } + } + + private void assertExpectedTrials(IsChunkBreakpoint isChunkBreakpoint, long expectedTrials) { + long sum = 0; + for (int i = 0; i < NUMBER_OF_TESTS; i++) { + sum += numberOfTrialsTillBreakpoint(isChunkBreakpoint); + } + long averageTrials = sum / NUMBER_OF_TESTS; + assertThat((double) Math.abs(averageTrials - expectedTrials)) + .isLessThan(TOLERANCE * expectedTrials); + } + + private int numberOfTrialsTillBreakpoint(IsChunkBreakpoint isChunkBreakpoint) { + int trials = 0; + + while (true) { + trials++; + if (isChunkBreakpoint.isBreakpoint(mRandom.nextLong())) { + return trials; + } + } + } +} diff --git a/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64Test.java b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64Test.java new file mode 100644 index 000000000000..729580cf5101 --- /dev/null +++ b/services/robotests/src/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64Test.java @@ -0,0 +1,132 @@ +/* + * Copyright (C) 2018 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.server.backup.encryption.chunking.cdc; + +import static com.google.common.truth.Truth.assertThat; + +import static java.nio.charset.StandardCharsets.UTF_8; + +import android.platform.test.annotations.Presubmit; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; + +import org.junit.Test; +import org.junit.runner.RunWith; +import org.robolectric.RobolectricTestRunner; + +/** Tests for {@link RabinFingerprint64}. */ +@RunWith(RobolectricTestRunner.class) +@Presubmit +public class RabinFingerprint64Test { + private static final int WINDOW_SIZE = 31; + private static final ImmutableList<String> TEST_STRINGS = + ImmutableList.of( + "ervHTtChYXO6eXivYqThlyyzqkbRaOR", + "IxaVunH9ZC3qneWfhj1GkBH4ys9CYqz", + "wZRVjlE1p976icCFPX9pibk4PEBvjSH", + "pHIVaT8x8If9D6s9croksgNmJpmGYWI"); + + private final RabinFingerprint64 mRabinFingerprint64 = new RabinFingerprint64(); + + /** + * No matter where in the input buffer a string occurs, {@link + * RabinFingerprint64#computeFingerprint64(byte, byte, long)} should return the same + * fingerprint. + */ + @Test + public void computeFingerprint64_forSameWindow_returnsSameFingerprint() { + long fingerprint1 = + computeFingerprintAtPosition(getBytes(TEST_STRINGS.get(0)), WINDOW_SIZE - 1); + long fingerprint2 = + computeFingerprintAtPosition( + getBytes(TEST_STRINGS.get(1), TEST_STRINGS.get(0)), WINDOW_SIZE * 2 - 1); + long fingerprint3 = + computeFingerprintAtPosition( + getBytes(TEST_STRINGS.get(2), TEST_STRINGS.get(3), TEST_STRINGS.get(0)), + WINDOW_SIZE * 3 - 1); + String stub = "abc"; + long fingerprint4 = + computeFingerprintAtPosition( + getBytes(stub, TEST_STRINGS.get(0)), WINDOW_SIZE + stub.length() - 1); + + // Assert that all fingerprints are exactly the same + assertThat(ImmutableSet.of(fingerprint1, fingerprint2, fingerprint3, fingerprint4)) + .hasSize(1); + } + + /** The computed fingerprint should be different for different inputs. */ + @Test + public void computeFingerprint64_withDifferentInput_returnsDifferentFingerprint() { + long fingerprint1 = computeFingerprintOf(TEST_STRINGS.get(0)); + long fingerprint2 = computeFingerprintOf(TEST_STRINGS.get(1)); + long fingerprint3 = computeFingerprintOf(TEST_STRINGS.get(2)); + long fingerprint4 = computeFingerprintOf(TEST_STRINGS.get(3)); + + assertThat(ImmutableList.of(fingerprint1, fingerprint2, fingerprint3, fingerprint4)) + .containsNoDuplicates(); + } + + /** + * An input with the same characters in a different order should return a different fingerprint. + */ + @Test + public void computeFingerprint64_withSameInputInDifferentOrder_returnsDifferentFingerprint() { + long fingerprint1 = computeFingerprintOf("abcdefghijklmnopqrstuvwxyz12345"); + long fingerprint2 = computeFingerprintOf("54321zyxwvutsrqponmlkjihgfedcba"); + long fingerprint3 = computeFingerprintOf("4bcdefghijklmnopqrstuvwxyz123a5"); + long fingerprint4 = computeFingerprintOf("bacdefghijklmnopqrstuvwxyz12345"); + + assertThat(ImmutableList.of(fingerprint1, fingerprint2, fingerprint3, fingerprint4)) + .containsNoDuplicates(); + } + + /** UTF-8 bytes of all the given strings in order. */ + private byte[] getBytes(String... strings) { + StringBuilder sb = new StringBuilder(); + for (String s : strings) { + sb.append(s); + } + return sb.toString().getBytes(UTF_8); + } + + /** + * The Rabin fingerprint of a window of bytes ending at {@code position} in the {@code bytes} + * array. + */ + private long computeFingerprintAtPosition(byte[] bytes, int position) { + assertThat(position).isAtMost(bytes.length - 1); + long fingerprint = 0; + for (int i = 0; i <= position; i++) { + byte outChar; + if (i >= WINDOW_SIZE) { + outChar = bytes[i - WINDOW_SIZE]; + } else { + outChar = (byte) 0; + } + fingerprint = + mRabinFingerprint64.computeFingerprint64( + /*inChar=*/ bytes[i], outChar, fingerprint); + } + return fingerprint; + } + + private long computeFingerprintOf(String s) { + assertThat(s.length()).isEqualTo(WINDOW_SIZE); + return computeFingerprintAtPosition(s.getBytes(UTF_8), WINDOW_SIZE - 1); + } +} |