import java.util.HashMap;
import java.util.List;
import java.util.Map;
-import java.util.concurrent.CopyOnWriteArrayList;
import java.util.function.Function;
/**
* 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;
private int mInclusionTimeMillis;
+ /**
+ * Keeping track of maximum number of skipped packets
+ */
+ private int mMaxSkippedPackets;
+ private List<Integer> mSkippedPackets;
+
+ 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);
}
/**
* @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;
+ mSkippedPackets = new ArrayList<>();
+ // Give integer's MAX_VALUE if -1
+ mLimitSkippedPackets = limitSkippedPackets == -1 ? Integer.MAX_VALUE : limitSkippedPackets;
}
@Override
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 {
}
}
+ // 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;
+ }
+ if (mLimitSkippedPackets < skippedPackets) {
+ stillMatch = false;
+ }
+ mSkippedPackets.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).
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;
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);
}
}
}
-// 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
System.out.println(">>> IGNORING FLOW: " + newFlow + " <<<");
}
}
+
+ /**
+ * Return the maximum number of skipped packets.
+ */
+ public int getMaxSkippedPackets() {
+ return mMaxSkippedPackets;
+ }
+
+ /**
+ * Return the numbers of skipped packets.
+ */
+ public List<Integer> getSkippedPackets() {
+ return mSkippedPackets;
+ }
}
projects / pingpong.git / blobdiff