An attack surface enumerates resources accessible to an attacker for cyber attacks on a system. These resources are: methods that can be called as part of an attack; channels that an attacker outside the system can use to get to a system’s interface; and untrusted data that an attacker can use in conjunction with the system’s programs and channels. Historically, a system’s attacks surface has provided a metric on the vulnerability of a system, in part to compare two systems’ exposure to attack.

The information security community is haunted by the failure of an appropriate break-the-glass access control at the United States Center for Disease Control that led to an estimated additional 1.2 million deaths in North America in 2036. In this paper we review what caused the security failures in this system and argue that, by combining human intelligence with multiple technological approaches to create a system that emphasizes human approaches to guide analysis, the failures that occurred will not recur. We also leverage people and technologies to identify and fill gaps in the training data to minimize the threat of unexpected events. While we use this scenario as our running example, we note that our approach is generalizable to a broader problem space where machine learning approaches have been deployed to make decisions.

Consensus is a fundamental approach to implementing fault-tolerant services through replication. It is well known that there exists a tradeoff between the cost and the resilience. For instance, Crash Fault Tolerant (CFT) protocols have a low cost but can only handle crash failures while Byzantine Fault Tolerant (BFT) protocols handle arbitrary failures but have a higher cost. Hybrid protocols enjoy the benefits of both high performance without failures and high resiliency under failures by switching among different subprotocols. However, it is challenging to determine which subprotocols should be used. We propose a moving target approach to switch among protocols according to the existing system and network vulnerability. At the core of our approach is a formalized cost model that evaluates the vulnerability and performance of consensus protocols based on real-time Intrusion Detection System (IDS) signals. Based on the evaluation results, we demonstrate that a safe, cheap, and unpredictable protocol is always used and a high IDS error rate can be tolerated.

We present hBFT, a hybrid, Byzantine fault-tolerant, replicated state machine protocol with optimal resilience. Under normal circumstances, hBFT uses speculation, i.e., replicas directly adopt the order from the primary and send replies to the clients. As in prior work such as Zyzzyva, when replicas are out of order, clients can detect the inconsistency and help replicas converge on the total ordering. However, we take a different approach than previous work that has four distinct benefits: it requires many fewer cryptographic operations, it moves critical jobs to the clients with no additional costs, faulty clients can be detected and identified, and performance in the presence of client participation will not degrade as long as the primary is correct. The correctness is guaranteed by a three-phase checkpoint subprotocol similar to PBFT, which is tailored to our needs. The protocol is triggered by the primary when a certain number of requests are executed or by clients when they detect an inconsistency.

Building robust network services that can withstand a wide range of failure types is a fundamental problem in distributed systems. The most general approach, called Byzantine fault tolerance, can mask arbitrary failures. Yet it is often considered too costly to deploy in practice, and many solutions are not resilient to performance attacks. To address this concern we leverage two key technologies already widely deployed in cloud computing infrastructures: replicated state machines and intrusion detection systems. First, we have designed a general framework for constructing Byzantine failure detectors based on an intrusion detection system. Based on such a failure detector, we have designed and built a practical Byzantine fault-tolerant protocol, which has costs comparable to crash-resilient protocols like Paxos. More importantly, our protocol is particularly robust against several key attacks such as flooding attacks, timing attacks, and fairness attacks, that are typically not handled well by Byzantine fault masking procedures.

It has been a longstanding goal of the cyber-security community to improve the collective security of the general computing population by reducing the attack incidents and the overall susceptibility to attack; we refer to this as improving the public cyber-security. Traditionally, computer security techniques have tried to accomplish this by focusing upon securing specific computing systems and networks. This approach is akin to the practice of medicine in the health care industry to treat illness and disease in individuals. In the field of health care, the collective health of the population is treated by the practice of public health. Currently, there is no analogous public cyber-security system to treat the collective cyber-health of the computing population. We assert that a public cyber-security system, based upon well founded, sound principles currently used in the public health care discipline is needed in order to satisfy our longstanding goal of improving public cyber-security. We outline some of the technical features of such a system and how it might operate.

