In recent years packet-filtering firewalls have seen some impressive technological advances (e.g., stateful inspection, transparency, performance, etc.) and wide-spread deployment. In contrast, firewall and security management technology is lacking. In this paper we present Firmato, a firewall management toolkit, with the following distinguishing properties and components: (1) an entity-relationship model containing, in a unified form, global knowledge of the security policy and of the network topology; (2) a model definition language, which we use as an interface to define an instance of the entity-relationship model; (3) a model compiler, translating the global knowledge of the model into firewall-specific configuration files; and (4) a graphical firewall rule illustrator. We implemented a prototype of our toolkit to work with several commercially available firewall products. This prototype was used to control an operational firewall for several months. We believe that our approach is an important step toward streamlining the process of configuring and managing firewalls, especially in complex, multi-firewall installations.

We investigate the problem of self-stabilizing round-robin token management on a bidirectional ring of identical processors. Each processor is an asynchronous probabilistic finite state (i.e., constant space) machine which sends and receives constant-size messages and whose state transition is triggered by the receipt of a message. We also show that this problem is equivalent to symmetry breaking (i.e., leader election). Wejustify and suggest a two-layer (hardware and software) solution to the token management problem: The subproblem of reducing an arbitrary but nonzero number of tokens (in an otherwise arbitrary initial system state) to exactly one token (and a legal system state) is solved in hardware and takes only small polynomial time. The detection of a complete lack of tokens (communication deadlock) is done by a software clock. In high-speed networks the hardware layer can be implemented using fast universal switches (i.e., finite state machines) independent of the size of the network. We note that randomization is essential, since Dijkstra showed that for arbitrary rings the subproblem does not have a deterministic solution (regardless of the computational power of the identical processors). The use of the software layer (deadlock detection) in our solution is minimized.

Today, even a moderately sized corporate intranet contains multiple firewalls and routers, which are all used to enforce various aspects of the global corporate security policy. Configuring these devices to work in unison is difficult, especially if they are made by different vendors. Even testing or reverse engineering an existing configuration (say when a new security administrator takes over) is hard. Firewall configuration files are written in low level formalisms, whose readability is comparable to assembly code, and the global policy is spread over all the firewalls that are involved. To alleviate some of these difficulties, we designed and implemented a novel firewall analysis tool. Our software allows the administrator to easily discover and test the global firewall policy (either a deployed policy or a planned one). Our tool uses a minimal description of the network topology and directly parses the various vendor-specific low level configuration files. It interacts with the user through a query-and-answer session, which is conducted at a much higher level of abstruction. A typical question our tool can answer is "from which machines can our DMZ be reached and with which services?" Thus, the tool complements existing vulnerability analysis tools, as it can be used before a policy is actually deployed it operates on a more understandable level of abstraction, and it deals with all the firewalls at once.

Typically, bandwidth reservation is not made for data applications. Therefore, the only way to provide minimum bandwidth guarantees to such an application is by using a fairness mechanism to regulate the access to the network and by controlling the packet loss (i.e., congestion) inside the network. There are numerous works treating fairness in ring networks, however, there are almost no such works on fairness in arbitrary topology networks. The context of this work is fairness in an arbitrary topology network, the MetaNet, which employs convergence routing, a loss-free routing technique which is a variant on deflection routing. We note that minimum bandwidth guarantee combined with loss-free routing are the desired quality-of-service (QoS) attributes for most data applications. While developing the mechanisms, we also present performance measures to assess the new access- and flow-control algorithm: i) locality and congestion-driven-only the subnetwork containing conflicting traffic streams becomes involved in the fairness regulation. Furthermore, the fairness regulation is activated only when congestion occurs. This implies that when there is no congestion, nodes can access the network immediately and freely, which is a key requirement for distributed computing. ii) Scalability-the data-structure sizes used in the algorithm are a function of the switching node degree, and use constant space control signals of two bits only (the ATM standard, for example, dedicates four bits in the header of each cell to generic flow-control). iii) Linear access time in the congested subnetwork-measured by "the maximal clique in what we call the conflict graph to which a node belongs," and a frequency which is inverse linear in this parameter (when the traffic pattern stabilizes).

