Adding skipped packets correlation.
[pingpong.git] / Code / Projects / PacketLevelSignatureExtractor / src / main / java / edu / uci / iotproject / detection / layer2 / Layer2ClusterMatcher.java
index ab5f148..5bf4655 100644 (file)
@@ -12,7 +12,6 @@ import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
-import java.util.concurrent.CopyOnWriteArrayList;
 import java.util.function.Function;
 
 /**
@@ -29,7 +28,6 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
      * of {@link #mCluster} and has so far matched {@code j} packets of that particular sequence.
      */
     private final Map<Layer2Flow, Layer2SequenceMatcher[][]> mPerFlowSeqMatchers = new HashMap<>();
-//    private final Map<Layer2Flow, Layer2RangeMatcher[]> mPerFlowRangeMatcher = new HashMap<>();
     private final Map<Layer2Flow, List<Layer2RangeMatcher>> mPerFlowRangeMatcher = new HashMap<>();
 
     private final Function<Layer2Flow, Boolean> mFlowFilter;
@@ -46,14 +44,22 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
 
     private int mInclusionTimeMillis;
 
+    /**
+     * Keeping track of maximum number of skipped packets
+     */
+    private int mMaxSkippedPackets;
+//    private List<Integer> mMaxSkippedPackets;
+
+    private int mLimitSkippedPackets;
+
     /**
      * Create a new {@link Layer2ClusterMatcher} that attempts to find occurrences of {@code cluster}'s members.
      * @param cluster The sequence mutations that the new {@link Layer2ClusterMatcher} should search for.
      */
     public Layer2ClusterMatcher(List<List<PcapPacket>> cluster, int inclusionTimeMillis,
-                                boolean isRangeBased, double eps) {
+                                boolean isRangeBased, double eps, int limitSkippedPackets) {
         // Consider all flows if no flow filter specified.
-        this(cluster, flow -> true, inclusionTimeMillis, isRangeBased, eps);
+        this(cluster, flow -> true, inclusionTimeMillis, isRangeBased, eps, limitSkippedPackets);
     }
 
     /**
@@ -70,13 +76,17 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
      * @param eps The epsilon value used in the DBSCAN algorithm.
      */
     public Layer2ClusterMatcher(List<List<PcapPacket>> cluster, Function<Layer2Flow, Boolean> flowFilter,
-                                int inclusionTimeMillis, boolean isRangeBased, double eps) {
+                                int inclusionTimeMillis, boolean isRangeBased, double eps, int limitSkippedPackets) {
         super(cluster, isRangeBased);
         mFlowFilter = flowFilter;
         mRangeBased = isRangeBased;
         mEps = eps;
         mInclusionTimeMillis =
                 inclusionTimeMillis == 0 ? TriggerTrafficExtractor.INCLUSION_WINDOW_MILLIS : inclusionTimeMillis;
+        mMaxSkippedPackets = 0;
+//        mMaxSkippedPackets = new ArrayList<>();
+        // Give integer's MAX_VALUE if -1
+        mLimitSkippedPackets = limitSkippedPackets == -1 ? Integer.MAX_VALUE : limitSkippedPackets;
     }
 
     @Override
@@ -119,8 +129,12 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
                 boolean matched = sm.matchPacket(newPacket);
                 if (matched) {
                     if (sm.getMatchedPacketsCount() == sm.getTargetSequencePacketCount()) {
-                        // Sequence matcher has a match. Report it to observers.
-                        mObservers.forEach(o -> o.onMatch(this, sm.getMatchedPackets()));
+                        // Update maximum skipped packets
+                        boolean stillMatch = checkMaxSkippedPackets(flow.getPackets(), sm.getMatchedPackets());
+                        if (stillMatch) {
+                            // Sequence matcher has a match. Report it to observers.
+                            mObservers.forEach(o -> o.onMatch(this, sm.getMatchedPackets()));
+                        }
                         // Remove the now terminated sequence matcher.
                         matchers[i][j] = null;
                     } else {
@@ -145,6 +159,24 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
         }
     }
 
