From: rtrimana Date: Sat, 22 Sep 2018 00:00:12 +0000 (-0700) Subject: Adding signature sorting by timestamps. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=pingpong.git;a=commitdiff_plain;h=d1d08c6c615098b31c54cc4a3cac38d795587d00;ds=sidebyside Adding signature sorting by timestamps. --- diff --git a/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/Main.java b/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/Main.java index 022052f..4e1c565 100644 --- a/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/Main.java +++ b/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/Main.java @@ -295,7 +295,8 @@ public class Main { } } // TODO: Merging test - ppListOfListListOn = PcapPacketUtils.mergeSignatures(ppListOfListListOn, sortedAllConversation); + PcapPacketUtils.mergeSignatures(ppListOfListListOn, sortedAllConversation); + PcapPacketUtils.sortSignatures(ppListOfListListOn); count = 0; for (List> ll : ppListOfListListOn) { PrintUtils.serializeClustersIntoFile("./onSignature" + ++count + ".sig", ll); @@ -318,13 +319,13 @@ public class Main { } } // TODO: Merging test - ppListOfListListOff = PcapPacketUtils.mergeSignatures(ppListOfListListOff, sortedAllConversation); + PcapPacketUtils.mergeSignatures(ppListOfListListOff, sortedAllConversation); + PcapPacketUtils.sortSignatures(ppListOfListListOff); count = 0; for (List> ll : ppListOfListListOff) { PrintUtils.serializeClustersIntoFile("./offSignature" + ++count + ".sig", ll); ppListOfListReadOff.add(PrintUtils.serializeClustersFromFile("./offSignature" + count + ".sig")); } - System.out.println("========================================"); // ============================================================================================================ @@ -334,6 +335,8 @@ public class Main { File fileOnEvents = new File(onPairsPath); PrintWriter pwOn = null; try { + + pwOn = new PrintWriter(fileOnEvents); } catch(Exception ex) { ex.printStackTrace(); diff --git a/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/analysis/TcpConversationUtils.java b/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/analysis/TcpConversationUtils.java index 1b0c8fd..7484d8a 100644 --- a/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/analysis/TcpConversationUtils.java +++ b/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/analysis/TcpConversationUtils.java @@ -358,7 +358,7 @@ public class TcpConversationUtils { * packet in the {@code Conversation}. */ public static List sortConversationList(List conversations) { - // Get rid of Conversation objects with no packets + // Get rid of Conversation objects with no packets. conversations.removeIf(x -> x.getPackets().size() == 0); // Sort the list based on the first packet's timestamp! Collections.sort(conversations, (c1, c2) -> @@ -408,28 +408,28 @@ public class TcpConversationUtils { // TODO: as a parameter if (isPartOfConversation(ppListSecond, conversation)) { // Compare the first element of ppListSecond with the last element of ppListFirst to know - // whether ppListSecond is RIGHT_ADJACENT relative to ppListFirst + // whether ppListSecond is RIGHT_ADJACENT relative to ppListFirst. PcapPacket lastElOfFirstList = ppListFirst.get(ppListFirst.size() - 1); PcapPacket firstElOfSecondList = ppListSecond.get(0); - // If the positions of the two are in order, then they are adjacent + // If the positions of the two are in order, then they are adjacent. int indexOfLastElOfFirstList = returnIndexInConversation(lastElOfFirstList, conversation); int indexOfFirstElOfSecondList = returnIndexInConversation(firstElOfSecondList, conversation); if(indexOfLastElOfFirstList + 1 == indexOfFirstElOfSecondList) { return SignaturePosition.RIGHT_ADJACENT; } - // NOT RIGHT_ADJACENT, so check for LEFT_ADJACENT + // NOT RIGHT_ADJACENT, so check for LEFT_ADJACENT. // Compare the first element of ppListRight with the last element of ppListSecond to know - // whether ppListSecond is LEFT_ADJACENT relative to ppListFirst + // whether ppListSecond is LEFT_ADJACENT relative to ppListFirst. PcapPacket firstElOfFirstList = ppListFirst.get(0); PcapPacket lastElOfSecondList = ppListSecond.get(ppListSecond.size() - 1); - // If the positions of the two are in order, then they are adjacent + // If the positions of the two are in order, then they are adjacent. int indexOfFirstElOfFirstList = returnIndexInConversation(firstElOfFirstList, conversation); int indexOfLastElOfSecondList = returnIndexInConversation(lastElOfSecondList, conversation); if(indexOfLastElOfSecondList + 1 == indexOfFirstElOfFirstList) { return SignaturePosition.LEFT_ADJACENT; } } - // Return NOT_ADJACENT if not found + // Return NOT_ADJACENT if not found. return SignaturePosition.NOT_ADJACENT; } @@ -441,10 +441,10 @@ public class TcpConversationUtils { * the {@link Conversation}. */ private static boolean isPartOfConversation(List ppList, Conversation conversation) { - // Find the first element of ppList in conversation + // Find the first element of ppList in conversation. if (conversation.getPackets().contains(ppList.get(0))) return true; - // Return false if not found + // Return false if not found. return false; } @@ -455,10 +455,10 @@ public class TcpConversationUtils { * @return An {@code Integer} value that gives the index of the {@code PcapPacket} in the {@link Conversation}. */ private static int returnIndexInConversation(PcapPacket pp, Conversation conversation) { - // Find pp in conversation + // Find pp in conversation. if (conversation.getPackets().contains(pp)) return conversation.getPackets().indexOf(pp); - // Return -1 if not found + // Return -1 if not found. return -1; } } diff --git a/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/util/PcapPacketUtils.java b/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/util/PcapPacketUtils.java index c5d944f..4c991e4 100644 --- a/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/util/PcapPacketUtils.java +++ b/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/util/PcapPacketUtils.java @@ -3,6 +3,7 @@ package edu.uci.iotproject.util; import edu.uci.iotproject.Conversation; import edu.uci.iotproject.analysis.PcapPacketPair; import edu.uci.iotproject.analysis.TcpConversationUtils; +import edu.uci.iotproject.analysis.TriggerTrafficExtractor; import org.apache.commons.math3.stat.clustering.Cluster; import org.pcap4j.core.PcapPacket; import org.pcap4j.packet.IpV4Packet; @@ -136,14 +137,14 @@ public final class PcapPacketUtils { public static List> clusterToListOfPcapPackets(Cluster cluster) { List> ppListOfList = new ArrayList<>(); for (PcapPacketPair ppp: cluster.getPoints()) { - // Create a list of PcapPacket objects (list of two members) + // Create a list of PcapPacket objects (list of two members). List ppList = new ArrayList<>(); ppList.add(ppp.getFirst()); if(ppp.getSecond().isPresent()) ppList.add(ppp.getSecond().get()); else ppList.add(null); - // Create a list of list of PcapPacket objects + // Create a list of list of PcapPacket objects. ppListOfList.add(ppList); } // Sort the list of lists based on the first packet's timestamp! @@ -155,7 +156,6 @@ public final class PcapPacketUtils { * Merge signatures in {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects. * We cross-check these with {@code List} of {@code Conversation} objects to see * if two {@code List} of {@code PcapPacket} objects actually belong to the same {@code Conversation}. - * * @param signatures A {@link List} of {@link List} of {@link List} of * {@link PcapPacket} objects that needs to be checked and merged. * @param conversations A {@link List} of {@link Conversation} objects as reference for merging. @@ -164,61 +164,118 @@ public final class PcapPacketUtils { */ public static List>> mergeSignatures(List>> signatures, List conversations) { - // Make a copy first + // Make a copy first. List>> copySignatures = new ArrayList<>(signatures); - // Traverse and look into the pairs of signatures + // Traverse and look into the pairs of signatures. for (int first = 0; first < signatures.size(); first++) { List> firstList = signatures.get(first); for (int second = first+1; second < signatures.size(); second++) { - int maxSignatureEl = 0; // Number of maximum signature elements + int maxSignatureEl = 0; // Number of maximum signature elements. List> secondList = signatures.get(second); int initialSecondListMembers = secondList.size(); - // Iterate over the signatures in the first list + // Iterate over the signatures in the first list. for (List signature : firstList) { - signature.removeIf(el -> el == null); // Clean up null elements - // Return the Conversation that the signature is part of + signature.removeIf(el -> el == null); // Clean up null elements. + // Return the Conversation that the signature is part of. Conversation conv = TcpConversationUtils.returnConversation(signature, conversations); - // Find the element of the second list that is a match for that Conversation + // Find the element of the second list that is a match for that Conversation. for (List ppList : secondList) { - ppList.removeIf(el -> el == null); // Clean up null elements - // Check if they are part of a Conversation and are adjacent to the first signature - // If yes then merge into the first list + ppList.removeIf(el -> el == null); // Clean up null elements. + // Check if they are part of a Conversation and are adjacent to the first signature. + // If yes then merge into the first list. TcpConversationUtils.SignaturePosition position = TcpConversationUtils.isPartOfConversationAndAdjacent(signature, ppList, conv); if (position == TcpConversationUtils.SignaturePosition.LEFT_ADJACENT) { - // Merge to the left side of the first signature + // Merge to the left side of the first signature. ppList.addAll(signature); signature = ppList; maxSignatureEl = signature.size() > maxSignatureEl ? signature.size() : maxSignatureEl; - secondList.remove(ppList); // Remove as we merge - //System.out.println("LEFT_ADJACENT!"); + secondList.remove(ppList); // Remove as we merge. break; } else if (position == TcpConversationUtils.SignaturePosition.RIGHT_ADJACENT) { - // Merge to the right side of the first signature + // Merge to the right side of the first signature. signature.addAll(ppList); maxSignatureEl = signature.size() > maxSignatureEl ? signature.size() : maxSignatureEl; - secondList.remove(ppList); // Remove as we merge - //System.out.println("RIGHT_ADJACENT!"); + secondList.remove(ppList); // Remove as we merge. break; - } // TcpConversationUtils.SignaturePosition.NOT_ADJACENT - //System.out.println("NOT_ADJACENT!"); + } // TcpConversationUtils.SignaturePosition.NOT_ADJACENT. } } // Call it a successful merging if there are only less than 5 elements from the second list that - // cannot be merged + // cannot be merged. if (secondList.size() < SIGNATURE_MERGE_THRESHOLD) { - // Prune the unsuccessfully merged signatures (i.e., these will have size() < maxSignatureEl) + // Prune the unsuccessfully merged signatures (i.e., these will have size() < maxSignatureEl). final int maxNumOfEl = maxSignatureEl; firstList.removeIf(el -> el.size() < maxNumOfEl); - // Remove the merged set of signatures when successful + // Remove the merged set of signatures when successful. signatures.remove(secondList); } else if (secondList.size() < initialSecondListMembers) { - // If only some of the signatures from the second list are merged, this means UNSUCCESSFUL merging - // Return the original copy of the signatures object + // If only some of the signatures from the second list are merged, this means UNSUCCESSFUL merging. + // Return the original copy of the signatures object. return copySignatures; } } } return signatures; } + + /** + * Sort the signatures in the {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects. + * The purpose of this is to sort the order of signatures in the signature list. For detection purposes, we need + * to know if one signature occurs earlier/later in time with respect to the other signatures for more confidence + * in detecting the occurrence of an event. + * @param signatures A {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects that needs sorting. + * We assume that innermost {@code List} of {@code PcapPacket} objects have been sorted ascending + * by timestamps. By the time we use this method, we should have sorted it when calling the + * {@code clusterToListOfPcapPackets} method. + * @return A sorted {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects. + */ + public static List>> sortSignatures(List>> signatures) { + // TODO: This is the simplest solution!!! Might not cover all corner cases. + // TODO: Sort the list of lists based on the first packet's timestamps! + //Collections.sort(signatures, (p1, p2) -> { + // return p1.get(0).get(0).getTimestamp().compareTo(p2.get(0).get(0).getTimestamp()); + //}); + // TODO: The following is a more complete solution that covers corner cases. + // Sort the list of lists based on one-to-one comparison between timestamps of signatures on both lists. + // This also takes into account the fact that the number of signatures in the two lists could be different. + // Additionally, this code forces the comparison between two signatures only if they occur in the + // INCLUSION_WINDOW_MILLIS window; otherwise, it tries to find the right pair of signatures in the time window. + Collections.sort(signatures, (p1, p2) -> { + int compare = 0; + int comparePrev = 0; + int count1 = 0; + int count2 = 0; + // Need to make sure that both are not out of bound! + while(count1 + 1 < p1.size() && count2 + 1 < p2.size()) { + long timestamp1 = p1.get(count1).get(0).getTimestamp().toEpochMilli(); + long timestamp2 = p2.get(count2).get(0).getTimestamp().toEpochMilli(); + // The two timestamps have to be within a 15-second window! + if(Math.abs(timestamp1 - timestamp2) < TriggerTrafficExtractor.INCLUSION_WINDOW_MILLIS) { + // If these two are within INCLUSION_WINDOW_MILLIS window then compare! + compare = p1.get(count1).get(0).getTimestamp().compareTo(p2.get(count2).get(0).getTimestamp()); + if (comparePrev != 0) { // First time since it is 0 + if (Integer.signum(compare) != Integer.signum(comparePrev)) { + // Throw an exception if the order of the two signatures is not consistent, + // E.g., 111, 222, 333 in one occassion and 222, 333, 111 in the other. + throw new Error("For some reason, the order of signatures are not always consistent!" + + "Returning the original data structure of signatures..."); + } + } + comparePrev = compare; + count1++; + count2++; + } else { + // If not within INCLUSION_WINDOW_MILLIS window then find the correct pair + // by incrementing one of them. + if(timestamp1 < timestamp2) + count1++; + else + count2++; + } + } + return compare; + }); + return signatures; + } } diff --git a/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/util/PrintUtils.java b/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/util/PrintUtils.java index 34412d0..ba782ea 100644 --- a/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/util/PrintUtils.java +++ b/Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/util/PrintUtils.java @@ -134,15 +134,15 @@ public class PrintUtils { Optional> secondHostnames = secondSrc.map(src -> ipHostnameMappings.getHostnamesForIp(src)); final String delimiter = " "; if (firstHostnames != null) { - // If one IP maps to multiple hostnames, we concatenate the hostnames (separated by a delimiter) + // If one IP maps to multiple hostnames, we concatenate the hostnames (separated by a delimiter). firstSrc = firstHostnames.stream().collect(Collectors.joining(delimiter)); } - // If one IP maps to multiple hostnames, we concatenate the hostnames (separated by a delimiter) + // If one IP maps to multiple hostnames, we concatenate the hostnames (separated by a delimiter). Optional hostnames = secondHostnames.map(hostnameSet -> hostnameSet.stream().collect(Collectors.joining(delimiter))); // Fall back to IP if we couldn't second pair is present, but we couldn't map to (a) hostname(s). secondSrc = hostnames.isPresent() ? hostnames : secondSrc; - // Check if the first source is C (client) or S (server) + // Check if the first source is C (client) or S (server). String firstSrcCorS = packetPair.isFirstClient() ? "C" : "S"; String secondSrcCorS = packetPair.isSecondClient() ? "C" : "S";