COMPUTER-READABLE RECORDING MEDIUM, DETECTION METHOD, AND DETECTION APPARATUS

A non-transitory computer-readable recording medium stores a program that causes a computer to execute a process including: performing a first conversion processing to convert a value indicating each event, and to convert, based on conversion information that indicates a group of the value and an identification value that corresponds to values belonging to the group; constructing information with occurrence probabilities by connecting identification values; performing second conversion processing to convert a value indicating each event included in event data, and to convert values that belong to a group indicated in the conversion information into an identical identification value corresponding to the group based on the conversion information; and detecting an anomaly based on a result of comparison between the constructed information and the identification value.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2016-006453, filed on Jan. 15, 2016, the entire contents of which are incorporated herein by reference.

FIELD

The embodiment discussed herein is related to a computer-readable recording medium, a detection method, and a detection apparatus.

BACKGROUND

Conventionally, anomaly detection for a system, operation, and the like by analyzing big data (hereinafter, referred to as history log), such as a log of a system and measurement data has been proposed. In this anomaly detection, a risk tree in which an anomaly event included in a history log is arranged at the top, and other anomaly events that occur due to the anomaly event are arranged as following events, and that indicates a risk value of each anomaly event is stored. When successive events occur in real time in a system in a sequence indicated in the risk tree, an anomaly in the system in a current state is detected (Japanese Laid-open Patent Publication Nos. 7-217963, 9-231321, 2014-126882).

As a method learning an occurrence sequence (pattern) of an event and an occurrence probability of each event to reflect to a tree to which the occurrence probability of each event has been added, there has been a probabilistic suffix tree (PST). In this PST, a PST obtained as a result of learning and an occurrence sequence (pattern) of current events are compared. When the current pattern is new (no such path exists in the PST) or is a rare pattern (pattern with a significantly low occurrence probability), an anomaly that is “unusual” can be detected.

For the anomaly detection, real time detection enabling to detect an anomaly in real time is demanded. Therefore, when considering to adopt PST in the anomaly detection, a PST is to be stored in a memory such as a random access memory (RAM). However, a region length (memory usage) of a PST increases sharply in proportion to a product of the number of levels of patterns and the number of elements in each level in the PST. When the memory usage increases as such, storage of a PST in a memory is difficult.

SUMMARY

According to an aspect of an embodiment, a non-transitory computer-readable recording medium stores therein a detection program that causes a computer to execute a process including: performing a first conversion processing to convert a value indicating each event that is included in history log into an identification value corresponding to the value, and to convert, based on conversion information that indicates a group of the value and an identification value that corresponds to values belonging to the group, values that belong to a group indicated in the conversion information into an identical identification value that corresponds to the group; constructing information with occurrence probabilities by connecting identification values that are obtained by conversion by the first conversion processing in order of occurrence of the event sequentially from a root, and by assigning an occurrence probability of an event that corresponds to the identification value per identification value; performing second conversion processing to convert a value indicating each event included in event data that is input according to an event has occurred into an identification value corresponding to the value, and to convert values that belong to a group indicated in the conversion information into an identical identification value corresponding to the group based on the conversion information; and detecting an anomaly based on a result of comparison between the constructed information with occurrence probabilities and the identification value that is obtained by conversion by the second conversion processing.

DESCRIPTION OF EMBODIMENT

Preferred embodiments of the present invention will be explained with reference to accompanying drawings. The same reference symbol is given to components having the same function in an embodiment, and duplicated explanation is omitted. The detection program, the detection method, and the detection apparatus explained in the following embodiment are only one example, and are not intended to limit embodiments. Moreover, the following embodiments can be combined as appropriate within a range not causing a contradiction.

FIG. 1is a block diagram depicting a configuration example of a detection apparatus1according to an embodiment. The detection apparatus1depicted inFIG. 1is an information processing apparatus such as a personal computer (PC).

