diff --git a/Android.mk b/Android.mk
index 69490a5..93e658c 100644
--- a/Android.mk
+++ b/Android.mk
@@ -162,7 +162,7 @@
 
 LOCAL_FORCE_STATIC_EXECUTABLE := true
 
-LOCAL_MODULE_PATH := $(TARGET_RECOVERY_ROOT_OUT)/sbin
+LOCAL_MODULE_PATH := $(TARGET_RECOVERY_ROOT_OUT)/system/bin
 
 # Cannot link with LLD: undefined symbol: UsbNoPermissionsLongHelpText
 # http://b/77543887, lld does not handle -Wl,--gc-sections as well as ld.
diff --git a/adb_install.cpp b/adb_install.cpp
index 4ee5333..97dff22 100644
--- a/adb_install.cpp
+++ b/adb_install.cpp
@@ -82,7 +82,7 @@
 
   pid_t child;
   if ((child = fork()) == 0) {
-    execl("/sbin/recovery", "recovery", "--adbd", nullptr);
+    execl("/system/bin/recovery", "recovery", "--adbd", nullptr);
     _exit(EXIT_FAILURE);
   }
 
diff --git a/bootloader_message/Android.bp b/bootloader_message/Android.bp
index ab23733..5cd2132 100644
--- a/bootloader_message/Android.bp
+++ b/bootloader_message/Android.bp
@@ -14,7 +14,7 @@
 // limitations under the License.
 //
 