In this paper, we present a new framework to analyze firewall policy by using argumentation. At the core of this new idea is extending firewall rules with the concept of “reasons” and arguing about the reasons, not the rules. Depending on how the reasons are designed, the resulting framework can be useful in a number of ways: new anomalies in a firewall policy can be identified while, at the same time, stronger recommendations can be given to resolve those anomalies that are detected.

Trust is a natural mechanism by which an autonomous party can deal with the inherent uncertainty regarding the behaviors of other parties and the uncertainty in the information it shares with those parties. Trust is thus crucial in any decentralized system. We build on recent efforts to use argumentation to reason about trust. Specifically, we provide a set of schemes, abstract patterns of reasoning that apply in multiple situations, geared toward trust. We describe, in the form of a set of critical questions, the situations in which the schemes may default.

We present our preliminary work in using argumentation logics to reason about security administration tasks. Decisionsabout network security are increasingly complex, involvingtradeoffs between keeping systems secure, maintaining system operation, escalating costs, and compromising functionality. In this paper we suggest the use of argumentation to provide automated support for security decisions. Argumentation is a formal approach to decision making that has proved to be effective in a number of domains. In contrast to traditional first order logic, argumentation logic provides the basis for presenting arguments to a user for or against a position, along with well-founded methods for assessing the outcome of interactions among the arguments. We demonstrate the use of argumentation in a reconfiguration problem, to diagnose the root cause of cyber-attack, and to set policies.

Social informatics is the core of Facebook's business and is its most valuable asset which consists of the social graph and the private data of over 500 million users. However, without secure methods of managing this data, Face book has become vulnerable to privacy risks and devaluation. In Facebook's model, users are asked upon access to grant applications the required permissions without sufficient knowledge of the applications' intentions. As a result, if they are deceived, users risk the exposure of sensitive and personal data. This paper presents a system dubbed FAITH (Face book Applications: Identification, Transformation & Hyper visor) to mitigate or eliminate these issues by enhancing the management of social data. First, FAITH allows users to adjust the visibility of their social informatics for each individual application depending on how much they trust the application. Users can configure FAITH to let non-trusted applications run with the least privileges (least amount of social informatics) to minimize potential privacy leaks. Second, FAITH logs the activities of applications to assist users in making more secure decisions. Users can closely monitor each activity performed by applications to adjust their privacy settings more securely. Third, FAITH allows users to transform their social graph such that different applications see different social graphs preventing the formation of friendship inflation caused by applications. The implementation of FAITH only needs the resources and tools available to the public by Face book and requires no further cooperation from the social network. FAITH is a prototype system: the design and concept can be extended to secure other OSNs (Online Social Networks). Currently, FAITH contains thirteen Face book social applications and has been officially released for public usage with approximately two hundred monthly active users as of now.

In large wireless sensor networks (WSNs), each hop might incur varying delays due to medium access contention, transmission and computation delays. Fast and efficient query responses are essential to network performance and maintenance. To save energy in battery-powered sensors, it is desirable that data be aggregated or compressed along the way toward the base-station (BS). The common method to aggregate data from network edge to the BS uses a hard-line precomputed timer that requires sensors near the network edge to respond to a query earlier than sensors in the vicinity of the BS [1], [2]. Such rigid scheduling ignores the WSNs's topology and stability. Aggregation opportunities are wasted if the query response timer is set incorrectly. Estimating and allocating precise per- hop communication timers for each node in a large WSN is difficult because timing depends on the network dynamics. We develop a novel, generic and scalable method, which we call soft-line recursive response (SRR), that bases response-wait on actual response times to previous queries using a history buffer, and therefore, is tolerant of network faults or temporal delays. Our simulations show that SRR can improve aggregation opportunities up to 120% over the hard-line approach, while increasing delay less than 5%. SRR reduces query response traffic and data redundancy in both homogeneous and heterogeneous static and mobile WSNs with a maximum O(N) transmission overhead in large WSNs of N nodes and O(logb) update cost where b is the history buffer size.

