Joint anomaly detection across IOT devices

Systems and methods of the present disclosure provide technology to identify when network-connected devices are likely infected with malware. Network communications are be monitored during a specific time window and a graph is created for a conditional random field (CRF) model. Vertices of the graph represent devices connected to the network and an edge between two vertices indicates that one or more network communications occurred between two devices represented by the two vertices during the time window. Network devices can report observations about network behavior during the time window and the observations can be used as input for the CRF model. The CRF model can then be used to determine infection-status values for the network devices.

TECHNICAL FIELD

Embodiments presented in this disclosure generally relate to systems and methods for detecting anomalous network traffic behavior.

BACKGROUND

Many modern machines and devices are equipped to connect to networks. While traditional computers such as desktops and laptops have been designed to connect to wired and wireless networks for many years, many other types of modern devices and machines are now being designed to connect to networks. For example, many consumer devices like televisions (TVs), gaming consoles, and security systems are designed to send and receive data via networks, such as local area networks or the Internet. These “smart” devices provide greater functionality and convenience for people who wish to control, monitor, or otherwise access their devices remotely (e.g., using a smart phone). In addition, industrial devices such as remote sensors for wireless sensor networks are also being designed to connect to networks so that sensor readings can be rapidly transferred to data repositories. For both businesses and consumers, it is both convenient and useful to have devices that can connect to networks such as the Internet.

The Internet of Things (IoT) generally refers to the devices and machines embedded with electronics and software enabling these devices and machines to exchange data over a network (e.g., the Internet). The number of IoT devices connected to networks worldwide is poised to grow rapidly. While IoT devices offer promising conveniences, they also provide a large number of potential hosts that could be infected by malicious software through network connections. Malicious software (also called malware), such as viruses, worms, Trojans, malicious bots, spyware, ransomware, and adware, can infect various types of electronic devices and can cause a great deal of damage to valuable computer systems and devices.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

Systems and methods of the present disclosure address detecting network traffic anomalies at a gateway device by monitoring network communications that occur in between devices during a time window, creating a graph in which vertices represent devices in the network and an edges between two vertices indicates that the devices represented by the two vertices communicated with each other during the time window, and using the graph and observations made at the devices to determine measures of risk (e.g., infection-status values) for the devices. Specifically, the graph can be used in a conditional random field (CRF) model that determines the infection-status values for the devices collectively in a manner that allows context from all devices represented in the graph to be taken into account.

Example Embodiments

Embodiments presented herein provide systems and methods for detecting when devices in a network have been infected with malware based on network traffic patterns. In general, embodiments presented herein may be applied or implemented at network gateways. Embodiments presented herein further may incorporate individualized classifiers for respective devices connected to a network. An anomaly detector for the network may use outputs (e.g., anomaly-suspicion values) from the specially tailored individual classifiers and observations from the network-connected devices as input. The anomaly detector for the network may generate an undirected graph and determine infection-status values for the network-connected devices using a conditional random field (CRF) model applied to the graph. Vertices in the graph may represent nodes in the network, while an edge between two vertices in the graph may signify that at least one network communication was exchanged between those two vertices during a specified time window to which the graph applies.

Many types of malware can spread from one device to another via communications over a network. Once infected with malware, a device may engage in various types of network activities as a result of the malware infection. For example, an infected device may take part in a distributed denial-of-service (DoS) attack by sending one or more communications to a host for the purpose of overwhelming the host at a coordinated time when other infected devices also send communications to the host. In another example, a device infected with a worm may send communications over a local area network (LAN) for the purpose of spreading the worm to other devices that are connected to the LAN.

In some cases, the patterns of communication engaged in by a device infected by malware may noticeably change. For example, after a device is infected, the rate at which messages are sent, the types of messages that are sent, and the destinations to which messages are sent may change noticeably. Software for detecting anomalies in network-communication patterns can sometimes infer that a device is infected.

However, it is difficult to define globally what types of network-communication behavior should be regarded as anomalous because many devices may have different configurations and may use a network for different purposes. Diverse types of IoT devices, for example, may exhibit diverse types of network behavior. Furthermore, two devices of the same type may have configuration differences that cause them to exhibit different network communication patterns. In addition, even for a single device, different network-communication behavior patterns may be normal in one context, but anomalous in another context. A single device's network-communication patterns may also gradually change over time even in the absence of a malware infection.

Anomaly detectors that use global definitions of normal and anomalous network behavior are therefore very susceptible to giving false alarms (false positives) for devices whose network behavior aligns poorly with a global definition of what is normal. In order to avoid such false alarms, many anomaly detectors are configured to yield a very low number of false positives. This approach ultimately tends to favor precision and specificity at the expense of recall and sensitivity.

A one-size-fits-all approach that globally defines normal and anomalous network behavior tends to struggle with recall and sensitivity. In order to avoid this drawback, specialized anomaly detectors can be locally installed and trained on a device to learn a network-behavior model that is specifically tailored to that device. However, for some IoT devices, it may be impractical, to store, execute, or update a specialized anomaly detector locally due to limited memory, storage, processing, and power resources. Furthermore, a locally stored anomaly detector may lack the ability to take certain types of context information into account. For example, if a device with a local anomaly detector is connected to a LAN, the behavior of other devices connected to the LAN may constitute valuable context information—particularly if other devices on the LAN are infected with malware. A locally stored anomaly detector may be limited because it is unable to consider such context information.