The design of simple cryptographic protocols for elementary two-party (session oriented) tasks (such as entity authentication and key transport) has had a history (starting with [NS78]) where security has been quite evasive. Only recently we have seen protocol designs which are both provably secure and efficient

In recent years, packet filtering firewalls have seen some impressive technological advances (e.g., stateful inspection, transparency, performance, etc.) and widespread deployment. In contrast, firewall and security management technology is lacking. We present Firmato, a firewall management toolkit, with the following distinguishing properties and components: (1) an entity relationship model containing, in a unified form, global knowledge of the security policy and of the network topology; (2) a model definition language, which we use as an interface to define an instance of the entity relationship model; (3) a model compiler translating the global knowledge of the model into firewall-specific configuration files; and (4) a graphical firewall rule illustrator. We demonstrate Firmato's capabilities on a realistic example, thus showing that firewall management can be done successfully at an appropriate level of abstraction. We implemented our toolkit to work with a commercially available firewall product. We believe that our approach is an important step towards streamlining the process of configuring and managing firewalls, especially in complex, multi firewall installations.

This paper introduces a cryptographic engine, Janus, which assists clients in establishing and maintaining secure and pseudonymous relationships with multiple servers. The setting is such that clients reside on a particular subnet (e.g., corporate intranet, ISP) and the servers reside anywhere on the Internet. The Janus engine allows each client-server relationship to use either weak or strong authentication on each interaction. At the same time, each interaction preserves privacy by neither revealing a clients true identity (except for the subnet) nor the set of servers with which a particular client interacts. Furthermore, clients do not need any secure long-term memory, enabling scalability and mobility. The interaction model extends to allow servers to send data back to clients via e-mail at a later date. Hence, our results complement the functionality of current network anonymity tools and remailers. The paper also describes the design and implementation of the Lucent Personalized Web Assistant (LPWA), which is a practical system that provides secure and pseudonymous relations with multiple servers on the Internet. LPWA employs the Janus function to generate site-specific personæ, which consist of alias usernames, passwords, and e-mail addresses.

We introduce a new scheduling problem that is motivated by applications in the area of access and flow control in high-speed and wireless networks. An instance of the problem consists of a set of persistent tasks that have to be scheduled repeatedly. Each task has a demand to be scheduled "as often as possible." There is no explicit limit on the number of tasks that can be scheduled concurrently. However, such limits are imposed implicitly because some tasks may be in conflict and cannot be scheduled simultaneously. These conflicts are presented in the form of a conflict graph. We define parameters which quantify the fairness and regularity of a given schedule. We then proceed to show lower bounds on these parameters and present fair and efficient scheduling algorithms for the case where the conflict graph is an interval graph. Some of the results presented here extend to the case of perfect graphs and circular-arc graphs as well.

Max-min fairness has been recognized as an optimal throughput-fairness definition. However, its realization in packet switching networks and its computational requirements have not yet been understood. We attempt to take a step in this direction, in the context of local area network (LAN) traffic. The max-min definition is given in terms of transmission rates of sources sending to their destinations (sessions). In order to realize max-min rates in a packet switching environment, transmission schedules of packets need to be realized. We first show that finding max-min fair schedules (with given rates) requires global state and timing information of all the nodes in the network. We then design a local scheduling algorithm for ring and bus networks with minimum transmission-delay, concurrent access, and spatial bandwidth reuse. This distributed algorithm uses only partial state information and is based on locally exchanging simple signals only between directly conflicting sessions (sessions which share at least one link) rather than collecting global information. The results of this algorithm are novel in various ways: (1) we prove that each session has an access-delay of at most twice its bottleneck link; (2) we show that the algorithm operates adaptively with an optimal access-delay in a dynamic environment (bursty traffic sources); and (3) by means of simulation experiments we further show that this algorithm achieves, in a steady-state, max-min fair rates for a vast majority of sessions and an average aggregate throughput which is 99 percent the throughput obtained by max-min fair rates.

