IEEE Transactions on Dependable and Secure Computing

PrePrint: SAT: A Security Architecture Achieving Anonymity and Traceability in Wireless Mesh Networks

Anonymity has received increasing attention in the literature due to the users' awareness of their privacy nowadays. Anonymity provides protection for users to enjoy network services without being traced. While anonymity related issues have been extensively studied in payment-based systems such as e-cash and peer-to-peer (P2P) systems, little effort has been devoted to wireless mesh networks (WMNs). On the other hand, the network authority requires conditional anonymity such that misbehaving entities in the network remain traceable. In this paper, we propose a security architecture to ensure unconditional anonymity for honest users and traceability of misbehaving users for network authorities in WMNs. The proposed architecture strives to resolve the conflicts between the anonymity and traceability objectives, in addition to guaranteeing fundamental security requirements including authentication, confidentiality, data integrity, and non-repudiation. Thorough analysis on security and efficiency is incorporated, demonstrating the feasibility and effectiveness of the proposed architecture.

IEEE Transactions on Dependable and Secure Computing - January-March 2010 (Vol. 7, No. 1)

PrePrint: Greedy Receivers in IEEE 802.11 Hotspots: Impacts and Detection

As wireless hotspot business becomes a tremendous financial success, users of these networks have increasing motives to misbehave in order to obtain more bandwidth at the expense of other users. Such misbehaviors threaten the performance and availability of hotspot networks, and have recently attracted increasing research attention. However the existing work so far focuses on sender-side misbehavior. Motivated by the observation that many hotspot users receive more traffic than they send, we study greedy receivers in this paper. We identify a range of greedy receiver misbehaviors, and quantify their damage using both simulation and testbed experiments. Our results show that even though greedy receivers do not directly control data transmission, they can still result in very serious damage, including completely shutting off the competing traffic. To address the issues, we further develop techniques to detect and mitigate greedy receiver misbehavior, and demonstrate their effectiveness.

PrePrint: An Architectural Approach to Preventing Code Injection Attacks

Code injection attacks, despite being well researched, continue to be a problem today. Modern architectural solutions such as the execute-disable bit and PaX have been useful in limiting the attacks, however they enforce program layout restrictions and can often times still be circumvented by a determined attacker. We propose a change to the memory architecture of modern processors that addresses the code injection problem at its very root by virtually splitting memory into code memory and data memory such that a processor will never be able to fetch injected code for execution. This virtual split memory system can be implemented as a software only patch to an operating system and can be used to supplement existing schemes for improved protection. Furthermore, our system is able to accommodate a number of response modes when a code injection attack occurs. Our experiments with both benchmark and real-world attacks show the system is effective in preventing a wide range of code injection attacks while incurring reasonable overhead.

PrePrint: Adaptive Fault Tolerant QoS Control Algorithms for Maximizing System Lifetime of Query-Based Wireless Sensor Networks

Data sensing and retrieval in wireless sensor systems have a widespread application in areas such as security and surveillance monitoring, and command and control in battlefields. In query-based wireless sensor systems, a user would issue a query and expect a response to be returned within the deadline. While the use of fault tolerance mechanisms through redundancy improves query reliability in the presence of unreliable wireless communication and sensor faults, it could cause the energy of the system to be quickly depleted. Therefore, there is an inherent tradeoff between query reliability vs. energy consumption in query-based wireless sensor systems. In this paper, we develop adaptive fault tolerant quality of service (QoS) control algorithms based on hop-by-hop data delivery utilizing “source” and “path” redundancy, with the goal to satisfy application QoS requirements while prolonging the lifetime of the sensor system. We develop a mathematical model for the lifetime of the sensor system as a function of system parameters including the “source” and “path” redundancy levels utilized. We discover that there exists optimal “source” and “path” redundancy under which the lifetime of the system is maximized while satisfying application QoS requirements. Numerical data are presented and validated through extensive simulation, with physical interpretations given, to demonstrate the feasibility of our algorithm design.

PrePrint: Chip Self-Organization and Fault-Tolerance in Massively Defective Multicore Arrays

We study chip self-organization and fault tolerance at the architectural level to improve dependable continuous operation of multicore arrays in massively defective nanotechnologies. Architectural self-organization results from the conjunction of self-diagnosis and self-disconnection mechanisms (to identify and isolate most permanently faulty or inaccessible cores and routers), plus self-discovery of routes to maintain the communication in the array. In the methodology presented in this work, chip self-diagnosis is performed in 3 steps, following an ascending order of complexity: interconnects are tested first, then routers through mutual test, and cores in the last step. The mutual testing of routers is especially important as faulty routers are disconnected by good ones with no assumption on the behavior of defective elements. Moreover, the disconnection of faulty routers is not physical (“hard”) but logical (“soft”) in that a good router simply stops communicating with any adjacent router diagnosed as defective. There is no physical reconfiguration in the chip and no need for spare elements. Ultimately, the multicore array may be viewed as a black box, which incorporates protection mechanisms and self-organizes while the external control reduces to a simple chip validation test which, in the simplest cases, reduces to counting the number of valid and accessible cores

PrePrint: Diagnosability of Two-Matching Composition Networks under the MM* Model