+    // Update the maximum number of skipped packets
+    private boolean checkMaxSkippedPackets(List<PcapPacket> flowPackets, List<PcapPacket> matchedPackets) {
+        // Count number of skipped packets by looking into
+        // the difference of indices of two matched packets
+        boolean stillMatch = true;
+        for(int i = 1; i < matchedPackets.size(); ++i) {
+            int currIndex = flowPackets.indexOf(matchedPackets.get(i-1));
+            int nextIndex = flowPackets.indexOf(matchedPackets.get(i));
+            int skippedPackets = nextIndex - currIndex;
+            if (mMaxSkippedPackets < skippedPackets) {
+                mMaxSkippedPackets = skippedPackets;
+                stillMatch = false;
+            }
+//            mMaxSkippedPackets.add(skippedPackets);
+        }
+        return stillMatch;
+    }
+
     private void rangeBasedMatching(Layer2Flow flow, PcapPacket newPacket) {
         // TODO: For range-based matching, we need to create a new matcher every time we see the first element of
         //  the sequence (between lower and upper bounds).
@@ -175,7 +207,8 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
             listMatchers.add(newMatcher);
         }
         // Present packet to the sequence matchers.
-        // Make a shallow copy of the list so that we can clean up the actual list when a matcher is terminated
+        // Make a shallow copy of the list so that we can clean up the actual list when a matcher is terminated.
+        // Otherwise, we would get an exception for changing the list while iterating on it.
         List<Layer2RangeMatcher> listMatchersCopy = new ArrayList<>(listMatchers);
         for(Layer2RangeMatcher matcher : listMatchersCopy) {
             Layer2RangeMatcher sm = matcher;
@@ -190,8 +223,12 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
                 boolean matched = sm.matchPacket(newPacket);
                 if (matched) {
                     if (sm.getMatchedPacketsCount() == sm.getTargetSequencePacketCount()) {
-                        // Sequence matcher has a match. Report it to observers.
-                        mObservers.forEach(o -> o.onMatch(this, sm.getMatchedPackets()));
+                        // Update maximum skipped packets
+                        boolean stillMatch = checkMaxSkippedPackets(flow.getPackets(), sm.getMatchedPackets());
+                        if (stillMatch) {
+                            // Sequence matcher has a match. Report it to observers.
+                            mObservers.forEach(o -> o.onMatch(this, sm.getMatchedPackets()));
+                        }
                         // Terminate sequence matcher since matching is complete.
                         listMatchers.remove(matcher);
                     }
@@ -200,79 +237,6 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
         }
     }
 