The detection apparatus1constructs a PST14by reading a history log20that are big data such as a log and measurement data of a large-scale computer system, a network system, and the like, and in which events that have occurred once are described in chronological order. The detection apparatus1accepts event data30that is input according to an event occurring in real time in a system of a subject of monitoring, detects an anomaly in the system of a subject of monitoring based on a comparison result between the constructed PST14and the event data30, and informs the detection result to a user. For example, the detection apparatus1outputs a detection result of the anomaly detection to another terminal device2or a predetermined application, and informs the detection result to the user by displaying the detection result in the terminal device2or by notification by the application.

Events in the history log20and the event data30can be of various kinds, and not particularly limited. For example, when a cyberattack to a system of a subject of monitoring is detected as anomaly, an events can be mail reception, mail operation, PC operation, a web access, data communication, or the like. Moreover, when unauthorized entrance to a system of a subject of monitoring is detected as anomaly, an event can be an action of a user that is detected by an image taken by a monitoring camera or an operation of a card key. Furthermore, when an environmental abnormality in a system of a subject of monitoring is detected as anomaly, an event can be temperature, humidity, or the like detected by a sensor. Moreover, in a system of monitoring a stock market and the like, a stock price of each brand, weather information, a comment in a social networking service (SNS), and the like can be an event.

FIG. 2is an explanatory diagram explaining an overview of the anomaly detection. The history log20depicted inFIG. 2is one example of a series of event that starts with “GET text/html” in data communication of a proxy server and the like.

As depicted inFIG. 2, the detection apparatus1converts events described in chronological order in the history log20into identification values. In the depicted example, “GET text/html” is converted into an identification value “1”, and “GET image/jpg” is converted into “9”, and “POST text/html” is converted into “11”. Subsequently, the detection apparatus1generates a pattern20ain which identification values are arranged in order of occurrence of the events.

Subsequently, the detection apparatus1connects the identification values (1, 9, 9, 9, 11) in the order of occurrence of the events from a root to branches. For example, for the identification values having a trunk (path) from the root (duplicated identification values) are connected so as to follow the same path. The identification values having no path (not duplicated) are arranged to be structured as a tree with a new branch. Subsequently, the detection apparatus1adds an occurrence probability (transition probability) of the event corresponding to the identification value to each of the identification values in the tree structure, to construct the PST14. Specifically, a transition probability is calculated by using the total number of events as a denominator, and the number of occurrence of each event (the number of times of passing through a path of identification values) as a numerator, and the calculated transition probability is added to each identification value. The number of path levels in the PST14can be limited to suppress increase of the memory usage.

The detection apparatus1converts events that are described in chronological order in the event data30into identification values similarly to the history log20, and arranges the identification values in order of occurrence, thereby generating a pattern (current pattern) that indicates the current state of the system. Subsequently, the detection apparatus1compares the constructed PST14with the current pattern that is obtained by conversion from the event data30. When the current pattern is new (no such path exists in the PST14) or is a rare pattern (pattern with a significantly low occurrence probability, lower than a predetermined value), an anomaly is detected.

As depicted inFIG. 1, the detection apparatus1includes a preprocessing units10aand10b,a detection/rule information11, a conversion table12, a PST constructing unit13, the PST14, a PST searching unit15, a distributing/layering processing unit16, and an anomaly detecting unit17.

The preprocessing units10aand10bperform preprocessing, such as data shaping/processing, for input data. The preprocessing unit10asubjects the history log20that is input by the system of a subject of monitoring to preprocessing, and outputs the processed data to the PST constructing unit13. The preprocessing unit10bsubjects the event data30that is input by the system of a subject of monitoring to preprocessing, and outputs the processed data to the PST searching unit15. Note that the preprocessing units10aand10bcan be configured without being separated for the history log20and the event data30, but it can be configured such that a single preprocessing unit is shared.

The preprocessing performed by the preprocessing units10aand10bincludes conversion processing to convert a value (details) of each event included in the history log20and the event data30into a corresponding identification value based on a predetermined rule. This identification value can be a numeric value, a character, a symbol, or a combination of a numeric value, a character, and a symbol that corresponds to the details of an event, and is not particularly limited. In the present embodiment, a value of an event is converted into a numeric value by the preprocessing by the preprocessing units10aand10b,as one example.