-cc_library_static {
+cc_library {
     name: "libbootloader_message",
     recovery_available: true,
     srcs: ["bootloader_message.cpp"],
@@ -22,7 +22,7 @@
         "-Wall",
         "-Werror",
     ],
-    static_libs: [
+    shared_libs: [
         "libbase",
         "libfs_mgr",
     ],
diff --git a/etc/init.rc b/etc/init.rc
index 96c37b1..8e18438 100644
--- a/etc/init.rc
+++ b/etc/init.rc
@@ -85,7 +85,7 @@
     critical
     seclabel u:r:charger:s0
 
-service recovery /sbin/recovery
+service recovery /system/bin/recovery
     seclabel u:r:recovery:s0
 
 service adbd /system/bin/adbd --root_seclabel=u:r:su:s0 --device_banner=recovery
diff --git a/tests/Android.mk b/tests/Android.mk
index 1fa259e..e68e77e 100644
--- a/tests/Android.mk
+++ b/tests/Android.mk
@@ -113,7 +113,8 @@
     component/verifier_test.cpp
 
 LOCAL_SHARED_LIBRARIES := \
-    libhidlbase
+    libhidlbase \
+    libprotobuf-cpp-lite
 
 tune2fs_static_libraries := \
     libext2_com_err \
diff --git a/tests/component/update_verifier_test.cpp b/tests/component/update_verifier_test.cpp
index f6ef6dc..a970716 100644
--- a/tests/component/update_verifier_test.cpp
+++ b/tests/component/update_verifier_test.cpp
@@ -14,14 +14,20 @@
  * limitations under the License.
  */
 
+#include <update_verifier/update_verifier.h>
+
 #include <string>
+#include <unordered_map>
+#include <vector>
 
 #include <android-base/file.h>
 #include <android-base/properties.h>
 #include <android-base/strings.h>
 #include <android-base/test_utils.h>
+#include <google/protobuf/repeated_field.h>
 #include <gtest/gtest.h>
-#include <update_verifier/update_verifier.h>
+
+#include "care_map.pb.h"
 
 class UpdateVerifierTest : public ::testing::Test {
  protected:
@@ -30,7 +36,30 @@
     verity_supported = android::base::EqualsIgnoreCase(verity_mode, "enforcing");
   }
 
+  // Returns a serialized string of the proto3 message according to the given partition info.
+  std::string ConstructProto(
+      std::vector<std::unordered_map<std::string, std::string>>& partitions) {
+    UpdateVerifier::CareMap result;
+    for (const auto& partition : partitions) {
+      UpdateVerifier::CareMap::PartitionInfo info;
+      if (partition.find("name") != partition.end()) {
+        info.set_name(partition.at("name"));
+      }
+      if (partition.find("ranges") != partition.end()) {
+        info.set_ranges(partition.at("ranges"));
+      }
+      if (partition.find("fingerprint") != partition.end()) {
+        info.set_fingerprint(partition.at("fingerprint"));
+      }
+
+      *result.add_partitions() = info;
+    }
+
+    return result.SerializeAsString();
+  }
+
   bool verity_supported;
+  TemporaryFile care_map_file;
 };
 
 TEST_F(UpdateVerifierTest, verify_image_no_care_map) {
@@ -45,26 +74,26 @@
     return;
   }
 
-  TemporaryFile temp_file;
   std::string content = "system\n2,0,1";
-  ASSERT_TRUE(android::base::WriteStringToFile(content, temp_file.path));
-  ASSERT_TRUE(verify_image(temp_file.path));
+  ASSERT_TRUE(android::base::WriteStringToFile(content, care_map_file.path));
+  ASSERT_TRUE(verify_image(care_map_file.path));
 
   // Leading and trailing newlines should be accepted.
-  ASSERT_TRUE(android::base::WriteStringToFile("\n" + content + "\n\n", temp_file.path));
-  ASSERT_TRUE(verify_image(temp_file.path));
+  ASSERT_TRUE(android::base::WriteStringToFile("\n" + content + "\n\n", care_map_file.path));
+  ASSERT_TRUE(verify_image(care_map_file.path));
+}
+
+TEST_F(UpdateVerifierTest, verify_image_empty_care_map) {
+  ASSERT_FALSE(verify_image(care_map_file.path));
 }
 
 TEST_F(UpdateVerifierTest, verify_image_wrong_lines) {
   // The care map file can have only 2 / 4 / 6 lines.
-  TemporaryFile temp_file;
-  ASSERT_FALSE(verify_image(temp_file.path));
+  ASSERT_TRUE(android::base::WriteStringToFile("line1", care_map_file.path));
+  ASSERT_FALSE(verify_image(care_map_file.path));
 
-  ASSERT_TRUE(android::base::WriteStringToFile("line1", temp_file.path));
-  ASSERT_FALSE(verify_image(temp_file.path));
-
-  ASSERT_TRUE(android::base::WriteStringToFile("line1\nline2\nline3", temp_file.path));
-  ASSERT_FALSE(verify_image(temp_file.path));
+  ASSERT_TRUE(android::base::WriteStringToFile("line1\nline2\nline3", care_map_file.path));
+  ASSERT_FALSE(verify_image(care_map_file.path));
 }
 
 TEST_F(UpdateVerifierTest, verify_image_malformed_care_map) {
@@ -74,10 +103,9 @@
     return;
   }
 
-  TemporaryFile temp_file;
   std::string content = "system\n2,1,0";
-  ASSERT_TRUE(android::base::WriteStringToFile(content, temp_file.path));
-  ASSERT_FALSE(verify_image(temp_file.path));
+  ASSERT_TRUE(android::base::WriteStringToFile(content, care_map_file.path));
+  ASSERT_FALSE(verify_image(care_map_file.path));
 }
 
 TEST_F(UpdateVerifierTest, verify_image_legacy_care_map) {
@@ -87,8 +115,55 @@
     return;
   }
 
-  TemporaryFile temp_file;
   std::string content = "/dev/block/bootdevice/by-name/system\n2,1,0";