Many tasks require multiple sensing capabilities; in wireless sensor networks (WSNs), it is expensive to deploy a homogeneous network wherein every sensor has the same functionality. Instead, it is economical to deploy a heterogeneous network wherein sensors differ in their capabilities; in such a network, efficient data querying is essential. We propose a multi-keyword routing protocol, iBubble, for heterogeneous wireless sensor networks (HWSNs) where keywords describe sensor functionalities. iBubble provides an efficient query interface for locating data; queries are routed only along paths with nodes matching the query. iBubble utilizes an intelligent bubbling mechanism to propagate keywords to the base-station (BS). The keywords are aggregated via a novel use of lattices to reduce network cost. We show that iBubble can emulate diffusion and generally produce less traffic by restricting the query dissemination based upon both application type and data value. Our study analytically compares iBubble and diffusion, and formally characterizes the conditions required for iBubble to outperform diffusion in both static (fixed) and dynamic (mobile) networks. We did extensive simulations, our results match our theory and show that iBubble can outperform diffusion in many heterogeneous deployments when keyword distributions are "clustered" enough to satisfy the fraction of the network involved in a query/update defined by our analytical bound. Additionally, iBubble handles mobility, fault-tolerance, and provides network diagnosis via keyword bubbling. By utilizing keywords, iBubble bridges many routing and energy problems prevalent in WSNs, and provides a simple, uniform solution.

We present a framework to prevent code injection attacks in MS Windows using Native APIs in the operating system. By adopting the idea of diversity, this approach is implemented in a two-tier framework. The first tier permutes the Native API dispatch ID number so that only the Native API calls from legitimate sources are executed. The second tier provides an authentication process in case an attacker guesses the first-tier permutation order. The function call stack is back-traced to verify whether the original caller's return address resides within the legitimate process. The process is terminated and an alert is generated when an attack is suspected. Experiments indicate that our approach poses no significant overhead.

A Mobile Ad Hoc Network (MANET) is a group of mobile wireless nodes that can communicate with each other without pre-established base stations. Their communication relies on cooperative forwarding behavior, and therefore, routing service is critical for MANET. Most routing protocols depend on forwarded routing messages. If a malicious node propagates forged routing information through forwarded routing messages, all other nodes' routing tables will be damaged. We first propose Distributed Routing Evidence Tracing and Authentication intrusion prevention model (DRETA) for MANET routing protocols. DRETA provides low computation authentication service by adopting one-way key chain with delayed key disclosure. DRETA proposes Previous Forwarder (PF), which is a scalable technique for tracing and protecting the routing evidence of forwarded routing messages. Second, we implement DRETA in two representative routing protocols in MANET, Ad-hoc On-demand Distance Vector routing protocol (AODV) and Optimized Link State Routing protocol (OLSR). Experimental results show that DRETA is accurate, scalable, and requires low message overhead, and offers small delays under high mobility conditions.

Processing and storage of confidential or critical information is an every day occurrence in computing systems. The trustworthiness of computing devices has become an important consideration during hardware design and fabrication. For instance, devices are increasingly required to store confidential information. This includes data such as cryptographic keys, personal information, and the intellectual property (IP) in the device's design. Furthermore, computing systems in critical applications must work as specified. Therefore it is important that hardware be designed and fabricated to be trustworthy.

Computer worms are a serious problem. Much research has been done to detect and contain worms. One major deficiency in most research is that the claims are supported by theoretic models or simulations only and not by realistic tests. Network testbeds such as emulab and deter can be used to conduct worm experiments on networks of a few hundreds nodes. However, setting up such an experiment is not trivial. In this paper, we describe a wrapper around emulab to deploy such experiments quickly. We also demonstrate its use by evaluating an example worm containment strategy.