Embodiments presented herein provide systems and methods for detecting anomalous network traffic with increased accuracy. In general, embodiments presented herein may be applied or implemented at network gateways. Embodiments presented herein further may incorporate specially tailored individual classifiers for respective devices connected to a network. An anomaly detector for the network may use outputs (e.g., anomaly-suspicion values) from the specially tailored individual classifiers and observations from the network-connected devices as input. The anomaly detector for the network may determine infection-status values for devices that are connected to the network based on a conditional random field (CRF) model and based on a graph. Vertices in the graph may represent nodes in the network, while an edge between two vertices in the graph may signify that at least one network communication was exchanged between those two vertices during a specified time window to which the graph applies. Technologies of the present disclosure may be particularly useful for networks that include IoT devices, since the specially tailored individual anomaly detectors for IoT devices may be stored and executed at the gateway (rather than on the devices themselves) alongside the anomaly detector for the network.

FIG. 1illustrates a computing environment100that may be used to apply techniques of the present disclosure, according to one embodiment. An IoT device108, an IoT device112, and a gateway104communicate via a network102. The gateway can include an anomaly detector106. The gateway104is also connected to the Internet116. The IoT device108and the IoT device112can include observer110and observer114, respectively, as shown. The observer110can make observations about the network behavior of the IoT device108over a period of time and send those observations to the anomaly detector106. Similarly, the observer114can make observations about the network behavior of the IoT device112over the same period of time and send those observations to the anomaly detector106. The observers110,114may be, for example, software units that are configured to measure predefined aspects of network behavior and report to the anomaly detector106.

The anomaly detector106uses the observations received from the observer110and the observer114to predict whether the IoT device108and the IoT device112are infected with malware. Based on the observations, the anomaly detector106may predict that it is highly likely that the IoT device108is infected with malware. In addition, if the observations indicate that the IoT device108sent a network communication to the IoT device112during the time period, the anomaly detector104may conclude that it is also highly likely that the IoT device112is also infected.

FIG. 2is a block diagram illustrating a more detailed view of an anomaly detector204within a gateway202, according to one embodiment. The anomaly detector204comprises a conditional random field (CRF) model224that includes a graph224, feature functions227, and weights228. The anomaly detector204may further comprise classifiers214a-j. The classifiers214a-jcorrespond to the devices212a-jin the sense that classifier214ais configured to predict an anomaly-suspicion value for device212a, classifier214bis configured to predict an anomaly-suspicion value for device212b, classifier214cis configured to predict an anomaly-suspicion value for device212c, and so forth for other classifiers up to and including classifier214j, which is configured to predict an anomaly-suspicion value for device212j.

The term “anomaly-suspicion value” generally refers to a value that indicates a level of how anomalous a device's network communication patterns during a specific period of time are judged to be by a classifier. Anomaly-suspicion values may be quantitative (e.g., continuous or discrete) or categorical and may have varying levels of granularity. In one relatively simple example, anomaly-suspicion values may be binary (e.g., 0 for non-suspicious and 1 for highly suspicious). In another example, anomaly-suspicion values may be real-valued numbers defined along a continuous range from 0 to 1 (e.g., wherein higher values indicate higher suspiciousness).

The classifiers214a-jmay be trained machine-learning models that use observations received from the devices212a-j, respectively, as input features or attributes. The classifier214a, for example, may use observations made by the device212aduring a time period as input and, in turn, output an anomaly-suspicion value for device212afor the time period. The observations made at the device212acan, in some examples, be compiled into an observation vector that is provided to the classifier214a. In the context of this disclosure, the term “vector” refers to an array or another data structure that contains multiple values. Such an observation vector is one example of a collection of performance metrics (e.g., observations) that describe a device's network behavior.

In some examples, each of the classifiers214a-jcan be trained and refined using training data so that each classifier is customized for the respective device to which it corresponds. Training data for a classifier may include, for example, training instances. A training instance for a classifier may comprise an observation vector for the classifier's respective device. In addition, a training instance for the classifier may optionally comprise an infection-status label indicating whether the respective device was infected with malware at the time when the observation vector was observed. The infection-status label can serve as the target value for the anomaly-suspicion value. Depending on the type of machine-learning model used, labeled and/or unlabeled training instances may be used for training.

Different types of inductive and transductive machine-learning models that may be used as the classifiers214a-j. Some examples of machine-learning models include adsorption models, neural networks, support vector machines, radial basis functions, Bayesian belief networks, association-rule models, decision trees, k-nearest-neighbor models, regression models, Hopfield networks, deep belief networks, and Q-learning models. Furthermore, pluralities of individual machine learning models can be combined to form ensemble machine-learning models. Ensemble machine-learning models may be homogenous (i.e., using multiple member models of the same type) or non-homogenous (i.e., using multiple member models of different types).

