diff --git a/.gitignore b/.gitignore
index 6e3db8c..1d3b249 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,13 +1,14 @@
 *.pyc
 *.sw?
 *~
 .coverage
 .eggs/
 __pycache__
 *.egg-info/
 build/
 dist/
 version.txt
 /sql/createdb-stamp
 /sql/filldb-stamp
 .tox/
+.hypothesis/
\ No newline at end of file
diff --git a/Makefile.local b/Makefile.local
new file mode 100644
index 0000000..c163514
--- /dev/null
+++ b/Makefile.local
@@ -0,0 +1 @@
+TESTFLAGS=--hypothesis-profile=fast
diff --git a/conftest.py b/conftest.py
new file mode 100644
index 0000000..eb6de3d
--- /dev/null
+++ b/conftest.py
@@ -0,0 +1,6 @@
+from hypothesis import settings
+
+# define tests profile. Full documentation is at:
+# https://hypothesis.readthedocs.io/en/latest/settings.html#settings-profiles
+settings.register_profile("fast", max_examples=5, deadline=5000)
+settings.register_profile("slow", max_examples=20, deadline=5000)
diff --git a/debian/control b/debian/control
index 793f9b6..3abbfd7 100644
--- a/debian/control
+++ b/debian/control
@@ -1,47 +1,48 @@
 Source: swh-indexer
 Maintainer: Software Heritage developers <swh-devel@inria.fr>
 Section: python
 Priority: optional
 Build-Depends: debhelper (>= 9),
                dh-python (>= 2),
                python3-all,
                python3-chardet (>= 2.3.0~),
                python3-click,
+	       python3-hypothesis,
                python3-pytest,
                python3-pygments,
                python3-magic,
                python3-setuptools,
                python3-swh.core (>= 0.0.44~),
                python3-swh.model (>= 0.0.15~),
                python3-swh.objstorage (>= 0.0.13~),
                python3-swh.scheduler (>= 0.0.35~),
                python3-swh.storage (>= 0.0.102~),
                python3-vcversioner
 Standards-Version: 3.9.6
 Homepage: https://forge.softwareheritage.org/diffusion/78/
 
 Package: python3-swh.indexer.storage
 Architecture: all
 Depends: python3-swh.core (>= 0.0.44~),
          python3-swh.model (>= 0.0.15~),
          python3-swh.objstorage (>= 0.0.13~),
          python3-swh.scheduler (>= 0.0.35~),
          python3-swh.storage (>= 0.0.102~),
          ${misc:Depends},
          ${python3:Depends}
 Description: Software Heritage Content Indexer Storage
 
 Package: python3-swh.indexer
 Architecture: all
 Depends: python3-swh.scheduler (>= 0.0.14~),
          python3-swh.core (>= 0.0.44~),
          python3-swh.model (>= 0.0.15~),
          python3-swh.objstorage (>= 0.0.13~),
          python3-swh.scheduler (>= 0.0.35~),
          python3-swh.storage (>= 0.0.102~),
          python3-swh.indexer.storage (= ${binary:Version}),
          universal-ctags (>= 0.8~),
          fossology-nomossa (>= 3.1~),
          ${misc:Depends},
          ${python3:Depends}
 Description: Software Heritage Content Indexer
diff --git a/requirements-test.txt b/requirements-test.txt
index e079f8a..9b9e5f9 100644
--- a/requirements-test.txt
+++ b/requirements-test.txt
@@ -1 +1,2 @@
 pytest
+hypothesis
diff --git a/tox.ini b/tox.ini
index 70265ee..385a77f 100644
--- a/tox.ini
+++ b/tox.ini
@@ -1,17 +1,25 @@
 [tox]
 envlist=flake8,py3
 
 [testenv:py3]
 deps =
   .[testing]
   pytest-cov
   pifpaf
 commands =
-  pifpaf run postgresql -- pytest --cov=swh --cov-branch {posargs}
+  pifpaf run postgresql -- pytest --hypothesis-profile=fast --cov=swh --cov-branch {posargs}
+
+[testenv:py3-slow]
+deps =
+  .[testing]
+  pytest-cov
+  pifpaf
+commands =
+  pifpaf run postgresql -- pytest --hypothesis-profile=slow --cov=swh --cov-branch {posargs}
 
 [testenv:flake8]
 skip_install = true
 deps =
   flake8
 commands =
   {envpython} -m flake8