Attack polymorphism is a powerful tool for the attackers in the Internet to evade signature-based intrusion detection/prevention systems. In addition, new and faster Internet worms can be coded and launched easily by even high school students anytime against our critical infrastructures, such as DNS or update servers. We believe that polymorphic Internet worms will be developed in the future such that many of our current solutions might have a very small chance to survive. In this paper, we propose a simple solution called "Buttercup" to counter against attacks based on buffer-overflow exploits (such as CodeRed, Nimda, Slammer, and Blaster). We have implemented our idea in SNORT, and included 19 return address ranges of buffer-overflow exploits. With a suite of tests against 55 TCPdump traces, the false positive rate for our best algorithm is as low as 0.01%. This indicates that, potentially, Buttercup can drop 100% worm attack packets on the wire while only 0.01% of the good packets will be sacrificed.

When computer security violations are detected, computer forensic analysts attempting to determine the relevant causes and effects are forced to perform the tedious tasks of finding and preserving useful clues in large networks of operational machines. To augment a computer crime investigator's efforts, we present an expert system with a decision tree that uses predetermined invariant relationships between redundant digital objects to detect semantic incongruities. By analyzing data from a host or network and searching for violations of known data relationships, particularly when an attacker is attempting to hide his presence, an attacker's unauthorized changes may be automatically identified. Examples of such invariant data relationships are provided, as are techniques to identify new, useful ones. By automatically identifying relevant evidence, experts can focus on the relevant files, users, times and other facts first.

Cyber attacks continue to increase in sophistication. Advanced attackers often gather information about a target system before launching a precise attack to exploit a discovered vulnerability. This paper discusses techniques for remote identification of web servers and suggests possible defenses to the probing activity. General concepts of finger-printing and their application to the identification of Web servers, even where server information has been omitted are described and methodologies for detecting and limiting such activity are discussed.

Intrusion detection is a technique employed tocatch and report attacks as they occur. It isneeded given that vulnerabilities in operatingsystems, network protocols, applications, andconfigurations leave systems open to attacks.

We describe the implementation of an intrusion tolerant system for providing Internet services to known users through secure connections. Network attacks are treated as maliciously devised conditions to exploit design, implementation, or configuration faults, intrusions (successful attacks) are treated as failures, and their effects are mitigated by using the three pillars of fault tolerance: detection, isolation, and recovery. Fundamental to our approach is the use of diverse process pairs, which provides partial solutions to detection and isolation problems. The architecture uses the comparison of outputs from diverse applications to provide a significant and novel intrusion detection capability. The diverse applications also strengthen isolation by forcing attacks to exploit independent vulnerabilities. The isolation of intrusions is mainly achieved with an out-of-band control system. The control system not only provides separation between the primary and backup system, it also initiates attack diagnosis, attack blocking, and recovery, which is accelerated by on-line repair.

Many network applications depend on the security of the domain name system (DNS). Attacks on the DNS can cause denial of service and entity authentication to fail. In our approach, we use formal specifications to characterize DNS clients and DNS name servers, and to define a security goal. A name server should only use DNS data that is consistent with data from name servers that manage the corresponding domains (i.e. authoritative name servers). To enforce the security goal, we formally specify a DNS wrapper that examines the incoming and outgoing DNS messages of a name server to detect messages that could cause violations of the security goal, cooperates with the corresponding authoritative name servers to diagnose those messages, and drops the messages that are identified as threats. Based on the wrapper specification, we implemented a wrapper prototype and evaluated its performance. Out experiments show that the wrapper incurs reasonable overhead and is effective against DNS attacks such as cache poisoning and certain spoofing attacks.

This paper presents a layered verification technique, called LVT, for the verification of distributed computing systems with multiple component layers. Each lower layer in such a system provides services in support of functionality of the higher layer. By taking a very general view of programming languages as interfaces of systems, LVT treats each layer in a distributed computing system as a distributed programming language. Each relatively higher-level language in the computing system is implemented in terms of a lower-level language. The verification of each layer in a distributed computing system can then be viewed as the verification of implementation correctness for a distributed language. This paper also presents the application of LVT to the verification of a distributed computing system, which has three layers: a small high-level distributed programming language; a multiple processor architecture consisting of an instruction set and system calls for inter-process message passing; and a network interface. Programs in the high-level language are implemented by a compiler mapping from the language layer to the multiprocessor layer. System calls are implemented by network services. LVT and its application demonstrate that the correct execution of a distributed program, most notably its inter-process communication, is verifiable through layers. The verified layers guarantee the correctness of (1) the compiled code that makes reference to operating system calls, (2) the operating system calls in terms of network calls, and (3) the network calls in terms of network transmission steps. The specification and verification involved are carried out by using the Cambridge Higher Order Logic (HOL) theorem proving system. Copyright © 1999 John Wiley & Sons, Ltd.

