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