Method and apparatus for generating a combined isolation forest model for detecting anomalies in data

A method for generating a combined Isolation Forest model for detecting anomalies in data is provided. The method includes receiving a first Isolation Forest model for detecting anomalies in data from a first electronic device. The first Isolation Forest model is trained at the first electronic device. Further, the method includes receiving a second Isolation Forest model for detecting anomalies in data from a second electronic device. The second Isolation Forest model is trained at the second electronic device. The method additionally includes combining the first Isolation Forest model and the second Isolation Forest model to obtain the combined Isolation Forest model.

CROSS-REFERENCE TO RELATED APPLICATION

The present application claims priority to European Patent Application 19191523.0 filed by the European Patent Office on Aug. 13, 2019, the entire contents of which being incorporated herein by reference.

FIELD

The present disclosure relates to detection of anomalous activities at electronic devices. In particular, examples relate to a method and an apparatus for generating a combined Isolation Forest model for detecting anomalies in data. Further examples relate an electronic device and a system comprising multiple electronic devices.

BACKGROUND

Anomaly detection is the challenge of finding anomalies in data of a device or system. Anomalies are data patterns that do not conform to a well-defined notion of normal behavior of the device or system. Finding anomalies is important since the anomalies may represent significant events for a huge variety of applications. For example, anomalies may be caused by frauds in financial systems, hacker intrusions in a computer or a computer network, enemy activities in military surveillance systems, etc.

Conventional approaches detect anomalies at either a centralized server or in a centralized network of servers. Therefore, it is necessary to transfer data from individual monitored devices to the detection servers. The conventional approaches gather data from several monitored devices into a cluster of servers, perform some data pre-processing and create features to be used by machine learning models for detection of anomalies. However, these approaches do no scale well when the number of monitored devices is large and increasing continuously. Further, the cost of infrastructure (computing and storage servers, redundant servers, computer networks) is high. Additionally, data privacy concerns as well as security concerns exist.

Other conventional approaches perform model training on the server side and classification of events on the device side. However, also these conventional approaches require transfer of data from the monitored device to the server for model training. Therefore, data privacy concerns as well as security concerns exist also for these conventional approaches.

Hence, there is a desire for improved generation of machine learning models for detecting anomalies in data.

SUMMARY

This desire is met by apparatuses and methods in accordance with the independent claims. Advantageous embodiments are addressed by the dependent claims.

According to a first aspect, the present disclosure provides a method for generating a combined Isolation Forest model for detecting anomalies in data. The method comprises receiving a first Isolation Forest model for detecting anomalies in data from a first electronic device. The first Isolation Forest model is trained at the first electronic device. Further, the method comprises receiving a second Isolation Forest model for detecting anomalies in data from a second electronic device. The second Isolation Forest model is trained at the second electronic device. The method additionally comprises combining the first Isolation Forest model and the second Isolation Forest model to obtain the combined Isolation Forest model.

According to a second aspect, the present disclosure provides a method for an electronic device. The method comprises training a first Isolation Forest model for detecting anomalies in data. Further, the method comprises transmitting the trained first Isolation Forest model to another electronic device. The method comprises receiving from the other electronic device a combined Isolation Forest model for detecting anomalies in data. The combined Isolation Forest model is a combination of the first Isolation Forest model and at least a second Isolation Forest model for detecting anomalies in data. Additionally, the method comprises analyzing data at the electronic device for anomalies using the combined Isolation Forest model.

According to a third aspect, the present disclosure provides an apparatus for generating a combined Isolation Forest model for detecting anomalies in data. The apparatus comprises an input interface configured to receive a first Isolation Forest model for detecting anomalies in data from a first electronic device. The first Isolation Forest model is trained at the first electronic device. Further, the input interface is configured to receive a second Isolation Forest model for detecting anomalies in data from a second electronic device. The second Isolation Forest model is trained at the second electronic device. The apparatus further comprises a processing circuit configured to combine the first Isolation Forest model and the second Isolation Forest model to obtain the combined Isolation Forest model.