Existing work on inference detection for database systems mainly employ functional dependencies in the database schema to detect inferences. It has been noticed that analyzing the data stored in the database may help to detect more inferences. We describe our effort in developing a data level inference detection system. We have identified five inference rules that a user can use to perform inferences. They are "subsume", "unique characteristic", "overlapping", "complementary", and "functional dependency" inference rules. The existence of these inference rules confirms the inadequacy of detecting inferences using just functional dependencies. The rules can be applied any number of times and in any order. These inference rules are sound. They are not necessarily complete, although we have no example that demonstrates incompleteness. We employ a rule based approach so that future inference rules can be incorporated into the detection system. We have developed a prototype of the inference detection system using Perl on a Sun SPARC 20 workstation. The preliminary results show that on average it takes seconds to process a query for a database with thousands of records. Thus, our approach to inference detection is best performed offline, and would be most useful to detect subtle inference attacks.

We present a solution to the denial of service problem for routing infrastructures. When a network suffers from denial of service, packets cannot reach their destinations. Existing routing protocols are not well-equipped to deal with denial of service; a misbehaving router---which may be caused by software/hardware faults, misconfiguration, or malicious attacks---may be able to disable entire networks. To protect network infrastructures from routers that incorrectly drop packets and misroute packets, we hypothesize failure models for routers and present protocols that detect and respond to those misbehaving routers. Based on realistic assumptions, we prove that our protocols have the following properties: (1) A well-behaved router never incorrectly claims another router as a misbehaving router; (2) If a network has misbehaving routers, one or more of them can be located; (3) Misbehaving routers will eventually be removed. 1 Introduction Through a myriad of applications, including elec...

We describe a specification-based approach to detect exploitations of vulnerabilities in security-critical programs. The approach utilizes security specifications that describe the intended behavior of programs and scans audit trails for operations that are in violation of the specifications. We developed a formal framework for specifying the security-relevant behavior of programs, on which we based the design and implementation of a real-time intrusion detection system for a distributed system. Also, we wrote security specifications for 15 Unix setuid root programs. Our system detects attacks caused by monitored programs, including security violations caused by improper synchronization in distributed programs. Our approach encompasses attacks that exploit previously unknown vulnerabilities in security-critical programs.

A program that accesses an out-of-bound array element can cause unexpected behaviour that is unacceptable to safety-critical or security-critical systems. Two traditional compile-time approaches to array bound checking are flow analysis and program verification. This paper presents a new approach, IFV, that integrates flow analysis and program verification techniques. IFV is generally about as effective as program verification yet runs in about the same time as flow analysis. Its typical runtime is proportional to the product of the program size and the number of declared variables. IFV matches loops to templates, which represent commonly occurring loop patterns, to discover loop invariants automatically, which it then uses to strengthen flow analysis. With only seven templates, it handles many common array-access patterns. Patterns not verified by flow analysis are processed with verification techniques entirely automatically. This paper also describes a prototype IFV system that performs compile-time array bound checking for programs in a subset of C. © 1997 John Wiley & Sons, Ltd.