Diagnosability is an important metric for measuring the reliability of multiprocessor systems. In this paper, we study the diagnosability of a class of networks, called Two-Matching Composition Networks (2-MCNs), each of which is constructed by connecting two graphs via two perfect matchings. By applying our result to multiprocessor systems, we also compute the diagnosability of folded hypercubes and augmented cubes, both of which belong to two-matching composition networks.

PrePrint: On Complexity and Approximability of Optimal DoS Attacks on Multiple-Tree P2P Streaming Topologies

We investigate the hardness of malicious attacks on multiple-tree topologies of push-based Peer-to-Peer streaming systems. In particular, we study the optimization problem of finding a minimum set of target nodes to achieve a certain damage objective. For this, we differentiate between three natural and increasingly complex damage types: global packet loss, service loss when using Multiple Description Coding and service loss when using Forward Error Correction. We show that each of these attack problems is NP-hard, even for an idealized attacker with global knowledge about the topology. Despite tree-based topologies seem susceptible to such attacks, we can even prove that (under strong assumptions about NP) there is no polynomial time attacker, capable of guaranteeing a general solution quality within factors of $c_1 \log(n)$ and $c_2~2^{\log^{1-\delta} n}$ (with $n$ topology nodes, $\delta = 1 / \log\log^d n$ for $d<1/2$ and constants $c_1, c_2$), respectively. To our knowledge, these are the first lower bounds on the quality of polynomial time attacks on P2P streaming topologies. The results naturally apply to major real-world DoS attackers and show hard limits for their possibilities. In addition, they demonstrate superior stability of Forward Error Correction systems compared to Multiple Description Coding and give theoretical foundation to properties of stable topologies.

PrePrint: Replica Placement for Route Diversity in Tree-Based Routing Distributed Hash Tables

Distributed hash tables (DHTs) spread storage and routing responsibility among all nodes in the peer-to-peer network. These structures have bounded path length unlike unstructured networks. Unfortunately, nodes can deny access to keys or misroute lookups. We address both of these problems through replica placement. We characterize tree-based routing DHTs and define MAXDISJOINT, a replica placement that creates route diversity for these DHTs. We prove that this placement creates disjoint routes and find the replication degree necessary to produce a desired number of disjoint routes. Using simulations of Pastry (a tree-based routing DHT), we evaluate the impact of MAXDISJOINT on routing robustness compared to other placements when nodes are compromised at random or in a contiguous run. Furthermore, we consider another route diversity mechanism that we call neighbor set routing and show that, when used with our replica placement, it can successfully route messages to a correct replica even with a quarter of the nodes in the system compromised at random. Finally, we demonstrate a family of replica query strategies that can trade off response time and system load. We present a hybrid query strategy that keeps response time low without producing too high a load.

PrePrint: Cross Layer Detection of Sinking Behavior in Wireless Ad hoc Networks Using SVM and FDA

The uniqueness of security vulnerabilities in ad-hoc networks has given rise to the need for designing novel intrusion detection algorithms, different from those present in conventional networks. In this work, we propose an autonomous host-based intrusion detection system for detecting malicious sinking behavior. The proposed detection system maximizes the detection accuracy by using cross layer features to define a routing behavior. For learning and adaptation to new attack scenarios and network environments, two machine learning techniques are utilized. Support Vector Machines (SVM) and Fisher Discriminant Analysis (FDA) are used together to exploit the better accuracy of SVM and faster speed of FDA. Instead of using all cross layer features, features from MAC layer are associated/correlated with features from other layers, thereby reducing the feature set without reducing the information content. Various experiments are conducted with varying network conditions and malicious node behavior. The effects of factors such as mobility, traffic density and the packet drop ratios of the malicious nodes are analyzed. Experiments based on simulation show that the proposed cross layer approach aided by a combination of SVM and FDA performs significantly better than other existing approaches.

PrePrint: CASTLE: Continuously Anonymizing Data Streams

Most of existing privacy preserving techniques, such as k-anonymity methods, are designed for static data sets. As such, they cannot be applied to streaming data which are continuous, transient and usually unbounded. Moreover, in streaming applications, there is a need to offer strong guarantees on the maximum allowed delay between incoming data and the corresponding anonymized output. To cope with these requirements, in this paper, we present CASTLE (Continuously Anonymizing STreaming data via adaptive cLustEring), a cluster-based scheme that anonymizes data streams on-the-fly and, at the same time, ensures the freshness of the anonymized data by satisfying specified delay constraints. We further show how CASTLE can be easily extended to handle l-diversity. Our extensive performance study shows that CASTLE is efficient and effective w.r.t. the quality of the output data.

PrePrint: Securing Topology Maintenance Protocols for Sensor Networks

We analyze the security vulnerabilities of PEAS, ASCENT, and CCP, three well-known topology maintenance protocols (TMPs) for sensor networks. These protocols aim to increase the lifetime of the sensor network by only maintaining a subset of nodes in an active or awake state. We propose a meta-protocol (Meta-TMP) to represent the class of topology maintenance protocols. The Meta-TMP provides us with a better understanding of the characteristics and of how a specific TMP works, and it can be used to study the vulnerabilities of a specific TMP. We describe various types of malicious behavior and actions that can be carried out by an adversary to attack a wireless sensor network by exploiting the TMP being used in the network. We describe three attacks against these protocols that may be used to reduce the lifetime of the sensor network, or to degrade the functionality of the sensor application by reducing the network connectivity and the sensing coverage that can be achieved. Further, we describe countermeasures that can be taken to increase the robustness of the protocols and make them resilient to such attacks.

