+ /**
+ * Overload the same method with relaxed matching.
+ *
+ * @param subsequence The sequence to search for.
+ * @param sequence The sequence to search.
+ * @param subsequenceDirections The directions of packets in {@code subsequence} such that for all {@code i},
+ * {@code subsequenceDirections[i]} is the direction of the packet returned by
+ * {@code subsequence.get(i)}. May be set to {@code null}, in which this call will
+ * internally compute the packet directions.
+ * @param sequenceDirections The directions of packets in {@code sequence} such that for all {@code i},
+ * {@code sequenceDirections[i]} is the direction of the packet returned by
+ * {@code sequence.get(i)}. May be set to {@code null}, in which this call will internally
+ * compute the packet directions.
+ * @param delta The delta for relaxed matching
+ * @param packetSet The set of unique packet lengths, whose matching is to be relaxed
+ *
+ * @return An {@link Optional} containing the part of {@code sequence} that matches {@code subsequence}, or an empty
+ * {@link Optional} if no part of {@code sequence} matches {@code subsequence}.
+ */
+ private Optional<List<PcapPacket>> findSubsequenceInSequence(List<PcapPacket> subsequence,
+ List<PcapPacket> sequence,
+ Conversation.Direction[] subsequenceDirections,
+ Conversation.Direction[] sequenceDirections,
+ int delta,
+ Set<Integer> packetSet) {
+ if (sequence.size() < subsequence.size()) {
+ // If subsequence is longer, it cannot be contained in sequence.
+ return Optional.empty();
+ }
+ if (isTlsSequence(subsequence) != isTlsSequence(sequence)) {
+ // We consider it a mismatch if one is a TLS application data sequence and the other is not.
+ return Optional.empty();
+ }
+ // If packet directions have not been precomputed by calling code, we need to construct them.
+ if (subsequenceDirections == null) {
+ subsequenceDirections = getPacketDirections(subsequence, mRouterWanIp);
+ }
+ if (sequenceDirections == null) {
+ sequenceDirections = getPacketDirections(sequence, mRouterWanIp);
+ }
+ int subseqIdx = 0;
+ int seqIdx = 0;
+ while (seqIdx < sequence.size()) {
+ PcapPacket subseqPkt = subsequence.get(subseqIdx);
+ PcapPacket seqPkt = sequence.get(seqIdx);
+ // We only have a match if packet lengths and directions match.
+ // Do relaxed matching here if applicable
+ if ((delta > 0 && packetSet.contains(subseqPkt.getOriginalLength()) &&
+ subseqPkt.getOriginalLength() - delta <= seqPkt.getOriginalLength() &&
+ seqPkt.getOriginalLength() <= subseqPkt.getOriginalLength() + delta &&
+ subsequenceDirections[subseqIdx] == sequenceDirections[seqIdx]) ||
+ // Or just exact matching
+ (subseqPkt.getOriginalLength() == seqPkt.getOriginalLength() &&
+ subsequenceDirections[subseqIdx] == sequenceDirections[seqIdx])) {
+ // A match; advance both indices to consider next packet in subsequence vs. next packet in sequence.
+ subseqIdx++;
+ seqIdx++;
+ if (subseqIdx == subsequence.size()) {
+ // We managed to match the entire subsequence in sequence.
+ // Return the sublist of sequence that matches subsequence.
+ /*
+ * TODO:
+ * ASSUMES THE BACKING LIST (i.e., 'sequence') IS _NOT_ STRUCTURALLY MODIFIED, hence may not work
+ * for live traces!
+ */
+ return Optional.of(sequence.subList(seqIdx - subsequence.size(), seqIdx));
+ }
+ } else {
+ // Mismatch.
+ if (subseqIdx > 0) {
+ /*
+ * If we managed to match parts of subsequence, we restart the search for subsequence in sequence at
+ * the index of sequence where the current mismatch occurred. I.e., we must reset subseqIdx, but
+ * leave seqIdx untouched.
+ */
+ subseqIdx = 0;
+ } else {
+ /*
+ * First packet of subsequence didn't match packet at seqIdx of sequence, so we move forward in
+ * sequence, i.e., we continue the search for subsequence in sequence starting at index seqIdx+1 of
+ * sequence.
+ */
+ seqIdx++;
+ }
+ }
+ }
+ return Optional.empty();
+ }
+