Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2ClusterMatcher.java

   1 package edu.uci.iotproject.detection.layer2;
   2
   3 import edu.uci.iotproject.trafficreassembly.layer2.Layer2FlowReassembler;
   4 import edu.uci.iotproject.trafficreassembly.layer2.Layer2Flow;
   5 import edu.uci.iotproject.trafficreassembly.layer2.Layer2FlowReassemblerObserver;
   6 import edu.uci.iotproject.detection.AbstractClusterMatcher;
   7 import edu.uci.iotproject.trafficreassembly.layer2.Layer2FlowObserver;
   8 import org.pcap4j.core.*;
   9
  10 import java.util.ArrayList;
  11 import java.util.HashMap;
  12 import java.util.List;
  13 import java.util.Map;
  14 import java.util.function.Function;
  15
  16 /**
  17  * Attempts to detect members of a cluster (packet sequence mutations) in layer 2 flows.
  18  *
  19  * @author Janus Varmarken {@literal <jvarmark@uci.edu>}
  20  * @author Rahmadi Trimananda {@literal <rtrimana@uci.edu>}
  21  */
  22 public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Layer2FlowReassemblerObserver, Layer2FlowObserver {
  23
  24     /**
  25      * Maps from a flow to a table of {@link Layer2SequenceMatcher}s for that particular flow. The table {@code t} is
  26      * structured such that {@code t[i][j]} is a {@link Layer2SequenceMatcher} that attempts to match member {@code i}
  27      * of {@link #mCluster} and has so far matched {@code j} packets of that particular sequence.
  28      */
  29     private final Map<Layer2Flow, Layer2SequenceMatcher[][]> mPerFlowSeqMatchers = new HashMap<>();
  30
  31     private final Function<Layer2Flow, Boolean> mFlowFilter;
  32
  33     /**
  34      * Create a new {@link Layer2ClusterMatcher} that attempts to find occurrences of {@code cluster}'s members.
  35      * @param cluster The sequence mutations that the new {@link Layer2ClusterMatcher} should search for.
  36      */
  37     public Layer2ClusterMatcher(List<List<PcapPacket>> cluster) {
  38         // Consider all flows if no flow filter specified.
  39         this(cluster, flow -> true, false);
  40     }
  41
  42     /**
  43      * Create a new {@link Layer2ClusterMatcher} that attempts to find occurrences of {@code cluster}'s members.
  44      * @param cluster The sequence mutations that the new {@link Layer2ClusterMatcher} should search for.
  45      * @param flowFilter A filter that defines what {@link Layer2Flow}s the new {@link Layer2ClusterMatcher} should
  46      *                   search for {@code cluster}'s members in. If {@code flowFilter} returns {@code true}, the flow
  47      *                   will be included (searched). Note that {@code flowFilter} is only queried once for each flow,
  48      *                   namely when the {@link Layer2FlowReassembler} notifies the {@link Layer2ClusterMatcher} about
  49      *                   the new flow. This functionality may for example come in handy when one only wants to search
  50      *                   for matches in the subset of flows that involves a specific (range of) MAC(s).
  51      * @param isRangeBased The boolean that decides if it is range-based vs. strict matching.
  52      */
  53     public Layer2ClusterMatcher(List<List<PcapPacket>> cluster, Function<Layer2Flow, Boolean> flowFilter,
  54                                 boolean isRangeBased) {
  55         super(cluster, isRangeBased);
  56         mFlowFilter = flowFilter;
  57     }
  58
  59     @Override
  60     public void onNewPacket(Layer2Flow flow, PcapPacket newPacket) {
  61         if (mPerFlowSeqMatchers.get(flow) == null) {
  62             // If this is the first time we encounter this flow, we need to set up sequence matchers for it.
  63             // All sequences of the cluster have the same length, so we only need to compute the length of the nested
  64             // arrays once. We want to make room for a cluster matcher in each state, including the initial empty state
  65             // but excluding the final "full match" state (as there is no point in keeping a terminated sequence matcher
  66             // around), so the length of the inner array is simply the sequence length.
  67             Layer2SequenceMatcher[][] matchers = new Layer2SequenceMatcher[mCluster.size()][mCluster.get(0).size()];
  68             // Prepare a "state 0" sequence matcher for each sequence variation in the cluster.
  69             for (int i = 0; i < matchers.length; i++) {
  70                 matchers[i][0] = new Layer2SequenceMatcher(mCluster.get(i));
  71             }
  72             // Associate the new sequence matcher table with the new flow
  73             mPerFlowSeqMatchers.put(flow, matchers);
  74         }
  75         // Fetch table that contains sequence matchers for this flow.
  76         Layer2SequenceMatcher[][] matchers = mPerFlowSeqMatchers.get(flow);
  77         // Present the packet to all sequence matchers.
  78         for (int i = 0; i < matchers.length; i++) {
  79             // Present packet to the sequence matchers that has advanced the most first. This is to prevent discarding
  80             // the sequence matchers that have advanced the most in the special case where the searched sequence
  81             // contains two packets of the same length going in the same direction.
  82             for (int j = matchers[i].length - 1; j >= 0 ; j--) {
  83                 Layer2SequenceMatcher sm = matchers[i][j];
  84                 if (sm == null) {
  85                     // There is currently no sequence matcher that has managed to match j packets.
  86                     continue;
  87                 }
  88                 boolean matched = sm.matchPacket(newPacket);
  89                 if (matched) {
  90                     if (sm.getMatchedPacketsCount() == sm.getTargetSequencePacketCount()) {
  91                         // Sequence matcher has a match. Report it to observers.
  92                         mObservers.forEach(o -> o.onMatch(this, sm.getMatchedPackets()));
  93                         // Remove the now terminated sequence matcher.
  94                         matchers[i][j] = null;
  95                     } else {
  96                         // Sequence matcher advanced one step, so move it to its corresponding new position iff the
  97                         // packet that advanced it has a later timestamp than that of the last matched packet of the
  98                         // sequence matcher at the new index, if any. In most traces, a small amount of the packets
  99                         // appear out of order (with regards to their timestamp), which is why this check is required.
 100                         // Obviously it would not be needed if packets where guaranteed to be processed in timestamp
 101                         // order here.
 102                         if (matchers[i][j+1] == null ||
 103                                 newPacket.getTimestamp().isAfter(matchers[i][j+1].getLastPacket().getTimestamp())) {
 104                             matchers[i][j+1] = sm;
 105                         }
 106                     }
 107                     // We always want to have a sequence matcher in state 0, regardless of if the one that advanced
 108                     // from state zero completed its matching or if it replaced a different one in state 1 or not.
 109                     if (sm.getMatchedPacketsCount() == 1) {
 110                         matchers[i][j] = new Layer2SequenceMatcher(sm.getTargetSequence());
 111                     }
 112                 }
 113             }
 114         }
 115     }
 116
 117
 118     @Override
 119     protected List<List<PcapPacket>> pruneCluster(List<List<PcapPacket>> cluster) {
 120         // Note: we assume that all sequences in the input cluster are of the same length and that their packet
 121         // directions are identical.
 122         List<List<PcapPacket>> prunedCluster = new ArrayList<>();
 123         for (List<PcapPacket> originalClusterSeq : cluster) {
 124             boolean alreadyPresent = prunedCluster.stream().anyMatch(pcPkts -> {
 125                 for (int i = 0; i < pcPkts.size(); i++) {
 126                     if (pcPkts.get(i).getOriginalLength() != originalClusterSeq.get(i).getOriginalLength()) {
 127                         return false;
 128                     }
 129                 }
 130                 return true;
 131             });
 132             if (!alreadyPresent) {
 133                 // Add the sequence if not already present in the pruned cluster.
 134                 prunedCluster.add(originalClusterSeq);
 135             }
 136         }
 137         return prunedCluster;
 138     }
 139
 140     private static final boolean DEBUG = false;
 141
 142     @Override
 143     public void onNewFlow(Layer2FlowReassembler reassembler, Layer2Flow newFlow) {
 144         // New flow detected. Check if we should consider it when searching for cluster member matches.
 145         if (mFlowFilter.apply(newFlow)) {
 146             if (DEBUG) {
 147                 System.out.println(">>> ACCEPTING FLOW: " + newFlow + " <<<");
 148             }
 149             // Subscribe to the new flow to get updates whenever a new packet pertaining to the flow is processed.
 150             newFlow.addFlowObserver(this);
 151         } else if (DEBUG) {
 152             System.out.println(">>> IGNORING FLOW: " + newFlow + " <<<");
 153         }
 154     }
 155 }