It looks like you have a set of many-to-many relations: some hosts have multiple services with vulnerabilities, and some of the vulnerabilities show up on multiple hosts. You are given an input list that organizes the relations by host, and you want to create the "inverse" list, organized by vulnerability.

If that's correct, then I think you don't quite have the right data structure yet, and your loop is not giving proper treatment to hosts with multiple "Service:..." entries -- e.g. suppose host A has service problems X and Y, host B has just X, and host C has just Y. The way the OP code is written, the output list will have three "vulnerability" units, with a single host in each unit. If the idea is to group all hosts that have a given problem, you missed that goal. Something like the following might work better:

use strict;
use warnings;

$/ = "-------------\n";  # don't bother counting dashes

my %services; # keys will be service messages, values will be arrays o
+f host IPs

while (<>)   # put file name on command line (or pipe data to stdin)
{
    my @service_keys = ();
    my $current_service = '';
    my @lines = split /\n/; # step through line-by-line...
    my $host = '';

    while ( @lines )
    {
        $_ = pop @lines;    # ... from the bottom up
        next if /-------/;
        $current_service = "$_\n$current_service";

        if ( /^Service: / ) {  # top of a sub-record
            push @service_keys, $current_service;
            $current_service = '';
        }
        elsif ( /^Host: +([\d.]+)/ ) { # top of record
            $host = $1;
            push @{$services{$_}}, $host for ( @service_keys );
            last;
        }
    }
    warn "Record $. did not contain a host IP\n"  # (update: die is to
+o harsh here)
        if ( $host eq '' );  # just in case...
}

# %services is now HoA; let's suppose we want
# to order the output by "severity" (high ... low)
# but within any severity level, order doesn't matter:

for my $level ( qw/High Moderate Low/ )  # any others?
{
    for my $service ( grep /Severity: $level/, keys %services )
    {
        print "-----------------\n\nVulnerability:\n\n$service\nHosts:
+\n";
        print join "\n", @{$services{$service}}, "\n";
    }
}
[download]

This seems to work, but I only tried it on the sample of input you provided, which didn't have any cases of two hosts with the same problem.

One thing you might need to be careful about is variable white-space in the input service reports -- e.g. if a given message is reported on various hosts with differences in blank lines or trailing spaces, it will show up as multiple keys in the main hash. But when you start by reading a whole record at a time like you're doing, it's easy to start each iteration by normalizing white-space, if necessary.

(update: when I fudged an extra "Host:" entry to try for two hosts with the same problem, I discovered that the last record in the input file needs to end with "------\n", or else the "split /\n/" needs to be  split /\n/,$_,-1, to preserve trailing newlines, if any; and/or you need to muck with normalizing whitespace anyway.)