I would suggest breaking this down as follows:

1. Write a parser that transforms a generic ADD RULE statement into a useful data object. This could just be a hash/hashref or an object (see Moose) if you want more functionality. This will allow you to more easily determine if objects have similar content.
2. Read in the full rule set and treat it one rule at a time. This is definitely a TIMTOWTDI moment. I would enable slurp mode (local $/;, see $/ in perlvar) and then split the input into blocks and iterate over them (for (split /\n(?=ADD RULE$)/m) {...}), stashing the parsed objects into an array for later comparison. You could easily accomplish this a number of different ways.

This should give you plenty to get started.