Moreover, the preprocessing performed by the preprocessing units10aand10bincludes conversion processing to convert values that belong to a group indicated in the conversion table12into an identical identification value corresponding to the group, based on the conversion table12that indicates a group of values of each event, and an identification value that corresponds to the values belonging to the group. By this conversion processing, when values of respective events included in the history log20and the event data30belong to the group indicated in the conversion table12, the values are uniformly converted into the same identification value, thereby reducing the number of elements of the PST14.

Furthermore, the processing performed by the preprocessing unit10aincludes processing of calculating a statistical distribution of values indicating respective events that are included in the history log20according to definition/rule indicated in the definition/rule information11, and of making a group based on a range of values according to the calculated statistical distribution, and of creating the conversion table12in which an identification value corresponding to this group is defined. By thus creating the conversion table12, grouping according to a statistical distribution of values that indicate respective events can be done in the preprocessing that is performed by the preprocessing units10aand10b.

Moreover, the processing performed by the preprocessing unit10aincludes processing of calculating an appearance frequency of a sequence in chronological order according to definition/rule indicated in the definition/rule11, for values indicating respective events that are included in the history log20, and of making a group based on a sequence, the calculated appearance frequency of which is equal to or higher than a predetermined value, and of creating the conversion table12in which an identification value corresponding to this group is defined. By thus creating the conversion table12, a sequence, the appearance frequency of which is equal to or higher than a predetermined value, that is, a pattern of frequent appearance, is uniformly converted into an identical identification value, thereby reducing the number of path levels in the PST14.

The definition/rule information11is information indicating definitions and rules, and for example, definitions and rules relating to calculation of the statistical distribution and the appearance frequency described above, and the like are indicated therein. The definition/rule information11is specified by a user in advance and stored in a storage device such as a memory and a hard disk drive HDD).

The PST constructing unit13constructs the PST14based on the history log20subjected to the preprocessing. The constructed PST14is stored in a storage device such as a memory and an HDD. The PST searching unit15compares the PST14constructed from the history log20with the event data30subjected to the preprocessing, and searches for a tree that matches the current pattern obtained by converting from the event data30. The search result by the PST searching unit15is output to the anomaly detecting unit17.

The distributing/layering processing unit16distributes/layers respective processing in the detection apparatus1by using plural threads, and the like. For example, the distributing/layering processing unit16distributes/layers processing for the PST search in the PST searching unit15, and the anomaly detection in the anomaly detecting unit17. By thus distributing/layering the processing in the PST searching unit15and the anomaly detecting unit17, real time detection of the anomaly detection can be improved. Note that the distribution and layering of processing by the PST searching unit15can be applied to the respective processing in the preprocessing units10aand10b,and the PST constructing unit13.

The anomaly detecting unit17performs anomaly detection based on a search result by the PST searching unit15. Specifically, when there is no matching tree as a result of searching by the PST searching unit15, the current pattern is new (there is no path in the PST), and therefore detected as an anomaly. Moreover, when there is a matching tree as a result of searching by the PST searching unit15, if the transition probability added to the tree is equal to or lower than a predetermined value and is significantly low, it is detected as an anomaly. The anomaly detecting unit17outputs the detection result to the terminal device2or a predetermined application.

Details of the processing for construction of the PST14are explained.FIG. 3is a flowchart indicating one example of processing for construction of the PST14.

As indicated inFIG. 3, when processing is started, the preprocessing unit10areads the definition/rule information11that is stored in a memory or the like (S1).

FIG. 4is an explanatory diagram explaining the definition/rule information11. As depicted inFIG. 4, in the definition/rule information11, definitions and rules, such as a grouping rule and remarks per event (elements A to Y) that is included in the history log20are indicated. In the grouping rule, whether to perform grouping (1or0), a learning algorithm indicating a statistical processing and the like performed when grouping is performed, and the number of division/threshold to be set are indicated.

