  Property-based testing (PBT) is a technique for validating code against an
executable specification by automatically generating test-data. We present a
proof-theoretical reconstruction of this style of testing for relational
specifications and employ the Foundational Proof Certificate framework to
describe test generators. We do this by encoding certain kinds of ``proof
outlines'' as proof certificates that can describe various common generation
strategies in the PBT literature, ranging from random to exhaustive, including
their combination. We also address the shrinking of counterexamples as a first
step toward their explanation. Once generation is accomplished, the testing
phase is a standard logic programming search. After illustrating our techniques
on simple, first-order (algebraic) data structures, we lift it to data
structures containing bindings by using the $\lambda$-tree syntax approach to
encode bindings. The $\lambda$Prolog programming language can perform both
generating and checking of tests using this approach to syntax. We then further
extend PBT to specifications in a fragment of linear logic. Under consideration
in Theory and Practice of Logic Programming (TPLP).
