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

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