Automatic model evolution

A system includes a storage medium. The storage medium includes a model generation module that generates a candidate model based on a discrepancy and a model template. The storage medium also includes a model evaluation module that selectively updates a system model based on the candidate model.

BACKGROUND

The present invention relates to modeling of software systems, and more specifically, to automatic model evolution.

Transactions processed by distributed software applications can be difficult to monitor. Monitoring typically utilizes a precise model of the software system indicating how a transaction propagates through various states. When the software system changes, or is outdated, incomplete, or error-prone the models need to be updated. Manual updating of system models can be time-consuming.

SUMMARY

According to one embodiment of the present invention, a system includes a storage medium that includes a model generation module that generates a candidate model based on a discrepancy and a model template, and a model evaluation module that selectively updates a system model based on the candidate model.

DETAILED DESCRIPTION

Turning now to the drawings in greater detail, it will be seen that inFIG. 1an exemplary computing system includes a model evolution system in accordance with the present disclosure. The computing system100is shown to include a computer101. As can be appreciated, the computing system100can include any computing device, including but not limited to, a desktop computer, a laptop, a server, a portable handheld device, or any other electronic device that includes a memory and processor. For ease of the discussion, the disclosure will be discussed in the context of the computer101.

The computer101is shown to include a processor102, memory104coupled to a memory controller106, one or more input and/or output (I/O) devices108,110(or peripherals) that are communicatively coupled via a local input/output controller112, and a display controller114coupled to a display116. In an exemplary embodiment, a conventional keyboard122and mouse124can be coupled to the input/output controller112. In an exemplary embodiment, the computing system100can further include a network interface118for coupling to a network120. The network120transmits and receives data between the computer101and external systems.

In various embodiments, the memory104stores instructions that can be performed by the processor102. The instructions stored in memory104may include one or more separate programs, each of which comprises an ordered listing of executable instructions for implementing logical functions. In the example ofFIG. 1, the instructions stored in the memory104include a suitable operating system (OS)126. The operating system126essentially controls the performance of other computer programs and provides scheduling, input-output control, file and data management, memory management, and communication control and related services.

When the computer101is in operation, the processor102is configured to execute the instructions stored within the memory104, to communicate data to and from the memory104, and to generally control operations of the computer101pursuant to the instructions. The processor102can be any custom made or commercially available processor, a central processing unit (CPU), an auxiliary processor among several processors associated with the computer101, a semiconductor based microprocessor (in the form of a microchip or chip set), a macroprocessor, or generally any device for executing instructions.

The processor102executes the instructions of a model evolution system (MES)128of the present disclosure. In various embodiments, the model evolution system128of the present disclosure is stored in the memory104(as shown), is run from a portable storage device (e.g., CD-ROM, Diskette, FlashDrive, etc.) (not shown), and/or is run from a remote location, such as from a central server (not shown).

Generally speaking, the model evolution system128manages the evolution of system models by automatically identifying changes and updating the model based on the changes. For example, the model evolution system128monitors computer transactions to determine discrepancies in log output. When discrepancies are found, the model evolution system128uses one or more templates to create candidate replacement models. If the candidate replacement models meet specified goodness of fit criteria, then the existing model can be updated with the changes from the candidate replacement model.

Turning now toFIG. 2, the model evolution system128is shown in more detail in accordance with an exemplary embodiment. The model evolution system128includes one or more sub-modules and datastores. As can be appreciated, the sub-modules can be implemented as software, hardware, firmware, a combination thereof, and/or other suitable components that provide the described functionality. As can further be appreciated, the sub-modules shown inFIG. 2can be combined and/or further partitioned to similarly update evaluation models automatically. In various embodiments, the model evolution system128includes a monitoring module130, a model generation module132, a model evaluation module134, a model datastore136, and a templates datastore138.

The monitoring module130receives as input log data140. The log data140can be generated when one or more operations of a software system are performed. The software system can include one or more software applications that when performed carry out a transaction. For example, the transaction can be a computerized purchase, trade, etc. Based on the log data140, the monitoring module130determines any discrepancies between the log data140and a model141of the software system. The discrepancies may be due to new perspectives of a user of the model and/or newly-emerging behaviors of system transactions. The monitoring module130generates discrepancy data142based on the discrepancies. The discrepancy data142can identify a particular feature of the model that is different and details on how that feature is different. The model141can include features such as states and transitions and can be predefined and stored in a model datastore136.

The model generation module132receives as input the discrepancy data142. Based on the discrepancy data142, the model generation module132generates a candidate model144of the system using a set of meta-models, or templates146. The process of generating the candidate model144may include adding or removing states and/or transitions and/or changing the definitions of the states.

A template146includes, for example, a set of rules for updating a model given the differences as well as a computerized agent for executing the rules. Additionally, the template146may make decisions based on past history, as will be discussed in more detail below. For example, as shown inFIG. 3, the template146can include model generation implementation logic156, goodness of fit measurement logic154, confidence of goodness of fit measurement logic152, and decision threshold definitions150.

