Anomaly detection at the level of run time data structures

Abstract

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.

What is claimed is: 
     
         1 . In association with a computer program comprising one or more basic blocks, and concrete data structures that each pertains to a basic block, a computer program product executable in a recordable storage medium comprising:
 instructions for identifying one or more invariants, wherein each invariant is associated with one of the concrete data structures;   instructions for determining at specified times whether an invariant has been violated; and   instructions responsive to detecting a violation of one of the invariants, for flagging the detected violation as an anomaly.   
     
     
         2 . The computer program product of  claim 1 , wherein:
 the computer program comprising one or more basic blocks includes multiple control flows, and at least one invariant violation comprising an anomaly is detected across two or more control flows.   
     
     
         3 . The computer program product of  claim 1 , wherein:
 each invariant comprises a selected invariant rule, wherein each invariant rule corresponds to a logical data structure that is mapped to the concrete data structure of a basic block.   
     
     
         4 . The computer program product of  claim 1 , wherein:
 instrumentation code, for use in detecting violation of one or more invariants, is selectively inserted into each concrete data structure associated with one or more invariants.   
     
     
         5 . The computer program product of  claim 4 , wherein:
 a training procedure is applied to each basic block having a concrete data structure associated with one or more invariants, in order to determine standards that define violations of said invariants.   
     
     
         6 . The computer program product of  claim 5 , wherein:
 information pertaining to said instrumentation code and said training procedure is mapped from a given concrete data structure to a given logical data structure that corresponds to the given concrete data structure.   
     
     
         7 . The computer program product of  claim 6 , wherein:
 the given concrete data structure pertains to a given basic block, and responsive to modifying the given basic block, instrumentation and training information mapped to the given logical data structure is remapped back therefrom to the given concrete data structure, for use in updating the given basic block.   
     
     
         8 . The computer program product of  claim 7 , wherein:
 a management tool is used for inserting instrumentation codes and applying training procedures.   
     
     
         9 . The computer program product of  claim 1 , wherein:
 an abstraction applied to a concrete data structure associated with an invariant is used to map the concrete data structure to a corresponding logical data structure.   
     
     
         10 . The computer program product of  claim 1 , wherein:
 the number of basic blocks that pertain to concrete data structures associated with invariants is selectively less than the total number of basic blocks included in the computer program.   
     
     
         11 . The computer program product of  claim 1 , wherein:
 each concrete data structure associated with one or more invariants is selectively monitored for invariant violations during computer runtimes.   
     
     
         12 . In association with a computer program comprising one or more basic blocks, and concrete data structures that each pertains to a basic block, a computer system comprising:
 a bus;   a memory connected to the bus, wherein program code is stored on the memory; and   a processor unit connected to the bus, wherein the processor unit executes the program code to identify one or more invariants, wherein each invariant is associated with one of the concrete data structures; determine at specified times whether an invariant has been violated; and responsive to detecting a violation of one of the invariants, flagging the detected violation as an anomaly.   
     
     
         13 . The system of  claim 12 , wherein:
 the program includes multiple control flows, and at least one invariant violation comprising an anomaly is detected across two or more control flows.   
     
     
         14 . The system of  claim 12 , wherein:
 each invariant comprises a selected invariant rule, wherein each invariant rule corresponds to a logical data structure that is mapped to the concrete data structure of a basic block.   
     
     
         15 . The system of  claim 12 , wherein:
 instrumentation code, for use in detecting violation of one or more invariants, is selectively inserted into each concrete data structure associated with one or more invariants.   
     
     
         16 . The system of  claim 15 , wherein:
 a training procedure is applied to each basic block having a concrete data structure associated with one or more invariants, in order to determine standards that define violations of said invariants.   
     
     
         17 . The system of  claim 16 , wherein:
 information pertaining to said instrumentation code and said training procedure is mapped from a given concrete data structure to a given logical data structure that corresponds to the given concrete data structure.   
     
     
         18 . The system of  claim 17 , wherein:
 the given concrete data structure pertains to a given basic block, and responsive to modifying the given basic block, instrumentation and training information mapped to the given logical data structure is remapped back therefrom to the given concrete data structure, for use in updating the given basic block.   
     
     
         19 . The system of  claim 18 , wherein:
 a management tool is used for inserting instrumentation codes and applying training procedures.   
     
     
         20 . The system of  claim 12 , wherein:
 the number of basic blocks that pertain to concrete data structures associated with invariants is selectively less than the total number of basic blocks included in the computer program.