diff --git a/swh/storage/tests/algos/test_snapshot.py b/swh/storage/tests/algos/test_snapshot.py
--- a/swh/storage/tests/algos/test_snapshot.py
+++ b/swh/storage/tests/algos/test_snapshot.py
@@ -73,7 +73,15 @@
     ret = {
         'branches': branches,
     }
-    ret['id'] = identifier_to_bytes(snapshot_identifier(ret))
+    while True:
+        try:
+            id_ = snapshot_identifier(ret)
+        except ValueError as e:
+            for (source, target) in e.args[1]:
+                ret[source] = draw(branch_targets(only_objects=True))
+        else:
+            break
+    ret['id'] = identifier_to_bytes(id_)
     return ret