Following S1, the preprocessing unit10areads the history log20(S2). Subsequently, the preprocessing unit10aperforms processing at S3to S7per event (elements A to Y) that is included in the history log20.

Specifically, at S3, the preprocessing unit10arefers to the grouping rule per event (elements A to Y) indicated in the definition/rule information11, and determines whether to perform grouping of the elements of a subject of processing (S3). When it is determined not to perform grouping (S3: NO), the preprocessing unit10askips processing at S4to S6and proceeds the processing to S7.

When it is determined to perform grouping (S3: YES), the preprocessing unit10arefers to the grouping rule per event (elements A to Y) indicated in the definition/rule information11, and determines which learning/rule is used for grouping (S4).

For example, when statistical processing such as “clustering” and “distribution/frequency calculation” is indicated in the grouping rule, it is determined that grouping is performed by learning. Moreover, when a rule such as “upper limit/lower limit setting” is indicated in the grouping rule, it is determined to perform grouping by rule.

When grouping is performed by learning at S4, the preprocessing unit10aacquires a statistical distribution of events that are included in the history log20by the statistical processing indicated in the grouping rule, and performs learning for a subject element (S5).

FIG. 5is an explanatory diagram explaining learning by statistical processing. As depicted inFIG. 5, a case C1is a case in which values within certain values (for example 6σ, 2σ in product quality, +30%, −30% in stock price, and the like) relative to a standard deviation (σ) matter. For elements of this case C1, statistical processing such as “distribution/frequency calculation” is indicated in the grouping rule, and a standard deviation (σ) and the like necessary for grouping is acquired by the statistical processing.

A case C2is a case in which a certain range (successive values) matters such as temperature and humidity. For elements of this case C2, a rule such as “upper limit/lower limit setting” is indicated in the grouping rule, and a threshold corresponding to a certain range is set.

A case C3is a case in which a distribution of a specific group (cluster) appears as a result of statistics/analysis, such as a preference. For elements of this case C3, statistical processing such as “clustering” is indicated in the grouping rule, and a cluster transform for grouping is acquired by the statistical processing.

When grouping is performed by the rule at S4, the preprocessing unit10aperform threshold setting corresponding to a range, such as “17 degrees Celsius (C.) to 19 degrees C.”, indicated in the grouping rule (S6).

Subsequently, the preprocessing unit10adetermines a threshold for grouping of elements based on a result of the learning of subject elements (S5), or the threshold setting (S6). For example, when a standard deviation (σ) is acquired by statistical processing such as “distribution/frequency calculation” in the learning of the subject elements, thresholds (2σ, 6σ) to divide into three are determined using the standard deviation (σ). When grouping is not performed (S3: NO), it determines as no threshold.

Subsequently, the preprocessing unit10adetermines whether the processing at S3to S7have been completed for all of the elements of the event included in the history log20(S8). When the processing has not completed for the all of the elements (S8: NO), the preprocessing unit10areturns the processing to S3to perform the processing at S3to S7for a next element.

When the processing has been completed for all of the elements (S8: YES), the preprocessing unit10acreates the conversion table12in which a unique identification value is assigned to a range of grouping determined by the processing of grouping/threshold determination (S7) for each element (S9). When the conversion table12has been set in advance by a user or the like, the processing from S1to S9described above can be omitted.

Subsequently, the preprocessing unit10areads the history log20(S10), and converts a value (details) of each event included in the history log20into a corresponding identification value based on the rule defined in advance. Moreover, as for values that belong to a group indicated in the conversion table12, the preprocessing unit10aconverts the values into the same identification value corresponding to the group based on the conversion table12. The PST constructing unit13then constructs the PST14based on the history log20subjected to conversion (S11).

