IEEE Transactions on Dependable and Secure Computing

PrePrint: SigFree: A Signature-Free Buffer Overflow Attack Blocker

We propose SigFree, signature-free, out-of-the-box method for blocking code-injection buffer overflow attack messages targeting at various Internet services such as web service. Motivated by the observation that buffer overflow attacks typically contain executables whereas legitimate client requests never contain executables in most Internet services, SigFree blocks attacks by detecting the presence of code. Unlike the previous code detection algorithms, SigFree uses a new data-flow analysis technique called code abstraction that is generic, fast and hard for exploit code to evade. SigFree first blindly dissembles and extracts instruction sequences from a request. It then applies a novel technique, which uses new data flow anomaly to prune useless instructions in an instruction sequence. Finally it compares the number of useful instructions or dependent degree to a threshold to determine if this instruction sequence contains code. SigFree is signature free, thus it can block new and unknown buffer overflow attacks; SigFree is also immunized from most attack-side code obfuscation methods. Since SigFree is a transparent deployment to the servers being protected, it is good for economical Internet wide deployment with very low deployment and maintenance cost. Our experimental study shows that the dependency-degree-based SigFree could block all types of code-injection attack packets (above 750) tested in our experiments with very few false positives.

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.

IEEE Transactions on Dependable and Secure Computing - April-June 2009 (Vol. 6, No. 2)

IEEE Transactions on Dependable and Secure Computing

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: 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: BLAST-SSAHA Hybridization for Credit Card Fraud Detection

A phenomenal growth in the number of credit card transactions, especially for online purchases, has recently led to a substantial rise in fraudulent activities. Implementation of efficient fraud detection systems has thus become imperative for all credit card issuing banks to minimize their losses. In real life, fraudulent transactions are interspersed with genuine transactions and simple pattern matching is not often sufficient to detect them accurately. Thus, there is a need for combining both anomaly detection as well as misuse detection techniques. In this paper, we propose to use two-stage sequence alignment in which a profile analyzer (PA) first determines the similarity of an incoming sequence of transactions on a given credit card with the genuine cardholder's past spending sequences. The unusual transactions traced by the profile analyzer are next passed on to a deviation analyzer (DA) for possible alignment with past fraudulent behavior. The final decision about the nature of a transaction is taken on the basis of the observations by these two analyzers. In order to achieve on-line response time for both PA and DA, we suggest a new approach for combining two sequence alignment algorithms BLAST and SSAHA.

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: Steward: Scaling Byzantine Fault-Tolerant Replication to Wide Area Networks

This paper presents the first hierarchical Byzantine fault-tolerant replication architecture suitable to systems that span multiple wide area sites. The architecture confines the effects of any malicious replica to its local site, reduces message complexity of wide area communication, and allows read-only queries to be performed locally within a site for the price of additional standard hardware. We present proofs that our algorithm provides safety and liveness properties. A prototype implementation is evaluated over several network topologies and is compared with a flat Byzantine fault-tolerant approach. The experimental results show considerable improvement over flat Byzantine replication algorithms, bringing the performance of Byzantine replication closer to existing benign fault-tolerant replication techniques over wide area networks.

PrePrint: A Novel Bicriteria Scheduling Heuristics Providing a Guaranteed Global System Failure Rate.

We propose a new framework for the (length,reliability) bicriteria static multiprocessor scheduling problem. Our first criteria remains the static schedule's length: this is crucial to assess the system's real-time property. For our second criteria, we consider the global system failure rate, seen as if the whole system were a single task scheduled onto a single processor, instead of the usual reliability, because it does not depend on the schedule length like the reliability does (due to its computation in the classical reliability model of Shatz and Wang). Therefore, we control better the replication factor of each individual task of the dependency task graph given as a specification, with respect to the desired failure rate. To solve this bicriteria optimization problem, we take the failure rate as a constraint, and we minimize the schedule length. We are thus able to produce, for a given dependency task graph and multiprocessor architecture, a Pareto curve of non-dominated solutions, among which the user can choose the compromise that fits his requirements best. Compared to the other bicriteria (length,reliability) scheduling algorithms found in the literature, the algorithm we present here is the first able to improve significantly the reliability, by several orders of magnitude, making it suitable to safety critical systems.

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: Is Asynchronous Logic More Robust Than Synchronous Logic?

