Comment by akoboldfrying

I think an interesting direction for benchmarking is to take inspiration from metamorphic testing. Metamorphic testing is a way of extending property-based testing (in which you ask the test framework itself to automatically generate many random (input, expected output) pairs to test for you, instead of manually writing individual tests yourself) to handle situations where (a) it's hard to independently come up with the right answer for a specific given input, but (b) relationships between inputs imply checkable relationships between outputs. For example, if you're trying to test your own implementation of sin(), it's hard to automatically generate random (input, expected output) test pairs without using a separate, trusted implementation of the sine function, which may not be available; but one thing you can easily do is check, for many different random x, that sin(x) == -sin(x+180).

How to apply this idea to benchmarks? Basically, look for simple transformations of the input instances that should yield simple transformations of the outputs -- in particular, outputs that, in a non-overfitted implementation, should take the same length of time to compute. For regexes, you could rotate a subset of non-magic characters in both the string and the regex (e.g., A -> B, B -> C, ..., Z -> A).

Another example would be to reverse both the string and the regex (taking care to handle parenthesised regex subexpressions correctly) -- unlike the previous one, it's not expected that the transformed instance will take the exact same length of time, but there should not be too much blow up.