-//    private void rangeBasedMatching(Layer2Flow flow, PcapPacket newPacket) {
-//        // TODO: For range-based matching, we only care about matching a range; therefore it is a matcher array.
-//        if (mPerFlowRangeMatcher.get(flow) == null) {
-//            // If this is the first time we encounter this flow, we need to set up a sequence matcher.
-//            // All sequences of the cluster have the same length, so we only need to compute the length of the
-//            // arrays once. We want to make room for a cluster matcher in each state, including the initial empty state
-//            // but excluding the final "full match" state (as there is no point in keeping a terminated sequence matcher
-//            // around), so the length of the array is simply the sequence length.
-//            Layer2RangeMatcher[] matcher = new Layer2RangeMatcher[mCluster.get(0).size()];
-//            // Prepare a "state 0" sequence matcher.
-//            matcher[0] = new Layer2RangeMatcher(mCluster.get(0), mCluster.get(1), mInclusionTimeMillis, mEps);
-//            // Associate the new sequence matcher table with the new flow.
-//            mPerFlowRangeMatcher.put(flow, matcher);
-//        }
-//        // Fetch table that contains sequence matchers for this flow.
-//        Layer2RangeMatcher[] matcher = mPerFlowRangeMatcher.get(flow);
-//        // Present packet to the sequence matcher.
-//        for (int j = matcher.length - 1; j >= 0; j--) {
-//            Layer2RangeMatcher sm = matcher[j];
-//            if (sm == null) {
-//                // There is currently no sequence matcher that has managed to match j packets.
-//                continue;
-//            }
-//            boolean matched = sm.matchPacket(newPacket);
-//
-//            // TODO: DEBUGGING
-//            long timeStamp = newPacket.getTimestamp().getEpochSecond();
-//            if (339 == newPacket.length() && timeStamp == 1542297773) {
-//                System.out.println("Timestamp of length 339: " + newPacket.getTimestamp().getEpochSecond());
-//                int length = matcher.length;
-//            }
-//            if (329 == newPacket.length() && timeStamp == 1542297773) {
-//                System.out.println("Timestamp of length 329: " + newPacket.getTimestamp().getEpochSecond());
-//            }
-//            if (364 <= newPacket.length() && newPacket.length() <= 365 && timeStamp == 1542297773) {
-//                System.out.println("Timestamp of length 364-365: " + newPacket.getTimestamp().getEpochSecond());
-//            }
-//            if (1061 <= newPacket.length() && newPacket.length() <= 1070 && timeStamp == 1542297773) {
-//                System.out.println("Timestamp of length 1061-1070: " + newPacket.getTimestamp().getEpochSecond());
-//            }
-//            // TODO: DEBUGGING
-//
-//            if (matched) {
-//                if (sm.getMatchedPacketsCount() == sm.getTargetSequencePacketCount()) {
-//                    // Sequence matcher has a match. Report it to observers.
-//                    mObservers.forEach(o -> o.onMatch(this, sm.getMatchedPackets()));
-//                    // Remove the now terminated sequence matcher.
-//                    matcher[j] = null;
-//                } else {
-//                    // Sequence matcher advanced one step, so move it to its corresponding new position iff the
-//                    // packet that advanced it has a later timestamp than that of the last matched packet of the
-//                    // sequence matcher at the new index, if any. In most traces, a small amount of the packets
-//                    // appear out of order (with regards to their timestamp), which is why this check is required.
-//                    // Obviously it would not be needed if packets where guaranteed to be processed in timestamp
-//                    // order here.
-//                    if (matcher[j+1] == null ||
-//                            newPacket.getTimestamp().isAfter(matcher[j+1].getLastPacket().getTimestamp())) {
-//                        matcher[j+1] = sm;
-//                        if (matcher[j+1].getTargetUpperBound().size() == 4 && matcher[j+1].mMatchedPackets.size() > 1) {
-//                            System.out.println("Got here");
-//                        }
-//                    }
-//                }
-//                // We always want to have a sequence matcher in state 0, regardless of if the one that advanced
-//                // from state zero completed its matching or if it replaced a different one in state 1 or not.
-//                if (sm.getMatchedPacketsCount() == 1) {
-//                    matcher[j] = new Layer2RangeMatcher(sm.getTargetLowerBound(), sm.getTargetUpperBound(),
-//                            mInclusionTimeMillis, mEps);
-//                }
-//            }
-//        }
-//    }
-
     @Override
     protected List<List<PcapPacket>> pruneCluster(List<List<PcapPacket>> cluster) {
         // Note: we assume that all sequences in the input cluster are of the same length and that their packet
@@ -310,4 +274,14 @@ public class Layer2ClusterMatcher extends AbstractClusterMatcher implements Laye
             System.out.println(">>> IGNORING FLOW: " + newFlow + " <<<");
         }
     }
+
+    /**
+      * Return the maximum number of skipped packets.
+      */
+    public int getMaxSkippedPackets() {
+       return mMaxSkippedPackets;
+    }
+//    public List<Integer> getMaxSkippedPackets() {
+//        return mMaxSkippedPackets;
+//    }
 }