How does update_engine validate a differential update-image with dm-verity enabled?

Question

I am working with Android 8, Android verified boot with dm-verity, and block-based differential seamless A/B updates. To my understanding, the Android update_engine performs some validations of the received update image before it proceeds to write the target partitions. AFAIK, update_engine checks if the differential update can be installed atop the current partitions. How is this check performed?

I can imagine two possibilities, but I haven't found authoritative documentation of either hypothesis:

1. The differential update package contains a linear hash of the source partition. On the device, update_enigne computes a SHA-256 hash of the entire partition on top of which the differential update is to be applied. It compares this value with the one provided as part of the update package and proceeds only if the two values agree.
2. The differential update package contains the dm-verity root hash of the Merkle-Tree used for block-wise validation with dm-verity. The update_engine compares this target root-hash with the one provided on the device in the vbmeta structure. Only if the two match, it proceeds to install the update.

Is either one of these hypotheses correct, or am I missing something? Similarly, how does the update_engine validate the target partitions once they have been written? Via a linear hash, or using the root hash? Or otherwise?

Answer 1

Is either one of these hypotheses correct?

I haven't experimented with A/B device so far but what I understand from official documentation and source code is that it's both. SHA-256 hash of target partition is checked against the one received from update server. And after reboot dm-verity check is performed.

From Life of an A/B update:

"5. The whole partitions are re-read and verified against the expected hash."

Additionally implementer can put extra post-installation checks. And:

"After rebooting, update_verifier triggers the integrity check using dm-verity".
...
"After the check completes, update_verifier marks the boot successful."

.

Android update_engine performs some validations of the received update image before it proceeds to write the target partitions

A/B updates differ from old non-A/B recovery-based updates. In latter case update package is verified twice against public keys in /system/etc/security/otacerts.zip (normal boot) and /res/keys (recovery boot). In case of Block-Based OTAs dm-verity is an additional check. But A/B updates have support for streaming updates:

"Updates can be streamed to A/B devices, removing the need to download the package before installing it. Streaming means it's not necessary for the user to have enough free space to store the update package on /data or /cache
...
update_engine will update the raw blocks on the currently unused partition as it streams the update package."

So it's not always possible to verify the integrity of whole update package (payload) before flashing. Instead integrity of update package is verified after updating. If something goes wrong, the older partition slot is still intact as a fallback while the updated slot is marked unbootable until next update.

.

Does that mean that update_engine computes a complete linear SHA-256 hash of all source-partitions that it is supposed to update?

"During incremental or delta updates, the binary data from the current slot is used to generate the data in the new slot". But update_engine computes hashes of all target partitions after those are updated. From source code:

"This action will hash all the partitions of the target slot involved in the update. The hashes are then verified against the ones in the InstallPlan. If the target hash does not match, the action will fail."

.

dm-verity does not perform an exhaustive check on every boot, because that would take way too long. That's why I assume that update_verifier, in contrast, does the exhaustive verification upon a reboot after a successful installation

From the details found in Implementing dm-verity, hash of every 4k block is pre-calculated and appended at the end of system.img (or vendor.img) in dm-verity table (metablock; slightly different details in case of AVB) which is signed by OEM's private key. Public key is saved to kernel's system keyring (on A/B devices) which kernel uses to verify the integrity of verity table on every boot.

"One way of verifying a block device is to directly hash its contents and compare them to a stored value. However, attempting to verify an entire block device can take an extended period and consume much of a device's power.
...
Instead, dm-verity verifies blocks individually and only when each one is accessed. When read into memory, the block is hashed in parallel. The hash is then verified up the tree. And since reading the block is such an expensive operation, the latency introduced by this block-level verification is comparatively nominal.
...
If verification fails, the device generates an I/O error indicating the block cannot be read."

update_verifier reads a list of blocks on next reboot. No I/O error means new system.img is signed by genuine key and the updated slot is marked successful.

for a very small differential update, only the blocks that have changed are checked. For a full update, all blocks are re-read. Is this assumption correct?

Documentation says:

"update_verifier will read only the blocks listed in /data/ota_package/care_map.txt, which is included in an A/B OTA package"

It won't read other blocks whether updated or not.