We show that matrix multiplication, matrix inversion, convolution, and sorting can be securely “outsourced”, in the following sence: A customer who needs these computations done on some data but lacks the computational resources (or programming expertise) to do so, can use an external agent to perform these computations without revealing to the agent either the actual data or the actual answer to the computation. This general situation currentlly arises in many practical situations, including the finacial services and petroleum services industries. The general idea is for the customer to do some carefully designed local preprocessing of data before sending it to the agent, and also some local postprocessing of the answer returned by the agent, in order to extract from it the true answer. The pre- and post- processing should not take more time than proportional to the size of the input, which is unavoidable because the customer must at least read the input once. The purpose of the preprocessing step that the customer performs locally is to “hide” the real data The purpose of the postprocessing is to extract from the noisy answer returned by the agent the true answer that the customer seeks.

In a computer network that consists of M subnetworks, the L-bit address of a machine consists of two parts: A prefix s(sub i) that contains the address of the subnetwork to which the machine belongs, and a sufix (of length L - |s(sub i)| ) containing the address of that particular machine within its subnetwork. In fixed-length subnetwork addressing, |s(sub i)| varies from one subnetwork to another. To avoid ambiguity when decoding addresses, there is a requirement that no s(sub i) be a prefix of another s(sub j). The practical problem is how to find a suitable set of s(sub i’s) in order to maximize the total number of addressable machines, when the ith subnetwork contains n(sub i) machines. Not all of the n(sub i) machines of a subnetwork i need to be addressable in a solution: If n(sub i) > 2^(L - |s(sub i)|) then only 2^(L - |s(sub m machines of that subnetwork are addressable (none is addressable if the solution assigns no address s(sub i) to that subnetwork). The abstract problem implied by this formulation is: Given an integer L, and given M (not necessarily distinct) positive integers n1,....n(sub m) find M binary stings s1, ... s(sub m) (some of which may be empty) such that (i) no nonempty string s(sub i) is prefix of another string s(sub j), (ii) no s(sub i) is more than L bits long, and (iii) the quantity (sumation |s(sub k)| is not equal to 0 ) min{n(sub k, 2^(L - |s(sub k)|} is maximized. We generalize the algorithm to the case where each n(sub i) also has a priority p(sub i) associated with it and there is an additional constraint involving priorities: Some subnetworks are then more important than others and are treated preferentially when assigning addresses. The algorithms can be used to solve the case when L itself is a variable; that is, when the input no longer specifies L but rather gives a target integer gama for the number of addressable machines, and the goal is to find the smallest L whose corresponding optimal solution results in at least gama addressable machines.

We give a randomized O(N Log M) time algorithm for determining the Hamming-distance score vector between a text string T of length N and a pattern string P of length M M <= N. This is the vector whose ith entry contains the number of positions at which there is equality between the symbols of the pattern and the corresponding positions of the substring that begins at the i-th position of the text. No assumptions are made about the size of the alphabet or about the probabilistic characteristics of the input. The solution extends to the weighted case, and to higher dimensions.

We consider the problem of distributing potentially dangerous information to a number of competing parties. As a prime examplem, we focus on the issue of distributing security patches to software. These patches implicitly contain vulnerablility information that may be abused to jeopardize the security of other systems. When a vedor supplies a binary program patch, different users may receive it at different times. The differential application times of the patch create a window of vulnerablility until all users have installed the patch. An abuser might analyze the binary patch before others install it. Armed with this information, he might be able to abuse another user’s machine. A related situation occurs in the deployment of security tools. However, many tools will necessarily encode vulnerability information or explicit information about security “` “localisms”. This information may be reverse-engineered and used against systems. We discuss several ways in which security patches and tools may be made safer. Among these are: customizing patches to apply only to one machine, disguising patches to hinder thier interpretation, synchronizing patch distribution to shrink the window of vulnerablility, applying patches automatically, and using cryptoprocessors with enciphered operating systems. We conclude with some observations on the utility and effectiveness of these methods.

This report presents a prototype architecture of a defense mechanism for computer systems. The intrusion detection problem is introduced and some of the key aspects of any solution are explained. Standard intrusion detection systems are built as a single monolithic module. A finer-grained approach is proposed, where small, independent agents monitor the system. These agents are taught how to recognise intrusive behaviour. The learning mechanism in the agents is built using Genetic Programming. This is explained, and some sample agents are described. The flex- ibility, scalability and resilience of the agent approach are discussed. Future issues are also outlined.

This manual gives a detailed technical description of the IDIOT intrusion detection system from the COAST Laboratory at Purdue University. It is intended to help any- one who wishes to use, extend or test the IDIOT system. Familiarity with security issues, and intrusion detection in particular, is assumed.