1 package edu.uci.iotproject;
3 import static edu.uci.iotproject.analysis.UserAction.Type;
5 import edu.uci.iotproject.analysis.*;
6 import edu.uci.iotproject.io.PrintWriterUtils;
7 import edu.uci.iotproject.io.TriggerTimesFileReader;
8 import edu.uci.iotproject.trafficreassembly.layer3.Conversation;
9 import edu.uci.iotproject.trafficreassembly.layer3.TcpReassembler;
10 import edu.uci.iotproject.util.PcapPacketUtils;
11 import edu.uci.iotproject.util.PrintUtils;
12 import org.apache.commons.math3.stat.clustering.Cluster;
13 import org.apache.commons.math3.stat.clustering.DBSCANClusterer;
14 import org.pcap4j.core.*;
15 import org.pcap4j.packet.namednumber.DataLinkType;
18 import java.net.UnknownHostException;
19 import java.time.Duration;
20 import java.time.Instant;
22 import java.util.concurrent.TimeoutException;
23 import java.util.stream.Collectors;
24 import java.util.stream.Stream;
27 * This is a system that reads PCAP files to compare
28 * patterns of DNS hostnames, packet sequences, and packet
29 * lengths with training data to determine certain events
30 * or actions for smart home devices.
32 * @author Janus Varmarken
33 * @author Rahmadi Trimananda (rtrimana@uci.edu)
36 public class SignatureGenerator {
39 * If set to {@code true}, output written to the results file is also dumped to standard out.
41 private static boolean DUPLICATE_OUTPUT_TO_STD_OUT = true;
43 * File name for logging.
45 private static String LOG_EXTENSION = "_signature-generation.log";
47 * Directory for logging.
49 private static String LOG_DIRECTORY = "./";
51 * Multiplier for cluster bounds.
53 private static float CLUSTER_BOUNDS_MULTIPLIER = 0.1f;
55 public static void main(String[] args) throws PcapNativeException, NotOpenException, EOFException,
56 TimeoutException, UnknownHostException, IOException {
57 // -------------------------------------------------------------------------------------------------------------
58 // ------------ # Code for extracting traffic generated by a device within x seconds of a trigger # ------------
59 if (args.length < 11) {
60 String errMsg = String.format("SPECTO version 1.0\n" +
61 "Copyright (C) 2018-2019 Janus Varmarken and Rahmadi Trimananda.\n" +
62 "University of California, Irvine.\n" +
63 "All rights reserved.\n\n" +
64 "Usage: %s inputPcapFile outputPcapFile triggerTimesFile deviceIp" +
65 " onSignatureFile offSignatureFile onClusterAnalysisFile offClusterAnalysisFile epsilon" +
66 " deletedSequencesOn deletedSequencesOff" +
67 "\n inputPcapFile: the target of the detection" +
68 "\n outputPcapFile: the processed PCAP file through 15-second window filtering" +
69 "\n triggerTimesFile: the trigger timestamps" +
70 "\n deviceIp: the IP address of the device we want to generate a signature for" +
71 "\n onSignatureFile: name of the ON signature file" +
72 "\n offSignatureFile: name of the OFF signature file" +
73 "\n onClusterAnalysisFile: name of the ON signature cluster analysis file" +
74 "\n offClusterAnalysisFile: name of the OFF signature cluster analysis file" +
75 "\n epsilon: epsilon value of the DBSCAN algorithm" +
76 "\n deletedSequencesOn: sequences to be deleted from the final ON signature" +
77 " (please separate with commas, e.g., 0,1,2, or put '-1' if not needed)" +
78 "\n deletedSequencesOff: sequences to be deleted from the final OFF signature" +
79 " (please separate with commas, e.g., 0,1,2, or put '-1' if not needed)",
80 SignatureGenerator.class.getSimpleName());
81 System.out.println(errMsg);
84 boolean verbose = true;
85 final String inputPcapFile = args[0];
86 final String outputPcapFile = args[1];
87 final String triggerTimesFile = args[2];
88 final String deviceIp = args[3];
89 final String onSignatureFile = args[4];
90 final String offSignatureFile = args[5];
91 final String onClusterAnalysisFile = args[6];
92 final String offClusterAnalysisFile = args[7];
93 final double eps = Double.parseDouble(args[8]);
94 final String deletedSequencesOn = args[9];
95 final String deletedSequencesOff = args[10];
96 final String logFile = inputPcapFile + LOG_EXTENSION;
98 // Prepare file outputter.
99 File outputFile = new File(logFile);
100 outputFile.getParentFile().mkdirs();
101 final PrintWriter resultsWriter = new PrintWriter(new FileWriter(outputFile));
103 // =========================================== TRAFFIC FILTERING ============================================
105 TriggerTimesFileReader ttfr = new TriggerTimesFileReader();
106 List<Instant> triggerTimes = ttfr.readTriggerTimes(triggerTimesFile, false);
107 // Tag each trigger with "ON" or "OFF", assuming that the first trigger is an "ON" and that they alternate.
108 List<UserAction> userActions = new ArrayList<>();
109 for (int i = 0; i < triggerTimes.size(); i++) {
110 userActions.add(new UserAction(i % 2 == 0 ? Type.TOGGLE_ON : Type.TOGGLE_OFF, triggerTimes.get(i)));
112 TriggerTrafficExtractor tte = new TriggerTrafficExtractor(inputPcapFile, triggerTimes, deviceIp);
113 final PcapDumper outputter = Pcaps.openDead(DataLinkType.EN10MB, 65536).dumpOpen(outputPcapFile);
114 DnsMap dnsMap = new DnsMap();
115 TcpReassembler tcpReassembler = new TcpReassembler();
116 TrafficLabeler trafficLabeler = new TrafficLabeler(userActions);
117 tte.performExtraction(pkt -> {
120 } catch (NotOpenException e) {
123 }, dnsMap, tcpReassembler, trafficLabeler);
127 if (tte.getPacketsIncludedCount() != trafficLabeler.getTotalPacketCount()) {
128 // Sanity/debug check
129 throw new AssertionError(String.format("mismatch between packet count in %s and %s",
130 TriggerTrafficExtractor.class.getSimpleName(), TrafficLabeler.class.getSimpleName()));
133 // Extract all conversations present in the filtered trace.
134 List<Conversation> allConversations = tcpReassembler.getTcpConversations();
135 // Group conversations by hostname.
136 Map<String, List<Conversation>> convsByHostname =
137 TcpConversationUtils.groupConversationsByHostname(allConversations, dnsMap);
138 PrintWriterUtils.println("Grouped conversations by hostname.", resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
139 // For each hostname, count the frequencies of packet lengths exchanged with that hostname.
140 final Map<String, Map<Integer, Integer>> pktLenFreqsByHostname = new HashMap<>();
141 convsByHostname.forEach((host, convs) -> pktLenFreqsByHostname.put(host,
142 TcpConversationUtils.countPacketLengthFrequencies(convs)));
143 PrintWriterUtils.println("Counted frequencies of packet lengths exchanged with each hostname.",
144 resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
145 // For each hostname, count the frequencies of packet sequences (i.e., count how many
146 // conversations exchange a sequence of packets of some specific lengths).
147 final Map<String, Map<String, Integer>> pktSeqFreqsByHostname = new HashMap<>();
148 convsByHostname.forEach((host, convs) -> pktSeqFreqsByHostname.put(host,
149 TcpConversationUtils.countPacketSequenceFrequencies(convs)));
150 PrintWriterUtils.println("Counted frequencies of packet sequences exchanged with each hostname.",
151 resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
152 // For each hostname, count frequencies of packet pairs exchanged
153 // with that hostname across all conversations
154 final Map<String, Map<String, Integer>> pktPairFreqsByHostname =
155 TcpConversationUtils.countPacketPairFrequenciesByHostname(allConversations, dnsMap);
156 PrintWriterUtils.println("Counted frequencies of packet pairs per hostname.",
157 resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
158 // For each user action, reassemble the set of TCP connections occurring shortly after
159 final Map<UserAction, List<Conversation>> userActionToConversations =
160 trafficLabeler.getLabeledReassembledTcpTraffic();
161 final Map<UserAction, Map<String, List<Conversation>>> userActionsToConvsByHostname =
162 trafficLabeler.getLabeledReassembledTcpTraffic(dnsMap);
163 PrintWriterUtils.println("Reassembled TCP conversations occurring shortly after each user event.",
164 resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
167 * NOTE: no need to generate these more complex on/off maps that also contain mappings from hostname and
168 * sequence identifiers as we do not care about hostnames and sequences during clustering.
169 * We can simply use the UserAction->List<Conversation> map to generate ON/OFF groupings of conversations.
171 // Contains all ON events: hostname -> sequence identifier -> list of conversations with that sequence
172 Map<String, Map<String, List<Conversation>>> ons = new HashMap<>();
173 // Contains all OFF events: hostname -> sequence identifier -> list of conversations with that sequence
174 Map<String, Map<String, List<Conversation>>> offs = new HashMap<>();
175 userActionsToConvsByHostname.forEach((ua, hostnameToConvs) -> {
176 Map<String, Map<String, List<Conversation>>> outer = ua.getType() == Type.TOGGLE_ON ? ons : offs;
177 hostnameToConvs.forEach((host, convs) -> {
178 Map<String, List<Conversation>> seqsToConvs = TcpConversationUtils.
179 groupConversationsByPacketSequence(convs, verbose);
180 outer.merge(host, seqsToConvs, (oldMap, newMap) -> {
181 newMap.forEach((sequence, cs) -> oldMap.merge(sequence, cs, (list1, list2) -> {
190 // ============================================== PAIR CLUSTERING ============================================
191 // TODO: No need to use the more convoluted on/off maps; Can simply use the UserAction->List<Conversation> map
192 // TODO: when don't care about hostnames and sequences (see comment earlier).
193 // ===========================================================================================================
194 List<Conversation> onConversations = userActionToConversations.entrySet().stream().
195 filter(e -> e.getKey().getType() == Type.TOGGLE_ON). // drop all OFF events from stream
196 map(e -> e.getValue()). // no longer interested in the UserActions
197 flatMap(List::stream). // flatten List<List<T>> to a List<T>
198 collect(Collectors.toList());
199 List<Conversation> offConversations = userActionToConversations.entrySet().stream().
200 filter(e -> e.getKey().getType() == Type.TOGGLE_OFF).
201 map(e -> e.getValue()).
202 flatMap(List::stream).
203 collect(Collectors.toList());
204 //Collections.sort(onConversations, (c1, c2) -> c1.getPackets().)
206 List<PcapPacketPair> onPairs = onConversations.stream().
207 map(c -> c.isTls() ? TcpConversationUtils.extractTlsAppDataPacketPairs(c) :
208 TcpConversationUtils.extractPacketPairs(c)).
209 flatMap(List::stream). // flatten List<List<>> to List<>
210 collect(Collectors.toList());
211 List<PcapPacketPair> offPairs = offConversations.stream().
212 map(c -> c.isTls() ? TcpConversationUtils.extractTlsAppDataPacketPairs(c) :
213 TcpConversationUtils.extractPacketPairs(c)).
214 flatMap(List::stream). // flatten List<List<>> to List<>
215 collect(Collectors.toList());
216 // Note: need to update the DnsMap of all PcapPacketPairs if we want to use the IP/hostname-sensitive distance.
217 Stream.concat(Stream.of(onPairs), Stream.of(offPairs)).flatMap(List::stream).forEach(p -> p.setDnsMap(dnsMap));
218 // Perform clustering on conversation logged as part of all ON events.
219 // Calculate number of events per type (only ON/only OFF), which means half of the number of all timestamps.
220 int numberOfEventsPerType = triggerTimes.size() / 2;
221 int lowerBound = numberOfEventsPerType - (int)(numberOfEventsPerType * CLUSTER_BOUNDS_MULTIPLIER);
222 int upperBound = numberOfEventsPerType + (int)(numberOfEventsPerType * CLUSTER_BOUNDS_MULTIPLIER);
223 int minPts = lowerBound;
224 DBSCANClusterer<PcapPacketPair> onClusterer = new DBSCANClusterer<>(eps, minPts);
225 List<Cluster<PcapPacketPair>> onClusters = onClusterer.cluster(onPairs);
226 // Perform clustering on conversation logged as part of all OFF events.
227 DBSCANClusterer<PcapPacketPair> offClusterer = new DBSCANClusterer<>(eps, minPts);
228 List<Cluster<PcapPacketPair>> offClusters = offClusterer.cluster(offPairs);
229 // Sort the conversations as reference
230 List<Conversation> sortedAllConversation = TcpConversationUtils.sortConversationList(allConversations);
232 PrintWriterUtils.println("========================================", resultsWriter,
233 DUPLICATE_OUTPUT_TO_STD_OUT);
234 PrintWriterUtils.println(" Clustering results for ON ", resultsWriter,
235 DUPLICATE_OUTPUT_TO_STD_OUT);
236 PrintWriterUtils.println(" Number of clusters: " + onClusters.size(), resultsWriter,
237 DUPLICATE_OUTPUT_TO_STD_OUT);
239 List<List<List<PcapPacket>>> ppListOfListReadOn = new ArrayList<>();
240 List<List<List<PcapPacket>>> ppListOfListListOn = new ArrayList<>();
241 List<List<List<PcapPacket>>> corePointRangeSignatureOn = new ArrayList<>();
242 for (Cluster<PcapPacketPair> c : onClusters) {
243 PrintWriterUtils.println(String.format("<<< Cluster #%02d (%03d points) >>>", ++count, c.getPoints().size()),
244 resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
245 PrintWriterUtils.println(PrintUtils.toSummaryString(c), resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
246 if(c.getPoints().size() > lowerBound && c.getPoints().size() < upperBound) {
248 List<List<PcapPacket>> ppListOfList = PcapPacketUtils.clusterToListOfPcapPackets(c);
249 // Check for overlaps and decide whether to do range-based or conservative checking
250 corePointRangeSignatureOn.add(PcapPacketUtils.extractRangeCorePoints(ppListOfList, eps, minPts));
251 ppListOfListListOn.add(ppListOfList);
254 PrintWriterUtils.println("========================================", resultsWriter,
255 DUPLICATE_OUTPUT_TO_STD_OUT);
256 PrintWriterUtils.println(" Clustering results for OFF ", resultsWriter,
257 DUPLICATE_OUTPUT_TO_STD_OUT);
258 PrintWriterUtils.println(" Number of clusters: " + offClusters.size(), resultsWriter,
259 DUPLICATE_OUTPUT_TO_STD_OUT);
261 List<List<List<PcapPacket>>> ppListOfListReadOff = new ArrayList<>();
262 List<List<List<PcapPacket>>> ppListOfListListOff = new ArrayList<>();
263 List<List<List<PcapPacket>>> corePointRangeSignatureOff = new ArrayList<>();
264 for (Cluster<PcapPacketPair> c : offClusters) {
265 PrintWriterUtils.println(String.format("<<< Cluster #%03d (%06d points) >>>", ++count, c.getPoints().size()),
266 resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
267 PrintWriterUtils.println(PrintUtils.toSummaryString(c), resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
268 if(c.getPoints().size() > lowerBound && c.getPoints().size() < upperBound) {
270 List<List<PcapPacket>> ppListOfList = PcapPacketUtils.clusterToListOfPcapPackets(c);
271 // Check for overlaps and decide whether to do range-based or conservative checking
272 corePointRangeSignatureOff.add(PcapPacketUtils.extractRangeCorePoints(ppListOfList, eps, minPts));
273 ppListOfListListOff.add(ppListOfList);
277 // =========================================== SIGNATURE CREATION ===========================================
279 ppListOfListListOn = PcapPacketUtils.concatSequences(ppListOfListListOn, sortedAllConversation);
280 // Remove sequences in the list that have overlap
281 StringTokenizer stringTokenizerOn = new StringTokenizer(deletedSequencesOn, ",");
282 while(stringTokenizerOn.hasMoreTokens()) {
283 int sequenceToDelete = Integer.parseInt(stringTokenizerOn.nextToken());
284 if (sequenceToDelete == -1) { // '-1' means there is no removal
287 PcapPacketUtils.removeSequenceFromSignature(ppListOfListListOn, sequenceToDelete);
289 PrintWriterUtils.println("ON Sequences: ", resultsWriter,
290 DUPLICATE_OUTPUT_TO_STD_OUT);
291 for(List<List<PcapPacket>> listOfList : ppListOfListListOn) {
292 PrintWriterUtils.println(listOfList.get(0).get(0).length() + "...", resultsWriter,
293 DUPLICATE_OUTPUT_TO_STD_OUT);
295 ppListOfListListOn = PcapPacketUtils.sortSequences(ppListOfListListOn);
296 PrintWriterUtils.println("Concatenated and sorted ON signature sequences...", resultsWriter,
297 DUPLICATE_OUTPUT_TO_STD_OUT);
300 ppListOfListListOff = PcapPacketUtils.concatSequences(ppListOfListListOff, sortedAllConversation);
301 // Remove sequences in the list that have overlap
302 StringTokenizer stringTokenizerOff = new StringTokenizer(deletedSequencesOff, ",");
303 while(stringTokenizerOff.hasMoreTokens()) {
304 int sequenceToDelete = Integer.parseInt(stringTokenizerOff.nextToken());
305 if (sequenceToDelete == -1) { // '-1' means there is no removal
308 PcapPacketUtils.removeSequenceFromSignature(ppListOfListListOff, sequenceToDelete);
310 PrintWriterUtils.println("OFF Sequences: ", resultsWriter,
311 DUPLICATE_OUTPUT_TO_STD_OUT);
312 for(List<List<PcapPacket>> listOfList : ppListOfListListOff) {
313 PrintWriterUtils.println(listOfList.get(0).get(0).length() + "...", resultsWriter,
314 DUPLICATE_OUTPUT_TO_STD_OUT);
316 ppListOfListListOff = PcapPacketUtils.sortSequences(ppListOfListListOff);
317 PrintWriterUtils.println("Concatenated and sorted OFF signature sequences...", resultsWriter,
318 DUPLICATE_OUTPUT_TO_STD_OUT);
320 // Write the signatures into the screen
321 PrintWriterUtils.println("========================================", resultsWriter,
322 DUPLICATE_OUTPUT_TO_STD_OUT);
323 PrintWriterUtils.println(" ON Signature ", resultsWriter,
324 DUPLICATE_OUTPUT_TO_STD_OUT);
325 PrintWriterUtils.println("========================================", resultsWriter,
326 DUPLICATE_OUTPUT_TO_STD_OUT);
327 PcapPacketUtils.printSignatures(ppListOfListListOn, resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
328 PrintWriterUtils.println("========================================", resultsWriter,
329 DUPLICATE_OUTPUT_TO_STD_OUT);
330 PrintWriterUtils.println(" OFF Signature ", resultsWriter,
331 DUPLICATE_OUTPUT_TO_STD_OUT);
332 PrintWriterUtils.println("========================================", resultsWriter,
333 DUPLICATE_OUTPUT_TO_STD_OUT);
334 PcapPacketUtils.printSignatures(ppListOfListListOff, resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
335 // Clean signatures from null elements
336 PcapPacketUtils.cleanSignature(ppListOfListListOn);
337 PcapPacketUtils.cleanSignature(ppListOfListListOff);
338 // Printing signatures into files
339 PrintUtils.serializeIntoFile(onSignatureFile, ppListOfListListOn);
340 PrintUtils.serializeIntoFile(offSignatureFile, ppListOfListListOff);
341 // Printing cluster analyses into files
342 PrintUtils.serializeIntoFile(onClusterAnalysisFile, corePointRangeSignatureOn);
343 PrintUtils.serializeIntoFile(offClusterAnalysisFile, corePointRangeSignatureOff);
345 // =========================================== SIGNATURE DURATIONS =============================================
346 List<Instant> firstSignatureTimestamps = new ArrayList<>();
347 List<Instant> lastSignatureTimestamps = new ArrayList<>();
348 if (!ppListOfListListOn.isEmpty()) {
349 List<List<PcapPacket>> firstListOnSign = ppListOfListListOn.get(0);
350 List<List<PcapPacket>> lastListOnSign = ppListOfListListOn.get(ppListOfListListOn.size() - 1);
351 // Load ON signature first and last packet's timestamps
352 for (List<PcapPacket> list : firstListOnSign) {
353 // Get timestamp Instant from the last packet
354 firstSignatureTimestamps.add(list.get(0).getTimestamp());
356 for (List<PcapPacket> list : lastListOnSign) {
357 // Get timestamp Instant from the last packet
358 int lastPacketIndex = list.size() - 1;
359 lastSignatureTimestamps.add(list.get(lastPacketIndex).getTimestamp());
363 if (!ppListOfListListOff.isEmpty()) {
364 List<List<PcapPacket>> firstListOffSign = ppListOfListListOff.get(0);
365 List<List<PcapPacket>> lastListOffSign = ppListOfListListOff.get(ppListOfListListOff.size() - 1);
366 // Load OFF signature first and last packet's timestamps
367 for (List<PcapPacket> list : firstListOffSign) {
368 // Get timestamp Instant from the last packet
369 firstSignatureTimestamps.add(list.get(0).getTimestamp());
371 for (List<PcapPacket> list : lastListOffSign) {
372 // Get timestamp Instant from the last packet
373 int lastPacketIndex = list.size() - 1;
374 lastSignatureTimestamps.add(list.get(lastPacketIndex).getTimestamp());
377 // Sort the timestamps
378 firstSignatureTimestamps.sort(Comparator.comparing(Instant::toEpochMilli));
379 lastSignatureTimestamps.sort(Comparator.comparing(Instant::toEpochMilli));
381 Iterator<Instant> iterFirst = firstSignatureTimestamps.iterator();
382 Iterator<Instant> iterLast = lastSignatureTimestamps.iterator();
384 long maxDuration = Long.MIN_VALUE;
385 PrintWriterUtils.println("========================================", resultsWriter,
386 DUPLICATE_OUTPUT_TO_STD_OUT);
387 PrintWriterUtils.println(" Signature Durations ", resultsWriter,
388 DUPLICATE_OUTPUT_TO_STD_OUT);
389 PrintWriterUtils.println("========================================", resultsWriter,
390 DUPLICATE_OUTPUT_TO_STD_OUT);
391 while (iterFirst.hasNext() && iterLast.hasNext()) {
392 Instant firstInst = iterFirst.next();
393 Instant lastInst = iterLast.next();
394 Duration dur = Duration.between(firstInst, lastInst);
395 duration = dur.toMillis();
396 // Check duration --- should be below 15 seconds
397 if (duration > TriggerTrafficExtractor.INCLUSION_WINDOW_MILLIS) {
398 while (duration > TriggerTrafficExtractor.INCLUSION_WINDOW_MILLIS && iterFirst.hasNext()) {
399 // that means we have to move to the next trigger
400 firstInst = iterFirst.next();
401 dur = Duration.between(firstInst, lastInst);
402 duration = dur.toMillis();
404 } else { // Below 0/Negative --- that means we have to move to the next signature
405 while (duration < 0 && iterLast.hasNext()) {
406 // that means we have to move to the next trigger
407 lastInst = iterLast.next();
408 dur = Duration.between(firstInst, lastInst);
409 duration = dur.toMillis();
412 PrintWriterUtils.println(duration, resultsWriter, DUPLICATE_OUTPUT_TO_STD_OUT);
413 // Update duration if this bigger than the max value and still less than the window inclusion time
414 maxDuration = maxDuration < duration && duration <= TriggerTrafficExtractor.INCLUSION_WINDOW_MILLIS ?
415 duration : maxDuration;
417 // Just assign the value 0 if there is no signature
418 if (maxDuration == Long.MIN_VALUE) {
421 PrintWriterUtils.println("========================================", resultsWriter,
422 DUPLICATE_OUTPUT_TO_STD_OUT);
423 PrintWriterUtils.println("Max signature duration: " + maxDuration, resultsWriter,
424 DUPLICATE_OUTPUT_TO_STD_OUT);
425 PrintWriterUtils.println("========================================", resultsWriter,
426 DUPLICATE_OUTPUT_TO_STD_OUT);
427 resultsWriter.flush();
428 resultsWriter.close();
429 // ==========================================================================================================