In actuality, if verifying that the output of your algorithm is valid
is an open problem itself, you obviously haven't proved that your
algorithm is correct (let alone the implementation), so perhaps you
should do that first.

For your integration algorithm, I'm pretty sure you would be able to
tell from the implementation what kind of choices the algorithm should
make so that you can bound the variation to a range within which
equality (up to a constant) can be tested.

Alternatively, you would probably have a guarantee that the system
should be able to evaluate arbitrary order derivatives of the
antiderivative returned, so you'd be able to check its series
expansion is a constant to some high order (assuming you're doing this
with some meromorphic function):

sage: f = some difficult function
sage: F = integrate(f,x); F       # random (underspecified, really)
...
sage: delta = diff(series(F(x),x=0,prec=11)(z),z) -
series(f(x),x=0,prec=10)(z)
sage: order(delta,z=0) >= 10
True

Of course it doesn't prove that the implementation is correct, but no
amount of testing would.