Anomaly detection at the level of run time data structures

A useful embodiment of the invention is directed to a method associated with a computer program comprising one or more basic blocks, wherein the program defines and uses multiple data structures, such as the list of all customers of a bank along with their account information. The method includes identifying one or more invariants, wherein each invariant is associated with one of the data structures. The method further includes determining at specified times whether an invariant has been violated. Responsive to detecting a violation of one of the invariants, the detected violation is flagged as an anomaly.

BACKGROUND

The invention disclosed and claimed herein generally pertains to a method of anomaly detection at the code level of a computer program. More particularly, the invention pertains to a method of the above type, wherein invariants associated with data structures of the program's concrete state are used to detect anomalies.

2. Description of the Related Art

Anomaly detection is the act of detecting patterns in a given data set that do not conform to an established normal behavior. Anomaly detection is a highly active area of research and development in academia as well as in industry, and breaks into two subareas. One subarea is rule-based anomaly detection, which is the act of discovering anomalies based on a set of rules defining normal behavior. The other subarea is statistical anomaly detection, which uses learning techniques to automatically infer a set of “likely invariants” that characterize the normal behavior of the software system. In this case, there is no need for a user provided specification of the normal behavior. Instead, the anomaly detection system needs to be trained prior to its deployment.

A recent and significant development in the area of statistical anomaly detection, published in a paper of Cova et al., referred to herein as the “Swaddler approach”, suggests that anomalies can be discovered at the level of program code, rather than at the external interface of a program, i.e. input payloads. This is achieved by instrumenting the subject program, and establishing likely invariants at each basic block of the program visited during the training phase. These invariants are encoded as a model, assigning a probability value to a feature of the state variable or a set of state variables associated with a block that is about to be executed. This value reflects the probability of occurrence of a given feature value with regards to an established model of “normality”.

While the current state of the art as represented by the Swaddler approach has been shown, quite convincingly, to be of practical value, it is still characterized by a number of limitations. These include issues pertaining to expressiveness, portability, overhead and accuracy. In regard to expressiveness, Swaddler cannot capture invariants across more than one control flow. Regarding portability, letting each basic block in the program be anomaly aware has the undesirable effect of making the detection system highly sensitive to code changes. Regarding overhead, performing anomaly checks at each basic block is highly expensive. It is difficult to see how the Swaddler solution can scale to enterprise applications comprising on the order of hundreds of millions of lines of code, including their library dependencies.

Finally, in regard to accuracy, a further negative byproduct of testing for anomalies at each basic block is that the system is more likely to issue false alarms. The more checks there are, the more likely it is for statistical reasoning to come to the wrong conclusion.

SUMMARY

Embodiments of the invention prescribe that anomaly detection is to be performed with regard to the data of a computer program, rather than the program control. Instead of associating likely invariants with program points, embodiments of the invention associate invariants with the data structures governing the concrete or semantic state of the program. As used herein, an invariant is a specific rule, condition or standard, such as a particular numerical value, which is associated with given data structure of a program and indicates normal operation of the program. The invariant is broken or violated, if the specific rule or standard is deviated from, or is not adhered to, during computer runtime.

One useful embodiment of the invention is directed to a computer implemented method associated with a computer program comprising one or more basic blocks, wherein the program defines and uses multiple data structures. An example of such a data structure could be a list of all customers of a bank along with their account information, but embodiments of the invention are by no means limited thereto. The method includes identifying one or more invariants, wherein each invariant is associated with one of the concrete data structures. The method further includes determining at specified times whether an invariant has been violated. Responsive to detecting a violation of one of the invariants, the detected violation is flagged as an anomaly.

DETAILED DESCRIPTION

Referring toFIG. 1, there are shown basic blocks102-108, collectively representing basic blocks1-N of a computer program100. For purposes of illustration program100may comprise a program for enabling a user to perform various bank transactions or the like, but the invention is by no means limited thereto. The basic blocks102-108also have associated concrete data structures (CDS)110-116, respectively.

FIG. 1further shows logical data structures (LDS), which correspond to and can also be mapped to each of the concrete data structures110-116, as described hereinafter in further detail. More particularly, logical data structures118-124correspond to concrete data structures110-116, respectively. A tool130is provided to manage and monitor activities and operations of basic blocks102-108and logical data structures118-124.

