How can I test the integrity of a backup made with Backup (Deja Dup)?
Update Deja-dup to 24.x or latest release.
In later version of 23.x they have added integrity check feature.
Have a look this link. https://bugs.launchpad.net/deja-dup/+bug/1055356
After every backup, we make a small check to confirm we can restore a test file. And every two months, we make a more intensive check.
Restore the data, either in a VM or test home directory.
as bodhi.zazen explained, the best way would be to restore the backup on a test environment. Then, I suggest you to store somekind of checksum database of your backups after the restoration test