1. code injection by string interpolation, like /@{[ do_evil() ]}/
2. code injection by regex, like /(?{ do_evil() })/
3. exponential time regexes with excessive backtracking, something like /((x*)*)*/ IIRC

This will compile a regex into an anonymous sub without executing it

use re qw(debug);
my $sub = eval "sub { m/$evil_re/ }";
[download]

the re debug will emit regex-opcodes for the regexes involved to STDERR

Final program:
   1: EVAL (4)
   4: EXACT <\n> (6)
   6: END (0)
[download]

the 1: EVAL here tells you that an EVAL was involved which you need to reject, you don't want embedded Perl code

$evil_re = "(?{ BEGIN { do_evil() } })";

with Keyword::Simple disabling BEGIN,END,... etc you won't risk that the compilation of the sub inside the eval will run any code (see here)

with Safe you'll be able to additionally disable a bunch of external commands. (see here)

For this to work you need to spawn an external command for each regex and capture STDERR, you can use this to also limit the maximal runtime.

Since your code looks a lot like a test suite, you might wanna use the TAP protocol anyway.

NB: No guaranties whatsoever!

HTH! :)