In order to implement embodiments of the invention,FIG. 1is provided with a rule information component126, which contains a rule specification128. In accordance with the invention, it has been recognized that certain data structures associated with the runtime state of a program can indicate a condition or state considered to be normal. More specifically, certain invariants associated with the data structure can be determined, which correspond to normal conditions. Thus, invariants in the form of invariant rules are included in rule specification128. By deriving suitable invariants for specific tasks or operations, and then monitoring the status of respective invariants at runtimes, an anomaly can be detected when one or more invariants are found to be broken or violated.

As an illustrative example for the bank transactions program100, a useful invariant rule is a rule that the user of a particular account performs at most n operations per hour. The value of n for the particular user account is determined by an initial training phase, as described hereinafter in further detail. If the value of n is then found to be exceeded during subsequent use of the program, for the particular account, an anomaly is flagged for the account, or an alarm is triggered.

It will be appreciated that the above exemplary invariant rule requires the performance of two specific tasks, namely, identifying the particular user account, and counting the number of operations per hour for that account. Each of the invariant rules contained in rule specification128, together with its related tasks, corresponds and is mapped to a logical data structure118-124or the like. Management tool130is operable to read rules specification128, in order to identify the logical data structure to which respective invariant rules correspond.FIG. 1shows the two tasks of the above invariant rule being directed from specification128to logical data structure120.

Referring further toFIG. 1, logical data structure120is mapped to a corresponding concrete data structure112. Concrete data structure112is associated with basic block104, which performs the above operation of counting operations per unit time for the particular account. In one useful embodiment, the mapping between the logical data structure120and concrete data structure112is carried out by first applying an abstraction to the concrete data structure, in accordance with the Hawkeye technique, disclosed in the publication “Hawkeye: effective discovery of dataflow impediments to parallelization” (Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications; 2011; pages 207-224; ACM New York, N.Y., USA).

As a further step in preparing the embodiment ofFIG. 1for deployment or use, it is necessary to provide instrumentation for concrete data structure112of basic block104. This is done to monitor the above invariant during operation of basic block104, in order to detect any violation of the invariant and provide notice thereof. Usefully, the instrumentation is carried out by management tool130, which identifies certain locations at concrete data structure112, such as locations where concrete data structure is being added to or modified. Tool130then inserts instrumentation code at such locations. The instrumentation of concrete data structure112, of basic block104, is represented inFIG. 1as instrumentation132.

FIG. 1further shows instrumentation132of concrete data structure112mapped back to logical data structure120, as instrumentation134. This information identifies the particular version of basic block104, the instrumentation codes, and their respective locations in basic block104.

After carrying out the above deployment preparation steps, the instrumented blocks must be trained in accordance with the above invariant rule. Thus, a training function136is provided, which receives training data138. The training data may comprise, for example, sets of data that are typical of the data processed by the basic blocks of program100, for a particular user. The training data could also include data recently processed by the particular user. The training data is run through the basic blocks of program100, and instrumentation in respective blocks records results of processing the training data. For example, the results may include training data acquired by instrumentation132, which shows that the value n for the above invariant rule does not exceed a specified value for normal operation. The collective training results140are delivered to management tool130, and are also mapped back to logical data structure120. The management tool130may then use the training data to set the value of n, for the invariant rule associated with basic block104, to the specified value.

After completing the training phase, program100may be used or deployed in its actual environment of operations. If an invariant is then violated during runtime, for example the number of operations of the particular account per hour exceeds the specified value, notice is provided of a possible anomaly. Examples of other invariant rules for detecting anomalies include a user's balance does not change by more than x in a single operation; a user's ID does not contain characters such as “<” or “>”; and the distribution of operations by a user, e.g., checking the balance, depositing money, and withdrawing money, has a prespecified shape.

The embodiment ofFIG. 1provides a number of important benefits. For example, the instrumentation and training of concrete data structure112may be for Version 1 of basic block104. Accordingly, the instrumentation and training data for such version is mapped to corresponding logical data structure120, as described above. If basic block104is then updated to Version 2, the instrumentation and training data mapped to logical data structure120can be remapped back to concrete data structure112, to update the new version of basic block104. Thus, the embodiment ofFIG. 1significantly enhances the feature of portability. As a further advantage, if the program includes multiple control flows, embodiments of the invention could detect anomalies across multiple control flows. An example of multiple control flows could be a customer performing60transactions within one hour, or two consecutive transactions from different geographical locations.

