diff --git a/README.md b/README.md
index 827e55c..4905b56 100644
--- a/README.md
+++ b/README.md
@@ -20,6 +20,7 @@
 * [Microdroid kernel](microdroid/kernel/README.md)
 * [Microdroid payload](microdroid/payload/README.md)
 * [vmbase](vmbase/README.md)
+* [Encrypted Storage](encryptedstore/README.md)
 
 AVF APIs:
 * [Java API](java/framework/README.md)
diff --git a/encryptedstore/README.md b/encryptedstore/README.md
new file mode 100644
index 0000000..544d6eb
--- /dev/null
+++ b/encryptedstore/README.md
@@ -0,0 +1,31 @@
+# Encrypted Storage
+
+Since Android U, AVF (with Microdroid) supports Encrypted Storage which is the storage solution
+in a VM. Within a VM, this is mounted at a path that can be retrieved via the [`AVmPayload_getEncryptedStoragePath()`][vm_payload_api].
+Any data written in encrypted storage is persisted and is available next time the VM is run.
+
+Encrypted Storage is backed by a para-virtualized block device on the guest which is further
+backed by a qcow2 disk image in the host. The block device is formatted with an ext4 filesystem.
+
+## Security
+
+Encrypted Storage uses block level encryption layer (Device-Mapper's "crypt" target) using a key
+derived from the VM secret and AES256 cipher with HCTR2 mode. The Block level encryption ensures
+the filesystem is also encrypted.
+
+### Integrity
+Encrypted Storage does not offer the level of integrity offered by primitives such as
+authenticated encryption/dm-integrity/RPMB. That level of integrity comes with substantial
+disk/performance overhead. Instead, it uses HCTR2 which is a super-pseudorandom
+permutation encryption mode, this offers better resilience against malleability attacks (than other
+modes such as XTS).
+
+## Encrypted Storage and Updatable VMs
+
+With [Updatable VM feature][updatable_vm] shipping in Android V, Encrypted Storage can be accessed
+even after OTA/updates of boot images and apks. This requires chipsets to support [Secretkeeper HAL][sk_hal].
+
+
+[vm_payload_api]: https://cs.android.com/android/platform/superproject/main/+/main:packages/modules/Virtualization/vm_payload/include/vm_payload.h;l=2?q=vm_payload%2Finclude%2Fvm_payload.h&ss=android%2Fplatform%2Fsuperproject%2Fmain
+[updatable_vm]: https://cs.android.com/android/platform/superproject/main/+/main:packages/modules/Virtualization/docs/updatable_vm.md
+[sk_hal]: https://cs.android.com/android/platform/superproject/main/+/main:system/secretkeeper/README.md
diff --git a/java/framework/README.md b/java/framework/README.md
index cf7a6cb..bbcd0ef 100644
--- a/java/framework/README.md
+++ b/java/framework/README.md
@@ -339,6 +339,8 @@
 powerful attacker could delete it, wholly or partially roll it back to an
 earlier version, or modify it, corrupting the data.
 
+For more info see [README](https://cs.android.com/android/platform/superproject/main/+/main:packages/modules/Virtualization/java/framework/README.md)
+
 # Transferring a VM
 
 It is possible to make a copy of a VM instance. This can be used to transfer a
diff --git a/libs/devicemapper/src/crypt.rs b/libs/devicemapper/src/crypt.rs
index 36c45c7..3afd374 100644
--- a/libs/devicemapper/src/crypt.rs
+++ b/libs/devicemapper/src/crypt.rs
@@ -15,8 +15,8 @@
  */
 
 /// `crypt` module implements the "crypt" target in the device mapper framework. Specifically,
-/// it provides `DmCryptTargetBuilder` struct which is used to construct a `DmCryptTarget` struct
-/// which is then given to `DeviceMapper` to create a mapper device.
+/// it provides `DmCryptTargetBuilder` struct which is used to construct a `DmCryptTarget`
+/// struct which is then given to `DeviceMapper` to create a mapper device.
 use crate::DmTargetSpec;
 
 use anyhow::{ensure, Context, Result};
@@ -33,9 +33,14 @@
 /// Supported ciphers
 #[derive(Clone, Copy, Debug)]
 pub enum CipherType {
-    // AES-256-HCTR2 takes a 32-byte key
+    /// AES256 with HCTR2 mode. HCTR2 is a tweakable super-pseudorandom permutation
+    /// length-preserving encryption mode. It is the preferred mode in absence of other
+    /// dedicated integrity primitives (such as for encryptedstore in pVM) since it is less
+    /// malleable than other modes.
     AES256HCTR2,
-    // XTS requires key of twice the length of the underlying block cipher i.e., 64B for AES256
+    /// AES with XTS mode. This has slight performance benefits over HCTR2. In particular, XTS is
+    /// supported by inline encryption hardware. Note that (status quo) `encryptedstore` in VMs
+    /// is the only user of this module & inline encryption is not supported by guest kernel.
     AES256XTS,
 }
 impl CipherType {
@@ -50,7 +55,10 @@
 
     fn get_required_key_size(&self) -> usize {
         match *self {
+            // AES-256-HCTR2 takes a 32-byte key
             CipherType::AES256HCTR2 => 32,
+            // XTS requires key of twice the length of the underlying block cipher
+            // i.e., 64B for AES256
             CipherType::AES256XTS => 64,
         }
     }
diff --git a/pvmfw/src/instance.rs b/pvmfw/src/instance.rs
index 6daadd9..43c7442 100644
--- a/pvmfw/src/instance.rs
+++ b/pvmfw/src/instance.rs
@@ -27,7 +27,6 @@
 use log::trace;
 use uuid::Uuid;
 use virtio_drivers::transport::{pci::bus::PciRoot, DeviceType, Transport};
-use vmbase::rand;
 use vmbase::util::ceiling_div;
 use vmbase::virtio::pci::{PciTransportIterator, VirtIOBlk};
 use vmbase::virtio::HalImpl;
@@ -38,8 +37,6 @@
 pub enum Error {
     /// Unexpected I/O error while accessing the underlying disk.
     FailedIo(gpt::Error),
-    /// Failed to generate a random salt to be stored.
-    FailedSaltGeneration(rand::Error),
     /// Impossible to create a new instance.img entry.
     InstanceImageFull,
     /// Badly formatted instance.img header block.
@@ -66,7 +63,6 @@
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         match self {
             Self::FailedIo(e) => write!(f, "Failed I/O to disk: {e}"),
-            Self::FailedSaltGeneration(e) => write!(f, "Failed to generate salt: {e}"),
             Self::InstanceImageFull => write!(f, "Failed to obtain a free instance.img partition"),
             Self::InvalidInstanceImageHeader => write!(f, "instance.img header is invalid"),
             Self::MissingInstanceImage => write!(f, "Failed to find the instance.img partition"),
@@ -93,27 +89,27 @@
 
 pub type Result<T> = core::result::Result<T, Error>;
 
-pub fn get_or_generate_instance_salt(
+fn aead_ctx_from_secret(secret: &[u8]) -> Result<AeadContext> {
+    let key = hkdf::<32>(secret, /* salt= */ &[], b"vm-instance", Digester::sha512())?;
+    Ok(AeadContext::new(Aead::aes_256_gcm_randnonce(), key.as_slice(), /* tag_len */ None)?)
+}
+
+/// Get the entry from instance.img. This method additionally returns Partition corresponding to
+/// pvmfw in the instance.img as well as index corresponding to empty header which can be used to
+/// record instance data with `record_instance_entry`.
+pub(crate) fn get_recorded_entry(
     pci_root: &mut PciRoot,
-    dice_inputs: &PartialInputs,
     secret: &[u8],
-) -> Result<(bool, Hidden)> {
+) -> Result<(Option<EntryBody>, Partition, usize)> {
     let mut instance_img = find_instance_img(pci_root)?;
 
     let entry = locate_entry(&mut instance_img)?;
     trace!("Found pvmfw instance.img entry: {entry:?}");
 
-    let key = hkdf::<32>(secret, /* salt= */ &[], b"vm-instance", Digester::sha512())?;
-    let tag_len = None;
-    let aead_ctx = AeadContext::new(Aead::aes_256_gcm_randnonce(), key.as_slice(), tag_len)?;
-    let ad = &[];
-    // The nonce is generated internally for `aes_256_gcm_randnonce`, so no additional
-    // nonce is required.
-    let nonce = &[];
-
-    let mut blk = [0; BLK_SIZE];
     match entry {
         PvmfwEntry::Existing { header_index, payload_size } => {
+            let aead_ctx = aead_ctx_from_secret(secret)?;
+            let mut blk = [0; BLK_SIZE];
             if payload_size > blk.len() {
                 // We currently only support single-blk entries.
                 return Err(Error::UnsupportedEntrySize(payload_size));
@@ -123,52 +119,41 @@
 
             let payload = &blk[..payload_size];
             let mut entry = [0; size_of::<EntryBody>()];
-            let decrypted = aead_ctx.open(payload, nonce, ad, &mut entry)?;
-
+            // The nonce is generated internally for `aes_256_gcm_randnonce`, so no additional
+            // nonce is required.
+            let decrypted =
+                aead_ctx.open(payload, /* nonce */ &[], /* ad */ &[], &mut entry)?;
             let body = EntryBody::read_from(decrypted).unwrap();
-            if dice_inputs.rkp_vm_marker {
-                // The RKP VM is allowed to run if it has passed the verified boot check and
-                // contains the expected version in its AVB footer.
-                // The comparison below with the previous boot information is skipped to enable the
-                // simultaneous update of the pvmfw and RKP VM.
-                // For instance, when both the pvmfw and RKP VM are updated, the code hash of the
-                // RKP VM will differ from the one stored in the instance image. In this case, the
-                // RKP VM is still allowed to run.
-                // This ensures that the updated RKP VM will retain the same CDIs in the next stage.
-                return Ok((false, body.salt));
-            }
-            if body.code_hash != dice_inputs.code_hash {
-                Err(Error::RecordedCodeHashMismatch)
-            } else if body.auth_hash != dice_inputs.auth_hash {
-                Err(Error::RecordedAuthHashMismatch)
-            } else if body.mode() != dice_inputs.mode {
-                Err(Error::RecordedDiceModeMismatch)
-            } else {
-                Ok((false, body.salt))
-            }
+            Ok((Some(body), instance_img, header_index))
         }
-        PvmfwEntry::New { header_index } => {
-            let salt = rand::random_array().map_err(Error::FailedSaltGeneration)?;
-            let body = EntryBody::new(dice_inputs, &salt);
-
-            // We currently only support single-blk entries.
-            let plaintext = body.as_bytes();
-            assert!(plaintext.len() + aead_ctx.aead().max_overhead() < blk.len());
-            let encrypted = aead_ctx.seal(plaintext, nonce, ad, &mut blk)?;
-            let payload_size = encrypted.len();
-            let payload_index = header_index + 1;
-            instance_img.write_block(payload_index, &blk).map_err(Error::FailedIo)?;
-
-            let header = EntryHeader::new(PvmfwEntry::UUID, payload_size);
-            header.write_to_prefix(blk.as_mut_slice()).unwrap();
-            blk[header.as_bytes().len()..].fill(0);
-            instance_img.write_block(header_index, &blk).map_err(Error::FailedIo)?;
-
-            Ok((true, salt))
-        }
+        PvmfwEntry::New { header_index } => Ok((None, instance_img, header_index)),
     }
 }
 
+pub(crate) fn record_instance_entry(
+    body: &EntryBody,
+    secret: &[u8],
+    instance_img: &mut Partition,
+    header_index: usize,
+) -> Result<()> {
+    // We currently only support single-blk entries.
+    let mut blk = [0; BLK_SIZE];
+    let plaintext = body.as_bytes();
+    let aead_ctx = aead_ctx_from_secret(secret)?;
+    assert!(plaintext.len() + aead_ctx.aead().max_overhead() < blk.len());
+    let encrypted = aead_ctx.seal(plaintext, /* nonce */ &[], /* ad */ &[], &mut blk)?;
+    let payload_size = encrypted.len();
+    let payload_index = header_index + 1;
+    instance_img.write_block(payload_index, &blk).map_err(Error::FailedIo)?;
+
+    let header = EntryHeader::new(PvmfwEntry::UUID, payload_size);
+    header.write_to_prefix(blk.as_mut_slice()).unwrap();
+    blk[header.as_bytes().len()..].fill(0);
+    instance_img.write_block(header_index, &blk).map_err(Error::FailedIo)?;
+
+    Ok(())
+}
+
 #[derive(FromZeroes, FromBytes)]
 #[repr(C, packed)]
 struct Header {
@@ -276,15 +261,15 @@
 
 #[derive(AsBytes, FromZeroes, FromBytes)]
 #[repr(C)]
-struct EntryBody {
-    code_hash: Hash,
-    auth_hash: Hash,
-    salt: Hidden,
+pub(crate) struct EntryBody {
+    pub code_hash: Hash,
+    pub auth_hash: Hash,
+    pub salt: Hidden,
     mode: u8,
 }
 
 impl EntryBody {
-    fn new(dice_inputs: &PartialInputs, salt: &Hidden) -> Self {
+    pub(crate) fn new(dice_inputs: &PartialInputs, salt: &Hidden) -> Self {
         let mode = match dice_inputs.mode {
             DiceMode::kDiceModeNotInitialized => 0,
             DiceMode::kDiceModeNormal => 1,
@@ -300,7 +285,7 @@
         }
     }
 
-    fn mode(&self) -> DiceMode {
+    pub(crate) fn mode(&self) -> DiceMode {
         match self.mode {
             1 => DiceMode::kDiceModeNormal,
             2 => DiceMode::kDiceModeDebug,
diff --git a/pvmfw/src/main.rs b/pvmfw/src/main.rs
index f80bae1..12d63d5 100644
--- a/pvmfw/src/main.rs
+++ b/pvmfw/src/main.rs
@@ -37,7 +37,9 @@
 use crate::entry::RebootReason;
 use crate::fdt::modify_for_next_stage;
 use crate::helpers::GUEST_PAGE_SIZE;
-use crate::instance::get_or_generate_instance_salt;
+use crate::instance::EntryBody;
+use crate::instance::Error as InstanceError;
+use crate::instance::{get_recorded_entry, record_instance_entry};
 use alloc::borrow::Cow;
 use alloc::boxed::Box;
 use core::ops::Range;
@@ -150,11 +152,43 @@
         error!("Failed to compute partial DICE inputs: {e:?}");
         RebootReason::InternalError
     })?;
-    let (new_instance, salt) = get_or_generate_instance_salt(&mut pci_root, &dice_inputs, cdi_seal)
-        .map_err(|e| {
-            error!("Failed to get instance.img salt: {e}");
+
+    let (recorded_entry, mut instance_img, header_index) =
+        get_recorded_entry(&mut pci_root, cdi_seal).map_err(|e| {
+            error!("Failed to get entry from instance.img: {e}");
             RebootReason::InternalError
         })?;
+    let (new_instance, salt) = if let Some(entry) = recorded_entry {
+        // The RKP VM is allowed to run if it has passed the verified boot check and
+        // contains the expected version in its AVB footer.
+        // The comparison below with the previous boot information is skipped to enable the
+        // simultaneous update of the pvmfw and RKP VM.
+        // For instance, when both the pvmfw and RKP VM are updated, the code hash of the
+        // RKP VM will differ from the one stored in the instance image. In this case, the
+        // RKP VM is still allowed to run.
+        // This ensures that the updated RKP VM will retain the same CDIs in the next stage.
+        if !dice_inputs.rkp_vm_marker {
+            ensure_dice_measurements_match_entry(&dice_inputs, &entry).map_err(|e| {
+                error!(
+                    "Dice measurements do not match recorded entry.
+                This may be because of update: {e}"
+                );
+                RebootReason::InternalError
+            })?;
+        }
+        (false, entry.salt)
+    } else {
+        let salt = rand::random_array().map_err(|e| {
+            error!("Failed to generated instance.img salt: {e}");
+            RebootReason::InternalError
+        })?;
+        let entry = EntryBody::new(&dice_inputs, &salt);
+        record_instance_entry(&entry, cdi_seal, &mut instance_img, header_index).map_err(|e| {
+            error!("Failed to get recorded entry in instance.img: {e}");
+            RebootReason::InternalError
+        })?;
+        (true, salt)
+    };
     trace!("Got salt from instance.img: {salt:x?}");
 
     let new_bcc_handover = if cfg!(dice_changes) {
@@ -207,6 +241,21 @@
     Ok(bcc_range)
 }
 
+fn ensure_dice_measurements_match_entry(
+    dice_inputs: &PartialInputs,
+    entry: &EntryBody,
+) -> Result<(), InstanceError> {
+    if entry.code_hash != dice_inputs.code_hash {
+        Err(InstanceError::RecordedCodeHashMismatch)
+    } else if entry.auth_hash != dice_inputs.auth_hash {
+        Err(InstanceError::RecordedAuthHashMismatch)
+    } else if entry.mode() != dice_inputs.mode {
+        Err(InstanceError::RecordedDiceModeMismatch)
+    } else {
+        Ok(())
+    }
+}
+
 /// Logs the given PCI error and returns the appropriate `RebootReason`.
 fn handle_pci_error(e: PciError) -> RebootReason {
     error!("{}", e);
diff --git a/virtualizationservice/Android.bp b/virtualizationservice/Android.bp
index fc7fcd2..0c39501 100644
--- a/virtualizationservice/Android.bp
+++ b/virtualizationservice/Android.bp
@@ -77,6 +77,9 @@
         "virtualizationservice_defaults",
     ],
     test_suites: ["general-tests"],
+    rustlibs: [
+        "libtempfile",
+    ],
     data: [
         ":test_rkp_cert_chain",
     ],
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index bbfb220..2fe14c0 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -39,7 +39,10 @@
 use openssl::x509::X509;
 use rand::Fill;
 use rkpd_client::get_rkpd_attestation_key;
-use rustutils::system_properties;
+use rustutils::{
+    system_properties,
+    users::{multiuser_get_app_id, multiuser_get_user_id},
+};
 use serde::Deserialize;
 use service_vm_comm::Response;
 use std::collections::{HashMap, HashSet};
@@ -385,7 +388,6 @@
         Ok(ParcelFileDescriptor::new(file))
     }
 
-    // TODO(b/294177871) Persist this Id, along with client uuid.
     fn allocateInstanceId(&self) -> binder::Result<[u8; 64]> {
         let mut id = [0u8; 64];
         id.try_fill(&mut rand::thread_rng())
@@ -393,6 +395,16 @@
             .or_service_specific_exception(-1)?;
         let uid = get_calling_uid();
         info!("Allocated a VM's instance_id: {:?}, for uid: {:?}", hex::encode(id), uid);
+        let state = &mut *self.state.lock().unwrap();
+        if let Some(sk_state) = &mut state.sk_state {
+            let user_id = multiuser_get_user_id(uid);
+            let app_id = multiuser_get_app_id(uid);
+            info!("Recording potential existence of state for (user_id={user_id}, app_id={app_id}");
+            if let Err(e) = sk_state.add_id(&id, user_id, app_id) {
+                error!("Failed to record the instance_id: {e:?}");
+            }
+        }
+
         Ok(id)
     }
 
diff --git a/virtualizationservice/src/maintenance.rs b/virtualizationservice/src/maintenance.rs
index 7fc2f37..0a367c5 100644
--- a/virtualizationservice/src/maintenance.rs
+++ b/virtualizationservice/src/maintenance.rs
@@ -15,7 +15,7 @@
 use android_hardware_security_secretkeeper::aidl::android::hardware::security::secretkeeper::{
     ISecretkeeper::ISecretkeeper, SecretId::SecretId,
 };
-use anyhow::Result;
+use anyhow::{Context, Result};
 use log::{error, info, warn};
 
 mod vmdb;
@@ -88,6 +88,13 @@
         }
     }
 
+    /// Record a new VM ID.
+    pub fn add_id(&mut self, vm_id: &VmId, user_id: u32, app_id: u32) -> Result<()> {
+        let user_id: i32 = user_id.try_into().context(format!("user_id {user_id} out of range"))?;
+        let app_id: i32 = app_id.try_into().context(format!("app_id {app_id} out of range"))?;
+        self.vm_id_db.add_vm_id(vm_id, user_id, app_id)
+    }
+
     /// Delete the VM IDs associated with Android user ID `user_id`.
     pub fn delete_ids_for_user(&mut self, user_id: i32) -> Result<()> {
         let vm_ids = self.vm_id_db.vm_ids_for_user(user_id)?;
diff --git a/virtualizationservice/src/maintenance/vmdb.rs b/virtualizationservice/src/maintenance/vmdb.rs
index bdff034..ce1e1e7 100644
--- a/virtualizationservice/src/maintenance/vmdb.rs
+++ b/virtualizationservice/src/maintenance/vmdb.rs
@@ -14,7 +14,7 @@
 
 //! Database of VM IDs.
 
-use anyhow::{Context, Result};
+use anyhow::{anyhow, Context, Result};
 use log::{debug, error, info, warn};
 use rusqlite::{params, params_from_iter, Connection, OpenFlags, Rows};
 use std::path::PathBuf;
@@ -29,6 +29,15 @@
 /// (Default value of `SQLITE_LIMIT_VARIABLE_NUMBER` for <= 3.32.0)
 const MAX_VARIABLES: usize = 999;
 
+/// Return the current time as milliseconds since epoch.
+fn db_now() -> u64 {
+    let now = std::time::SystemTime::now()
+        .duration_since(std::time::UNIX_EPOCH)
+        .unwrap_or(std::time::Duration::ZERO)
+        .as_millis();
+    now.try_into().unwrap_or(u64::MAX)
+}
+
 /// Identifier for a VM and its corresponding secret.
 pub type VmId = [u8; 64];
 
@@ -37,6 +46,8 @@
     conn: Connection,
 }
 
+struct RetryOnFailure(bool);
+
 impl VmIdDb {
     /// Connect to the VM ID database file held in the given directory, creating it if necessary.
     /// The second return value indicates whether a new database file was created.
@@ -49,8 +60,11 @@
             std::fs::create_dir(&db_path).context("failed to create {db_path:?}")?;
             info!("created persistent db dir {db_path:?}");
         }
-
         db_path.push(DB_FILENAME);
+        Self::new_at_path(db_path, RetryOnFailure(true))
+    }
+
+    fn new_at_path(db_path: PathBuf, retry: RetryOnFailure) -> Result<(Self, bool)> {
         let (flags, created) = if db_path.exists() {
             debug!("connecting to existing database {db_path:?}");
             (
@@ -69,15 +83,42 @@
                 true,
             )
         };
-        let mut result = Self {
-            conn: Connection::open_with_flags(db_path, flags)
+        let mut db = Self {
+            conn: Connection::open_with_flags(&db_path, flags)
                 .context(format!("failed to open/create DB with {flags:?}"))?,
         };
 
         if created {
-            result.init_tables().context("failed to create tables")?;
+            db.init_tables().context("failed to create tables")?;
+        } else {
+            // An existing .sqlite file may have an earlier schema.
+            match db.schema_version() {
+                Err(e) => {
+                    // Couldn't determine a schema version, so wipe and try again.
+                    error!("failed to determine VM DB schema: {e:?}");
+                    if retry.0 {
+                        // This is the first attempt, so wipe and retry.
+                        error!("resetting database file {db_path:?}");
+                        let _ = std::fs::remove_file(&db_path);
+                        return Self::new_at_path(db_path, RetryOnFailure(false));
+                    } else {
+                        // An earlier attempt at wiping/retrying has failed, so give up.
+                        return Err(anyhow!("failed to reset database file {db_path:?}"));
+                    }
+                }
+                Ok(0) => db.upgrade_tables_v0_v1().context("failed to upgrade schema v0 -> v1")?,
+                Ok(1) => {
+                    // Current version, no action needed.
+                }
+                Ok(version) => {
+                    // If the database looks like it's from a future version, leave it alone and
+                    // fail to connect to it.
+                    error!("database from the future (v{version})");
+                    return Err(anyhow!("database from the future (v{version})"));
+                }
+            }
         }
-        Ok((result, created))
+        Ok((db, created))
     }
 
     /// Delete the associated database file.
@@ -94,8 +135,63 @@
         }
     }
 
-    /// Create the database table and indices.
+    fn schema_version(&mut self) -> Result<i32> {
+        let version: i32 = self
+            .conn
+            .query_row("PRAGMA main.user_version", (), |row| row.get(0))
+            .context("failed to read pragma")?;
+        Ok(version)
+    }
+
+    /// Create the database table and indices using the current schema.
     fn init_tables(&mut self) -> Result<()> {
+        self.init_tables_v1()
+    }
+
+    /// Create the database table and indices using the v1 schema.
+    fn init_tables_v1(&mut self) -> Result<()> {
+        info!("creating v1 database schema");
+        self.conn
+            .execute(
+                "CREATE TABLE IF NOT EXISTS main.vmids (
+                     vm_id BLOB PRIMARY KEY,
+                     user_id INTEGER,
+                     app_id INTEGER,
+                     created INTEGER
+                 ) WITHOUT ROWID;",
+                (),
+            )
+            .context("failed to create table")?;
+        self.conn
+            .execute("CREATE INDEX IF NOT EXISTS main.vmids_user_index ON vmids(user_id);", [])
+            .context("Failed to create user index")?;
+        self.conn
+            .execute(
+                "CREATE INDEX IF NOT EXISTS main.vmids_app_index ON vmids(user_id, app_id);",
+                [],
+            )
+            .context("Failed to create app index")?;
+        self.conn
+            .execute("PRAGMA main.user_version = 1;", ())
+            .context("failed to declare version")?;
+        Ok(())
+    }
+
+    fn upgrade_tables_v0_v1(&mut self) -> Result<()> {
+        let _rows = self
+            .conn
+            .execute("ALTER TABLE main.vmids ADD COLUMN created INTEGER;", ())
+            .context("failed to alter table v0->v1")?;
+        self.conn
+            .execute("PRAGMA main.user_version = 1;", ())
+            .context("failed to set schema version")?;
+        Ok(())
+    }
+
+    /// Create the database table and indices using the v0 schema.
+    #[cfg(test)]
+    fn init_tables_v0(&mut self) -> Result<()> {
+        info!("creating v0 database schema");
         self.conn
             .execute(
                 "CREATE TABLE IF NOT EXISTS main.vmids (
@@ -119,13 +215,13 @@
     }
 
     /// Add the given VM ID into the database.
-    #[allow(dead_code)] // TODO(b/294177871): connect this up
     pub fn add_vm_id(&mut self, vm_id: &VmId, user_id: i32, app_id: i32) -> Result<()> {
+        let now = db_now();
         let _rows = self
             .conn
             .execute(
-                "REPLACE INTO main.vmids (vm_id, user_id, app_id) VALUES (?1, ?2, ?3);",
-                params![vm_id, &user_id, &app_id],
+                "REPLACE INTO main.vmids (vm_id, user_id, app_id, created) VALUES (?1, ?2, ?3, ?4);",
+                params![vm_id, &user_id, &app_id, &now],
             )
             .context("failed to add VM ID")?;
         Ok(())
@@ -177,16 +273,21 @@
     }
 }
 
+/// Current schema version.
+#[cfg(test)]
+const SCHEMA_VERSION: usize = 1;
+
+/// Create a new in-memory database for testing.
 #[cfg(test)]
 pub fn new_test_db() -> VmIdDb {
-    let mut db = VmIdDb { conn: Connection::open_in_memory().unwrap() };
-    db.init_tables().unwrap();
-    db
+    tests::new_test_db_version(SCHEMA_VERSION)
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
+    use std::io::Write;
+
     const VM_ID1: VmId = [1u8; 64];
     const VM_ID2: VmId = [2u8; 64];
     const VM_ID3: VmId = [3u8; 64];
@@ -201,6 +302,113 @@
     const APP_C: i32 = 70;
     const APP_UNKNOWN: i32 = 99;
 
+    pub fn new_test_db_version(version: usize) -> VmIdDb {
+        let mut db = VmIdDb { conn: Connection::open_in_memory().unwrap() };
+        match version {
+            0 => db.init_tables_v0().unwrap(),
+            1 => db.init_tables_v1().unwrap(),
+            _ => panic!("unexpected version {version}"),
+        }
+        db
+    }
+
+    fn show_contents(db: &VmIdDb) {
+        let mut stmt = db.conn.prepare("SELECT * FROM main.vmids;").unwrap();
+        let mut rows = stmt.query(()).unwrap();
+        while let Some(row) = rows.next().unwrap() {
+            println!("  {row:?}");
+        }
+    }
+
+    #[test]
+    fn test_schema_version0() {
+        let mut db0 = VmIdDb { conn: Connection::open_in_memory().unwrap() };
+        db0.init_tables_v0().unwrap();
+        let version = db0.schema_version().unwrap();
+        assert_eq!(0, version);
+    }
+
+    #[test]
+    fn test_schema_version1() {
+        let mut db1 = VmIdDb { conn: Connection::open_in_memory().unwrap() };
+        db1.init_tables_v1().unwrap();
+        let version = db1.schema_version().unwrap();
+        assert_eq!(1, version);
+    }
+
+    #[test]
+    fn test_schema_upgrade_v0_v1() {
+        let mut db = new_test_db_version(0);
+        let version = db.schema_version().unwrap();
+        assert_eq!(0, version);
+
+        // Manually insert a row before upgrade.
+        db.conn
+            .execute(
+                "REPLACE INTO main.vmids (vm_id, user_id, app_id) VALUES (?1, ?2, ?3);",
+                params![&VM_ID1, &USER1, APP_A],
+            )
+            .unwrap();
+
+        db.upgrade_tables_v0_v1().unwrap();
+        let version = db.schema_version().unwrap();
+        assert_eq!(1, version);
+
+        assert_eq!(vec![VM_ID1], db.vm_ids_for_user(USER1).unwrap());
+        show_contents(&db);
+    }
+
+    #[test]
+    fn test_corrupt_database_file() {
+        let db_dir = tempfile::Builder::new().prefix("vmdb-test-").tempdir().unwrap();
+        let mut db_path = db_dir.path().to_owned();
+        db_path.push(DB_FILENAME);
+        {
+            let mut file = std::fs::File::create(db_path).unwrap();
+            let _ = file.write_all(b"This is not an SQLite file!");
+        }
+
+        // Non-DB file should be wiped and start over.
+        let (mut db, created) =
+            VmIdDb::new(&db_dir.path().to_string_lossy()).expect("failed to replace bogus DB");
+        assert!(created);
+        db.add_vm_id(&VM_ID1, USER1, APP_A).unwrap();
+        assert_eq!(vec![VM_ID1], db.vm_ids_for_user(USER1).unwrap());
+    }
+
+    #[test]
+    fn test_non_upgradable_database_file() {
+        let db_dir = tempfile::Builder::new().prefix("vmdb-test-").tempdir().unwrap();
+        let mut db_path = db_dir.path().to_owned();
+        db_path.push(DB_FILENAME);
+        {
+            // Create an unrelated database that happens to apparently have a schema version of 0.
+            let (db, created) = VmIdDb::new(&db_dir.path().to_string_lossy()).unwrap();
+            assert!(created);
+            db.conn.execute("DROP TABLE main.vmids", ()).unwrap();
+            db.conn.execute("PRAGMA main.user_version = 0;", ()).unwrap();
+        }
+
+        // Should fail to open a database because the upgrade fails.
+        let result = VmIdDb::new(&db_dir.path().to_string_lossy());
+        assert!(result.is_err());
+    }
+
+    #[test]
+    fn test_database_from_the_future() {
+        let db_dir = tempfile::Builder::new().prefix("vmdb-test-").tempdir().unwrap();
+        {
+            let (mut db, created) = VmIdDb::new(&db_dir.path().to_string_lossy()).unwrap();
+            assert!(created);
+            db.add_vm_id(&VM_ID1, USER1, APP_A).unwrap();
+            // Make the database look like it's from a future version.
+            db.conn.execute("PRAGMA main.user_version = 99;", ()).unwrap();
+        }
+        // Should fail to open a database from the future.
+        let result = VmIdDb::new(&db_dir.path().to_string_lossy());
+        assert!(result.is_err());
+    }
+
     #[test]
     fn test_add_remove() {
         let mut db = new_test_db();
@@ -239,6 +447,7 @@
         assert_eq!(vec![VM_ID5], db.vm_ids_for_user(USER3).unwrap());
         assert_eq!(empty, db.vm_ids_for_user(USER_UNKNOWN).unwrap());
         assert_eq!(empty, db.vm_ids_for_app(USER1, APP_UNKNOWN).unwrap());
+        show_contents(&db);
     }
 
     #[test]
@@ -254,12 +463,13 @@
         // Manually insert a row with a VM ID that's the wrong size.
         db.conn
             .execute(
-                "REPLACE INTO main.vmids (vm_id, user_id, app_id) VALUES (?1, ?2, ?3);",
-                params![&[99u8; 60], &USER1, APP_A],
+                "REPLACE INTO main.vmids (vm_id, user_id, app_id, created) VALUES (?1, ?2, ?3, ?4);",
+                params![&[99u8; 60], &USER1, APP_A, &db_now()],
             )
             .unwrap();
 
         // Invalid row is skipped and remainder returned.
         assert_eq!(vec![VM_ID1, VM_ID2, VM_ID3], db.vm_ids_for_user(USER1).unwrap());
+        show_contents(&db);
     }
 }