In various embodiments, the model generation implementation logic156may comprise rules to create a new state for the model, such as grouping log data based on the number of words they contain, tokenizing log data, and clustering log data using a Hamming-like distance between log data. For example, the tokenization of log data may split a log entry into words separated by empty space. In another example, the Hamming distance of two strings with the same number of tokens (i.e., words) may be a string of the same length marking the matching and mismatching token. For example, the log entries “Server 192.168.0.1 initializes port5” and “Server 192.168.0.2 initializes port7” may be mapped to the same model state “Server * initializes port *” when the Hamming distance of at least two is allowed for log data comprising of five tokens. Alternatively, each of the log entries may be in different clusters if the maximum Hamming distance allowed per cluster is either zero or one.

In various embodiments, the model generation implementation logic156may specify that each state be eventually represented using a regular expression syntax (such is the case with the string “String * initializes port *”). Log data entries (i.e., log records) will be compared against the regular expression representations of states and, when matched, the log record can be mapped to the state corresponding to the matched regular expression.

In various embodiments, the model generation implementation logic156may also comprise rules for ignoring newly created states, if for example, a newly created state can be found in the datastore of model states to be excluded from the evolution of the model (black-listed model states).

In various embodiments, the goodness of fit measurement logic154may include a process for collecting figures of merit associated with a candidate model that could result from a newly generated state, a newly generate transition between states, an updated parameter describing those, such as the likelihood of a particular state transition. Examples of such figures of merit may include, but are not limited to, a fraction of correctly matched log records, and an average likelihood of log record transitions or a fraction of correctly predicted log record transitions under the modeled state transition probabilities. Other figures of merit may include, but are not limited to, a count of the state appearances, an average variance of time between successive appearances of the state, a number of times two states follow each other, an average and variance of time between successive occurrences of transitions between the same two states, etc.

In various embodiments, the confidence of goodness of fit measurement logic152may comprise rules that describe acceptable error bounds on the measured figures of merit for the goodness of fit, or a minimum required number of new log records required for each state and/or pairs of log records for newly observed state transitions and so on. The combination of these two pieces of logic results in producing new candidate model elements (e.g., the state models, state transition, and state transition parameters, such as the frequency of specific transition), and/or model elements that satisfy prescribed confidence (or, quality) levels so that reliable model decision updates can be made.

In various embodiments, the decision threshold definitions150may provide a set of thresholds for each goodness of fit metric. For example, it may provide a lower bound and an upper bound. If the goodness of fit metric is below the lower bound, the new model can be discarded. If the goodness of fit metric is above the upper bound, the new model can be adopted. Otherwise, both models can be evaluated based on additional log records.

With reference back toFIG. 2, the model evaluation module134receives as input the candidate model144. The model evaluation module134determines whether the candidate model144should be accepted as a new model. The model evaluation module134can make the determination based on information147entered by a user or can be made automatically based on rules specified in the template146. If the candidate model144is accepted, then the new model is stored as an updated model148in the model datastore136for subsequent use. If the candidate model144is rejected, then the original model141will continue to be used.

In various embodiments, before a decision is reached, the model evaluation module134can provide the option of testing the candidate model144by deploying it to a development/test monitoring application (as opposed to the real production application) and having the application run with both the original model141and the candidate model144in parallel on the same transaction data used in real monitoring. This is done to maintain the current transaction monitoring process while also testing the “goodness of fit” of the candidate model144in real-time. After a set period and/or particular event occurrences, the test monitoring application can send a notification with information about the quality of both models141,144, and the decision-making entity can then make a final decision to accept/reject the candidate model144or to redeploy the candidate model144back to the test monitor to further measure its goodness of fit (e.g., such redeployment can happen over multiple iterations).

In various embodiments, a history of model changes can be stored and used at different levels. Fore example, in various embodiments, history indicating model discrepancies intentionally ignored in the past can be used to suppress future notifications on the same problem. In various embodiments, the history can be used to adjust decision thresholds in the template based on past decisions and/or the past measurements in the current decision-making process. For example, it may raise the acceptance threshold to prevent model fluctuation, or lower the threshold to reduce decision time.

Turning now toFIG. 4and with continued reference toFIG. 2, a flowchart illustrates a model evolution method that can be performed by model evolution system ofFIG. 2in accordance with an exemplary embodiment. As can be appreciated in light of the disclosure, the order of operation within the method is not limited to the sequential performance as illustrated inFIG. 4, but may be performed in one or more varying orders as applicable and in accordance with the present disclosure. As can be appreciated, one or more steps can be added or deleted from the method without altering the spirit of the method.

In various embodiments, the method can run continually, for example, during operation of the computer101or be schedule to run based on time intervals or predetermined events.

In one example, the method may begin at block200. The transactions are monitored based on the log data140and the system model141at block210. If discrepancies exist between the model141and the log data140at220, the method continues at block230with generating a candidate model144based on the model templates146. Otherwise, the method continues with monitoring the transactions at210.

Once the candidate model144has been generated at230, the candidate model144is evaluated for a goodness of fit, based on the model templates146at240. If the candidate model144passes a goodness of fitness test, it is determined whether the changes indicated by the candidate model144should be accepted at250. If the changes should be accepted at250, the original model141is updated with the changes and stored to the model datastore136at260. Otherwise, the changes are ignored and the method continues with monitoring the transactions at210.