In general, the term “observation” may refer to, for example, a value that quantifies or categorizes some aspect of network behavior. Many different types of observations can be made at the devices212a-j, respectively. Some observations may pertain to issues of protocol. For example, one observation could be whether any packets sent from the device in a time frame were shorter than a threshold packet length or how many of these short packets were sent. Another observation could be whether any packets sent from the device included ambiguous options in a packet option field or how many of these packets were sent. Another observation could be whether any packets sent from the device violated certain application-layer protocols or how many of these packets were sent.

Some observations may relate to rates at which a device communicates. For example, the total number of network communications (or network communications of a certain type) can be divided by a time window in which the network communications were sent in order to determine an average rate over the time window. In addition, the time window can be divided into sub-windows and a rate can be calculated for each sub-window. The rates of the sub-windows can then be compared. Statistics about the sub-window rates, such as variance, standard deviation, range, mean, median, mode, or the presence of outliers can be recorded and serve as observations.

Other observations may relate to relational issues of the observed network activity. For example, one observation could be the total number of different destinations to which the device sent communications during a time window. Another observation could be whether any of the destinations are Internet Protocol (IP) addresses that are known to be malicious (e.g., that are included in a list of malicious IP addresses). Another observation could be a list of ports that were used for network communication during the time window or how much traffic was associated with each port.

The graph224may be an undirected graph which includes vertices225and edges226. Each vertex in the graph224may represent a device (e.g., one of the devices212a-j) connected to the network200. Each edge in the graph224may connect two vertices and indicate that communication messages were sent between the two devices represented by the two vertices during a time period to which the graph224applies.

Each of the feature functions227may be associated with one of the weights228. Furthermore, each of the feature functions227may use an infection-status label for an nth device, an infection-status label for an n−1thdevice, and some or all of the observations received from the devices212a-jas input parameters. The symbol n can represent an index used to indicate a specific device in the devices212a-j. The n−1thdevice can be a device whose corresponding vertex in the graph225precedes a vertex corresponding to the nth device in an order in which the graph225is traversed. In addition, each of the feature functions227may use the anomaly-suspicion value that was generated by an nth classifier for the nth device as input. Mathematical products of the feature functions227and their associated respective weights228may be summed as part of an expression that represents a conditional probability of infection-status labels for the devices212a-jgiven the observations received from the devices212a-j. In Markovian terms, an infection-status label for a given device is a hidden variable indicating whether the device is infected with malware infection. The weights228may be determined or refined using a training process.

In one example, a conditional probability of infection-status labels given observations can be formally represented as p(z1:N|x1:N). The upper-case letter N can represent the number of vertices225in the graph224and is therefore a non-negative integer. The lower-case letter z with a subscript can represent an infection-status label for a device corresponding to a vertex indicated by the subscript. Hence, the term z1:Nrepresents the set of infection-status labels for the N devices that are represented by the N vertices. Similarly, the lower-case letter x with a subscript can represent a vector of observations for the device corresponding to the vertex indicated by the subscript. The term x1:Nrepresents the set of observation vectors for the N devices that are represented by the N vertices.

In addition, the upper-case letter F can represent the number of feature functions227in the CRF model222and is therefore be a non-negative integer. The lower-case letter f with a subscript can represent a feature function indexed by the subscript. The lower-case letter w with a subscript can represent a weight that is associated with a feature function indexed by the subscript. Given these definitions, the conditional probability of infection-status labels z1:Ngiven observation vectors x1:Ncan be defined by equation 1 below:

where the lower-case letter n is an integer index ranging from 1 to N and is an index corresponding to a vertex in the graph224, the lower-case letter i is an integer index ranging from 1 to F and is an index corresponding to a feature function of the feature functions227, the capital letter Z is a normalization factor used to ensure that the conditional probability ranges from 0 to 1, is an nthinfection-status label associated with an nthvertex in the graph224, zn-1is an (n−1)thinfection-status label associated with an (n−1)thvertex that is connected to the nthvertex by an edge (of the edges226) in the graph224, and exp is the exponential function (i.e., the exponential function is evaluated by raising Euler's number e, also known as the base of the natural logarithm or the sum of the infinite series

∑k=0∞⁢1/k!,
to the power of the braced expression).

In order to train the weights228, training instances for the CRF Model222can be used in conjunction with the conditional probability defined by equation 1. A training instance for the CRF model can comprise a set of N known (or assumed) infection-status labels and a set of N known (or assumed) respective observation vectors for the N devices represented by the N vertices of the graph224. Each training instance for the CRF model222can be associated with a specific time or time window. The capital letter T can be a positive integer representing the total number of training instances available for the CRF Model222. An objective function for training the weights can be defined as:

where the lower-case letter t is a positive integer index ranging from 1 to T, z(f)1:Nis the set of infection-status labels included in the tthtraining instance, x(f)1:Nis the set of observation vectors included in the tthtraining instance, and log is the logarithmic function (e.g., with base 10, base 2, base e, or some other base). A maximum (local and/or global) for this objective function can be identified using a gradient-based optimization technique such as the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS or LM-BFGS) method. This maximum represents a point at which the weights228have values such that the conditional likelihood of the training data (i.e., the training instances, collectively) is substantially maximized (globally and/or locally).