With clock rates beyond 1 GHz the model of a system-wide synchronous clock is becoming difficult to maintain, therefore asynchronous design styles are increasingly receiving attention. While the traditional synchronous design style is well-proven and backed up by a rich field experience, comparatively little is known about the properties of asynchronous circuits in practical application. In the face of increased transient fault rates, robustness is a crucial property, and from a conceptual view the so called "delay insensitive" asynchronous design approaches promise to be more robust than synchronous ones, since their operation does not depend on tight timing margins, and data are two-rail coded. A practical assessment of asynchronous designs in fault injection studies does, however, not exist, nor are there adequate methods and tools in this particular domain available. Therefore the objective of this work is (a) to provide a common approach for efficient and accurate fault injection in synchronous and in asynchronous designs, and (b) to experimentally compare the robustness of both synchronous and asynchronous designs. To this end a synchronous 16 bit processor as well as its asynchronous equivalent are subjected to signal flips and delay faults. The results of over 489 million experiments are summarized and discussed, and a detailed comparison is given.

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.

PrePrint: Semi-Concurrent On-Line Testing of Transition Faults Through Output Response Comparison of Identical Circuits

We describe a method for on-line testing of delay faults based on the comparison of output responses of identical circuits. The method allows one of the circuits to participate in useful computations during the testing process, while the other circuit must be idle. We refer to this method as semi-concurrent on-line testing. While unknown input vectors are applied to the circuit that participates in useful computations, the proposed method applies modified vectors to the idle circuit. In this way, different conditions are created for the detection of delay faults, allowing identical delay faults that affect both circuits to be detected. In designing the modified vectors, we ensure that the expected fault free responses of the two circuits are identical. We also ensure that the hardware for modifying the vectors applied to the idle circuit will be easy to implement on-chip.

PrePrint: Cryptanalysis of New Ultralightweight RFID Authentication Protocol - SASI

Since RFID tags are ubiquitous and at times even oblivious to the human user, all modern RFID protocols are designed to resist tracking so that the location privacy of the human RFID user is not violated. Another design criterion for RFIDs is the low computational effort required for tags, in view that most tags are passive devices that derive power from an RFID reader's signals. Along this vein, a class of ultra-lightweight RFID authentication protocols have been designed that use only the most basic bitwise and arithmetic operations like exclusive-OR, OR, addition, rotation, etc. In this paper, we analyze the security of the SASI protocol, a recently proposed ultra-lightweight RFID protocol with better claimed security than earlier protocols. We show that SASI does not achieve resistance to tracking, which is one of its design objectives.

PrePrint: Using Underutilized CPU Resources to Enhance Its Reliability

Soft errors are temporary faults that arise in a circuit due to a variety of internal noise and external sources. Though soft errors still occur infrequently, they are rapidly becoming a major impediment to processor reliability. This is due primarily to processor scaling characteristics. As the feature size keeps shrinking and the proliferation of multiprocessor-on-die in all segments of computer based systems, the capability to detect and recover from faults is also desired for commodity hardware. For such systems, however, performance and power constitute the main drivers, so the traditional solutions prove inadequate. We introduce two independent and complementary micro-architecture level techniques: Double Execution and Double Decoding. Both exploit the low average processor resource utilization that characterizes modern processors to help enhance processor reliability. Double Execution protects the Out-Of-Order part of the CPU by executing each instruction twice. Double Decoding uses a second, low-performance, low-power instruction decoder in order to detect soft errors in the decoder logic. We show that these techniques improve the processor's reliability with relatively low performance, power and hardware overheads, and their implementation is moreover simple. Finally, the resulting "excessive" reliability can even be traded back for performance by increasing clock rate and/or reducing voltage, thereby improving upon single execution approaches.

PrePrint: Chasing the Weakest System Model for Implementing Ω and Consensus

Aguilera et al. and Malkhi et al. have presented two system models, which are weaker than all previously proposed models where the eventual leader election oracle Ω can be implemented and thus also consensus can be solved. The former model assumes assumes unicast steps and at least one correct process with ƒ outgoing eventually timely links, whereas the latter assumes broadcast steps and at least one correct process with ƒ bidirectional but moving eventually timely links. Consequently, those models are incomparable. In this paper, we show that Ω can also be implemented in a system with at least one process with ƒ outgoing moving eventually timely links, assuming either unicast or broadcast steps. It seems to be the weakest system model that allows to solve consensus via Ω-based algorithms known so far. We also provide matching lower bounds for the communication complexity of Ω in this model, which are based on an interesting "stabilization property" of infinite runs. Those results reveal a fairly high price to be paid for the further relaxation of synchrony properties.

PrePrint: A Survey on the Encryption of Convergecast-Traffic with In-Network Processing

