The ever-rising complexity of operating systems and communication networks has resulted in an increased difficulty in designing reliable security protection mechanisms. As a last line of defense, automated audit trail analysis can be used to detect various forms of security intrusions. However, automated audit trail analysis is difficult because of the complextity of intrusion patterns, of the lack of a complete model of security intrusions, and of the huge amount of audit data. This difficulty is even compounded in a distributed environment, where an attack evidence may span numerous hosts of possibly different architectures, operating systems, and auditing facilities. Because of the lack of an accurate model of security intrusions and because existing audit trails have operating system-specific formats and semantics, we approach the problem of detecting intrusions by designing languages and tools for powerful yet convenient data streams analysis. The proposed approach is independent of any model of security intrusions and audit data format and semantics, making it possible to implement the detection of new intrusion scenarios as they are learned by security experts. This dissertation describes a novel rule-based language (RUSSEL), tailor-made for efficient processing of sequential unstructured data streams in a heterogeneous multi-host environment. The proposed approach enables event correlation occuring at multiple hosts and achieves gradual event abstraction at different levels. The universality of the analysis is attained by providing a format adaptor generator, which automatically converts a broad range of native audit trail formats into a Normalized Audit Data Format (NADF). The approach is powerful thanks to the rule-based RUSSEL, which allows us to express and match arbitrary event patterns in the audit trail. The efficiency of the system is attained by a careful implementation design. We have also developed a deductive system for continuously checking target- system security vulnerablilities. The deductive component is coupled with the audit trail analysis component, therby enabling an adaptive decection rule set. The proposed approach is computationally viable as suggested by the performance measurements of the implemented system against real-life penetrations scenarios. Performance measurements of the implemented tools on real-life scenarios (in simulated environments) suggests that the approach is computationally viable.

New methods for computing perfect hash functions and applications of such functions to the problems of lexicon design are reported in this paper. After stating the problem and briefly discussing previous solutions, we present Cichelli’s algorithm, which introduced the form of the solutions we have pursued in this research. An informal analysis of the problemis given, followed by a presentation of three algorithms which refine and generalise Cichelli’s method in different ways. We next report the results of applying programmed versions of these algorithms to problem sets drawn from natural and artificial languages. A discusion of conceptual designs for the application of perfect hash functions to small and large computer lexicons is followed by a summary of our research and suggestions for futher work.

Both single level and two level indexed descriptor schemes for multikey retrieval are presented and compared. The descriptors are formed using superimposed coding techniques and stored using a bit-inversion technique. A fast-batch insertion algorithm for which the cost of forming the bit-inverted level implementation is generally more efficient for queries with a small number of matching records. For queries that specify two or more values, there is a potential problem with the two-level implementation in that costs may accrue when blocks of records match the query but individual records within these blocks do not. One approach to overcoming this problem is to set bits in the descriptors based on pairs of indexed terms. This approach is presented and analyzed.

A relation can be represented by a bit matrix such that relational intersections, union, natural join, product and equiselection operations can be implemented by parallel bitwise AND and OR of bit matrices. Depending on the dimensions of the bit matrices, this representation is more or less approximate in so far as spurious tuples may be recovered from a bit matrix along with genuine tuples. The process of outputting a result relation is serial and has desirable properties that output tuples can be sorted at no extra cost, and elimination of duplicates from projections actually speeds up the process instead of requiring extra work. Results of small-scale simulation are reported.

A highly compressed index for a collection of variable-sized documents is described. Arrays of small Bloom filters are used to effeciently locate documents where the search probe contains ‘anded’ and ‘ored’ combinations of words. Theoretical and experimental results are reported. The method is applicable to unplanned searching of large text files. We further describe a method to provide an index to the filters. Thus only a small proportion of the compressed filter need be examined. The method is highly amendable to parallel processing.

The empirical false drop rate associated with a fixed-size Bloom filter used to represent textual documents may be quite different than the theoretical rate. This problem arises when the filter size is based on the expectation of a uniform distribution of the number of different terms per document. The distribution is, in fact, not uniform. This paper describes a method to determine the filter size for a database of textual documents, based on the desired false drop rate and the actual distribution of different words over the documents for that database. Theoretical and experimental results are reported and indicate that a filter size based on this method produces empirical false drop rates equivalent to the theoretical rates. The filter was also compared to variable-length filters with respect to storage requirements and search times.

