Renaming root project name.
[pingpong.git] / Code / Projects / SmartPlugDetector / src / main / java / edu / uci / iotproject / analysis / TcpConversationUtils.java
1 package edu.uci.iotproject.analysis;
2
3 import edu.uci.iotproject.trafficreassembly.layer3.Conversation;
4 import edu.uci.iotproject.DnsMap;
5 import edu.uci.iotproject.util.PcapPacketUtils;
6 import org.pcap4j.core.PcapPacket;
7 import org.pcap4j.packet.IpV4Packet;
8 import org.pcap4j.packet.TcpPacket;
9
10 import java.util.*;
11 import java.util.stream.Collectors;
12 import java.util.stream.Stream;
13
14 import static edu.uci.iotproject.util.PcapPacketUtils.*;
15
16 /**
17  * Utility functions for analyzing and structuring (sets of) {@link Conversation}s.
18  *
19  * @author Janus Varmarken {@literal <jvarmark@uci.edu>}
20  * @author Rahmadi Trimananda {@literal <rtrimana@uci.edu>}
21  */
22 public class TcpConversationUtils {
23
24     /**
25      * Identifies the adjacency type of the signature for merging.
26      */
27     public enum SignaturePosition {
28         NOT_ADJACENT,
29         LEFT_ADJACENT,
30         RIGHT_ADJACENT
31     }
32
33     /**
34      * <p>
35      *      Given a {@link Conversation}, extract its set of "packet pairs", i.e., pairs of request-reply packets.
36      *      <em>The extracted pairs are formed from the full set of payload-carrying TCP packets.</em>
37      * </p>
38      *
39      * <b>Note:</b> in the current implementation, if one endpoint sends multiple packets back-to-back with no
40      * interleaved reply packets from the other endpoint, such packets are converted to one-item pairs (i.e., instances
41      * of {@link PcapPacketPair} where {@link PcapPacketPair#getSecond()} is {@code null}).
42      *
43      * @param conv The {@code Conversation} for which packet pairs are to be extracted.
44      * @return The packet pairs extracted from {@code conv}.
45      */
46     public static List<PcapPacketPair> extractPacketPairs(Conversation conv) {
47         return extractPacketPairs(conv.getPackets());
48     }
49
50
51     /**
52      * <p>
53      *      Given a {@link Conversation}, extract its set of "packet pairs", i.e., pairs of request-reply packets.
54      *      <em>The extracted pairs are formed from the full set of TLS Application Data packets.</em>
55      * </p>
56      *
57      * <b>Note:</b> in the current implementation, if one endpoint sends multiple packets back-to-back with no
58      * interleaved reply packets from the other endpoint, such packets are converted to one-item pairs (i.e., instances
59      * of {@link PcapPacketPair} where {@link PcapPacketPair#getSecond()} is {@code null}).
60      *
61      * @param conv The {@code Conversation} for which packet pairs are to be extracted.
62      * @return The packet pairs extracted from {@code conv}.
63      */
64     public static List<PcapPacketPair> extractTlsAppDataPacketPairs(Conversation conv) {
65         if (!conv.isTls()) {
66             throw new IllegalArgumentException(String.format("Provided %s argument is not a TLS session"));
67         }
68         return extractPacketPairs(conv.getTlsApplicationDataPackets());
69     }
70
71     // Helper method for implementing the public API of similarly named methods.
72     private static List<PcapPacketPair> extractPacketPairs(List<PcapPacket> packets) {
73         List<PcapPacketPair> pairs = new ArrayList<>();
74 //        for(PcapPacket pp : packets) {
75 //            System.out.print(pp.length() + " ");
76 //        }
77 //        System.out.println();
78
79         int i = 0;
80         while (i < packets.size()) {
81             PcapPacket p1 = packets.get(i);
82             String p1SrcIp = p1.get(IpV4Packet.class).getHeader().getSrcAddr().getHostAddress();
83             int p1SrcPort = p1.get(TcpPacket.class).getHeader().getSrcPort().valueAsInt();
84             if (i+1 < packets.size()) {
85                 PcapPacket p2 = packets.get(i+1);
86                 if (PcapPacketUtils.isSource(p2, p1SrcIp, p1SrcPort)) {
87                     // Two packets in a row going in the same direction -> create one item pair for p1
88                     pairs.add(new PcapPacketPair(p1, null));
89                     // Advance one packet as the following two packets may form a valid two-item pair.
90                     i++;
91                 } else {
92                     // The two packets form a response-reply pair, create two-item pair.
93                     pairs.add(new PcapPacketPair(p1, p2));
94                     // Advance two packets as we have already processed the packet at index i+1 in order to create the pair.
95                     i += 2;
96                     //i++;
97                 }
98             } else {
99                 // Last packet of conversation => one item pair
100                 pairs.add(new PcapPacketPair(p1, null));
101                 // Advance i to ensure termination.
102                 i++;
103             }
104         }
105         return pairs;
106         // TODO: what if there is long time between response and reply packet? Should we add a threshold and exclude those cases?
107     }
108
109     /**
110      * Given a collection of TCP conversations and associated DNS mappings, groups the conversations by hostname.
111      * @param tcpConversations The collection of TCP conversations.
112      * @param ipHostnameMappings The associated DNS mappings.
113      * @return A map where each key is a hostname and its associated value is a list of conversations where one of the
114      *         two communicating hosts is that hostname (i.e. its IP maps to the hostname).
115      */
116     public static Map<String, List<Conversation>> groupConversationsByHostname(Collection<Conversation> tcpConversations, DnsMap ipHostnameMappings) {
117         HashMap<String, List<Conversation>> result = new HashMap<>();
118         for (Conversation c : tcpConversations) {
119             if (c.getPackets().size() == 0) {
120                 String warningStr = String.format("Detected a %s [%s] with no payload packets.",
121                         c.getClass().getSimpleName(), c.toString());
122                 System.err.println(warningStr);
123                 continue;
124             }
125             IpV4Packet firstPacketIp = c.getPackets().get(0).get(IpV4Packet.class);
126             String ipSrc = firstPacketIp.getHeader().getSrcAddr().getHostAddress();
127             String ipDst = firstPacketIp.getHeader().getDstAddr().getHostAddress();
128             // Check if src or dst IP is associated with one or more hostnames.
129             Set<String> hostnames = ipHostnameMappings.getHostnamesForIp(ipSrc);
130             if (hostnames == null) {
131                 // No luck with src ip (possibly because it's a client->srv packet), try dst ip.
132                 hostnames = ipHostnameMappings.getHostnamesForIp(ipDst);
133             }
134             if (hostnames != null) {
135                 // Put a reference to the conversation for each of the hostnames that the conversation's IP maps to.
136                 for (String hostname : hostnames) {
137                     List<Conversation> newValue = new ArrayList<>();
138                     newValue.add(c);
139                     result.merge(hostname, newValue, (l1, l2) -> { l1.addAll(l2); return l1; });
140                 }
141                 if (hostnames.size() > 1) {
142                     // Print notice of IP mapping to multiple hostnames (debugging)
143                     System.err.println(String.format("%s: encountered an IP that maps to multiple (%d) hostnames",
144                             TcpConversationUtils.class.getSimpleName(), hostnames.size()));
145                 }
146             } else {
147                 // If no hostname mapping, store conversation under the key that is the concatenation of the two IPs.
148                 // In order to ensure consistency when mapping conversations, use lexicographic order to select which IP
149                 // goes first.
150                 String delimiter = "_";
151                 // Note that the in case the comparison returns 0, the strings are equal, so it doesn't matter which of
152                 // ipSrc and ipDst go first (also, this case should not occur in practice as it means that the device is
153                 // communicating with itself!)
154                 String key = ipSrc.compareTo(ipDst) <= 0 ? ipSrc + delimiter + ipDst : ipDst + delimiter + ipSrc;
155                 List<Conversation> newValue = new ArrayList<>();
156                 newValue.add(c);
157                 result.merge(key, newValue, (l1, l2) -> { l1.addAll(l2); return l1; });
158             }
159         }
160         return result;
161     }
162
163     public static Map<String, Integer> countPacketSequenceFrequencies(Collection<Conversation> conversations) {
164         Map<String, Integer> result = new HashMap<>();
165         for (Conversation conv : conversations) {
166             if (conv.getPackets().size() == 0) {
167                 // Skip conversations with no payload packets.
168                 continue;
169             }
170             StringBuilder sb = new StringBuilder();
171             for (PcapPacket pp : conv.getPackets()) {
172                 sb.append(pp.length() + " ");
173             }
174             result.merge(sb.toString(), 1, (i1, i2) -> i1+i2);
175         }
176         return result;
177     }
178
179     /**
180      * Given a {@link Collection} of {@link Conversation}s, builds a {@link Map} from {@link String} to {@link List}
181      * of {@link Conversation}s such that each key is the <em>concatenation of the packet lengths of all payload packets
182      * (i.e., the set of packets returned by {@link Conversation#getPackets()}) separated by a delimiter</em> of any
183      * {@link Conversation} pointed to by that key. In other words, what the {@link Conversation}s {@code cs} pointed to
184      * by the key {@code s} have in common is that they all contain exactly the same number of payload packets <em>and
185      * </em> these payload packets are identical across all {@code Conversation}s in {@code cs} in terms of packet
186      * length and packet order. For example, if the key is "152 440 550", this means that every individual
187      * {@code Conversation} in the list of {@code Conversation}s pointed to by that key contain exactly three payload
188      * packet of lengths 152, 440, and 550, and these three packets are ordered in the order prescribed by the key.
189      *
190      * @param conversations The collection of {@code Conversation}s to group by packet sequence.
191      * @param verbose If set to {@code true}, the grouping (and therefore the key) will also include SYN/SYNACK,
192      *                FIN/FINACK, RST packets, and each payload-carrying packet will have an indication of the direction
193      *                of the packet prepended.
194      * @return a {@link Map} from {@link String} to {@link List} of {@link Conversation}s such that each key is the
195      *         <em>concatenation of the packet lengths of all payload packets (i.e., the set of packets returned by
196      *         {@link Conversation#getPackets()}) separated by a delimiter</em> of any {@link Conversation} pointed to
197      *         by that key.
198      */
199     public static Map<String, List<Conversation>> groupConversationsByPacketSequence(Collection<Conversation> conversations, boolean verbose) {
200         return conversations.stream().collect(Collectors.groupingBy(c -> toSequenceString(c, verbose)));
201     }
202
203     public static Map<String, List<Conversation>> groupConversationsByTlsApplicationDataPacketSequence(Collection<Conversation> conversations) {
204         return conversations.stream().collect(Collectors.groupingBy(
205                 c -> c.getTlsApplicationDataPackets().stream().map(p -> Integer.toString(p.getOriginalLength())).
206                         reduce("", (s1, s2) -> s1.length() == 0 ? s2 : s1 + " " + s2))
207         );
208     }
209
210     /**
211      * Given a {@link Conversation}, counts the frequencies of each unique packet length seen as part of the
212      * {@code Conversation}.
213      * @param c The {@code Conversation} for which unique packet length frequencies are to be determined.
214      * @return A mapping from packet length to its frequency.
215      */
216     public static Map<Integer, Integer> countPacketLengthFrequencies(Conversation c) {
217         Map<Integer, Integer> result = new HashMap<>();
218         for (PcapPacket packet : c.getPackets()) {
219             result.merge(packet.length(), 1, (i1, i2) -> i1 + i2);
220         }
221         return result;
222     }
223
224     /**
225      * Like {@link #countPacketLengthFrequencies(Conversation)}, but counts packet length frequencies for a collection
226      * of {@code Conversation}s, i.e., the frequency of a packet length becomes the total number of packets with that
227      * length across <em>all</em> {@code Conversation}s in {@code conversations}.
228      * @param conversations The collection of {@code Conversation}s for which packet length frequencies are to be
229      *                      counted.
230      * @return A mapping from packet length to its frequency.
231      */
232     public static Map<Integer, Integer> countPacketLengthFrequencies(Collection<Conversation> conversations) {
233         Map<Integer, Integer> result = new HashMap<>();
234         for (Conversation c : conversations) {
235             Map<Integer, Integer> intermediateResult = countPacketLengthFrequencies(c);
236             for (Map.Entry<Integer, Integer> entry : intermediateResult.entrySet()) {
237                 result.merge(entry.getKey(), entry.getValue(), (i1, i2) -> i1 + i2);
238             }
239         }
240         return result;
241     }
242
243     public static Map<String, Integer> countPacketPairFrequencies(Collection<PcapPacketPair> pairs) {
244         Map<String, Integer> result = new HashMap<>();
245         for (PcapPacketPair ppp : pairs) {
246             result.merge(ppp.toString(), 1, (i1, i2) -> i1 + i2);
247         }
248         return result;
249     }
250
251     public static Map<String, Map<String, Integer>> countPacketPairFrequenciesByHostname(Collection<Conversation> tcpConversations, DnsMap ipHostnameMappings) {
252         Map<String, List<Conversation>> convsByHostname = groupConversationsByHostname(tcpConversations, ipHostnameMappings);
253         HashMap<String, Map<String, Integer>> result = new HashMap<>();
254         for (Map.Entry<String, List<Conversation>> entry : convsByHostname.entrySet()) {
255             // Merge all packet pairs exchanged during the course of all conversations with hostname into one list
256             List<PcapPacketPair> allPairsExchangedWithHostname = new ArrayList<>();
257             entry.getValue().forEach(conversation -> allPairsExchangedWithHostname.addAll(extractPacketPairs(conversation)));
258             // Then count the frequencies of packet pairs exchanged with the hostname, irrespective of individual
259             // conversations
260             result.put(entry.getKey(), countPacketPairFrequencies(allPairsExchangedWithHostname));
261         }
262         return result;
263     }
264
265     /**
266      * Given a {@link Conversation}, extract its packet length sequence.
267      * @param c The {@link Conversation} from which a packet length sequence is to be extracted.
268      * @return An {@code Integer[]} that holds the packet lengths of all payload-carrying packets in {@code c}. The
269      *         packet lengths in the returned array are ordered by packet timestamp.
270      */
271     public static Integer[] getPacketLengthSequence(Conversation c) {
272         return getPacketLengthSequence(c.getPackets());
273     }
274
275
276     /**
277      * Given a {@link Conversation}, extract its packet length sequence, but only include packet lengths of those
278      * packets that carry TLS Application Data.
279      * @param c The {@link Conversation} from which a TLS Application Data packet length sequence is to be extracted.
280      * @return An {@code Integer[]} that holds the packet lengths of all packets in {@code c} that carry TLS Application
281      *         Data. The packet lengths in the returned array are ordered by packet timestamp.
282      */
283     public static Integer[] getPacketLengthSequenceTlsAppDataOnly(Conversation c) {
284         if (!c.isTls()) {
285             throw new IllegalArgumentException("Provided " + c.getClass().getSimpleName() + " was not a TLS session");
286         }
287         return getPacketLengthSequence(c.getTlsApplicationDataPackets());
288     }
289
290     /**
291      * Given a list of packets, extract the packet lengths and wrap them in an array such that the packet lengths in the
292      * resulting array appear in the same order as their corresponding packets in the input list.
293      * @param packets The list of packets for which the packet lengths are to be extracted.
294      * @return An array containing the packet lengths in the same order as their corresponding packets in the input list.
295      */
296     private static Integer[] getPacketLengthSequence(List<PcapPacket> packets) {
297         return packets.stream().map(pkt -> pkt.getOriginalLength()).toArray(Integer[]::new);
298     }
299
300     /**
301      * Builds a string representation of the sequence of packets exchanged as part of {@code c}.
302      * @param c The {@link Conversation} for which a string representation of the packet sequence is to be constructed.
303      * @param verbose {@code true} if set to true, the returned sequence string will also include SYN/SYNACK,
304      *                FIN/FINACK, RST packets, as well as an indication of the direction of payload-carrying packets.
305      * @return a string representation of the sequence of packets exchanged as part of {@code c}.
306      */
307     private static String toSequenceString(Conversation c, boolean verbose) {
308         // Payload-parrying packets are always included, but only prepend direction if verbose output is chosen.
309         Stream<String> s = c.getPackets().stream().map(p -> verbose ? c.getDirection(p).toCompactString() + p.getOriginalLength() : Integer.toString(p.getOriginalLength()));
310         if (verbose) {
311             // In the verbose case, we also print SYN, FIN and RST packets.
312             // Convert the SYN packets to a string representation and prepend them in front of the payload packets.
313             s = Stream.concat(c.getSynPackets().stream().map(p -> isSyn(p) && isAck(p) ? "SYNACK" : "SYN"), s);
314             // Convert the FIN packets to a string representation and append them after the payload packets.
315             s = Stream.concat(s, c.getFinAckPairs().stream().map(f -> f.isAcknowledged() ? "FINACK" : "FIN"));
316             // Convert the RST packets to a string representation and append at the end.
317             s = Stream.concat(s, c.getRstPackets().stream().map(r -> "RST"));
318         }
319         /*
320          * Note: the collector internally uses a StringBuilder, which is more efficient than simply doing string
321          * concatenation as in the following example:
322          * s.reduce("", (s1, s2) -> s1.length() == 0 ? s2 : s1 + " " + s2);
323          * (above code is O(N^2) where N is the number of characters)
324          */
325         return s.collect(Collectors.joining(" "));
326     }
327
328     /**
329      * Set of port numbers that we consider TLS traffic.
330      * Note: purposefully initialized as a {@link HashSet} to get O(1) {@code contains()} call.
331      */
332     private static final Set<Integer> TLS_PORTS = Stream.of(443, 8443, 41143).
333             collect(Collectors.toCollection(HashSet::new));
334
335     /**
336      * Check if a given port number is considered a TLS port.
337      * @param port The port number to check.
338      * @return {@code true} if the port number is considered a TLS port, {@code false} otherwise.
339      */
340     public static boolean isTlsPort(int port) {
341         return TLS_PORTS.contains(port);
342     }
343
344     /**
345      * Appends a space to {@code sb} <em>iff</em> {@code sb} already contains some content.
346      * @param sb A {@link StringBuilder} that should have a space appended <em>iff</em> it is not empty.
347      */
348     private static void appendSpaceIfNotEmpty(StringBuilder sb) {
349         if (sb.length() != 0) {
350             sb.append(" ");
351         }
352     }
353
354     /**
355      * Given a list of {@link Conversation} objects, sort them by timestamps.
356      * @param conversations The list of {@link Conversation} objects to be sorted.
357      * @return A sorted list of {@code Conversation} based on timestamps of the first
358      *          packet in the {@code Conversation}.
359      */
360     public static List<Conversation> sortConversationList(List<Conversation> conversations) {
361         // Get rid of Conversation objects with no packets.
362         conversations.removeIf(x -> x.getPackets().size() == 0);
363         // Sort the list based on the first packet's timestamp!
364         Collections.sort(conversations, (c1, c2) ->
365                 c1.getPackets().get(0).getTimestamp().compareTo(c2.getPackets().get(0).getTimestamp()));
366         return conversations;
367     }
368
369     /**
370      * Given a {@code List} of {@link Conversation} objects, find one that has the given {@code List}
371      * of {@code PcapPacket}.
372      * @param conversations The {@code List} of {@link Conversation} objects as reference.
373      * @param ppList The {@code List} of {@code PcapPacket} objects to search in the {@code List} of {@link Conversation}.
374      * @return A {@code Conversation} that contains the given {@code List} of {@code PcapPacket}.
375      */
376     public static Conversation returnConversation(List<PcapPacket> ppList, List<Conversation> conversations) {
377         // TODO: This part of comparison takes into account that the list of conversations is not sorted
378         // TODO: We could optimize this to have a better performance by requiring a sorted-by-timestamp list
379         // TODO:    as a parameter
380         // Find a Conversation that ppList is part of
381         for (Conversation c : conversations) {
382             // Figure out if c is the Conversation that ppList is in
383             if (isPartOfConversation(ppList, c)) {
384                 return c;
385             }
386         }
387         // Return null if not found
388         return null;
389     }
390
391     /**
392      * Given a {@link Conversation} objects, check if {@code List} of {@code PcapPacket} is part of it and return the
393      * adjacency label based on {@code SignaturePosition}.
394      * @param conversation The {@link Conversation} object as reference.
395      * @param ppListFirst The first {@code List} of {@code PcapPacket} objects in the {@link Conversation}.
396      * @param ppListSecond The second {@code List} of {@code PcapPacket} objects in the {@link Conversation} whose
397      *                     position will be observed in the {@link Conversation} with respect to ppListFirst.
398      * @return A {@code SignaturePosition} that represents the position of the signature against another signature
399      *          in a {@link Conversation}.
400      */
401     public static SignaturePosition isPartOfConversationAndAdjacent(List<PcapPacket> ppListFirst,
402                                                                     List<PcapPacket> ppListSecond,
403                                                                     Conversation conversation) {
404         // Take the first element in ppList and compare it
405         // The following elements in ppList are guaranteed to be in the same Conversation
406         // TODO: This part of comparison takes into account that the list of conversations is not sorted
407         // TODO: We could optimize this to have a better performance by requiring a sorted-by-timestamp list
408         // TODO:    as a parameter
409         if (isPartOfConversation(ppListSecond, conversation)) {
410             // Compare the first element of ppListSecond with the last element of ppListFirst to know
411             // whether ppListSecond is RIGHT_ADJACENT relative to ppListFirst.
412             PcapPacket lastElOfFirstList = ppListFirst.get(ppListFirst.size() - 1);
413             PcapPacket firstElOfSecondList = ppListSecond.get(0);
414             // If the positions of the two are in order, then they are adjacent.
415             int indexOfLastElOfFirstList = returnIndexInConversation(lastElOfFirstList, conversation);
416             int indexOfFirstElOfSecondList = returnIndexInConversation(firstElOfSecondList, conversation);
417             if(indexOfLastElOfFirstList + 1 == indexOfFirstElOfSecondList) {
418                 return SignaturePosition.RIGHT_ADJACENT;
419             }
420             // NOT RIGHT_ADJACENT, so check for LEFT_ADJACENT.
421             // Compare the first element of ppListRight with the last element of ppListSecond to know
422             // whether ppListSecond is LEFT_ADJACENT relative to ppListFirst.
423             PcapPacket firstElOfFirstList = ppListFirst.get(0);
424             PcapPacket lastElOfSecondList = ppListSecond.get(ppListSecond.size() - 1);
425             // If the positions of the two are in order, then they are adjacent.
426             int indexOfFirstElOfFirstList = returnIndexInConversation(firstElOfFirstList, conversation);
427             int indexOfLastElOfSecondList = returnIndexInConversation(lastElOfSecondList, conversation);
428             if(indexOfLastElOfSecondList + 1 == indexOfFirstElOfFirstList) {
429                 return SignaturePosition.LEFT_ADJACENT;
430             }
431         }
432         // Return NOT_ADJACENT if not found.
433         return SignaturePosition.NOT_ADJACENT;
434     }
435
436     /**
437      * Given a {@link Conversation} objects, check if {@code List} of {@code PcapPacket} is part of it.
438      * @param conversation The {@link Conversation} object as reference.
439      * @param ppList The {@code List} of {@code PcapPacket} objects to search in the {@link Conversation}.
440      * @return A {@code Boolean} value that represents the presence of the {@code List} of {@code PcapPacket} in
441      *         the {@link Conversation}.
442      */
443     private static boolean isPartOfConversation(List<PcapPacket> ppList, Conversation conversation) {
444         // Find the first element of ppList in conversation.
445         if (conversation.getPackets().contains(ppList.get(0)))
446             return true;
447         // Return false if not found.
448         return false;
449     }
450
451     /**
452      * Given a {@link Conversation} objects, check the index of a {@code PcapPacket} in it.
453      * @param conversation The {@link Conversation} object as reference.
454      * @param pp The {@code PcapPacket} object to search in the {@link Conversation}.
455      * @return An {@code Integer} value that gives the index of the {@code PcapPacket} in the {@link Conversation}.
456      */
457     private static int returnIndexInConversation(PcapPacket pp, Conversation conversation) {
458         // Find pp in conversation.
459         if (conversation.getPackets().contains(pp))
460             return conversation.getPackets().indexOf(pp);
461         // Return -1 if not found.
462         return -1;
463     }
464 }