According to a fourth aspect, the present disclosure provides an electronic device. The electronic device comprises a processing circuit configured to train a first Isolation Forest model for detecting anomalies in data. Further, the electronic device comprises an output interface configured to transmit the trained first Isolation Forest model to another electronic device. The electronic device additionally comprises an input interface configured to receive from the other electronic device a combined Isolation Forest model for detecting anomalies in data. The combined Isolation Forest model is a combination of the first Isolation Forest model and at least a second Isolation Forest model for detecting anomalies in data. The processing circuit is further configured to analyze data at the electronic device for anomalies using the combined Isolation Forest model.

According to a fifth aspect, the present disclosure provides a system. The system comprises a first electronic device comprising a first processing circuit configured to train a first Isolation Forest model for detecting anomalies in data. Further, the system comprises a second electronic device comprising a second processing circuit configured to train a second Isolation Forest model for detecting anomalies in data. The system additionally comprises a third electronic device comprising an input interface configured to receive the first Isolation Forest model from the first electronic device and the second Isolation Forest model from the second electronic device. The third electronic device further comprises a third processing circuit configured to combine the first Isolation Forest model and the second Isolation Forest model to obtain a combined Isolation Forest model. Additionally, the third electronic device comprises an output interface configured to transmit the combined Isolation Forest model to the first electronic device and the second electronic device. At least one of the first processing circuit and the second processing circuit is configured to analyze data at the respective electronic device for anomalies using the second Isolation Forest model.

DETAILED DESCRIPTION

It will be understood that when an element is referred to as being “connected” or “coupled” to another element, the elements may be directly connected or coupled via one or more intervening elements. If two elements A and B are combined using an “or”, this is to be understood to disclose all possible combinations, i.e. only A, only B as well as A and B, if not explicitly or implicitly defined otherwise. An alternative wording for the same combinations is “at least one of A and B” or “A and/or B”. The same applies, mutatis mutandis, for combinations of more than two Elements.

Isolation Forest is an unsupervised machine learning model proposed by F. Liu et al. in their paper “Isolation Forest”, 2008 Eighth IEEE International Conference on Data Mining, ISBN: 978-0-7695-3502-9, which is hereby incorporated by reference. The Isolation Forest model distinguishes normal from abnormal instances based on two assumptions: 1) Anomalies are the minority and consist of fewer instances in comparison to normal instances; and 2) Anomalies have attribute values that are very different from those of normal instances. If the two above assumptions are met, anomaly instances have short path lengths. The path length is the number of decisions or branches traversed from a root node to an end (external) node of an isolation (decision) tree. In other words, anomalies are located closer to the root of the tree than normal instances. Accordingly, when a forest of trees produces short path lengths for some particular data points, these data points are highly likely to be or to relate to anomalies.

FIG.1illustrates a flowchart of an example of a method100for generating a combined (unified) Isolation Forest model for detecting anomalies in data.

Method100comprises receiving102, from a first electronic device, a first Isolation Forest model for detecting anomalies in data. The first Isolation Forest model is trained at the first electronic device using only local data of the first electronic device (e.g. data available only to the first electronic device).

Further, method100comprises receiving102, from a second electronic device, a second Isolation Forest model for detecting anomalies in data. The second Isolation Forest model is trained at the second electronic device using only local data of the second electronic device (e.g. data available only to the second electronic device).

The first electronic device and the second electronic device may be any physical entity comprising electronic circuitry capable of exchanging data with one or more communication networks such as a Local Area Network (LAN), a Wireless LAN (WLAN), a Metropolitan Area Network (MAN), a Wide Area Network (WAN), a Global Area Network (GAN) or the Internet. The electronic device may comprise further circuitry—conventional and/or custom. For example, the first electronic device and the second electronic device may be an Internet-of-Things (IoT) device. An IoT device is an electronic device that is capable of connecting to the Internet, and to receive, transmit and process data.

Further, method100comprises combining106the first Isolation Forest model and the second Isolation Forest model to obtain the combined Isolation Forest model. In other words, the first Isolation Forest model and the second Isolation Forest model are merged/fused to obtain the combined Isolation Forest model.

Each of the first Isolation Forest model, the second Isolation Forest model and the combined Isolation Forest model may be represented by a corresponding algorithm (data structure).

According to method100, the model training is split into two phases. In a first phase, a respective Isolation Forest model is trained at each electronic device using data available only to that device. The training of the respective Isolation Forest model at each electronic device may be done as described in the paper of Liu et al. The individual Isolation Forest model are therefore capable of detecting anomalies for patterns learnt from the respective data set available at the electronic device. However, the individual Isolation Forest models are not able to generalize to additional patterns captured at other devices because they only learn patterns based on their respective local data set. This is exemplarily illustrated inFIG.2.