To provide a logic for reasoning about concurrently executing programs, Abrahamson has defined an extension of propositional dynamic logic (PDL) by allowing interleaving as an operator for combining programs, in addition to the regular PDL operators union, concatenation, and star. We show that the satisfiability problem for interleaving PDL is complete for deterministic double-exponential time, and that this problem requires time double-exponential in cnlog n for some positive constant c. Moreover, this lower bound holds even when restricted to formulas where each program appearing in the formula has the form a1¦a2¦ … ¦ak where ¦ denotes the interleaving operator and where a1, …, ak are regular programs, i.e., programs built from atomic programs using only the regular operators. Another consequence of the method used to prove this result is that the equivalence problem for regular expressions with interleaving requires space 2cnlog n and that this lower bound holds even to decide whether (E1¦E2¦ … ¦Ek) ∪ F ≡ ∑∗ where E1, …, Ek, F are ordinary regular expressions; this improves a previous result of the authors. Moreover, the same lower bound holds for the containment problem for expressions of the form E1¦E2¦ … ¦Ek.

Byzantine Agreement among processors is a basic primitive in distributed computing. It comes in a number of basic fault models: "Crash", "Omission" and "Malicious" adversarial behaviors. The message complexity of the primitive has been known for the strong failure models of Malicious and Omission adversary since the early 80's, while the question for the more benign Crash failure model has been open. We show how to solve agreement in the presence of crash failures using O(n) messages which is optimal, thus settling a thirteen year old open problem. Our solution has almost linear time and our new algorithmic techniques have further implications: a family of "early stopping" agreement protocols with improved message-complexity; and a new solution to "Checkpoint" yielding a substantial improvement of the protocol for distributed work performance under adaptive parallelism in a network of workstations.

Article Free Access Share on Time-optimal message-efficient work performance in the presence of faults Authors: Roberto De Prisco Dept. of Computer Science, Columbia University, New York, NY and Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081 Baronissi (SA), Italy Dept. of Computer Science, Columbia University, New York, NY and Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081 Baronissi (SA), ItalyView Profile , Alain Mayer Dept. of Computer Science, Columbia University, New York, NY Dept. of Computer Science, Columbia University, New York, NYView Profile , Moti Yung IBM Research Division T.J. Watson Research Center, Yorktown Heights, NY IBM Research Division T.J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 161–172https://doi.org/10.1145/197917.198082Published:14 August 1994Publication History 48citation208DownloadsMetricsTotal Citations48Total Downloads208Last 12 Months20Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider regular expressions extended with the interleaving operator, and investigate the complexity of membership and inequivalence problems for these expressions. For expressions using the operators union, concatenation, Kleene star, and interleaving, we show that the inequivalence problem (deciding whether two given expressions do not describe the same set of words) is complete for exponential space. Without Kleene star, we show that the inequivalence problem is complete for the class Σp2 at the second level of the polynomial-time hierarchy. Certain cases of the membership problem (deciding whether a given word is in the language described by a given expression) are shown to be NP-complete. It is also shown that certain languages can be described exponentially more succinctly by using interleaving.

We investigate the problem of self-stabilizing round-robin token management scheme on an anonymous bidirectional ring of identical processors, where each processor is an asynchronous probabilistic (coin-flipping) finite state machine which sends and receives messages. We show that the solution to this problem is equivalent to symmetry breaking (i.e., leader election). Requiring only constant-size messages and message-passing model has practical implications: our solution can be implemented in high-speed networks using a universal fast hardware switches (i.e., finite state machines) of size independent of the size of the network. Our automata-based message-passing model has inherent deadlock possibility (i.e., when all processors are waiting for a message) which we assume is detected by an external timeout mechanism. Provided that there is no deadlock to begin with, we show how starting from an arbitrary con guration, the system never enters a deadlock state and further stabilizes in polynomial time. We note that Dijkstra showed that the last problem does not have a deterministic solution (even when the identical processors possess an arbitrary power): starting from a ring with a multitude of tokens, any deterministic system will either not stabilize or will enter a deadlock state.