Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/util/PcapPacketUtils.java

   1 package edu.uci.iotproject.util;
   2
   3 import edu.uci.iotproject.trafficreassembly.layer3.Conversation;
   4 import edu.uci.iotproject.analysis.PcapPacketPair;
   5 import edu.uci.iotproject.analysis.TcpConversationUtils;
   6 import edu.uci.iotproject.analysis.TriggerTrafficExtractor;
   7 import org.apache.commons.math3.stat.clustering.Cluster;
   8 import org.pcap4j.core.PcapPacket;
   9 import org.pcap4j.packet.EthernetPacket;
  10 import org.pcap4j.packet.IpV4Packet;
  11 import org.pcap4j.packet.TcpPacket;
  12 import org.pcap4j.util.MacAddress;
  13
  14 import java.util.*;
  15
  16 /**
  17  * Utility methods for inspecting {@link PcapPacket} properties.
  18  *
  19  * @author Janus Varmarken {@literal <jvarmark@uci.edu>}
  20  * @author Rahmadi Trimananda {@literal <rtrimana@uci.edu>}
  21  */
  22 public final class PcapPacketUtils {
  23
  24     /**
  25      * This is the threshold value for a signature's number of members
  26      * If after a merging the number of members of a signature falls below this threshold, then we can boldly
  27      * get rid of that signature.
  28      */
  29     private static final int SIGNATURE_MERGE_THRESHOLD = 5;
  30
  31     /**
  32      * This is an overlap counter (we consider overlaps between signatures if it happens more than once)
  33      */
  34     private static int mOverlapCounter = 0;
  35
  36
  37     /**
  38      * Gets the source address of the Ethernet part of {@code packet}.
  39      * @param packet The packet for which the Ethernet source address is to be extracted.
  40      * @return The source address of the Ethernet part of {@code packet}.
  41      */
  42     public static MacAddress getEthSrcAddr(PcapPacket packet) {
  43         return getEthernetPacketOrThrow(packet).getHeader().getSrcAddr();
  44     }
  45
  46     /**
  47      * Gets the destination address of the Ethernet part of {@code packet}.
  48      * @param packet The packet for which the Ethernet destination address is to be extracted.
  49      * @return The destination address of the Ethernet part of {@code packet}.
  50      */
  51     public static MacAddress getEthDstAddr(PcapPacket packet) {
  52         return getEthernetPacketOrThrow(packet).getHeader().getDstAddr();
  53     }
  54
  55     /**
  56      * Determines if a given {@link PcapPacket} wraps a {@link TcpPacket}.
  57      * @param packet The {@link PcapPacket} to inspect.
  58      * @return {@code true} if {@code packet} wraps a {@link TcpPacket}, {@code false} otherwise.
  59      */
  60     public static boolean isTcp(PcapPacket packet) {
  61         return packet.get(TcpPacket.class) != null;
  62     }
  63
  64     /**
  65      * Gets the source IP (in decimal format) of an IPv4 packet.
  66      * @param packet The packet for which the IPv4 source address is to be extracted.
  67      * @return The decimal representation of the source IP of {@code packet} <em>iff</em> {@code packet} wraps an
  68      *         {@link IpV4Packet}.
  69      * @throws NullPointerException if {@code packet} does not encapsulate an {@link IpV4Packet}.
  70      */
  71     public static String getSourceIp(PcapPacket packet) {
  72         return getIpV4PacketOrThrow(packet).getHeader().getSrcAddr().getHostAddress();
  73     }
  74
  75     /**
  76      * Gets the destination IP (in decimal format) of an IPv4 packet.
  77      * @param packet The packet for which the IPv4 source address is to be extracted.
  78      * @return The decimal representation of the destination IP of {@code packet} <em>iff</em> {@code packet} wraps an
  79      *         {@link IpV4Packet}.
  80      * @throws NullPointerException if {@code packet} does not encapsulate an {@link IpV4Packet}.
  81      */
  82     public static String getDestinationIp(PcapPacket packet) {
  83         return getIpV4PacketOrThrow(packet).getHeader().getDstAddr().getHostAddress();
  84     }
  85
  86     /**
  87      * Gets the source port of a TCP packet.
  88      * @param packet The packet for which the source port is to be extracted.
  89      * @return The source port of the {@link TcpPacket} encapsulated by {@code packet}.
  90      * @throws IllegalArgumentException if {@code packet} does not encapsulate a {@link TcpPacket}.
  91      */
  92     public static int getSourcePort(PcapPacket packet) {
  93         TcpPacket tcpPacket = packet.get(TcpPacket.class);
  94         if (tcpPacket == null) {
  95             throw new IllegalArgumentException("not a TCP packet");
  96         }
  97         return tcpPacket.getHeader().getSrcPort().valueAsInt();
  98     }
  99
 100     /**
 101      * Gets the destination port of a TCP packet.
 102      * @param packet The packet for which the destination port is to be extracted.
 103      * @return The destination port of the {@link TcpPacket} encapsulated by {@code packet}.
 104      * @throws IllegalArgumentException if {@code packet} does not encapsulate a {@link TcpPacket}.
 105      */
 106     public static int getDestinationPort(PcapPacket packet) {
 107         TcpPacket tcpPacket = packet.get(TcpPacket.class);
 108         if (tcpPacket == null) {
 109             throw new IllegalArgumentException("not a TCP packet");
 110         }
 111         return tcpPacket.getHeader().getDstPort().valueAsInt();
 112     }
 113
 114     /**
 115      * Helper method to determine if the given combination of IP and port matches the source of the given packet.
 116      * @param packet The packet to check.
 117      * @param ip The IP to look for in the ip.src field of {@code packet}.
 118      * @param port The port to look for in the tcp.port field of {@code packet}.
 119      * @return {@code true} if the given ip+port match the corresponding fields in {@code packet}.
 120      */
 121     public static boolean isSource(PcapPacket packet,         String ip, int port) {
 122         IpV4Packet ipPacket = Objects.requireNonNull(packet.get(IpV4Packet.class));
 123         // For now we only support TCP flows.
 124         TcpPacket tcpPacket = Objects.requireNonNull(packet.get(TcpPacket.class));
 125         String ipSrc = ipPacket.getHeader().getSrcAddr().getHostAddress();
 126         int srcPort = tcpPacket.getHeader().getSrcPort().valueAsInt();
 127         return ipSrc.equals(ip) && srcPort == port;
 128     }
 129
 130     /**
 131      * Helper method to determine if the given combination of IP and port matches the destination of the given packet.
 132      * @param packet The packet to check.
 133      * @param ip The IP to look for in the ip.dst field of {@code packet}.
 134      * @param port The port to look for in the tcp.dstport field of {@code packet}.
 135      * @return {@code true} if the given ip+port match the corresponding fields in {@code packet}.
 136      */
 137     public static boolean isDestination(PcapPacket packet, String ip, int port) {
 138         IpV4Packet ipPacket = Objects.requireNonNull(packet.get(IpV4Packet.class));
 139         // For now we only support TCP flows.
 140         TcpPacket tcpPacket = Objects.requireNonNull(packet.get(TcpPacket.class));
 141         String ipDst = ipPacket.getHeader().getDstAddr().getHostAddress();
 142         int dstPort = tcpPacket.getHeader().getDstPort().valueAsInt();
 143         return ipDst.equals(ip) && dstPort == port;
 144     }
 145
 146     /**
 147      * Checks if the source IP address of the {@link IpV4Packet} contained in {@code packet} is a local address, i.e.,
 148      * if it pertains to subnet 10.0.0.0/8, 172.16.0.0/16, or 192.168.0.0/16.
 149      * @param packet The packet for which the source IP address is to be examined.
 150      * @return {@code true} if {@code packet} wraps a {@link IpV4Packet} for which the source IP address is a local IP
 151      *         address, {@code false} otherwise.
 152      * @throws NullPointerException if {@code packet} does not encapsulate an {@link IpV4Packet}.
 153      */
 154     public static boolean isSrcIpLocal(PcapPacket packet) {
 155         return getIpV4PacketOrThrow(packet).getHeader().getSrcAddr().isSiteLocalAddress();
 156     }
 157
 158     /**
 159      * Checks if the destination IP address of the {@link IpV4Packet} contained in {@code packet} is a local address,
 160      * i.e., if it pertains to subnet 10.0.0.0/8, 172.16.0.0/16, or 192.168.0.0/16.
 161      * @param packet The packet for which the destination IP address is to be examined.
 162      * @return {@code true} if {@code packet} wraps a {@link IpV4Packet} for which the destination IP address is a local
 163      *         IP address, {@code false} otherwise.
 164      * @throws NullPointerException if {@code packet} does not encapsulate an {@link IpV4Packet}.
 165      */
 166     public static boolean isDstIpLocal(PcapPacket packet) {
 167         return getIpV4PacketOrThrow(packet).getHeader().getDstAddr().isSiteLocalAddress();
 168     }
 169
 170     /**
 171      * Checks if {@code packet} wraps a TCP packet that has the SYN flag set.
 172      * @param packet A {@link PcapPacket} that is suspected to contain a {@link TcpPacket} for which the SYN flag is set.
 173      * @return {@code true} <em>iff</em> {@code packet} contains a {@code TcpPacket} for which the SYN flag is set,
 174      *         {@code false} otherwise.
 175      */
 176     public static boolean isSyn(PcapPacket packet) {
 177         TcpPacket tcp = packet.get(TcpPacket.class);
 178         return tcp != null && tcp.getHeader().getSyn();
 179     }
 180
 181     /**
 182      * Checks if {@code packet} wraps a TCP packet th        at has the ACK flag set.
 183      * @param packet A {@link PcapPacket} that is suspected to contain a {@link TcpPacket} for which the ACK flag is set.
 184      * @return {@code true} <em>iff</em> {@code packet} contains a {@code TcpPacket} for which the ACK flag is set,
 185      *         {@code false} otherwise.
 186      */
 187     public static boolean isAck(PcapPacket packet) {
 188         TcpPacket tcp = packet.get(TcpPacket.class);
 189         return tcp != null && tcp.getHeader().getAck();
 190     }
 191
 192     /**
 193      * Transform a {@code Cluster} of {@code PcapPacketPair} objects into a {@code List} of {@code List} of
 194      * {@code PcapPacket} objects.
 195      * @param cluster A {@link Cluster} of {@link PcapPacketPair} objects that needs to be transformed.
 196      * @return A {@link List} of {@link List} of {@link PcapPacket} objects as the result of the transformation.
 197      */
 198     public static List<List<PcapPacket>> clusterToListOfPcapPackets(Cluster<PcapPacketPair> cluster) {
 199         List<List<PcapPacket>> ppListOfList = new ArrayList<>();
 200         for (PcapPacketPair ppp: cluster.getPoints()) {
 201             // Create a list of PcapPacket objects (list of two members).
 202             List<PcapPacket> ppList = new ArrayList<>();
 203             ppList.add(ppp.getFirst());
 204             if(ppp.getSecond().isPresent())
 205                 ppList.add(ppp.getSecond().get());
 206             else
 207                 ppList.add(null);
 208             // Create a list of list of PcapPacket objects.
 209             ppListOfList.add(ppList);
 210         }
 211         // Sort the list of lists based on the first packet's timestamp!
 212         Collections.sort(ppListOfList, (p1, p2) -> p1.        get(0).getTimestamp().compareTo(p2.get(0).getTimestamp()));
 213         return ppListOfList;
 214     }
 215
 216     /**
 217      * Merge signatures in {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects.
 218      * We cross-check these with {@code List} of {@code Conversation} objects to see
 219      * if two {@code List} of {@code PcapPacket} objects actually belong to the same {@code Conversation}.
 220      * @param signatures A {@link List} of {@link List} of {@link List} of
 221      *          {@link PcapPacket} objects that needs to be checked and merged.
 222      * @param conversations A {@link List} of {@link Conversation} objects as reference for merging.
 223      * @return A {@link List} of {@link List} of {@link List} of
 224      *          {@link PcapPacket} objects as the result of the merging.
 225      */
 226     public static List<List<List<PcapPacket>>>
 227             mergeSignatures(List<List<List<PcapPacket>>> signatures, List<Conversation> conversations) {
 228
 229         // TODO: THIS IS NOT A DEEP COPY; IT BASICALLY CREATES A REFERENCE TO THE SAME LIST OBJECT
 230         // List<List<List<PcapPacket>>> copySignatures = new ArrayList<>(signatures);
 231         // Make a deep copy first.
 232         List<List<List<PcapPacket>>> copySignatures = new ArrayList<>();
 233         listDeepCopy(copySignatures, signatures);
 234         // Traverse and look into the pairs of signatures.
 235         for (int first = 0; first < signatures.size(); first++) {
 236             List<List<PcapPacket>> firstList = signatures.get(first);
 237             for (int second = first+1; second < signatures.size(); second++) {
 238                 int maxSignatureEl = 0; // Number of maximum signature elements.
 239                 List<List<PcapPacket>> secondList = signatures.get(second);
 240                 int initialSecondListMembers = secondList.size();
 241                 // Iterate over the signatures in the first list.
 242                 for (List<PcapPacket> signature : firstList) {
 243                     signature.removeIf(el -> el == null); // Clean up null elements.
 244                     // Return the Conversation that the signature is part of.
 245                     Conversation conv = TcpConversationUtils.returnConversation(signature, conversations);
 246                     // Find the element of the second list that is a match for that Conversation.
 247                     for (List<PcapPacket> ppList : secondList) {
 248                         ppList.removeIf(el -> el == null); // Clean up null elements.
 249                         // Check if they are part of a Conversation and are adjacent to the first signature.
 250                         // If yes then merge into the first list.
 251                         TcpConversationUtils.SignaturePosition position =
 252                                 TcpConversationUtils.isPartOfConversationAndAdjacent(signature, ppList, conv);
 253                         if (position == TcpConversationUtils.SignaturePosition.LEFT_ADJACENT) {
 254                             // Merge to the left side of the first signature.
 255                             ppList.addAll(signature);
 256                             signature = ppList;
 257                             maxSignatureEl = signature.size() > maxSignatureEl ? signature.size() : maxSignatureEl;
 258                             secondList.remove(ppList); // Remove as we merge.
 259                             break;
 260                         } else if (position == TcpConversationUtils.SignaturePosition.RIGHT_ADJACENT) {
 261                             // Merge to the right side of the first signature.
 262                             signature.addAll(ppList);
 263                             maxSignatureEl = signature.size() > maxSignatureEl ? signature.size() : maxSignatureEl;
 264                             secondList.remove(ppList); // Remove as we merge.
 265                             break;
 266                         } // TcpConversationUtils.SignaturePosition.NOT_ADJACENT.
 267                     }
 268                 }
 269                 // Call it a successful merging if there are only less than 5 elements from the second list that
 270                 // cannot be merged.
 271                 if (secondList.size() < SIGNATURE_MERGE_THRESHOLD) {
 272                     // Prune the unsuccessfully merged signatures (i.e., these will have size() < maxSignatureEl).
 273                     final int maxNumOfEl = maxSignatureEl;
 274                     // TODO: DOUBLE CHECK IF WE REALLY NEED TO PRUNE FAILED BINDINGS
 275                     // TODO: SOMETIMES THE SEQUENCES ARE JUST INCOMPLETE
 276                     // TODO: AND BOTH THE COMPLETE AND INCOMPLETE SEQUENCES ARE VALID SIGNATURES!
 277                     firstList.removeIf(el -> el.size() < maxNumOfEl);
 278                     // Remove the merged set of signatures when successful.
 279                     signatures.remove(secondList);
 280                 } else if (secondList.size() < initialSecondListMembers) {
 281                     // If only some of the signatures from the second list are merged, this means UNSUCCESSFUL merging.
 282                     // Return the original copy of the signatures object.
 283                     return copySignatures;
 284                 }
 285             }
 286         }
 287         return signatures;
 288     }
 289
 290     /**
 291      * Deep copy to create an entirely new {@link List} of {@link List} of {@link List} of {@link PcapPacket} objects.
 292      * @param destList A {@link List} of {@link List} of {@link List} of
 293      *          {@link PcapPacket} objects that will be the final container of the deep copy
 294      * @param sourceList A {@link List} of {@link List} of {@link List} of
 295      *          {@link PcapPacket} objects that will be the source of the deep copy.
 296      */
 297     private static void listDeepCopy(List<List<List<PcapPacket>>> destList, List<List<List<PcapPacket>>> sourceList) {
 298
 299         for(List<List<PcapPacket>> llPcapPacket : sourceList) {
 300             List<List<PcapPacket>> tmpListOfList = new ArrayList<>();
 301             for(List<PcapPacket> lPcapPacket : llPcapPacket) {
 302                 List<PcapPacket> tmpList = new ArrayList<>();
 303                 for(PcapPacket pcapPacket : lPcapPacket) {
 304                     tmpList.add(pcapPacket);
 305                 }
 306                 tmpListOfList.add(tmpList);
 307             }
 308             destList.add(tmpListOfList);
 309         }
 310     }
 311
 312     /**
 313      * Sort the signatures in the {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects.
 314      * The purpose of this is to sort the order of signatures in the signature list. For detection purposes, we need
 315      * to know if one signature occurs earlier/later in time with respect to the other signatures for more confidence
 316      * in detecting the occurrence of an event.
 317      * @param signatures A {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects that needs sorting.
 318      *                   We assume that innermost {@code List} of {@code PcapPacket} objects have been sorted ascending
 319      *                   by timestamps. By the time we use this method, we should have sorted it when calling the
 320      *                   {@code clusterToListOfPcapPackets} method.
 321      * @return A sorted {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects.
 322      */
 323     public static List<List<List<PcapPacket>>> sortSignatures(List<List<List<PcapPacket>>> signatures) {
 324         // TODO: This is the simplest solution!!! Might not cover all corner cases.
 325         // TODO: Sort the list of lists based on the first packet's timestamps!
 326 //        Collections.sort(signatures, (p1, p2) -> {
 327 //            //return p1.get(0).get(0).getTimestamp().compareTo(p2.get(0).get(0).getTimestamp());
 328 //            int compare = p1.get(0).get(0).getTimestamp().compareTo(p2.get(0).get(0).getTimestamp());
 329 //            return compare;
 330 //        });
 331         // TODO: The following is a more complete solution that covers corner cases.
 332         // Sort the list of lists based on one-to-one comparison between timestamps of signatures on both lists.
 333         // This also takes into account the fact that the number of signatures in the two lists could be different.
 334         // Additionally, this code forces the comparison between two signatures only if they occur in the
 335         // INCLUSION_WINDOW_MILLIS window; otherwise, it tries to find the right pair of signatures in the time window.
 336         Collections.sort(signatures, (p1, p2) -> {
 337             int compare = 0;
 338             int comparePrev = 0;
 339             int count1 = 0;
 340             int count2 = 0;
 341             // Need to make sure that both are not out of bound!
 342             while (count1 + 1 < p1.size() && count2 + 1 < p2.size()) {
 343                 long timestamp1 = p1.get(count1).get(0).getTimestamp().toEpochMilli();
 344                 long timestamp2 = p2.get(count2).get(0).getTimestamp().toEpochMilli();
 345                 // The two timestamps have to be within a 15-second window!
 346                 if (Math.abs(timestamp1 - timestamp2) < TriggerTrafficExtractor.INCLUSION_WINDOW_MILLIS) {
 347                     // If these two are within INCLUSION_WINDOW_MILLIS window then compare!
 348                     compare = p1.get(count1).get(0).getTimestamp().compareTo(p2.get(count2).get(0).getTimestamp());
 349 //                    if (comparePrev != 0) { // First time since it is 0
 350 //                        if (Integer.signum(compare) != Integer.signum(comparePrev)) {
 351 //                            // Throw an exception if the order of the two signatures is not consistent,
 352 //                            // E.g., 111, 222, 333 in one occassion and 222, 333, 111 in the other.
 353 //                            throw new Error("OVERLAP WARNING: " + "" +
 354 //                                    "Please remove one of the sequences: " +
 355 //                                    p1.get(0).get(0).length() + "... OR " +
 356 //                                    p2.get(0).get(0).length() + "...");
 357 //                        }
 358 //                    }
 359                     overlapChecking(compare, comparePrev, p1.get(count1), p2.get(count2));
 360                     comparePrev = compare;
 361                     count1++;
 362                     count2++;
 363                 } else {
 364                     // If not within INCLUSION_WINDOW_MILLIS window then find the correct pair
 365                     // by incrementing one of them.
 366                     if (timestamp1 < timestamp2)
 367                         count1++;
 368                     else
 369                         count2++;
 370                 }
 371             }
 372             return compare;
 373         });
 374         return signatures;
 375     }
 376
 377     /**
 378      * Checks for overlapping between two packet sequences.
 379      * @param compare Current comparison value between packet sequences p1 and p2
 380      * @param comparePrev Previous comparison value between packet sequences p1 and p2
 381      * @param sequence1 The packet sequence ({@link List} of {@link PcapPacket} objects).
 382      * @param sequence2 The packet sequence ({@link List} of {@link PcapPacket} objects).
 383      */
 384     private static void overlapChecking(int compare, int comparePrev, List<PcapPacket> sequence1, List<PcapPacket> sequence2) {
 385
 386         // Check if p1 occurs before p2 but both have same overlap
 387         if (comparePrev != 0) { // First time since it is 0
 388             if (Integer.signum(compare) != Integer.signum(comparePrev)) {
 389                 // Throw an exception if the order of the two signatures is not consistent,
 390                 // E.g., 111, 222, 333 in one occassion and 222, 333, 111 in the other.
 391                 throw new Error("OVERLAP WARNING: " + "" +
 392                         "Two sequences have some overlap. Please remove one of the sequences: " +
 393                         sequence1.get(0).length() + "... OR " +
 394                         sequence2.get(0).length() + "...");
 395             }
 396         }
 397         // Check if p1 is longer than p2 and p2 occurs during the occurrence of p1
 398         int lastIndexOfSequence1 = sequence1.size() - 1;
 399         int lastIndexOfSequence2 = sequence2.size() - 1;
 400         int compareLast =
 401                 sequence1.get(lastIndexOfSequence1).getTimestamp().compareTo(sequence2.get(lastIndexOfSequence2).getTimestamp());
 402         // Check the signs of compare and compareLast
 403         if ((compare <= 0 && compareLast > 0) ||
 404             (compareLast <= 0 && compare > 0)) {
 405             mOverlapCounter++;
 406             // TODO: Probably not the best approach but we consider overlap if it happens more than once
 407             if (mOverlapCounter > 1) {
 408                 throw new Error("OVERLAP WARNING: " + "" +
 409                         "One sequence is in the other. Please remove one of the sequences: " +
 410                         sequence1.get(0).length() + "... OR " +
 411                         sequence2.get(0).length() + "...");
 412             }
 413         }
 414
 415     }
 416
 417     /**
 418      * Gets the {@link IpV4Packet} contained in {@code packet}, or throws a {@link NullPointerException} if
 419      * {@code packet} does not contain an {@link IpV4Packet}.
 420      * @param packet A {@link PcapPacket} that is expected to contain an {@link IpV4Packet}.
 421      * @return The {@link IpV4Packet} contained in {@code packet}.
 422      * @throws NullPointerException if {@code packet} does not encapsulate an {@link IpV4Packet}.
 423      */
 424     private static IpV4Packet getIpV4PacketOrThrow(PcapPacket packet) {
 425         return Objects.requireNonNull(packet.get(IpV4Packet.class), "not an IPv4 packet");
 426     }
 427
 428     /**
 429      * Gets the {@link EthernetPacket} contained in {@code packet}, or throws a {@link NullPointerException} if
 430      * {@code packet} does not contain an {@link EthernetPacket}.
 431      * @param packet A {@link PcapPacket} that is expected to contain an {@link EthernetPacket}.
 432      * @return The {@link EthernetPacket} contained in {@code packet}.
 433      * @throws NullPointerException if {@code packet} does not encapsulate an {@link EthernetPacket}.
 434      */
 435     private static final EthernetPacket getEthernetPacketOrThrow(PcapPacket packet) {
 436         return Objects.requireNonNull(packet.get(EthernetPacket.class), "not an Ethernet packet");
 437     }
 438
 439     /**
 440      * Print signatures in {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects.
 441      *
 442      * @param signatures A {@link List} of {@link List} of {@link List} of
 443      *          {@link PcapPacket} objects that needs to be printed.
 444      */
 445     public static void printSignatures(List<List<List<PcapPacket>>> signatures) {
 446
 447         // Iterate over the list of all clusters/sequences
 448         int sequenceCounter = 0;
 449         for(List<List<PcapPacket>> listListPcapPacket : signatures) {
 450             // Iterate over every member of a cluster/sequence
 451             System.out.print("====== SEQUENCE " + ++sequenceCounter);
 452             System.out.println(" - " + listListPcapPacket.size() + " MEMBERS ======");
 453             for(List<PcapPacket> listPcapPacket : listListPcapPacket) {
 454                 // Print out packet lengths in a sequence
 455                 int packetCounter = 0;
 456                 for(PcapPacket pcapPacket : listPcapPacket) {
 457                     if(pcapPacket != null) {
 458                         System.out.print(pcapPacket.length());
 459                     }
 460                     if(packetCounter < listPcapPacket.size() - 1) {
 461                         System.out.print(" ");  // Provide space if not last packet
 462                     } else {
 463                         System.out.println();      // Newline if last packet
 464                     }
 465                     packetCounter++;
 466                 }
 467             }
 468         }
 469     }
 470
 471     /**
 472      * Extract core point range in the form of {@code List} of {@code List} of {@code PcapPacket} objects.
 473      *
 474      * @param pairs The pairs for core points extraction.
 475      * @param eps Epsilon value for the DBSCAN algorithm.
 476      * @param minPts minPts value for the DBSCAN algorithm.
 477      * @return A {@link List} of {@link List} of {@code PcapPacket} objects that contains core points range
 478      *          in the first and second element.
 479      */
 480     public static List<List<PcapPacket>> extractRangeCorePoints(List<List<PcapPacket>> pairs, double eps, int minPts) {
 481
 482         // Initialize min and max value
 483         PcapPacket minFirstElement = null;
 484         PcapPacket maxFirstElement = null;
 485         PcapPacket minSecondElement = null;
 486         PcapPacket maxSecondElement = null;
 487
 488         // Iterate over pairs
 489         for(List<PcapPacket> pair : pairs) {
 490             if (isCorePoint(pair, pairs, eps, minPts)) {
 491                 // Record the first element
 492                 if (minFirstElement == null || pair.get(0).length() < minFirstElement.length()) {
 493                     minFirstElement = pair.get(0);
 494                 }
 495                 if (maxFirstElement == null || pair.get(0).length() > maxFirstElement.length()) {
 496                     maxFirstElement = pair.get(0);
 497                 }
 498                 // Record the second element
 499                 if (minSecondElement == null || pair.get(1).length() < minSecondElement.length()) {
 500                     minSecondElement = pair.get(1);
 501                 }
 502                 if (maxSecondElement == null || pair.get(1).length() > maxSecondElement.length()) {
 503                     maxSecondElement = pair.get(1);
 504                 }
 505             }
 506         }
 507         List<PcapPacket> corePointLowerBound = new ArrayList<>();
 508         corePointLowerBound.add(0, minFirstElement);
 509         corePointLowerBound.add(1, minSecondElement);
 510         List<PcapPacket> corePointUpperBound = new ArrayList<>();
 511         corePointUpperBound.add(0, maxFirstElement);
 512         corePointUpperBound.add(1, maxSecondElement);
 513         // Combine lower and upper bounds
 514         List<List<PcapPacket>> listRangeCorePoints = new ArrayList<>();
 515         listRangeCorePoints.add(corePointLowerBound);
 516         listRangeCorePoints.add(corePointUpperBound);
 517
 518         return listRangeCorePoints;
 519     }
 520
 521     /**
 522      * Test whether the {@code List} of {@code PcapPacket} objects is a core point.
 523      *
 524      * @param pair The pair to be tested.
 525      * @param pairs All of the pairs.
 526      * @param eps Epsilon value for the DBSCAN algorithm.
 527      * @param minPts minPts value for the DBSCAN algorithm.
 528      * @return True if the pair is a core point.
 529      */
 530     private static boolean isCorePoint(List<PcapPacket> pair, List<List<PcapPacket>> pairs, double eps, int minPts) {
 531
 532         int corePoints = 0;
 533         int x1 = pair.get(0) == null ? 0 : pair.get(0).length();
 534         int y1 = pair.get(1) == null ? 0 : pair.get(1).length();
 535         // Check if we have enough core points
 536         for(List<PcapPacket> pairInPairs : pairs) {
 537             int x2 = pairInPairs.get(0) == null ? 0 : pairInPairs.get(0).length();
 538             int y2 = pairInPairs.get(1) == null ? 0 : pairInPairs.get(1).length();
 539             // Measure distance between x and y
 540             double distance = Math.sqrt(Math.pow((double)(x2 - x1), 2) + Math.pow((double)(y2 - y1), 2));
 541             // Increment core points count if this point is within eps
 542             if (distance <= eps) {
 543                 corePoints++;
 544             }
 545         }
 546         // Return true if the number of core points >= minPts
 547         if (corePoints >= minPts) {
 548             return true;
 549         }
 550
 551         return false;
 552     }
 553
 554     /**
 555      * Test the conservativeness of the signatures (basically whether we want strict or range-based matching).
 556      * We go for a conservative approach (strict matching) when there is no range or there are ranges but the
 557      * ranges overlap across multiple signatures, e.g., ON and OFF signatures.
 558      *
 559      * @param signature The signature we want to check and overwrite if needed.
 560      * @param eps Epsilon value for the DBSCAN algorithm.
 561      * @param otherSignatures Other signatures we want to check against this signature.
 562      * @return A boolean that is True when range-based matching is used.
 563      */
 564     public static boolean isRangeBasedMatching(List<List<List<PcapPacket>>> signature, double eps,
 565                                                 List<List<List<PcapPacket>>> ...otherSignatures) {
 566         // Check against multiple signatures
 567         // TODO: Per March 2019 we only support ON and OFF signatures though
 568         for(List<List<List<PcapPacket>>> otherSig : otherSignatures) {
 569             // Do conservative strict matching if there is any overlap
 570             if (isConservativeChecking(signature, otherSig, eps)) {
 571                 return false;
 572             }
 573         }
 574         return true;
 575     }
 576
 577     /**
 578      * Test the conservativeness of the signatures (basically whether we want strict or range-based matching).
 579      * We go for a conservative approach (strict matching) when there is no range or there are ranges but the
 580      * ranges overlap across multiple signatures, e.g., ON and OFF signatures.
 581      *
 582      * @param signature The signature we want to check and overwrite if needed.
 583      * @param corePointRange The core points range of this signature.
 584      * @return A boolean that is True when range-based matching is used.
 585      */
 586     public static List<List<List<PcapPacket>>> useRangeBasedMatching(List<List<List<PcapPacket>>> signature,
 587                                                                      List<List<List<PcapPacket>>> corePointRange) {
 588         // Do range-based checking instead if there is no overlap
 589         // Transform our signature into a range-based format
 590         List<List<List<PcapPacket>>> rangeBasedSignature = getSequenceRanges(signature);
 591         // We have to iterate sequence by sequence in the signature that has already gone through concatenation/merging
 592         // And compare the packet lengths against the ones in corePointRange that are still in pairs/points
 593         List<List<List<PcapPacket>>> finalSignature = new ArrayList<>();
 594
 595         // Construct the range-based signature
 596         for(List<List<PcapPacket>> listOfSequences : rangeBasedSignature) {
 597             List<PcapPacket> sequenceLowerBound = listOfSequences.get(0);
 598             List<PcapPacket> sequenceUpperBound = listOfSequences.get(1);
 599             List<List<PcapPacket>> newList = new ArrayList<>();
 600             List<PcapPacket> newListLowerBound = new ArrayList<>();
 601             List<PcapPacket> newListUpperBound = new ArrayList<>();
 602             // Iterate over the packets
 603             for(PcapPacket lowerBound : sequenceLowerBound) {
 604                 // Look for the lower and upper bounds from the signature
 605                 PcapPacket upperBound = sequenceUpperBound.get(sequenceLowerBound.indexOf(lowerBound));
 606                 // Look for the lower and upper bounds from the cluster analysis (core point range)
 607                 List<PcapPacket> bounds = getCorePointBounds(corePointRange, lowerBound, upperBound);
 608                 // Add into list
 609                 // The first element is the lower bound and the second element is the upper bound
 610                 newListLowerBound.add(bounds.get(0));
 611                 newListUpperBound.add(bounds.get(1));
 612             }
 613             newList.add(0, newListLowerBound);
 614             newList.add(1, newListUpperBound);
 615             finalSignature.add(newList);
 616         }
 617
 618         return finalSignature;
 619     }
 620
 621     /*
 622      * Get the corresponding PcapPacket object for lower and upper bounds.
 623      */
 624     private static List<PcapPacket> getCorePointBounds(List<List<List<PcapPacket>>> corePointRange,
 625                                                        PcapPacket lowerBound, PcapPacket upperBound) {
 626
 627         List<PcapPacket> listBounds = new ArrayList<>();
 628         // Iterate over PcapPacket one by one
 629         for(List<List<PcapPacket>> listOfListPcapPacket : corePointRange) {
 630             List<PcapPacket> listCorePointLowerBound = listOfListPcapPacket.get(0);
 631             List<PcapPacket> listCorePointUpperBound = listOfListPcapPacket.get(1);
 632             for(PcapPacket corePointLowerBound : listCorePointLowerBound) {
 633                 PcapPacket corePointUpperBound =
 634                         listCorePointUpperBound.get(listCorePointLowerBound.indexOf(corePointLowerBound));
 635                 // Return if the match for the core point bounds is found
 636                 // Basically the core point range has to be within the signature range
 637                 if (lowerBound.length() <= corePointLowerBound.length() &&
 638                     corePointUpperBound.length() <= upperBound.length()) {
 639                     listBounds.add(0, corePointLowerBound);
 640                     listBounds.add(1, corePointUpperBound);
 641                     return listBounds;
 642                 }
 643                 // Just skip the null elements
 644                 if (lowerBound == null && upperBound == null) {
 645                     continue;
 646                 }
 647             }
 648         }
 649         // Return null if not found
 650         return null;
 651     }
 652
 653     /*
 654      * Get the corresponding PcapPacket object for upper bound.
 655      */
 656 //    private static PcapPacket getUpperBound(List<List<List<PcapPacket>>> corePointRange, PcapPacket pcapPacket) {
 657 //
 658 //        // Iterate over PcapPacket one by one
 659 //        int counter = 0;
 660 //        for(List<List<PcapPacket>> listOfListPcapPacket : corePointRange) {
 661 //            List<PcapPacket> listUpperBound = listOfListPcapPacket.get(1);
 662 //            for(PcapPacket upperBound : listUpperBound) {
 663 //                // Return the counter matches
 664 //                if (counter == pcapPacketIndex) {
 665 //                    return upperBound;
 666 //                }
 667 //                if (upperBound == null) {
 668 //                    continue;
 669 //                }
 670 //                counter++;
 671 //            }
 672 //        }
 673 //
 674 //        return null;
 675 //    }
 676
 677     /**
 678      * Check if there is any overlap between the signature stored in this class and another signature.
 679      * Conditions:
 680      * 1) If both signatures do not have any range, then we need to do conservative checking (return true).
 681      * 2) If both signatures have the same number of packets/packet lengths, then we check the range; if the
 682      *    numbers of packets/packet lengths are different then we assume that there is no overlap.
 683      * 3) If there is any range in the signatures, then we need to check for overlap.
 684      * 4) If there is overlap for EVERY packet/packet length, then we return true (conservative checking);
 685      *    otherwise false (range-based checking).
 686      *
 687      * @param signature A {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects to be checked
 688      *                  for overlaps with the other signature.
 689      * @param otherSignature A {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects to be checked
 690      *                       for overlaps with the signature.
 691      * @param eps Epsilon value for the DBSCAN algorithm.
 692      * @return A boolean that is true if there is an overlap; false otherwise.
 693      */
 694     public static boolean isConservativeChecking(List<List<List<PcapPacket>>> signature,
 695                                                  List<List<List<PcapPacket>>> otherSignature,
 696                                                  double eps) {
 697
 698         // Get the ranges of the two signatures
 699         List<List<List<PcapPacket>>> signatureRanges = getSequenceRanges(signature);
 700         List<List<List<PcapPacket>>> otherSignatureRanges = getSequenceRanges(otherSignature);
 701         if (!isRangeBased(signatureRanges) && !isRangeBased(otherSignatureRanges)) {
 702             // Conservative checking when there is no range
 703             return true;
 704         } else if(signatureRanges.size() != otherSignatureRanges.size()) {
 705             // The two signatures have different numbers of packets/packet lengths
 706             return false;
 707         } else {
 708             // There is range; check if there is overlap
 709             return checkOverlap(signatureRanges, otherSignatureRanges, eps);
 710         }
 711     }
 712
 713     /* Find the sequence with the minimum packet lengths.
 714      * The second-layer list should contain the minimum sequence for element 0 and maximum sequence for element 1.
 715      */
 716     private static List<List<List<PcapPacket>>> getSequenceRanges(List<List<List<PcapPacket>>> signature) {
 717
 718         // Start from the first index
 719         List<List<List<PcapPacket>>> rangeBasedSequence = new ArrayList<>();
 720         for(List<List<PcapPacket>> listListPcapPacket : signature) {
 721             List<List<PcapPacket>> minMaxSequence = new ArrayList<>();
 722             // Both searches start from index 0
 723             List<PcapPacket> minSequence = new ArrayList<>(listListPcapPacket.get(0));
 724             List<PcapPacket> maxSequence = new ArrayList<>(listListPcapPacket.get(0));
 725             for(List<PcapPacket> listPcapPacket : listListPcapPacket) {
 726                 for(PcapPacket pcapPacket : listPcapPacket) {
 727                     int index = listPcapPacket.indexOf(pcapPacket);
 728                     // Set the new minimum if length at the index is minimum
 729                     if (pcapPacket.length() < minSequence.get(index).length()) {
 730                         minSequence.set(index, pcapPacket);
 731                     }
 732                     // Set the new maximum if length at the index is maximum
 733                     if (pcapPacket.length() > maxSequence.get(index).length()) {
 734                         maxSequence.set(index, pcapPacket);
 735                     }
 736                 }
 737             }
 738             // minSequence as element 0 and maxSequence as element 1
 739             minMaxSequence.add(minSequence);
 740             minMaxSequence.add(maxSequence);
 741             rangeBasedSequence.add(minMaxSequence);
 742         }
 743
 744         return rangeBasedSequence;
 745     }
 746
 747     /*
 748      * Check for overlap since we have range in at least one of the signatures.
 749      * Overlap is only true when all ranges overlap. We need to check in order.
 750      */
 751     private static boolean checkOverlap(List<List<List<PcapPacket>>> signatureRanges,
 752                                  List<List<List<PcapPacket>>> otherSignatureRanges, double eps) {
 753
 754         for(List<List<PcapPacket>> listListPcapPacket : signatureRanges) {
 755             // Lower bound of the range is in index 0
 756             // Upper bound of the range is in index 1
 757             int sequenceSetIndex = signatureRanges.indexOf(listListPcapPacket);
 758             List<PcapPacket> minSequenceSignature = listListPcapPacket.get(0);
 759             List<PcapPacket> maxSequenceSignature = listListPcapPacket.get(1);
 760             for(PcapPacket pcapPacket : minSequenceSignature) {
 761                 // Get the lower and upper bounds of the current signature
 762                 int packetIndex = minSequenceSignature.indexOf(pcapPacket);
 763                 int lowerBound = pcapPacket.length();
 764                 int upperBound = maxSequenceSignature.get(packetIndex).length();
 765                 // Check for range overlap in the other signature!
 766                 // Check the packet/packet length at the same position
 767                 List<PcapPacket> minSequenceSignatureOther = otherSignatureRanges.get(sequenceSetIndex).get(0);
 768                 List<PcapPacket> maxSequenceSignatureOther = otherSignatureRanges.get(sequenceSetIndex).get(1);
 769                 int lowerBoundOther = minSequenceSignatureOther.get(packetIndex).length();
 770                 int upperBoundOther = maxSequenceSignatureOther.get(packetIndex).length();
 771                 if (!(lowerBoundOther-(int)eps <= lowerBound && lowerBound <= upperBoundOther+(int)eps) &&
 772                     !(lowerBoundOther-(int)eps <= upperBound && upperBound <= upperBoundOther+(int)eps)) {
 773                     return false;
 774                 }
 775             }
 776         }
 777
 778         return true;
 779     }
 780
 781     /*
 782      * Check and see if there is any range in the signatures
 783      */
 784     private static boolean isRangeBased(List<List<List<PcapPacket>>> signatureRanges) {
 785
 786         for(List<List<PcapPacket>> listListPcapPacket : signatureRanges) {
 787             // Lower bound of the range is in index 0
 788             // Upper bound of the range is in index 1
 789             List<PcapPacket> minSequence = listListPcapPacket.get(0);
 790             List<PcapPacket> maxSequence = listListPcapPacket.get(1);
 791             for(PcapPacket pcapPacket : minSequence) {
 792                 int index = minSequence.indexOf(pcapPacket);
 793                 if (pcapPacket.length() != maxSequence.get(index).length()) {
 794                     // If there is any packet length that differs in the minSequence
 795                     // and maxSequence, then it is range-based
 796                     return true;
 797                 }
 798             }
 799         }
 800
 801         return false;
 802     }
 803
 804     /**
 805      * Remove a sequence in a signature object.
 806      *
 807      * @param signatures A {@link List} of {@link List} of {@link List} of
 808      *          {@link PcapPacket} objects.
 809      * @param sequenceIndex An index for a sequence that consists of {{@link List} of {@link List} of
 810      *          {@link PcapPacket} objects.
 811      */
 812     public static void removeSequenceFromSignature(List<List<List<PcapPacket>>> signatures, int sequenceIndex) {
 813
 814         // Sequence index starts from 0
 815         signatures.remove(sequenceIndex);
 816     }
 817 }