FIG. 6is an explanatory diagram explaining construction of a PST based on the conversion table12. As depicted inFIG. 6, the conversion table12has a group, which is a range of numeric value/character in each element, and an identification value to convert a value belonging to the group into. For example, in the conversion table12, it is indicated that for element (A) that is first from the root, numeric values “2 to 4” are converted into an identification value “10”. Therefore, compared to a PST14A that is constructed with independent identification values, the number of elements can be reduced in a PST14B in which the numeric values “2 to 4” of element A are replaced with “10”, and the horizontal width in the tree structure can be narrowed.

FIG. 7is an explanatory diagram explaining a case in which elements following a root are replaced in a PST. InFIG. 7, the tree structures from the root to the respective elements in the PST14A and PST14B are expressed as data in a table format that is referred to sequentially from the root by a lower-level element pointer.

As depicted inFIG. 7, the PST14A constructed with independent identification values has 300 elements that corresponds to numeric values 1 to 300 at the first level (element: A) from the root, and has 1 element corresponding to a single numeric value 1000 at the second level (element: B). To the contrary, the PST14B in which the elements following the root are replaced based on the conversion table12indicating that for the first level (element: A), a numeric value within upper limit=300 and lower limit=1 is replaced with a numeric value 500 has a single element of the numeric value 500 at the first level (element: A). Therefore, as is obvious from comparison between the numbers of tables in the PST14A and the PST14B, by constructing the PST14B based on the conversion table12, the memory usage for PST can be significantly reduced.

Next, details of processing in the anomaly detection are explained.FIG. 8is a flowchart indicating one example of processing in the anomaly detection.

As indicated inFIG. 8, when the processing is started, the preprocessing unit10breads the event data30, and creates a current pattern (S20). Subsequently, the preprocessing unit10bselects the created current pattern as a tree portion (subject tree) to be a subject of searching in the PST14(S21). Subsequently, the preprocessing unit10bperforms converts the subject tree into numeric values by the conversion table12(S22), and thereby converts into an identical identification value uniformly when values in the subject tree belong to a group indicated in the conversion table12.

Subsequently, the PST searching unit15compares the PST14with the subject tree subjected to numeric conversion, and searches for a corresponding tree that matches the subject tree (S23). The anomaly detecting unit17determines the transition probability of a new tree having no matching tree/corresponding tree, based on a result of searching by the PST searching unit15(S24). Based on a result of determination at S24, the anomaly detecting unit17detects as an anomaly when it is new with no matching tree and when the transition probability of the corresponding tree is significantly low being equal to or lower than a predetermined value (S25).

Subsequently, when the subject tree in this processing is connected to the PST14, the total number of events in the PST14increases, and therefore, the PST constructing unit13updates the transition probability in the PST14(S26). When the subject tree in this processing is not connected to the PST14, the total number of events in the PST14does not change, and therefore, the processing at S26is skipped, and the processing is ended without updating the transition probability.

Reduction in the number of levels (vertical width) of the PST14is explained. In reduction of the number of levels, grouping is performed on multiple number of successive levels (arranged sequence) in the PST14, thereby compressing the PST14.

Reduction in the number of levels includes reduction of combination patterns such as array, and reduction of sequence (chronological) patterns.

In the case of combination patterns, grouping is performed by the same method as that in reduction of elements (horizontal width) described above. Specifically, in the PST14, “plural levels” related to each other are arranged to be adjacent to each other, and grouping is performed by statistical processing (for example, clustering) and the like, and each group is replaced with an identical identification value (one element). In clustering or the like, there is a case in which both levels (vertical width) and elements (horizontal width) are reduced.

In the case of sequence (chronological) patterns, a “pattern” having high appearance frequency (basically, closing) is extracted, and is registered in the conversion table12for “substrings”. For example, “1→2→3” is replaced with “N”, and following “nests (destinations)” are all connected right under “N”. A disconnection of a pattern is extracted by frequency (transition probability), and a transition probability of a “substring” is stored for each replaced part. At the time of searching for the PST14, a replacement display of “N” and the conversion able12are recognized, and search is continued. Furthermore, a current pattern is used as a window, and is stored in a storage device, such as a memory and an HDD, together with the conversion table12, to be used for comparison. Moreover, by storing the window of the current pattern in the storage device together with the conversion table12, recursive replacement of the “substring” and branching in the middle can also be enabled.

FIG. 9is a flowchart indicating one example of processing for construction of the PST14. Specifically,FIG. 9is a flowchart exemplifying construction of the PST14for reducing the number of levels (vertical width). Processing (S30to S33) in the early stage inFIG. 9exemplifies processing for reducing combination patterns such as array. Processing (S34to S37) in a later stage inFIG. 9exemplifies processing for reducing sequence (chronological) patterns.

As depicted inFIG. 9, when processing is started, the preprocessing unit10areads the definition/rule information11and the history log20(S30).FIG. 10is an explanatory diagram explaining the definition/rule information11. As depicted inFIG. 10, in the definition/rule information11, a combination of levels according to the combination pattern and a grouping rule is indicated.

Subsequently to S30, the preprocessing unit10aacquires a level combination that is indicated in the definition/rule information11from a tree in the history log20(S31). Subsequently, the preprocessing unit10aperforms learning/grouping by statistical processing indicated in the definition/rule information11for the acquired combinations (S32).

Subsequently, the preprocessing unit10adetermines whether the processing at S31and S32are completed for all of the combinations indicated in the definition/rule information11(S33). When the processing at S31and S32has not been completed for all of the combinations (S33: NO), the preprocessing unit10areturns the processing to S31to perform the processing at S31and S32for a next level combination.

At S34, the preprocessing unit10aextracts a highly frequent substring (sequence), the transition probability of which is equal to or higher than a predetermined value in the PST14. Subsequently, the preprocessing unit10aregisters the extracted substring in the conversion table12together with a corresponding identification value (replacement number) (S35). Subsequently, the preprocessing unit10areplaces a substring that corresponds to the substring in the conversion table12with a replacement number in the PST14(S36).

Subsequently, the preprocessing unit10adetermines whether the processing at S34to S36has been completed for all of the substrings (S37). When the processing at S34to S36has not been completed for all of the substrings (S37: NO), the preprocessing unit10areturns the processing to S34to perform the processing at S34to S36for a next substring.

FIG. 11is an explanatory diagram explaining replacement of substrings in a PST. As depicted inFIG. 11, in the conversion table12, as the substring “1→2→3” has a high frequency, the replacement number “N” is registered. The preprocessing unit10aholds a current pattern as a window12A. The preprocessing unit10areplaces, when contents (sequence) of the window12A matches a substring in the conversion table12, the sequence is replaced with a replacement number. For example, the substring “1→2→3” in the PST14is replaced with “N”. Thus, the PST14A becomes the PST14B in which the number of levels has been reduced. Thus, by reducing the number of levels, the memory usage for a PST can be reduced.

The case in which the memory usage for a PST is reduced includes, for example, a case of stock price and a case of cluster. As for the case of a stock price, there is a case in which a stock valued at 1000 yen fluctuates in increments of 1 yen up to 1300 (+30%) to hit limit-up, as one example. In this case, by grouping points that fluctuates in increments of 1 yen, 300 elements (branches) from an event of 1000 yen at the root can be handled as a single element. Moreover, in the case of cluster, basically each cluster element is replaced with a single element. Therefore, multiple levels (vertical width) and multiple elements (horizontal width) can be reduced to the number corresponding to the number of clusters.

The PST constructing unit13can reconstruct a tree in the PST14by sorting in order of the transition probabilities in the PST14. This sorting mainly includes “sequence, and “array”. In the “sequence”, elements (horizontal width) at the same level are rearranged, starting from the root sequentially toward subordinating levels (toward branches). In “array”, levels (vertical) and elements (horizontal) in the same level are rearranged in a set in descending order of the transition probabilities.