We present an overview of end-to-end encryption solutions for convergecast-traffic in wireless sensor networks that support in-network processing at forwarding intermediate nodes. Other than hop-by-hop based encryption approaches, aggregator nodes can perform in-network processing on encrypted data. Since it is not required to decrypt the incoming ciphers before aggregating substantial advantages are i) neither keys nor plaintext is available at aggregating nodes, ii) the overall energy consumption of the backbone can be reduced, iii) the system is more flexible with respect to changing routes, and finally iv) the overall system security increases. We provide a qualitative comparison of available approaches, point out their strengths respectively weaknesses and investigate opportunities for further research.

PrePrint: Error Detection and Fault Tolerance in ECSM Using Input Randomization

For some applications, elliptic curve cryptography (ECC) is an attractive choice because it achieves the same level of security with a much smaller key size in comparison with other schemes such as those that are based on integer factorization or discrete logarithm. For security reasons, especially to provide resistance against fault-based attacks, it is very important to verify the correctness of computations in ECC applications. In this article, error-detecting and fault-tolerant elliptic curve cryptosystems are considered. Error detection may be a sufficient countermeasure for many security applications, however fault-tolerant characteristic enables a system to perform its normal operation in spite of faults. For the purpose of detecting errors due to faults, a number of schemes and hardware structures are presented based on re-computation or parallel computation. It is shown that these structures can be used for detecting errors with a very high probability during the computation of the elliptic curve scalar multiplication (ECSM). Additionally, we show that using parallel computation along with either PV or re-computation, it is possible to have fault-tolerant structures for the ECSM. If certain conditions are met, these schemes are more efficient than others such as the well-known triple modular redundancy.

PrePrint: Layered Approach using Conditional Random Fields for Intrusion Detection

Intrusion detection faces a number of challenges; the system must reliably detect malicious activities in a network and perform efficiently to cope with the large amount of network traffic. In this paper, we address these two issues of Accuracy and Efficiency using Conditional Random Fields and Layered Approach. We demonstrate that high attack detection accuracy can be achieved by using Conditional Random Fields and high efficiency by implementing the Layered Approach. Experimental results on the benchmark KDD'99 intrusion data set show that our proposed system based on Layered Conditional Random Fields outperforms other well known methods such as the decision trees and the naive Bayes. The improvement in attack detection accuracy is very high, particularly, for the U2R attacks (34.8% improvement) and the R2L attacks (34.5% improvement). Statistical Tests also demonstrate higher confidence in detection accuracy for our method. Finally, we show that our system is robust and is able to handle noisy data without compromising performance.

PrePrint: Secure Data Objects Replication in Data Grid

In this paper, we consider data partitioning and dynamic replication in data grids. More specifically, we investigate the problem of optimal allocation of secure data objects that are securely partitioned and replicated. The grid topology we consider consists of two layers. In the upper layer, multiple clusters form a network topology that can be represented by a general graph. The topology within each cluster is represented by a tree graph. We decompose the share replica allocation problem into two sub-problems, the Optimal Inter-cluster Resident Set Problem (OIRSP), that determines which clusters need share replicas, and the Optimal Intra-cluster Share Allocation Problem (OISAP), that determines the number of share replicas needed in a cluster and their placements. We develop two heuristic algorithms for the two sub-problems. Experimental studies show that the heuristic algorithms achieve good performance in reducing communication cost and are close to optimal solutions.

PrePrint: Reducing Soft Errors through Operand Width Aware Policies

Soft errors are an important challenge in contemporary microprocessors. Particle hits on the components of a processor are expected to create an increasing number of transient errors with each new microprocessor generation. In this paper we propose simple mechanisms that effectively reduce the vulnerability to soft errors in a processor. As a faster but less fault tolerant alternative to ECC and parity, we offer a variety of schemes that make use of narrow values and analyze their efficiency in reducing soft error vulnerability of different data-holding components of a processor. On average, techniques that make use of the narrowness of the values can provide 49% error detection, 45% error correction or 27% error avoidance coverage for single bit upsets in the first level data cache across all Spec2K. In other structures such as the immediate field of the issue queue, average error detection rate of 64% is achieved.

PrePrint: A Top-Down Design Methodology for Ultra High-Performance Hashing Cores

Many cryptographic primitives that are used in cryptographic schemes and security protocols such as SET, PKI, IPSec and VPN's utilize hash functions which form a special family of cryptographic algorithms. Applications that use these security schemes are becoming very popular as time goes by and this means that some of these applications call for higher throughput either due to their rapid acceptance by the market or due to their nature. In this work a new methodology is presented for achieving high operating frequency and throughput for the implementations of all widely used - and those expected to be used in the near future - hash functions such as MD-5, SHA-1, RIPEMD (all versions), SHA-256, SHA-384, and SHA-512 etc. In the proposed methodology five different techniques have been developed and combined with the finest way so as to achieve the maximum performance. Compared to conventional pipelined implementations of hash functions (in FPGAs), the proposed methodology can lead even to a 160% throughput increase.