Addresses the problem of testing security-relevant software, especially privileged (typically, setuid root) and daemon programs in UNIX. The problem is important, since it is these programs that are the source of most UNIX security flaws. For some programs, such as the UNIX sendmail program, new security flaws are still being discovered, despite being in use for many years. For special-purpose systems with fewer users, flaws are likely to remain undiscovered for even longer. Our testing process is driven by specifications we create for the privileged programs. These specifications simultaneously define the allowed behavior far these programs and identify problematic system calls, regions where the program is vulnerable, and generic security flaws. The specifications serve three roles in our testing methodology: as criteria against which a program is sliced, as oracles against which it is tested, and as a basis for generating useful tests. Slicing is employed to significantly reduce the size of the program to be tested. We show that a slice of a privileged program (rdist) with respect to its security specifications is quite small. We introduce the Tester's Assistant, a collection of tools to mechanize the process of testing security-related C programs.>

Presents a method for detecting exploitations of vulnerabilities in privileged programs by monitoring their execution using audit trails, where the monitoring is with respect to specifications of the security-relevant behavior of the programs. Our work is motivated by the intrusion detection paradigm, but is an attempt to avoid ad hoc approaches to codifying misuse behavior. Our approach is based on the observation that although privileged programs can be exploited (due to errors) to cause security compromises in systems because of the privileges accorded to them, the intended behavior of privileged programs is, of course, limited and benign. The key, then, is to specify the intended behavior (i.e. the program policy) and to detect any action by a privileged program that is outside the intended behavior and that imperils security. We describe a program policy specification language, which is based on simple predicate logic and regular expressions. In addition, we present specifications of privileged programs in Unix, and a prototype execution monitor for analyzing audit trails with respect to these specifications. The program policies are surprisingly concise and clear, and in addition, capable of detecting exploitations of known vulnerabilities in these programs. Although our work has been motivated by the known vulnerabilities in Unix, we believe that by tightly restricting the behavior of all privileged programs, exploitations of unknown vulnerabilities can be detected. As a check on the specifications, work is in progress on verifying them with respect to an abstract security policy.>

Computer and network systems are vulnerable to attacks. Abandoning the existing huge infrastructure of possibly-insecure computer and network systems is impossible, and replacing them by totally secure systems may not be feasible or cost effective. A common element in many attacks is that a single user will often attempt to intrude upon multiple resources throughout a network. Detecting the attack can become significantly easier by compiling and integrating evidence of such intrusion attempts across the network rather than attempting to assess the situation from the vantage point of only a single host. To solve this problem, we suggest an approach for distributed recognition and accountability (DRA), which consists of algorithms which “process”, at a central location, distributed and asynchronous “reports” generated by computers (or a subset thereof) throughout the network. Our highest-priority objectives are to observe ways by which an individual moves around in a network of computers, including changing user names to possibly hide his/her true identity, and to associate all activities of multiple instances of the same individual to the same networkwide user. We present the DRA algorithm and a sketch of its proof under an initial set of simplifying albeit realistic assumptions. Later, we relax these assumptions to accommodate pragmatic aspects such as missing or delayed “reports”, clock skew, tampered “reports”, etc. We believe that such algorithms will have widespread applications in the future, particularly in intrusion-detection systems.

In a previous paper, M. Archer et al. (1990) presented a tool for the rapid prototyping of operating systems based on an executable template operating system specification. By extending the template specification, a designer can generate a rapid prototype of a specific operating system. The template specification consists of sorts (object classes) arranged in a hierarchy of three kinds, where the design decisions made in the template for each kind are in some sense more general than those made for its successor kind. The FASE (final algebra specification and execution) system language was used as the language for the specification. It is the authors' belief that the SRM template is general enough to be used as a basis for rapid prototyping nearly any non-distributed operating system at the system call level. It is important to test this belief, and to show that the speed of prototype development and the execution speed of a rapid prototype are great enough for the development of a prototype to be useful for testing the properties of a design. The authors answer these questions, demonstrate the usefulness of having a rapid prototype of an operating system, and evaluate the template methodology in general.>

Probably the most important characteristic of a user interface is its 'look and feel'. One can model the 'look and feel' of user interfaces via rapid prototyping. However, the behavior of a particular user interface is greatly influenced by the particular user interface management system (UIMS) upon which it is built, so it is necessary to prototype an interface with regard to a particular user interface management system. Moving an application and its user interface to a different UIMS may result in a user interface that behaves in a substantially different manner. The authors describe a methodology that may be used to develop a UIMS prototype using a template. This template will assist developers not only in developing new UIMSs but in evaluating the behavior of user interfaces when the underlying UIMS changes.>

