Code/Projects/PacketLevelSignatureExtractor/src/main/java/edu/uci/iotproject/detection/layer3/SignatureDetector.java

   1 package edu.uci.iotproject.detection.layer3;
   2
   3 import edu.uci.iotproject.analysis.TriggerTrafficExtractor;
   4 import edu.uci.iotproject.analysis.UserAction;
   5 import edu.uci.iotproject.detection.AbstractClusterMatcher;
   6 import edu.uci.iotproject.detection.ClusterMatcherObserver;
   7 import edu.uci.iotproject.io.PcapHandleReader;
   8 import edu.uci.iotproject.util.PrintUtils;
   9 import org.apache.commons.math3.distribution.AbstractRealDistribution;
  10 import org.apache.commons.math3.distribution.NormalDistribution;
  11 import org.jgrapht.GraphPath;
  12 import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
  13 import org.jgrapht.graph.DefaultWeightedEdge;
  14 import org.jgrapht.graph.SimpleDirectedWeightedGraph;
  15 import org.pcap4j.core.*;
  16
  17 import java.time.Duration;
  18 import java.time.ZoneId;
  19 import java.time.format.DateTimeFormatter;
  20 import java.time.format.FormatStyle;
  21 import java.util.*;
  22 import java.util.function.Consumer;
  23
  24 /**
  25  * Detects an event signature that spans one or multiple TCP connections.
  26  *
  27  * @author Janus Varmarken {@literal <jvarmark@uci.edu>}
  28  * @author Rahmadi Trimananda {@literal <rtrimana@uci.edu>}
  29  */
  30 public class SignatureDetector implements PacketListener, ClusterMatcherObserver {
  31
  32     // Test client
  33     public static void main(String[] args) throws PcapNativeException, NotOpenException {
  34 //        if (args.length < 3) {
  35 //            String errMsg = String.format("Usage: %s inputPcapFile onSignatureFile offSignatureFile",
  36 //                    SignatureDetector.class.getSimpleName());
  37 //            System.out.println(errMsg);
  38 //            return;
  39 //        }
  40 //        final String inputPcapFile = args[0];
  41 //        final String onSignatureFile = args[1];
  42 //        final String offSignatureFile = args[2];
  43
  44         String path = "/scratch/July-2018"; // Rahmadi
  45 //        String path = "/Users/varmarken/temp/UCI IoT Project/experiments"; // Janus
  46 //        String path = "/home/jvarmark/iot_project/datasets"; // Hera (server)
  47 //        String path = "/raid/varmarken/iot_project/datasets"; // Zeus (server)
  48
  49         // No activity test
  50         //final String inputPcapFile = path + "/evaluation/no-activity/no-activity.wlan1.pcap";
  51
  52         // D-Link Siren experiment
  53 //        final String inputPcapFile = path + "/evaluation/dlink-siren/dlink-siren.data.wlan1.pcap";
  54 //        final String inputPcapFile = path + "/evaluation/dlink-siren/dlink-siren.eth0.local.pcap";
  55         // D-Link Siren DEVICE signatures
  56 //        final String onSignatureFile = path + "/2018-08/dlink-siren/onSignature-DLink-Siren-device.sig";
  57 //        final String offSignatureFile = path + "/2018-08/dlink-siren/offSignature-DLink-Siren-device.sig";
  58         // D-Link Siren PHONE signatures
  59 //        final String onSignatureFile = path + "/2018-08/dlink-siren/onSignature-DLink-Siren-phone.sig";
  60 //        final String offSignatureFile = path + "/2018-08/dlink-siren/offSignature-DLink-Siren-phone.sig";
  61         // TODO: EXPERIMENT - November 19, 2018
  62         // Hue Bulb experiment
  63 //        final String inputPcapFile = path + "/2018-08/hue-bulb/hue-bulb.wlan1.local.pcap";
  64         // Hue Bulb PHONE signatures
  65 //        final String onSignatureFile = path + "/experimental_result/standalone/hue-bulb/signatures/hue-bulb-onSignature-phone-side.sig";
  66 //        final String offSignatureFile = path + "/experimental_result/standalone/hue-bulb/signatures/hue-bulb-offSignature-phone-side.sig";
  67
  68         /*
  69         // Kwikset Doorlock Sep 12 experiment
  70 //        final String inputPcapFile = path + "/evaluation/kwikset-doorlock/kwikset-doorlock.data.wlan1.pcap";
  71         final String inputPcapFile = path + "/evaluation/kwikset-doorlock/kwikset-doorlock.data.eth0.pcap";
  72 //        // Kwikset Doorlock PHONE signatures
  73         final String onSignatureFile = path + "/2018-08/kwikset-doorlock/onSignature-Kwikset-Doorlock-phone-new.sig";
  74         final String offSignatureFile = path + "/2018-08/kwikset-doorlock/offSignature-Kwikset-Doorlock-phone-new.sig";
  75         */
  76
  77         // D-Link Plug experiment
  78         //final String inputPcapFile = path + "/evaluation/dlink/dlink-plug.data.wlan1.pcap";
  79 //        final String inputPcapFile = path + "/evaluation/dlink/dlink-plug.data.eth0.pcap";
  80
  81         // D-Link Plug DEVICE signatures
  82 //        final String onSignatureFile = path + "/2018-07/dlink/onSignature-DLink-Plug-device.sig";
  83 //        final String offSignatureFile = path + "/2018-07/dlink/offSignature-DLink-Plug-device.sig";
  84         // D-Link Plug PHONE signatures
  85 //        final String onSignatureFile = path + "/2018-07/dlink/onSignature-DLink-Plug-phone.sig";
  86 //        final String offSignatureFile = path + "/2018-07/dlink/offSignature-DLink-Plug-phone.sig";
  87
  88         // TODO: The following are negative tests against the PCAP file from UNSW
  89 //        final String inputPcapFile = path + "/UNSW/16-10-04.pcap"; // TODO: Seems to be broken! Zero-payload!
  90 //          final String inputPcapFile = path + "/UNSW/16-10-12.pcap";
  91
  92 //        final String inputPcapFile = path + "/UNSW/16-09-28.pcap"; // TODO: Seems to be broken! Zero-payload!
  93 //        final String inputPcapFile = path + "/UNSW/16-10-02.pcap"; // TODO: Seems to be broken!
  94 //        final String inputPcapFile = path + "/UNSW/16-10-03.pcap"; // TODO: Seems to be broken!
  95 //        final String inputPcapFile = path + "/UNSW/16-10-04-a.pcap"; // TODO: Seems to be broken! Zero-payload!
  96 //        final String inputPcapFile = path + "/UNSW/16-10-04-b.pcap"; // TODO: Seems to be broken! Zero-payload!
  97 //        final String inputPcapFile = path + "/UNSW/16-10-07.pcap"; // TODO: Seems to be broken!
  98 //        final String inputPcapFile = path + "/UNSW/16-10-08.pcap"; // TODO: Seems to be broken!
  99 //        final String inputPcapFile = path + "/UNSW/16-10-09.pcap"; // TODO: Seems to be broken!
 100 //        final String inputPcapFile = path + "/UNSW/16-10-10.pcap"; // TODO: Seems to be broken!
 101 //        final String inputPcapFile = path + "/UNSW/16-10-11.pcap"; // TODO: Seems to be broken!
 102         // TODO: The following one is very long!!! - Split into smaller files!
 103 //        final String inputPcapFile = path + "/UNSW/16-10-12-a.pcap";
 104 //        final String inputPcapFile = path + "/UNSW/16-10-12-b.pcap";
 105 //        final String inputPcapFile = path + "/UNSW/16-10-12-c.pcap";
 106 //        final String inputPcapFile = path + "/UNSW/16-10-12-d.pcap";
 107
 108 //        final String inputPcapFile = path + "/UNSW/16-09-23.pcap";
 109 //        final String inputPcapFile = path + "/UNSW/16-09-24.pcap";
 110 //        final String inputPcapFile = path + "/UNSW/16-09-25.pcap";
 111 //        final String inputPcapFile = path + "/UNSW/16-09-26.pcap";
 112 //        final String inputPcapFile = path + "/UNSW/16-09-27.pcap";
 113 //        final String inputPcapFile = path + "/UNSW/16-09-29.pcap";
 114 //        final String inputPcapFile = path + "/UNSW/16-10-01.pcap";
 115 //        final String inputPcapFile = path + "/UNSW/16-10-06.pcap";
 116         // Negative test: dataset from UNB
 117 //        final String inputPcapFile = path + "/evaluation/negative-datasets/UNB/Monday-WorkingHours_one-local-endpoint-001.pcap";
 118
 119         // TODO: The following are tests for signatures against training data
 120
 121         // D-Link Plug experiment
 122 //        final String inputPcapFile = path + "/training/dlink-plug/wlan1/dlink-plug.wlan1.local.pcap";
 123         // D-Link Plug DEVICE signatures
 124 //        final String onSignatureFile = path + "/training/dlink-plug/signatures/dlink-plug-onSignature-device-side.sig";
 125 //        final String offSignatureFile = path + "/training/dlink-plug/signatures/dlink-plug-offSignature-device-side.sig";
 126         // D-Link Plug PHONE signatures
 127 //        final String onSignatureFile = path + "/training/dlink-plug/signatures/dlink-plug-onSignature-phone-side.sig";
 128 //        final String offSignatureFile = path + "/training/dlink-plug/signatures/dlink-plug-offSignature-phone-side.sig";
 129
 130         // TODO: EXPERIMENT - November 7, 2018
 131         // D-Link Plug experiment
 132 //        //final String inputPcapFile = path + "/experimental_result/standalone/dlink-plug/wlan1/dlink-plug.wlan1.local.pcap";
 133 //        final String inputPcapFile = path + "/experimental_result/smarthome/dlink-plug/wlan1/dlink-plug.wlan1.detection.pcap";
 134 //        //final String inputPcapFile = path + "/experimental_result/smarthome/dlink-plug/eth0/dlink-plug.eth0.detection.pcap";
 135 //        // D-Link Plug DEVICE signatures
 136 //        final String onSignatureFile = path + "/experimental_result/standalone/dlink-plug/signatures/dlink-plug-onSignature-device-side.sig";
 137 //        final String offSignatureFile = path + "/experimental_result/standalone/dlink-plug/signatures/dlink-plug-offSignature-device-side.sig";
 138         // D-Link Plug PHONE signatures
 139 //        final String onSignatureFile = path + "/experimental_result/standalone/dlink-plug/signatures/dlink-plug-onSignature-phone-side.sig";
 140 //        final String offSignatureFile = path + "/experimental_result/standalone/dlink-plug/signatures/dlink-plug-offSignature-phone-side.sig";
 141
 142         // TODO: EXPERIMENT - November 9, 2018
 143         // D-Link Siren experiment
 144         //final String inputPcapFile = path + "/experimental_result/standalone/dlink-siren/wlan1/dlink-siren.wlan1.local.pcap";
 145         //final String inputPcapFile = path + "/experimental_result/smarthome/dlink-siren/wlan1/dlink-siren.wlan1.detection.pcap";
 146 //        final String inputPcapFile = path + "/experimental_result/smarthome/dlink-siren/eth0/dlink-siren.eth0.detection.pcap";
 147 //        // D-Link Siren DEVICE signatures
 148 //        // TODO: The device signature does not have pairs---only one packet which is 216, so we don't consider this as a signature
 149 //        final String onSignatureFile = path + "/experimental_result/standalone/dlink-siren/signatures/dlink-siren-onSignature-device-side.sig";
 150 //        final String offSignatureFile = path + "/experimental_result/standalone/dlink-siren/signatures/dlink-siren-offSignature-device-side.sig";
 151         // D-Link Siren PHONE signatures
 152 //        final String onSignatureFile = path + "/experimental_result/standalone/dlink-siren/signatures/dlink-siren-onSignature-phone-side.sig";
 153 //        final String offSignatureFile = path + "/experimental_result/standalone/dlink-siren/signatures/dlink-siren-offSignature-phone-side.sig";
 154 //        final String onSignatureFile = path + "/training/signatures/dlink-siren/dlink-siren-onSignature-phone-side.sig";
 155 //        final String offSignatureFile = path + "/training/signatures/dlink-siren/dlink-siren-offSignature-phone-side.sig";
 156
 157         // TP-Link Plug experiment
 158 ////        final String inputPcapFile = path + "/training/tplink-plug/wlan1/tplink-plug.wlan1.local.pcap";
 159 ////        final String inputPcapFile = path + "/experimental_result/wifi-Sniffer/tests2/airtool_2019-01-04_11.08.45.AM.pcap";
 160 //        final String inputPcapFile = path + "/experimental_result/wifi-Sniffer/tests2/command-frames-only.pcap";
 161 //        // TP-Link Plug DEVICE signatures
 162 //        final String onSignatureFile = path + "/training/tplink-plug/signatures/tplink-plug-onSignature-device-side.sig";
 163 //        final String offSignatureFile = path + "/training/tplink-plug/signatures/tplink-plug-offSignature-device-side.sig";
 164         // TODO: EXPERIMENT - November 8, 2018
 165         // TP-Link Plug experiment
 166 //        final String inputPcapFile = path + "/experimental_result/standalone/tplink-plug/wlan1/tplink-plug.wlan1.local.pcap";
 167 ////        final String inputPcapFile = path + "/experimental_result/standalone/tplink-plug/eth0/tplink-plug.eth0.local.pcap";
 168 ////        final String inputPcapFile = path + "/experimental_result/smarthome/tplink-plug/wlan1/tplink-plug.wlan1.detection.pcap";
 169 //        //final String inputPcapFile = path + "/experimental_result/smarthome/tplink-plug/eth0/tplink-plug.eth0.detection.pcap";
 170 //        // TP-Link Plug DEVICE signatures
 171 ////        final String onSignatureFile = path + "/experimental_result/standalone/tplink-plug/signatures/tplink-plug-onSignature-device-side.sig";
 172 ////        final String offSignatureFile = path + "/experimental_result/standalone/tplink-plug/signatures/tplink-plug-offSignature-device-side.sig";
 173 //        final String onSignatureFile = path + "/experimental_result/standalone/tplink-plug/signatures/tplink-plug-onSignature-device-side-outbound.sig";
 174 //        final String offSignatureFile = path + "/experimental_result/standalone/tplink-plug/signatures/tplink-plug-offSignature-device-side-outbound.sig";
 175         // TP-Link Plug PHONE signatures
 176 //        final String onSignatureFile = path + "/experimental_result/standalone/tplink-plug/signatures/tplink-plug-onSignature-phone-side.sig";
 177 //        final String offSignatureFile = path + "/experimental_result/standalone/tplink-plug/signatures/tplink-plug-offSignature-phone-side.sig";
 178
 179         // Arlo camera experiment
 180 //        final String inputPcapFile = path + "/training/arlo-camera/wlan1/arlo-camera.wlan1.local.pcap";
 181 ////        // TP-Link Plug DEVICE signatures
 182 //        final String onSignatureFile = path + "/training/arlo-camera/signatures/arlo-camera-onSignature-phone-side.sig";
 183 //        final String offSignatureFile = path + "/training/arlo-camera/signatures/arlo-camera-offSignature-phone-side.sig";
 184         // TODO: EXPERIMENT - November 13, 2018
 185         // Arlo Camera experiment
 186 //        final String inputPcapFile = path + "/experimental_result/standalone/arlo-camera/wlan1/arlo-camera.wlan1.local.pcap";
 187 //        final String inputPcapFile = path + "/experimental_result/standalone/arlo-camera/eth0/arlo-camera.eth0.local.pcap";
 188 //        final String inputPcapFile = path + "/experimental_result/smarthome/arlo-camera/wlan1/arlo-camera.wlan1.detection.pcap";
 189 ////        final String inputPcapFile = path + "/experimental_result/smarthome/arlo-camera/eth0/arlo-camera.eth0.detection.pcap";
 190 ////        final String inputPcapFile = path + "/training/arlo-camera/eth0/arlo-camera.eth0.local.pcap";
 191 //        // Arlo Camera PHONE signatures
 192 ////        final String onSignatureFile = path + "/experimental_result/standalone/arlo-camera/signatures/arlo-camera-onSignature-phone-side.sig";
 193 ////        final String offSignatureFile = path + "/experimental_result/standalone/arlo-camera/signatures/arlo-camera-offSignature-phone-side.sig";
 194 //        final String onSignatureFile = path + "/experimental_result/standalone/arlo-camera/signatures/arlo-camera-onSignature-phone-side.sig.complete";
 195 //        final String offSignatureFile = path + "/experimental_result/standalone/arlo-camera/signatures/arlo-camera-offSignature-phone-side.sig.complete";
 196
 197         // Amazon Alexa experiment
 198 //        final String inputPcapFile = path + "/training/amazon-alexa/wlan1/alexa2.wlan1.local.pcap";
 199 //        // TP-Link Plug DEVICE signatures
 200 //        final String onSignatureFile = path + "/training/amazon-alexa/signatures/amazon-alexa-onSignature-device-side.sig";
 201 //        final String offSignatureFile = path + "/training/amazon-alexa/signatures/amazon-alexa-offSignature-device-side.sig";
 202
 203         // SmartThings Plug experiment
 204 //        final String inputPcapFile = path + "/training/st-plug/wlan1/st-plug.wlan1.local.pcap";
 205 //        // SmartThings Plug DEVICE signatures
 206 //        //final String onSignatureFile = path + "/training/st-plug/signatures/st-plug-onSignature-device-side.sig";
 207 //        //final String offSignatureFile = path + "/training/st-plug/signatures/st-plug-offSignature-device-side.sig";
 208 //        // SmartThings Plug PHONE signatures
 209 //        final String onSignatureFile = path + "/training/st-plug/signatures/st-plug-onSignature-phone-side.sig";
 210 //        final String offSignatureFile = path + "/training/st-plug/signatures/st-plug-offSignature-phone-side.sig";
 211         // TODO: EXPERIMENT - November 12, 2018
 212         // SmartThings Plug experiment
 213 //        final String inputPcapFile = path + "/experimental_result/standalone/st-plug/wlan1/st-plug.wlan1.local.pcap";
 214 //        final String inputPcapFile = path + "/experimental_result/standalone/st-plug/eth0/st-plug.eth0.local.pcap";
 215 //        //final String inputPcapFile = path + "/experimental_result/smarthome/st-plug/wlan1/st-plug.wlan1.detection.pcap";
 216         final String inputPcapFile = path + "/experimental_result/smarthome/st-plug/eth0/st-plug.eth0.detection.pcap";
 217 //        // SmartThings Plug PHONE signatures
 218         final String onSignatureFile = path + "/experimental_result/standalone/st-plug/signatures/st-plug-onSignature-phone-side.sig";
 219         final String offSignatureFile = path + "/experimental_result/standalone/st-plug/signatures/st-plug-offSignature-phone-side.sig";
 220 //        final String onSignatureFile = path + "/training/signatures/st-plug/st-plug-onSignature-phone-side.sig";
 221 //        final String offSignatureFile = path + "/training/signatures/st-plug/st-plug-offSignature-phone-side.sig";
 222
 223         // TODO: EXPERIMENT - January 9, 2018
 224         // Blossom Sprinkler experiment
 225 ////        final String inputPcapFile = path + "/experimental_result/standalone/blossom-sprinkler/wlan1/blossom-sprinkler.wlan1.local.pcap";
 226 //        final String inputPcapFile = path + "/experimental_result/smarthome/blossom-sprinkler/eth0/blossom-sprinkler.eth0.detection.pcap";
 227 ////        final String inputPcapFile = path + "/experimental_result/smarthome/blossom-sprinkler/wlan1/blossom-sprinkler.wlan1.detection.pcap";
 228 //        // Blossom Sprinkler DEVICE signatures
 229 //        final String onSignatureFile = path + "/experimental_result/standalone/blossom-sprinkler/signatures/blossom-sprinkler-onSignature-device-side.sig";
 230 //        final String offSignatureFile = path + "/experimental_result/standalone/blossom-sprinkler/signatures/blossom-sprinkler-offSignature-device-side.sig";
 231 //        // Blossom Sprinkler PHONE signatures
 232 ////        final String onSignatureFile = path + "/experimental_result/standalone/blossom-sprinkler/signatures/blossom-sprinkler-onSignature-phone-side.sig";
 233 ////        final String offSignatureFile = path + "/experimental_result/standalone/blossom-sprinkler/signatures/blossom-sprinkler-offSignature-phone-side.sig";
 234
 235         // LiFX Bulb experiment
 236 //        final String inputPcapFile = path + "/training/lifx-bulb/wlan1/lifx-bulb.wlan1.local.pcap";
 237 //        // LiFX Bulb DEVICE signatures
 238 //        final String onSignatureFile = path + "/training/lifx-bulb/signatures/lifx-bulb-onSignature-device-side.sig";
 239 //        final String offSignatureFile = path + "/training/lifx-bulb/signatures/lifx-bulb-offSignature-device-side.sig";
 240         // LiFX Bulb PHONE signatures
 241 //        final String onSignatureFile = path + "/training/lifx-bulb/signatures/lifx-bulb-onSignature-phone-side.sig";
 242 //        final String offSignatureFile = path + "/training/lifx-bulb/signatures/lifx-bulb-offSignature-phone-side.sig";
 243
 244         // Blossom Sprinkler experiment
 245 //        //final String inputPcapFile = path + "/training/blossom-sprinkler/wlan1/blossom-sprinkler.wlan1.local.pcap";
 246 //        final String inputPcapFile = path + "/2018-08/blossom/blossom.wlan1.local.pcap";
 247 //        //final String inputPcapFile = path + "/training/blossom-sprinkler/eth0/blossom-sprinkler.eth0.local.pcap";
 248 //        // Blossom Sprinkler DEVICE signatures
 249 //        final String onSignatureFile = path + "/training/blossom-sprinkler/signatures/blossom-sprinkler-onSignature-device-side.sig";
 250 //        final String offSignatureFile = path + "/training/blossom-sprinkler/signatures/blossom-sprinkler-offSignature-device-side.sig";
 251
 252         // Nest Thermostat experiment
 253 //        final String inputPcapFile = path + "/training/nest-thermostat/wlan1/nest-thermostat.wlan1.local.pcap";
 254 //        // Nest Thermostat DEVICE signatures
 255 ////        final String onSignatureFile = path + "/training/nest-thermostat/signatures/nest-thermostat-onSignature-device-side.sig";
 256 ////        final String offSignatureFile = path + "/training/nest-thermostat/signatures/nest-thermostat-offSignature-device-side.sig";
 257 //        // Nest Thermostat PHONE signatures
 258 //        final String onSignatureFile = path + "/training/nest-thermostat/signatures/nest-thermostat-onSignature-phone-side.sig";
 259 //        final String offSignatureFile = path + "/training/nest-thermostat/signatures/nest-thermostat-offSignature-phone-side.sig";
 260 //        // TODO: EXPERIMENT - November 15, 2018
 261         // Nest Thermostat experiment
 262 //        final String inputPcapFile = path + "/experimental_result/standalone/nest-thermostat/wlan1/nest-thermostat.wlan1.local.pcap";
 263 ////        final String inputPcapFile = path + "/experimental_result/standalone/nest-thermostat/eth0/nest-thermostat.eth0.local.pcap";
 264 ////        final String inputPcapFile = path + "/experimental_result/smarthome/nest-thermostat/wlan1/nest-thermostat.wlan1.detection.pcap";
 265 ////        final String inputPcapFile = path + "/experimental_result/smarthome/nest-thermostat/eth0/nest-thermostat.eth0.detection.pcap";
 266 ////        // Nest Thermostat PHONE signatures
 267 //        final String onSignatureFile = path + "/experimental_result/standalone/nest-thermostat/signatures/nest-thermostat-onSignature-phone-side.sig";
 268 //        final String offSignatureFile = path + "/experimental_result/standalone/nest-thermostat/signatures/nest-thermostat-offSignature-phone-side.sig";
 269
 270         /*
 271         // Hue Bulb experiment
 272         final String inputPcapFile = path + "/training/hue-bulb/wlan1/hue-bulb.wlan1.local.pcap";
 273         // Hue Bulb PHONE signatures
 274         final String onSignatureFile = path + "/training/hue-bulb/signatures/hue-bulb-onSignature-phone-side.sig";
 275         final String offSignatureFile = path + "/training/hue-bulb/signatures/hue-bulb-offSignature-phone-side.sig";
 276         */
 277
 278
 279
 280         // TP-Link Bulb experiment
 281 //        final String inputPcapFile = path + "/training/tplink-bulb/wlan1/tplink-bulb.wlan1.local.pcap";
 282 //        // TP-Link Bulb PHONE signatures
 283 //        final String onSignatureFile = path + "/training/tplink-bulb/signatures/tplink-bulb-onSignature-phone-side.sig";
 284 //        final String offSignatureFile = path + "/training/tplink-bulb/signatures/tplink-bulb-offSignature-phone-side.sig";
 285         // TODO: EXPERIMENT - November 16, 2018
 286         // TP-Link Bulb experiment
 287 //        final String inputPcapFile = path + "/experimental_result/standalone/tplink-bulb/wlan1/tplink-bulb.wlan1.local.pcap";
 288 //        final String inputPcapFile = path + "/experimental_result/standalone/tplink-bulb/eth0/tplink-bulb.eth0.local.pcap";
 289 //        final String inputPcapFile = path + "/experimental_result/smarthome/tplink-bulb/wlan1/tplink-bulb.wlan1.detection.pcap";
 290 ////        final String inputPcapFile = path + "/experimental_result/smarthome/tplink-bulb/eth0/tplink-bulb.eth0.detection.pcap";
 291 //        // TP-Link Bulb PHONE signatures
 292 //        final String onSignatureFile = path + "/experimental_result/standalone/tplink-bulb/signatures/tplink-bulb-onSignature-phone-side.sig";
 293 //        final String offSignatureFile = path + "/experimental_result/standalone/tplink-bulb/signatures/tplink-bulb-offSignature-phone-side.sig";
 294
 295         /*
 296         // WeMo Plug experiment
 297         final String inputPcapFile = path + "/training/wemo-plug/wlan1/wemo-plug.wlan1.local.pcap";
 298         // WeMo Plug PHONE signatures
 299         final String onSignatureFile = path + "/training/wemo-plug/signatures/wemo-plug-onSignature-device-side.sig";
 300         final String offSignatureFile = path + "/training/wemo-plug/signatures/wemo-plug-offSignature-device-side.sig";
 301         */
 302         // TODO: EXPERIMENT - November 20, 2018
 303         // WeMo Plug experiment
 304 //        final String inputPcapFile = path + "/experimental_result/standalone/wemo-plug/wlan1/wemo-plug.wlan1.local.pcap";
 305 //        final String inputPcapFile = path + "/experimental_result/standalone/wemo-plug/eth0/wemo-plug.eth0.local.pcap";
 306         // TODO: WE HAVE 4 ADDITIONAL EVENTS (TRIGGERED MANUALLY), SO WE JUST IGNORE THEM BECAUSE THEY HAPPENED BEFORE
 307         // TODO: THE ACTUAL TRIGGERS
 308 //        final String inputPcapFile = path + "/experimental_result/smarthome/wemo-plug/wlan1/wemo-plug.wlan1.detection.pcap";
 309 ////        final String inputPcapFile = path + "/experimental_result/smarthome/wemo-plug/eth0/wemo-plug.eth0.detection.pcap";
 310 //        // WeMo Plug PHONE signatures
 311 //        final String onSignatureFile = path + "/experimental_result/standalone/wemo-plug/signatures/wemo-plug-onSignature-phone-side.sig";
 312 //        final String offSignatureFile = path + "/experimental_result/standalone/wemo-plug/signatures/wemo-plug-offSignature-phone-side.sig";
 313
 314         /*
 315         // WeMo Insight Plug experiment
 316         final String inputPcapFile = path + "/training/wemo-insight-plug/wlan1/wemo-insight-plug.wlan1.local.pcap";
 317         // WeMo Insight Plug PHONE signatures
 318         final String onSignatureFile = path + "/training/wemo-insight-plug/signatures/wemo-insight-plug-onSignature-device-side.sig";
 319         final String offSignatureFile = path + "/training/wemo-insight-plug/signatures/wemo-insight-plug-offSignature-device-side.sig";
 320         */
 321         // TODO: EXPERIMENT - November 21, 2018
 322         // WeMo Insight Plug experiment
 323 //        final String inputPcapFile = path + "/experimental_result/standalone/wemo-insight-plug/wlan1/wemo-insight-plug.wlan1.local.pcap";
 324 //        final String inputPcapFile = path + "/experimental_result/standalone/wemo-insight-plug/eth0/wemo-insight-plug.eth0.local.pcap";
 325         // TODO: WE HAVE 1 ADDITIONAL EVENT (FROM WEMO PLUG)
 326 //        final String inputPcapFile = path + "/experimental_result/smarthome/wemo-insight-plug/wlan1/wemo-insight-plug.wlan1.detection.pcap";
 327 //        final String inputPcapFile = path + "/experimental_result/smarthome/wemo-insight-plug/eth0/wemo-insight-plug.eth0.detection.pcap";
 328         // WeMo Insight Plug PHONE signatures
 329 //        final String onSignatureFile = path + "/experimental_result/standalone/wemo-insight-plug/signatures/wemo-insight-plug-onSignature-phone-side.sig";
 330 //        final String offSignatureFile = path + "/experimental_result/standalone/wemo-insight-plug/signatures/wemo-insight-plug-offSignature-phone-side.sig";
 331
 332
 333         // Kwikset Doorlock Sep 12 experiment
 334 //        final String inputPcapFile = path + "/2018-08/kwikset-doorlock/kwikset3.wlan1.local.pcap";
 335 //        // Kwikset Doorlock PHONE signatures
 336 //        final String onSignatureFile = path + "/2018-08/kwikset-doorlock/onSignature-Kwikset-Doorlock-phone.sig";
 337 //        final String offSignatureFile = path + "/2018-08/kwikset-doorlock/offSignature-Kwikset-Doorlock-phone.sig";
 338         // TODO: EXPERIMENT - November 10, 2018
 339         // Kwikset Door lock experiment
 340 //        final String inputPcapFile = path + "/experimental_result/standalone/kwikset-doorlock/wlan1/kwikset-doorlock.wlan1.local.pcap";
 341         //final String inputPcapFile = path + "/experimental_result/smarthome/kwikset-doorlock/wlan1/kwikset-doorlock.wlan1.detection.pcap";
 342 //        final String inputPcapFile = path + "/experimental_result/smarthome/kwikset-doorlock/eth0/kwikset-doorlock.eth0.detection.pcap";
 343 //        // Kwikset Door lock PHONE signatures
 344 //        final String onSignatureFile = path + "/experimental_result/standalone/kwikset-doorlock/signatures/kwikset-doorlock-onSignature-phone-side.sig";
 345 //        final String offSignatureFile = path + "/experimental_result/standalone/kwikset-doorlock/signatures/kwikset-doorlock-offSignature-phone-side.sig";
 346 ////        final String onSignatureFile = path + "/training/signatures/kwikset-doorlock/kwikset-doorlock-onSignature-phone-side.sig";
 347 ////        final String offSignatureFile = path + "/training/signatures/kwikset-doorlock/kwikset-doorlock-offSignature-phone-side.sig";
 348
 349
 350
 351         // D-Link Siren experiment
 352 //        final String inputPcapFile = path + "/2018-08/dlink-siren/dlink-siren.wlan1.local.pcap";
 353         // D-Link Siren DEVICE signatures
 354         //final String onSignatureFile = path + "/2018-08/dlink-siren/onSignature-DLink-Siren-device.sig";
 355         //final String offSignatureFile = path + "/2018-08/dlink-siren/offSignature-DLink-Siren-device.sig";
 356         // D-Link Siren PHONE signatures
 357 //        final String onSignatureFile = path + "/2018-08/dlink-siren/onSignature-DLink-Siren-phone.sig";
 358 //        final String offSignatureFile = path + "/2018-08/dlink-siren/offSignature-DLink-Siren-phone.sig";
 359
 360
 361         // Output file names used (to make it easy to catch if one forgets to change them)
 362         System.out.println("ON signature file in use is " + onSignatureFile);
 363         System.out.println("OFF signature file in use is " + offSignatureFile);
 364         System.out.println("PCAP file that is the target of detection is " + inputPcapFile);
 365
 366         List<List<List<PcapPacket>>> onSignature = PrintUtils.deserializeSignatureFromFile(onSignatureFile);
 367         List<List<List<PcapPacket>>> offSignature = PrintUtils.deserializeSignatureFromFile(offSignatureFile);
 368
 369         // LAN
 370 //        SignatureDetector onDetector = new SignatureDetector(onSignature, null);
 371 //        SignatureDetector offDetector = new SignatureDetector(offSignature, null);
 372
 373         // TODO: We need the array that contains other signatures so that we can check for overlap and decide
 374         // TODO: whether we use conservative or range-based matching
 375         // Right now we have ON signature as other signature for OFF and OFF signature as other signature for ON
 376         // In the future, we might have more other signatures
 377         List<List<List<List<PcapPacket>>>> otherSignaturesOutsideOn = new ArrayList<>();
 378         otherSignaturesOutsideOn.add(offSignature);
 379         List<List<List<List<PcapPacket>>>> otherSignaturesOutsideOff = new ArrayList<>();
 380         otherSignaturesOutsideOff.add(onSignature);
 381
 382         // WAN
 383         SignatureDetector onDetector = new SignatureDetector(onSignature, "128.195.205.105", 0,
 384                 otherSignaturesOutsideOn);
 385         SignatureDetector offDetector = new SignatureDetector(offSignature, "128.195.205.105", 0,
 386                 otherSignaturesOutsideOff);
 387
 388         final DateTimeFormatter dateTimeFormatter = DateTimeFormatter.ofLocalizedDateTime(FormatStyle.MEDIUM).
 389                 withLocale(Locale.US).withZone(ZoneId.of("America/Los_Angeles"));
 390
 391         // Outputs information about a detected event to std.out
 392         final Consumer<UserAction> outputter = ua -> {
 393             String eventDescription;
 394             switch (ua.getType()) {
 395                 case TOGGLE_ON:
 396                     eventDescription = "ON";
 397                     break;
 398                 case TOGGLE_OFF:
 399                     eventDescription = "OFF";
 400                     break;
 401                 default:
 402                     throw new AssertionError("unhandled event type");
 403             }
 404             //String output = String.format("[ !!! %s SIGNATURE DETECTED at %s !!! ]",
 405             //      eventDescription, dateTimeFormatter.format(ua.getTimestamp()));
 406             String output = String.format("%s",
 407                     dateTimeFormatter.format(ua.getTimestamp()));
 408             System.out.println(output);
 409         };
 410
 411         // Let's create observers that construct a UserAction representing the detected event.
 412         final List<UserAction> detectedEvents = new ArrayList<>();
 413         onDetector.addObserver((searched, match) -> {
 414             PcapPacket firstPkt = match.get(0).get(0);
 415             detectedEvents.add(new UserAction(UserAction.Type.TOGGLE_ON, firstPkt.getTimestamp()));
 416         });
 417         offDetector.addObserver((searched, match) -> {
 418             PcapPacket firstPkt = match.get(0).get(0);
 419             detectedEvents.add(new UserAction(UserAction.Type.TOGGLE_OFF, firstPkt.getTimestamp()));
 420         });
 421
 422         PcapHandle handle;
 423         try {
 424             handle = Pcaps.openOffline(inputPcapFile, PcapHandle.TimestampPrecision.NANO);
 425         } catch (PcapNativeException pne) {
 426             handle = Pcaps.openOffline(inputPcapFile);
 427         }
 428         PcapHandleReader reader = new PcapHandleReader(handle, p -> true, onDetector, offDetector);
 429         reader.readFromHandle();
 430
 431         //if (onDetector.isConservativeChecking(offSignature)) {
 432         // System.out.println("Do conservative checking!");
 433         //} else {
 434         // TODO: WORK ON THIS RANGE-BASED CHECKING
 435         // System.out.println("Do range-based checking!");
 436         //}
 437
 438         // TODO: need a better way of triggering detection than this...
 439         onDetector.mClusterMatchers.forEach(cm -> cm.performDetection());
 440         offDetector.mClusterMatchers.forEach(cm -> cm.performDetection());
 441
 442         // Sort the list of detected events by timestamp to make it easier to compare it line-by-line with the trigger
 443         // times file.
 444         Collections.sort(detectedEvents, Comparator.comparing(UserAction::getTimestamp));
 445
 446         // Output the detected events
 447         detectedEvents.forEach(outputter);
 448
 449         System.out.println("Number of detected events of type " + UserAction.Type.TOGGLE_ON + ": " +
 450                 detectedEvents.stream().filter(ua -> ua.getType() == UserAction.Type.TOGGLE_ON).count());
 451         System.out.println("Number of detected events of type " + UserAction.Type.TOGGLE_OFF + ": " +
 452                 detectedEvents.stream().filter(ua -> ua.getType() == UserAction.Type.TOGGLE_OFF).count());
 453
 454
 455         // TODO: Temporary clean up until we clean the pipeline
 456 //      List<UserAction> cleanedDetectedEvents = SignatureDetector.removeDuplicates(detectedEvents);
 457 //      cleanedDetectedEvents.forEach(outputter);
 458
 459     }
 460
 461     /**
 462      * The signature that this {@link SignatureDetector} is searching for.
 463      */
 464     private final List<List<List<PcapPacket>>> mSignature;
 465
 466     /**
 467      * The {@link Layer3ClusterMatcher}s in charge of detecting each individual sequence of packets that together make up the
 468      * the signature.
 469      */
 470     private final List<Layer3ClusterMatcher> mClusterMatchers;
 471
 472     /**
 473      * For each {@code i} ({@code i >= 0 && i < pendingMatches.length}), {@code pendingMatches[i]} holds the matches
 474      * found by the {@link Layer3ClusterMatcher} at {@code mClusterMatchers.get(i)} that have yet to be "consumed", i.e.,
 475      * have yet to be included in a signature detected by this {@link SignatureDetector} (a signature can be encompassed
 476      * of multiple packet sequences occurring shortly after one another on multiple connections).
 477      */
 478     private final List<List<PcapPacket>>[] pendingMatches;
 479
 480     /**
 481      * Maps a {@link Layer3ClusterMatcher} to its corresponding index in {@link #pendingMatches}.
 482      */
 483     private final Map<Layer3ClusterMatcher, Integer> mClusterMatcherIds;
 484
 485     private final List<SignatureDetectionObserver> mObservers = new ArrayList<>();
 486
 487     private int mInclusionTimeMillis;
 488
 489     /**
 490      * Remove duplicates in {@code List} of {@code UserAction} objects. We need to clean this up for user actions
 491      * that appear multiple times.
 492      * TODO: This static method is probably just for temporary and we could get rid of this after we clean up
 493      * TODO:    the pipeline
 494      *
 495      * @param listUserAction A {@link List} of {@code UserAction}.
 496      *
 497      */
 498     public static List<UserAction> removeDuplicates(List<UserAction> listUserAction) {
 499
 500         // Iterate and check for duplicates (check timestamps)
 501         Set<Long> epochSecondSet = new HashSet<>();
 502         // Create a target list for cleaned up list
 503         List<UserAction> listUserActionClean = new ArrayList<>();
 504         for(UserAction userAction : listUserAction) {
 505             // Don't insert if any duplicate is found
 506             if(!epochSecondSet.contains(userAction.getTimestamp().getEpochSecond())) {
 507                 listUserActionClean.add(userAction);
 508                 epochSecondSet.add(userAction.getTimestamp().getEpochSecond());
 509             }
 510         }
 511         return listUserActionClean;
 512     }
 513
 514 //    /**
 515 //     * Check if there is any overlap between the signature stored in this class and another signature.
 516 //     * Conditions:
 517 //     * 1) If both signatures do not have any range, then we need to do conservative checking (return true).
 518 //     * 2) If both signatures have the same number of packets/packet lengths, then we check the range; if the
 519 //     *    numbers of packets/packet lengths are different then we assume that there is no overlap.
 520 //     * 3) If there is any range in the signatures, then we need to check for overlap.
 521 //     * 4) If there is overlap for every packet/packet length, then we return false (range-based checking); otherwise,
 522 //     *    true (conservative checking).
 523 //     *
 524 //     * @param otherSignature A {@code List} of {@code List} of {@code List} of {@code PcapPacket} objects to be checked
 525 //     *                       for overlaps with the signature stored in this class.
 526 //     * @return A boolean that is true if there is an overlap; false otherwise.
 527 //     */
 528 //    public boolean isConservativeChecking(List<List<List<PcapPacket>>> otherSignature) {
 529 //
 530 //        // Get the ranges of the two signatures
 531 //        List<List<List<PcapPacket>>> signatureRanges = getSequenceRanges(mSignature);
 532 //        List<List<List<PcapPacket>>> otherSignatureRanges = getSequenceRanges(otherSignature);
 533 //        if (!isRangeBased(signatureRanges) && !isRangeBased(otherSignatureRanges)) {
 534 //            // Conservative checking when there is no range
 535 //            return true;
 536 //        } else if(signatureRanges.size() != otherSignatureRanges.size()) {
 537 //            // The two signatures have different numbers of packets/packet lengths
 538 //            return false;
 539 //        } else {
 540 //            // There is range; check if there is overlap
 541 //            return checkOverlap(signatureRanges, otherSignatureRanges);
 542 //        }
 543 //    }
 544 //
 545 //    /*
 546 //     * Check for overlap since we have range in at least one of the signatures.
 547 //     * Overlap is only true when all ranges overlap. We need to check in order.
 548 //     */
 549 //    private boolean checkOverlap(List<List<List<PcapPacket>>> signatureRanges,
 550 //                                 List<List<List<PcapPacket>>> otherSignatureRanges) {
 551 //
 552 //        for(List<List<PcapPacket>> listListPcapPacket : signatureRanges) {
 553 //            // Lower bound of the range is in index 0
 554 //            // Upper bound of the range is in index 1
 555 //            int sequenceSetIndex = signatureRanges.indexOf(listListPcapPacket);
 556 //            List<PcapPacket> minSequenceSignature = listListPcapPacket.get(0);
 557 //            List<PcapPacket> maxSequenceSignature = listListPcapPacket.get(1);
 558 //            for(PcapPacket pcapPacket : minSequenceSignature) {
 559 //                // Get the lower and upper bounds of the current signature
 560 //                int packetIndex = minSequenceSignature.indexOf(pcapPacket);
 561 //                int lowerBound = pcapPacket.length();
 562 //                int upperBound = maxSequenceSignature.get(packetIndex).length();
 563 //                // Check for range overlap in the other signature!
 564 //                // Check the packet/packet length at the same position
 565 //                List<PcapPacket> minSequenceSignatureOther = otherSignatureRanges.get(sequenceSetIndex).get(0);
 566 //                List<PcapPacket> maxSequenceSignatureOther = otherSignatureRanges.get(sequenceSetIndex).get(1);
 567 //                int lowerBoundOther = minSequenceSignatureOther.get(packetIndex).length();
 568 //                int upperBoundOther = maxSequenceSignatureOther.get(packetIndex).length();
 569 //                if (!(lowerBoundOther <= lowerBound && lowerBound <= upperBoundOther) &&
 570 //                    !(lowerBoundOther <= upperBound && upperBound <= upperBoundOther)) {
 571 //                    return false;
 572 //                }
 573 //            }
 574 //        }
 575 //
 576 //        return true;
 577 //    }
 578 //
 579 //    /*
 580 //     * Check and see if there is any range in the signatures
 581 //     */
 582 //    private boolean isRangeBased(List<List<List<PcapPacket>>> signatureRanges) {
 583 //
 584 //        for(List<List<PcapPacket>> listListPcapPacket : signatureRanges) {
 585 //            // Lower bound of the range is in index 0
 586 //            // Upper bound of the range is in index 1
 587 //            List<PcapPacket> minSequence = listListPcapPacket.get(0);
 588 //            List<PcapPacket> maxSequence = listListPcapPacket.get(1);
 589 //            for(PcapPacket pcapPacket : minSequence) {
 590 //                int index = minSequence.indexOf(pcapPacket);
 591 //                if (pcapPacket.length() != maxSequence.get(index).length()) {
 592 //                    // If there is any packet length that differs in the minSequence
 593 //                    // and maxSequence, then it is range-based
 594 //                    return true;
 595 //                }
 596 //            }
 597 //        }
 598 //
 599 //        return false;
 600 //    }
 601
 602     /* Find the sequence with the minimum packet lengths.
 603      * The second-layer list should contain the minimum sequence for element 0 and maximum sequence for element 1.
 604      */
 605     private List<List<List<PcapPacket>>> getSequenceRanges(List<List<List<PcapPacket>>> signature) {
 606
 607         // Start from the first index
 608         List<List<List<PcapPacket>>> rangeBasedSequence = new ArrayList<>();
 609         for(List<List<PcapPacket>> listListPcapPacket : signature) {
 610             List<List<PcapPacket>> minMaxSequence = new ArrayList<>();
 611             // Both searches start from index 0
 612             List<PcapPacket> minSequence = new ArrayList<>(listListPcapPacket.get(0));
 613             List<PcapPacket> maxSequence = new ArrayList<>(listListPcapPacket.get(0));
 614             for(List<PcapPacket> listPcapPacket : listListPcapPacket) {
 615                 for(PcapPacket pcapPacket : listPcapPacket) {
 616                     int index = listPcapPacket.indexOf(pcapPacket);
 617                     // Set the new minimum if length at the index is minimum
 618                     if (pcapPacket.length() < minSequence.get(index).length()) {
 619                         minSequence.set(index, pcapPacket);
 620                     }
 621                     // Set the new maximum if length at the index is maximum
 622                     if (pcapPacket.length() > maxSequence.get(index).length()) {
 623                         maxSequence.set(index, pcapPacket);
 624                     }
 625                 }
 626             }
 627             // minSequence as element 0 and maxSequence as element 1
 628             minMaxSequence.add(minSequence);
 629             minMaxSequence.add(maxSequence);
 630             rangeBasedSequence.add(minMaxSequence);
 631         }
 632
 633         return rangeBasedSequence;
 634     }
 635
 636     public SignatureDetector(List<List<List<PcapPacket>>> searchedSignature, String routerWanIp, int inclusionTimeMillis,
 637                              List<List<List<List<PcapPacket>>>> otherSignatures) {
 638         // note: doesn't protect inner lists from changes :'(
 639         mSignature = Collections.unmodifiableList(searchedSignature);
 640         // Generate corresponding/appropriate ClusterMatchers based on the provided signature
 641         List<Layer3ClusterMatcher> clusterMatchers = new ArrayList<>();
 642         for (List<List<PcapPacket>> cluster : mSignature) {
 643             clusterMatchers.add(new Layer3ClusterMatcher(cluster, routerWanIp, otherSignatures, this));
 644         }
 645         mClusterMatchers = Collections.unmodifiableList(clusterMatchers);
 646
 647         // < exploratory >
 648         pendingMatches = new List[mClusterMatchers.size()];
 649         for (int i = 0; i < pendingMatches.length; i++) {
 650             pendingMatches[i] = new ArrayList<>();
 651         }
 652         Map<Layer3ClusterMatcher, Integer> clusterMatcherIds = new HashMap<>();
 653         for (int i = 0; i < mClusterMatchers.size(); i++) {
 654             clusterMatcherIds.put(mClusterMatchers.get(i), i);
 655         }
 656         mClusterMatcherIds = Collections.unmodifiableMap(clusterMatcherIds);
 657         mInclusionTimeMillis =
 658                 inclusionTimeMillis == 0 ? TriggerTrafficExtractor.INCLUSION_WINDOW_MILLIS : inclusionTimeMillis;
 659     }
 660
 661     public void addObserver(SignatureDetectionObserver observer) {
 662         mObservers.add(observer);
 663     }
 664
 665     public boolean removeObserver(SignatureDetectionObserver observer) {
 666         return mObservers.remove(observer);
 667     }
 668
 669     @Override
 670     public void gotPacket(PcapPacket packet) {
 671         // simply delegate packet reception to all ClusterMatchers.
 672         mClusterMatchers.forEach(cm -> cm.gotPacket(packet));
 673     }
 674
 675     @Override
 676     public void onMatch(AbstractClusterMatcher clusterMatcher, List<PcapPacket> match) {
 677         // Add the match at the corresponding index
 678         pendingMatches[mClusterMatcherIds.get(clusterMatcher)].add(match);
 679         checkSignatureMatch();
 680     }
 681
 682     private void checkSignatureMatch() {
 683         // << Graph-based approach using Balint's idea. >>
 684         // This implementation assumes that the packets in the inner lists (the sequences) are ordered by asc timestamp.
 685
 686         // There cannot be a signature match until each Layer3ClusterMatcher has found a match of its respective sequence.
 687         if (Arrays.stream(pendingMatches).noneMatch(l -> l.isEmpty())) {
 688             // Construct the DAG
 689             final SimpleDirectedWeightedGraph<Vertex, DefaultWeightedEdge> graph =
 690                     new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
 691             // Add a vertex for each match found by all ClusterMatchers
 692             // And maintain an array to keep track of what cluster matcher each vertex corresponds to
 693             final List<Vertex>[] vertices = new List[pendingMatches.length];
 694             for (int i = 0; i < pendingMatches.length; i++) {
 695                 vertices[i] = new ArrayList<>();
 696                 for (List<PcapPacket> sequence : pendingMatches[i]) {
 697                     Vertex v = new Vertex(sequence);
 698                     vertices[i].add(v); // retain reference for later when we are to add edges
 699                     graph.addVertex(v); // add to vertex to graph
 700                 }
 701             }
 702             // Add dummy source and sink vertices to facilitate search.
 703             final Vertex source = new Vertex(null);
 704             final Vertex sink = new Vertex(null);
 705             graph.addVertex(source);
 706             graph.addVertex(sink);
 707             // The source is connected to all vertices that wrap the sequences detected by Layer3ClusterMatcher at index 0.
 708             // Note: zero cost edges as this is just a dummy link to facilitate search from a common start node.
 709             for (Vertex v : vertices[0]) {
 710                 DefaultWeightedEdge edge = graph.addEdge(source, v);
 711                 graph.setEdgeWeight(edge, 0.0);
 712             }
 713             // Similarly, all vertices that wrap the sequences detected by the last Layer3ClusterMatcher of the signature
 714             // are connected to the sink node.
 715             for (Vertex v : vertices[vertices.length-1]) {
 716                 DefaultWeightedEdge edge = graph.addEdge(v, sink);
 717                 graph.setEdgeWeight(edge, 0.0);
 718             }
 719             // Now link sequences detected by Layer3ClusterMatcher at index i to sequences detected by Layer3ClusterMatcher at index
 720             // i+1 if they obey the timestamp constraint (i.e., that the latter is later in time than the former).
 721             for (int i = 0; i < vertices.length; i++) {
 722                 int j = i + 1;
 723                 if (j < vertices.length) {
 724                     for (Vertex iv : vertices[i]) {
 725                         PcapPacket ivLast = iv.sequence.get(iv.sequence.size()-1);
 726                         for (Vertex jv : vertices[j]) {
 727                             PcapPacket jvFirst = jv.sequence.get(jv.sequence.size()-1);
 728                             if (ivLast.getTimestamp().isBefore(jvFirst.getTimestamp())) {
 729                                 DefaultWeightedEdge edge = graph.addEdge(iv, jv);
 730                                 // The weight is the duration of the i'th sequence plus the duration between the i'th
 731                                 // and i+1'th sequence.
 732                                 Duration d = Duration.
 733                                         between(iv.sequence.get(0).getTimestamp(), jvFirst.getTimestamp());
 734                                 // Unfortunately weights are double values, so must convert from long to double.
 735                                 // TODO: need nano second precision? If so, use d.toNanos().
 736                                 // TODO: risk of overflow when converting from long to double..?
 737                                 graph.setEdgeWeight(edge, Long.valueOf(d.toMillis()).doubleValue());
 738                             }
 739                             // Alternative version if we cannot assume that sequences are ordered by timestamp:
 740 //                            if (iv.sequence.stream().max(Comparator.comparing(PcapPacket::getTimestamp)).get()
 741 //                                    .getTimestamp().isBefore(jv.sequence.stream().min(
 742 //                                            Comparator.comparing(PcapPacket::getTimestamp)).get().getTimestamp())) {
 743 //
 744 //                            }
 745                         }
 746                     }
 747                 }
 748             }
 749             // Graph construction complete, run shortest-path to find a (potential) signature match.
 750             DijkstraShortestPath<Vertex, DefaultWeightedEdge> dijkstra = new DijkstraShortestPath<>(graph);
 751             GraphPath<Vertex, DefaultWeightedEdge> shortestPath = dijkstra.getPath(source, sink);
 752             if (shortestPath != null) {
 753                 // The total weight is the duration between the first packet of the first sequence and the last packet
 754                 // of the last sequence, so we simply have to compare the weight against the timeframe that we allow
 755                 // the signature to span. For now we just use the inclusion window we defined for training purposes.
 756                 // Note however, that we must convert back from double to long as the weight is stored as a double in
 757                 // JGraphT's API.
 758                 if (((long)shortestPath.getWeight()) < mInclusionTimeMillis) {
 759                     // There's a signature match!
 760                     // Extract the match from the vertices
 761                     List<List<PcapPacket>> signatureMatch = new ArrayList<>();
 762                     for(Vertex v : shortestPath.getVertexList()) {
 763                         if (v == source || v == sink) {
 764                             // Skip the dummy source and sink nodes.
 765                             continue;
 766                         }
 767                         signatureMatch.add(v.sequence);
 768                         // As there is a one-to-one correspondence between vertices[] and pendingMatches[], we know that
 769                         // the sequence we've "consumed" for index i of the matched signature is also at index i in
 770                         // pendingMatches. We must remove it from pendingMatches so that we don't use it to construct
 771                         // another signature match in a later call.
 772                         pendingMatches[signatureMatch.size()-1].remove(v.sequence);
 773                     }
 774                     // Declare success: notify observers
 775                     mObservers.forEach(obs -> obs.onSignatureDetected(mSignature,
 776                             Collections.unmodifiableList(signatureMatch)));
 777                 }
 778             }
 779         }
 780     }
 781
 782     /**
 783      * Used for registering for notifications of signatures detected by a {@link SignatureDetector}.
 784      */
 785     interface SignatureDetectionObserver {
 786
 787         /**
 788          * Invoked when the {@link SignatureDetector} detects the presence of a signature in the traffic that it's
 789          * examining.
 790          * @param searchedSignature The signature that the {@link SignatureDetector} reporting the match is searching
 791          *                          for.
 792          * @param matchingTraffic The actual traffic trace that matches the searched signature.
 793          */
 794         void onSignatureDetected(List<List<List<PcapPacket>>> searchedSignature,
 795                                  List<List<PcapPacket>> matchingTraffic);
 796     }
 797
 798     /**
 799      * Encapsulates a {@code List<PcapPacket>} so as to allow the list to be used as a vertex in a graph while avoiding
 800      * the expensive {@link AbstractList#equals(Object)} calls when adding vertices to the graph.
 801      * Using this wrapper makes the incurred {@code equals(Object)} calls delegate to {@link Object#equals(Object)}
 802      * instead of {@link AbstractList#equals(Object)}. The net effect is a faster implementation, but the graph will not
 803      * recognize two lists that contain the same items--from a value and not reference point of view--as the same
 804      * vertex. However, this is fine for our purposes -- in fact restricting it to reference equality seems more
 805      * appropriate.
 806      */
 807     private static class Vertex {
 808         private final List<PcapPacket> sequence;
 809         private Vertex(List<PcapPacket> wrappedSequence) {
 810             sequence = wrappedSequence;
 811         }
 812     }
 813 }