PrePrint: A Rigorous, Compositional, and Extensible Framework for Dynamic Fault Tree Analysis

Fault trees (FT) are among the most prominent formalisms for reliability analysis of technical systems. Dynamic FTs extend FTs with support for expressing dynamic dependencies among components. The standard analysis vehicle for DFTs is state-based, and treats the model as a CTMC, a continuous-time Markov chain. This is not always possible, as we will explain, since some DFTs allow multiple interpretations. This paper introduces a rigorous semantic interpretation of DFTs. The semantics is defined in such a way that the semantics of a composite DFT arises in a transparent manner from the semantics of its components. This not only eases the understanding of how the FT building blocks interact. It also is a key to alleviate the state explosion problem. By lifting a classical aggregation strategy to our setting, we can exploit the DFT structure to build the smallest possible Markov chain representation of the system. The semantics - as well as the aggregation and analysis engine is implemented in a tool, called CORAL. We show by a number of realistic and complex systems that this methodology achieves drastic reductions in the state space.

PrePrint: Comparative Evaluation of Spoofing Defenses

IP spoofing exacerbates many security threats, and reducing it would greatly enhance Internet security. Seven defenses that filter spoofed traffic have been proposed to date; three are designed for end-network deployment, while four assume some collaboration with core routers for packet marking or filtering. Because each defense has been evaluated in a unique setting, the following important questions remain unanswered: (1) Can end networks effectively protect themselves or is core support necessary? (2) Which defense performs best assuming sparse deployment? (3) How to select core participants to achieve best protection with fewest deployment points? This paper answers the above questions by: (1) Formalizing the problem of spoofed traffic filtering and defining novel effectiveness measures, (2) Observing each defense as "selfish" (it helps its participants) or "altruistic" (it helps everyone) and differentiating their performance goals, (3) Defining optimal core deployment points for defenses that need core support, and (4) Evaluating all defenses in a common and realistic setting. Our results offer a valuable insight into advantages and limitations of the proposed defenses, and uncover the relationship between any spoofing defense's performance and the Internet's topology.

PrePrint: Nymble: Blocking Misbehaving Users in Anonymizing Networks

Anonymizing networks such as Tor allow users to access Internet services privately by using a series of routers to hide the client's IP address from the server. The success of such networks, however, has been limited by users employing this anonymity for abusive purposes such as defacing popular websites. Website administrators routinely rely on IP-address blocking for disabling access to misbehaving users, but blocking IP addresses is not practical if the abuser routes through an anonymizing network. As a result, administrators block {\em all} known exit nodes of anonymizing networks, denying anonymous access to honest and dishonest users alike. To address this problem, we present Nymble, a system in which \emph{servers can blacklist misbehaving users without compromising their anonymity}. Our system is thus agnostic to different servers' definitions of misbehavior — servers can block users for whatever reason, and the privacy of blacklisted users is maintained.

PrePrint: Fault Localization via Risk Modeling

Internet backbone networks are under constant flux in order to keep up with demand and to offer new features. The pace of change in features and technology often outstrips the pace of introduction of the associated fault monitoring capabilities that are built into today's IP protocols and routers. Moreover, some of these new technologies cross networking layers, raising the potential for unanticipated interactions and service disruptions, which the built-in monitoring capabilities in each layer may not detect. In these instances, operators typically employ higher-layer monitoring techniques such as end-to-end liveness probing to detect lower- or cross-layer failures, but lack tools to precisely determine where a detected failure may have occurred. In this paper, we evaluate the effectiveness of using risk modeling to translate high-level failure notifications into lower-layer root causes. We show that a simple greedy heuristic works with accuracy exceeding 80% for many failure scenarios in realistic topologies, while delivering extremely high precision (greater than 80%). We further report our operational experience using risk modeling to isolate optical component and MPLS control-plane failures in a tier-1 ISP.

PrePrint: On-Line Intrusion Alert Aggregation With Generative Data Stream Modeling

Alert aggregation is an important subtask of intrusion detection. The goal is to identify and to cluster different alerts—produced by low-level intrusion detection systems, firewalls, etc.—belonging to a specific attack instance which has been initiated by an attacker at a certain point in time. Thus, meta-alerts can be generated for the clusters that contain all the relevant information whereas the amount of data (i.e., alerts) can be reduced substantially. Meta-alerts may then be the basis for reporting to security experts or for communication within a distributed intrusion detection system. We propose a novel technique for on-line alert aggregation which is based on a dynamic, probabilistic model of the current attack situation. Basically, it can be regarded as a data stream version of a maximum likelihood approach for the estimation of the model parameters. With three benchmark data sets we demonstrate that it is possible to achieve reduction rates of up to 99.96% while the number of missing meta-alerts is extremely low. In addition, meta-alerts are generated with a delay of typically only a few seconds after observing the first alert belonging to a new attack instance.

PrePrint: On the Quality of Service of Crash-Recovery Failure Detectors

We model the probabilistic behaviour of a system comprising a failure detector and a monitored crash-recovery target. We extend Chen’s work on failure detectors to take account of failure recovery in the target system. This involves extending Chen’s QoS measures to include the recovery detection speed and proportion of failures detected. We also extend Chen’s approach to estimating the parameters of the failure detector to achieve a required QoS and his approach to configuring the failure detector. We investigate the impact of the dependability of the monitored process on the QoS of our failure detector. Our analysis indicates that variation in the MTTF and MTTR of the monitored process can have a significant impact on the QoS of our failure detector. Our analysis is supported by simulations that agree with our theoretical results.

PrePrint: Cluster-Based Key Pre-Distribution Using Deployment Knowledge

We present a novel key pre-distribution scheme that uses deployment knowledge to divide deployment regions into overlapping clusters, each of which has its own distinct key space. Through careful construction of these clusters, network resilience is improved, without compromising connectivity or communications overhead. Experimental results show significant improvement in performance over existing schemes based on deployment knowledge.

PrePrint: Soft Error Rate Analysis for Combinational Logic Using An Accurate Electrical Masking Model

Accurate electrical masking modeling represents a significant challenge in soft error rate analysis for combinational logic circuits. In this paper, we use table lookup MOSFET models to accurately capture the nonlinear properties of submicron MOS transistors. Based on these models, we propose and validate the transient pulse generation model and propagation model for soft error rate analysis. The pulse generated by our pulse generation model matches well with that of HSPICE simulation, and the pulse propagation model provides nearly one order of magnitude improvement in accuracy over the previous models. Using these two models, we propose an accurate and efficient block-based soft error rate analysis method for combinational logic circuits.

PrePrint: The Geometric Efficient Matching Algorithm for Firewalls

Firewall packet matching can be viewed as a point location problem: Each packet (point) has 5 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(n^4)$ for a rule-base with $n$ rules. Based on statistics from real firewall rule-bases, we created a Perimeter rules model that generates random, but non-uniform, 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 13MB of space for rule-bases of 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 \GEMiptables\ 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

PrePrint: Balancing Revocation and Storage Tradeoffs in Secure Group Communication

In this paper, we focus on tradeoffs between storage cost and rekeying cost for secure multicast. Membership in secure multicast groups is dynamic and requires multiple updates in a single time frame. We present a family of algorithms that provide a tradeoff between the number of keys maintained by users and the time required for rekeying due to revocation of multiple users. We show that some well known algorithms in the literature are members of this family. We show that algorithms in this family can be used to reduce the cost of rekeying by 43%-79% when compared with previous solutions while keeping the number of keys manageable. We also describe a scheme to reduce the number of secrets further when revocations are periodic. Furthermore, we describe techniques to provide preferential treatment for long standing members of the group without affecting the performance of the algorithms. Using our techniques, as the group size increases, long standing members need to store smaller number of keys than short lived members. This property is useful for adapting to the variable storage requirements of users in current day heterogeneous networks.

PrePrint: On the Security of Chien's Ultra-Lightweight RFID Authentication Protocol

Recently, Chien proposed an ultra-lightweight RFID authentication protocol to prevent all possible attacks. However, we find two de-synchronization attacks to break the protocol.

PrePrint: An Obfuscation-Based Approach for Protecting Location Privacy

The pervasive diffusion of mobile communication devices and the technical improvements of location techniques are fostering the development of new applications that use the physical position of users to offer location-based services for business, social, or informational purposes. In such a context, privacy concerns are increasing and call for sophisticated solutions able to guarantee different levels of location privacy to the users. In this paper, we address this problem and present a solution based on different obfuscation operators that, when used individually or in combination, protect the privacy of the location information of users. We also introduce an adversary model and provide an analysis of the proposed obfuscation operators to evaluate their robustness against adversaries aiming to reverse the obfuscation effects to retrieve a location that better approximates the location of the users. Finally, we present some experimental results that validate our solution.

PrePrint: Automated Derivation of Application-Aware Error Detectors using Static Analysis: The Trusted Illiac approach

This paper presents a technique to derive and implement error detectors to protect an application from data errors. The error detectors are derived automatically using compiler-based static analysis from the backward program slice of critical variables in the program. Critical variables are defined as those that are highly sensitive to errors, and deriving error detectors for these variables provides high coverage for errors in any data value used in the program. The error detectors take the form of checking expressions and are optimized for each control flow path followed at runtime. The derived detectors are implemented using a combination of hardware and software and continuously monitor the application at runtime. If an error is detected at runtime, the application is stopped so as to prevent error propagation and enable a clean recovery. Experiments show that the derived detectors achieve low-overhead error detection while providing high coverage for errors that matter to the application.

PrePrint: Mechanism Design-Based Secure Leader Election Model for Intrusion Detection in MANET

We study leader election in the presence of selfish nodes for intrusion detection in (MANETs). To balance the resource consumption among all nodes and prolong the lifetime of a MANET, nodes with the most remaining resources should be elected as the leaders. However, there are two main obstacles in achieving this goal. First, without incentives for serving others, a node might behave selfishly by lying about its remaining resources and avoiding being elected. Second, electing an optimal collection of leaders to minimize the overall resource consumption may incur a prohibitive performance overhead, if such an election requires flooding the network. To address the issue of selfish nodes, we present a solution based on mechanism design. More specifically, the solution provides nodes with incentives in the form of reputations to encourage nodes in honestly participating in the election process. The amount of incentives is based on the Vickrey, Clarke, and Groves (VCG) model to ensure truth-telling to be the dominant strategy for any node. To address the optimal election issue, we propose a series of local election algorithms that can lead to globally optimal election results. Finally, we justify the effectiveness of the proposed schemes through extensive experiments.

PrePrint: A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree

Communication in networks suffers if a link fails. When the links are edges of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnects the network. Most often, the link is restored rapidly. A good policy to deal with this sort of transient link failures is swap rerouting, where the temporarily broken link is replaced by a single swap link from the underlying graph. A rapid replacement of a broken link by a swap link is only possible if all swap links have been precomputed. The selection of high quality swap links is essential; it must follow the same objective as the originally chosen communication subnetwork. We are interested in a minimum diameter tree in a graph with edge weights (so as to minimize the maximum travel time of messages). Hence, each swap link must minimize (among all possible swaps) the diameter of the tree that results from swapping. We propose a distributed algorithm that efficiently computes all of these swap links, and we explain how to route messages across swap edges with a compact routing scheme. Finally, we consider [omitted due to word count limit]

PrePrint: On the Thermal Attack in Instruction Caches

The instruction cache has been recognized as one of the least hot units in microprocessors, which leaves the instruction cache largely ignored in on-chip thermal management. Consequently, thermal sensors are not allocated near the instruction cache. However, malicious codes can exploit the deficiency in this empirical design and heat up fine-grain localized hotspots in the instruction cache, which might lead to physical damages. In this paper, we show how instruction caches can be thermally attacked by malicious codes and how simple techniques can be utilized to protect instruction caches from the thermal attack.

PrePrint: Wavelet Codes for Algorithm-Based Fault Tolerance Applications

Algorithm-based fault tolerance (ABFT) methods, which use real number parity values computed in two separate comparable ways to detect computer-induced errors in numerical processing operations, can employ wavelet codes for establishing the necessary redundancy. Wavelet codes, one form of real number convolutional codes, determine the required parity values in a continuous fashion and can be intertwined naturally with normal data processing. Such codes are the transform coefficients associated with an analysis uniform filter bank which employs downsampling, while parity-checking operations are performed by a syndrome synthesis filter bank that includes upsampling. The data processing operations are merged effectively with the parity generating function to provide one set of parity values. Good wavelet codes can be designed starting from standard convolutional codes over finite-fields by relating the field elements with the integers in the real number space. ABFT techniques are most efficient when employing a systematic form and methods for developing systematic codes are detailed. Bounds on the ABFT overhead computations are given and ABFT protection methods for processing that contains feedback are outlined. Analyzing syndromes' variances guide the selection of thresholds for syndrome comparisons. Simulations demonstrate the detection and miss probabilities for some high-rate wavelet codes.

PrePrint: A Large-Scale Study of Failures in High-Performance Computing Systems

Designing highly dependable systems requires a good understanding of failure characteristics. Unfortunately, little raw data on failures in large IT installations is publicly available. This paper analyzes failure data collected at two large high-performance computing sites. The first data set has been collected over the past 9 years at Los Alamos National Laboratory (LNAL) and has recently been made publicly available. It covers 23,000 failures recorded on more than 20 different systems at LANL, mostly large clusters of SMP and NUMA nodes. The second data set has been collected over the period of one year on one large supercomputing system comprised of 20 nodes and more than 10,000 processors. We study the statistics of the data, including the root cause of failures, the mean time between failures, and the mean time to repair. We find, for example, that average failure rates differ widely across systems, ranging from 20-1,000 failures per year, and that time between failures is modeled well by a Weibull distribution with decreasing hazard rate. From one system to another, mean repair time varies from less than an hour to more than a day, and repair times are well modeled by a lognormal distribution.

PrePrint: Deadlock-Free Adaptive Routing in Meshes with Fault-Tolerance Ability Based on Channel Overlapping

A new deadlock-free routing scheme for meshes is proposed based on a new virtual network partitioning scheme, called channel overlapping. Two virtual networks can share some common virtual channels based on the new virtual network partitioning scheme. The deadlock-free adaptive routing method is then extended to deadlock-free adaptive fault-tolerant routing in 3-dimensional meshes still with two virtual channels. A few faulty nodes can make a higher dimensional mesh unsafe for fault-tolerant routing methods based on the block fault model, where the whole system (n-dimensional space) forms a fault block. Planar safety information in meshes is proposed to guide fault-tolerant routing, and classifies fault-free nodes inside 2-dimensional planes. Many nodes globally marked as unsafe in the whole system become locally enabled inside 2-dimensional planes. This fault-tolerant deadlock-free adaptive routing algorithm is extended to the one in an n-dimensional meshes also with two virtual channels. Extensive simulation results are presented and compared to previous methods.

PrePrint: Providing e-Transaction Guarantees in Asynchronous Systems with no Assumptions on the Accuracy of Failure Detection

In this paper we address reliability issues in three-tier systems with stateless application servers. For these systems, a framework called e-Transaction has been recently proposed, which specifies a set of desirable end-to-end reliability guarantees. In this article we propose an innovative distributed protocol providing e-Transaction guarantees in the general case of multiple, autonomous back-end databases (typical of scenarios with multiple parties involved within a same business process). Differently from existing proposals coping with the e-Transaction framework, our protocol does not rely on any assumption on the accuracy of failure detection. Hence it reveals suited for a wider class of distributed systems. To achieve such a target, our protocol exploits an innovative scheme for distributed transaction management (based on ad-hoc demarcation and concurrency control mechanisms), which we introduce in this paper. Beyond providing the proof of protocol correctness, we also discuss hints on the protocol integration with conventional systems (e.g. database systems) and show the minimal overhead imposed by the protocol.

PrePrint: Differential Power Analysis Attacks to Precharged Busses: A General Analysis for Symmetric-Key Cryptographic Algorithms

In this paper, a general model of multi-bit Differential Power Analysis (DPA) attacks to precharged busses is discussed, with emphasis on symmetric-key cryptographic algorithms. Analysis provides a deeper insight into the dependence of the DPA effectiveness (i.e., the vulnerability of cryptographic chips) on the parameters that define the attack, the algorithm and the processor architecture in which the latter is implemented. To this aim, the main parameters that are of interest in practical DPA attacks are analytically derived under appropriate approximations, and a novel figure of merit to measure the DPA effectiveness of multi-bit attacks is proposed. This figure of merit allows for identifying conditions that maximize the effectiveness of DPA attacks, i.e. conditions under which a cryptographic chip should be tested to assess its robustness. Several interesting properties of DPA attacks are derived, and suggestions to design algorithms and circuits with higher robustness against DPA are given. The proposed model is validated in the case of DES and AES algorithms with both simulations on an MIPS32 architecture and measurements on an FPGA-based implementation of AES. The model accuracy is shown to be adequate, as the resulting error is always lower than 10%, and typically of a few percentage points.

PrePrint: RITAS: Services for Randomized Intrusion Tolerance

Randomized agreement protocols have been around for more than two decades. Often assumed to be inefficient due to their high expected communication and computation complexities, they have remained overlooked by the community-at-large as a valid solution for the deployment of fault-tolerant distributed systems. This paper aims to demonstrate that randomization can be a very competitive approach even in hostile environments where arbitrary faults can occur. A stack of randomized intrusion-tolerant protocols is described and its performance evaluated under several settings in both LAN and WAN environments. The stack provides a set of relevant services ranging from basic communication primitives up through atomic broadcast. The experimental evaluation shows that the protocols are efficient, especially in LAN environments where no performance reduction is observed under certain Byzantine faults.

PrePrint: A Stochastic Model for Quantitative Security Analyses of Networked Systems

Traditional security analyses are often geared towards cryptographic primitives or protocols. Although such analyses are necessary, they cannot address a defender's need for insight into which aspects of a networked system having a significant impact on its security, and how to tune its configurations or parameters so as to improve security. This question is known to be notoriously difficult to answer, and the state-of-the-art is that we know little about it. Towards ultimately addressing this question, this paper presents a stochastic model for quantifying security of networked systems. The resulting model captures two aspects of a networked system: (1) the strength of deployed security mechanisms such as intrusion detection systems, and (2) the underlying vulnerability graph, which reflects how attacks may proceed. The resulting model brings the following insights: (1) How should a defender "tune" system configurations so as to improve security? (2) How should a defender "tune" system parameters (e.g., by upgrading which security mechanisms) so as to improve security? (3) Under what conditions the steady-state number of compromised entities of interest is below a given threshold with a high probability? Simulation studies are conducted to confirm the analytic results, and to show the tightness of the bounds of certain important metric that cannot be resolved analytically.

PrePrint: Proactive Detection of Computer Worms Using Model Checking

Although recent estimates are speaking of 200,000 different viruses, worms, and Trojan horses, the majority of them are variations of previously existing malware. As these variations much more affect the binary of the malware than its functionality, they can be recognized by analyzing the program behavior, even though they are not covered by the signature databases of current anti-virus tools. Proactive malware detectors mitigate this risk by detection procedures which use a single signature to detect whole classes of functionally related malware without signature updates. It is evident that the quality of proactive detection procedures depends on their ability to analyze the semantics of the binary. In this paper, we propose the use of model checking—a well established software verification technique—for proactive malware detection. We describe a tool which extracts an annotated control flow graph from the binary and automatically verifies it against a formal malware specification. To this end, we introduce a new specification language CTPL which balances the high expressive power needed for malware signatures with efficient model checking algorithms. Our experiments demonstrate that our technique indeed is able to recognize variations of existing malware with a low risk of false positives.

PrePrint: On the Survivability of Wireless Ad Hoc Networks with Node Misbehaviors and Failures

Network survivability is the ability of a network keeping connected under failures and attacks, which is a fundamental issue to the design and performance evaluation of wireless ad hoc networks. In this paper, we focus on the analysis of network survivability in the presence of node misbehaviors and failures. First, we propose a novel semi-Markov process model to characterize the evolution of node behaviors. As an immediate application of the proposed model, we investigate the problem of node isolation where the effects of Denial-of-Service (DoS) attacks are considered. Then we present the derivation of network survivability and obtain the lower and upper bounds on the topological survivability for k-connected networks. We find that the network survivability degrades very quickly with the increasing likelihood of node misbehaviors, depending on the requirements of disjoint outgoing paths or network connectivity. Moreover, DoS attacks have a significant impact on the network survivability, especially in dense networks. Finally, we validate the proposed model and analytical result by simulations and numerical analysis, showing the effects of node misbehaviors on both topological survivability and network performance.

PrePrint: Shifting Inference Control to User Side: Architecture and Protocol

Inference has been a long standing issue in database security, and inference control, aiming to curb inference, provides an extra line of defence to the confidentiality of databases by complementing access control. However, in traditional inference control architecture, database server is a crucial bottleneck, as it enforces highly computation-intensive auditing for all users who query the protected database. As a result, most auditing methods, though rigorously studied, are not practical for protecting large-scale real-world database systems. In this paper, we shift this paradigm by proposing a new inference control architecture, entrusting inference control to each user's platform that is equipped with trusted computing technology. The trusted computing technology is designed to attest the state of a user's platform to the database server, so as to assure the server that inference control could be enforced as prescribed. A generic protocol is proposed to formalize the interactions between the user's platform and database server. The authentication property of the protocol is formally proven. Since inference control is enforced in a distributed manner, our solution avoids the bottleneck in the traditional architecture, thus can potentially support a large number of users making queries.

PrePrint: Detecting Intrusions through System Call Sequence and Argument Analysis

We describe an unsupervised host-based intrusion detection system based on system calls arguments and sequences. We define a set of anomaly detection models for the individual parameters of the call. We then describe a clustering process which helps to better fit models to system call arguments, and creates inter-relations among different arguments of a system call. Finally, we add a behavioral Markov model in order to capture time correlations and abnormal behaviors. The whole system needs no prior knowledge input; it has a good signal to noise ratio, and it is also able to correctly contextualize alarms, giving the user more information to understand whether a true or false positive happened, and to detect global variations over the entire execution flow, as opposed to punctual ones over individual instances.

PrePrint: Role Engineering via Prioritized Subset Enumeration

Today, role-based access control (RBAC) has become a well accepted paradigm for implementing access control because of its convenience and ease of administration. However, in order to realize the full benefits of the RBAC paradigm, one must first define the roles accurately. This task of defining roles and associating permissions with them, also known as role engineering, is typically accomplished either in a top-down or in a bottom-up manner. Under the top-down approach, a careful analysis of the business processes is done to first define job functions and then to specify appropriate roles from them. While this approach can help in defining roles more accurately, it is tedious and time consuming since it requires that the semantics of the business processes be well understood. Moreover, it ignores existing permissions within an organization and does not utilize them. On the other hand, under the bottom-up approach, existing permissions are used to derive roles from them. As a result, it may help automate the process of role definition. In this paper, we present an unsupervised approach, called RoleMiner, for mining roles from existing user-permission assignments. Since a role, when semantics are unavailable, is nothing but a set of permissions, the task of role mining is essentially that of clustering users having the same (or similar) permissions. However, unlike the traditional applications of data mining that ideally require identification of non-overlapping clusters, roles will have overlapping permissions and thus permission sets that define roles should be allowed to overlap. It is this distinction from traditional clustering that makes the problem of role mining non-trivial. Our experiments with real and simulated data sets indicate that our role mining process is quite accurate and efficient. Since our role mining approach is based on subset enumeration by employing intersections of permission sets, it is fairly robust to reasonable levels of noise.

PrePrint: On the Effects of Process Variation in Network-on-Chip Architectures

The advent of diminutive technology feature sizes has led to escalating transistor densities. Burgeoning transistor counts are casting a dark shadow on modern chip design: global interconnect delays are dominating gate delays and affecting overall system performance. Networks-on-Chip (NoC) are viewed as a viable solution to this problem, because of their scalability and optimized electrical properties. However, on-chip routers are susceptible to another artifact of deep sub-micron technology, Process Variation (PV). PV is a consequence of manufacturing imperfections, which may lead to degraded performance and even erroneous behavior. In this work, we present the first comprehensive evaluation of NoC susceptibility to PV effects, and we propose an array of architectural improvements in the form of a new router design - called SturdiSwitch - to increase resiliency to these effects. Through extensive re-engineering of critical components, SturdiSwitch provides increased immunity to PV while improving performance and increasing area and power efficiency.

PrePrint: On The General Applicability of Instruction-Set Randomization

We describe Instruction-Set Randomization, a general approach for safeguarding systems against any type of code-injection attack. We apply Kerckhoffs' principle to create OS process-specific randomized intstruction sets (e.g., machine instructions) of the system executing potentially vulnerable software. An attacker who does not know the key to the randomization algorithm will inject code that is invalid for that (randomized) environment, causing a runtime exception. Our approach is applicable to machine-language programs, scripting and interpreted languages. We discuss three approaches (protection for Intel x86 executa- bles, Perl scripts, and SQL queries), one from each of the above categories. Our goal is to demonstrate the generality and appli- cability of ISR as a protection mechanism. Our emulator-based prototype demonstrates the feasibility ISR for x86 executables, and should be directly usable on a suitably modified processor. We demonstrate how to mitigate the significant performance impact of emulation-based ISR by using several heuristics to limit the scope of randomized (and interpreted) execution to sections of code that may be more susceptible to exploitation. The SQL prototype consists of an SQL query-randomizing proxy that protects against SQL-injection attacks with no changes to database servers, minor changes to CGI scripts, and with negligible performance overhead. Similarly, the performance penalty of a randomized Perl interpreter is minimal.

PrePrint: In-depth Packet Inspection Using a Hierarchical Pattern Matching Algorithm

