From 2faef4940976a927c5983a51a7824a3e01d5354a Mon Sep 17 00:00:00 2001 From: rtrimana Date: Tue, 19 Mar 2019 10:04:10 -0700 Subject: [PATCH] Fixing bug in Layer 2 matching. --- .../layer2/Layer2ClusterMatcher.java | 158 +++++++++++++----- .../detection/layer2/Layer2RangeMatcher.java | 22 ++- 2 files changed, 132 insertions(+), 48 deletions(-) diff --git a/Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2ClusterMatcher.java b/Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2ClusterMatcher.java index a3f4d0e..ab5f148 100644 --- a/Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2ClusterMatcher.java +++ b/Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2ClusterMatcher.java @@ -12,6 +12,7 @@ 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; /** @@ -28,7 +29,8 @@ 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 mPerFlowSeqMatchers = new HashMap<>(); - private final Map mPerFlowRangeMatcher = new HashMap<>(); +// private final Map mPerFlowRangeMatcher = new HashMap<>(); + private final Map> mPerFlowRangeMatcher = new HashMap<>(); private final Function mFlowFilter; @@ -144,57 +146,133 @@ 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. + // 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 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()]; + // If this is the first time we encounter this flow, we need to set up a list of sequence matchers. + List listMatchers = new ArrayList<>(); // Prepare a "state 0" sequence matcher. - matcher[0] = new Layer2RangeMatcher(mCluster.get(0), mCluster.get(1), mInclusionTimeMillis, mEps); + 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, matcher); + mPerFlowRangeMatcher.put(flow, listMatchers); } // 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; + List 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; } - 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())); - // 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; + } + // 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 + List 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()) { + // 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); } } - // 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); - } } } } +// 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> pruneCluster(List> cluster) { // Note: we assume that all sequences in the input cluster are of the same length and that their packet diff --git a/Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2RangeMatcher.java b/Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2RangeMatcher.java index eb3b34e..32bb732 100644 --- a/Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2RangeMatcher.java +++ b/Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer2/Layer2RangeMatcher.java @@ -71,12 +71,18 @@ public class Layer2RangeMatcher extends Layer2AbstractMatcher { // Get representative of the packet we expect to match next. PcapPacket expectedLowerBound = mLowerBound.get(mMatchedPackets.size()); PcapPacket expectedUpperBound = mUpperBound.get(mMatchedPackets.size()); + int lowerBound = expectedLowerBound.getOriginalLength(); + int upperBound = expectedUpperBound.getOriginalLength(); +// int lowerBound = expectedLowerBound.getOriginalLength() - (int) mEps; +// int upperBound = expectedUpperBound.getOriginalLength() + (int) mEps; + // Do strict matching if the lower and upper bounds are the same length + // Do range matching with eps otherwise + if (lowerBound != upperBound) { + lowerBound = lowerBound - (int) mEps; + upperBound = upperBound + (int) mEps; + } // First verify if the received packet has the length we're looking for (the length should be within the range). - if (expectedLowerBound.getOriginalLength() - (int) mEps <= packet.getOriginalLength() && - packet.getOriginalLength() <= expectedUpperBound.getOriginalLength() + (int) mEps){ - // TODO: TEMPORARILY WITHOUT EPS -// if (expectedLowerBound.getOriginalLength() <= packet.getOriginalLength() && -// packet.getOriginalLength() <= expectedUpperBound.getOriginalLength()){ + if (lowerBound <= packet.getOriginalLength() && packet.getOriginalLength() <= upperBound){ // If this is the first packet, we only need to verify that its length is correct. Time constraints are // obviously satisfied as there are no previous packets. Furthermore, direction matches by definition as we // don't know the MAC of the device (or phone) in advance, so we can't enforce a rule saying "first packet @@ -94,8 +100,8 @@ public class Layer2RangeMatcher extends Layer2AbstractMatcher { return false; } // Next apply timing constraints: - // 1: to be a match, the packet must have a later timestamp than any other packet currently matched - // 2: does adding the packet cause the max allowed time between first packet and last packet to be exceeded? + // 1) to be a match, the packet must have a later timestamp than any other packet currently matched + // 2) does adding the packet cause the max allowed time between first packet and last packet to be exceeded? if (!packet.getTimestamp().isAfter(mMatchedPackets.get(getMatchedPacketsCount()-1).getTimestamp())) { return false; } @@ -125,6 +131,6 @@ public class Layer2RangeMatcher extends Layer2AbstractMatcher { } public List getTargetUpperBound() { - return mLowerBound; + return mUpperBound; } } -- 2.34.1