-  ASSERT_TRUE(android::base::WriteStringToFile(content, temp_file.path));
-  ASSERT_TRUE(verify_image(temp_file.path));
+  ASSERT_TRUE(android::base::WriteStringToFile(content, care_map_file.path));
+  ASSERT_TRUE(verify_image(care_map_file.path));
+}
+
+TEST_F(UpdateVerifierTest, verify_image_protobuf_care_map_smoke) {
+  // This test relies on dm-verity support.
+  if (!verity_supported) {
+    GTEST_LOG_(INFO) << "Test skipped on devices without dm-verity support.";
+    return;
+  }
+
+  std::vector<std::unordered_map<std::string, std::string>> partitions = {
+    { { "name", "system" }, { "ranges", "2,0,1" } },
+  };
+
+  std::string proto = ConstructProto(partitions);
+  ASSERT_TRUE(android::base::WriteStringToFile(proto, care_map_file.path));
+  ASSERT_TRUE(verify_image(care_map_file.path));
+}
+
+TEST_F(UpdateVerifierTest, verify_image_protobuf_care_map_missing_name) {
+  // This test relies on dm-verity support.
+  if (!verity_supported) {
+    GTEST_LOG_(INFO) << "Test skipped on devices without dm-verity support.";
+    return;
+  }
+
+  std::vector<std::unordered_map<std::string, std::string>> partitions = {
+    { { "ranges", "2,0,1" } },
+  };
+
+  std::string proto = ConstructProto(partitions);
+  ASSERT_TRUE(android::base::WriteStringToFile(proto, care_map_file.path));
+  ASSERT_FALSE(verify_image(care_map_file.path));
+}
+
+TEST_F(UpdateVerifierTest, verify_image_protobuf_care_map_bad_ranges) {
+  // This test relies on dm-verity support.
+  if (!verity_supported) {
+    GTEST_LOG_(INFO) << "Test skipped on devices without dm-verity support.";
+    return;
+  }
+
+  std::vector<std::unordered_map<std::string, std::string>> partitions = {
+    { { "name", "system" }, { "ranges", "3,0,1" } },
+  };
+
+  std::string proto = ConstructProto(partitions);
+  ASSERT_TRUE(android::base::WriteStringToFile(proto, care_map_file.path));
+  ASSERT_FALSE(verify_image(care_map_file.path));
 }
diff --git a/update_verifier/Android.bp b/update_verifier/Android.bp
index f6c7056..f4dc1f4 100644
--- a/update_verifier/Android.bp
+++ b/update_verifier/Android.bp
@@ -33,6 +33,7 @@
     ],
 
     srcs: [
+        "care_map.proto",
         "update_verifier.cpp",
     ],
 
@@ -49,6 +50,11 @@
         "libbase",
         "libcutils",
     ],
+
+    proto: {
+        type: "lite",
+        export_proto_headers: true,
+    }
 }
 
 cc_binary {
@@ -74,6 +80,7 @@
         "libhardware",
         "libhidlbase",
         "liblog",
+        "libprotobuf-cpp-lite",
         "libutils",
     ],
 
diff --git a/update_verifier/care_map.proto b/update_verifier/care_map.proto
new file mode 100644
index 0000000..442ddd4
--- /dev/null
+++ b/update_verifier/care_map.proto
@@ -0,0 +1,31 @@
+/*
+ * 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.
+ */
+
+syntax = "proto3";
+
+package UpdateVerifier;
+option optimize_for = LITE_RUNTIME;
+
+message CareMap {
+  message PartitionInfo {
+    string name = 1;
+    string ranges = 2;
+    string id = 3;
+    string fingerprint = 4;
+  }
+
+  repeated PartitionInfo partitions = 1;
+}
diff --git a/update_verifier/include/update_verifier/update_verifier.h b/update_verifier/include/update_verifier/update_verifier.h
index 16b394e..534384e 100644
--- a/update_verifier/include/update_verifier/update_verifier.h
+++ b/update_verifier/include/update_verifier/update_verifier.h
@@ -20,5 +20,13 @@
 
 int update_verifier(int argc, char** argv);
 
-// Exposed for testing purpose.
+// Returns true to indicate a passing verification (or the error should be ignored); Otherwise
+// returns false on fatal errors, where we should reject the current boot and trigger a fallback.
+// This function tries to process the care_map.txt as protobuf message; and falls back to use the
+// plain text format if the parse failed.
+//
+// Note that update_verifier should be backward compatible to not reject care_map.txt from old
+// releases, which could otherwise fail to boot into the new release. For example, we've changed
+// the care_map format between N and O. An O update_verifier would fail to work with N care_map.txt.
+// This could be a result of sideloading an O OTA while the device having a pending N update.
 bool verify_image(const std::string& care_map_name);