Training instances are generally used to train or determine the weights228. As a practical matter, the set of infection-status labels for a given set of observation vectors for the devices212a-jis often not known. However, once the weights228have been determined through training (or through some other means), the conditional probability defined by equation 1 can also be used to help determine a set of infection-status values for a set of observation vectors. As used herein, the term infection-status value refers to an infection-status label that is not actually known (or assumed to be known), but rather is estimated using the CRF Model222as described herein. An asterisk can be used to denote infection-status values such that the term z* with a subscript represents an infection-status value estimated for a device corresponding to a vertex indicated by the subscript. Hence, the term z*1:Nrepresents the set of infection-status values estimated for the N devices that are represented by the N vertices. The infection status values can be determined or estimated using equation 2:
z*1:N=argmaxz(1:N)p(z1:N|x1:N)  (2),

where argmaxz(1:N)denotes the arguments-of-the-maxima function and x1:Nrepresents the set of observation vectors for the N devices that are represented by the N vertices for a given time window. In other words, z*1:Nis the set of infection-status values that substantially maximizes (locally or globally) the conditional probability p(z1:N|x1:N).

In some examples (e.g., examples where the feature functions227use anomaly-suspicion values provided by the classifiers214a-jas input), an infection-status value for a device can be used to train the classifier associated with the device. For example, suppose the classifier214aproduces an anomaly-suspicion value of 0.4 for the device212abased on the observation vector observed at the device212afor a given time window. Also suppose that the CRF Model222, based collectively on the observation vectors for devices212a-j, determines that the infection-status value for the device212afor the same time window is 0.9. Also suppose that the anomaly detector204determines that the difference between the anomaly-suspicion value and the infection-status value exceeds a predefined threshold value (e.g., 0.3). A new training instance for the classifier214aincluding the observation vector for the device212aand the infection-status value can be made. The infection-status value can serve as the target value for the anomaly-suspicion value. The new training instance can be used to train or tune the classifier214ato predict the infection-status value upon receiving an instance that includes the observation vector.

In some examples, the anomaly detector204may be configured to calculate a sum of the infection-status values

(e.g.,according⁢⁢to⁢⁢the⁢⁢expression⁢⁢∑n=1N⁢zn*).⁢
If the sum of the infection-status values exceeds a predefined threshold, an alert flag can be triggered at the gateway202. Alternatively, a ratio of infected devices can be determined based on the infection-status values. For example, devices with infection-status values that exceed a predefined threshold can be considered infected. The number of infected devices connected to the network200can be divided by the total number of devices connected to the network to determine the ratio of infected devices. If the ratio of infected devices exceeds a threshold ratio, an alert flag can be triggered at the gateway202.

FIG. 3is a block diagram illustrating an example of an anomaly detector304generating a graph320based on network communications, according to one embodiment. For this example, assume that the device306acommunicates with the device306gduring the time period. Also assume device306gcommunicates with device306k, device306ecommunicates with device306k, device306ecommunicates with device306j, device306jcommunicates with device306o, and device306pcommunicates with device306o. Also assume that the devices308b-d,306f,306h-i, and306l-ndo not send or receive any network communications during the time period. The anomaly detector302generates vertex308ato represent device306a. Furthermore, the anomaly detector302generates vertex308gto represent device306g, vertex308kto represent device306k, vertex308eto represent device306e, vertex308jto represent device306j, vertex308oto represent device306o, and vertex308pto represent device306p.

In one embodiment, the anomaly detector304creates edge310to reflect that device306acommunicated with device306g. Further, the anomaly detector304creates edge311to reflect that device306gcommunicated with device306k, edge312to reflect that device306kcommunicated with device306e, edge313to reflect that device306ecommunicated with device306j, edge314to reflect that device306jcommunicated with device306o, and edge315to reflect that device306ocommunicated with device306p. Network communications may be sent via the network300. The anomaly detector receives observation vectors from each device306a,306g,306k,306e,306j,306o, and306p.

The anomaly detector304then uses the graph320to determine an order (i.e., permutation) for the vertices308a-pfor a conditional probability function of infection-status labels given the observation vectors. In one example, since the first network communication in the time period was exchanged between device306aand device306g, and since vertex308ais only associated with a single edge (edge310), vertex308acan be designated as the first in the order. Vertex308gcan be designated as second,308kas third,308eas fourth,308jas fifth,308oas sixth, and308pas seventh. Based on this order, the conditional probability function can be used to determine infection-status values for the devices306a,306g,306k,306e,306j,306o, and306pfor the time period to which the graph320applies. Since the anomaly detector304determines the order of the vertices for the conditional probability function based on the graph320, the graph320ultimately helps determine which set of infection-status values the anomaly detector304will predict for the devices306a,306g,306k,306e,306j,306o, and306p.