FIG. 12is a flowchart indicating one example of processing for reconstruction of the PST14. As indicated inFIG. 12, when processing is started, the PST constructing unit13determines either sorting of “sequence” or “array” is to be performed (S40). When determined as “array” at S40, the PST constructing unit13refers to the PST14, and rearranges all levels (vertical) in descending order of transition probabilities (S41). Subsequently, the PST constructing unit13rearranges elements, for example, in descending order in each level sequentially from the tree top toward subordinating levels (S42). When determined as “sequence at S40, the PST constructing unit13rearranges elements in each levels in descending order of transition probabilities while avoiding duplication, sequentially from the treetop (S43).

FIG. 13is an explanatory diagram explaining reconstruction of a PST. As depicted inFIG. 13, the PST14A before reconstruction has a tree structure in which branches extend irrespective of transition probabilities. To the contrary, the PST14B after reconstruction has a tree structure in which branches with high transition probabilities are adjacent to each other. Since data having high transition probability has a high access frequency, the probability of being held in a cache of a memory is to be high. Therefore, by reconstruction of the PST14by sorting, the cache hit rate at the time of referring to the PST14is expected to be improved.

FIG. 14is a flowchart indicating one example of processing for reconstruction of the PST14. Specifically,FIG. 14is another example of the processing exemplified inFIG. 12. In this example, to the reconstructed PST14, numbers are reassigned from a (low) “number” in descending order of transition probabilities. As for “sequence”, replacement to a (low) number is uniform in the entire part. As for “array”, assignment of a number is independent in each level (vertical), and a “number” can be duplicated among levels.

As indicated inFIG. 14, when processing is started, the PST constructing unit13determines either sorting of “sequence” or “array” is to be performed (S50). When determined as “array” at S50, the PST constructing unit13refers to the PST14, and replaces with a (low) number unique to each level sequentially from the tree top (S51). When determined as “sequence” at S50, the PST constructing unit13refers to the PST14, and replaces with low numbers without duplication in descending order of transition probabilities, sequentially from the tree top (S52). Subsequently to S51, S52, the PST constructing unit13divides/cuts the PST14in a certain transition probability/region length (S53).

FIG. 15is a flowchart indicating one example of processing for division/cut of the PST14.FIG. 16is an explanatory diagram explaining the division/cut of the PST14. As indicated inFIG. 15, when processing is started, the PST constructing unit13refers to the PST14, evaluates transition probabilities from the tree top (S60), and compares with a predetermined value to make determination of “HIGH”/“MEDIUM”/“LOW” (S61).

When a transition probability is high (“HIGH”), the PST constructing unit13makes the tree evaluated as to have a high transition probability memory resident (S62). Moreover, when a transition probability is medium (“MEDIUM”), the PST constructing unit13arranges a part evaluated as to have medium transition probability in the memory in a distributed/layered manner (S63). For example, distribution can be done by arranging to a memory of another server. Layering can be done by arranging in, for example, a disk device (external storage). However, as for divided part, a pointer is held on the memory.

Furthermore, when a transition probability is low (“LOW”), the PST constructing unit13cuts a part (lower part of tree) evaluated as to have a low transition probability from the memory (S64). As depicted inFIG. 16, by performing division/cut described above, the memory usage for the PST14can be made efficient.

As described above, the preprocessing unit10aof the detection apparatus1converts a value indicating each event that is included in the history log20into an identification value that corresponds to the value. Moreover, the preprocessing unit10aperforms processing of converting values that belong to a group indicated in the conversion table12into an identical identification value that corresponds to the group, based on the conversion table12in which a group of values and an identification value that corresponds to values belonging to this group are indicated. Furthermore, the PST constructing unit13of the detection apparatus1constructs the PST14in which the identification values that are obtained by conversion by the preprocessing unit10ain order of occurrence of events are sequentially connected from the root, and in which an occurrence probability of an event corresponding to an identification value is assigned to each identification value. Moreover, the preprocessing unit10bof the detection apparatus1converts a value indicating each event included in the event data30into an identification value corresponding to a value. Furthermore, the preprocessing unit10bperforms processing of converting values that belong to a group indicated in the conversion table12into an identical identification value corresponding to the group, based on the conversion table12. The anomaly detecting unit17of the detection apparatus1performs anomaly detection based on a result of comparison between the constructed PST14and the identification value obtained by conversion by the preprocessing unit10b.

