Anomaly Detection in Database Systems


In today's business world, information is the most valuable asset of organizations and thus requires appropriate management and protection. In this, database systems play a center role because they not only allow the efficient management and retrieval of huge amounts of data, but also because they provide mechanisms that can be employed to ensure the integrity of the stored data.

Reality, however, shows that such mechanisms for enforcing organizational security policies are often not adequately used. There are various reasons for this. First, security policies are often not known or not well specified, making it difficult or even impossible to translate them into appropriate security mechanisms. This observation holds for both general security policies as well as policies tailored to individual database users and applications. Second, and more importantly, security policies do not sufficiently guard data stored in a database system against "privileged users". For example, [CK96] revealed that in computer systems the primary security threat comes from insider abuse rather than from intrusion. This observation results in the fact that much more emphasis has to be placed on internal control mechanisms of systems, such as audit log analysis.

Related Work

The security goals of database systems are availability, confidentiality and integrity. Mandatory and discretionary access control models ([BL73, Bib77, Dio81,HRU76]) have been proposed for general computer systems to prevent misuse (Misuse includes both insider abuse and intrusion.). Nevertheless, these mechanisms typically operate on the file and command/process level of operating systems, which is too coarse for the finer level of granularity of data in database systems.

There are various extensions of these security models to database systems. [Den86, JS90, SW92] extend the concept of mandatory access control in relational database systems by allowing polyinstantiation of data at the tuple level. [WSF79] provides a mapping between access control in a DBS to that at operating system level. These mechanisms are fundamentally the same as general mandatory access control models and hence suffer the same limitation of being only applicable to an organization with known security policies. Further, polyinstantiations come at the cost of increasing the number of tuples in the database.

Misuse detection systems (MDSs) are a cost-effective compromise to establish and assure a certain degree of security in a system. (Intrusion Detection System IDS is often used instead of MDS. However, the term IDS is confusing under the author's definition of intrusion and misuse. Since most systems detect both intrusion and insider abuses, we will adopt the terminology MDS.) Nevertheless, concepts for misuse detection in database systems have not been adequately addressed by existing MDSs ([JV91, VL89, HDL90, SCCC96, FHSL96, LS98]) which neither consider the structure and semantics nor the fine granularity of data in database systems. These systems typically reside on the operating system and/or network which work with files and system commands. The mapping between files in operating systems to relations and attributes in database systems is not exact and hence cannot closely reflect the user behavior. Moreover, auditing the user behavior at these layers is unsuited for misuse detection at the DBS level because the semantics and structure of the data are not reflected in such audit logs.

Our Approach

We propose a misuse detection system tailored to relational database systems. The system called DEMIDS (DEtection of MIsuse in Database Systems) provides a rich set of tools to derive user profiles from audit logs.

Such profiles describe the typical behavior (access patterns) of users in the system by specifying the typical values of features that are audited in audit logs. The profiles derived are used to detect misuse behavior. Although it can be used to detect both intrusion and insider abuse, DEMIDS places emphasis on the detection of malicious behavior by legitimate users who abuse their privileges. Hence the systems is particularly useful for internal control. Our system can complement misuse detection at the operating system layer because intrusion attempts that MDSs fail to detect at the operating system layer may be detected as anomalous events at the database system layer. Further, the profiles derived can serve as a valuable tool for security re-engineering of an organization by helping the security officer to define/refine security policies and to verify existing security policies, if there are any. Finally, profiles can be used to implement respective enforcing mechanisms in the database systems using, e.g., triggers, assignment of privileges, or roles.

Essential to the proposed approach is that, given a database schema and associated applications, the access patterns of users will form some working scopes comprising certain sets of attributes that are usually referenced together with some values. The idea of working scopes is nicely captured by the concept of frequent itemsets which are sets of features with certain values. Based on the data structure and semantics (integrity constraints) encoded in the data dictionary and the user behavior reflected in the audit logs, DEMIDS defines a notion of distance measure which measures the closeness of a set of attributes with respect to the working scopes. Distance measures are used to guide the search for frequent itemsets in the audit logs by a novel data mining approach that takes advantage of the efficient data processing functionality of database management systems. Misuse, such as tampering with the integrity of data, then can be detected by comparing the derived profiles against the security policies specified or against new information (audit data) gathered about the users.


[Bib77] K. J. Biba. Integrity considerations for secure computer systems. Technical Report ESD­TR­76­372, MITRE Corp., Redford, MA, 1977.

[BLP73] D. E. Bell and L.J. La Padula. Secure computer systems: mathematical foundations. Technical Report ESD­TR­73­278, MITRE Corp., Redford, MA, Nov 1973.

[CK96] Carter and Katz. Computer crime: an emerging challenge for law enforcement. FBI Law Enforcement Bulletin, 1-8, December 1996.

[Den86] Dorothy E. Denning et. al. Secure distributed data view: security policy and interpretation for class A1 multilevel secure relational database system. Technical Report A002, SRI International, 1986.

[Dio81] L.C. Dion. A complete protection model. In Proceedinges of the IEEE Symposium on Research in Security and Privacy [OAK], 49-55, 1981.

[FHSL96] Stephanie Forrest, S. A. Hofmeyr, A. Somayaji, and T. A. Longstaff. A sense of self for unix processes. In Proceedinges of the IEEE Symposium on Research in Security and Privacy [OAK], 120-128, 1996.

[HDL90] L. T. Heberlein, G. V. Dias, K. N. Levitt, B. Mukherjee, J. Wood, and D. Wolber. A network security monitor. [OAK], 296-304, 1990.

[HRU76] Michael A. Harrison, Walter L. Ruzzo, and Jeffrey D. Ullman. Protection in operating systems. Communications of ACM, 19(8):461-471, August 1976.

[JS90] S. Jajodia and R. Sandhu. Polyinstantiation integrity in multilevel relations. In Proceedinges of the IEEE Symposium on Research in Security and Privacy [OAK], 104-115, 1990.

[JV91] H. Javitz and A. Valdez. The SRI IDES statistical anomaly detector. [OAK], 316-326, 1991.

[LS98] Wenke Lee and Salvatore J. Stolfo. Data mining approaches for intrusion detection. In Proceedings of the 7th USENIX Security Symposium (SECURITY­98), 79-94, Berkeley, January 26-29 1998. Usenix Association.

[OAK] Proceedings of the IEEE symposium on research in security and privacy.

[SCCC96] Stuart Staniford­Chen, Steven Cheung, Richard Crawford, Mark Dilger, Jeremy Frank, James Hoagland, Karl Levitt, Christopher Wee, Raymond Yip, and Dan Zerkle. GrIDS­A graph based intrusion detection system for large networks. In Proceedings of the 19th National Information Systems Security Conference, 1996.

[SW92] K. Smith and M. Winslett. Entity modelling in the MLS relational model. In Proceedings of the International Conference on Very Large Data Bases, Vancouver, British Columbia, Canada, 1992.

[VL89] H. S. Vaccaro and G. E. Liepins. Detection of anomalous computer session activity. In Proceedinges of the IEEE Symposium on Research in Security and Privacy [OAK], 280-289, 1989.

[WSF79] C. Wood, R. C. Summers, and E.B. Fernandez. Authorization in multilevel database models. Information Systems, 4(2):155-161, 1979.

Contact Christina Yip Chung
Last modified June 1, 1999