Abstract:
Systems and methods are disclosed for detecting periodic event behaviors from machine generated logging by: capturing heterogeneous log messages, each log message including a time stamp and text content with one or more fields; recognizing log formats from log messages; transforming the text content into a set of time series data, one time series for each log format; during a training phase, analyzing the set of time series data and building a category model for each periodic event type in heterogeneous logs; and during live operation, applying the category model to a stream of time series data from live heterogeneous log messages and generating a flag on a time series data point violating the category model and generating an alarm report for the corresponding log message.

Description:
BACKGROUND 
       [0001]    The system relates to machine determination of periodic event behaviors. 
         [0002]    A periodic event is an event that happens regularly over and over again at a fixed interval or a set of fixed intervals (meaning the time between events is substantially the same or among several possible values). Periodicity analysis from the recorded log data is an important task which provides useful insights into the physical events and enables a system to report outliers and predict future behaviors. For example,  FIG. 1  shows a set of text logs mined from IT system logs including the periodical pattern of a system event type: it happens twice a day, around 1:00 AM and 14:00 PM. Based on the log event periodicity learnt from  FIG. 1 , unexpected system behaviors can be detected. For example,  FIG. 2  shows the detection of two events that violate the 1:00 AM and 14:00 PM periodicity. 
         [0003]    To mine periodicity in an event, systems have to face real-world challenges of inherently complicated periodic behaviors and imperfect data collection problem. Specifically, the hidden temporal periodic behaviors could be oscillating and noisy. Traditional periodicity analysis methods, such as Fourier transform (FFT) and auto-correlation usually require the data to be evenly sampled, that is, there is an observation at every timestamp. Even though some extensions of Fourier transform have been proposed to handle uneven data samples, they are still not applicable to the case with very low sampling rate. 
         [0004]    Some methods apply statistical analysis techniques on a single time series of one event type. A probabilistic measure for periodicity, ePeriodicity, has been used to detect periods. This is done by applying different potential periodicity length T to segment the time series into multiple length-T time series, overlay those time series, and report as the periodicity the value T that have the largest clustering behavior measured by an event conditional probability. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]      FIG. 1  shows an exemplary periodic event example mined from IT system logs. 
           [0006]      FIG. 2  shows exemplary system anomalies detected through the log event periodicity checking. 
           [0007]      FIG. 3  shows an exemplary Category Model Based Periodicity Analysis (CMBPA) process. 
           [0008]      FIG. 4  shows an exemplary CMBPA logs-to-time series conversion procedure. 
           [0009]      FIG. 5  shows an exemplary CMBPA time series data for the logs in  FIG. 1 . 
           [0010]      FIG. 5  shows an exemplary CMBPA time series data for the logs in  FIG. 1 . 
           [0011]      FIG. 7  shows an exemplary category model output for the logs in  FIG. 1 . 
           [0012]      FIG. 8  shows an exemplary CMBPA logs-to-time series conversion procedure. 
           [0013]      FIG. 9  shows an exemplary CMBPA category model testing procedure. 
           [0014]      FIG. 10  shows an exemplary Category model testing output for the logs in  FIG. 2 . 
           [0015]      FIG. 11  shows exemplary hardware for  FIG. 1 . 
       
    
    
     SUMMARY 
       [0016]    Systems and methods are disclosed for detecting periodic event behaviors from machine generated logging by: capturing heterogeneous log messages, each log message including a time stamp and text content with one or more fields; transforming the text content into a set of time series data; during a training phase, analyzing the set of time series data and building a category model for each periodic event type in heterogeneous logs; and during live operation, applying the category model to a stream of time series data from live heterogeneous log messages and generating a flag on a time series data point violating the category model and generating corresponding log messages. 
         [0017]    In another aspect, a system includes a mechanical actuator; a digitizer coupled to the actuator to log data; a module for detecting periodic event behaviors from machine generated logging, including code for: capturing heterogeneous log messages, each log message including a time stamp and text content with one or more fields; transforming the text content into a set of time series data; during a training phase, analyzing the set of time series data and building a category model for each periodic event type in heterogeneous logs; and during live operation, applying the category model to a stream of time series data from live heterogeneous log messages and generating a flag on a time series data point violating the category model and generating corresponding log messages. 
         [0018]    In implementations, the actuator can be a motor or an engine that generates periodic event behaviors that need monitoring for performance, reliability, or maintenance purposes, for example. 
         [0019]    Advantages of the system may include one or more of the following. Instead of treating the input data as a single time series, the invention transforms heterogeneous logs into multiple time series, and provides a fast and robust mechanism to discover potentially multiple periods existing in each time series. The periodicity discovery mechanism is based on a category model with the parameters of fitness score, category center and error bounds. The system also provides linear methods to build the category model and test periodicity anomalies based on the category model. The system significantly reduces the complexity of finding statistically periodic event patterns in huge amount of heterogeneous log, even when prior knowledge about the system might not be available. By integrating advanced text mining and time series analysis in a novel way, the present principles construct an automatic periodic pattern mining method for heterogeneous logs in a principled way, and allow faster operation and system updates. 
       DESCRIPTION 
       [0020]      FIG. 3  shows one exemplary process called Category Model Based Periodicity Analysis (CMBPA) for heterogeneous logs. The process operates as follows:
         101 . Heterogeneous log collection for training. This step takes heterogeneous logs from arbitrary/unknown systems or applications. A log message consists of a time stamp and the text content with one or multiple fields.     102 . Logs to time series conversion. This step transforms original training text logs into a set of time series data.     103 . Category model generation. This step analyzes the set of time series output by  102 , and builds a category model for each periodic event type in heterogeneous logs.     104 . Heterogeneous log collection for testing. This step takes heterogeneous logs collected from the same system in  101  for periodicity behavior testing. A log message consists of a time stamp and the text content with one or multiple fields. The testing data may come in one batch as a log file, or come in a stream process.     105 . Logs to time series conversion. This step transforms original testing text logs into a set of time series data.     106 . Category model checking. This step analyzes the set of time series data output by  102  based on the corresponding category models output by  103 , and outputs alarms on any time series data point violating the category model and the corresponding log messages.     107 . Log management applications. This step applies a set of management applications onto the heterogeneous logs from  101  based on the category models output by  103 , or onto the heterogeneous logs from  104  based on the category model checking output by  106 . For example, log based fault management can be applied by discovering missing log messages not shown up on expected time points, or detecting abnormal log messages shown up on unexpected time points output by  106 .       
 
         [0028]      FIG. 4  shows the details of the CMBPA logs-to-time series conversion procedure as follows:
         201 . Log format recognition. A set of log formats matching the training logs can be provided by users directly, or generated automatically by a format recognition procedure on all the heterogeneous logs as below:
             201 . a —Taking arbitrary heterogeneous logs (step  101 ), a tokenization is processed is so as to generate semantically meaningful tokens from logs. After the heterogeneous logs are tokenized, a similarity measurement on heterogeneous logs is applied. This similarity measurement leverages both the log layout information and log content information, and it is specially tailored to arbitrary heterogeneous logs. Once the similarities among logs are captured, a log hierarchical clustering algorithm can be applied so as to generate and output a log cluster hierarchy. CMPBA allows users to plug in their favorite hierarchical clustering algorithms.     201 . b —Once the log cluster hierarchies are received, within each cluster that on the lowest level in the log cluster hierarchy, the logs are aligned. The log alignment is designed to preserve the unknown layouts of heterogeneous logs so as to help log pattern recognition in the following steps. Once the logs are aligned, log motif discovery is conducted so as to find the most representative layouts and log fields. The following step is pattern recognition from such motifs. First, fields such as time stamps, Internet Protocol (IP) addresses and universal resource locators (URLs) are recognized. Second, other fields which are highly conserved in the logs are recognized and organized in a data structure in the cluster hierarchy. Note that the above log motif discovery and pattern recognition are first done in the lowest level of the log hierarchy. After that, all the information is back propagated up to higher levels in the hierarchy, and fused with their local patterns to provide format pattern representations from the logs.         202 . Per-format time series generation. For each unique format in the clustering hierarchy, following is the time series generation procedure on all the heterogeneous logs:     202 . a —find all log messages that match the pattern format (e.g., through a regular expression testing).     202 . b —order those matched messages based on the time stamps in them. Assume there are K ordered messages, denote their time stamps as X={X1, X2,. . . , XK}.     202 . c —output the inter-arrival time series as Y={Y1=X2−X1, Y2=X3−X2, . . . , YK−1=XK−XK−1}.       
 
         [0036]    For example,  FIG. 5  shows a part of the time series for the logs in  FIG. 1  matched on the log format “{%TIME_STAMP} (%IP_ADDRESS) COMMIT”
       Y1=46800000   Y2=39600000   Y3=46800000   Y4=39600000   Y5=46800000   Y6=39600000   Y7=46800000   Y8=39600000   . . .       
 
         [0046]      FIG. 6  shows the details of the CMBPA category model generation procedure. For each log format Y with the inter-arrival time series Y={Y1, Y2, . . . , YK−1} output from  202 , following is the category model generation procedure to decide if it contains a periodic event pattern, and in case of yes, the detailed periodicity model: 
         [0047]      301 . estimate categories. counter the appearance times of unique values in the time series Y, sort those unique values in an increasing order, and record them in an ordered list C estimated =[C 1 , C 2 , . . . C u } and N estimated =[N 1 , N 2 , . . . N u },where u is the number of the unique values, and N i  is the appearance time of the unique value C i  in Y. 
         [0048]      302 . cluster estimated categories. From the estimated category values in C estimated , we will cluster them based on their distance given a category distance ratio σ (e.g., σ=0.01). 
         [0049]      302 . a —calculate the distance of each value in C estimated  to its next neighbor in the sorted list: D estimated =[d 1 =/C 2 −C 1 |, d 2 =/C 3 −C 2 |, . . . d u−1 =/C u −C u−1 |}. Let d max =max{d i , 1≦i≦u−1}. 
         [0050]      302 . b —initialize a list d index ={ }. From i=1 to (u−1), if the distance value d i  satisfies that (d i /d max )≦ σ,i is added into the list D index =D index +{i}. 
         [0051]      302 . c —if the list D index  is empty, there is no category model found for the time series Y. 
         [0052]      302 . d —if the list D index  is not empty, initialize the final category model as a list C final ={ }, and set k=1. From i=1 to u: 
         [0053]      302 . d . 1 —if i is not in D index  and C final , creates a new category list C′ k ={C i }; add it into the final category model C final =C final +{C′ k },k=k+1; 
         [0054]      302 . d . 2 —if i is in D index , finds the longest consecutive integer sequence (i, i+1, i+2, . . . , i+c) in D index , creates a new category list C′ k ={C i , C i+1 , . . . , C i+c+1 }, and add it into the final category model C final =C final +{C′ k }, k=k+1.
         303 . model categories If there is no category model, stops here. Otherwise, for the final category model C final ={C′ 1 ,C′ 2 , . . . , C′ f }, the model parameter (Center(C′ k ), Error(C′ k )) is calculated for each C′ k ={C i , C i+1 , . . . , C i+j }, 1≦k≦F, and a fitness score is calculated for the whole category model C final :     303 . a —Center(C′ k )=C m , where m is Max{N m , i≦m≦i+j}. i.e., we choose the unique value with the largest appearance time in Y as the cluster center of the category C′ k .     303 . b —Error(C′ k )=max{|C m −Center(C′ k )|, i≦m≦i+j}. i.e., we choose the error bound as the largest distance of the unique values in C′ k  to its center.     303 . c —Size(C′ k )=Σ m:i , . . . , i+j N m ; average_size(C final )=(K−1)/F; fitness(C final )=min{Size(C′ k ), 1≦k≦F}average_size(C final ).       
 
         [0059]    For example,  FIG. 7  shows two categories are generated for the logs in  FIG. 1 : one with the Center value 3.96E7 (11-hour interval) &amp; error bound 0, and another with the Center value 4.68E7 (13-hour interval) &amp; error bound 0; the fitness score for the whole category model is 0.9629629629629629. 
         [0060]      FIG. 8  shows the details of the CMBPA logs-to-time series conversion procedure for the testing procedure:
         501 . Log format selection. From the set of log formats generated in  201 , only the formats with category models are selected for the rest of the testing procedure.     502 . Per-message time stamp recognition. For each log message i in the testing data,   find the log format f i  for that it matches (e.g., through a regular expression testing), and extract the time stamp t i  for i. If i does not find a matching format, it will be filtered out for the rest of the testing procedure.       
 
         [0064]      FIG. 9  shows the details of the CMBPA category model testing procedure. For each log message i having a matching format fi in  105 , following is the category model testing procedure to decide if it violates the periodicity behavior described by fi&#39;s category model and an anomaly should be reported:
         601 . find the category. Let T be the inter-arrival time of log i and the previous log matching format f i . For format f i &#39;s category model C f ={C′ 1 , C′ 2 , . . . , C′ F }, find C′ m Center (C′ m ) = min{/T−Center(C′ j )|, , 1≦j≦F}.     602 . check the error bound. If |T−Center(C′ m ))|&gt;Error(C′ m )), log message i violates the periodicity behavior described by f i &#39;s category model. Otherwise it does not violate any periodicity behavior.     603 . report an anomaly. If log message i violates the periodicity behavior, the category model fitness score is checked; if it is larger than a threshold α (e.g., 0.5), an anomaly will be reported; otherwise, an anomaly will not be reported until κ (e.g., 2) consecutive logs matching format f i  including the log message i violate the periodicity behavior.       
 
         [0068]      FIG. 10  shows the three periodicity anomalies detected from the logs in  FIG. 2  based on the periodicity model learnt from the logs in  FIG. 1 . 
         [0069]    Referring to the drawings in which like numerals represent the same or similar elements and initially to  FIG. 11 , a block diagram describing an exemplary processing system  100  to which the present principles may be applied is shown, according to an embodiment of the present principles. The processing system  100  includes at least one processor (CPU)  104  operatively coupled to other components via a system bus  102 . A cache  106 , a Read Only Memory (ROM)  108 , a Random Access Memory (RAM)  110 , an input/output (I/O) adapter  120 , a sound adapter  130 , a network adapter  140 , a user interface adapter  150 , and a display adapter  160 , are operatively coupled to the system bus  102 . 
         [0070]    A first storage device  122  and a second storage device  124  are operatively coupled to a system bus  102  by the I/O adapter  120 . The storage devices  122  and  124  can be any of a disk storage device (e.g., a magnetic or optical disk storage device), a solid state magnetic device, and so forth. The storage devices  122  and  124  can be the same type of storage device or different types of storage devices. 
         [0071]    A speaker  132  is operatively coupled to the system bus  102  by the sound adapter  130 . A transceiver  142  is operatively coupled to the system bus  102  by a network adapter  140 . A display device  162  is operatively coupled to the system bus  102  by a display adapter  160 . A first user input device  152 , a second user input device  154 , and a third user input device  156  are operatively coupled to the system bus  102  by a user interface adapter  150 . The user input devices  152 ,  154 , and  156  can be any of a keyboard, a mouse, a keypad, an image capture device, a motion sensing device, a microphone, a device incorporating the functionality of at least two of the preceding devices, and so forth. Of course, other types of input devices can also be used while maintaining the spirit of the present principles. The user input devices  152 ,  154 , and  156  can be the same type of user input device or different types of user input devices. The user input devices  152 ,  154 , and  156  are used to input and output information to and from the system  100 . 
         [0072]    Of course, the processing system  100  may also include other elements (not shown), as readily contemplated by one of skill in the art, as well as omit certain elements. For example, various other input devices and/or output devices can be included in the processing system  100 , depending upon the particular implementation of the same, as readily understood by one of ordinary skill in the art. For example, various types of wireless and/or wired input and/or output devices can be used. Moreover, additional processors, controllers, memories, and so forth, in various configurations, can also be utilized as readily appreciated by one of ordinary skill in the art. These and other variations of the processing system  100  are readily contemplated by one of ordinary skill in the art given the teachings of the present principles provided herein. 
         [0073]    It should be understood that embodiments described herein may be entirely hardware, or may include both hardware and software elements which includes, but is not limited to, firmware, resident software, microcode, etc. 
         [0074]    Embodiments may include a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. A computer-usable or computer readable medium may include any apparatus that stores, communicates, propagates, or transports the program for use by or in connection with the instruction execution system, apparatus, or device. The medium can be magnetic, optical, electronic, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. The medium may include a computer-readable storage medium such as a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk, etc. 
         [0075]    A data processing system suitable for storing and/or executing program code may include at least one processor, e.g., a hardware processor, coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code to reduce the number of times code is retrieved from bulk storage during execution. Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc.) may be coupled to the system either directly or through intervening I/O controllers. 
         [0076]    The foregoing is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that those skilled in the art may implement various modifications without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention.