Anomaly detection in network traffic is critical for identifying deviations from normal behavior—including sophisticated cyber threats and previously unseen attacks—especially when anomalous examples are absent from the training data. The escalating complexity of cyber-attacks necessitates developing methods that not only identify low-likelihood traffic but also provide insights into its anomalous nature and deviations from normal behavior, enabling effective response and troubleshooting. In this work, we leverage the unique capabilities of normalizing flows (NF), a state-of-the-art reversible generative model for exact density estimation, to detect anomalies using only normal traffic. Our approach fundamentally differs from previous methods by utilizing NF’s exact likelihood computation for unsupervised detection and combining it with Shapley values to introduce a novel feature selection framework for guiding the selection of discriminative features in anomaly detection, while also providing statistically grounded enhanced explanations for detected anomalies, pinpointing potential root causes. Through experiments on CICIoT-2023, ISCXTor2016, and CICIDS2017, we demonstrate that our NF-based approach outperforms existing state-of-the-art methods for unsupervised anomaly detection. Notably, on the CICIoT-2023 dataset, we achieve an accuracy of 0.9951, comparable or higher than supervised methods, despite being trained solely on normal data.

Human-chosen passwords are the dominant form of authentication systems. Passwords strength estimators are used to help users avoid picking weak passwords by predicting how many attempts a password cracker would need until it finds a given password. In this paper we propose a novel password strength estimator, called PESrank, which accurately models the behavior of a powerful password cracker. PESrank calculates the rank of a given password in an optimal descending order of likelihood. PESrank estimates a given password’s rank in fractions of a second – without actually enumerating the passwords – so it is practical for online use. It also has a training time that is drastically shorter than previous methods. Moreover, PESrank is efficiently tweakable to allow model personalization in fractions of a second, without the need to retrain the model; and it is explainable: it is able to provide information on why the password has its calculated rank, and gives the user insight on how to pick a better password. We implemented PESrank in Python and conducted an extensive evaluation study of it. We also integrated it into the registration page of a course at our university. Even with a model based on 905 million passwords, the response time was well under 1 second, with up to a 1-bit accuracy margin between the upper bound and the lower bound on the rank.

Cyber-Physical Systems (CPS) are becoming increasingly critical for the well-being of society (e.g., electricity generation and distribution, water treatment, implantable medical devices etc. ). While the convergence of computing, communications and physical control in such systems provides benefits in terms of efficiency and convenience, the attack surface resulting from this convergence poses unique security and privacy challenges. These systems represent the new frontier for cyber risk. CPS-SPC is an annual forum in its 5th edition this year, that aims to provide a focal point for the research community to begin addressing the security and privacy challenges of CPS in a comprehensive and multidisciplinary manner and, in tandem with other efforts, build a comprehensive research road map. Related Workshop Proceedings are available in the ACM DL at: https://dl.acm.org/citation.cfm?id=3338499

Traffic of Industrial Control System (ICS) between the Human Machine Interface (HMI) and the Programmable Logic Controller (PLC) is known to be highly periodic. However, it is sometimes multiplexed, due to asynchronous scheduling. Modeling the network traffic patterns of multiplexed ICS streams using Deterministic Finite Automata (DFA) for anomaly detection typically produces a very large DFA and a high false-alarm rate. In this article, we introduce a new modeling approach that addresses this gap. Our Statechart DFA modeling includes multiple DFAs, one per cyclic pattern, together with a DFA-selector that de-multiplexes the incoming traffic into sub-channels and sends them to their respective DFAs. We demonstrate how to automatically construct the statechart from a captured traffic stream. Our unsupervised learning algorithms first build a Discrete-Time Markov Chain (DTMC) from the stream. Next, we split the symbols into sets, one per multiplexed cycle, based on symbol frequencies and node degrees in the DTMC graph. Then, we create a sub-graph for each cycle and extract Euler cycles for each sub-graph. The final statechart is comprised of one DFA per Euler cycle. The algorithms allow for non-unique symbols, which appear in more than one cycle, and also for symbols that appear more than once in a cycle. We evaluated our solution on traces from a production ICS using the Siemens S7-0x72 protocol. We also stress-tested our algorithms on a collection of synthetically-generated traces that simulated multiplexed ICS traces with varying levels of symbol uniqueness and time overlap. The algorithms were able to split the symbols into sets with 99.6% accuracy. The resulting statechart modeled the traces with a median false-alarm rate of as low as 0.483%. In all but the most extreme scenarios, the Statechart model drastically reduced both the false-alarm rate and the learned model size in comparison with the naive single-DFA model.

Since firewalls need to filter all the traffic crossing the network perimeter, they should be able to sustain a very high throughput, or risk becoming a bottleneck. Firewall packet matching can be viewed as a point location problem: Each packet (point) has five fields (dimensions), which need to be checked against every firewall rule in order to find the first matching rule. Thus, algorithms from computational geometry can be applied. In this paper, we consider a classical algorithm that we adapted to the firewall domain. We call the resulting algorithm “Geometric Efficient Matching” (GEM). The GEM algorithm enjoys a logarithmic matching time performance. However, the algorithm's theoretical worst-case space complexity is O(n4) for a rule-base with n rules. Because of this perceived high space complexity, GEM-like algorithms were rejected as impractical by earlier works. Contrary to this conclusion, this paper shows that GEM is actually an excellent choice. Based on statistics from real firewall rule-bases, we created a Perimeter rules model that generates random, but nonuniform, rule-bases. We evaluated GEM via extensive simulation using the Perimeter rules model. Our simulations show that on such rule-bases, GEM uses near-linear space, and only needs approximately 13 MB of space for rule-bases of 5,000 rules. Moreover, with use of additional space improving heuristics, we have been able to reduce the space requirement to 2-3 MB for 5,000 rules. But most importantly, we integrated GEM into the code of the Linux iptables open-source firewall, and tested it on real traffic loads. Our GEM-iptables implementation managed to filter over 30,000 packets-per-second on a standard PC, even with 10,000 rules. Therefore, we believe that GEM is an efficient and practical algorithm for firewall packet matching.

We present a dictionary attack that is based on keyboard acoustic emanations. We combine signal processing and efficient data structures and algorithms, to successfully reconstruct single words of 7-13 characters from a recording of the clicks made when typing them on a keyboard. Our attack does not require any training, and works on an individual recording of the typed word (may be under 5 seconds of sound). The attack is very efficient, taking under 20 seconds per word on a standard PC. We demonstrate a 90% or better success rate of finding the correct word in the top 50 candidates identified by the attack, for words of 10 or more characters, and a success rate of 73% over all the words we tested. We show that the dominant factors affecting the attack's success are the word length, and more importantly, the number of repeated characters within the word. Our attack can be used as an effective acoustic-based password cracker. Our attack can also be used as part of an acoustic long-text reconstruction method, that is much more efficient and requires much less text than previous approaches.

Stack smashing is still one of the most popular techniques for computer system attack. In this work, we present an anti-stack-smashing defense technique for Microsoft Windows systems. Our approach works at install-time, and does not rely on having access to the source-code: The user decides when and which executables to vaccinate. Our technique consists of instrumenting a given executable with a mechanism to detect stack smashing attacks. We developed a prototype implementing our technique and verified that it successfully defends against actual exploit code. We then extended our prototype to vaccinate DLLs, multithreaded applications, and DLLs used by multithreaded applications, which present significant additional complications. We present promising performance results measured on SPEC2000 benchmarks: Vaccinated executables were no more than 8 percent slower than their un-vaccinated originals.

We present an anti-pirate revocation scheme for broadcast encryption systems (e.g., pay TV), in which the data is encrypted to ensure payment by users. In the systems we consider, decryption of keys is done on smartcards and key management is done in-band. Our starting point is a scheme of Naor and Pinkas. Their basic scheme uses secret sharing to remove up to t parties, is information-theoretic secure against coalitions of size t , and is capable of creating a new group key. However, with current smartcard technology, this scheme is only feasible for small system parameters, allowing up to about 100 pirates to be revoked before all the smartcards need to be replaced. We first present a novel implementation method of their basic scheme that distributes the work among the smartcard, set-top terminal, and center. Based on this, we construct several improved schemes for many revocation rounds that scale to realistic system sizes. We allow up to about 10,000 pirates to be revoked using current smartcard technology before recarding is needed. The transmission lengths of our constructions are on par with those of the best tree-based schemes. However, our constructions have much lower smartcard CPU complexity: only O (1) smartcard operations per revocation round (a single 10-byte field multiplication and addition), as opposed to the complexity of the best tree-based schemes, which is polylogarithmic in the number of users. We evaluate the system behavior via an exhaustive simulation study coupled with a queueing theory analysis. Our simulations show that with mild assumptions on the piracy discovery rate, our constructions can perform effective pirate revocation for realistic broadcast encryption scenarios.

The goal of this work is to model the peering arrangements between autonomous systems (ASes). Most existing models of the AS-graph assume an undirected graph. However, peering arrangements are mostly asymmetric customer-provider arrangements, which are better modeled as directed edges. Furthermore, it is well known that the AS-graph, and in particular its clustering structure, is influenced by geography. We introduce a new model that describes the AS-graph as a directed graph, with an edge going from the customer to the provider, but also models symmetric peer-to-peer arrangements. In addition, our model takes geography into account. We are able to mathematically analyze its power-law exponent and number of leaves. Beyond the analysis, we have implemented our model as a synthetic network generator called GDNG. Experimentation with GDNG shows that the networks it produces are more realistic than those generated by other network generators, in terms of its power-law exponent, fractions of customer-provider and symmetric peering arrangements, and the size of its dense core. We believe that our model is the first to manifest realistic regional dense cores that have a clear geographic flavor. Our synthetic networks also exhibit path inflation effects that are similar to those observed in the real AS graph.

This paper describes the implementation of an attack on the Bluetooth security mechanism. Specifically, we describe a passive attack, in which an attacker can find the PIN used during the pairing process. We then describe the cracking speed we can achieve through three optimizations methods. Our fastest optimization employs an algebraic representation of a central cryptographic primitive (SAFER+) used in Bluetooth. Our results show that a 4-digit PIN can be cracked in less than 0.3 sec on an old Pentium III 450MHz computer, and in 0.06 sec on a Pentium IV 3Ghz HT computer.

A contactless smartcard is a smartcard that can communicate with other devices without any physical connection, using Radio-Frequency Identifier (RFID) technology. Contactless smartcards are becoming increasingly popular, with applications like credit-cards, national-ID, passports, physical access. The security of such applications is clearly critical. A key feature of RFID-based systems is their very short range: typical systems are designed to operate at a range of ≈ 10cm. In this study we show that contactless smartcard technology is vulnerable to relay attacks: An attacker can trick the reader into communicating with a victim smartcard that is very far away. A "low-tech" attacker can build a pick-pocket system that can remotely use a victim contactless smartcard, without the victim’s knowledge. The attack system consists of two devices, which we call the "ghost" and the "leech". We discuss basic designs for the attacker’s equipment, and explore their possible operating ranges. We show that the ghost can be up to 50m away from the card reader— 3 orders of magnitude higher than the nominal range. We also show that the leech can be up to 50cm away from the the victim card. The main characteristics of the attack are: orthogonality to any security protocol, unlimited distance between the attacker and the victim, and low cost of the attack system.

In this paper we analyze the E₀ cipher, which is the encryption system used in the Bluetooth specification. We suggest a uniform framework for cryptanalysis of the E₀ cipher. Our method requires 128 known bits of the keystream in order to recover the initial state of the LFSRs, which reflects the secret key of this encryption engine. In one setting, our framework reduces to an attack of D. Bleichenbacher. In another setting, our framework is equivalent to an attack presented by Fluhrer and Lucks. Our best attack can recover the initial state of the LFSRs after solving 2⁸⁶ boolean linear systems of equations, which is roughly equivalent to the results obtained by Fluhrer and Lucks.

Distance estimation is important to many Internet applications. It can aid a World Wide Web client when selecting among several potential candidate servers or among candidate peer-to-peer servers. It can also aid in building efficient overlay or peer-to-peer networks that react dynamically to changes in the underlying Internet. One of the approaches to distance (i.e., time delay) estimation in the Internet is based on placing tracer stations in key locations and conducting measurements between them. The tracers construct an approximated map of the Internet after processing the information obtained from these measurements. This work presents a novel algorithm, based on algebraic tools, that computes additional distances, which are not explicitly measured. As such, the algorithm extracts more information from the same amount of measurement data. Our algorithm has several practical impacts. First, it can reduce the number of tracers and measurements without sacrificing information. Second, our algorithm is able to compute distance estimates between locations where tracers cannot be placed. To evaluate the algorithm's performance, we tested it both on randomly generated topologies and on real Internet measurements. Our results show that the algorithm computes up to 50%-200% additional distances beyond the basic tracer-to-tracer measurements.

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.

The IEEE 802.11 wireless local area network standard did not incorporate a cryptographic message integrity code into its wired equivalent privacy (WEP) protocol, and relied upon CRC-32 for message integrity. This was shown to be completely insecure since WEP uses a stream cipher (RC4) for encryption. The latest IEEE 802.11i draft addresses this, and other, weaknesses discovered in WEP. IEEE 802.11i suggests three new modes of operation: two based on the Advanced Encryption Standard cipher and one [temporal key integrity protocol (TKIP)] still based on RC4. The TKIP mode is intended for use on legacy hardware, which is computationally weak. TKIP uses a new, keyed, 64-b, message integrity code called Michael. In this letter, we highlight a weakness in Michael and suggest a simple fix.

We present an anti-pirate revocation scheme for broadcast encryption systems (e.g., pay TV), in which the data is encrypted to ensure payment by users. In the systems we consider decryption of keys is done on smart cards and key management is done in-band. Our starting point is a recent scheme of Naor and Pinkas. The basic scheme uses secret sharing to remove up to t parties, is information theoretic secure against coalitions of size t, and is capable of creating a new group key. However with current smart card technology, this scheme is only feasible for small system parameters, allowing up to about 100 pirates to be revoked before all the smart cards need to be replaced. We first present a novel implementation method of their basic scheme that distributes the work in novel ways among the smart card, set-top terminal, and center. Based on this, we construct several improved schemes for many stateful revocation rounds that scale to realistic system sizes. We allow up to about 10000 pirates to be revoked using current smart card technology before re-carding is needed. The transmission lengths of our constructions are on a par with those of the best tree-based schemes. However, our constructions have much lower smartcard CPU complexity: only O(1) smartcard operations per revocation round, as opposed to a poly-logarithmic complexity of the best tree-based schemes. We evaluate the system behavior via an exhaustive simulation study. Our simulations show that with mild assumptions on the piracy discovery rate, our constructions can perform effective pirate revocation for realistic broadcast encryption scenarios.

A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication, and dissemination of information. When the elements may fail, a user of a distributed protocol needs to quickly find a quorum all of whose elements are alive or evidence that no such quorum exists. This is done by probing the system elements, one at a time, to determine if they are alive or dead. This paper studies the probe complexity $\cal{PC(S)}$ of a quorum system $\cal{S}$, defined as the worst case number of probes required to find a live quorum or to show its nonexistence in $\cal{S}$, using the best probing strategy. We show that for large classes of quorum systems, all n elements must be probed in the worst case. Such systems are called evasive. However, not all quorum systems are evasive; we demonstrate a system where O(log n) probes always suffice. Then we prove two lower bounds on the probe complexity in terms of the minimal quorum cardinality $c \cal{(S)}$ and the number of minimal quorums $m\cal{(S)}$. Finally, we show a universal probe strategy which never makes more than $c {\cal(S)}^2 - c{\cal(S)}+ 1$ probes; thus any system with $c{\cal(S)}\le\sqrt n $ is nonevasive.

Distance estimation is important to many Internet applications, most notably for a WWW client that needs to select a server among several potential candidates. Current approaches to distance (i.e., time delay) estimation in the Internet are based on placing Tracer stations in key locations and conducting measurements between them. The Tracers construct an approximated map of the Internet after processing the information obtained from these measurements. This work presents a novel algorithm, based on algebraic tools, that computes additional distances, which are not explicitly measured. As such, the algorithm extracts more information from the same amount of measurement data. Our algorithm has several practical imparts. First, it can reduce the number of Tracers and measurements without sacrificing information. Second, our algorithm is able to compute distance estimates between locations where Tracers cannot be placed. This is especially important when unidirectional measurements are conducted, since such measurements require specialized equipment which cannot be placed everywhere. To evaluate the algorithm's performance, we tested it both on randomly generated topologies and on real Internet measurements. Our results show that the algorithm computes up to 50-200% additional distances beyond the basic Tracer-to-Tracer measurements.

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.

Replicated services accessed via quorums enable each access to be performed at only a subset (quorum) of the servers and achieve consistency across accesses by requiring any two quorums to intersect. Recently, b-masking quorum systems, whose intersections contain at least 2b+1 servers, have been proposed to construct replicated services tolerant of b-arbitrary (Byzantine) server failures. In this paper we consider a hybrid fault model allowing benign failures in addition to the Byzantine ones. We present four novel constructions for b-masking quorum systems in this model, each of which has optimal load (the probability of access of the busiest server) or optimal availability (probability of some quorum surviving failures). To show optimality we also prove lower bounds on the load and availability of any b-masking quorum system in this model.

We consider broadcast applications where the transmissions need to be encrypted, such as direct broadcast digital TV networks or Internet multicast. In these applications the number of encrypted TV programs may be very large, but the secure memory capacity at the set-top terminals (STT) is severely limited due to the need to withstand pirate attacks and hardware tampering. Despite this, we would like to allow the service provider to offer different packages of programs to the users. A user who buys a package should be able to view every program belonging to that package, but nothing else. A flexible scheme should allow for packages of various sizes to be offered, from a single program up to all the programs. We suggest two novel schemes to manage the encryption keys for these applications. The schemes are highly flexible, and understandable to users, yet require very few keys to be stored in the STTs' secure memory. The computational power required of the STTs is very low. The security of these schems is as good or better than that offered by current technology.

The problem we address is how to communicate securely with a set of users (the target set) over an insecure broadcast channel. This problem occurs in two application domains: satellite/cable pay TV and the Internet MBone. In these systems, the parameters of major concern are the number of key transmissions and the number of keys held by each receiver. In the Internet domain, previous schemes suggest building a separate key tree for each multicast program, thus incurring a setup cost of at least k log k per program for target sets of size k. In the pay TV domain, a single key structure is used for all programs, but known theoretical bounds show that either very long transmissions are required, or that each receiver needs to keep prohibitively many keys. Our approach is targeted at both domains. Our schemes maintain a single key structure that requires each receiver to keep only a logarithmic number of establishment keys for its entire lifetime. At the same time our schemes admit low numbers of transmissions. In order to achieve these goals, and to break away from the theoretical bounds, we allow a controlled number of users outside the target set to occasionally receive the multicast. This relaxation is appropriate for many scenarios in which the encryption is used to force consumers to pay for a service, rather than to withhold sensitive information. For this purpose, we introduce f-redundant establishment key allocations, which guarantee that the total number of recipients is no more than f times the number of intended recipients. We measure the performance of such schemes by the number of key transmissions they require, by their redundancy f, and by the probability that a user outside the target set (a free-rider) will be able to decrypt the multicast. We prove a new lower bound, present several new establishment key allocations, and evaluate our schemes' performance by extensive simulation.

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.

Monitoring the location of customer equipment is an important problem in the direct broadcasting sateMte indw try.This is because the service providers wotdd We to pr~ vent unauthorized movement of a customer's set top terminal (STT) from a home to a pubtic venue, or acro~an international border, due to tious kancid, copyright and po~ticd issues.h this paper we study four schemw for detecting the movement of the an STT using the ~ting (or emerging) communication tiastructttre.We start with the currently used scheme which is based on the telephone network's ~ or Cm (cdlw-~) featurw, and show how it can be undermined.Then we suggest three new schem= which are more robust than the cder ~scheme one that that uses the Globrd Positioning System (GPS), one that uses the cefldar phone's enhanced 911 (E911) service, and one that mea-sur~the tim~Werenceof-arriti of the sat eMte's broadcast.We ~the accuracy, featur~and vtdnerabtities of ed scheme.We *O present possible attacks that Mow pirates to coned their movement when these schemw are employed._-.

Article Free Access Share on Key management for encrypted broadcast Author: Avishai Wool Bell Laboratories, Lucent Technologies, 700 Mountain Ave., Murray Hill, NJ Bell Laboratories, Lucent Technologies, 700 Mountain Ave., Murray Hill, NJView Profile Authors Info & Claims CCS '98: Proceedings of the 5th ACM conference on Computer and communications securityNovember 1998 Pages 7–16https://doi.org/10.1145/288090.288096Published:01 November 1998Publication History 8citation573DownloadsMetricsTotal Citations8Total Downloads573Last 12 Months6Last 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

In this paper we present probabilistic masking quorum systems, a technique for replicating data that can mask, with high probability, the arbitrary (Byzantine) failure of data servers from clients. This technique generalizes previous work on probabilistic quorum systems to mask Byzantine server failures in their full generality, and improves over previous masking quorum systems by offering better data availability and access efficiency. We define probabilistic masking quorum systems, demonstrate a novel access protocol for implementing replicated data with them, and prove general and tight lower bounds on the performance that they can achieve. We also present a probabilistic masking quorum construction that outperforms strict masking constructions in measures of both availability and efficiency.

Previous papers have postulated that traditional schemes for the management of replicated data are doomed to failure in practice due to a quartic (or worse) explosion in the probability of deadlocks. In this paper, we present results of a simulation study for three recently introduced protocols that guarantee global serializability and transaction atomicity without resorting to the two-phase commit protocol. The protocols analyzed in this paper include a global locking protocol [10], a “pessimistic” protocol based on a replication graph [5], and an “optimistic” protocol based on a replication graph [7]. The results of the study show a wide range of practical applicability for the lazy replica-update approach employed in these protocols. We show that under reasonable contention conditions and sufficiently high transaction rate, both replication-graph-based protocols outperform the global locking protocol. The distinctions among the protocols in terms of performance are significant. For example, an offered load where 70% - 80% of transactions under the global locking protocol were aborted, only 10% of transactions were aborted under the protocols based on the replication graph. The results of the study suggest that protocols based on a replication graph offer practical techniques for replica management. However, it also shows that performance deteriorates rapidly and dramatically when transaction throughput reaches a saturation point.

A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication, and dissemination of information. Given a strategy to pick quorums, the load LS is the minimal access probability of the busiest element, minimizing over the strategies. The capacity \capS\ is the highest quorum accesses rate that cS can handle, so $\capS=1/\LS$. The availability of a quorum system cS is the probability that at least one quorum survives, assuming that each element fails independently with probability p. A tradeoff between LS and the availability of cS is shown. We present four novel constructions of quorum systems, all featuring optimal or near optimal load, and high availability. The best construction, based on paths in a grid, has a load of $O(1/\sqn)$, and a failure probability of $\exp(-\Omega(\sqn))$ when the elements fail with probability $p < \half$. Moreover, even in the presence of faults, with exponentially high probability the load of this system is still $O(1/\sqn)$. The analysis of this scheme is based on percolation theory.

We suggest a method of controlling the access to a secure database via quorum systems. A quorum system is a collection of sets (quorums) every two of which have a nonempty intersection. Quorum systems have been used for a number of applications in the area of distributed systems. We propose a separation between access servers, which are protected and trustworthy, but may be outdated, and the data servers, which may all be compromised. The main paradigm is that only the servers in a complete quorum can collectively grant (or revoke) access permission. The method we suggest ensures that, after authorization is revoked, a cheating user Alice will not be able to access the data even if many access servers still consider her authorized and even if the complete raw database is available to her. The method has a low overhead in terms of communication and computation. It can also be converted into a distributed system for issuing secure signatures. An important building block in our method is the use of secret sharing schemes that realize the access structures of quorum systems. We provide several efficient constructions of such schemes which may be of interest in their own right.

Replicated services accessed via quorurmcnable each access to be performed at only a subset (quorum) of the servers, and achieve consistency across accesses by requiring any two quorums to intersect.Recently, bmasking quorum systems, whose intersections contain at least 2b+l servers, have been proposed to construct replicated services tolerant of barbitrary (B ymntine) server failures.In this paper we consider a hybrid fault model allowing benign failures in addition to the Byzantine ones.We present four novel constructions for bmasking quorum systems in this model, each of which has optimal load (the probability of access of the busiest server) or optimal availability (probabllit y of some quorum surviving failures).To show optimalit y we also prove lower bounds on the load and availabilityy of any bmasking quorum system in this model.I&mission to make digilnlflmrd copies of all or piIIIof(hi~nu}icri:ll fix personal or classroom use is grw!cd without ~cc prm idcd III;IIIIICcopies are not mwlc or distrihukd I'orpmlil or wmncrciid :IdvmIIogc.theCXWrlght notice, (he title of the pohlic:it ion mMlils d:IIcnppcw.xnd WIicc is given that urpyrighl is hy pwmission OI"IIW ACM, INC. '1"0 copy otherwise.to republish, In post on wrws or to rcdistrihu[c 10 lists.ruplircs specilic pem~ission andlor 13c 1997 I'OD(' 97 .Srlnta 13m+ora [ '.4 1 I*Y.4

Article Access control and signatures via quorum secret sharing Share on Authors: Moni Naor Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile , Avishai Wool Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile Authors Info & Claims CCS '96: Proceedings of the 3rd ACM conference on Computer and communications securityJanuary 1996 Pages 157–168https://doi.org/10.1145/238168.238209Online:01 January 1996Publication History 23citation613DownloadsMetricsTotal Citations23Total Downloads613Last 12 Months8Last 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 SiteGet Access

No abstract available.

Article How to be an efficient snoop, or the probe complexity of quorum systems (extended abstract) Share on Authors: David Peleg Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile , Avishai Wool Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile Authors Info & Claims PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computingMay 1996 Pages 290–299https://doi.org/10.1145/248052.248112Online:01 May 1996Publication History 15citation207DownloadsMetricsTotal Citations15Total Downloads207Last 12 Months2Last 6 weeks1 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 SiteGet Access

Article Crumbling walls: a class of practical and efficient quorum systems Share on Authors: David Peleg Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile , Avishai Wool Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, IsraelView Profile Authors Info & Claims PODC '95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computingAugust 1995 Pages 120–129https://doi.org/10.1145/224964.224978Online:20 August 1995Publication History 23citation309DownloadsMetricsTotal Citations23Total Downloads309Last 12 Months2Last 6 weeks1 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 SiteGet Access

A quorum system is a collection of sets (quorums) every two of which have a nonempty intersection. Quorum systems have been used for a number of applications in the area of distributed systems. We investigate the load, capacity and availability of quorum systems. We present four novel constructions of quorum system, all featuring optimal or near optimal load, and high availability. These desirable properties of the constructions translate into improvements of any protocol using them: a low work load on the processors and a high resilience to processor failures. The best construction, based on paths in a grid, has a load of O(1//spl radic/n), and a failure probability of exp(-O(/spl radic/n)) when the elements fail with probability p>