A generalization of D. McCullough's (1987; 1988) restrictiveness model is given as the basis for providing security properties for distributed system designs. This generalization is mechanized for an event-based model of computer systems in the HOL (higher order logic) system to prove the composability of the model and several other properties about the model. A set of generalized classes of system components is developed and it is shown for which families of user views they satisfy the model. Using these classes, a collection of general system components that are specializations of one of these classes is delineated and it is shown that the specializations also satisfy the security property. A sample distributed secure system is presented along with an example of how the proposed mechanized verification system can be used to verify such designs.>

Rapid prototyping of many classes of systems can be facilitated by starting from an executable template specification appropriate to that class. A system template serves several useful purposes. It organizes ones thinking about the particular system to be specified, and speeds the specification process by pre-specifying structures and operations common to all systems in a class. If executable, it can be developed into a system prototype. Though beyond the scope of this paper, it can organize proofs of properties of the specification and its implementations by making it possible to isolate the relevant proof obligations. The authors templates have an additional property: they classify sub-specifications according to "kinds" that needs to be completed differently. The authors illustrate rapid prototyping from a template for operating systems, specifically showing how to obtain a rapid prototype of the MINIX system. This approach may also be useful for other classes of systems, such as architectures.>

This study concentrates on the security-related issues in a single broadcast LAN (local area network) such as Ethernet. The authors formalize various possible network attacks. Their basic strategy is to develop profiles of usage of network resources and then compare current usage patterns with the historical profile to determine possible security violations. Thus, the work is similar to the host-based intrusion-detection systems. Different from such systems, however, is the use of a hierarchical model to refine the focus of the intrusion-detection mechanism. The authors also report on the development of an experimental LAN monitor currently under implementation. Several network attacks have been simulated, and results on how the monitor has been able to detect these attacks are analyzed. Initial results demonstrate that many network attacks are detectable with the authors' monitor, although it can be defeated.>

A memory organization is considered for which a large number of faults can be tolerated at a low cost in redundancy. The primitive element in the memory is a large-scale integrated (LSI) chip that realizes a section of memory, b bits wide by y words long, together with an address decoder for the y words. The chips (including spares) are connected via a switching network so that the memory can be reconfigured effectively in the presence of chip failures. The main results of the paper relating to the switching network are as follows.

This paper describes a theorem prover that embodies knowledge about programming constructs, such as numbers, arrays, lists, and expressions. The program can reason about these concepts and is used as part of a program verification system that uses the Floyd-Naur explication of program semantics. It is implemented in the QA4 language; the QA4 system allows many bits of strategic knowledge, each expressed as a small program, to be coordinated so that a program stands forward when it is relevant to the problem at hand. The language allows clear, concise representation of this sort of knowledge. The QA4 system also has special facilities for dealing with commutative functions, ordering relations, and equivalence relations; these features are heavily used in this deductive system. The program interrogates the user and asks his advice in the course of a proof. Verifications have been found for Hoare's FIND program, a real-number division algorithm, and some sort programs, as well as for many simpler algorithms. Additional theorems have been proved about a pattern matcher and a version of Robinson's unification algorithm.

Applying some simple, easily understood principles, Spira, in extending some earlier work of Winograd, points the way to a powerful theory of computation complexity. Spira considers a (d, r) combinational network which is an interconnection of r-input, single-output modules, with each input-output line carrying a value from the set {0, 1, ⋯ , d -1}. A finite function φ: X1 × X2 × ⋯ Xn→Y is to be computed, but it is assumed that before the inputs are inserted into the network, each input can be individually (and arbitrarily) transformed by a set of maps gj: Xj→Ij. It is also assumed that there is a 1-1 output map h: Y→Oc, so in practice the (d, r) network will have as input [g1(x), ⋯, gn(xn)] and as output h(φ(x1, ⋯, xn)). The problem is to bound the number of levels required of the network. Given a φ for a particular output mapping, it is not difficult to specify a lower bound on the number of levels required, by identifying for each output line the number of different values of input variables which yield a different output value. The minimum number of levels required for each output line is then evaluated by noting that an output at level z can depend on at most r' input lines whence the output line requiring the most levels provides the bound.

