From ded2d1a37e4db8d7b996121a2d1d3f98ebc1ffa1 Mon Sep 17 00:00:00 2001 From: rtrimana Date: Thu, 20 Sep 2018 16:29:08 -0700 Subject: [PATCH] Adding signature combining; we can improve the performance later by requiring that the Conversation list should always be sorted based on timestamps. --- .../main/java/edu/uci/iotproject/Main.java | 50 ++++--- .../analysis/TcpConversationUtils.java | 122 ++++++++++++++++++ .../uci/iotproject/util/PcapPacketUtils.java | 85 +++++++++++- 3 files changed, 238 insertions(+), 19 deletions(-) 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 d909be8..022052f 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 @@ -49,10 +49,10 @@ public class Main { final String offPairsPath = "/scratch/July-2018/off.txt"; // 1) D-Link July 26 experiment -// final String inputPcapFile = path + "/2018-07/dlink/dlink.wlan1.local.pcap"; -// final String outputPcapFile = path + "/2018-07/dlink/dlink-processed.pcap"; -// final String triggerTimesFile = path + "/2018-07/dlink/dlink-july-26-2018.timestamps"; -// final String deviceIp = "192.168.1.246"; // .246 == phone; .199 == dlink plug? + final String inputPcapFile = path + "/2018-07/dlink/dlink.wlan1.local.pcap"; + final String outputPcapFile = path + "/2018-07/dlink/dlink-processed.pcap"; + final String triggerTimesFile = path + "/2018-07/dlink/dlink-july-26-2018.timestamps"; + final String deviceIp = "192.168.1.199"; // .246 == phone; .199 == dlink plug? // 2) TP-Link July 25 experiment // final String inputPcapFile = path + "/2018-07/tplink/tplink.wlan1.local.pcap"; @@ -93,10 +93,10 @@ public class Main { // final String deviceIp = "192.168.1.140"; // .246 == phone; .140 == TP-Link bulb // 7) Kwikset Doorlock August 6 experiment - final String inputPcapFile = path + "/2018-08/kwikset-doorlock/kwikset-doorlock.wlan1.local.pcap"; - final String outputPcapFile = path + "/2018-08/kwikset-doorlock/kwikset-doorlock-processed.pcap"; - final String triggerTimesFile = path + "/2018-08/kwikset-doorlock/kwikset-doorlock-aug-6-2018.timestamps"; - final String deviceIp = "192.168.1.246"; // .246 == phone; .142 == SmartThings Hub (note: use eth0 capture for this!) +// final String inputPcapFile = path + "/2018-08/kwikset-doorlock/kwikset-doorlock.wlan1.local.pcap"; +// final String outputPcapFile = path + "/2018-08/kwikset-doorlock/kwikset-doorlock-processed.pcap"; +// final String triggerTimesFile = path + "/2018-08/kwikset-doorlock/kwikset-doorlock-aug-6-2018.timestamps"; +// final String deviceIp = "192.168.1.246"; // .246 == phone; .142 == SmartThings Hub (note: use eth0 capture for this!) // September 12, 2018 - includes both wlan1 and eth1 interfaces //final String inputPcapFile = path + "/2018-08/kwikset-doorlock/kwikset3.wlan1.local.pcap"; @@ -256,6 +256,8 @@ public class Main { map(e -> e.getValue()). flatMap(List::stream). collect(Collectors.toList()); + //Collections.sort(onConversations, (c1, c2) -> c1.getPackets().) + List onPairs = onConversations.stream(). map(c -> c.isTls() ? TcpConversationUtils.extractTlsAppDataPacketPairs(c) : TcpConversationUtils.extractPacketPairs(c)). @@ -274,39 +276,55 @@ public class Main { // Perform clustering on conversation logged as part of all OFF events. DBSCANClusterer offClusterer = new DBSCANClusterer<>(10.0, 45); List> offClusters = offClusterer.cluster(offPairs); + // Sort the conversations as reference + List sortedAllConversation = TcpConversationUtils.sortConversationList(allConversations); // Output clusters System.out.println("========================================"); System.out.println(" Clustering results for ON "); System.out.println(" Number of clusters: " + onClusters.size()); int count = 0; - List> ppListOfListReadOn = null; + List>> ppListOfListReadOn = new ArrayList<>(); + List>> ppListOfListListOn = new ArrayList<>(); for (Cluster c : onClusters) { System.out.println(String.format("<<< Cluster #%02d (%03d points) >>>", ++count, c.getPoints().size())); System.out.print(PrintUtils.toSummaryString(c)); if(c.getPoints().size() > 45 && c.getPoints().size() < 55) { // Print to file List> ppListOfList = PcapPacketUtils.clusterToListOfPcapPackets(c); - PrintUtils.serializeClustersIntoFile("./onSignature" + count + ".sig", ppListOfList); - ppListOfListReadOn = - PrintUtils.serializeClustersFromFile("./onSignature" + count + ".sig"); + ppListOfListListOn.add(ppListOfList); } } + // TODO: Merging test + ppListOfListListOn = PcapPacketUtils.mergeSignatures(ppListOfListListOn, sortedAllConversation); + count = 0; + for (List> ll : ppListOfListListOn) { + PrintUtils.serializeClustersIntoFile("./onSignature" + ++count + ".sig", ll); + ppListOfListReadOn.add(PrintUtils.serializeClustersFromFile("./onSignature" + count + ".sig")); + } + System.out.println("========================================"); System.out.println(" Clustering results for OFF "); System.out.println(" Number of clusters: " + offClusters.size()); count = 0; - List> ppListOfListReadOff = null; + List>> ppListOfListReadOff = new ArrayList<>(); + List>> ppListOfListListOff = new ArrayList<>(); for (Cluster c : offClusters) { System.out.println(String.format("<<< Cluster #%03d (%06d points) >>>", ++count, c.getPoints().size())); System.out.print(PrintUtils.toSummaryString(c)); if(c.getPoints().size() > 45 && c.getPoints().size() < 55) { // Print to file List> ppListOfList = PcapPacketUtils.clusterToListOfPcapPackets(c); - PrintUtils.serializeClustersIntoFile("./offSignature" + count + ".sig", ppListOfList); - ppListOfListReadOff = - PrintUtils.serializeClustersFromFile("./offSignature" + count + ".sig"); + ppListOfListListOff.add(ppListOfList); } } + // TODO: Merging test + ppListOfListListOff = PcapPacketUtils.mergeSignatures(ppListOfListListOff, sortedAllConversation); + count = 0; + for (List> ll : ppListOfListListOff) { + PrintUtils.serializeClustersIntoFile("./offSignature" + ++count + ".sig", ll); + ppListOfListReadOff.add(PrintUtils.serializeClustersFromFile("./offSignature" + count + ".sig")); + } + System.out.println("========================================"); // ============================================================================================================ 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 0db25e3..bd7f9ac 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 @@ -21,6 +21,15 @@ import static edu.uci.iotproject.util.PcapPacketUtils.*; */ public class TcpConversationUtils { + /** + * Identifies the adjacency type of the signature for merging. + */ + public enum SignaturePosition { + NOT_ADJACENT, + LEFT_ADJACENT, + RIGHT_ADJACENT + } + /** *

* Given a {@link Conversation}, extract its set of "packet pairs", i.e., pairs of request-reply packets. @@ -325,4 +334,117 @@ public class TcpConversationUtils { sb.append(" "); } } + + /** + * Given a list of {@link Conversation} objects, sort them by timestamps. + * @param conversations The list of {@link Conversation} objects to be sorted. + * @return A sorted list of {@code Conversation} based on timestamps of the first + * packet in the {@code Conversation}. + */ + public static List sortConversationList(List conversations) { + // 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) -> + c1.getPackets().get(0).getTimestamp().compareTo(c2.getPackets().get(0).getTimestamp())); + return conversations; + } + + /** + * Given a {@code List} of {@link Conversation} objects, find one that has the given {@code List} + * of {@code PcapPacket}. + * @param conversations The {@code List} of {@link Conversation} objects as reference. + * @param ppList The {@code List} of {@code PcapPacket} objects to search in the {@code List} of {@link Conversation}. + * @return A {@code Conversation} that contains the given {@code List} of {@code PcapPacket}. + */ + public static Conversation returnConversation(List ppList, List conversations) { + // TODO: This part of comparison takes into account that the list of conversations is not sorted + // TODO: We could optimize this to have a better performance by requiring a sorted-by-timestamp list + // TODO: as a parameter + // Find a Conversation that ppList is part of + for (Conversation c : conversations) { + // Figure out if c is the Conversation that ppList is in + if (isPartOfConversation(ppList, c)) { + return c; + } + } + // Return null if not found + return null; + } + + /** + * Given a {@link Conversation} objects, check if {@code List} of {@code PcapPacket} is part of it and return the + * adjacency label based on {@code SignaturePosition}. + * @param conversation The {@link Conversation} object as reference. + * @param ppListFirst The first {@code List} of {@code PcapPacket} objects in the {@link Conversation}. + * @param ppListSecond The second {@code List} of {@code PcapPacket} objects in the {@link Conversation} whose + * position will be observed in the {@link Conversation} with respect to ppListFirst. + * @return A {@code SignaturePosition} that represents the position of the signature against another signature + * in a {@link Conversation}. + */ + public static SignaturePosition isPartOfConversationAndAdjacent(List ppListFirst, + List ppListSecond, + Conversation conversation) { + for (PcapPacket pp : conversation.getPackets()) { + // Take the first element in ppList and compare it + // The following elements in ppList are guaranteed to be in the same Conversation + // TODO: This part of comparison takes into account that the list of conversations is not sorted + // TODO: We could optimize this to have a better performance by requiring a sorted-by-timestamp list + // 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 + 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 + 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 + // Compare the first element of ppListRight with the last element of ppListSecond to know + // 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 + 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 SignaturePosition.NOT_ADJACENT; + } + + /** + * Given a {@link Conversation} objects, check if {@code List} of {@code PcapPacket} is part of it. + * @param conversation The {@link Conversation} object as reference. + * @param ppList The {@code List} of {@code PcapPacket} objects to search in the {@link Conversation}. + * @return A {@code Boolean} value that represents the presence of the {@code List} of {@code PcapPacket} in + * the {@link Conversation}. + */ + private static boolean isPartOfConversation(List ppList, Conversation 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; + } + + /** + * Given a {@link Conversation} objects, check the index of a {@code PcapPacket} in it. + * @param conversation The {@link Conversation} object as reference. + * @param pp The {@code PcapPacket} object to search in the {@link Conversation}. + * @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 + if (conversation.getPackets().contains(pp)) + return conversation.getPackets().indexOf(pp); + // 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 932c492..bd1f1c8 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 @@ -1,14 +1,14 @@ package edu.uci.iotproject.util; +import edu.uci.iotproject.Conversation; import edu.uci.iotproject.analysis.PcapPacketPair; +import edu.uci.iotproject.analysis.TcpConversationUtils; import org.apache.commons.math3.stat.clustering.Cluster; import org.pcap4j.core.PcapPacket; import org.pcap4j.packet.IpV4Packet; import org.pcap4j.packet.TcpPacket; -import java.util.ArrayList; -import java.util.List; -import java.util.Objects; +import java.util.*; /** * Utility methods for inspecting {@link PcapPacket} properties. @@ -18,6 +18,13 @@ import java.util.Objects; */ public final class PcapPacketUtils { + /** + * This is the threshold value for a signature's number of members + * If after a merging the number of members of a signature falls below this threshold, then we can boldly + * get rid of that signature. + */ + private static final int SIGNATURE_MERGE_THRESHOLD = 5; + /** * Gets the source IP (in decimal format) of an IPv4 packet. * @param packet The packet for which the IPv4 source address is to be extracted. @@ -102,7 +109,79 @@ public final class PcapPacketUtils { // Create a list of list of PcapPacket objects ppListOfList.add(ppList); } + // Sort the list of lists based on the first packet's timestamp! + Collections.sort(ppListOfList, (p1, p2) -> p1.get(0).getTimestamp().compareTo(p2.get(0).getTimestamp())); return ppListOfList; } + /** + * 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. + * @return A {@link List} of {@link List} of {@link List} of + * {@link PcapPacket} objects as the result of the merging. + */ + public static List>> + mergeSignatures(List>> signatures, List conversations) { + // Make a copy first + List>> copySignatures = new ArrayList<>(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 + List> secondList = signatures.get(second); + int initialSecondListMembers = secondList.size(); + // 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 + Conversation conv = TcpConversationUtils.returnConversation(signature, conversations); + // 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 + TcpConversationUtils.SignaturePosition position = + TcpConversationUtils.isPartOfConversationAndAdjacent(signature, ppList, conv); + if (position == TcpConversationUtils.SignaturePosition.LEFT_ADJACENT) { + // 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!"); + break; + } else if (position == TcpConversationUtils.SignaturePosition.RIGHT_ADJACENT) { + // 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!"); + break; + } // TcpConversationUtils.SignaturePosition.NOT_ADJACENT + //System.out.println("NOT_ADJACENT!"); + } + } + // Call it a successful merging if there are only less than 5 elements from the second list that + // cannot be merged + if (secondList.size() < SIGNATURE_MERGE_THRESHOLD) { + // 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 + 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 + return copySignatures; + } + } + } + return signatures; + } } -- 2.34.1