At a first electronic device210, a first set of data points211is available. Training the Isolation Forest model at the first electronic device210using the first set of data points211results in the first Isolation Forest model213comprising a first plurality of trained decision (isolation) trees.

At a second electronic device220, a different second set of data points221is available. Training the Isolation Forest model at the second electronic device220using the second set of data points221results in the second Isolation Forest model223comprising a different second plurality of trained decision (isolation) trees.

Since the Isolation Forest models are trained using different sets of data points at the electronic devices210and220, the resulting trained Isolation Forest models213and223are capable of detecting different types of anomalies. For example, the first Isolation Forest model213is capable of detecting a first type of anomalies212, whereas the second Isolation Forest models223is capable of detecting a different second type of anomalies222.

Method100extends the first training phase at the electronic devices210and220by a second training phase. The second training phase continues the training phase started at the electronic devices210and220by combining the locally learnt Isolation Forest models213and223into the combined Isolation Forest models231, i.e. a universal or unified Isolation Forest model. Combining the locally learnt Isolation Forest models213and223allows to transfer knowledge between the electronic devices210and220.

In the second training phase, the electronic devices210and220share their trained Isolation Forest models213and223with another (third) electronic device230(e.g. a server, a server network such as a cloud infrastructure, or peers of IoT devices) which creates the combined Isolation Forest model231. As indicated inFIG.2, combined Isolation Forest model231is a combination of the incoming trained Isolation Forest models213and223.

The combined Isolation Forest model231is more generic than the individual Isolation Forest models213and223trained at the electronic devices210and220. Accordingly, the combined Isolation Forest model231is capable of detecting (identifying) more types of anomalies in data than the individual Isolation Forest models213and223. In the example ofFIG.2, the combined Isolation Forest model231is capable of detecting both the first type of anomalies212and the second type of anomalies222. The combined Isolation Forest model231is, hence, able to detect more anomalies than each of the first Isolation Forest model213and the second Isolation Forest model223alone.

Further, it is to be noted that only the forests of decision trees are transferred between the electronic devices210,220and230. There is no need to send any user data out of one of the electronic devices210and220. Accordingly, no user data is transferred during execution of method100such that user data privacy concerns may be omitted. Therefore, less concerns and obligations about user data protection and privacy may be enabled. The Isolation Forest model213,223and231consist of a set of compact rules for classifying instances. Therefore, the amount of transferred information (data) between the electronic devices210,220and230is reduced compared to transferring an entire data set like in conventional approaches. In addition, method100is a scalable and cost-effective solution because part of the processing takes place at the electronic devices210and220(e.g. IoT devices). Further, since Isolation Forest is an unsupervised machine learning model, no human intervention for data labelling is needed.

According to examples, method100additionally comprises transmitting108the combined Isolation Forest model to at least one of the first electronic device and the second electronic device. For example, the combined Isolation Forest model may be shared to all electronic devices in the network such that they can use the combined Isolation Forest model for classification of data instances. In the example ofFIG.2, the first electronic device210may analyze data at the electronic device210for anomalies using the combined Isolation Forest model231.

Although the examples described above in connection withFIGS.1and2combine a first and a second Isolation Forest model individually trained at a first and a second electronic device, it is to be noted that method100may in general combine any number N≥2 of Isolation Forest models individually trained at a respective electronic device in order to obtain a combined Isolation Forest model.

As described above, the first Isolation Forest model represents a first plurality of trained decision trees, and the second Isolation Forest model represents a second plurality of trained decision trees. When performing the step of combining106the first Isolation Forest model and the second Isolation Forest model, one or more tree operations (algorithms) may be applied. Some exemplary tree operations will be described in the following.

In some examples, combining106the first Isolation Forest model and the second Isolation Forest model may comprise merging the first plurality of trained decision trees and the second plurality of trained decision trees. Accordingly, the combined Isolation Forest model comprises the first plurality of trained decision trees and the second plurality of trained decision trees.