An important aspect of the packaging of digital networks is the allocation of logic gates to modules such that a predetermined objective function is minimized. In order to develop techniques for this partitioning of a logic network we have considered the following problem: Given an acyclic combinational network composed of various primitive blocks such as NOR gates, assume that a maximum of M gates can be "clustered" together into larger modules, and that a maximum of P pins can be accommodated in each larger module. Assume also that in a network composed of such larger modules, no delay is encountered on the interconnections linking two gates internal to a module and a delay of one time unit is encountered on interconnections linking two gates in different modules . Find an easily applied algorithm that will result in a network such that the maximum delay through the network is minimized.

Described in this report are the results of a comprehensive technical survey of all published Soviet literature in coding theory and its applications--over400papers and books appearing before March 1967. The purpose of this report is to draw attention to this important collection of technical results, which are not well known in the West, and to summarize the significant contributions. Particular emphasis is placed upon those results that fill gaps in the body of knowledge about coding theory and practice as familiar to non-Soviet The most noteworthy Soviet contributions have occurred in those areas that deal with codes for the noiseless channel, codes that correct asymmetric errors, decoding for cyclic codes, randomcoding bounds on the amount of computation required, and various application criteria--that is, when to use which code, and how well it performs. Other important but isolated results have been reported on the construction of optimal low-rate codes, bounds on nonrandom codes, linear (continuous) coding, codes for checking arithmetic operations, properties of code polynomials, linear transformations of codes, multiple-burst-correcting codes, special synchronization codes, and certain broad generalizations of the conventional coding problem. Little or no significant work has been done on pseudorandom sequences, unit-distance codes (with one exception), the application of codes to the design of redundant computers and memories, the search for good cyclic codes, and the physical realization of sequential decoding algorithms. Section II of this report is directed to the nonspecialist, and describes the status of the field of coding theory in the Soviet Union, summarizes the major technical results, and compares these with corresponding work in the West. Section III discusses in detail for the coding specialist new theoretical results, details of coding procedures, and analytical tools described in the Soviet literature. A complete bibliography is included.

A cellular array is a logical network of identical or almost identical cells, each of which contains a small amount of logic and storage, and, except for a few buses to the edge of the array, is connected only to its immediate neighbors. The cellular approach offers special advantages for realization by the forthcoming large-scale-integrated (LSI) technology. Such arrays are shown to be applicable for the encoding and decoding of binary error-correcting codes, and also for identifying the possibilities of tradeoffs between decoding time and equipment complexity. Arrays are presented for the decoding of single errors, burst errors, and erasures; the decoding of erasures is accomplished by the equation-solution approach, and it is shown for several code families that the Gauss elimination procedure is not required.

Abstract—A class of networks is described that has the capability of permuting in an arbitrary manner a set of n digital input lines onto a set of n digital output lines. The circuitry of the networks is arranged in cellular form, i. e., in a two-dimensional iterative pattern with mainly local intercell connections, where the basic cell behaves as a reversing switch with a single memory flip-flop. Various network forms are described, differing in the number of cells needed, in the shape of the array, and in the length and regularity of intercell connections. Also discussed are some ways of setting up the array to achieve a desired permutation.

In this correspondence, we consider nonlinear binary error-correcting codes based upon then-fold interleaving of a periodic binary sequence of lengthLwith out-of-phase (normalized) autocorrelation-1/L. Examples of binary sequences with such out-of-phase autocorrelation (termed two-level sequences) are: 1) maximal-length linear shift-register \footnote[1]{sequences}, 2) twin-prime \footnote[2]{sequences}, 3) quadratic residue \footnote[3]{sequences}, and 4) Hall \foonote[4]{sequences}.