Bloom filter technique of hashing finds several applications, such as in efficient maintenance of differential files, space efficient storage of dictionaries, and parallel free-text searching. The performance of has transformations with reference to the filter error rate is the focus of this article.

As computer security becomes a more important issue in modern society, it begins to warrent a systematic approach. The vast majority of the computer security problems and the costs associated with them can be prevented with simple inexpensive measures. The most important and cost effective of these measures are available in the prevention and planning phases. These methods are presented following by a simplified guide to incident handlying and recovery.

Executive Summary: Computer system security officials typically have very few, if any good automated tools to gather and process auditing information on potential computer system intruduers. It is most challenging to determine just what actions constitute potential intrusion in a complex mainframe computer environment. Trusted Information Systems (TIS), Inc. recently completed a survey to determine what auditing tools are available that will reliably detect intruders on mainframe computer systems. Their report #348 was done for the Air Force and includes details on nine specific software tools for intrusion detection.

Today’s computer systems are vulnerable both to abuse by insiders and to penetration by outsiders, as evidenced by the growing number of incidents reported in the press. To close all security loopholes from today’s systems is infeasible, and no combination of technologies can prevent legitimate users from abusing their authority in a system; thus auditing is viewed as the last line of defense. Over the past several years, the computer security community has been developing automated tools to analyze computer system audit data for suspicious user behavior. This paper describes the use of such tools for detecting computer system intrusion and describes futher technologies that may be of use for intrusion detection in the future.

Intrusion detection is a new, retrofit approach for providing a sense of security in existing computers and data networks, while allowing them to operate in their current “open” mode. The goal of intrusion detection is to identify, preferably in real time, unauthorized use, misuse, and abuse of computer systems by both system insiders and external penetrators. The intrusion detection problem is becoming a challenging task due to the proliferation of heterogeneous computer networks since the increased connectivity of computer systems gives greater access to outsiders and makes it easier for intruders to avoid identification. Intrusion detection systems (IDSs) are based on the beliefs that an intruder’s behavior will be noticeably different from that of a legitimate user and that many unauthorized actions are detectable. Typically, IDSs employ statistical anomaly and rule-based misuse models in order to detect intrusions. A number of prototype IDSs have been developed at several institutions, and some of them have also been deployed on an experimental basis in operational systems. In this paper, several host-based and network-based are surveyed, and the characteristics of the corresponding systems employ the host operating system’s audit trails as the main source of input to detect intrusive activity, while most of the network-based IDSs build their detection mechanism on monitored network traffic, and some employ host audit trails as well. An outline of a statistical anomaly detection algorithm employed in a typical IDS is also included.

This paper describes a new concept in network intrusion detection based up statistical recognition of an intruder’s control-loop. These criteria offer advantages in infinite networks and where a priori attack scenarios are not known. This paper describes the need for better intrusion detection methods, the applicablity of digital signal processing to real-time network surveillance, the concept of control-loop behavior, and the design of an innovative intrusion detection system employing these. We also discuss the benefits of this new system in comparison with alternative technologies.

Developers of audit trail analysis tools need a data interchange format to allow sharing audit trail information from different operating sytems. We wanted an audit data interchange format to provide interoperability of intrusion and misuse detection tools and to facilitate cooperative work involving audit trail analysis, especially for the detection of intrusions and other misuses. While the general case of this problem is very difficult (to convert from IBM MVS SMF records to SunOS Basic Security Module data, for example), it is much more feasible to define a common record format across those Unix versions that support auditing at least at the NCSC C2 level. This document describes the format we have developed. Our internal name for this format is “svr4++”.

This paper builds upon and extends Weber’s (1982) pioneering analysis of the concept of an audit trail, incorporating recent developments from the fields of computer security and temporal modeling in databases. A review of current usage suggests that the term audit trail is being used in two distinct senses: as meaning an abstract property of an accounting information system and as meaning a concrete log file. The various kinds and purposes of log files are analyzed, and a classification system is proposed. The more general audit trail concept is then discussed. A definition of the property of audit trail which captures the notion behind its use in current literature is proposed. It is shown that the various categories of information that are found in log files can be explained in terms of this definition, but that the property of audit trail does not intrinsically require the use of any log files. The “loss” of the audit trail brought about by the move from manual accounting systems to computer-based ones, and from register-orientated designs to database systems, is discussed and a description of the nature of the change is proposed.