Additionally or alternatively, combining106the first Isolation Forest model and the second Isolation Forest model may comprise compacting at least one of the first plurality of trained decision trees and the second plurality of trained decision trees. Accordingly, more compact versions of the first plurality of trained decision trees and/or the second plurality of trained decision trees may be obtained such that the combined Isolation Forest model may be more compact.

Further additionally or further additionally, combining106the first Isolation Forest model and the second Isolation Forest model may comprise pruning at least one of the first plurality of trained decision trees and the second plurality of trained decision trees. By removing sections of the decision trees that provide little power to classify instances, the size of the decision trees may be reduced. Accordingly, the size of the combined Isolation Forest model may be reduced.

In some examples, combining106the first Isolation Forest model and the second Isolation Forest model may comprise searching for redundancies in the first plurality of trained decision trees and the second plurality of trained decision trees. For example, redundant trees or redundant tree branches may be searched. Combining106the first Isolation Forest model and the second Isolation Forest model may then further comprise removing found redundancies from the first plurality of trained decision trees and the second plurality of trained decision trees. Accordingly, redundant parts of the first plurality of trained decision trees and the second plurality of trained decision trees may be omitted in the combined Isolation Forest model.

According to some examples, combining106the first Isolation Forest model and the second Isolation Forest model may comprise calculating path lengths for paths from root nodes to end (external) nodes of the first plurality of trained decision trees and the second plurality of trained decision trees. Further, combining106the first Isolation Forest model and the second Isolation Forest model may comprise calculating statistics indicative of a relevance of a respective path for paths exhibiting a path length shorter than a threshold value (e.g. the threshold value may depend on the anomalies to be detected by the combined Isolation Forest model). The statistics may, e.g., be a median, a standard deviation, a probability distribution, etc., or a combination thereof. Only the paths for which the statistics indicates that the respective path is relevant may be used for the combined Isolation Forest model. In other words, a path length analysis may be performed on the incoming trees of the first and the second Isolation Forest model. As described above, statistics may be computed for the short path lengths as selection criterion for deciding which ones are relevant or not in order to only include the relevant ones into the combined Isolation Forest model. The above processing may allow filtering out nodes far away from the root node of a tree. As described above, anomalies have short path lengths. Therefore, omitting long paths in the combined Isolation Forest model may allow obtaining a compact Isolation Forest model.

In order to highlight the processing in the electronic devices training the individual Isolation Forest models as described above,FIG.3illustrates a flow chart of a method300for an electronic device (e.g. an IoT device) that focusses on the method steps performed by the respective electronic device. Method300is performed by each of the electronic devices.

Method300comprises training302a first Isolation Forest model for detecting anomalies in data (e.g. as described in the paper of Liu et al.). The first Isolation Forest model is trained at the electronic device using only local data of the electronic device (e.g. data available only to the first electronic device).

Further, method300comprises transmitting304the trained first Isolation Forest model to another (an external) electronic device such as a server or a server network (e.g. a cloud infrastructure).

Method300additionally comprises receiving306from the other electronic device a combined Isolation Forest model for detecting anomalies in data. As described above, the combined Isolation Forest model is a combination of the first Isolation Forest model and at least a second Isolation Forest model for detecting anomalies in data.

In addition, method300comprises analyzing308data at the electronic device for anomalies using the combined Isolation Forest model. For example, the data at the electronic device are classified using the combined Isolation Forest model in order to detect anomalies in the data. Since the combined Isolation Forest model is more generic than the first Isolation Forest model trained at the electronic device, the electronic device is capable of detecting more types of anomalies in data. Further, the electronic device is not required to send user data to the other electronic device for obtaining the more generic combined Isolation Forest model.

An example of an electronic system400for applying the proposed technique is illustrated inFIG.4. The system400comprises a first electronic device410, a second electronic device420and a third electronic device430. For example, the first electronic device410and the second electronic device420may be IoT devices. The third electronic device430may, e.g., be a server or a server network. The first electronic device410, the second electronic device420and the third electronic device430are communicatively coupled via a communication network such as e.g. a LAN, a WLAN, a MAN, a GAN or the Internet.

The first electronic device410comprises a first processing circuit413configured to train a first Isolation Forest model for detecting anomalies in data based on local data of the first electronic device410as described above. Similarly, the second electronic device420comprises a second processing circuit423configured to train a second Isolation Forest model for detecting anomalies in data based on local data of the second electronic device420.

