Ports chunking/cdc from gmscore to AOSP.
Some additional changes (apart from the regular style modifications)
were needed:
- Guava crypto methods are replaced by their javax equivalents.
- Preconditions checks now depend on com.android.util rather than Guava.
Bug: 111386661,116575321
Test: atest RunFrameworksServicesRoboTests
Change-Id: I43f92f1c0fb3acf62469712d8db212f94429116c
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 0000000..18011f6
--- /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 0000000..e9f3050
--- /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 0000000..6f4f549
--- /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 0000000..e867e7c
--- /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 0000000..1e14ffa
--- /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 0000000..77b7347
--- /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 0000000..936b5dc
--- /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 0000000..5494374
--- /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 0000000..277dc37
--- /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 0000000..729580c
--- /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);
+ }
+}