diff --git a/packages/BackupEncryption/test/robolectric/Android.bp b/packages/BackupEncryption/test/robolectric/Android.bp
new file mode 100644
index 0000000..6d1abbb
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/Android.bp
@@ -0,0 +1,32 @@
+// 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.
+
+android_robolectric_test {
+    name: "BackupEncryptionRoboTests",
+    srcs: [
+        "src/**/*.java",
+        ":FrameworksServicesRoboShadows",
+    ],
+    java_resource_dirs: ["config"],
+    libs: [
+        "platform-test-annotations",
+        "testng",
+    ],
+    instrumentation_for: "BackupEncryption",
+}
+
+filegroup {
+    name: "BackupEncryptionRoboShadows",
+    srcs: ["src/com/android/server/testing/shadows/**/*.java"],
+}
diff --git a/packages/BackupEncryption/test/robolectric/AndroidManifest.xml b/packages/BackupEncryption/test/robolectric/AndroidManifest.xml
new file mode 100644
index 0000000..ae5cdd9
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/AndroidManifest.xml
@@ -0,0 +1,24 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!--
+  Copyright (C) 2019 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.
+  -->
+
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+          coreApp="true"
+          package="com.android.server.backup.encryption.robotests">
+
+    <application/>
+
+</manifest>
diff --git a/packages/BackupEncryption/test/robolectric/config/robolectric.properties b/packages/BackupEncryption/test/robolectric/config/robolectric.properties
new file mode 100644
index 0000000..26fceb3
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/config/robolectric.properties
@@ -0,0 +1,17 @@
+#
+# Copyright (C) 2019 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.
+#
+
+sdk=NEWEST_SDK
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkHashTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkHashTest.java
new file mode 100644
index 0000000..c12464c
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkHashTest.java
@@ -0,0 +1,100 @@
+/*
+ * 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.chunk;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.google.common.primitives.Bytes;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import java.util.Arrays;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class ChunkHashTest {
+    private static final int HASH_LENGTH_BYTES = 256 / 8;
+    private static final byte[] TEST_HASH_1 = Arrays.copyOf(new byte[] {1}, HASH_LENGTH_BYTES);
+    private static final byte[] TEST_HASH_2 = Arrays.copyOf(new byte[] {2}, HASH_LENGTH_BYTES);
+
+    @Test
+    public void testGetHash_returnsHash() {
+        ChunkHash chunkHash = new ChunkHash(TEST_HASH_1);
+
+        byte[] hash = chunkHash.getHash();
+
+        assertThat(hash).asList().containsExactlyElementsIn(Bytes.asList(TEST_HASH_1)).inOrder();
+    }
+
+    @Test
+    public void testEquals() {
+        ChunkHash chunkHash1 = new ChunkHash(TEST_HASH_1);
+        ChunkHash equalChunkHash1 = new ChunkHash(TEST_HASH_1);
+        ChunkHash chunkHash2 = new ChunkHash(TEST_HASH_2);
+
+        assertThat(chunkHash1).isEqualTo(equalChunkHash1);
+        assertThat(chunkHash1).isNotEqualTo(chunkHash2);
+    }
+
+    @Test
+    public void testHashCode() {
+        ChunkHash chunkHash1 = new ChunkHash(TEST_HASH_1);
+        ChunkHash equalChunkHash1 = new ChunkHash(TEST_HASH_1);
+        ChunkHash chunkHash2 = new ChunkHash(TEST_HASH_2);
+
+        int hash1 = chunkHash1.hashCode();
+        int equalHash1 = equalChunkHash1.hashCode();
+        int hash2 = chunkHash2.hashCode();
+
+        assertThat(hash1).isEqualTo(equalHash1);
+        assertThat(hash1).isNotEqualTo(hash2);
+    }
+
+    @Test
+    public void testCompareTo_whenEqual_returnsZero() {
+        ChunkHash chunkHash = new ChunkHash(TEST_HASH_1);
+        ChunkHash equalChunkHash = new ChunkHash(TEST_HASH_1);
+
+        int result = chunkHash.compareTo(equalChunkHash);
+
+        assertThat(result).isEqualTo(0);
+    }
+
+    @Test
+    public void testCompareTo_whenArgumentGreater_returnsNegative() {
+        ChunkHash chunkHash1 = new ChunkHash(TEST_HASH_1);
+        ChunkHash chunkHash2 = new ChunkHash(TEST_HASH_2);
+
+        int result = chunkHash1.compareTo(chunkHash2);
+
+        assertThat(result).isLessThan(0);
+    }
+
+    @Test
+    public void testCompareTo_whenArgumentSmaller_returnsPositive() {
+        ChunkHash chunkHash1 = new ChunkHash(TEST_HASH_1);
+        ChunkHash chunkHash2 = new ChunkHash(TEST_HASH_2);
+
+        int result = chunkHash2.compareTo(chunkHash1);
+
+        assertThat(result).isGreaterThan(0);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkListingMapTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkListingMapTest.java
new file mode 100644
index 0000000..24e5573
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkListingMapTest.java
@@ -0,0 +1,197 @@
+/*
+ * Copyright (C) 2019 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.chunk;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+import android.util.proto.ProtoInputStream;
+import android.util.proto.ProtoOutputStream;
+
+import com.android.internal.util.Preconditions;
+
+import com.google.common.base.Charsets;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import java.io.ByteArrayInputStream;
+import java.util.Arrays;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class ChunkListingMapTest {
+    private static final String CHUNK_A = "CHUNK_A";
+    private static final String CHUNK_B = "CHUNK_B";
+    private static final String CHUNK_C = "CHUNK_C";
+
+    private static final int CHUNK_A_LENGTH = 256;
+    private static final int CHUNK_B_LENGTH = 1024;
+    private static final int CHUNK_C_LENGTH = 4055;
+
+    private ChunkHash mChunkHashA;
+    private ChunkHash mChunkHashB;
+    private ChunkHash mChunkHashC;
+
+    @Before
+    public void setUp() throws Exception {
+        mChunkHashA = getHash(CHUNK_A);
+        mChunkHashB = getHash(CHUNK_B);
+        mChunkHashC = getHash(CHUNK_C);
+    }
+
+    @Test
+    public void testHasChunk_whenChunkInListing_returnsTrue() throws Exception {
+        byte[] chunkListingProto =
+                createChunkListingProto(
+                        new ChunkHash[] {mChunkHashA, mChunkHashB, mChunkHashC},
+                        new int[] {CHUNK_A_LENGTH, CHUNK_B_LENGTH, CHUNK_C_LENGTH});
+        ChunkListingMap chunkListingMap =
+                ChunkListingMap.readFromProto(
+                        new ProtoInputStream(new ByteArrayInputStream(chunkListingProto)));
+
+        boolean chunkAInList = chunkListingMap.hasChunk(mChunkHashA);
+        boolean chunkBInList = chunkListingMap.hasChunk(mChunkHashB);
+        boolean chunkCInList = chunkListingMap.hasChunk(mChunkHashC);
+
+        assertThat(chunkAInList).isTrue();
+        assertThat(chunkBInList).isTrue();
+        assertThat(chunkCInList).isTrue();
+    }
+
+    @Test
+    public void testHasChunk_whenChunkNotInListing_returnsFalse() throws Exception {
+        byte[] chunkListingProto =
+                createChunkListingProto(
+                        new ChunkHash[] {mChunkHashA, mChunkHashB},
+                        new int[] {CHUNK_A_LENGTH, CHUNK_B_LENGTH});
+        ChunkListingMap chunkListingMap =
+                ChunkListingMap.readFromProto(
+                        new ProtoInputStream(new ByteArrayInputStream(chunkListingProto)));
+        ChunkHash chunkHashEmpty = getHash("");
+
+        boolean chunkCInList = chunkListingMap.hasChunk(mChunkHashC);
+        boolean emptyChunkInList = chunkListingMap.hasChunk(chunkHashEmpty);
+
+        assertThat(chunkCInList).isFalse();
+        assertThat(emptyChunkInList).isFalse();
+    }
+
+    @Test
+    public void testGetChunkEntry_returnsEntryWithCorrectLength() throws Exception {
+        byte[] chunkListingProto =
+                createChunkListingProto(
+                        new ChunkHash[] {mChunkHashA, mChunkHashB, mChunkHashC},
+                        new int[] {CHUNK_A_LENGTH, CHUNK_B_LENGTH, CHUNK_C_LENGTH});
+        ChunkListingMap chunkListingMap =
+                ChunkListingMap.readFromProto(
+                        new ProtoInputStream(new ByteArrayInputStream(chunkListingProto)));
+
+        ChunkListingMap.Entry entryA = chunkListingMap.getChunkEntry(mChunkHashA);
+        ChunkListingMap.Entry entryB = chunkListingMap.getChunkEntry(mChunkHashB);
+        ChunkListingMap.Entry entryC = chunkListingMap.getChunkEntry(mChunkHashC);
+
+        assertThat(entryA.getLength()).isEqualTo(CHUNK_A_LENGTH);
+        assertThat(entryB.getLength()).isEqualTo(CHUNK_B_LENGTH);
+        assertThat(entryC.getLength()).isEqualTo(CHUNK_C_LENGTH);
+    }
+
+    @Test
+    public void testGetChunkEntry_returnsEntryWithCorrectStart() throws Exception {
+        byte[] chunkListingProto =
+                createChunkListingProto(
+                        new ChunkHash[] {mChunkHashA, mChunkHashB, mChunkHashC},
+                        new int[] {CHUNK_A_LENGTH, CHUNK_B_LENGTH, CHUNK_C_LENGTH});
+        ChunkListingMap chunkListingMap =
+                ChunkListingMap.readFromProto(
+                        new ProtoInputStream(new ByteArrayInputStream(chunkListingProto)));
+
+        ChunkListingMap.Entry entryA = chunkListingMap.getChunkEntry(mChunkHashA);
+        ChunkListingMap.Entry entryB = chunkListingMap.getChunkEntry(mChunkHashB);
+        ChunkListingMap.Entry entryC = chunkListingMap.getChunkEntry(mChunkHashC);
+
+        assertThat(entryA.getStart()).isEqualTo(0);
+        assertThat(entryB.getStart()).isEqualTo(CHUNK_A_LENGTH);
+        assertThat(entryC.getStart()).isEqualTo(CHUNK_A_LENGTH + CHUNK_B_LENGTH);
+    }
+
+    @Test
+    public void testGetChunkEntry_returnsNullForNonExistentChunk() throws Exception {
+        byte[] chunkListingProto =
+                createChunkListingProto(
+                        new ChunkHash[] {mChunkHashA, mChunkHashB},
+                        new int[] {CHUNK_A_LENGTH, CHUNK_B_LENGTH});
+        ChunkListingMap chunkListingMap =
+                ChunkListingMap.readFromProto(
+                        new ProtoInputStream(new ByteArrayInputStream(chunkListingProto)));
+
+        ChunkListingMap.Entry chunkEntryNonexistentChunk =
+                chunkListingMap.getChunkEntry(mChunkHashC);
+
+        assertThat(chunkEntryNonexistentChunk).isNull();
+    }
+
+    @Test
+    public void testReadFromProto_whenEmptyProto_returnsChunkListingMapWith0Chunks()
+            throws Exception {
+        ProtoInputStream emptyProto = new ProtoInputStream(new ByteArrayInputStream(new byte[] {}));
+
+        ChunkListingMap chunkListingMap = ChunkListingMap.readFromProto(emptyProto);
+
+        assertThat(chunkListingMap.getChunkCount()).isEqualTo(0);
+    }
+
+    @Test
+    public void testReadFromProto_returnsChunkListingWithCorrectSize() throws Exception {
+        byte[] chunkListingProto =
+                createChunkListingProto(
+                        new ChunkHash[] {mChunkHashA, mChunkHashB, mChunkHashC},
+                        new int[] {CHUNK_A_LENGTH, CHUNK_B_LENGTH, CHUNK_C_LENGTH});
+
+        ChunkListingMap chunkListingMap =
+                ChunkListingMap.readFromProto(
+                        new ProtoInputStream(new ByteArrayInputStream(chunkListingProto)));
+
+        assertThat(chunkListingMap.getChunkCount()).isEqualTo(3);
+    }
+
+    private byte[] createChunkListingProto(ChunkHash[] hashes, int[] lengths) {
+        Preconditions.checkArgument(hashes.length == lengths.length);
+        ProtoOutputStream outputStream = new ProtoOutputStream();
+
+        for (int i = 0; i < hashes.length; ++i) {
+            writeToProtoOutputStream(outputStream, hashes[i], lengths[i]);
+        }
+        outputStream.flush();
+
+        return outputStream.getBytes();
+    }
+
+    private void writeToProtoOutputStream(ProtoOutputStream out, ChunkHash chunkHash, int length) {
+        long token = out.start(ChunksMetadataProto.ChunkListing.CHUNKS);
+        out.write(ChunksMetadataProto.Chunk.HASH, chunkHash.getHash());
+        out.write(ChunksMetadataProto.Chunk.LENGTH, length);
+        out.end(token);
+    }
+
+    private ChunkHash getHash(String name) {
+        return new ChunkHash(
+                Arrays.copyOf(name.getBytes(Charsets.UTF_8), ChunkHash.HASH_LENGTH_BYTES));
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkTest.java
new file mode 100644
index 0000000..1796f56
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/ChunkTest.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.chunk;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+import android.util.proto.ProtoInputStream;
+import android.util.proto.ProtoOutputStream;
+
+import com.google.common.base.Charsets;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import java.io.ByteArrayInputStream;
+import java.util.Arrays;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class ChunkTest {
+    private static final String CHUNK_A = "CHUNK_A";
+    private static final int CHUNK_A_LENGTH = 256;
+
+    private ChunkHash mChunkHashA;
+
+    @Before
+    public void setUp() throws Exception {
+        mChunkHashA = getHash(CHUNK_A);
+    }
+
+    @Test
+    public void testReadFromProto_readsCorrectly() throws Exception {
+        ProtoOutputStream out = new ProtoOutputStream();
+        out.write(ChunksMetadataProto.Chunk.HASH, mChunkHashA.getHash());
+        out.write(ChunksMetadataProto.Chunk.LENGTH, CHUNK_A_LENGTH);
+        out.flush();
+        byte[] protoBytes = out.getBytes();
+
+        Chunk chunk =
+                Chunk.readFromProto(new ProtoInputStream(new ByteArrayInputStream(protoBytes)));
+
+        assertThat(chunk.getHash()).isEqualTo(mChunkHashA.getHash());
+        assertThat(chunk.getLength()).isEqualTo(CHUNK_A_LENGTH);
+    }
+
+    @Test
+    public void testReadFromProto_whenFieldsWrittenInReversedOrder_readsCorrectly()
+            throws Exception {
+        ProtoOutputStream out = new ProtoOutputStream();
+        // Write fields of Chunk proto in reverse order.
+        out.write(ChunksMetadataProto.Chunk.LENGTH, CHUNK_A_LENGTH);
+        out.write(ChunksMetadataProto.Chunk.HASH, mChunkHashA.getHash());
+        out.flush();
+        byte[] protoBytes = out.getBytes();
+
+        Chunk chunk =
+                Chunk.readFromProto(new ProtoInputStream(new ByteArrayInputStream(protoBytes)));
+
+        assertThat(chunk.getHash()).isEqualTo(mChunkHashA.getHash());
+        assertThat(chunk.getLength()).isEqualTo(CHUNK_A_LENGTH);
+    }
+
+    @Test
+    public void testReadFromProto_whenEmptyProto_returnsEmptyHash() throws Exception {
+        ProtoInputStream emptyProto = new ProtoInputStream(new ByteArrayInputStream(new byte[] {}));
+
+        Chunk chunk = Chunk.readFromProto(emptyProto);
+
+        assertThat(chunk.getHash()).asList().hasSize(0);
+        assertThat(chunk.getLength()).isEqualTo(0);
+    }
+
+    @Test
+    public void testReadFromProto_whenOnlyHashSet_returnsChunkWithOnlyHash() throws Exception {
+        ProtoOutputStream out = new ProtoOutputStream();
+        out.write(ChunksMetadataProto.Chunk.HASH, mChunkHashA.getHash());
+        out.flush();
+        byte[] protoBytes = out.getBytes();
+
+        Chunk chunk =
+                Chunk.readFromProto(new ProtoInputStream(new ByteArrayInputStream(protoBytes)));
+
+        assertThat(chunk.getHash()).isEqualTo(mChunkHashA.getHash());
+        assertThat(chunk.getLength()).isEqualTo(0);
+    }
+
+    @Test
+    public void testReadFromProto_whenOnlyLengthSet_returnsChunkWithOnlyLength() throws Exception {
+        ProtoOutputStream out = new ProtoOutputStream();
+        out.write(ChunksMetadataProto.Chunk.LENGTH, CHUNK_A_LENGTH);
+        out.flush();
+        byte[] protoBytes = out.getBytes();
+
+        Chunk chunk =
+                Chunk.readFromProto(new ProtoInputStream(new ByteArrayInputStream(protoBytes)));
+
+        assertThat(chunk.getHash()).isEqualTo(new byte[] {});
+        assertThat(chunk.getLength()).isEqualTo(CHUNK_A_LENGTH);
+    }
+
+    private ChunkHash getHash(String name) {
+        return new ChunkHash(
+                Arrays.copyOf(name.getBytes(Charsets.UTF_8), ChunkHash.HASH_LENGTH_BYTES));
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/EncryptedChunkOrderingTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/EncryptedChunkOrderingTest.java
new file mode 100644
index 0000000..c6b29b7b
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunk/EncryptedChunkOrderingTest.java
@@ -0,0 +1,73 @@
+/*
+ * 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.chunk;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.google.common.primitives.Bytes;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class EncryptedChunkOrderingTest {
+    private static final byte[] TEST_BYTE_ARRAY_1 = new byte[] {1, 2, 3, 4, 5};
+    private static final byte[] TEST_BYTE_ARRAY_2 = new byte[] {5, 4, 3, 2, 1};
+
+    @Test
+    public void testEncryptedChunkOrdering_returnsValue() {
+        EncryptedChunkOrdering encryptedChunkOrdering =
+                EncryptedChunkOrdering.create(TEST_BYTE_ARRAY_1);
+
+        byte[] bytes = encryptedChunkOrdering.encryptedChunkOrdering();
+
+        assertThat(bytes)
+                .asList()
+                .containsExactlyElementsIn(Bytes.asList(TEST_BYTE_ARRAY_1))
+                .inOrder();
+    }
+
+    @Test
+    public void testEquals() {
+        EncryptedChunkOrdering chunkOrdering1 = EncryptedChunkOrdering.create(TEST_BYTE_ARRAY_1);
+        EncryptedChunkOrdering equalChunkOrdering1 =
+                EncryptedChunkOrdering.create(TEST_BYTE_ARRAY_1);
+        EncryptedChunkOrdering chunkOrdering2 = EncryptedChunkOrdering.create(TEST_BYTE_ARRAY_2);
+
+        assertThat(chunkOrdering1).isEqualTo(equalChunkOrdering1);
+        assertThat(chunkOrdering1).isNotEqualTo(chunkOrdering2);
+    }
+
+    @Test
+    public void testHashCode() {
+        EncryptedChunkOrdering chunkOrdering1 = EncryptedChunkOrdering.create(TEST_BYTE_ARRAY_1);
+        EncryptedChunkOrdering equalChunkOrdering1 =
+                EncryptedChunkOrdering.create(TEST_BYTE_ARRAY_1);
+        EncryptedChunkOrdering chunkOrdering2 = EncryptedChunkOrdering.create(TEST_BYTE_ARRAY_2);
+
+        int hash1 = chunkOrdering1.hashCode();
+        int equalHash1 = equalChunkOrdering1.hashCode();
+        int hash2 = chunkOrdering2.hashCode();
+
+        assertThat(hash1).isEqualTo(equalHash1);
+        assertThat(hash1).isNotEqualTo(hash2);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ByteRangeTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ByteRangeTest.java
new file mode 100644
index 0000000..8df0826
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ByteRangeTest.java
@@ -0,0 +1,57 @@
+/*
+ * 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;
+
+import static org.junit.Assert.assertEquals;
+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 ByteRange}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class ByteRangeTest {
+    @Test
+    public void getLength_includesEnd() throws Exception {
+        ByteRange byteRange = new ByteRange(5, 10);
+
+        int length = byteRange.getLength();
+
+        assertEquals(6, length);
+    }
+
+    @Test
+    public void constructor_rejectsNegativeStart() {
+        assertThrows(IllegalArgumentException.class, () -> new ByteRange(-1, 10));
+    }
+
+    @Test
+    public void constructor_rejectsEndBeforeStart() {
+        assertThrows(IllegalArgumentException.class, () -> new ByteRange(10, 9));
+    }
+
+    @Test
+    public void extend_withZeroLength_throwsException() {
+        ByteRange byteRange = new ByteRange(5, 10);
+
+        assertThrows(IllegalArgumentException.class, () -> byteRange.extend(0));
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ChunkEncryptorTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ChunkEncryptorTest.java
new file mode 100644
index 0000000..19e3b28
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ChunkEncryptorTest.java
@@ -0,0 +1,157 @@
+/*
+ * 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;
+
+import static com.android.server.backup.testing.CryptoTestUtils.generateAesKey;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.mockito.ArgumentMatchers.any;
+import static org.mockito.Mockito.doAnswer;
+import static org.mockito.Mockito.mock;
+
+import static java.nio.charset.StandardCharsets.UTF_8;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.Mock;
+import org.mockito.invocation.InvocationOnMock;
+import org.mockito.stubbing.Answer;
+import org.robolectric.RobolectricTestRunner;
+
+import java.security.SecureRandom;
+
+import javax.crypto.Cipher;
+import javax.crypto.Mac;
+import javax.crypto.SecretKey;
+import javax.crypto.spec.GCMParameterSpec;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class ChunkEncryptorTest {
+    private static final String MAC_ALGORITHM = "HmacSHA256";
+    private static final String CIPHER_ALGORITHM = "AES/GCM/NoPadding";
+    private static final int GCM_NONCE_LENGTH_BYTES = 12;
+    private static final int GCM_TAG_LENGTH_BYTES = 16;
+    private static final String CHUNK_PLAINTEXT =
+            "A little Learning is a dang'rous Thing;\n"
+                    + "Drink deep, or taste not the Pierian Spring:\n"
+                    + "There shallow Draughts intoxicate the Brain,\n"
+                    + "And drinking largely sobers us again.";
+    private static final byte[] PLAINTEXT_BYTES = CHUNK_PLAINTEXT.getBytes(UTF_8);
+    private static final byte[] NONCE_1 = "0123456789abc".getBytes(UTF_8);
+    private static final byte[] NONCE_2 = "123456789abcd".getBytes(UTF_8);
+
+    private static final byte[][] NONCES = new byte[][] {NONCE_1, NONCE_2};
+
+    @Mock private SecureRandom mSecureRandomMock;
+    private SecretKey mSecretKey;
+    private ChunkHash mPlaintextHash;
+    private ChunkEncryptor mChunkEncryptor;
+
+    @Before
+    public void setUp() throws Exception {
+        mSecretKey = generateAesKey();
+        ChunkHasher chunkHasher = new ChunkHasher(mSecretKey);
+        mPlaintextHash = chunkHasher.computeHash(PLAINTEXT_BYTES);
+        mSecureRandomMock = mock(SecureRandom.class);
+        mChunkEncryptor = new ChunkEncryptor(mSecretKey, mSecureRandomMock);
+
+        // Return NONCE_1, then NONCE_2 for invocations of mSecureRandomMock.nextBytes().
+        doAnswer(
+                    new Answer<Void>() {
+                        private int mInvocation = 0;
+
+                        @Override
+                        public Void answer(InvocationOnMock invocation) {
+                            byte[] nonceDestination = invocation.getArgument(0);
+                            System.arraycopy(
+                                    NONCES[this.mInvocation],
+                                    0,
+                                    nonceDestination,
+                                    0,
+                                    GCM_NONCE_LENGTH_BYTES);
+                            this.mInvocation++;
+                            return null;
+                        }
+                    })
+                .when(mSecureRandomMock)
+                .nextBytes(any(byte[].class));
+    }
+
+    @Test
+    public void encrypt_withHash_resultContainsHashAsKey() throws Exception {
+        EncryptedChunk chunk = mChunkEncryptor.encrypt(mPlaintextHash, PLAINTEXT_BYTES);
+
+        assertThat(chunk.key()).isEqualTo(mPlaintextHash);
+    }
+
+    @Test
+    public void encrypt_generatesHmacOfPlaintext() throws Exception {
+        EncryptedChunk chunk = mChunkEncryptor.encrypt(mPlaintextHash, PLAINTEXT_BYTES);
+
+        byte[] generatedHash = chunk.key().getHash();
+        Mac mac = Mac.getInstance(MAC_ALGORITHM);
+        mac.init(mSecretKey);
+        byte[] plaintextHmac = mac.doFinal(PLAINTEXT_BYTES);
+        assertThat(generatedHash).isEqualTo(plaintextHmac);
+    }
+
+    @Test
+    public void encrypt_whenInvokedAgain_generatesNewNonce() throws Exception {
+        EncryptedChunk chunk1 = mChunkEncryptor.encrypt(mPlaintextHash, PLAINTEXT_BYTES);
+
+        EncryptedChunk chunk2 = mChunkEncryptor.encrypt(mPlaintextHash, PLAINTEXT_BYTES);
+
+        assertThat(chunk1.nonce()).isNotEqualTo(chunk2.nonce());
+    }
+
+    @Test
+    public void encrypt_whenInvokedAgain_generatesNewCiphertext() throws Exception {
+        EncryptedChunk chunk1 = mChunkEncryptor.encrypt(mPlaintextHash, PLAINTEXT_BYTES);
+
+        EncryptedChunk chunk2 = mChunkEncryptor.encrypt(mPlaintextHash, PLAINTEXT_BYTES);
+
+        assertThat(chunk1.encryptedBytes()).isNotEqualTo(chunk2.encryptedBytes());
+    }
+
+    @Test
+    public void encrypt_generates12ByteNonce() throws Exception {
+        EncryptedChunk encryptedChunk = mChunkEncryptor.encrypt(mPlaintextHash, PLAINTEXT_BYTES);
+
+        byte[] nonce = encryptedChunk.nonce();
+        assertThat(nonce).hasLength(GCM_NONCE_LENGTH_BYTES);
+    }
+
+    @Test
+    public void encrypt_decryptedResultCorrespondsToPlaintext() throws Exception {
+        EncryptedChunk chunk = mChunkEncryptor.encrypt(mPlaintextHash, PLAINTEXT_BYTES);
+
+        Cipher cipher = Cipher.getInstance(CIPHER_ALGORITHM);
+        cipher.init(
+                Cipher.DECRYPT_MODE,
+                mSecretKey,
+                new GCMParameterSpec(GCM_TAG_LENGTH_BYTES * 8, chunk.nonce()));
+        byte[] decrypted = cipher.doFinal(chunk.encryptedBytes());
+        assertThat(decrypted).isEqualTo(PLAINTEXT_BYTES);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ChunkHasherTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ChunkHasherTest.java
new file mode 100644
index 0000000..72a927d
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/ChunkHasherTest.java
@@ -0,0 +1,71 @@
+/*
+ * 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;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import javax.crypto.Mac;
+import javax.crypto.SecretKey;
+import javax.crypto.spec.SecretKeySpec;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class ChunkHasherTest {
+    private static final String KEY_ALGORITHM = "AES";
+    private static final String MAC_ALGORITHM = "HmacSHA256";
+
+    private static final byte[] TEST_KEY = {100, 120};
+    private static final byte[] TEST_DATA = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
+
+    private SecretKey mSecretKey;
+    private ChunkHasher mChunkHasher;
+
+    @Before
+    public void setUp() throws Exception {
+        mSecretKey = new SecretKeySpec(TEST_KEY, KEY_ALGORITHM);
+        mChunkHasher = new ChunkHasher(mSecretKey);
+    }
+
+    @Test
+    public void computeHash_returnsHmacForData() throws Exception {
+        ChunkHash chunkHash = mChunkHasher.computeHash(TEST_DATA);
+
+        byte[] hash = chunkHash.getHash();
+        Mac mac = Mac.getInstance(MAC_ALGORITHM);
+        mac.init(mSecretKey);
+        byte[] expectedHash = mac.doFinal(TEST_DATA);
+        assertThat(hash).isEqualTo(expectedHash);
+    }
+
+    @Test
+    public void computeHash_generates256BitHmac() throws Exception {
+        int expectedLength = 256 / Byte.SIZE;
+
+        byte[] hash = mChunkHasher.computeHash(TEST_DATA).getHash();
+
+        assertThat(hash).hasLength(expectedLength);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/DecryptedChunkFileOutputTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/DecryptedChunkFileOutputTest.java
new file mode 100644
index 0000000..823a63c
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/DecryptedChunkFileOutputTest.java
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2019 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;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.testng.Assert.assertThrows;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.android.server.backup.encryption.tasks.DecryptedChunkOutput;
+
+import com.google.common.io.Files;
+import com.google.common.primitives.Bytes;
+
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import java.io.File;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.security.MessageDigest;
+import java.util.Arrays;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class DecryptedChunkFileOutputTest {
+    private static final byte[] TEST_CHUNK_1 = {1, 2, 3};
+    private static final byte[] TEST_CHUNK_2 = {4, 5, 6, 7, 8, 9, 10};
+    private static final int TEST_BUFFER_LENGTH =
+            Math.max(TEST_CHUNK_1.length, TEST_CHUNK_2.length);
+
+    @Rule
+    public TemporaryFolder temporaryFolder = new TemporaryFolder();
+
+    private File mOutputFile;
+    private DecryptedChunkFileOutput mDecryptedChunkFileOutput;
+
+    @Before
+    public void setUp() throws Exception {
+        mOutputFile = temporaryFolder.newFile();
+        mDecryptedChunkFileOutput = new DecryptedChunkFileOutput(mOutputFile);
+    }
+
+    @Test
+    public void open_returnsInstance() throws Exception {
+        DecryptedChunkOutput result = mDecryptedChunkFileOutput.open();
+        assertThat(result).isEqualTo(mDecryptedChunkFileOutput);
+    }
+
+    @Test
+    public void open_nonExistentOutputFolder_throwsException() throws Exception {
+        mDecryptedChunkFileOutput =
+                new DecryptedChunkFileOutput(
+                        new File(temporaryFolder.newFolder(), "mOutput/directory"));
+        assertThrows(FileNotFoundException.class, () -> mDecryptedChunkFileOutput.open());
+    }
+
+    @Test
+    public void open_whenRunTwice_throwsException() throws Exception {
+        mDecryptedChunkFileOutput.open();
+        assertThrows(IllegalStateException.class, () -> mDecryptedChunkFileOutput.open());
+    }
+
+    @Test
+    public void processChunk_beforeOpen_throwsException() throws Exception {
+        assertThrows(IllegalStateException.class,
+                () -> mDecryptedChunkFileOutput.processChunk(new byte[0], 0));
+    }
+
+    @Test
+    public void processChunk_writesChunksToFile() throws Exception {
+        processTestChunks();
+
+        assertThat(Files.toByteArray(mOutputFile))
+                .isEqualTo(Bytes.concat(TEST_CHUNK_1, TEST_CHUNK_2));
+    }
+
+    @Test
+    public void getDigest_beforeClose_throws() throws Exception {
+        mDecryptedChunkFileOutput.open();
+        assertThrows(IllegalStateException.class, () -> mDecryptedChunkFileOutput.getDigest());
+    }
+
+    @Test
+    public void getDigest_returnsCorrectDigest() throws Exception {
+        processTestChunks();
+
+        byte[] actualDigest = mDecryptedChunkFileOutput.getDigest();
+
+        MessageDigest expectedDigest =
+                MessageDigest.getInstance(DecryptedChunkFileOutput.DIGEST_ALGORITHM);
+        expectedDigest.update(TEST_CHUNK_1);
+        expectedDigest.update(TEST_CHUNK_2);
+        assertThat(actualDigest).isEqualTo(expectedDigest.digest());
+    }
+
+    @Test
+    public void getDigest_whenRunTwice_returnsIdenticalDigestBothTimes() throws Exception {
+        processTestChunks();
+
+        byte[] digest1 = mDecryptedChunkFileOutput.getDigest();
+        byte[] digest2 = mDecryptedChunkFileOutput.getDigest();
+
+        assertThat(digest1).isEqualTo(digest2);
+    }
+
+    private void processTestChunks() throws IOException {
+        mDecryptedChunkFileOutput.open();
+        mDecryptedChunkFileOutput.processChunk(Arrays.copyOf(TEST_CHUNK_1, TEST_BUFFER_LENGTH),
+                TEST_CHUNK_1.length);
+        mDecryptedChunkFileOutput.processChunk(Arrays.copyOf(TEST_CHUNK_2, TEST_BUFFER_LENGTH),
+                TEST_CHUNK_2.length);
+        mDecryptedChunkFileOutput.close();
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/DiffScriptBackupWriterTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/DiffScriptBackupWriterTest.java
new file mode 100644
index 0000000..2af6f2b
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/DiffScriptBackupWriterTest.java
@@ -0,0 +1,90 @@
+/*
+ * 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;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.mockito.Mockito.atLeastOnce;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.verify;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.google.common.primitives.Bytes;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.ArgumentCaptor;
+import org.mockito.Captor;
+import org.mockito.Mock;
+import org.robolectric.RobolectricTestRunner;
+
+import java.io.IOException;
+
+/** Tests for {@link DiffScriptBackupWriter}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class DiffScriptBackupWriterTest {
+    private static final byte[] TEST_BYTES = {1, 2, 3, 4, 5, 6, 7, 8, 9};
+
+    @Captor private ArgumentCaptor<Byte> mBytesCaptor;
+    @Mock private SingleStreamDiffScriptWriter mDiffScriptWriter;
+    private BackupWriter mBackupWriter;
+
+    @Before
+    public void setUp() {
+        mDiffScriptWriter = mock(SingleStreamDiffScriptWriter.class);
+        mBackupWriter = new DiffScriptBackupWriter(mDiffScriptWriter);
+        mBytesCaptor = ArgumentCaptor.forClass(Byte.class);
+    }
+
+    @Test
+    public void writeBytes_writesBytesToWriter() throws Exception {
+        mBackupWriter.writeBytes(TEST_BYTES);
+
+        verify(mDiffScriptWriter, atLeastOnce()).writeByte(mBytesCaptor.capture());
+        assertThat(mBytesCaptor.getAllValues())
+                .containsExactlyElementsIn(Bytes.asList(TEST_BYTES))
+                .inOrder();
+    }
+
+    @Test
+    public void writeChunk_writesChunkToWriter() throws Exception {
+        mBackupWriter.writeChunk(0, 10);
+
+        verify(mDiffScriptWriter).writeChunk(0, 10);
+    }
+
+    @Test
+    public void getBytesWritten_returnsTotalSum() throws Exception {
+        mBackupWriter.writeBytes(TEST_BYTES);
+        mBackupWriter.writeBytes(TEST_BYTES);
+        mBackupWriter.writeChunk(/*start=*/ 0, /*length=*/ 10);
+
+        long bytesWritten = mBackupWriter.getBytesWritten();
+
+        assertThat(bytesWritten).isEqualTo(2 * TEST_BYTES.length + 10);
+    }
+
+    @Test
+    public void flush_flushesWriter() throws IOException {
+        mBackupWriter.flush();
+
+        verify(mDiffScriptWriter).flush();
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/EncryptedChunkTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/EncryptedChunkTest.java
new file mode 100644
index 0000000..325b601
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/EncryptedChunkTest.java
@@ -0,0 +1,133 @@
+/*
+ * 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;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.testng.Assert.assertThrows;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+
+import com.google.common.primitives.Bytes;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import java.util.Arrays;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class EncryptedChunkTest {
+    private static final byte[] CHUNK_HASH_1_BYTES =
+            Arrays.copyOf(new byte[] {1}, ChunkHash.HASH_LENGTH_BYTES);
+    private static final byte[] NONCE_1 =
+            Arrays.copyOf(new byte[] {2}, EncryptedChunk.NONCE_LENGTH_BYTES);
+    private static final byte[] ENCRYPTED_BYTES_1 =
+            Arrays.copyOf(new byte[] {3}, EncryptedChunk.KEY_LENGTH_BYTES);
+
+    private static final byte[] CHUNK_HASH_2_BYTES =
+            Arrays.copyOf(new byte[] {4}, ChunkHash.HASH_LENGTH_BYTES);
+    private static final byte[] NONCE_2 =
+            Arrays.copyOf(new byte[] {5}, EncryptedChunk.NONCE_LENGTH_BYTES);
+    private static final byte[] ENCRYPTED_BYTES_2 =
+            Arrays.copyOf(new byte[] {6}, EncryptedChunk.KEY_LENGTH_BYTES);
+
+    @Test
+    public void testCreate_withIncorrectLength_throwsException() {
+        ChunkHash chunkHash = new ChunkHash(CHUNK_HASH_1_BYTES);
+        byte[] shortNonce = Arrays.copyOf(new byte[] {2}, EncryptedChunk.NONCE_LENGTH_BYTES - 1);
+
+        assertThrows(
+                IllegalArgumentException.class,
+                () -> EncryptedChunk.create(chunkHash, shortNonce, ENCRYPTED_BYTES_1));
+    }
+
+    @Test
+    public void testEncryptedBytes_forNewlyCreatedObject_returnsCorrectValue() {
+        ChunkHash chunkHash = new ChunkHash(CHUNK_HASH_1_BYTES);
+        EncryptedChunk encryptedChunk =
+                EncryptedChunk.create(chunkHash, NONCE_1, ENCRYPTED_BYTES_1);
+
+        byte[] returnedBytes = encryptedChunk.encryptedBytes();
+
+        assertThat(returnedBytes)
+                .asList()
+                .containsExactlyElementsIn(Bytes.asList(ENCRYPTED_BYTES_1))
+                .inOrder();
+    }
+
+    @Test
+    public void testKey_forNewlyCreatedObject_returnsCorrectValue() {
+        ChunkHash chunkHash = new ChunkHash(CHUNK_HASH_1_BYTES);
+        EncryptedChunk encryptedChunk =
+                EncryptedChunk.create(chunkHash, NONCE_1, ENCRYPTED_BYTES_1);
+
+        ChunkHash returnedKey = encryptedChunk.key();
+
+        assertThat(returnedKey).isEqualTo(chunkHash);
+    }
+
+    @Test
+    public void testNonce_forNewlycreatedObject_returnCorrectValue() {
+        ChunkHash chunkHash = new ChunkHash(CHUNK_HASH_1_BYTES);
+        EncryptedChunk encryptedChunk =
+                EncryptedChunk.create(chunkHash, NONCE_1, ENCRYPTED_BYTES_1);
+
+        byte[] returnedNonce = encryptedChunk.nonce();
+
+        assertThat(returnedNonce).asList().containsExactlyElementsIn(Bytes.asList(NONCE_1));
+    }
+
+    @Test
+    public void testEquals() {
+        ChunkHash chunkHash1 = new ChunkHash(CHUNK_HASH_1_BYTES);
+        ChunkHash equalChunkHash1 = new ChunkHash(CHUNK_HASH_1_BYTES);
+        ChunkHash chunkHash2 = new ChunkHash(CHUNK_HASH_2_BYTES);
+        EncryptedChunk encryptedChunk1 =
+                EncryptedChunk.create(chunkHash1, NONCE_1, ENCRYPTED_BYTES_1);
+        EncryptedChunk equalEncryptedChunk1 =
+                EncryptedChunk.create(equalChunkHash1, NONCE_1, ENCRYPTED_BYTES_1);
+        EncryptedChunk encryptedChunk2 =
+                EncryptedChunk.create(chunkHash2, NONCE_2, ENCRYPTED_BYTES_2);
+
+        assertThat(encryptedChunk1).isEqualTo(equalEncryptedChunk1);
+        assertThat(encryptedChunk1).isNotEqualTo(encryptedChunk2);
+    }
+
+    @Test
+    public void testHashCode() {
+        ChunkHash chunkHash1 = new ChunkHash(CHUNK_HASH_1_BYTES);
+        ChunkHash equalChunkHash1 = new ChunkHash(CHUNK_HASH_1_BYTES);
+        ChunkHash chunkHash2 = new ChunkHash(CHUNK_HASH_2_BYTES);
+        EncryptedChunk encryptedChunk1 =
+                EncryptedChunk.create(chunkHash1, NONCE_1, ENCRYPTED_BYTES_1);
+        EncryptedChunk equalEncryptedChunk1 =
+                EncryptedChunk.create(equalChunkHash1, NONCE_1, ENCRYPTED_BYTES_1);
+        EncryptedChunk encryptedChunk2 =
+                EncryptedChunk.create(chunkHash2, NONCE_2, ENCRYPTED_BYTES_2);
+
+        int hash1 = encryptedChunk1.hashCode();
+        int equalHash1 = equalEncryptedChunk1.hashCode();
+        int hash2 = encryptedChunk2.hashCode();
+
+        assertThat(hash1).isEqualTo(equalHash1);
+        assertThat(hash1).isNotEqualTo(hash2);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/InlineLengthsEncryptedChunkEncoderTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/InlineLengthsEncryptedChunkEncoderTest.java
new file mode 100644
index 0000000..634acdc
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/InlineLengthsEncryptedChunkEncoderTest.java
@@ -0,0 +1,85 @@
+/*
+ * 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;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.mockito.Mockito.inOrder;
+import static org.mockito.Mockito.mock;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+import com.android.server.backup.encryption.chunk.ChunksMetadataProto;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.InOrder;
+import org.mockito.Mock;
+import org.robolectric.RobolectricTestRunner;
+
+import java.util.Arrays;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class InlineLengthsEncryptedChunkEncoderTest {
+
+    private static final byte[] TEST_NONCE =
+            Arrays.copyOf(new byte[] {1}, EncryptedChunk.NONCE_LENGTH_BYTES);
+    private static final byte[] TEST_KEY_DATA =
+            Arrays.copyOf(new byte[] {2}, EncryptedChunk.KEY_LENGTH_BYTES);
+    private static final byte[] TEST_DATA = {5, 4, 5, 7, 10, 12, 1, 2, 9};
+
+    @Mock private BackupWriter mMockBackupWriter;
+    private ChunkHash mTestKey;
+    private EncryptedChunk mTestChunk;
+    private EncryptedChunkEncoder mEncoder;
+
+    @Before
+    public void setUp() throws Exception {
+        mMockBackupWriter = mock(BackupWriter.class);
+        mTestKey = new ChunkHash(TEST_KEY_DATA);
+        mTestChunk = EncryptedChunk.create(mTestKey, TEST_NONCE, TEST_DATA);
+        mEncoder = new InlineLengthsEncryptedChunkEncoder();
+    }
+
+    @Test
+    public void writeChunkToWriter_writesLengthThenNonceThenData() throws Exception {
+        mEncoder.writeChunkToWriter(mMockBackupWriter, mTestChunk);
+
+        InOrder inOrder = inOrder(mMockBackupWriter);
+        inOrder.verify(mMockBackupWriter)
+                .writeBytes(
+                        InlineLengthsEncryptedChunkEncoder.toByteArray(
+                                TEST_NONCE.length + TEST_DATA.length));
+        inOrder.verify(mMockBackupWriter).writeBytes(TEST_NONCE);
+        inOrder.verify(mMockBackupWriter).writeBytes(TEST_DATA);
+    }
+
+    @Test
+    public void getEncodedLengthOfChunk_returnsSumOfNonceAndDataLengths() {
+        int encodedLength = mEncoder.getEncodedLengthOfChunk(mTestChunk);
+
+        assertThat(encodedLength).isEqualTo(Integer.BYTES + TEST_NONCE.length + TEST_DATA.length);
+    }
+
+    @Test
+    public void getChunkOrderingType_returnsExplicitStartsType() {
+        assertThat(mEncoder.getChunkOrderingType()).isEqualTo(ChunksMetadataProto.INLINE_LENGTHS);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/LengthlessEncryptedChunkEncoderTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/LengthlessEncryptedChunkEncoderTest.java
new file mode 100644
index 0000000..d231603
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/LengthlessEncryptedChunkEncoderTest.java
@@ -0,0 +1,80 @@
+/*
+ * 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;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.mockito.Mockito.inOrder;
+import static org.mockito.Mockito.mock;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+import com.android.server.backup.encryption.chunk.ChunksMetadataProto;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.InOrder;
+import org.mockito.Mock;
+import org.robolectric.RobolectricTestRunner;
+
+import java.util.Arrays;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class LengthlessEncryptedChunkEncoderTest {
+    private static final byte[] TEST_NONCE =
+            Arrays.copyOf(new byte[] {1}, EncryptedChunk.NONCE_LENGTH_BYTES);
+    private static final byte[] TEST_KEY_DATA =
+            Arrays.copyOf(new byte[] {2}, EncryptedChunk.KEY_LENGTH_BYTES);
+    private static final byte[] TEST_DATA = {5, 4, 5, 7, 10, 12, 1, 2, 9};
+
+    @Mock private BackupWriter mMockBackupWriter;
+    private ChunkHash mTestKey;
+    private EncryptedChunk mTestChunk;
+    private EncryptedChunkEncoder mEncoder;
+
+    @Before
+    public void setUp() throws Exception {
+        mMockBackupWriter = mock(BackupWriter.class);
+        mTestKey = new ChunkHash(TEST_KEY_DATA);
+        mTestChunk = EncryptedChunk.create(mTestKey, TEST_NONCE, TEST_DATA);
+        mEncoder = new LengthlessEncryptedChunkEncoder();
+    }
+
+    @Test
+    public void writeChunkToWriter_writesNonceThenData() throws Exception {
+        mEncoder.writeChunkToWriter(mMockBackupWriter, mTestChunk);
+
+        InOrder inOrder = inOrder(mMockBackupWriter);
+        inOrder.verify(mMockBackupWriter).writeBytes(TEST_NONCE);
+        inOrder.verify(mMockBackupWriter).writeBytes(TEST_DATA);
+    }
+
+    @Test
+    public void getEncodedLengthOfChunk_returnsSumOfNonceAndDataLengths() {
+        int encodedLength = mEncoder.getEncodedLengthOfChunk(mTestChunk);
+
+        assertThat(encodedLength).isEqualTo(TEST_NONCE.length + TEST_DATA.length);
+    }
+
+    @Test
+    public void getChunkOrderingType_returnsExplicitStartsType() {
+        assertThat(mEncoder.getChunkOrderingType()).isEqualTo(ChunksMetadataProto.EXPLICIT_STARTS);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/RawBackupWriterTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/RawBackupWriterTest.java
new file mode 100644
index 0000000..966d3e2
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/RawBackupWriterTest.java
@@ -0,0 +1,84 @@
+/*
+ * 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;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.verify;
+import static org.testng.Assert.assertThrows;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.google.common.primitives.Bytes;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import java.io.ByteArrayOutputStream;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class RawBackupWriterTest {
+    private static final byte[] TEST_BYTES = {1, 2, 3, 4, 5, 6};
+
+    private BackupWriter mWriter;
+    private ByteArrayOutputStream mOutput;
+
+    @Before
+    public void setUp() {
+        mOutput = new ByteArrayOutputStream();
+        mWriter = new RawBackupWriter(mOutput);
+    }
+
+    @Test
+    public void writeBytes_writesToOutputStream() throws Exception {
+        mWriter.writeBytes(TEST_BYTES);
+
+        assertThat(mOutput.toByteArray())
+                .asList()
+                .containsExactlyElementsIn(Bytes.asList(TEST_BYTES))
+                .inOrder();
+    }
+
+    @Test
+    public void writeChunk_throwsUnsupportedOperationException() throws Exception {
+        assertThrows(UnsupportedOperationException.class, () -> mWriter.writeChunk(0, 0));
+    }
+
+    @Test
+    public void getBytesWritten_returnsTotalSum() throws Exception {
+        mWriter.writeBytes(TEST_BYTES);
+        mWriter.writeBytes(TEST_BYTES);
+
+        long bytesWritten = mWriter.getBytesWritten();
+
+        assertThat(bytesWritten).isEqualTo(2 * TEST_BYTES.length);
+    }
+
+    @Test
+    public void flush_flushesOutputStream() throws Exception {
+        mOutput = mock(ByteArrayOutputStream.class);
+        mWriter = new RawBackupWriter(mOutput);
+
+        mWriter.flush();
+
+        verify(mOutput).flush();
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/SingleStreamDiffScriptWriterTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/SingleStreamDiffScriptWriterTest.java
new file mode 100644
index 0000000..73baf80
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/SingleStreamDiffScriptWriterTest.java
@@ -0,0 +1,128 @@
+/*
+ * 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;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.verify;
+import static org.testng.Assert.assertThrows;
+
+import android.platform.test.annotations.Presubmit;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.util.Locale;
+
+/** Tests for {@link SingleStreamDiffScriptWriter}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class SingleStreamDiffScriptWriterTest {
+    private static final int MAX_CHUNK_SIZE_IN_BYTES = 256;
+    /** By default this Locale does not use Arabic numbers for %d formatting. */
+    private static final Locale HINDI = new Locale("hi", "IN");
+
+    private Locale mDefaultLocale;
+    private ByteArrayOutputStream mOutputStream;
+    private SingleStreamDiffScriptWriter mDiffScriptWriter;
+
+    @Before
+    public void setUp() {
+        mDefaultLocale = Locale.getDefault();
+        mOutputStream = new ByteArrayOutputStream();
+        mDiffScriptWriter =
+                new SingleStreamDiffScriptWriter(mOutputStream, MAX_CHUNK_SIZE_IN_BYTES);
+    }
+
+    @After
+    public void tearDown() {
+        Locale.setDefault(mDefaultLocale);
+    }
+
+    @Test
+    public void writeChunk_withNegativeStart_throwsException() {
+        assertThrows(
+                IllegalArgumentException.class,
+                () -> mDiffScriptWriter.writeChunk(-1, 50));
+    }
+
+    @Test
+    public void writeChunk_withZeroLength_throwsException() {
+        assertThrows(
+                IllegalArgumentException.class,
+                () -> mDiffScriptWriter.writeChunk(0, 0));
+    }
+
+    @Test
+    public void writeChunk_withExistingBytesInBuffer_writesBufferFirst()
+            throws IOException {
+        String testString = "abcd";
+        writeStringAsBytesToWriter(testString, mDiffScriptWriter);
+
+        mDiffScriptWriter.writeChunk(0, 20);
+        mDiffScriptWriter.flush();
+
+        // Expected format: length of abcd, newline, abcd, newline, chunk start - chunk end
+        assertThat(mOutputStream.toString("UTF-8")).isEqualTo(
+                String.format("%d\n%s\n%d-%d\n", testString.length(), testString, 0, 19));
+    }
+
+    @Test
+    public void writeChunk_overlappingPreviousChunk_combinesChunks() throws IOException {
+        mDiffScriptWriter.writeChunk(3, 4);
+
+        mDiffScriptWriter.writeChunk(7, 5);
+        mDiffScriptWriter.flush();
+
+        assertThat(mOutputStream.toString("UTF-8")).isEqualTo(String.format("3-11\n"));
+    }
+
+    @Test
+    public void writeChunk_formatsByteIndexesUsingArabicNumbers() throws Exception {
+        Locale.setDefault(HINDI);
+
+        mDiffScriptWriter.writeChunk(0, 12345);
+        mDiffScriptWriter.flush();
+
+        assertThat(mOutputStream.toString("UTF-8")).isEqualTo("0-12344\n");
+    }
+
+    @Test
+    public void flush_flushesOutputStream() throws IOException {
+        ByteArrayOutputStream mockOutputStream = mock(ByteArrayOutputStream.class);
+        SingleStreamDiffScriptWriter diffScriptWriter =
+                new SingleStreamDiffScriptWriter(mockOutputStream, MAX_CHUNK_SIZE_IN_BYTES);
+
+        diffScriptWriter.flush();
+
+        verify(mockOutputStream).flush();
+    }
+
+    private void writeStringAsBytesToWriter(String string, SingleStreamDiffScriptWriter writer)
+            throws IOException {
+        byte[] bytes = string.getBytes("UTF-8");
+        for (int i = 0; i < bytes.length; i++) {
+            writer.writeByte(bytes[i]);
+        }
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunkerTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunkerTest.java
new file mode 100644
index 0000000..77b7347
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/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/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/FingerprintMixerTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/FingerprintMixerTest.java
new file mode 100644
index 0000000..936b5dc
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/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/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/HkdfTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/HkdfTest.java
new file mode 100644
index 0000000..5494374
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/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/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpointTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpointTest.java
new file mode 100644
index 0000000..277dc37
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/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/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64Test.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64Test.java
new file mode 100644
index 0000000..729580c
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/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);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyManagerTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyManagerTest.java
new file mode 100644
index 0000000..5342efa
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyManagerTest.java
@@ -0,0 +1,148 @@
+/*
+ * 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.keys;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.testng.Assert.assertThrows;
+
+import android.content.Context;
+import android.platform.test.annotations.Presubmit;
+import android.security.keystore.recovery.InternalRecoveryServiceException;
+import android.security.keystore.recovery.RecoveryController;
+
+import com.android.server.testing.shadows.ShadowInternalRecoveryServiceException;
+import com.android.server.testing.shadows.ShadowRecoveryController;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+import org.robolectric.RuntimeEnvironment;
+import org.robolectric.annotation.Config;
+
+import java.security.SecureRandom;
+import java.util.Optional;
+
+/** Tests for {@link RecoverableKeyStoreSecondaryKeyManager}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+@Config(shadows = {ShadowRecoveryController.class, ShadowInternalRecoveryServiceException.class})
+public class RecoverableKeyStoreSecondaryKeyManagerTest {
+    private static final String BACKUP_KEY_ALIAS_PREFIX =
+            "com.android.server.backup/recoverablekeystore/";
+    private static final int BITS_PER_BYTE = 8;
+    private static final int BACKUP_KEY_SUFFIX_LENGTH_BYTES = 128 / BITS_PER_BYTE;
+    private static final int HEX_PER_BYTE = 2;
+    private static final int BACKUP_KEY_ALIAS_LENGTH =
+            BACKUP_KEY_ALIAS_PREFIX.length() + BACKUP_KEY_SUFFIX_LENGTH_BYTES * HEX_PER_BYTE;
+    private static final String NONEXISTENT_KEY_ALIAS = "NONEXISTENT_KEY_ALIAS";
+
+    private RecoverableKeyStoreSecondaryKeyManager mRecoverableKeyStoreSecondaryKeyManager;
+    private Context mContext;
+
+    /** Create a new {@link RecoverableKeyStoreSecondaryKeyManager} to use in tests. */
+    @Before
+    public void setUp() throws Exception {
+        mContext = RuntimeEnvironment.application;
+
+        mRecoverableKeyStoreSecondaryKeyManager =
+                new RecoverableKeyStoreSecondaryKeyManager(
+                        RecoveryController.getInstance(mContext), new SecureRandom());
+    }
+
+    /** Reset the {@link ShadowRecoveryController}. */
+    @After
+    public void tearDown() throws Exception {
+        ShadowRecoveryController.reset();
+    }
+
+    /** The generated key should always have the prefix {@code BACKUP_KEY_ALIAS_PREFIX}. */
+    @Test
+    public void generate_generatesKeyWithExpectedPrefix() throws Exception {
+        RecoverableKeyStoreSecondaryKey key = mRecoverableKeyStoreSecondaryKeyManager.generate();
+
+        assertThat(key.getAlias()).startsWith(BACKUP_KEY_ALIAS_PREFIX);
+    }
+
+    /** The generated key should always have length {@code BACKUP_KEY_ALIAS_LENGTH}. */
+    @Test
+    public void generate_generatesKeyWithExpectedLength() throws Exception {
+        RecoverableKeyStoreSecondaryKey key = mRecoverableKeyStoreSecondaryKeyManager.generate();
+
+        assertThat(key.getAlias()).hasLength(BACKUP_KEY_ALIAS_LENGTH);
+    }
+
+    /** Ensure that hidden API exceptions are rethrown when generating keys. */
+    @Test
+    public void generate_encounteringHiddenApiException_rethrowsException() {
+        ShadowRecoveryController.setThrowsInternalError(true);
+
+        assertThrows(
+                InternalRecoveryServiceException.class,
+                mRecoverableKeyStoreSecondaryKeyManager::generate);
+    }
+
+    /** Ensure that retrieved keys correspond to those generated earlier. */
+    @Test
+    public void get_getsKeyGeneratedByController() throws Exception {
+        RecoverableKeyStoreSecondaryKey key = mRecoverableKeyStoreSecondaryKeyManager.generate();
+
+        Optional<RecoverableKeyStoreSecondaryKey> retrievedKey =
+                mRecoverableKeyStoreSecondaryKeyManager.get(key.getAlias());
+
+        assertThat(retrievedKey.isPresent()).isTrue();
+        assertThat(retrievedKey.get().getAlias()).isEqualTo(key.getAlias());
+        assertThat(retrievedKey.get().getSecretKey()).isEqualTo(key.getSecretKey());
+    }
+
+    /**
+     * Ensure that a call to {@link RecoverableKeyStoreSecondaryKeyManager#get(java.lang.String)}
+     * for nonexistent aliases returns an emtpy {@link Optional}.
+     */
+    @Test
+    public void get_forNonExistentKey_returnsEmptyOptional() throws Exception {
+        Optional<RecoverableKeyStoreSecondaryKey> retrievedKey =
+                mRecoverableKeyStoreSecondaryKeyManager.get(NONEXISTENT_KEY_ALIAS);
+
+        assertThat(retrievedKey.isPresent()).isFalse();
+    }
+
+    /**
+     * Ensure that exceptions occurring during {@link
+     * RecoverableKeyStoreSecondaryKeyManager#get(java.lang.String)} are not rethrown.
+     */
+    @Test
+    public void get_encounteringInternalException_doesNotPropagateException() throws Exception {
+        ShadowRecoveryController.setThrowsInternalError(true);
+
+        // Should not throw exception
+        mRecoverableKeyStoreSecondaryKeyManager.get(NONEXISTENT_KEY_ALIAS);
+    }
+
+    /** Ensure that keys are correctly removed from the store. */
+    @Test
+    public void remove_removesKeyFromRecoverableStore() throws Exception {
+        RecoverableKeyStoreSecondaryKey key = mRecoverableKeyStoreSecondaryKeyManager.generate();
+
+        mRecoverableKeyStoreSecondaryKeyManager.remove(key.getAlias());
+
+        assertThat(RecoveryController.getInstance(mContext).getAliases())
+                .doesNotContain(key.getAlias());
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyTest.java
new file mode 100644
index 0000000..89977f8
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyTest.java
@@ -0,0 +1,163 @@
+/*
+ * 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.keys;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.testng.Assert.assertThrows;
+
+import android.content.Context;
+import android.platform.test.annotations.Presubmit;
+import android.security.keystore.recovery.RecoveryController;
+
+import com.android.server.backup.encryption.keys.RecoverableKeyStoreSecondaryKey.Status;
+import com.android.server.backup.testing.CryptoTestUtils;
+import com.android.server.testing.shadows.ShadowInternalRecoveryServiceException;
+import com.android.server.testing.shadows.ShadowRecoveryController;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+import org.robolectric.RuntimeEnvironment;
+import org.robolectric.annotation.Config;
+
+import javax.crypto.SecretKey;
+
+/** Tests for {@link RecoverableKeyStoreSecondaryKey}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+@Config(shadows = {ShadowRecoveryController.class, ShadowInternalRecoveryServiceException.class})
+public class RecoverableKeyStoreSecondaryKeyTest {
+    private static final String TEST_ALIAS = "test";
+    private static final int NONEXISTENT_STATUS_CODE = 42;
+
+    private RecoverableKeyStoreSecondaryKey mSecondaryKey;
+    private SecretKey mGeneratedSecretKey;
+    private Context mContext;
+
+    /** Instantiate a {@link RecoverableKeyStoreSecondaryKey} to use in tests. */
+    @Before
+    public void setUp() throws Exception {
+        mContext = RuntimeEnvironment.application;
+        mGeneratedSecretKey = CryptoTestUtils.generateAesKey();
+        mSecondaryKey = new RecoverableKeyStoreSecondaryKey(TEST_ALIAS, mGeneratedSecretKey);
+    }
+
+    /** Reset the {@link ShadowRecoveryController}. */
+    @After
+    public void tearDown() throws Exception {
+        ShadowRecoveryController.reset();
+    }
+
+    /**
+     * Checks that {@link RecoverableKeyStoreSecondaryKey#getAlias()} returns the value supplied in
+     * the constructor.
+     */
+    @Test
+    public void getAlias() {
+        String alias = mSecondaryKey.getAlias();
+
+        assertThat(alias).isEqualTo(TEST_ALIAS);
+    }
+
+    /**
+     * Checks that {@link RecoverableKeyStoreSecondaryKey#getSecretKey()} returns the value supplied
+     * in the constructor.
+     */
+    @Test
+    public void getSecretKey() {
+        SecretKey secretKey = mSecondaryKey.getSecretKey();
+
+        assertThat(secretKey).isEqualTo(mGeneratedSecretKey);
+    }
+
+    /**
+     * Checks that passing a secret key that is null to the constructor throws an exception.
+     */
+    @Test
+    public void constructor_withNullSecretKey_throwsNullPointerException() {
+        assertThrows(
+                NullPointerException.class,
+                () -> new RecoverableKeyStoreSecondaryKey(TEST_ALIAS, null));
+    }
+
+    /**
+     * Checks that passing an alias that is null to the constructor throws an exception.
+     */
+    @Test
+    public void constructor_withNullAlias_throwsNullPointerException() {
+        assertThrows(
+                NullPointerException.class,
+                () -> new RecoverableKeyStoreSecondaryKey(null, mGeneratedSecretKey));
+    }
+
+    /** Checks that the synced status is returned correctly. */
+    @Test
+    public void getStatus_whenSynced_returnsSynced() throws Exception {
+        setStatus(RecoveryController.RECOVERY_STATUS_SYNCED);
+
+        int status = mSecondaryKey.getStatus(mContext);
+
+        assertThat(status).isEqualTo(Status.SYNCED);
+    }
+
+    /** Checks that the in progress sync status is returned correctly. */
+    @Test
+    public void getStatus_whenNotSynced_returnsNotSynced() throws Exception {
+        setStatus(RecoveryController.RECOVERY_STATUS_SYNC_IN_PROGRESS);
+
+        int status = mSecondaryKey.getStatus(mContext);
+
+        assertThat(status).isEqualTo(Status.NOT_SYNCED);
+    }
+
+    /** Checks that the failure status is returned correctly. */
+    @Test
+    public void getStatus_onPermanentFailure_returnsDestroyed() throws Exception {
+        setStatus(RecoveryController.RECOVERY_STATUS_PERMANENT_FAILURE);
+
+        int status = mSecondaryKey.getStatus(mContext);
+
+        assertThat(status).isEqualTo(Status.DESTROYED);
+    }
+
+    /** Checks that an unknown status results in {@code NOT_SYNCED} being returned. */
+    @Test
+    public void getStatus_forUnknownStatusCode_returnsNotSynced() throws Exception {
+        setStatus(NONEXISTENT_STATUS_CODE);
+
+        int status = mSecondaryKey.getStatus(mContext);
+
+        assertThat(status).isEqualTo(Status.NOT_SYNCED);
+    }
+
+    /** Checks that an internal error results in {@code NOT_SYNCED} being returned. */
+    @Test
+    public void getStatus_onInternalError_returnsNotSynced() throws Exception {
+        ShadowRecoveryController.setThrowsInternalError(true);
+
+        int status = mSecondaryKey.getStatus(mContext);
+
+        assertThat(status).isEqualTo(Status.NOT_SYNCED);
+    }
+
+    private void setStatus(int status) throws Exception {
+        ShadowRecoveryController.setRecoveryStatus(TEST_ALIAS, status);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/TertiaryKeyGeneratorTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/TertiaryKeyGeneratorTest.java
new file mode 100644
index 0000000..48216f8
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/TertiaryKeyGeneratorTest.java
@@ -0,0 +1,73 @@
+/*
+ * 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.keys;
+
+import static com.google.common.truth.Truth.assertThat;
+
+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.SecureRandom;
+
+import javax.crypto.SecretKey;
+
+/** Tests for {@link TertiaryKeyGenerator}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class TertiaryKeyGeneratorTest {
+    private static final String KEY_ALGORITHM = "AES";
+    private static final int KEY_SIZE_BITS = 256;
+
+    private TertiaryKeyGenerator mTertiaryKeyGenerator;
+
+    /** Instantiate a new {@link TertiaryKeyGenerator} for use in tests. */
+    @Before
+    public void setUp() {
+        mTertiaryKeyGenerator = new TertiaryKeyGenerator(new SecureRandom());
+    }
+
+    /** Generated keys should be AES keys. */
+    @Test
+    public void generate_generatesAESKeys() {
+        SecretKey secretKey = mTertiaryKeyGenerator.generate();
+
+        assertThat(secretKey.getAlgorithm()).isEqualTo(KEY_ALGORITHM);
+    }
+
+    /** Generated keys should be 256 bits in size. */
+    @Test
+    public void generate_generates256BitKeys() {
+        SecretKey secretKey = mTertiaryKeyGenerator.generate();
+
+        assertThat(secretKey.getEncoded()).hasLength(KEY_SIZE_BITS / 8);
+    }
+
+    /**
+     * Subsequent calls to {@link TertiaryKeyGenerator#generate()} should generate different keys.
+     */
+    @Test
+    public void generate_generatesNewKeys() {
+        SecretKey key1 = mTertiaryKeyGenerator.generate();
+        SecretKey key2 = mTertiaryKeyGenerator.generate();
+
+        assertThat(key1).isNotEqualTo(key2);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTrackerTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTrackerTest.java
new file mode 100644
index 0000000..49bb410
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTrackerTest.java
@@ -0,0 +1,137 @@
+/*
+ * 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.keys;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+import org.robolectric.RuntimeEnvironment;
+
+/** Tests for {@link TertiaryKeyRotationTracker}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class TertiaryKeyRotationTrackerTest {
+    private static final String PACKAGE_1 = "com.package.one";
+    private static final int NUMBER_OF_BACKUPS_BEFORE_ROTATION = 31;
+
+    private TertiaryKeyRotationTracker mTertiaryKeyRotationTracker;
+
+    /** Instantiate a {@link TertiaryKeyRotationTracker} for use in tests. */
+    @Before
+    public void setUp() {
+        mTertiaryKeyRotationTracker = newInstance();
+    }
+
+    /** New packages should not be due for key rotation. */
+    @Test
+    public void isKeyRotationDue_forNewPackage_isFalse() {
+        // Simulate a new package by not calling simulateBackups(). As a result, PACKAGE_1 hasn't
+        // been seen by mTertiaryKeyRotationTracker before.
+        boolean keyRotationDue = mTertiaryKeyRotationTracker.isKeyRotationDue(PACKAGE_1);
+
+        assertThat(keyRotationDue).isFalse();
+    }
+
+    /**
+     * Key rotation should not be due after less than {@code NUMBER_OF_BACKUPS_BEFORE_ROTATION}
+     * backups.
+     */
+    @Test
+    public void isKeyRotationDue_afterLessThanRotationAmountBackups_isFalse() {
+        simulateBackups(PACKAGE_1, NUMBER_OF_BACKUPS_BEFORE_ROTATION - 1);
+
+        boolean keyRotationDue = mTertiaryKeyRotationTracker.isKeyRotationDue(PACKAGE_1);
+
+        assertThat(keyRotationDue).isFalse();
+    }
+
+    /** Key rotation should be due after {@code NUMBER_OF_BACKUPS_BEFORE_ROTATION} backups. */
+    @Test
+    public void isKeyRotationDue_afterRotationAmountBackups_isTrue() {
+        simulateBackups(PACKAGE_1, NUMBER_OF_BACKUPS_BEFORE_ROTATION);
+
+        boolean keyRotationDue = mTertiaryKeyRotationTracker.isKeyRotationDue(PACKAGE_1);
+
+        assertThat(keyRotationDue).isTrue();
+    }
+
+    /**
+     * A call to {@link TertiaryKeyRotationTracker#resetCountdown(String)} should make sure no key
+     * rotation is due.
+     */
+    @Test
+    public void resetCountdown_makesKeyRotationNotDue() {
+        simulateBackups(PACKAGE_1, NUMBER_OF_BACKUPS_BEFORE_ROTATION);
+
+        mTertiaryKeyRotationTracker.resetCountdown(PACKAGE_1);
+
+        assertThat(mTertiaryKeyRotationTracker.isKeyRotationDue(PACKAGE_1)).isFalse();
+    }
+
+    /**
+     * New instances of {@link TertiaryKeyRotationTracker} should read state about the number of
+     * backups from disk.
+     */
+    @Test
+    public void isKeyRotationDue_forNewInstance_readsStateFromDisk() {
+        simulateBackups(PACKAGE_1, NUMBER_OF_BACKUPS_BEFORE_ROTATION);
+
+        boolean keyRotationDueForNewInstance = newInstance().isKeyRotationDue(PACKAGE_1);
+
+        assertThat(keyRotationDueForNewInstance).isTrue();
+    }
+
+    /**
+     * A call to {@link TertiaryKeyRotationTracker#markAllForRotation()} should mark all previously
+     * seen packages for rotation.
+     */
+    @Test
+    public void markAllForRotation_marksSeenPackagesForKeyRotation() {
+        simulateBackups(PACKAGE_1, /*numberOfBackups=*/ 1);
+
+        mTertiaryKeyRotationTracker.markAllForRotation();
+
+        assertThat(mTertiaryKeyRotationTracker.isKeyRotationDue(PACKAGE_1)).isTrue();
+    }
+
+    /**
+     * A call to {@link TertiaryKeyRotationTracker#markAllForRotation()} should not mark any new
+     * packages for rotation.
+     */
+    @Test
+    public void markAllForRotation_doesNotMarkUnseenPackages() {
+        mTertiaryKeyRotationTracker.markAllForRotation();
+
+        assertThat(mTertiaryKeyRotationTracker.isKeyRotationDue(PACKAGE_1)).isFalse();
+    }
+
+    private void simulateBackups(String packageName, int numberOfBackups) {
+        while (numberOfBackups > 0) {
+            mTertiaryKeyRotationTracker.recordBackup(packageName);
+            numberOfBackups--;
+        }
+    }
+
+    private static TertiaryKeyRotationTracker newInstance() {
+        return TertiaryKeyRotationTracker.getInstance(RuntimeEnvironment.application);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/storage/BackupEncryptionDbTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/storage/BackupEncryptionDbTest.java
new file mode 100644
index 0000000..87f21bf
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/storage/BackupEncryptionDbTest.java
@@ -0,0 +1,55 @@
+/*
+ * 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.storage;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+import org.robolectric.RuntimeEnvironment;
+
+/** Tests for {@link BackupEncryptionDb}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class BackupEncryptionDbTest {
+    private BackupEncryptionDb mBackupEncryptionDb;
+
+    /** Creates an empty {@link BackupEncryptionDb} */
+    @Before
+    public void setUp() {
+        mBackupEncryptionDb = BackupEncryptionDb.newInstance(RuntimeEnvironment.application);
+    }
+
+    /**
+     * Tests that the tertiary keys table gets cleared when calling {@link
+     * BackupEncryptionDb#clear()}.
+     */
+    @Test
+    public void clear_withNonEmptyTertiaryKeysTable_clearsTertiaryKeysTable() throws Exception {
+        String secondaryKeyAlias = "secondaryKeyAlias";
+        TertiaryKeysTable tertiaryKeysTable = mBackupEncryptionDb.getTertiaryKeysTable();
+        tertiaryKeysTable.addKey(new TertiaryKey(secondaryKeyAlias, "packageName", new byte[0]));
+
+        mBackupEncryptionDb.clear();
+
+        assertThat(tertiaryKeysTable.getAllKeys(secondaryKeyAlias)).isEmpty();
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/storage/TertiaryKeysTableTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/storage/TertiaryKeysTableTest.java
new file mode 100644
index 0000000..319ec89
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/storage/TertiaryKeysTableTest.java
@@ -0,0 +1,179 @@
+/*
+ * 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.storage;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.android.server.backup.testing.CryptoTestUtils;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+import org.robolectric.RuntimeEnvironment;
+
+import java.util.Map;
+import java.util.Optional;
+
+/** Tests for {@link TertiaryKeysTable}. */
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class TertiaryKeysTableTest {
+    private static final int KEY_SIZE_BYTES = 32;
+    private static final String SECONDARY_ALIAS = "phoebe";
+    private static final String PACKAGE_NAME = "generic.package.name";
+
+    private TertiaryKeysTable mTertiaryKeysTable;
+
+    /** Creates an empty {@link BackupEncryptionDb}. */
+    @Before
+    public void setUp() {
+        mTertiaryKeysTable =
+                BackupEncryptionDb.newInstance(RuntimeEnvironment.application)
+                        .getTertiaryKeysTable();
+    }
+
+    /** Tests that new {@link TertiaryKey}s get successfully added to the database. */
+    @Test
+    public void addKey_onEmptyDatabase_putsKeyInDb() throws Exception {
+        byte[] key = generateRandomKey();
+        TertiaryKey keyToInsert = new TertiaryKey(SECONDARY_ALIAS, PACKAGE_NAME, key);
+
+        long result = mTertiaryKeysTable.addKey(keyToInsert);
+
+        assertThat(result).isNotEqualTo(-1);
+        Optional<TertiaryKey> maybeKeyInDb =
+                mTertiaryKeysTable.getKey(SECONDARY_ALIAS, PACKAGE_NAME);
+        assertThat(maybeKeyInDb.isPresent()).isTrue();
+        TertiaryKey keyInDb = maybeKeyInDb.get();
+        assertTertiaryKeysEqual(keyInDb, keyToInsert);
+    }
+
+    /** Tests that keys replace older keys with the same secondary alias and package name. */
+    @Test
+    public void addKey_havingSameSecondaryAliasAndPackageName_replacesOldKey() throws Exception {
+        mTertiaryKeysTable.addKey(
+                new TertiaryKey(SECONDARY_ALIAS, PACKAGE_NAME, generateRandomKey()));
+        byte[] newKey = generateRandomKey();
+
+        long result =
+                mTertiaryKeysTable.addKey(new TertiaryKey(SECONDARY_ALIAS, PACKAGE_NAME, newKey));
+
+        assertThat(result).isNotEqualTo(-1);
+        TertiaryKey keyInDb = mTertiaryKeysTable.getKey(SECONDARY_ALIAS, PACKAGE_NAME).get();
+        assertThat(keyInDb.getWrappedKeyBytes()).isEqualTo(newKey);
+    }
+
+    /**
+     * Tests that keys do not replace older keys with the same package name but a different alias.
+     */
+    @Test
+    public void addKey_havingSamePackageNameButDifferentAlias_doesNotReplaceOldKey()
+            throws Exception {
+        String alias2 = "karl";
+        TertiaryKey key1 = generateTertiaryKey(SECONDARY_ALIAS, PACKAGE_NAME);
+        TertiaryKey key2 = generateTertiaryKey(alias2, PACKAGE_NAME);
+
+        long primaryKey1 = mTertiaryKeysTable.addKey(key1);
+        long primaryKey2 = mTertiaryKeysTable.addKey(key2);
+
+        assertThat(primaryKey1).isNotEqualTo(primaryKey2);
+        assertThat(mTertiaryKeysTable.getKey(SECONDARY_ALIAS, PACKAGE_NAME).isPresent()).isTrue();
+        assertTertiaryKeysEqual(
+                mTertiaryKeysTable.getKey(SECONDARY_ALIAS, PACKAGE_NAME).get(), key1);
+        assertThat(mTertiaryKeysTable.getKey(alias2, PACKAGE_NAME).isPresent()).isTrue();
+        assertTertiaryKeysEqual(mTertiaryKeysTable.getKey(alias2, PACKAGE_NAME).get(), key2);
+    }
+
+    /**
+     * Tests that {@link TertiaryKeysTable#getKey(String, String)} returns an empty {@link Optional}
+     * for a missing key.
+     */
+    @Test
+    public void getKey_forMissingKey_returnsEmptyOptional() throws Exception {
+        Optional<TertiaryKey> key = mTertiaryKeysTable.getKey(SECONDARY_ALIAS, PACKAGE_NAME);
+
+        assertThat(key.isPresent()).isFalse();
+    }
+
+    /**
+     * Tests that {@link TertiaryKeysTable#getAllKeys(String)} returns an empty map when no keys
+     * with the secondary alias exist.
+     */
+    @Test
+    public void getAllKeys_withNoKeysForAlias_returnsEmptyMap() throws Exception {
+        assertThat(mTertiaryKeysTable.getAllKeys(SECONDARY_ALIAS)).isEmpty();
+    }
+
+    /**
+     * Tests that {@link TertiaryKeysTable#getAllKeys(String)} returns all keys corresponding to the
+     * provided secondary alias.
+     */
+    @Test
+    public void getAllKeys_withMatchingKeys_returnsAllKeysWrappedWithSecondary() throws Exception {
+        TertiaryKey key1 = generateTertiaryKey(SECONDARY_ALIAS, PACKAGE_NAME);
+        mTertiaryKeysTable.addKey(key1);
+        String package2 = "generic.package.two";
+        TertiaryKey key2 = generateTertiaryKey(SECONDARY_ALIAS, package2);
+        mTertiaryKeysTable.addKey(key2);
+        String package3 = "generic.package.three";
+        TertiaryKey key3 = generateTertiaryKey(SECONDARY_ALIAS, package3);
+        mTertiaryKeysTable.addKey(key3);
+
+        Map<String, TertiaryKey> keysByPackageName = mTertiaryKeysTable.getAllKeys(SECONDARY_ALIAS);
+
+        assertThat(keysByPackageName).hasSize(3);
+        assertThat(keysByPackageName).containsKey(PACKAGE_NAME);
+        assertTertiaryKeysEqual(keysByPackageName.get(PACKAGE_NAME), key1);
+        assertThat(keysByPackageName).containsKey(package2);
+        assertTertiaryKeysEqual(keysByPackageName.get(package2), key2);
+        assertThat(keysByPackageName).containsKey(package3);
+        assertTertiaryKeysEqual(keysByPackageName.get(package3), key3);
+    }
+
+    /**
+     * Tests that {@link TertiaryKeysTable#getAllKeys(String)} does not return any keys wrapped with
+     * another alias.
+     */
+    @Test
+    public void getAllKeys_withMatchingKeys_doesNotReturnKeysWrappedWithOtherAlias()
+            throws Exception {
+        mTertiaryKeysTable.addKey(generateTertiaryKey(SECONDARY_ALIAS, PACKAGE_NAME));
+        mTertiaryKeysTable.addKey(generateTertiaryKey("somekey", "generic.package.two"));
+
+        Map<String, TertiaryKey> keysByPackageName = mTertiaryKeysTable.getAllKeys(SECONDARY_ALIAS);
+
+        assertThat(keysByPackageName).hasSize(1);
+        assertThat(keysByPackageName).containsKey(PACKAGE_NAME);
+    }
+
+    private void assertTertiaryKeysEqual(TertiaryKey a, TertiaryKey b) {
+        assertThat(a.getSecondaryKeyAlias()).isEqualTo(b.getSecondaryKeyAlias());
+        assertThat(a.getPackageName()).isEqualTo(b.getPackageName());
+        assertThat(a.getWrappedKeyBytes()).isEqualTo(b.getWrappedKeyBytes());
+    }
+
+    private TertiaryKey generateTertiaryKey(String alias, String packageName) {
+        return new TertiaryKey(alias, packageName, generateRandomKey());
+    }
+
+    private byte[] generateRandomKey() {
+        return CryptoTestUtils.generateRandomBytes(KEY_SIZE_BYTES);
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/tasks/BackupStreamEncrypterTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/tasks/BackupStreamEncrypterTest.java
new file mode 100644
index 0000000..21c4e07
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/tasks/BackupStreamEncrypterTest.java
@@ -0,0 +1,262 @@
+/*
+ * Copyright (C) 2019 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.tasks;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.platform.test.annotations.Presubmit;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+import com.android.server.backup.encryption.chunking.EncryptedChunk;
+import com.android.server.backup.testing.CryptoTestUtils;
+import com.android.server.backup.testing.RandomInputStream;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.robolectric.RobolectricTestRunner;
+
+import java.io.ByteArrayInputStream;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+
+import javax.crypto.SecretKey;
+
+@RunWith(RobolectricTestRunner.class)
+@Presubmit
+public class BackupStreamEncrypterTest {
+    private static final int SALT_LENGTH = 32;
+    private static final int BITS_PER_BYTE = 8;
+    private static final int BYTES_PER_KILOBYTE = 1024;
+    private static final int BYTES_PER_MEGABYTE = 1024 * 1024;
+    private static final int MIN_CHUNK_SIZE = 2 * BYTES_PER_KILOBYTE;
+    private static final int AVERAGE_CHUNK_SIZE = 4 * BYTES_PER_KILOBYTE;
+    private static final int MAX_CHUNK_SIZE = 64 * BYTES_PER_KILOBYTE;
+    private static final int BACKUP_SIZE = 2 * BYTES_PER_MEGABYTE;
+    private static final int SMALL_BACKUP_SIZE = BYTES_PER_KILOBYTE;
+    // 16 bytes for the mac. iv is encoded in a separate field.
+    private static final int BYTES_OVERHEAD_PER_CHUNK = 16;
+    private static final int MESSAGE_DIGEST_SIZE_IN_BYTES = 256 / BITS_PER_BYTE;
+    private static final int RANDOM_SEED = 42;
+    private static final double TOLERANCE = 0.1;
+
+    private Random mRandom;
+    private SecretKey mSecretKey;
+    private byte[] mSalt;
+
+    @Before
+    public void setUp() throws Exception {
+        mSecretKey = CryptoTestUtils.generateAesKey();
+
+        mSalt = new byte[SALT_LENGTH];
+        // Make these tests deterministic
+        mRandom = new Random(RANDOM_SEED);
+        mRandom.nextBytes(mSalt);
+    }
+
+    @Test
+    public void testBackup_producesChunksOfTheGivenAverageSize() throws Exception {
+        BackupEncrypter.Result result = runBackup(BACKUP_SIZE);
+
+        long totalSize = 0;
+        for (EncryptedChunk chunk : result.getNewChunks()) {
+            totalSize += chunk.encryptedBytes().length;
+        }
+
+        double meanSize = totalSize / result.getNewChunks().size();
+        double expectedChunkSize = AVERAGE_CHUNK_SIZE + BYTES_OVERHEAD_PER_CHUNK;
+        assertThat(Math.abs(meanSize - expectedChunkSize) / expectedChunkSize)
+                .isLessThan(TOLERANCE);
+    }
+
+    @Test
+    public void testBackup_producesNoChunksSmallerThanMinSize() throws Exception {
+        BackupEncrypter.Result result = runBackup(BACKUP_SIZE);
+        List<EncryptedChunk> chunks = result.getNewChunks();
+
+        // Last chunk could be smaller, depending on the file size and how it is chunked
+        for (EncryptedChunk chunk : chunks.subList(0, chunks.size() - 2)) {
+            assertThat(chunk.encryptedBytes().length)
+                    .isAtLeast(MIN_CHUNK_SIZE + BYTES_OVERHEAD_PER_CHUNK);
+        }
+    }
+
+    @Test
+    public void testBackup_producesNoChunksLargerThanMaxSize() throws Exception {
+        BackupEncrypter.Result result = runBackup(BACKUP_SIZE);
+        List<EncryptedChunk> chunks = result.getNewChunks();
+
+        for (EncryptedChunk chunk : chunks) {
+            assertThat(chunk.encryptedBytes().length)
+                    .isAtMost(MAX_CHUNK_SIZE + BYTES_OVERHEAD_PER_CHUNK);
+        }
+    }
+
+    @Test
+    public void testBackup_producesAFileOfTheExpectedSize() throws Exception {
+        BackupEncrypter.Result result = runBackup(BACKUP_SIZE);
+        HashMap<ChunkHash, EncryptedChunk> chunksBySha256 =
+                chunksIndexedByKey(result.getNewChunks());
+
+        int expectedSize = BACKUP_SIZE + result.getAllChunks().size() * BYTES_OVERHEAD_PER_CHUNK;
+        int size = 0;
+        for (ChunkHash byteString : result.getAllChunks()) {
+            size += chunksBySha256.get(byteString).encryptedBytes().length;
+        }
+        assertThat(size).isEqualTo(expectedSize);
+    }
+
+    @Test
+    public void testBackup_forSameFile_producesNoNewChunks() throws Exception {
+        byte[] backupData = getRandomData(BACKUP_SIZE);
+        BackupEncrypter.Result result = runBackup(backupData, ImmutableList.of());
+
+        BackupEncrypter.Result incrementalResult = runBackup(backupData, result.getAllChunks());
+
+        assertThat(incrementalResult.getNewChunks()).isEmpty();
+    }
+
+    @Test
+    public void testBackup_onlyUpdatesChangedChunks() throws Exception {
+        byte[] backupData = getRandomData(BACKUP_SIZE);
+        BackupEncrypter.Result result = runBackup(backupData, ImmutableList.of());
+
+        // Let's update the 2nd and 5th chunk
+        backupData[positionOfChunk(result, 1)]++;
+        backupData[positionOfChunk(result, 4)]++;
+        BackupEncrypter.Result incrementalResult = runBackup(backupData, result.getAllChunks());
+
+        assertThat(incrementalResult.getNewChunks()).hasSize(2);
+    }
+
+    @Test
+    public void testBackup_doesNotIncludeUpdatedChunksInNewListing() throws Exception {
+        byte[] backupData = getRandomData(BACKUP_SIZE);
+        BackupEncrypter.Result result = runBackup(backupData, ImmutableList.of());
+
+        // Let's update the 2nd and 5th chunk
+        backupData[positionOfChunk(result, 1)]++;
+        backupData[positionOfChunk(result, 4)]++;
+        BackupEncrypter.Result incrementalResult = runBackup(backupData, result.getAllChunks());
+
+        List<EncryptedChunk> newChunks = incrementalResult.getNewChunks();
+        List<ChunkHash> chunkListing = result.getAllChunks();
+        assertThat(newChunks).doesNotContain(chunkListing.get(1));
+        assertThat(newChunks).doesNotContain(chunkListing.get(4));
+    }
+
+    @Test
+    public void testBackup_includesUnchangedChunksInNewListing() throws Exception {
+        byte[] backupData = getRandomData(BACKUP_SIZE);
+        BackupEncrypter.Result result = runBackup(backupData, ImmutableList.of());
+
+        // Let's update the 2nd and 5th chunk
+        backupData[positionOfChunk(result, 1)]++;
+        backupData[positionOfChunk(result, 4)]++;
+        BackupEncrypter.Result incrementalResult = runBackup(backupData, result.getAllChunks());
+
+        HashSet<ChunkHash> chunksPresentInIncremental =
+                new HashSet<>(incrementalResult.getAllChunks());
+        chunksPresentInIncremental.removeAll(result.getAllChunks());
+
+        assertThat(chunksPresentInIncremental).hasSize(2);
+    }
+
+    @Test
+    public void testBackup_forSameData_createsSameDigest() throws Exception {
+        byte[] backupData = getRandomData(SMALL_BACKUP_SIZE);
+
+        BackupEncrypter.Result result = runBackup(backupData, ImmutableList.of());
+        BackupEncrypter.Result result2 = runBackup(backupData, ImmutableList.of());
+        assertThat(result.getDigest()).isEqualTo(result2.getDigest());
+    }
+
+    @Test
+    public void testBackup_forDifferentData_createsDifferentDigest() throws Exception {
+        byte[] backup1Data = getRandomData(SMALL_BACKUP_SIZE);
+        byte[] backup2Data = getRandomData(SMALL_BACKUP_SIZE);
+
+        BackupEncrypter.Result result = runBackup(backup1Data, ImmutableList.of());
+        BackupEncrypter.Result result2 = runBackup(backup2Data, ImmutableList.of());
+        assertThat(result.getDigest()).isNotEqualTo(result2.getDigest());
+    }
+
+    @Test
+    public void testBackup_createsDigestOf32Bytes() throws Exception {
+        assertThat(runBackup(getRandomData(SMALL_BACKUP_SIZE), ImmutableList.of()).getDigest())
+                .hasLength(MESSAGE_DIGEST_SIZE_IN_BYTES);
+    }
+
+    private byte[] getRandomData(int size) throws Exception {
+        RandomInputStream randomInputStream = new RandomInputStream(mRandom, size);
+        byte[] backupData = new byte[size];
+        randomInputStream.read(backupData);
+        return backupData;
+    }
+
+    private BackupEncrypter.Result runBackup(int backupSize) throws Exception {
+        RandomInputStream dataStream = new RandomInputStream(mRandom, backupSize);
+        BackupStreamEncrypter task =
+                new BackupStreamEncrypter(
+                        dataStream, MIN_CHUNK_SIZE, MAX_CHUNK_SIZE, AVERAGE_CHUNK_SIZE);
+        return task.backup(mSecretKey, mSalt, ImmutableSet.of());
+    }
+
+    private BackupEncrypter.Result runBackup(byte[] data, List<ChunkHash> existingChunks)
+            throws Exception {
+        ByteArrayInputStream dataStream = new ByteArrayInputStream(data);
+        BackupStreamEncrypter task =
+                new BackupStreamEncrypter(
+                        dataStream, MIN_CHUNK_SIZE, MAX_CHUNK_SIZE, AVERAGE_CHUNK_SIZE);
+        return task.backup(mSecretKey, mSalt, ImmutableSet.copyOf(existingChunks));
+    }
+
+    /** Returns a {@link HashMap} of the chunks, indexed by the SHA-256 Mac key. */
+    private static HashMap<ChunkHash, EncryptedChunk> chunksIndexedByKey(
+            List<EncryptedChunk> chunks) {
+        HashMap<ChunkHash, EncryptedChunk> chunksByKey = new HashMap<>();
+        for (EncryptedChunk chunk : chunks) {
+            chunksByKey.put(chunk.key(), chunk);
+        }
+        return chunksByKey;
+    }
+
+    /**
+     * Returns the start position of the chunk in the plaintext backup data.
+     *
+     * @param result The result from a backup.
+     * @param index The index of the chunk in question.
+     * @return the start position.
+     */
+    private static int positionOfChunk(BackupEncrypter.Result result, int index) {
+        HashMap<ChunkHash, EncryptedChunk> byKey = chunksIndexedByKey(result.getNewChunks());
+        List<ChunkHash> listing = result.getAllChunks();
+
+        int position = 0;
+        for (int i = 0; i < index - 1; i++) {
+            EncryptedChunk chunk = byKey.get(listing.get(i));
+            position += chunk.encryptedBytes().length - BYTES_OVERHEAD_PER_CHUNK;
+        }
+
+        return position;
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/testing/RandomInputStream.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/testing/RandomInputStream.java
new file mode 100644
index 0000000..998da0b
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/testing/RandomInputStream.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2019 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.testing;
+
+import static com.android.internal.util.Preconditions.checkArgument;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.util.Random;
+
+/** {@link InputStream} that generates random bytes up to a given length. For testing purposes. */
+public class RandomInputStream extends InputStream {
+    private static final int BYTE_MAX_VALUE = 255;
+
+    private final Random mRandom;
+    private final int mSizeBytes;
+    private int mBytesRead;
+
+    /**
+     * A new instance, generating {@code sizeBytes} from {@code random} as a source.
+     *
+     * @param random Source of random bytes.
+     * @param sizeBytes The number of bytes to generate before closing the stream.
+     */
+    public RandomInputStream(Random random, int sizeBytes) {
+        mRandom = random;
+        mSizeBytes = sizeBytes;
+        mBytesRead = 0;
+    }
+
+    @Override
+    public int read() throws IOException {
+        if (isFinished()) {
+            return -1;
+        }
+        mBytesRead++;
+        return mRandom.nextInt(BYTE_MAX_VALUE);
+    }
+
+    @Override
+    public int read(byte[] b, int off, int len) throws IOException {
+        checkArgument(off + len <= b.length);
+        if (isFinished()) {
+            return -1;
+        }
+        int length = Math.min(len, mSizeBytes - mBytesRead);
+        int end = off + length;
+
+        for (int i = off; i < end; ) {
+            for (int rnd = mRandom.nextInt(), n = Math.min(end - i, Integer.SIZE / Byte.SIZE);
+                    n-- > 0;
+                    rnd >>= Byte.SIZE) {
+                b[i++] = (byte) rnd;
+            }
+        }
+
+        mBytesRead += length;
+        return length;
+    }
+
+    private boolean isFinished() {
+        return mBytesRead >= mSizeBytes;
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/CryptoTestUtils.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/CryptoTestUtils.java
new file mode 100644
index 0000000..3f3494d
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/CryptoTestUtils.java
@@ -0,0 +1,45 @@
+/*
+ * 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.testing;
+
+import java.security.NoSuchAlgorithmException;
+import java.util.Random;
+
+import javax.crypto.KeyGenerator;
+import javax.crypto.SecretKey;
+
+/** Helpers for crypto code tests. */
+public class CryptoTestUtils {
+    private static final String KEY_ALGORITHM = "AES";
+    private static final int KEY_SIZE_BITS = 256;
+
+    private CryptoTestUtils() {}
+
+    public static SecretKey generateAesKey() throws NoSuchAlgorithmException {
+        KeyGenerator keyGenerator = KeyGenerator.getInstance(KEY_ALGORITHM);
+        keyGenerator.init(KEY_SIZE_BITS);
+        return keyGenerator.generateKey();
+    }
+
+    /** Generates a byte array of size {@code n} containing random bytes. */
+    public static byte[] generateRandomBytes(int n) {
+        byte[] bytes = new byte[n];
+        Random random = new Random();
+        random.nextBytes(bytes);
+        return bytes;
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/shadows/ShadowInternalRecoveryServiceException.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/shadows/ShadowInternalRecoveryServiceException.java
new file mode 100644
index 0000000..9c06d81
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/shadows/ShadowInternalRecoveryServiceException.java
@@ -0,0 +1,43 @@
+/*
+ * 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.testing.shadows;
+
+import android.security.keystore.recovery.InternalRecoveryServiceException;
+
+import org.robolectric.annotation.Implementation;
+import org.robolectric.annotation.Implements;
+
+/** Shadow {@link InternalRecoveryServiceException}. */
+@Implements(InternalRecoveryServiceException.class)
+public class ShadowInternalRecoveryServiceException {
+    private String mMessage;
+
+    @Implementation
+    public void __constructor__(String message) {
+        mMessage = message;
+    }
+
+    @Implementation
+    public void __constructor__(String message, Throwable cause) {
+        mMessage = message;
+    }
+
+    @Implementation
+    public String getMessage() {
+        return mMessage;
+    }
+}
diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/shadows/ShadowRecoveryController.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/shadows/ShadowRecoveryController.java
new file mode 100644
index 0000000..7dad8a4
--- /dev/null
+++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/testing/shadows/ShadowRecoveryController.java
@@ -0,0 +1,152 @@
+/*
+ * 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.testing.shadows;
+
+import android.content.Context;
+import android.security.keystore.recovery.InternalRecoveryServiceException;
+import android.security.keystore.recovery.LockScreenRequiredException;
+import android.security.keystore.recovery.RecoveryController;
+
+import com.google.common.collect.ImmutableList;
+
+import org.robolectric.annotation.Implementation;
+import org.robolectric.annotation.Implements;
+import org.robolectric.annotation.Resetter;
+
+import java.lang.reflect.Constructor;
+import java.security.Key;
+import java.security.NoSuchAlgorithmException;
+import java.security.UnrecoverableKeyException;
+import java.util.HashMap;
+import java.util.List;
+
+import javax.crypto.KeyGenerator;
+
+/**
+ * Shadow of {@link RecoveryController}.
+ *
+ * <p>Instead of generating keys via the {@link RecoveryController}, this shadow generates them in
+ * memory.
+ */
+@Implements(RecoveryController.class)
+public class ShadowRecoveryController {
+    private static final String KEY_GENERATOR_ALGORITHM = "AES";
+    private static final int KEY_SIZE_BITS = 256;
+
+    private static boolean sIsSupported = true;
+    private static boolean sThrowsInternalError = false;
+    private static HashMap<String, Key> sKeysByAlias = new HashMap<>();
+    private static HashMap<String, Integer> sKeyStatusesByAlias = new HashMap<>();
+
+    @Implementation
+    public void __constructor__() {
+        // do not throw
+    }
+
+    @Implementation
+    public static RecoveryController getInstance(Context context) {
+        // Call non-public constructor.
+        try {
+            Constructor<RecoveryController> constructor = RecoveryController.class.getConstructor();
+            return constructor.newInstance();
+        } catch (Exception e) {
+            throw new RuntimeException(e);
+        }
+    }
+
+    @Implementation
+    public static boolean isRecoverableKeyStoreEnabled(Context context) {
+        return sIsSupported;
+    }
+
+    @Implementation
+    public Key generateKey(String alias)
+            throws InternalRecoveryServiceException, LockScreenRequiredException {
+        maybeThrowError();
+        KeyGenerator keyGenerator;
+        try {
+            keyGenerator = KeyGenerator.getInstance(KEY_GENERATOR_ALGORITHM);
+        } catch (NoSuchAlgorithmException e) {
+            // Should never happen
+            throw new RuntimeException(e);
+        }
+
+        keyGenerator.init(KEY_SIZE_BITS);
+        Key key = keyGenerator.generateKey();
+        sKeysByAlias.put(alias, key);
+        sKeyStatusesByAlias.put(alias, RecoveryController.RECOVERY_STATUS_SYNC_IN_PROGRESS);
+        return key;
+    }
+
+    @Implementation
+    public Key getKey(String alias)
+            throws InternalRecoveryServiceException, UnrecoverableKeyException {
+        return sKeysByAlias.get(alias);
+    }
+
+    @Implementation
+    public void removeKey(String alias) throws InternalRecoveryServiceException {
+        sKeyStatusesByAlias.remove(alias);
+        sKeysByAlias.remove(alias);
+    }
+
+    @Implementation
+    public int getRecoveryStatus(String alias) throws InternalRecoveryServiceException {
+        maybeThrowError();
+        return sKeyStatusesByAlias.getOrDefault(
+                alias, RecoveryController.RECOVERY_STATUS_PERMANENT_FAILURE);
+    }
+
+    @Implementation
+    public List<String> getAliases() throws InternalRecoveryServiceException {
+        return ImmutableList.copyOf(sKeyStatusesByAlias.keySet());
+    }
+
+    private static void maybeThrowError() throws InternalRecoveryServiceException {
+        if (sThrowsInternalError) {
+            throw new InternalRecoveryServiceException("test error");
+        }
+    }
+
+    /** Sets the recovery status of the key with {@code alias} to {@code status}. */
+    public static void setRecoveryStatus(String alias, int status) {
+        sKeyStatusesByAlias.put(alias, status);
+    }
+
+    /** Sets all existing keys to being synced. */
+    public static void syncAllKeys() {
+        for (String alias : sKeysByAlias.keySet()) {
+            sKeyStatusesByAlias.put(alias, RecoveryController.RECOVERY_STATUS_SYNCED);
+        }
+    }
+
+    public static void setThrowsInternalError(boolean throwsInternalError) {
+        ShadowRecoveryController.sThrowsInternalError = throwsInternalError;
+    }
+
+    public static void setIsSupported(boolean isSupported) {
+        ShadowRecoveryController.sIsSupported = isSupported;
+    }
+
+    @Resetter
+    public static void reset() {
+        sIsSupported = true;
+        sThrowsInternalError = false;
+        sKeysByAlias.clear();
+        sKeyStatusesByAlias.clear();
+    }
+}