Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer3/Layer3ClusterMatcher.java

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