The first electronic device410comprises an output interface411configured to transmit the trained first Isolation Forest model to the third electronic device430. The second electronic device420comprises an output interface421configured to transmit the trained second Isolation Forest model to the third electronic device430. Accordingly, the third electronic device430comprises an input interface432configured to receive the first Isolation Forest model from the first electronic device410and the second Isolation Forest model from the second electronic device420.

The third electronic device430comprises a third processing circuit433configured to combine the first Isolation Forest model and the second Isolation Forest model to obtain a combined Isolation Forest model as described above. Further, the third electronic device430comprises an output interface431configured to transmit the combined Isolation Forest model to the first electronic device410and the second electronic device420. In some example, the output interface431may be configured to transmit the combined Isolation Forest model to only one of the first electronic device410and the second electronic device420

The first electronic device410comprises an input interface412configured to receive the combined Isolation Forest model from the third electronic device430. Similarly, the second electronic device420comprises an input interface422configured to receive the combined Isolation Forest model from the third electronic device430.

The first processing circuit411is configured analyze data at the first electronic device410for anomalies using the second Isolation Forest model. Similarly, the second processing circuit421is configured analyze data at the second electronic device420for anomalies using the second Isolation Forest model.

For example, each of the processing circuits413,423and433may be a single dedicated processor, a single shared processor, or a plurality of individual processors, some of which or all of which may be shared, a digital signal processor (DSP) hardware, an application specific integrated circuit (ASIC) or a field programmable gate array (FPGA). Each of the processing circuits413,423and433may optionally be coupled to, e.g., read only memory (ROM) for storing software, random access memory (RAM) and/or non-volatile memory.

Each of the input interfaces412,422and432as well as each of the output interfaces411,421and431may be implemented as a hardware circuit or as a software interface.

The electronic device410,420and430may further comprise other hardware—conventional and/or custom.

By combining the Isolation forest models of the electronic devices410and420, the more generic combined Isolation Forest model is obtained and provided to the electronic devices410and420. Therefore, the electronic devices410and420are capable of detecting more types of anomalies in data.

For example, the proposed technique for anomaly detection may be deployed as an extension of an operating system service such as a firewall, or as a daemon running as a background process. In both cases, it does not need direct control of an interactive user and its interface need not be directly exposed.