Therefore, in the detection apparatus1, for values indicating respective events that are included in the history log20, values that belong to a group indicated in the conversion table12are converted in to an identical identification value corresponding to the group. Therefore, the memory usage of the PST14can be reduced. Moreover, by converting into an identical identification value corresponding to a group, transition probabilities in the PST14are concentrated at the identification value corresponding to the group, and therefore, the distribution of “dense/sparse” in transition probabilities becomes sharp and clear. Therefore, the anomaly detection performance (accuracy) by searching of the PST14is improved.

The illustrated components of respective devices are not necessarily required to be configured physically as illustrated. That is, a specific form of distribution and integration of the respective devices is not limited to the one illustrated, and all or a part thereof can be configured to be distributed/configured functionally or physically in an arbitrary unit according to various kinds of loads and use conditions.

For example, although a device configuration in a single unit of the detection apparatus1has been exemplified in the present embodiment, it can be configured as cloud computing in which multiple storage devices, server devices, and the like are connected through a network.

Moreover, respective processing functions executed in the detection apparatus1can be configured such that all or a part thereof is executed on a central processing unit (CPU) (or a microcomputer such as a micro-processing unit (MPU) and a micro controller unit (MCU)). Furthermore, it is needless to say that the respective processing functions can be configured such that all or an arbitrary part thereof is executed on a program that is analyzed and executed by a CPU (or a microcomputer such as an MPU and an MCU), or on hardware by wired logic.

The respective processing explained in the above embodiment can be implemented by executing a program that is prepared in advance by a computer. Therefore, in the following, one example of a computer (hardware) that executes a program that has the same functions as the embodiment described above is explained.FIG. 17is a block diagram of a hardware configuration of the detection apparatus1according to the embodiment.

As depicted inFIG. 17, the detection apparatus1includes a CPU101, that executed various kinds of arithmetic processing, an input device102that accepts data input, a monitor103, and a speaker104. Moreover, the detection apparatus1includes a medium reading device105, that reads a program and the like from a storage medium, an interface device106to connect to various devices, and a communication device107to connect to an external device by wired or wireless communication. Furthermore, the detection apparatus1includes a RAM108that temporarily stores various kinds of information and a hard disk device109. Moreover, the respective components (101to109) in the detection apparatus1are connected to a bus110.

In the hard disk device109, a program111to perform various kinds of processing in the preprocessing units10a,10b,the conversion table12, the PST constructing unit13, the PST searching unit15, the distributing/layering processing unit16, and the anomaly detecting unit17explained in the above embodiment is stored. Furthermore, in the hard disk device109, various kinds of data112(the definition/rule information11, the conversion table12, the PST14, the history log20, the event data30, and the like) that is referred to by the program111is stored. The input device102accepts an input of, for example, operation information from an operator of the detection apparatus1. The monitor103displays various kinds of screens that is operated by the operator, for example. To the interface device106, for example, a printer device and the like are connected. The communication device107is connected to a communication networks such as a local area network (LAN), and communicates various kinds of information with an external device through the communication network.

The CPU101reads the program111stored in the hard disk device109, and develops and executes the program111on the RAM108, to perform various kinds of processing. The program111is not necessarily required to be stored in the hard disk device109. For example, it can be configured such that the detection apparatus1reads the program111stored in a storage medium that can be read by the detection apparatus1to execute it. The storage medium that can be read by the detection apparatus1corresponds to a portable recording medium such as a compact disk read-only memory (CD-ROM), a digital versatile disk (DVD), a universal serial bus (USB) memory, a semiconductor memory such as a flash memory, a hard disk drive, and the like. Moreover, it can be configured such that the program111can be stored in a device connected to a public line, the Internet, a LAN, or the like, and the program111is read and executed by the detection apparatus1therefrom.

According to one embodiment of the present invention, memory usage in anomaly detection can be reduced.