FIG. 1shows further that basic block106is provided with instrumentation142, which pertains to a further invariant for use in detecting anomalies. Concrete data structure114of basic block106maps instrumentation142to corresponding logical data structure122, as instrumentation144. However, it is seen that instrumentation is not needed at other basic blocks of computer100, such as blocks102and108. By avoiding the need for instrumentation at all basic blocks of the program, embodiments of the invention significantly reduce overhead. Also, accuracy is improved, since it is not necessary to collect data from basic blocks that are irrelevant for anomaly detection.

Referring toFIG. 2, there are shown steps for a method comprising an embodiment of the invention. At step202a rule defining an invariant, for use in detecting an anomaly in a specified computer program, is selected. Such invariant rule is exemplified by the rule described above, wherein a particular account performs at most n operations per hour. At step204the invariant rule is mapped to a corresponding logical data structure, and is mapped at step206from the logical data structure to a concrete data structure of a basic block of the computer.

At step208, the basic block is instrumented as described above, to implement and monitor the invariant. At step210a training procedure is carried out, to determine standards for the invariant that represent normal program operation. At step212, instrumentation and training information is mapped from the concrete data structure to the logical data structure.

Step214is a decision step, which determines whether another invariant rule is needed for the program. If so, steps202-212are repeated. Otherwise, the method proceeds to step216. At step216a violation of the invariant is used to provide notice of an anomaly, when the program is running. Violation of invariants is usefully monitored continually or at specified intervals, during runtimes. Step218responds to modification of the basic block, to map instrumentation and training information back from the logical data structure to instrument and train the modified basic block.

Referring toFIG. 3, a block diagram of a data processing system is depicted, which may be used in implementing embodiments of the invention. In this illustrative example, data processing system300includes communications fabric302, which provides communications between processor unit304, memory306, persistent storage308, communications unit310, input/output (I/O) unit312, and display314.

Memory306and persistent storage308are examples of storage devices316. A storage device is any piece of hardware that is capable of storing information, such as, for example, without limitation, data, program code in functional form, and/or other suitable information either on a temporary basis and/or a permanent basis. Storage devices316may also be referred to as computer-readable storage devices in these examples. Memory306, in these examples, may be, for example, a random access memory or any other suitable volatile or non-volatile storage device. Persistent storage308may take various forms, depending on the particular implementation.

For example, persistent storage308may contain one or more components or devices. For example, persistent storage308may be a hard drive, a flash memory, a rewritable optical disk, a rewritable magnetic tape, or some combination of the above. The media used by persistent storage308also may be removable. For example, a removable hard drive may be used for persistent storage308.

Communications unit310, in these examples, provides for communications with other data processing systems or devices. In these examples, communications unit310is a network interface card. Communications unit310may provide communications through the use of either or both physical and wireless communications links.

Input/output unit312allows for input and output of data with other devices that may be connected to data processing system300. For example, input/output unit312may provide a connection for user input through a keyboard, a mouse, and/or some other suitable input device. Further, input/output unit312may send output to a printer. Display314provides a mechanism to display information to a user.

Instructions for the operating system, applications, and/or programs may be located in storage devices316, which are in communication with processor unit304through communications fabric302. In these illustrative examples, the instructions are in a functional form on persistent storage308. These instructions may be loaded into memory306for execution by processor unit304. The processes of the different embodiments may be performed by processor unit304using computer implemented instructions, which may be located in a memory, such as memory306.

These instructions are referred to as program code, computer-usable program code, or computer-readable program code that may be read and executed by a processor in processor unit304. The program code in the different embodiments may be embodied on different physical or computer-readable storage media, such as memory306or persistent storage308.

Program code318is located in a functional form on computer-readable media320that is selectively removable and may be loaded onto or transferred to data processing system300for execution by processor unit304. Program code318and computer-readable media320form computer program product322in these examples. In one example, computer-readable media320may be computer-readable storage media324. Computer-readable storage media324may include, for example, an optical or magnetic disk that is inserted or placed into a drive or other device that is part of persistent storage308for transfer onto a storage device, such as a hard drive, that is part of persistent storage308. Computer-readable storage media324also may take the form of a persistent storage, such as a hard drive, a thumb drive, or a flash memory, that is connected to data processing system300. In some instances, computer-readable storage media324may not be removable from data processing system300.

In still another illustrative example, processor unit304may be implemented using a combination of processors found in computers and hardware units. Processor unit304may have a number of hardware units and a number of processors that are configured to run program code318. With this depicted example, some of the processes may be implemented in the number of hardware units, while other processes may be implemented in the number of processors.

As another example, a storage device in data processing system300is any hardware apparatus that may store data. Memory306, persistent storage308, and computer-readable media320are examples of storage devices in a tangible form.