In other examples, the graph may not be a linear chain. For example, when a feature function is being evaluated for an nth vertex of a graph that does not form a linear chain, the feature function can operate on the entire neighborhood of the nth vertex rather than on a single vertex. The neighborhood of the nth vertex may be defined as a clique (e.g., a maximal clique) wherein each vertex of the clique is connected by an edge to every other vertex in the clique. If a graph has disjoint components, the disjoint components can be evaluated separately as though they were separate graphs.

FIG. 4Ais a block diagram illustrating a graph segment400athat may be used to provide inputs to an example feature function, according to one embodiment. In conjunction with a CRF model, the graph segment400amay be traversed in order from the vertex402ato the vertex404ato the vertex406a. Each of the vertices402a,404a, and406amay represent a respective device in a network. The graph segment400amay be part of a graph for a time window.

An example ithfeature function ƒimay be defined piecewise as:

where i is an integer index of the feature function ƒi, znis the infection-status label associated with an nthvertex, zn-1is the infection-status label associated with an (n−1)thvertex that precedes the nthvertex in an order and is connected to the nthvertex by an edge, N represents the number of vertices in the graph, x1:Nrepresents the set of observation vectors from devices that are represented by vertices in the graph, a(xn) is an anomaly-suspicion value calculated by a classifier that is associated with an nthdevice represented by the nthvertex using the observation vector xn, and the observation vector xnincludes observations of the nthdevice. In this example, assume that an infection-status label of 1 indicates a high likelihood of infection, an infection-status label closer to zero indicates a low likelihood of infection, and an infection-status label of 0.5 indicates a medium likelihood of infection (e.g., that the labeled device has engaged in some suspicious network activity).

To evaluate this example feature function ƒifor the graph segment400a, suppose that the vertex406ais the nthvertex and that vertex404ais the (n−1)thvertex. Also suppose that the infection-status label zn-1(which is z2in this example) is 0.5 and the infection-status label zn(which is z3in this example) is 1. Furthermore, suppose that the anomaly-suspicion value a(xn) is 0.7. Since zn-1is greater than or equal to 0.5, znequals 1, and a(xn) is greater than 0.5, the feature function ƒievaluates to an output of 1 in this example.

Considering this example in the context of equations 1 and 2, this example feature function has the effect of making it more probable that an infection-status value of the nthvertex will be 1 if the infection-status value of the (n−1)thvertex is at least 0.5. This is because, according to equation 1, the conditional probability of a set of infection-status labels increases when the weighted sum over the F feature functions increases. If the example feature function evaluates to 1, the weighted sum over the F feature functions will be greater than it would be if the example feature function evaluated to zero (unless the example feature function has a weight of zero).

FIG. 4Bis a block diagram illustrating a graph segment400bthat may be used to provide inputs to an example feature function, according to one embodiment. In conjunction with a CRF model, the graph segment400bmay be traversed in order from the vertex402bto the vertex404bto the vertex406b. Each of the vertices402b,404b, and406bmay represent a respective device in a network. The graph segment400bmay be part of a graph for a time window.

A second example ithfeature function ƒimay be defined piecewise as:

where i is an integer index of the feature function ƒi, is the infection-status label for the device, znis the infection-status label associated with an nthvertex, zn-1is the infection-status label associated with an (n−1)thvertex that precedes the nthvertex in an order and is connected to the nthvertex by an edge, N represents the number of vertices in the graph, x1:Nrepresents the set of observation vectors from devices that are represented by vertices in the graph, a(xn) is an anomaly-suspicion value calculated by a classifier that is associated with an nthdevice represented by the nthvertex using the observation vector xn, and the observation vector xnincludes observations of the nthdevice. Again, in this example, assume that an infection-status label of 1 indicates a high likelihood of infection, an infection-status label closer to zero indicates a low likelihood of infection, and an infection-status label of 0.5 indicates a medium likelihood of infection (e.g., that the labeled device has engaged in some suspicious network activity).

To evaluate this second example feature function ƒifor the graph segment400b, suppose that the vertex406bis the nthvertex and that vertex404bis the (n−1)thvertex. Also suppose that the infection-status label zn-1(which is z2in this example) is 0.5 and the infection-status label zn(which is z3in this example) is 0. Furthermore, suppose that the anomaly-suspicion value a(xn) is 0.3. Since zn-1is less than or equal to 0.5, znequals 0, and a(xn) is less than 0.4, the second feature function ƒievaluates to an output of 1 in this example.

Considering this example in the context of equations 1 and 2, this second example feature function has the effect of making it more probable that an infection-status value of the nthvertex will be 0 if the infection-status value of the (n−1)thvertex is less than or equal to 0.5 and the anomaly-suspicion value of the nthvertex is less than 0.4. Again, this is because the conditional probability of a set of infection-status labels (as shown in equation 1) increases when the weighted sum over the F feature functions increases. If the second example feature function evaluates to 1, the weighted sum over the F feature functions will be greater than it would be if the second example feature function evaluated to zero (unless the second example feature function has a weight of zero).