diff --git a/update_verifier/update_verifier.cpp b/update_verifier/update_verifier.cpp
index dc72763..5e5aa18 100644
--- a/update_verifier/update_verifier.cpp
+++ b/update_verifier/update_verifier.cpp
@@ -60,6 +60,7 @@
 #include <android/hardware/boot/1.0/IBootControl.h>
 #include <cutils/android_reboot.h>
 
+#include "care_map.pb.h"
 #include "otautil/rangeset.h"
 
 using android::sp;
@@ -189,33 +190,12 @@
   return ret;
 }
 
-// Returns true to indicate a passing verification (or the error should be ignored); Otherwise
-// returns false on fatal errors, where we should reject the current boot and trigger a fallback.
-// Note that update_verifier should be backward compatible to not reject care_map.txt from old
-// releases, which could otherwise fail to boot into the new release. For example, we've changed
-// the care_map format between N and O. An O update_verifier would fail to work with N
-// care_map.txt. This could be a result of sideloading an O OTA while the device having a pending N
-// update.
-bool verify_image(const std::string& care_map_name) {
-  android::base::unique_fd care_map_fd(TEMP_FAILURE_RETRY(open(care_map_name.c_str(), O_RDONLY)));
-  // If the device is flashed before the current boot, it may not have care_map.txt
-  // in /data/ota_package. To allow the device to continue booting in this situation,
-  // we should print a warning and skip the block verification.
-  if (care_map_fd.get() == -1) {
-    PLOG(WARNING) << "Failed to open " << care_map_name;
-    return true;
-  }
+static bool process_care_map_plain_text(const std::string& care_map_contents) {
   // care_map file has up to six lines, where every two lines make a pair. Within each pair, the
   // first line has the partition name (e.g. "system"), while the second line holds the ranges of
   // all the blocks to verify.
-  std::string file_content;
-  if (!android::base::ReadFdToString(care_map_fd.get(), &file_content)) {
-    LOG(ERROR) << "Error reading care map contents to string.";
-    return false;
-  }
-
-  std::vector<std::string> lines;
-  lines = android::base::Split(android::base::Trim(file_content), "\n");
+  std::vector<std::string> lines =
+      android::base::Split(android::base::Trim(care_map_contents), "\n");
   if (lines.size() != 2 && lines.size() != 4 && lines.size() != 6) {
     LOG(ERROR) << "Invalid lines in care_map: found " << lines.size()
                << " lines, expecting 2 or 4 or 6 lines.";
@@ -237,6 +217,50 @@
   return true;
 }
 
+bool verify_image(const std::string& care_map_name) {
+  android::base::unique_fd care_map_fd(TEMP_FAILURE_RETRY(open(care_map_name.c_str(), O_RDONLY)));
+  // If the device is flashed before the current boot, it may not have care_map.txt in
+  // /data/ota_package. To allow the device to continue booting in this situation, we should
+  // print a warning and skip the block verification.
+  if (care_map_fd.get() == -1) {
+    PLOG(WARNING) << "Failed to open " << care_map_name;
+    return true;
+  }
+
+  std::string file_content;
+  if (!android::base::ReadFdToString(care_map_fd.get(), &file_content)) {
+    PLOG(ERROR) << "Failed to read " << care_map_name;
+    return false;
+  }
+
+  if (file_content.empty()) {
+    LOG(ERROR) << "Unexpected empty care map";
+    return false;
+  }
+
+  UpdateVerifier::CareMap care_map;
+  // Falls back to use the plain text version if we cannot parse the file as protobuf message.
+  if (!care_map.ParseFromString(file_content)) {
+    return process_care_map_plain_text(file_content);
+  }
+
+  for (const auto& partition : care_map.partitions()) {
+    if (partition.name().empty()) {
+      LOG(ERROR) << "Unexpected empty partition name.";
+      return false;
+    }
+    if (partition.ranges().empty()) {
+      LOG(ERROR) << "Unexpected block ranges for partition " << partition.name();
+      return false;
+    }
+    if (!read_blocks(partition.name(), partition.ranges())) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
 static int reboot_device() {
   if (android_reboot(ANDROID_RB_RESTART2, 0, nullptr) == -1) {
     LOG(ERROR) << "Failed to reboot.";