Detection engines capable of inspecting packet payloads for application-layer network information are urgently required. The most important technology for fast payload inspection is an efficient multi-pattern matching algorithm, which performs exact string matching between packets and a large set of pre-defined patterns. This paper proposes a novel Enhanced Hierarchical Multi-pattern Matching Algorithm (EHMA) for packet inspection. Based on the occurrence frequency of grams, a small set of the most frequent grams is discovered and used in the EHMA. EHMA is a two-tier and cluster-wise matching algorithm, which significantly reduces the amount of external memory accesses and the capacity of memory. Using a skippable scan strategy, EHMA speeds up the scanning process. Furthermore, independent of parallel and special functions, EHMA is very simple and therefore practical for both software and hardware implementations. Simulation results reveal that EHMA significantly improves the matching performance. The speed of EHMA is about 0.89¡V1161 times faster than that of current matching algorithms. Even under real-life intense attack, EHMA still performs well.

PrePrint: Using Web-Referral Architectures to Mitigate Denial-of-Service Threats

The web is a complicated graph, with millions of websites interlinked together. In this paper, we propose to use this web sitegraph structure to mitigate flooding attacks on a website, using a new web referral architecture for privileged service ("WRAPS"). WRAPS allows a legitimate client to obtain a privilege URL through a simple click on a referral hypherlink, from a website trusted by the target website. Using that URL, the client can get privileged access to the target website in a manner that is far less vulnerable to a DDoS flooding attack. WRAPS does not require changes to web client software and is extremely lightweight for referrer websites, which makes its deployment easy. We present the design of WRAPS, and the implementation of a prototype system used to evaluate our proposal. Our empirical study demonstrates that WRAPS enables legitimate clients to connect to a website smoothly in spite of a very intensive flooding attack, at the cost of small overheads on the website's ISP's edge routers. We discuss the security properties of WRAPS over web sitegraph and a simple approach to encourage many small websites to help protect an important site during DoS attacks.

PrePrint: Conformance Testing of Temporal Role-Based Access Control Systems

Access control is a key security service at the foundation of information and system security. It has been extended with temporal constraints to support real-time considerations. Conformance testing of an access control implementation is crucial to ensure that it correctly enforces any required temporal and non-temporal policies for access control. We propose an approach for conformance testing of implementations required to enforce access control policies specified using Temporal Role Based Access Control (TRBAC) model. The proposed approach uses Timed Input Output Automata (TIOA) to model the behavior specified by a TRBAC policy. The TIOA model is then transformed to a deterministic se-FSA model that captures any temporal constraint by using two special events {\it Set} and {\it Exp}. Finally we adapt the W-method and use an integer programming based approach to construct a conformance test suite from the transformed model. The conformance test suite so generated provides complete fault coverage with respect to the proposed fault model for TRBAC specifications.

PrePrint: Designing Dependable Storage Solutions for Shared Application Environments

The costs of data loss and unavailability can be large, so businesses use many data protection techniques, such as remote mirroring, snapshots, and backups, to guard against failures. Choosing an appropriate combination of techniques is difficult because there are numerous approaches for protecting data and allocating resources. Storage system designers typically use ad hoc techniques, often resulting in over-engineered, expensive solutions or under-provisioned, inadequate ones. In contrast, this paper presents a principled, automated approach for designing dependable storage solutions for multiple applications in shared environments. Our contributions include search heuristics for intelligently exploring the large design space and modeling techniques for capturing interactions between applications during recovery. Using realistic storage system requirements, we show that our design tool produces designs that cost up to 2 times less in initial outlays and expected data penalties than the designs produced by an emulated human design process. Additionally, we compare our design tool to a random search heuristic and a genetic algorithm meta-heuristic, and show that our approach consistently produces better designs for the cases we have studied. Finally, we study the sensitivity of our design tool to several input parameters.

PrePrint: Dual-Quorum: A Highly Available and Consistent Replication System for Edge Services

This article introduces dual-quorum replication, a novel data replication algorithm designed to support Internet edge services. Edge services allow clients to access Internet services via distributed edge servers that operate on a shared collection of underlying data. Although it is generally difficult to share data while providing high availability, good performance, and strong consistency, replication algorithms designed for specific access patterns can offer nearly ideal trade-offs among these metrics. In this article, we focus on the key problem of sharing read/write data objects across a collection of edge servers when the references to each object (a) tend not to exhibit high concurrency across multiple nodes and (b) tend to exhibit bursts of read-dominated or write-dominated behavior. Dual-quorum replication combines volume leases and quorum based techniques to achieve availability, response time, and consistency for such workloads. In particular, through both analytical and experimental evaluation, we show that the dual-quorum protocol can (for the workloads of interest) approach the optimal performance and availability of Read-One/Write-All-Asynchronously (ROWA-A) epidemic algorithms without suffering the weak consistency guarantees and resulting design complexity inherent in ROWA-A systems.

PrePrint: An Advanced Hybrid Peer-to-Peer Botnet

A "botnet" consists of a network of compromised computers controlled by an attacker ("botmaster"). Recently botnets have become the root cause of many Internet attacks. To be well prepared for future attacks, it is not enough to study how to detect and defend against the botnets that have appeared in the past. More importantly, we should study advanced botnet designs that could be developed by botmasters in the near future. In this paper, we present the design of an advanced hybrid peer-to-peer botnet. Compared with current botnets, the proposed botnet is harder to be shut down, monitored, and hijacked. It provides robust network connectivity, individualized encryption and control traffic dispersion, limited botnet exposure by each bot, and easy monitoring and recovery by its botmaster. In the end, we suggest and analyze several possible defenses against this advanced botnet.