in reply to Re: How to create a Tree::DAG_Node tree with sorted hash elements
in thread How to create a Tree::DAG_Node tree with sorted hash elements

@ roboticus:

You are right, I should probably explain a bit about the background of my attempt. The Cisco firewalls we maintain at work have become bloated with several duplicate & overlapping rules due to mismanagement. Now a single firewall may have up to 900 ACL's. I want to sort & arrange them to identify rules that can be cleaned up. Most important need is to see which rules are sitting on top of smaller rules, some of them cover such wide access that they supersede quite a few other rules. So the visual representation of this supersets and subsets is very important.

Now, an ACL will contain an array of source & destination networks (may be host address X.X.X.X/32 or network address Y.Y.Y.Y/Z) and another array of service ports (tcp/udp ports). Now the examples I have used are just over-simplified ACL, with one source & destination address each, to be used for unit testing the rest of the code. I have managed to write the code to convert config files to array of hash of arrays(each ACL is a hash) and also the code to compare two ACL's. Now all that is left to do is put them in the right order and display the subsets and supersets.

Now back to your answer, you have summarized all the possibilities rather elegantly. I will not bother about case 5, I will treat such rules as unequal and yet insert them as peers to other rules (i.e, sue would be sister to bob & joe and I am not interested whether it can be split and inserted under the rest). I can think of no practical purpose to explore case 5 in my problem.

I did consider the root node conundrum and that is why I started with "permit ip any any" as the root node. However, I didn't imagine that such a rule would arrive as part of the rule hash. Perhaps I should write a special case for that.

Now that, all the obstructions are taken care of, what is the problem?

I am not really sure how to go about sorting an array of hashes. I have a procedure that compares two hashes and returns 1 or 0. 

# compares two Tree::DAG Nodes and returns positive if right (second) 
+argument is bigger
sub compare_nodes {
    my ($compare_node, $leaf_node) = @_;
    my $source_OK = compare_subnet($compare_node->{'attributes'}{'sour
+ce'},$leaf_node->{'attributes'}{'source'});
    my $destination_OK = compare_subnet($compare_node->{'attributes'}{
+'destination'},$leaf_node->{'attributes'}{'destination'});
    print "$compare_node->{'attributes'}{'original'} is a daughter of 
+$leaf_node->{'attributes'}{'original'}\n\n" if ($source_OK && $destin
+ation_OK);
    return 1 if ($source_OK && $destination_OK);
    return 0;
}

[download]

I feel I have to do something similar to overloading the "cmp" operator, but unsure of how to proceed. Any pointers would be of great help!

Also, I realize that if I get the sorting done, I have acheived most of my work, except that of grouping the rules into sets and subsets. At this point, I wonder if it is necessary to build a tree structure. Each comparison is an expensive task. For e.g, comparing hash1{sourcem,destn, portso} against hash2{sourcep,destq, portr} will require (mxp + nXq + oxr) calls to Net::IP->overlaps() procedure. By the time we finish sorting and ready to build tree, each ACL has already been compared every other ACL atleast once and all necessary information to group into sets & subsets have already been computed at least once (perhaps not remembered to be used later). So is there a better way to achieve my goal rather than build a N-ary tree? Should I code my own sort code with facility to group entries in to sets & subsets?Perhaps I am just being overly paranoid about repeating the comparison, deep inside I just want the task to be done. What is your opinion?

Apologies if I am confusing or misleading, I often tend to talk in a confusing manner.

  • Comment on Re^2: How to create a Tree::DAG_Node tree with sorted hash elements
  • Download Code

Replies are listed 'Best First'.
Re^3: How to create a Tree::DAG_Node tree with sorted hash elements
by roboticus (Chancellor) on Jun 20, 2011 at 17:49 UTC

    benny_vroom:

    Since you can ignore case 5, and it sounds like you're only interested in the case where some rules are possible subsets of others, then I think you can do it relatively easily. I think you could get away with sorting the list, like this:

    $ cat 910595.pl
#!/usr/bin/perl
use strict;
use warnings;
use Net::IP;

my @IPranges = map { new Net::IP($_) } <DATA>;

@IPranges = sort {
              # We want largest range first
              ($b->size() <=> $a->size())
              # use IP as next key
              || ($a->ip() cmp $b->ip())
            } @IPranges;

print join("\n", @IPranges), "\n";
__DATA__
1.2.3.0/24
1.2.0.0/16
192.168.0.0/16
192.168.4.0/24
192.168.4.192/26
127.0.0.1/32
10.0.0.0/8

$ ./910595.pl
10/8
1.2/16
192.168/16
1.2.3/24
192.168.4/24
192.168.4.192/26
127.0.0.1/32

    [download]

    Then you can probably use the rest of your code as-is to find the related rules.

    ...roboticus

    When your only tool is a hammer, all problems look like your thumb.

[reply]
[d/l]

      Roboticus,

      Note that the output is still not in the preferred order. The preferred order is:

      10/8
1.2/16
1.2.3/24
192.168/16
192.168.4/24
192.168.4.192/26
127.0.0.1/32

      [download]

      And this is happening because you are sorting based on network size first and if equal, going on to compare the IP address (which would simply say which one of either has a smaller decimal equivalent).

      10/8 may have a big network size, but it is not a supernet for 172.16/16.

      Also, my comparison is not that of single network address. I need to compare two hashes whose elements are network addresses. Anyways, I learnt that I can use custom expressions in place of cmp or <=> to perform sort operation.

      my $acl = {};
$acl->{source}  = [];            # array of Network address e.g, [10/8
+,172.16/16]
$acl->{dest}    = [];          # same as above
$acl->{original}= 'unknown';   # A string for original ACL e.g, permit
+ ip any 10/8

# After I create a hash I will store the hash reference in an array

push @acl_grp, \%acl;

# After populating the array of hash refs I want to sort them
# I would do something similar to this

foreach $acl ( sort compare @acl_grp ){
    print $acl->{original},"\n";
}

# compare function is coded as
#   return -1 if $b is a supernet of $a
#   return 1 if $a is a supernet of $b
#   return 0 for all other cases, mimicking the behaviour of <=>
sub compare($$){some code};

      [download]
      Assuming that above code works, I expect to get a list of ACL's sorted in order. Now my problem is, how can I indent them depending on whether above node is a super ACL or an unrelated ACL.
[reply]
[d/l]
[select]

        benny_vroom:

        The sorting was not intended to show the hierarchy of the nodes, but to give you an order to insert nodes with your original code that would give you the correct results. Given your original code, it would always work if (and only if) you inserted the larger ranges before the smaller ones.

        ...roboticus

        When your only tool is a hammer, all problems look like your thumb.

[reply]

In Section Seekers of Perl Wisdom