WhileFIGS. 4A and 4Bare used to show two possible examples of feature functions, many other types of feature functions are possible. Feature functions may be provided by domain experts or derived using machine-learning techniques applied to training data, for example. As explained herein, weights for feature functions can be learned. Thus, feature functions whose weights are large after training may be considered more valuable that feature functions whose weights are close to zero after training.

Since technologies of the present closure may be very useful for networks that include IoT devices,FIGS. 5 and 6are included to provide some specific examples of how and why IoT devices may communicate with each other and with other devices over a network. However, the examples ofFIGS. 5 and 6are not intended to limit the scope of the claimed subject matter.

FIG. 5illustrates an example of a multi-hop wireless sensor network (WSN)500that is connected to the Internet501via a gateway560, according to one embodiment. The multi-hop WSN500can include wireless sensor nodes562-590. Each of the wireless sensor nodes562-590may be equipped with a radio transceiver, an antenna, a microcontroller (MCU) with a processor and memory, a sensor, and an energy source (e.g., a battery). The wireless sensor nodes562-590may be distributed over a relatively large geographical area and may periodically take sensor readings (e.g., of temperature, pressure, humidity, or some other quantity).

In order to reduce energy consumption, each wireless sensor node562-590may be configured to send wireless transmissions with relatively low power. As a result, a wireless transmission from one of the wireless sensor nodes562-590may travel a relatively short distance. The wireless sensor nodes562-590can therefore be configured to relay a network communications from one node to another until the network communication reaches the gateway560.

For example, the wireless sensor node590may take a first sensor reading. The wireless sensor node590may then wirelessly send the first sensor reading in a first network communication to the wireless sensor node586. The wireless sensor node586may then wirelessly send the first sensor reading in a second network communication to the wireless sensor node588. Optionally, the wireless sensor node586may also include a second sensor reading (e.g., that was taken at the wireless sensor node586) in the second network communication. This pattern may continue as a network communication with the first sensor reading may be sent in turn from wireless sensor node588to wireless sensor node584, from wireless sensor node584to wireless sensor node574, from wireless sensor node574to wireless sensor node572, from wireless sensor node572to wireless sensor node566, from wireless sensor node566to wireless sensor node564, from wireless sensor node564to wireless sensor node578, and finally from wireless sensor node578to the gateway560. The network communication that arrives at the gateway560includes the first sensor reading that was made at the wireless sensor node590and may also include additional sensor readings from one or more of the other wireless nodes in the path.

FIG. 6illustrates one example of a local area network (LAN)600that is connected to the Internet601via a router604and a gateway603, according to one embodiment. (The router604and the gateway603may, in some examples, be housed or integrated in a single unit.) Multiple devices may be connected to the LAN600through wired (e.g., Ethernet) or wireless (e.g., WiFi or BlueTooth) connections to the router604. For example, a water meter606, an outdoor lawn-sprinkler system608, and an indoor emergency-sprinkler system610may be connected to the LAN600. In addition, a smoke detector612, a security camera614, a carbon monoxide detector616, and a motion detector system618may also be connected to the LAN600. An office telephone620, a television622, a desktop computer624, an audio system626(e.g., a stereo system or an intercom system), and a printer628may also be connected to the LAN. A coffee maker630, a microwave632, a wearable device634(e.g., a wearable baby monitor or a fitness tracker), a dishwasher636, a refrigerator638, and an oven/stove640may also be connected to the LAN600. A gas meter642, a water heater644, a lighting system646, a thermostat648, an electric meter650, a garage-door opener652, and a washer654may also be connected to the LAN600. A mobile device602may be able to communicate with devices that are connected to the LAN600via a cellular connection to the Internet601. Alternatively, if the mobile device602is connected to the LAN600, the mobile device may communicate directly through the LAN600(e.g., by a WiFi connection to the router604). Servers656may be connected to the Internet601and may include servers that belong to device manufacturers, utility companies, law enforcement agencies, emergency service providers, entertainment service providers, or other entities.

Devices connected to the LAN600may send a variety of digital communications to each other or to other destinations that are accessible via the Internet601for a variety of reasons. The following examples of such communications are provided for illustrative purposes, but are not intended to be limiting.

In one example, the water meter606may send a communication to a utility-company server of the servers656indicating an amount of water used by a household during a predefined time period (e.g., a month) to enable the utility company to generate a bill for the water used. The water meter606may also be configured to detect when the amount of water used by the household during a certain time period exceeds a predefined threshold. When the threshold has been exceeded, the water meter606may send a communication (e.g., an email) to the mobile device602to advise a user that the threshold has been exceeded. In addition, the water meter606may be configured to send a communication to the outdoor lawn-sprinkler system608indicating that the household's lawn is to be watered at slower rate (or not at all). The water meter606may also send a communication to the dishwasher636indicating that the dishwasher636is to use a more water-efficient dish-cleaning mode until further notice. The water meter606may also send a communication to the refrigerator638indicating that ice making is to be reduced or ceased until further notice. In addition, the water meter606may send a communication to the washer654indicating that the washer654is to forgo performing extra rinse cycles until further notice.