PrePrint: JANUS: A Framework for Scalable and Secure Routing in Hybrid Wireless Networks

Hybrid networks consisting of cellular and Wi-Fi networks were proposed as a high-throughput architecture for cellular services. In such networks, devices equipped with cellular and Wi-Fi network cards access Internet services through the cellular base station. The Wi-Fi interface is used to provide better service to clients that are far away from the base station, via multihop, ad hoc paths. The modified trust model of hybrid networks generates a set of new security challenges as clients rely on intermediate nodes to participate effectively in the resource reservation process and data forwarding. In this paper we introduce JANUS, a framework for scalable, secure and efficient routing for hybrid cellular and Wi-Fi networks. JANUS uses a scalable routing algorithm with multiple channel access, for improved network throughput. In addition, it provides protection against selfish nodes through a secure crediting protocol and protection against malicious nodes through secure route establishment and data forwarding mechanisms. We evaluate JANUS experimentally and show that it significantly improves the network capabilities of wireless devices, while having a low computation and communication overhead. Moreover, we evaluate the security overhead of JANUS against two type of attacks: a less aggressive, but sufficient for some applications, model of selfish attackers, and purely malicious attacks.

PrePrint: A Puzzle-Based Defense Strategy Against Flooding attacks Using Game Theory

In recent years, a number of puzzle-based defense mechanisms have been proposed against flooding denial-of-service (DoS) attacks in networks. Nonetheless, these mechanisms have not been designed through formal approaches and thereby some important design issues such as effectiveness and optimality have remained unresolved. This paper utilizes game theory to propose a series of optimal puzzle-based strategies for handling increasingly sophisticated flooding attack scenarios. In doing so, the solution concept of Nash equilibrium is used in a prescriptive way, where the defender takes his part in the solution as an optimum defense against rational attackers. This study culminates in a strategy for handling distributed attacks from an unknown number of sources.

PrePrint: KTR: an Efficient Key Management Scheme For Secure Data Access Control in Wireless Broadcast Services

Wireless broadcast is an effective approach to disseminate data to a number of users. To provide secure access to data in wireless broadcast services, symmetric key-based encryption is used to ensure that only users who own the valid keys can decrypt the data. Regarding various subscriptions, an efficient key management to distribute and change keys is in great demand for access control in the broadcast system. In this paper, we propose an efficient key management scheme (namely KTR) to handle key distribution with regarding to complex subscription options and user activities. KTR has the following advantages. First, it supports all subscription activities in wireless broadcast services. Second, in KTR, a user only needs to hold one set of keys for all subscribed programs, instead of separate sets of keys for each program. Third, KTR identifies the minimum set of keys that must be changed to ensure broadcast security and minimize the rekey cost. Our simulations show that KTR can save about 45% of communication overhead in the broadcast channel and about 50% of decryption cost for each user, compared with logical key hierarchy based approaches.

PrePrint: A New Decision Diagram Based Method for Efficient Analysis on Multi-State Systems

Multistate systems can model many practical systems in a wide range of real applications. A distinct characteristic of these systems is that the systems and their components may assume more than two levels of performance (or states) varying from perfect operation to complete failure. The non-binary property of multistate systems and their components make the analysis of multistate systems difficult. This paper proposes a new decision diagram based method, called multistate multivalued decision diagrams (MMDD) for the analysis of multistate systems with multistate components. Examples show how the MMDD models are generated and evaluated to obtain the system state probabilities. The MMDD method is compared with the existing binary decision diagrams (BDD) based method. Empirical results show that the MMDD method can offer less computational complexity and simpler model evaluation algorithm than the BDD-based method.

PrePrint: Modeling Soft Errors at Device and Logic Level for combinational circuits

Radiation induced soft errors in combinational logic is expected to become as important as directly induced errors on state elements. Consequently, it has become important to develop techniques to quickly and accurately predict soft error rates in combinational circuits. In this work, we present methodologies to model soft errors in both device and logic level. At the device level, a hierarchical methodology to model neutron induced soft errors is proposed. This model is used to create a transient current library which will be useful for circuit level soft error estimation. The library contains the transient current response to various different factors such as ion energies, operating voltage, substrate bias, angle and location of impact. At the logic level, we propose a new approach to estimating Soft Error Rate (SER) of logic circuits that attempts to capture electrical, logic and latch window masking concurrently. The average error of the SER estimates using our approach compared to the estimates obtained using circuit level simulations is 6.5% while providing an average speed up of 15000. We have demonstrated the scalability of our approach using designs from the ISCAS-85 benchmarks.