Extract ClusterMatcherObserver interface to separate file and move code that handles...
[pingpong.git] / Code / Projects / SmartPlugDetector / src / main / java / edu / uci / iotproject / detection / layer3 / Layer3ClusterMatcher.java
1 package edu.uci.iotproject.detection.layer3;
2
3 import edu.uci.iotproject.detection.AbstractClusterMatcher;
4 import edu.uci.iotproject.detection.ClusterMatcherObserver;
5 import edu.uci.iotproject.trafficreassembly.layer3.Conversation;
6 import edu.uci.iotproject.trafficreassembly.layer3.TcpReassembler;
7 import edu.uci.iotproject.analysis.TcpConversationUtils;
8 import edu.uci.iotproject.io.PcapHandleReader;
9 import edu.uci.iotproject.util.PrintUtils;
10 import org.pcap4j.core.*;
11
12 import java.time.ZoneId;
13 import java.util.*;
14 import java.util.stream.Collectors;
15
16 import static edu.uci.iotproject.util.PcapPacketUtils.*;
17
18 /**
19  * Searches a traffic trace for sequences of packets "belong to" a given cluster (in other words, attempts to classify
20  * traffic as pertaining to a given cluster).
21  *
22  * @author Janus Varmarken {@literal <jvarmark@uci.edu>}
23  * @author Rahmadi Trimananda {@literal <rtrimana@uci.edu>}
24  */
25 public class Layer3ClusterMatcher extends AbstractClusterMatcher implements PacketListener {
26
27     // Test client
28     public static void main(String[] args) throws PcapNativeException, NotOpenException {
29
30 //        String path = "/scratch/July-2018"; // Rahmadi
31         String path = "/Users/varmarken/temp/UCI IoT Project/experiments"; // Janus
32         final String inputPcapFile = path + "/2018-07/dlink/dlink.wlan1.local.pcap";
33         final String signatureFile = path + "/2018-07/dlink/offSignature1.sig";
34
35         List<List<PcapPacket>> signature = PrintUtils.deserializeClustersFromFile(signatureFile);
36         Layer3ClusterMatcher clusterMatcher = new Layer3ClusterMatcher(signature, null,
37                 (sig, match) -> System.out.println(
38                         String.format("[ !!! SIGNATURE DETECTED AT %s !!! ]",
39                                 match.get(0).getTimestamp().atZone(ZoneId.of("America/Los_Angeles")))
40                 )
41         );
42
43         PcapHandle handle;
44         try {
45             handle = Pcaps.openOffline(inputPcapFile, PcapHandle.TimestampPrecision.NANO);
46         } catch (PcapNativeException pne) {
47             handle = Pcaps.openOffline(inputPcapFile);
48         }
49         PcapHandleReader reader = new PcapHandleReader(handle, p -> true, clusterMatcher);
50         reader.readFromHandle();
51         clusterMatcher.performDetection();
52     }
53
54     /**
55      * The ordered directions of packets in the sequences that make up {@link #mCluster}.
56      */
57     private final Conversation.Direction[] mClusterMemberDirections;
58
59     /**
60      * For reassembling the observed traffic into TCP connections.
61      */
62     private final TcpReassembler mTcpReassembler = new TcpReassembler();
63
64     /**
65      * IP of the router's WAN port (if analyzed traffic is captured at the ISP's point of view).
66      */
67     private final String mRouterWanIp;
68
69     /**
70      * Create a {@link Layer3ClusterMatcher}.
71      * @param cluster The cluster that traffic is matched against.
72      * @param routerWanIp The router's WAN IP if examining traffic captured at the ISP's point of view (used for
73      *                    determining the direction of packets).
74      * @param detectionObservers Client code that wants to get notified whenever the {@link Layer3ClusterMatcher} detects that
75      *                          (a subset of) the examined traffic is similar to the traffic that makes up
76      *                          {@code cluster}, i.e., when the examined traffic is classified as pertaining to
77      *                          {@code cluster}.
78      */
79     public Layer3ClusterMatcher(List<List<PcapPacket>> cluster, String routerWanIp,
80                                 ClusterMatcherObserver... detectionObservers) {
81         super(cluster);
82         Objects.requireNonNull(detectionObservers, "detectionObservers cannot be null");
83         for (ClusterMatcherObserver obs : detectionObservers) {
84             addObserver(obs);
85         }
86         // Build the cluster members' direction sequence.
87         // Note: assumes that the provided cluster was captured within the local network (routerWanIp is set to null).
88         mClusterMemberDirections = getPacketDirections(cluster.get(0), null);
89         /*
90          * Enforce restriction on cluster members: all representatives must exhibit the same direction pattern and
91          * contain the same number of packets. Note that this is a somewhat heavy operation, so it may be disabled later
92          * on in favor of performance. However, it is only run once (at instantiation), so the overhead may be warranted
93          * in order to ensure correctness, especially during the development/debugging phase.
94          */
95         if (mCluster.stream().
96                 anyMatch(inner -> !Arrays.equals(mClusterMemberDirections, getPacketDirections(inner, null)))) {
97             throw new IllegalArgumentException(
98                     "cluster members must contain the same number of packets and exhibit the same packet direction " +
99                             "pattern"
100             );
101         }
102         mRouterWanIp = routerWanIp;
103     }
104
105     @Override
106     public void gotPacket(PcapPacket packet) {
107         // Present packet to TCP reassembler so that it can be mapped to a connection (if it is a TCP packet).
108         mTcpReassembler.gotPacket(packet);
109     }
110
111     /**
112      * Get the cluster that describes the packet sequence that this {@link Layer3ClusterMatcher} is searching for.
113      * @return the cluster that describes the packet sequence that this {@link Layer3ClusterMatcher} is searching for.
114      */
115     public List<List<PcapPacket>> getCluster() {
116         return mCluster;
117     }
118
119     public void performDetection() {
120         /*
121          * Let's start out simple by building a version that only works for signatures that do not span across multiple
122          * TCP conversations...
123          */
124         for (Conversation c : mTcpReassembler.getTcpConversations()) {
125             if (c.isTls() && c.getTlsApplicationDataPackets().isEmpty() || !c.isTls() && c.getPackets().isEmpty()) {
126                 // Skip empty conversations.
127                 continue;
128             }
129             for (List<PcapPacket> signatureSequence : mCluster) {
130                 if (isTlsSequence(signatureSequence) != c.isTls()) {
131                     // We consider it a mismatch if one is a TLS application data sequence and the other is not.
132                     continue;
133                 }
134                 // Fetch set of packets to examine based on TLS or not.
135                 List<PcapPacket> cPkts = c.isTls() ? c.getTlsApplicationDataPackets() : c.getPackets();
136                 /*
137                  * Note: we embed the attempt to detect the signature sequence in a loop in order to capture those cases
138                  * where the same signature sequence appears multiple times in one Conversation.
139                  *
140                  * Note: since we expect all sequences that together make up the signature to exhibit the same direction
141                  * pattern, we can simply pass the precomputed direction array for the signature sequence so that it
142                  * won't have to be recomputed internally in each call to findSubsequenceInSequence().
143                  */
144                 Optional<List<PcapPacket>> match;
145                 while ((match = findSubsequenceInSequence(signatureSequence, cPkts, mClusterMemberDirections, null)).
146                         isPresent()) {
147                     List<PcapPacket> matchSeq = match.get();
148                     // Notify observers about the match.
149                     mObservers.forEach(o -> o.onMatch(Layer3ClusterMatcher.this, matchSeq));
150                     /*
151                      * Get the index in cPkts of the last packet in the sequence of packets that matches the searched
152                      * signature sequence.
153                      */
154                     int matchSeqEndIdx = cPkts.indexOf(matchSeq.get(matchSeq.size()-1));
155                     // We restart the search for the signature sequence immediately after that index, so truncate cPkts.
156                     cPkts = cPkts.stream().skip(matchSeqEndIdx + 1).collect(Collectors.toList());
157                 }
158             }
159             /*
160              * TODO:
161              * if no item in cluster matches, also perform a distance-based matching to cover those cases where we did
162              * not manage to capture every single mutation of the sequence during training.
163              *
164              * Need to compute average/centroid of cluster to do so...? Compute within-cluster variance, then check if
165              * distance between input conversation and cluster average/centroid is smaller than or equal to the computed
166              * variance?
167              */
168         }
169     }
170
171     /**
172      * Checks if {@code sequence} is a sequence of TLS packets. Note: the current implementation relies on inspection
173      * of the port numbers when deciding between TLS vs. non-TLS. Therefore, only the first packet of {@code sequence}
174      * is examined as it is assumed that all packets in {@code sequence} pertain to the same {@link Conversation} and
175      * hence share the same set of two src/dst port numbers (albeit possibly alternating between which one is the src
176      * and which one is the dst, as packets in {@code sequence} may be in alternating directions).
177      * @param sequence The sequence of packets for which it is to be determined if it is a sequence of TLS packets or
178      *                 non-TLS packets.
179      * @return {@code true} if {@code sequence} is a sequence of TLS packets, {@code false} otherwise.
180      */
181     private boolean isTlsSequence(List<PcapPacket> sequence) {
182         // NOTE: Assumes ALL packets in sequence pertain to the same TCP connection!
183         PcapPacket firstPkt = sequence.get(0);
184         int srcPort = getSourcePort(firstPkt);
185         int dstPort = getDestinationPort(firstPkt);
186         return TcpConversationUtils.isTlsPort(srcPort) || TcpConversationUtils.isTlsPort(dstPort);
187     }
188
189     /**
190      * Examine if a given sequence of packets ({@code sequence}) contains a given shorter sequence of packets
191      * ({@code subsequence}). Note: the current implementation actually searches for a substring as it does not allow
192      * for interleaving packets in {@code sequence} that are not in {@code subsequence}; for example, if
193      * {@code subsequence} consists of packet lengths [2, 3, 5] and {@code sequence} consists of  packet lengths
194      * [2, 3, 4, 5], the result will be that there is no match (because of the interleaving 4). If we are to allow
195      * interleaving packets, we need a modified version of
196      * <a href="https://stackoverflow.com/a/20545604/1214974">this</a>.
197      *
198      * @param subsequence The sequence to search for.
199      * @param sequence The sequence to search.
200      * @param subsequenceDirections The directions of packets in {@code subsequence} such that for all {@code i},
201      *                              {@code subsequenceDirections[i]} is the direction of the packet returned by
202      *                              {@code subsequence.get(i)}. May be set to {@code null}, in which this call will
203      *                              internally compute the packet directions.
204      * @param sequenceDirections The directions of packets in {@code sequence} such that for all {@code i},
205      *                           {@code sequenceDirections[i]} is the direction of the packet returned by
206      *                           {@code sequence.get(i)}. May be set to {@code null}, in which this call will internally
207      *                           compute the packet directions.
208      *
209      * @return An {@link Optional} containing the part of {@code sequence} that matches {@code subsequence}, or an empty
210      *         {@link Optional} if no part of {@code sequence} matches {@code subsequence}.
211      */
212     private Optional<List<PcapPacket>> findSubsequenceInSequence(List<PcapPacket> subsequence,
213                                                                  List<PcapPacket> sequence,
214                                                                  Conversation.Direction[] subsequenceDirections,
215                                                                  Conversation.Direction[] sequenceDirections) {
216         if (sequence.size() < subsequence.size()) {
217             // If subsequence is longer, it cannot be contained in sequence.
218             return Optional.empty();
219         }
220         if (isTlsSequence(subsequence) != isTlsSequence(sequence)) {
221             // We consider it a mismatch if one is a TLS application data sequence and the other is not.
222             return Optional.empty();
223         }
224         // If packet directions have not been precomputed by calling code, we need to construct them.
225         if (subsequenceDirections == null) {
226             subsequenceDirections = getPacketDirections(subsequence, mRouterWanIp);
227         }
228         if (sequenceDirections == null) {
229             sequenceDirections = getPacketDirections(sequence, mRouterWanIp);
230         }
231         int subseqIdx = 0;
232         int seqIdx = 0;
233         while (seqIdx < sequence.size()) {
234             PcapPacket subseqPkt = subsequence.get(subseqIdx);
235             PcapPacket seqPkt = sequence.get(seqIdx);
236             // We only have a match if packet lengths and directions match.
237             if (subseqPkt.getOriginalLength() == seqPkt.getOriginalLength() &&
238                     subsequenceDirections[subseqIdx] == sequenceDirections[seqIdx]) {
239                 // A match; advance both indices to consider next packet in subsequence vs. next packet in sequence.
240                 subseqIdx++;
241                 seqIdx++;
242                 if (subseqIdx == subsequence.size()) {
243                     // We managed to match the entire subsequence in sequence.
244                     // Return the sublist of sequence that matches subsequence.
245                     /*
246                      * TODO:
247                      * ASSUMES THE BACKING LIST (i.e., 'sequence') IS _NOT_ STRUCTURALLY MODIFIED, hence may not work
248                      * for live traces!
249                      */
250                     return Optional.of(sequence.subList(seqIdx - subsequence.size(), seqIdx));
251                 }
252             } else {
253                 // Mismatch.
254                 if (subseqIdx > 0) {
255                     /*
256                      * If we managed to match parts of subsequence, we restart the search for subsequence in sequence at
257                      * the index of sequence where the current mismatch occurred. I.e., we must reset subseqIdx, but
258                      * leave seqIdx untouched.
259                      */
260                     subseqIdx = 0;
261                 } else {
262                     /*
263                      * First packet of subsequence didn't match packet at seqIdx of sequence, so we move forward in
264                      * sequence, i.e., we continue the search for subsequence in sequence starting at index seqIdx+1 of
265                      * sequence.
266                      */
267                     seqIdx++;
268                 }
269             }
270         }
271         return Optional.empty();
272     }
273
274     /**
275      * Given a cluster, produces a pruned version of that cluster. In the pruned version, there are no duplicate cluster
276      * members. Two cluster members are considered identical if their packets lengths and packet directions are
277      * identical. The resulting pruned cluster is unmodifiable (this applies to both the outermost list as well as the
278      * nested lists) in order to preserve its integrity when exposed to external code (e.g., through
279      * {@link #getCluster()}).
280      *
281      * @param cluster A cluster to prune.
282      * @return The resulting pruned cluster.
283      */
284     @Override
285     protected List<List<PcapPacket>> pruneCluster(List<List<PcapPacket>> cluster) {
286         List<List<PcapPacket>> prunedCluster = new ArrayList<>();
287         for (List<PcapPacket> originalClusterSeq : cluster) {
288             boolean alreadyPresent = false;
289             for (List<PcapPacket> prunedClusterSeq : prunedCluster) {
290                 Optional<List<PcapPacket>> duplicate = findSubsequenceInSequence(originalClusterSeq, prunedClusterSeq,
291                         mClusterMemberDirections, mClusterMemberDirections);
292                 if (duplicate.isPresent()) {
293                     alreadyPresent = true;
294                     break;
295                 }
296             }
297             if (!alreadyPresent) {
298                 prunedCluster.add(Collections.unmodifiableList(originalClusterSeq));
299             }
300         }
301         return Collections.unmodifiableList(prunedCluster);
302     }
303
304     /**
305      * Given a {@code List<PcapPacket>}, generate a {@code Conversation.Direction[]} such that each entry in the
306      * resulting {@code Conversation.Direction[]} specifies the direction of the {@link PcapPacket} at the corresponding
307      * index in the input list.
308      * @param packets The list of packets for which to construct a corresponding array of packet directions.
309      * @param routerWanIp The IP of the router's WAN port. This is used for determining the direction of packets when
310      *                    the traffic is captured just outside the local network (at the ISP side of the router). Set to
311      *                    {@code null} if {@code packets} stem from traffic captured within the local network.
312      * @return A {@code Conversation.Direction[]} specifying the direction of the {@link PcapPacket} at the
313      *         corresponding index in {@code packets}.
314      */
315     private static Conversation.Direction[] getPacketDirections(List<PcapPacket> packets, String routerWanIp) {
316         Conversation.Direction[] directions = new Conversation.Direction[packets.size()];
317         for (int i = 0; i < packets.size(); i++) {
318             PcapPacket pkt = packets.get(i);
319             if (getSourceIp(pkt).equals(getDestinationIp(pkt))) {
320                 // Sanity check: we shouldn't be processing loopback traffic
321                 throw new AssertionError("loopback traffic detected");
322             }
323             if (isSrcIpLocal(pkt) || getSourceIp(pkt).equals(routerWanIp)) {
324                 directions[i] = Conversation.Direction.CLIENT_TO_SERVER;
325             } else if (isDstIpLocal(pkt) || getDestinationIp(pkt).equals(routerWanIp)) {
326                 directions[i] = Conversation.Direction.SERVER_TO_CLIENT;
327             } else {
328                 throw new IllegalArgumentException("no local IP or router WAN port IP found, can't detect direction");
329             }
330         }
331         return directions;
332     }
333
334 }