In another example, the electric meter650may send a communication to a utility-company server of the servers656indicating an amount of power used by a household during a predefined time period (e.g., a month) to enable the utility company to generate a bill for the power used. The electric meter650may also be configured to detect when the amount of power used by the household during a certain time period exceeds a predefined threshold. When the threshold is exceeded, the electric meter650may send a communication to the thermostat648indicating that the household temperature should be set several degrees higher in order to reduce electricity use by an air conditioner or swamp cooler. The electric meter650may also send a communication to the lighting system646indicating that one or more lights are to be turned off in the household until further notice (e.g., from the motion detector system618). The electric meter650may also send a communication to the refrigerator638indicating that an internal temperature of the refrigerator638should be set several degrees higher in order to reduce power consumption. The electric meter650may also send communications to other devices, such as the washer654, the desktop computer624, the microwave632, and the dishwasher636, indicating that energy-efficient modes of operation for each respective device are to be used until further notice or for a specific period of time.

In another example, the gas meter642may send a communication to a utility-company server of the servers656indicating an amount of gas used during a predefined time period (e.g., a month) to enable the utility company to generate a bill for the gas used. The gas meter642may also detect that the amount of gas used by the household during a certain period of time exceeds a predefined threshold. As a response, the gas meter642may send a communication to the water heater644indicating that water in the water heater644should be heated to a lower temperature in order to reduce gas consumption. In addition, the gas meter642may send a communication the thermostat648indicating that the household temperature should be set several degrees lower in order to reduce gas consumption by a gas furnace or heater.

In another example, the smoke detector612may detect that there is smoke in a household. As a response, the smoke detector612may send a communication to the indoor emergency-sprinkler system610indicating that the emergency-sprinkler system610is to begin spraying water immediately or after a certain period of time. If the smoke detector612detects that there is no longer smoke in the household before that period of time elapses, the smoke detector612may send a follow-up communication to the emergency-sprinkler system610indicating that the scheduled water spraying should be aborted. The smoke detector612may also send a communication to the gas meter642, the oven/stove640, and/or the water heater644indicating that gas use should be cut off so that gas will not fuel a fire or cause an explosion. The smoke detector may also send a communication to the mobile device602indicating that smoke has been detected. The smoke detector612may also query the motion detector system618to determine if any motion has recently been detected in the household. If the motion detector system618responds affirmatively, the smoke detector612may signal the audio system626to broadcast an alarm and/or signal the office phone620to dial an emergency telephone number.

