Avoid reusing disposable VM names for some predefined time

[DemiMarie]

How to file a helpful issue

The problem you're addressing (if any)

Disposable VM names can be reused, creating a risk of VM name use after free.

The solution you'd like

Do not reuse disposable VM names for some predefined time, long enough for any timeouts to expire.

The value to a user, and who that user might be

Users will be able to write programs that need to create a disposable VM and run commands in it without fear of invoking commands in the wrong VM.

[alimirjamali]

This can be achieved by modifying VMCollection.get_new_unused_dispid function of qubes.app library and adding a dispid pool. I did something like this:

diff --git a/qubes/app.py b/qubes/app.py
index f85b4848..76ec4e02 100644
--- a/qubes/app.py
+++ b/qubes/app.py
@@ -427,6 +427,7 @@ class VMCollection:
     def __init__(self, app):
         self.app = app
         self._dict = {}
+        self._dispid_pool = list()
 
     def close(self):
         del self.app
@@ -579,11 +580,14 @@ class VMCollection:
                 return i
         raise LookupError("Cannot find unused qid!")
 
+
     def get_new_unused_dispid(self):
-        for _ in range(int(qubes.config.max_dispid ** 0.5)):
-            dispid = random.SystemRandom().randrange(qubes.config.max_dispid)
-            if not any(getattr(vm, 'dispid', None) == dispid for vm in self):
-                return dispid
+        if len(self._dispid_pool) == 0:
+            self._dispid_pool = [_ for _ in range(qubes.config.max_dispid)]
+            random.shuffle(self._dispid_pool)
+        dispid = self._dispid_pool.pop(0)
+        if not any(getattr(vm, 'dispid', None) == dispid for vm in self):
+            return dispid
         raise LookupError((
                               'https://xkcd.com/221/',
                               'http://dilbert.com/strip/2001-10-25')[

It will repeat the pool range after it consumed all 10000 possibilities set by qubes.config.max_dispid. This might be necessary for builder servers. But I believe that the first 100 possibilities should be shuffled independent of the rest. Since ordinary users might not need more than that in each of their sessions. Or maybe give up the shuffling entirely. Starting form 1 and go up.

Kindly advise if this is OK and what is the final desired behaviour. So I could make a pull request if this is acceptable.

[marmarek]

This approach still theoretically allows quick reuse in the unlucky situation, if some dispid in the first shuffled pool is near its end, and then near beginning in the next shuffled pool. A better solution would be trying to enforce not reusing specific dispid for some time - at least 5 min, but to be safer maybe 1h would be even better. This could be done by keeping a dict of recently used dispid with timestamps when they were last used (dispvm destroy time) and treat recently used dispid similar as currently used ones.

Or maybe give up the shuffling entirely. Starting form 1 and go up.

No, this leaks information about uptime / usage pattern too easily and is especially a concern for Whonix qubes.

In any case, I don't think preventing reuse strictly until reboot is a good idea, I'll update the issue in a moment.

[alimirjamali]

In any case, I don't think preventing reuse strictly until reboot is a good idea, I'll update the issue in a moment.

There could be another approach. A shuffled pool of [1..100] for start. Once it is consumed, a new shuffled pool of [101..1000], then [1001..10000] and so on until we exceed qubes.config.max_dispid. But theoretically we could go up to 536870912.

OK. I have a working prototype with timestamp dictionary. Delta time till possible reuse is set to one day. Will perform few tests and post the diff.

[alimirjamali]

Ok. Here is the suggested diff. No reuse for one day. 24 hours is currently hard coded but could be moved to qubes.config. And I should see if a test could be properly written

diff --git a/qubes/app.py b/qubes/app.py
index f85b4848..4eaeacae 100644
--- a/qubes/app.py
+++ b/qubes/app.py
@@ -31,6 +31,7 @@ import os
 import random
 import sys
 import time
+import datetime
 import traceback
 import uuid
 from contextlib import suppress
@@ -427,6 +428,8 @@ class VMCollection:
     def __init__(self, app):
         self.app = app
         self._dict = {}
+        ''' Dictionary of recently used Disposables: dispid -> destroy time'''
+        self._recent_disps = {}
 
     def close(self):
         del self.app
@@ -537,6 +540,8 @@ class VMCollection:
                 # already undefined
                 pass
         del self._dict[vm.qid]
+        if getattr(vm, 'dispid', None):
+            self._recent_disps[getattr(vm, 'dispid')] = datetime.datetime.now()
         self.app.fire_event('domain-delete', vm=vm)
 
     def __contains__(self, key):
@@ -583,6 +588,16 @@ class VMCollection:
         for _ in range(int(qubes.config.max_dispid ** 0.5)):
             dispid = random.SystemRandom().randrange(qubes.config.max_dispid)
             if not any(getattr(vm, 'dispid', None) == dispid for vm in self):
+                if dispid in self._recent_disps:
+                    delta = (datetime.datetime.now() - self_recent_disps[dispid])
+                    if delta.total_seconds() / 60 / 60 / 24 < 1:
+                        ''' Less than one day has passed. Do not risk it '''
+                        continue
+                    else:
+                        ''' Over one day has passed. Reuse dispid '''
+                        del self._recent_disps[dispid]
+                        self.app.log.debug('Reused dispid {} after {} hours'.format(
+                            dispid, delta / 60 / 60))
                 return dispid
         raise LookupError((
                               'https://xkcd.com/221/',

[rustybird]

@alimirjamali time.monotonic() instead of datetime.datetime.now() would have the advantage of not being affected by clock changes

[alimirjamali]

@alimirjamali time.monotonic() instead of datetime.datetime.now() would have the advantage of not being affected by clock changes

Excellent suggestion. I forgot about that. Or datetime.datetime.utcnow. The overall hypothetical max size of self._recent_disps will be 800KB for 100000 recent dispids.

[alimirjamali]

PR Submitted