The following examples pertain to further embodiments:(1) A method for generating a combined Isolation Forest model for detecting anomalies in data, the method comprising:receiving a first Isolation Forest model for detecting anomalies in data from a first electronic device, wherein the first Isolation Forest model is trained at the first electronic device;receiving a second Isolation Forest model for detecting anomalies in data from a second electronic device, wherein the second Isolation Forest model is trained at the second electronic device; andcombining the first Isolation Forest model and the second Isolation Forest model to obtain the combined Isolation Forest model.(2) The method of (1), further comprising:transmitting the combined Isolation Forest model to at least one of the first electronic device and the second electronic device.(3) The method of (1) or (2), wherein the first Isolation Forest model represents a first plurality of trained decision trees, and wherein the second Isolation Forest model represents a second plurality of trained decision trees.(4) The method of (3), wherein combining the first Isolation Forest model and the second Isolation Forest model comprises merging the first plurality of trained decision trees and the second plurality of trained decision trees.(5) The method of (3) or (4), wherein combining the first Isolation Forest model and the second Isolation Forest model comprises compacting at least one of the first plurality of trained decision trees and the second plurality of trained decision trees.(6) The method of any of (3) to (5), wherein combining the first Isolation Forest model and the second Isolation Forest model comprises pruning at least one of the first plurality of trained decision trees and the second plurality of trained decision trees.(7) The method of any of (3) to (6), wherein combining the first Isolation Forest model and the second Isolation Forest model comprises:searching for redundancies in the first plurality of trained decision trees and the second plurality of trained decision trees; andremoving found redundancies from the first plurality of trained decision trees and the second plurality of trained decision trees.(8) The method of any of (3) to (7), wherein combining the first Isolation Forest model and the second Isolation Forest model comprises:calculating path lengths for paths from root nodes to end nodes of the first plurality of trained decision trees and the second plurality of trained decision trees;calculating statistics indicative of a relevance of a respective path for paths exhibiting a path length shorter than a threshold value; andusing the paths for the combined Isolation Forest model for which the statistics indicates that the respective path is relevant.(9) The method of (8), wherein the threshold value depends on the anomalies to be detected by the combined Isolation Forest model.(10) The method of any of (1) to (9), wherein at least one of the first electronic device and the second electronic device is an Internet-of-Things, IoT, device.(11) A method for an electronic device, comprising:training a first Isolation Forest model for detecting anomalies in data;transmitting the trained first Isolation Forest model to another electronic device;receiving from the other electronic device a combined Isolation Forest model for detecting anomalies in data, wherein the combined Isolation Forest model is a combination of the first Isolation Forest model and at least a second Isolation Forest model for detecting anomalies in data; andanalyzing data at the electronic device for anomalies using the combined Isolation Forest model.(12) The method of (11), wherein the electronic device is an Internet-of-Things, IoT, device.(13) The method of (12), wherein the other electronic device is a server or a server network.(14) An apparatus for generating a combined Isolation Forest model for detecting anomalies in data, the apparatus comprising:an input interface configured to:receive a first Isolation Forest model for detecting anomalies in data from a first electronic device, wherein the first Isolation Forest model is trained at the first electronic device; andreceive a second Isolation Forest model for detecting anomalies in data from a second electronic device, wherein the second Isolation Forest model is trained at the second electronic device; anda processing circuit configured to combine the first Isolation Forest model and the second Isolation Forest model to obtain the combined Isolation Forest model.(15) An electronic device, comprising:a processing circuit configured to train a first Isolation Forest model for detecting anomalies in data;an output interface configured to transmit the trained first Isolation Forest model to another electronic device; andan input interface configured to receive from the other electronic device a combined Isolation Forest model for detecting anomalies in data, wherein the combined Isolation Forest model is a combination of the first Isolation Forest model and at least a second Isolation Forest model for detecting anomalies in data,wherein the processing circuit is further configured to analyze data at the electronic device for anomalies using the combined Isolation Forest model.(16) A system comprising:a first electronic device comprising a first processing circuit configured to train a first Isolation Forest model for detecting anomalies in data;a second electronic device comprising a second processing circuit configured to train a second Isolation Forest model for detecting anomalies in data; anda third electronic device comprising:an input interface configured to receive the first Isolation Forest model from the first electronic device and the second Isolation Forest model from the second electronic device;a third processing circuit configured to combine the first Isolation Forest model and the second Isolation Forest model to obtain a combined Isolation Forest model; andan output interface configured to transmit the combined Isolation Forest model to the first electronic device and the second electronic device,wherein at least one of the first processing circuit and the second processing circuit is configured to analyze data at the respective electronic device for anomalies using the second Isolation Forest model.(17) A non-transitory machine readable medium having stored thereon a program having a program code for performing the method for generating a combined Isolation Forest model according to any of (1) to (10), when the program is executed on a processor or a programmable hardware.(18) A program having a program code for performing the method for generating a combined Isolation Forest model according to any of (1) to (10), when the program is executed on a processor or a programmable hardware.(19) A non-transitory machine readable medium having stored thereon a program having a program code for performing the method according to (11) or (12), when the program is executed on a processor or a programmable hardware.(20) A program having a program code for performing the method according to (11) or (12), when the program is executed on a processor or a programmable hardware.

The description and drawings merely illustrate the principles of the disclosure. Furthermore, all examples recited herein are principally intended expressly to be only for illustrative purposes to aid the reader in understanding the principles of the disclosure and the concepts contributed by the inventor(s) to furthering the art. All statements herein reciting principles, aspects, and examples of the disclosure, as well as specific examples thereof, are intended to encompass equivalents thereof.

A block diagram may, for instance, illustrate a high-level circuit diagram implementing the principles of the disclosure. Similarly, a flow chart, a flow diagram, a state transition diagram, a pseudo code, and the like may represent various processes, operations or steps, which may, for instance, be substantially represented in non-transitory machine readable medium (e.g. a floppy disc, a DVD, a Blu-Ray, a CD, a ROM, a PROM, and EPROM, an EEPROM or a FLASH memory) and so executed by a processor or a programmable hardware, whether or not such processor or a programmable hardware is explicitly shown. Methods disclosed in the specification or in the claims may be implemented by a device having means for performing each of the respective acts of these methods.