In another example, the carbon monoxide detector616may detect that the level of carbon monoxide in a home has exceeded a predefined level. In response, the carbon monoxide detector616may send a communication to the garage-door opener652to open a garage door in order to ventilate a garage of the household. In addition, the carbon monoxide detector616may send a communication to the water heater644to stop a pilot flame that may be producing carbon monoxide. The carbon monoxide detector616may also send a communication to the mobile device602indicating that the level of carbon monoxide in the household is dangerously high. The carbon monoxide detector616may also send a communication to the gas meter642, the thermostat648, and/or the oven/stove640indicating that gas use should be cut off so that gas will not be burned in the household (since burning may be producing the carbon monoxide). The carbon monoxide detector616may also query the wearable device634to inquire whether any metrics measured by the wearable device (e.g., a wearer's heart rate or blood oxygenation levels) suggest that the wearer is imminently suffering from carbon monoxide poisoning. If the wearable device634responds affirmatively, the carbon monoxide detector616may signal the audio system626to broadcast an alarm and/or signal the office phone620to dial an emergency telephone number.

In another example, the television622may receive a video stream from a video-content server of the servers656. The television622may also send a communication to the audio system626requesting that the audio system626play an audio signal associated with the video stream. The television622may also send a communication to the audio system626requesting that the audio signal be played at a specified volume or with specific levels of bass and/or treble enhancement. In addition, the television622may send a communication to a data-mining server of the servers656to report use statistics associated with the television622or with services accessed through the television622(e.g., videos watched, times of day when the television622is used most frequently, etc.).

In another example, the motion detector system618may send a communication to the security camera614indicating that motion has been detected. The security camera614may begin recording a video feed and may send the video feed to the desktop computer624, the mobile device602, the television622, or a security-service server of the servers656. In addition, the motion detector system618or the security camera614may send a communication to the lighting system646indicating that one or more household lights should be turned on.

In another example, the mobile device602may send a communication to the coffee maker630indicating that the coffee maker630should commence brewing a cup of coffee. In response, the coffee maker can send a communication to the mobile device602indicating when a cup of coffee is ready for consumption. Similarly, the mobile device602may send a communication to the oven/stove640indicating that the oven/stove640should begin preheating. The oven/stove640can respond by sending one or more communications indicating a current temperature of the oven/stove640to the mobile device602.

In another example, the wearable device634may measure metrics associated with a wearer's health and/or movement and send periodic communications to the mobile device602, a server of the servers656, and/or the desktop computer624. The wearable device634may also send an alarm communication to the mobile device602, to the office telephone620, or to a server of the servers656if measured metrics indicate a latent or imminent threat to the wearer's health.

In another example, the desktop computer624may send performance metrics, error logs, and other information to a manufacturer server of the servers656and may also receive software updates from the manufacturer server. Similarly, other devices that are connected to the LAN600, such as the printer628, the office telephone620, or the wearable device634may send use statistics, error logs, and other communications to the servers656and may also receive software updates from the servers656.

The preceding examples provide some examples of Internet-of-Things (IoT) devices and communications. However, systems and methods of the present disclosure are also pertinent to many other types of devices and communications. Devices such as door sensors for security systems, digital video disk (DVD) players, gaming consoles, electronic safes, global positioning systems (GPSs), location trackers, activity trackers, laptop computers, tablet computers, automated door locks, air conditioners, furnaces, heaters, dryers, wireless sensors in wireless sensor networks, large or small appliances, personal alert devices (e.g., used by elderly persons who have fallen in their homes), pacemakers, bar-code readers, implanted devices, ankle bracelets (e.g., for individuals under house arrest), prosthetic devices, telemeters, traffic lights, user equipments (UEs), or any apparatuses including digital circuitry that is able to achieve network connectivity may be considered IoT devices or networking devices for the purposes of this disclosure. Furthermore, emails, simple message service (SMS) messages, transmission control protocol (TCP) messages, or other digital messages sent over a network are all considered to be “network communications” for the purposes of this disclosure.

FIG. 7is a flow diagram illustrating a process700for an anomaly detector, according to one embodiment. The process700that can be implemented as a method or can be executed as instructions on a machine (e.g., by one or more processors), where the instructions are included on at least one computer-readable storage medium (e.g., a transitory or non-transitory computer-readable storage medium).

At block702, the anomaly detector monitors, at a gateway device during a time window, network communications between devices that are connected a network associated with the gateway device.

At block704, the anomaly detector creates, at the gateway device, a graph wherein vertices represent devices connected to the network and an edge between two vertices signifies that a network communication occurred between two devices represented by the two vertices during the time window.

In addition, the anomaly detector can use a conditional random field (CRF) model to create a conditional probability function of infection-status values. The anomaly detector may define the conditional probability function using a plurality of feature functions that are associated with a plurality of weights.

Furthermore, the anomaly detector can receive training observation vectors and corresponding infection-status labels for the training observation vectors. A training observation vector and corresponding infection-status label can make up a training instance.

At block706, the anomaly detector receives, from a plurality of devices that are represented by a plurality of vertices in the graph, a plurality of observation vectors that were observed by the plurality of devices during the time window. The anomaly detector can determine the plurality of weights by training the CRF model using the observation vectors and the infection-status labels.

In addition, the anomaly detector may also determine a plurality of anomaly-suspicion values for the plurality of devices using a plurality of classifiers. Each anomaly-suspicion value can be associated with a respective device and can be determined by a respective classifier that uses an observation vector observed at the respective device as input.

At block708, the anomaly detector determines, at the gateway device and using the graph, a plurality of infection-status values for the plurality of devices based on the plurality of observation vectors.

In examples where a conditional probability function is defined, the anomaly detector can determine the plurality of infection-status values by identifying one or more maxima of the conditional probability function given the plurality of observation vectors. In addition, in examples where the anomaly detector determines anomaly-suspicion values, one or more feature functions of the plurality of feature functions can use an anomaly-suspicion value associated with an nthdevice as an input to determine an output value associated with the nthdevice, wherein n is an integer index.

Furthermore, in examples where the anomaly detector determines anomaly-suspicion values, the anomaly detector can also determine that a difference between an infection-status value for a device and an anomaly-suspicion value for the device exceeds a predefined threshold and use the infection-status value to update a classifier associated with the device.

In some examples, that anomaly detector may also calculate a sum of the infection-status values for the plurality of devices. If the sum of the infection-status values exceeds a predefined threshold value, the anomaly detector can set or trigger an alert flag at the gateway device based on the determination.

FIG. 8illustrates an example anomaly detection system800that determines infection-status values for devices connected to a network, according to an embodiment. As shown, the anomaly detection system800includes, without limitation, a central processing unit (CPU)802, one or more I/O device interfaces804which may allow for the connection of various I/O devices814(e.g., keyboards, displays, mouse devices, pen input, etc.) to the image processing system800, network interface806, a memory808, storage810, and an interconnect812.

CPU802may retrieve and execute programming instructions stored in the memory808. Similarly, the CPU802may retrieve and store application data residing in the memory808. The interconnect812transmits programming instructions and application data, among the CPU802, I/O device interface804, network interface806, memory808, and storage810. CPU802can represent a single CPU, multiple CPUs, a single CPU having multiple processing cores, and the like. Additionally, the memory806represents random access memory. Furthermore, the storage810may be a disk drive. Although shown as a single unit, the storage810may be a combination of fixed and/or removable storage devices, such as fixed disc drives, removable memory cards or optical storage, network attached storage (NAS), or a storage area-network (SAN).

As shown, memory808includes an anomaly detector818that includes a CRF model820and classifiers824. As shown, storage810includes training data822that includes observation vectors826and infection-status labels828. Both the CRF model820and the classifiers824can be trained using the training data.