+ // Update the maximum number of skipped packets
+ private void updateMaxSkippedPackets(List<PcapPacket> flowPackets, List<PcapPacket> matchedPackets) {
+ // Count number of skipped packets by looking into
+ // the difference of indices of two matched packets
+ 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;
+// }
+ mMaxSkippedPackets.add(skippedPackets);
+ }
+ }
+
+ 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).
+ if (mPerFlowRangeMatcher.get(flow) == null) {
+ // If this is the first time we encounter this flow, we need to set up a list of sequence matchers.
+ List<Layer2RangeMatcher> listMatchers = new ArrayList<>();
+ // Prepare a "state 0" sequence matcher.
+ Layer2RangeMatcher matcher = new Layer2RangeMatcher(mCluster.get(0), mCluster.get(1),
+ mInclusionTimeMillis, mEps);
+ listMatchers.add(matcher);
+ // Associate the new sequence matcher table with the new flow.
+ mPerFlowRangeMatcher.put(flow, listMatchers);
+ }
+ // Fetch table that contains sequence matchers for this flow.
+ List<Layer2RangeMatcher> listMatchers = mPerFlowRangeMatcher.get(flow);
+ // Add a new matcher if all matchers have already advanced to the next stage.
+ // We always need a new matcher to match from NO packets.
+ boolean addOneArray = true;
+ for(Layer2RangeMatcher matcher : listMatchers) {
+ if (matcher.getMatchedPacketsCount() == 0) {
+ addOneArray = false;
+ }
+ }
+ // Add the new matcher into the list
+ if (addOneArray) {
+ Layer2RangeMatcher newMatcher = new Layer2RangeMatcher(mCluster.get(0), mCluster.get(1),
+ mInclusionTimeMillis, mEps);
+ 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.
+ // 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;
+ // Check if no packets are matched yet or if there are matched packets, the next packet to be matched
+ // has to be later than the last matched packet.
+ // 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 (sm.getMatchedPacketsCount() == 0 ||
+ newPacket.getTimestamp().isAfter(sm.getLastPacket().getTimestamp())) {
+ boolean matched = sm.matchPacket(newPacket);
+ if (matched) {
+ if (sm.getMatchedPacketsCount() == sm.getTargetSequencePacketCount()) {
+ // Update maximum skipped packets
+ updateMaxSkippedPackets(flow.getPackets(), sm.getMatchedPackets());
+ // 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);
+ }
+ }
+ }
+ }
+ }