+ /**
+ * Check if there is any overlap between the signature stored in this class and another signature.
+ * Conditions:
+ * 1) If both signatures do not have any range, then we need to do conservative checking (return true).
+ * 2) If both signatures have the same number of packets/packet lengths, then we check the range; if the
+ * numbers of packets/packet lengths are different then we assume that there is no overlap.
+ * 3) If there is any range in the signatures, then we need to check for overlap.
+ * 4) If there is overlap for every packet/packet length, then we return false (range-based checking); otherwise,
+ * true (conservative checking).
+ *
+ * @param otherSignature A {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects to be checked
+ * for overlaps with the signature stored in this class.
+ * @return A boolean that is true if there is an overlap; false otherwise.
+ */
+ public boolean isConservativeChecking(List<List<List<PcapPacket>>> otherSignature) {
+
+ // Get the ranges of the two signatures
+ List<List<List<PcapPacket>>> signatureRanges = getSequenceRanges(mSignature);
+ List<List<List<PcapPacket>>> otherSignatureRanges = getSequenceRanges(otherSignature);
+ if (!isRangeBased(signatureRanges) && !isRangeBased(otherSignatureRanges)) {
+ // Conservative checking when there is no range
+ return true;
+ } else if(signatureRanges.size() != otherSignatureRanges.size()) {
+ // The two signatures have different numbers of packets/packet lengths
+ return false;
+ } else {
+ // There is range; check if there is overlap
+ return checkOverlap(signatureRanges, otherSignatureRanges);
+ }
+ }
+
+ /*
+ * Check for overlap since we have range in at least one of the signatures.
+ * Overlap is only true when all ranges overlap. We need to check in order.
+ */
+ private boolean checkOverlap(List<List<List<PcapPacket>>> signatureRanges,
+ List<List<List<PcapPacket>>> otherSignatureRanges) {
+
+ for(List<List<PcapPacket>> listListPcapPacket : signatureRanges) {
+ // Lower bound of the range is in index 0
+ // Upper bound of the range is in index 1
+ int sequenceSetIndex = signatureRanges.indexOf(listListPcapPacket);
+ List<PcapPacket> minSequenceSignature = listListPcapPacket.get(0);
+ List<PcapPacket> maxSequenceSignature = listListPcapPacket.get(1);
+ for(PcapPacket pcapPacket : minSequenceSignature) {
+ // Get the lower and upper bounds of the current signature
+ int packetIndex = minSequenceSignature.indexOf(pcapPacket);
+ int lowerBound = pcapPacket.length();
+ int upperBound = maxSequenceSignature.get(packetIndex).length();
+ // Check for range overlap in the other signature!
+ // Check the packet/packet length at the same position
+ List<PcapPacket> minSequenceSignatureOther = otherSignatureRanges.get(sequenceSetIndex).get(0);
+ List<PcapPacket> maxSequenceSignatureOther = otherSignatureRanges.get(sequenceSetIndex).get(1);
+ int lowerBoundOther = minSequenceSignatureOther.get(packetIndex).length();
+ int upperBoundOther = maxSequenceSignatureOther.get(packetIndex).length();
+ if (!(lowerBoundOther <= lowerBound && lowerBound <= upperBoundOther) &&
+ !(lowerBoundOther <= upperBound && upperBound <= upperBoundOther)) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+ }
+
+ /*
+ * Check and see if there is any range in the signatures
+ */
+ private boolean isRangeBased(List<List<List<PcapPacket>>> signatureRanges) {
+
+ for(List<List<PcapPacket>> listListPcapPacket : signatureRanges) {
+ // Lower bound of the range is in index 0
+ // Upper bound of the range is in index 1
+ List<PcapPacket> minSequence = listListPcapPacket.get(0);
+ List<PcapPacket> maxSequence = listListPcapPacket.get(1);
+ for(PcapPacket pcapPacket : minSequence) {
+ int index = minSequence.indexOf(pcapPacket);
+ if (pcapPacket.length() != maxSequence.get(index).length()) {
+ // If there is any packet length that differs in the minSequence
+ // and maxSequence, then it is range-based
+ return true;
+ }
+ }
+ }
+
+ return false;
+ }
+
+ /* Find the sequence with the minimum packet lengths.
+ * The second-layer list should contain the minimum sequence for element 0 and maximum sequence for element 1.
+ */
+ private List<List<List<PcapPacket>>> getSequenceRanges(List<List<List<PcapPacket>>> signature) {
+
+ // Start from the first index
+ List<List<List<PcapPacket>>> rangeBasedSequence = new ArrayList<>();
+ for(List<List<PcapPacket>> listListPcapPacket : signature) {
+ List<List<PcapPacket>> minMaxSequence = new ArrayList<>();
+ // Both searches start from index 0
+ List<PcapPacket> minSequence = new ArrayList<>(listListPcapPacket.get(0));
+ List<PcapPacket> maxSequence = new ArrayList<>(listListPcapPacket.get(0));
+ for(List<PcapPacket> listPcapPacket : listListPcapPacket) {
+ for(PcapPacket pcapPacket : listPcapPacket) {
+ int index = listPcapPacket.indexOf(pcapPacket);
+ // Set the new minimum if length at the index is minimum
+ if (pcapPacket.length() < minSequence.get(index).length()) {
+ minSequence.set(index, pcapPacket);
+ }
+ // Set the new maximum if length at the index is maximum
+ if (pcapPacket.length() > maxSequence.get(index).length()) {
+ maxSequence.set(index, pcapPacket);
+ }
+ }
+ }
+ // minSequence as element 0 and maxSequence as element 1
+ minMaxSequence.add(minSequence);
+ minMaxSequence.add(maxSequence);
+ rangeBasedSequence.add(minMaxSequence);
+ }
+
+ return rangeBasedSequence;
+ }
+