Code/Projects/SmartPlugDetector/src/main/java/edu/uci/iotproject/detection/ClusterMatcher.java

   1 package edu.uci.iotproject.detection;
   2
   3 import edu.uci.iotproject.Conversation;
   4 import edu.uci.iotproject.TcpReassembler;
   5 import edu.uci.iotproject.analysis.TcpConversationUtils;
   6 import edu.uci.iotproject.io.PcapHandleReader;
   7 import edu.uci.iotproject.util.PrintUtils;
   8 import org.pcap4j.core.*;
   9
  10 import java.time.ZoneId;
  11 import java.util.*;
  12 import java.util.stream.Collectors;
  13
  14 import static edu.uci.iotproject.util.PcapPacketUtils.*;
  15
  16 /**
  17  * Searches a traffic trace for sequences of packets "belong to" a given cluster (in other words, attempts to classify
  18  * traffic as pertaining to a given cluster).
  19  *
  20  * @author Janus Varmarken {@literal <jvarmark@uci.edu>}
  21  * @author Rahmadi Trimananda {@literal <rtrimana@uci.edu>}
  22  */
  23 public class ClusterMatcher implements PacketListener {
  24
  25     // Test client
  26     public static void main(String[] args) throws PcapNativeException, NotOpenException {
  27
  28 //        String path = "/scratch/July-2018"; // Rahmadi
  29         String path = "/Users/varmarken/temp/UCI IoT Project/experiments"; // Janus
  30         final String inputPcapFile = path + "/2018-07/dlink/dlink.wlan1.local.pcap";
  31         final String signatureFile = path + "/2018-07/dlink/offSignature1.sig";
  32
  33         List<List<PcapPacket>> signature = PrintUtils.deserializeClustersFromFile(signatureFile);
  34         ClusterMatcher clusterMatcher = new ClusterMatcher(signature, null,
  35                 (sig, match) -> System.out.println(
  36                         String.format("[ !!! SIGNATURE DETECTED AT %s !!! ]",
  37                                 match.get(0).getTimestamp().atZone(ZoneId.of("America/Los_Angeles")))
  38                 )
  39         );
  40
  41         PcapHandle handle;
  42         try {
  43             handle = Pcaps.openOffline(inputPcapFile, PcapHandle.TimestampPrecision.NANO);
  44         } catch (PcapNativeException pne) {
  45             handle = Pcaps.openOffline(inputPcapFile);
  46         }
  47         PcapHandleReader reader = new PcapHandleReader(handle, p -> true, clusterMatcher);
  48         reader.readFromHandle();
  49         clusterMatcher.performDetection();
  50     }
  51
  52     /**
  53      * The cluster that describes the sequence of packets that this {@link ClusterMatcher} is trying to detect in the
  54      * observed traffic.
  55      */
  56     private final List<List<PcapPacket>> mCluster;
  57
  58     /**
  59      * The ordered directions of packets in the sequences that make up {@link #mCluster}.
  60      */
  61     private final Conversation.Direction[] mClusterMemberDirections;
  62
  63     /**
  64      * For reassembling the observed traffic into TCP connections.
  65      */
  66     private final TcpReassembler mTcpReassembler = new TcpReassembler();
  67
  68     /**
  69      * IP of the router's WAN port (if analyzed traffic is captured at the ISP's point of view).
  70      */
  71     private final String mRouterWanIp;
  72
  73     private final ClusterMatchObserver[] mObservers;
  74
  75     /**
  76      * Create a {@link ClusterMatcher}.
  77      * @param cluster The cluster that traffic is matched against.
  78      * @param routerWanIp The router's WAN IP if examining traffic captured at the ISP's point of view (used for
  79      *                    determining the direction of packets).
  80      * @param detectionObservers Client code that wants to get notified whenever the {@link ClusterMatcher} detects that
  81      *                          (a subset of) the examined traffic is similar to the traffic that makes up
  82      *                          {@code cluster}, i.e., when the examined traffic is classified as pertaining to
  83      *                          {@code cluster}.
  84      */
  85     public ClusterMatcher(List<List<PcapPacket>> cluster, String routerWanIp, ClusterMatchObserver... detectionObservers) {
  86         // ===================== PRECONDITION SECTION =====================
  87         cluster = Objects.requireNonNull(cluster, "cluster cannot be null");
  88         if (cluster.isEmpty() || cluster.stream().anyMatch(inner -> inner.isEmpty())) {
  89             throw new IllegalArgumentException("cluster is empty (or contains an empty inner List)");
  90         }
  91         mObservers = Objects.requireNonNull(detectionObservers, "detectionObservers cannot be null");
  92         if (mObservers.length == 0) {
  93             throw new IllegalArgumentException("no detectionObservers provided");
  94         }
  95         // Build the cluster members' direction sequence.
  96         // Note: assumes that the provided cluster was captured within the local network (routerWanIp is set to null).
  97         mClusterMemberDirections = getPacketDirections(cluster.get(0), null);
  98         /*
  99          * Enforce restriction on cluster members: all representatives must exhibit the same direction pattern and
 100          * contain the same number of packets. Note that this is a somewhat heavy operation, so it may be disabled later
 101          * on in favor of performance. However, it is only run once (at instantiation), so the overhead may be warranted
 102          * in order to ensure correctness, especially during the development/debugging phase.
 103          */
 104         if (cluster.stream().
 105                 anyMatch(inner -> !Arrays.equals(mClusterMemberDirections, getPacketDirections(inner, null)))) {
 106             throw new IllegalArgumentException(
 107                     "cluster members must contain the same number of packets and exhibit the same packet direction " +
 108                             "pattern"
 109             );
 110         }
 111         // ================================================================
 112         // Prune the provided cluster.
 113         mCluster = pruneCluster(cluster);
 114         mRouterWanIp = routerWanIp;
 115     }
 116
 117     @Override
 118     public void gotPacket(PcapPacket packet) {
 119         // Present packet to TCP reassembler so that it can be mapped to a connection (if it is a TCP packet).
 120         mTcpReassembler.gotPacket(packet);
 121     }
 122
 123     /**
 124      * Get the cluster that describes the packet sequence that this {@link ClusterMatcher} is searching for.
 125      * @return the cluster that describes the packet sequence that this {@link ClusterMatcher} is searching for.
 126      */
 127     public List<List<PcapPacket>> getCluster() {
 128         return mCluster;
 129     }
 130
 131     public void performDetection() {
 132         /*
 133          * Let's start out simple by building a version that only works for signatures that do not span across multiple
 134          * TCP conversations...
 135          */
 136         for (Conversation c : mTcpReassembler.getTcpConversations()) {
 137             if (c.isTls() && c.getTlsApplicationDataPackets().isEmpty() || !c.isTls() && c.getPackets().isEmpty()) {
 138                 // Skip empty conversations.
 139                 continue;
 140             }
 141             for (List<PcapPacket> signatureSequence : mCluster) {
 142                 if (isTlsSequence(signatureSequence) != c.isTls()) {
 143                     // We consider it a mismatch if one is a TLS application data sequence and the other is not.
 144                     continue;
 145                 }
 146                 // Fetch set of packets to examine based on TLS or not.
 147                 List<PcapPacket> cPkts = c.isTls() ? c.getTlsApplicationDataPackets() : c.getPackets();
 148                 /*
 149                  * Note: we embed the attempt to detect the signature sequence in a loop in order to capture those cases
 150                  * where the same signature sequence appears multiple times in one Conversation.
 151                  *
 152                  * Note: since we expect all sequences that together make up the signature to exhibit the same direction
 153                  * pattern, we can simply pass the precomputed direction array for the signature sequence so that it
 154                  * won't have to be recomputed internally in each call to findSubsequenceInSequence().
 155                  */
 156                 Optional<List<PcapPacket>> match;
 157                 while ((match = findSubsequenceInSequence(signatureSequence, cPkts, mClusterMemberDirections, null)).
 158                         isPresent()) {
 159                     List<PcapPacket> matchSeq = match.get();
 160                     // Notify observers about the match.
 161                     Arrays.stream(mObservers).forEach(o -> o.onMatch(ClusterMatcher.this, matchSeq));
 162                     /*
 163                      * Get the index in cPkts of the last packet in the sequence of packets that matches the searched
 164                      * signature sequence.
 165                      */
 166                     int matchSeqEndIdx = cPkts.indexOf(matchSeq.get(matchSeq.size()-1));
 167                     // We restart the search for the signature sequence immediately after that index, so truncate cPkts.
 168                     cPkts = cPkts.stream().skip(matchSeqEndIdx + 1).collect(Collectors.toList());
 169                 }
 170             }
 171             /*
 172              * TODO:
 173              * if no item in cluster matches, also perform a distance-based matching to cover those cases where we did
 174              * not manage to capture every single mutation of the sequence during training.
 175              *
 176              * Need to compute average/centroid of cluster to do so...? Compute within-cluster variance, then check if
 177              * distance between input conversation and cluster average/centroid is smaller than or equal to the computed
 178              * variance?
 179              */
 180         }
 181     }
 182
 183     /**
 184      * Checks if {@code sequence} is a sequence of TLS packets. Note: the current implementation relies on inspection
 185      * of the port numbers when deciding between TLS vs. non-TLS. Therefore, only the first packet of {@code sequence}
 186      * is examined as it is assumed that all packets in {@code sequence} pertain to the same {@link Conversation} and
 187      * hence share the same set of two src/dst port numbers (albeit possibly alternating between which one is the src
 188      * and which one is the dst, as packets in {@code sequence} may be in alternating directions).
 189      * @param sequence The sequence of packets for which it is to be determined if it is a sequence of TLS packets or
 190      *                 non-TLS packets.
 191      * @return {@code true} if {@code sequence} is a sequence of TLS packets, {@code false} otherwise.
 192      */
 193     private boolean isTlsSequence(List<PcapPacket> sequence) {
 194         // NOTE: Assumes ALL packets in sequence pertain to the same TCP connection!
 195         PcapPacket firstPkt = sequence.get(0);
 196         int srcPort = getSourcePort(firstPkt);
 197         int dstPort = getDestinationPort(firstPkt);
 198         return TcpConversationUtils.isTlsPort(srcPort) || TcpConversationUtils.isTlsPort(dstPort);
 199     }
 200
 201     /**
 202      * Examine if a given sequence of packets ({@code sequence}) contains a given shorter sequence of packets
 203      * ({@code subsequence}). Note: the current implementation actually searches for a substring as it does not allow
 204      * for interleaving packets in {@code sequence} that are not in {@code subsequence}; for example, if
 205      * {@code subsequence} consists of packet lengths [2, 3, 5] and {@code sequence} consists of  packet lengths
 206      * [2, 3, 4, 5], the result will be that there is no match (because of the interleaving 4). If we are to allow
 207      * interleaving packets, we need a modified version of
 208      * <a href="https://stackoverflow.com/a/20545604/1214974">this</a>.
 209      *
 210      * @param subsequence The sequence to search for.
 211      * @param sequence The sequence to search.
 212      * @param subsequenceDirections The directions of packets in {@code subsequence} such that for all {@code i},
 213      *                              {@code subsequenceDirections[i]} is the direction of the packet returned by
 214      *                              {@code subsequence.get(i)}. May be set to {@code null}, in which this call will
 215      *                              internally compute the packet directions.
 216      * @param sequenceDirections The directions of packets in {@code sequence} such that for all {@code i},
 217      *                           {@code sequenceDirections[i]} is the direction of the packet returned by
 218      *                           {@code sequence.get(i)}. May be set to {@code null}, in which this call will internally
 219      *                           compute the packet directions.
 220      *
 221      * @return An {@link Optional} containing the part of {@code sequence} that matches {@code subsequence}, or an empty
 222      *         {@link Optional} if no part of {@code sequence} matches {@code subsequence}.
 223      */
 224     private Optional<List<PcapPacket>> findSubsequenceInSequence(List<PcapPacket> subsequence,
 225                                                                  List<PcapPacket> sequence,
 226                                                                  Conversation.Direction[] subsequenceDirections,
 227                                                                  Conversation.Direction[] sequenceDirections) {
 228         if (sequence.size() < subsequence.size()) {
 229             // If subsequence is longer, it cannot be contained in sequence.
 230             return Optional.empty();
 231         }
 232         if (isTlsSequence(subsequence) != isTlsSequence(sequence)) {
 233             // We consider it a mismatch if one is a TLS application data sequence and the other is not.
 234             return Optional.empty();
 235         }
 236         // If packet directions have not been precomputed by calling code, we need to construct them.
 237         if (subsequenceDirections == null) {
 238             subsequenceDirections = getPacketDirections(subsequence, mRouterWanIp);
 239         }
 240         if (sequenceDirections == null) {
 241             sequenceDirections = getPacketDirections(sequence, mRouterWanIp);
 242         }
 243         int subseqIdx = 0;
 244         int seqIdx = 0;
 245         while (seqIdx < sequence.size()) {
 246             PcapPacket subseqPkt = subsequence.get(subseqIdx);
 247             PcapPacket seqPkt = sequence.get(seqIdx);
 248             // We only have a match if packet lengths and directions match.
 249             if (subseqPkt.getOriginalLength() == seqPkt.getOriginalLength() &&
 250                     subsequenceDirections[subseqIdx] == sequenceDirections[seqIdx]) {
 251                 // A match; advance both indices to consider next packet in subsequence vs. next packet in sequence.
 252                 subseqIdx++;
 253                 seqIdx++;
 254                 if (subseqIdx == subsequence.size()) {
 255                     // We managed to match the entire subsequence in sequence.
 256                     // Return the sublist of sequence that matches subsequence.
 257                     /*
 258                      * TODO:
 259                      * ASSUMES THE BACKING LIST (i.e., 'sequence') IS _NOT_ STRUCTURALLY MODIFIED, hence may not work
 260                      * for live traces!
 261                      */
 262                     return Optional.of(sequence.subList(seqIdx - subsequence.size(), seqIdx));
 263                 }
 264             } else {
 265                 // Mismatch.
 266                 if (subseqIdx > 0) {
 267                     /*
 268                      * If we managed to match parts of subsequence, we restart the search for subsequence in sequence at
 269                      * the index of sequence where the current mismatch occurred. I.e., we must reset subseqIdx, but
 270                      * leave seqIdx untouched.
 271                      */
 272                     subseqIdx = 0;
 273                 } else {
 274                     /*
 275                      * First packet of subsequence didn't match packet at seqIdx of sequence, so we move forward in
 276                      * sequence, i.e., we continue the search for subsequence in sequence starting at index seqIdx+1 of
 277                      * sequence.
 278                      */
 279                     seqIdx++;
 280                 }
 281             }
 282         }
 283         return Optional.empty();
 284     }
 285
 286     /**
 287      * Given a cluster, produces a pruned version of that cluster. In the pruned version, there are no duplicate cluster
 288      * members. Two cluster members are considered identical if their packets lengths and packet directions are
 289      * identical. The resulting pruned cluster is unmodifiable (this applies to both the outermost list as well as the
 290      * nested lists) in order to preserve its integrity when exposed to external code (e.g., through
 291      * {@link #getCluster()}).
 292      *
 293      * @param cluster A cluster to prune.
 294      * @return The resulting pruned cluster.
 295      */
 296     private final List<List<PcapPacket>> pruneCluster(List<List<PcapPacket>> cluster) {
 297         List<List<PcapPacket>> prunedCluster = new ArrayList<>();
 298         for (List<PcapPacket> originalClusterSeq : cluster) {
 299             boolean alreadyPresent = false;
 300             for (List<PcapPacket> prunedClusterSeq : prunedCluster) {
 301                 Optional<List<PcapPacket>> duplicate = findSubsequenceInSequence(originalClusterSeq, prunedClusterSeq,
 302                         mClusterMemberDirections, mClusterMemberDirections);
 303                 if (duplicate.isPresent()) {
 304                     alreadyPresent = true;
 305                     break;
 306                 }
 307             }
 308             if (!alreadyPresent) {
 309                 prunedCluster.add(Collections.unmodifiableList(originalClusterSeq));
 310             }
 311         }
 312         return Collections.unmodifiableList(prunedCluster);
 313     }
 314
 315     /**
 316      * Given a {@code List<PcapPacket>}, generate a {@code Conversation.Direction[]} such that each entry in the
 317      * resulting {@code Conversation.Direction[]} specifies the direction of the {@link PcapPacket} at the corresponding
 318      * index in the input list.
 319      * @param packets The list of packets for which to construct a corresponding array of packet directions.
 320      * @param routerWanIp The IP of the router's WAN port. This is used for determining the direction of packets when
 321      *                    the traffic is captured just outside the local network (at the ISP side of the router). Set to
 322      *                    {@code null} if {@code packets} stem from traffic captured within the local network.
 323      * @return A {@code Conversation.Direction[]} specifying the direction of the {@link PcapPacket} at the
 324      *         corresponding index in {@code packets}.
 325      */
 326     private static Conversation.Direction[] getPacketDirections(List<PcapPacket> packets, String routerWanIp) {
 327         Conversation.Direction[] directions = new Conversation.Direction[packets.size()];
 328         for (int i = 0; i < packets.size(); i++) {
 329             PcapPacket pkt = packets.get(i);
 330             if (getSourceIp(pkt).equals(getDestinationIp(pkt))) {
 331                 // Sanity check: we shouldn't be processing loopback traffic
 332                 throw new AssertionError("loopback traffic detected");
 333             }
 334             if (isSrcIpLocal(pkt) || getSourceIp(pkt).equals(routerWanIp)) {
 335                 directions[i] = Conversation.Direction.CLIENT_TO_SERVER;
 336             } else if (isDstIpLocal(pkt) || getDestinationIp(pkt).equals(routerWanIp)) {
 337                 directions[i] = Conversation.Direction.SERVER_TO_CLIENT;
 338             } else {
 339                 //throw new IllegalArgumentException("no local IP or router WAN port IP found, can't detect direction");
 340             }
 341         }
 342         return directions;
 343     }
 344
 345     /**
 346      * Interface used by client code to register for receiving a notification whenever the {@link ClusterMatcher}
 347      * detects traffic that is similar to the traffic that makes up the cluster returned by
 348      * {@link ClusterMatcher#getCluster()}.
 349      */
 350     interface ClusterMatchObserver {
 351         /**
 352          * Callback that is invoked whenever a sequence that is similar to a sequence associated with the cluster (i.e.,
 353          * a sequence is a member of the cluster) is detected in the traffic that the associated {@link ClusterMatcher}
 354          * observes.
 355          * @param clusterMatcher The {@link ClusterMatcher} that detected a match (classified traffic as pertaining to
 356          *                       its associated cluster).
 357          * @param match The traffic that was deemed to match the cluster associated with {@code clusterMatcher}.
 358          */
 359         void onMatch(ClusterMatcher clusterMatcher, List<PcapPacket> match);
 360     }
 361
 362 }