Automatic speech recognition (ASR) systems are vulnerable to audio adversarial examples, which aim at deceiving ASR systems by adding perturbations to benign speech signals. These audio adversarial examples appear indistinguishable from benign audio waves, but the ASR system decodes them as intentional malicious commands. Previous studies have demonstrated the feasibility of such attacks in simulated environments (over-line) and have further showcased the creation of robust physical audio adversarial examples (over-air). Various defense techniques have been proposed to counter these attacks. However, most of them have either failed to handle various types of attacks effectively or have resulted in significant time overhead. In this article, we propose a novel method for detecting audio adversarial examples. Our approach involves feeding both smoothed audio and original audio inputs into the ASR system. Subsequently, we introduce noise to the logits before providing them to the decoder of the ASR. We demonstrate that carefully selected noise can considerably influence the transcription results of audio adversarial examples while having minimal impact on the transcription of benign audio waves. Leveraging this characteristic, we detect audio adversarial examples by comparing the altered transcription, resulting from logit noising, with the original transcription. The proposed method can be easily applied to ASR systems without requiring any structural modifications or additional training. Experimental results indicate that the proposed method exhibits robustness against both over-line and over-air audio adversarial examples, outperforming state-of-the-art detection methods.

Automatic speech recognition (ASR) systems are vulnerable to audio adversarial examples that attempt to deceive ASR systems by adding perturbations to benign speech signals. Although an adversarial example and the original benign wave are indistinguishable to humans, the former is transcribed as a malicious target sentence by ASR systems. Several methods have been proposed to generate audio adversarial examples and feed them directly into the ASR system (over-line). Furthermore, many researchers have demonstrated the feasibility of robust physical audio adversarial examples (over-air). To defend against the attacks, several studies have been proposed. However, deploying them in a real-world situation is difficult because of accuracy drop or time overhead.

In the Internet of Things (IoT) environment, detecting a faulty device is crucial to guarantee the reliable execution of IoT services. To detect a faulty device, existing schemes trace a series of events among IoT devices within a certain time window, extract correlations among them, and find a faulty device that violates the correlations. However, if a few users share the same IoT environment, since their concurrent activities make non-correlated devices react together in the same time window, the existing schemes fail to detect a faulty device without differentiating the concurrent activities. To correctly detect a faulty device in the multiple concurrent activities, this work proposes a new precise correlation extraction scheme, called PCoExtractor. Instead of using a time window, PCoExtractor continuously traces the events, removes unrelated device statuses that inconsistently react for the same activity, and constructs fine-grained correlations. Moreover, to increase the detection precision, this work newly defines a fine-grained correlation representation that reflects not only sensor values and functionalities of actuators but also their transitions and program states such as contexts. Compared to existing schemes, PCoExtractor detects and identifies 40.06% more faults for 4 IoT services with concurrent activities of 12 users while reducing 80.3% of detection and identification times.

In the Internet of Things (IoT) environments, cloud servers integrate various IoT devices including sensors and actuators, and provide new services that assist daily lives of users interacting with the physical world. While response time is a crucial factor of quality of the services, supporting short response time is challenging for the cloud servers due to a growing number and amount of connected devices and their communication. To reduce the burden of the cloud servers, fog computing is a promising alternative to offload computation and communication overheads from the cloud servers to fog nodes. However, since existing fog computing frameworks do not extract codes for fog nodes fully automatically, programmers should manually write and analyze their applications for fog computing. This work proposes Spinal Code, a new compiler-runtime framework for near-user computation that automatically partitions an original cloud-centric program into distributed sub-programs running over the cloud and fog nodes. Moreover, to reduce response time in the physical world, Spinal Code allows programmers to annotate latency sensitive actuators in a program, and optimizes the critical paths from required sensors to the actuators when it generates the sub-programs. This work implements 9 IoT programs across 4 service domains: healthcare, smart home, smart building and smart factory, and demonstrates that Spinal Code successfully reduces 44.3% of response time and 79.9% of communication on the cloud compared with a cloud-centric model.

In recent studies, sophisticated attack vectors that use a Rowhammer bug have been developed. These attacks are dangerous, given that they can corrupt data stored in arbitrary memory rows without accessing them. Successful Rowhammer attacks require to flip data of the target cell. However, non-target cells are also corrupted by the attacks. Such unwanted bit flips can lead to unexpected consequences such as an attack failure and a system crash. We propose a novel Rowhammer method, namely, Pinpoint rowhammer, which flips the target bit while suppressing unwanted bit flips. The basic idea is the use of an effective data pattern for the target bit and ineffective data patterns for non-target bits. We evaluate the proposed method by conducting 107,965 attack instances on four different dynamic random-access memory (DRAM) modules. The proposed method increases the attack success rate from 28.9% to 72.4%, when compared with the state-of-the-art method (double-sided Rowhammer). In addition, the proposed method suppresses 99.7% of the unwanted vulnerable cells.

A fast and reliable method to detect faulty IoT devices is indispensable in IoT environments. In this paper, we present DICE, an automatic method to detect and identify faulty IoT devices with context extraction. Our system works in two phases. In a precomputation phase, the system precomputes sensor correlation and the transition probability between sensor states known as context. During a real-time phase, the system finds a violation of sensor correlation and transition to detect and identify the faults. In detection, we analyze the sensor data to find any missing or newly reacting IoT devices that are deviating from already grouped correlated sensors, and state transition to find the presence of an abnormal sequence. Then, the system identifies the faulty device by comparing the problematic context with the probable ones. We demonstrate that DICE identifies faulty devices accurately and promptly through the evaluation on various fault types and datasets.

Modern servers are actively deploying Solid-State Drives (SSDs). However, rather than just a fast storage device, SSDs are complex devices designed for device-specific goals (e.g., latency, throughput, endurance, cost) with their internal mechanisms undisclosed to users as the proprietary asset, which leads to unpredictable, irregular inter/intra-SSD access latencies. This unpredictable irregular access latency has been a fundamental challenge to server architects aiming to satisfy critical quality-of-service requirements and/or achieve the full performance potential of commodity SSDs. In this paper, we propose SSDcheck, a novel SSD performance model to accurately predict the latency of next access to commodity black-box SSDs. First, after analyzing a wide spectrum of real-world SSDs, we identify key performance-critical features (e.g., garbage collection, write buffering) required to construct a general SSD performance model. Next, SSDcheck runs diagnosis code snippets to extract static feature parameters (e.g., size, threshold) from the target SSD, and constructs its performance model. Finally, during runtime, SSDcheck dynamically manages the performance model to predict the latency of the next access. Our evaluations show that SSDcheck achieves up to 98.96% and 79.96% on-average prediction accuracy for normal-latency and high-latency predictions, respectively. Next, we show the effectiveness of SSDcheck by implementing a new volume manager improving the throughput by up to 4.29x with the tail latency reduction down to 6.53%, and a new I/O request handler improving the throughput by up to 44.0% with the tail latency reduction down to 26.9%. We then show how to further improve the results of scheduling with the help of an emerging Non-Volatile Memory (e.g., PCM). SSDcheck does not require any hardware modifications, which can be harmlessly disabled for any SSDs uncovered by the performance model.

The explosion of networked devices has driven a new computing environment called the Internet of Things (IoT), enabling various services such as home automation and health monitoring. Despite the promising applicability of the IoT, developing an IoT service is challenging for programmers, because the programmers should integrate multiple programmable devices and heterogeneous third-party devices. Recent works have proposed integrated programming platforms, but they either require device-specific implementation for third-party devices without any device abstraction, or abstract all the devices to the standard interfaces requiring unnecessary abstraction of programmable devices. To integrate IoT devices with selective abstraction, this work revisits the object oriented programming (OOP) model, and proposes a new language extension and its compiler-runtime framework, called Esperanto. With three annotations that map each object to its corresponding IoT device, the Esperanto language allows programmers to integrate multiple programmable devices into one OOP program and to abstract similar third-party devices into their common ancestor classes. Given the annotations, the Esperanto compiler automatically partitions the integrated program into multiple sub-programs for each programmable IoT device, and inserts communication and synchronization code. Moreover, for the ancestor classes, the Esperanto runtime dynamically identifies connected third-party devices, and links their corresponding descendent objects. Compared to an existing approach on the integrated IoT programming, Esperanto requires 33.3% fewer lines of code to implement 5 IoT services, and reduces their response time by 44.8% on average.

Integrating various networked devices, the Internet of Things (IoT) enables various new services like home automation, making its market larger and more competitive. Although rapid development of an IoT application is crucial to keep up with the highly competitive IoT market, developing an IoT application is challenging for programmers because the programmers should integrate multiple programmable devices and heterogeneous third-party devices. Some IoT frameworks integrate programming environments of multiple devices, but they either require device-specific implementation for third-party devices without any device abstraction, or abstract all the devices to the standard interfaces requiring unnecessary abstraction of programmable devices. This work introduces the Esperanto framework that integrates IoT devices with selective abstraction, allowing rapid prototyping of an IoT application. Exploiting the correspondence between an object and a thing in the object oriented programming (OOP) model, the Esperanto framework allows programmers to write only one OOP program instead of multiple programs for each device, and to manipulate third-party devices with their common ancestor classes. Compared to an existing approach on the integrated IoT programming, Esperanto requires 33.3% fewer lines of code to implement 5 IoT services, and reduces their response time by 44.8% on average. Moreover, with an empirical study, this work shows that the Esperanto framework reduces the development time by 52.7%.

With a simple “If This Then That” syntax, IoT frameworks such as IFTTT and Microsoft Flow allow users to easily create custom applets integrating sensors and actuators. Users expect appropriate actions to be taken within a certain latency in response to sensor value changes while the sensors usually have limited battery power. Therefore, reading the sensor values at the right time point is crucial for the IoT frameworks to support real-time responses of the applets while saving battery lives of sensors. However, existing IoT frameworks periodically read the sensor data with fixed intervals without reflecting current sensor values and trigger conditions of applets, so the intervals are either too long to meet the real-time constraints, or too short wasting batteries of sensors. This work extends the existing IFTTT syntax for users to describe real-time constraints, and proposes the first real-time IoT framework with trigger condition-aware flexible polling intervals, called RT-IFTTT. RT-IFTTT analyzes current sensor values, trigger conditions and constraints of all the applets in the framework, and dynamically calculates the efficient polling intervals for each sensor. This work collects real-world sensing data from 10 physical sensors for 10 days, and shows that the RT-IFTTT framework with the proposed scheduling algorithm executes 100 to 400 applets according to user-defined real-time constraints with up to 64.12% less sensor polling counts compared to the framework with the fixed intervals.

Improvement in the security and availability is important for the success of the Internet of Things (IoT). Given that recent IoT devices are likely to have multiple functionalities and support third-party applications, this goal becomes challenging to achieve. Through an in-depth investigation of existing IoT frameworks, we focused on two inherent security flaws in their design caused by their device-centric approaches: (1) coarse-grained access control and (2) lack of resource isolation. Because of the coarse-grained access control, IoT devices suffer from over-privileged applications. Furthermore, the lack of resource isolation allows the possibility of Denial-of-Service attacks.

Twitter is a popular online social network service for sharing short messages (tweets) among friends. Its users frequently use URL shortening services that provide (i) a short alias of a long URL for sharing it via tweets and (ii) public click analytics of shortened URLs. The public click analytics is provided in an aggregated form to preserve the privacy of individual users. In this paper, we propose practical attack techniques inferring who clicks which shortened URLs on Twitter using the combination of public information: Twitter metadata and public click analytics. Unlike the conventional browser history stealing attacks, our attacks only demand publicly available information provided by Twitter and URL shortening services. Evaluation results show that our attack can compromise Twitter users' privacy with high accuracy.

Malicious crowdsourcing, also known as crowdturfing, has become an important security problem. However, detecting accounts performing crowdturfing tasks is challenging because human workers manage the crowdturfing accounts such that their characteristics are similar with the characteristics of normal accounts. In this paper, we propose a novel crowdturfing detection method, called CrowdTarget, that aims to detect target objects of crowdturfing tasks (e.g., post, page, and URL) not accounts performing the tasks. We identify that the manipulation patterns of target objects by crowdturfing workers are unique features to distinguish them from normal objects. We apply CrowdTarget to detect collusion-based crowdturfing services to manipulate account popularity on Twitter with artificial retweets. Evaluation results show that CrowdTarget can accurately distinguish tweets receiving crowdturfing retweets from normal tweets. When we fix the false-positive rate at 0.01, the best true-positive rate is up to 0.98.

The increasing use of mobile devices has triggered the development of location based services (LBS). By providing location information to LBS, mobile users can enjoy variety of useful applications utilizing location information, but might suffer the troubles of private information leakage. Location information of mobile users needs to be kept secret while maintaining utility to achieve desirable service quality. Existing location privacy enhancing techniques based on K-anonymity and Hilbertcurve cloaking area generation showed advantages in privacy protection and service quality but disadvantages due to the generation of large cloaking areas that makes query processing and communication less effective. In this paper we propose a novel location privacy preserving scheme that leverages some differential privacy based notions and mechanisms to publish the optimal size cloaking areas from multiple rotated and shifted versions of Hilbert curve. With experimental results, we show that our scheme significantly reduces the average size of cloaking areas compared to previous Hilbert curve method. We also show how to quantify adversary's ability to perform an inference attack on user location data and how to limit adversary's success rate under a designed threshold.

The HTML5 Geolocation API realizes location-based services via theWeb by granting web sites the geographical location information of user devices. However, the Geolocation API can violate a user's location privacy due to its coarse-grained permission and location models. The API provides either exact location or nothing to web sites even when they only require approximate location. In this paper, we first conduct case studies on numerous web browsers and web sites to explore how they implement and utilize the Geolocation API. We detect 14 vulnerable web browsers and 603 overprivileged web sites that can violate a user's location privacy. To mitigate the privacy threats of the Geolocation API, we propose a novel scheme that (1) supports fine-grained permission and location models, and (2) recommends appropriate privacy settings to each user by inspecting the location sensitivity of each web page. Our scheme can accurately estimate each web page's necessary geolocation degree (estimation accuracy: ~93.5%). We further provide suggestions to improve the Geolocation API.

Recent efforts towards mobile cloud propose to offload mobile applications to cloud servers for the improved performance and battery life of mobile devices. However, existing schemes completely ignore the costs of cloud resources by assuming that idle servers are always available for free of charge. These unrealistic assumptions make each server run only a small load to achieve the guaranteed high offload performance. Therefore, these schemes cannot be applied to real-world commercial clouds which aim to minimize the operation costs by maximizing the server throughput, and then charge users for their resource usage. In this paper, we propose CMcloud, a novel cost-effective mobile-to-cloud offloading platform, which works nicely under the real-world cloud environments. CMcloud minimizes both the server costs and the user service fee by offloading as many mobile applications to a single server as possible, while satisfying the target performance of all applications. To achieve such goals, CMcloud exploits novel architecture performance modeling and server migration techniques. Our implementation shows that CMcloud can improve the data enter throughput by 84% over a conventional static light-load scheme (or a 2.7x higher per-socket throughput.) Alternatively, CMcloud reduces the number of service failures by 83% over a static high-load scheme, while even improving the throughput by 31%.

Graphics processing units (GPUs) are important components of modern computing devices for not only graphics rendering, but also efficient parallel computations. However, their security problems are ignored despite their importance and popularity. In this paper, we first perform an in-depth security analysis on GPUs to detect security vulnerabilities. We observe that contemporary, widely-used GPUs, both NVIDIA's and AMD's, do not initialize newly allocated GPU memory pages which may contain sensitive user data. By exploiting such vulnerabilities, we propose attack methods for revealing a victim program's data kept in GPU memory both during its execution and right after its termination. We further show the high applicability of the proposed attacks by applying them to the Chromium and Firefox web browsers which use GPUs for accelerating webpage rendering. We detect that both browsers leave rendered webpage textures in GPU memory, so that we can infer which web pages a victim user has visited by analyzing the remaining textures. The accuracy of our advanced inference attack that uses both pixel sequence matching and RGB histogram matching is up to 95.4%.

Cloud infrastructure providers deploy Dynamic Resource Management (DRM) to minimize the cost of datacenter operation, while maintaining the Service Level Agreement (SLA). Such DRM schemes depend on the capability to migrate virtual machine (VM) images. However, existing migration techniques are not suitable for highly utilized clouds due to their latency and bandwidth critical memory transfer mechanisms. In this paper, we propose guide-copy migration, a novel VM migration scheme to provide a fast and silent migration, which works nicely under highly utilized clouds. The guide-copy migration transfers only the memory pages accessed at the destination node in the near future by running a guide version of the VM at the source node and a migrated VM at the destination node simultaneously during the migration. The guide-copy migration's highly accurate and low-bandwidth memory transfer mechanism enables a fast and silent VM migration to maintain the SLA of all VMs in the cloud.

Twitter is a popular social network service for sharing messages among friends. Because Twitter restricts the length of messages, many Twitter users use URL shortening services, such as bit.ly and goo.gl, to share long URLs with friends. Some URL shortening services also provide click analytics of the shortened URLs, including the number of clicks, countries, platforms, browsers and referrers. To protect visitors' privacy, they do not reveal identifying information about individual visitors. In this paper, we propose a practical attack technique that can infer who clicks what shortened URLs on Twitter. Unlike the conventional browser history stealing attacks, our attack methods only need publicly available information provided by URL shortening services and Twitter. Evaluation results show that our attack technique can compromise Twitter users' privacy with high accuracy.

Twitter is prone to malicious tweets containing URLs for spar, phishing, and malware distribution. Conventional Twitter spar detection schemes utilize account features such as the ratio of tweets containing URLs and the account creation date, or relation features in the Twitter graph. These detection schemes are ineffective against feature fabrications or consume much time and resources. Conventional suspicious URL detection schemes utilize several features including lexical features of URLs, URL redirection, HTIUIL content, and dynamic behavior. However, evading techniques such as time-based evasion and crawler evasion exist. in this paper, we propose WARNINGBIRD, a suspicious URL detection system for Twitter. Our system investigates correlations of URL redirect chains extracted from several tweets. Because attackers have limited resources and usually reuse them, their URL redirect chains frequently share the same URLs. We develop methods to discover correlated URL redirect chains using the frequently shared URLs and to determine their suspiciousness. We collect numerous tweets from the Twitter public timeline and build a statistical classifier using them. Evaluation results show that our classifier accurately and efficiently detects suspicious URLs. We also present WARNINGBIRD as a near real-time system for classifying suspicious URLs in the Twitter stream.

Optimized Link State Routing is a routing protocol that has been extensively studied for mobile ad-hoc networks. Link spoofing, which disturbs the routing service, is one of the critical security problems related to the OLSR protocol. Existing approaches against link spoofing attack have several drawbacks. In this paper, we propose an LT-OLSR protocol that broadcasts Hello messages to neighbors within two-hops to defend networks against link spoofing attacks. Simulation and analysis results show that the LT-OLSR protocol tolerates link spoofing attacks extensively. The contributions presented in this paper are as follows: (1) We design a mechanism to ensure the integrity of a routing table. (2) In addition, our approach against link spoofing attack is not only extensive but also compact. (3) Finally, it can be practically implemented under various types of MANET environments.

This paper proposes an algorithm to decide on the batch rekeying time for group key management schemes for Internet protocol television (IPTV) systems. Batch rekeying schemes can reduce the effect of membership changes in group key management schemes by collecting and processing several join and leave events at once. Because membership of IPTV systems frequently changes due to the frequent changes of TV channels viewed by subscribers, batch rekeying schemes are suitable to IPTV systems. Our algorithm considers one more factor; programs broadcasted on IPTV channels can have various values. By computing the expected loss from the value of programs, and the number and time of join and leave events, our algorithm decides on the next rekeying time where the expected loss becomes larger than the predefined loss value given by the service provider.

As the use of mobile devices increases, a location-based service (LBS) becomes increasingly popular because it provides more convenient context-aware services. However, LBS introduces problematic issues for location privacy due to the nature of the service. Location privacy protection methods based on k-anonymity and l-diversity have been proposed to provide anonymized use of LBS. However, the k-anonymity and l-diversity methods still can endanger the user's privacy because location semantic information could easily be breached while using LBS. This paper presents a novel location privacy protection technique, which protects the location semantics from an adversary. In our scheme, location semantics are first learned from location data. Then, the trusted-anonymization server performs the anonymization using the location semantic information by cloaking with semantically heterogeneous locations. Thus, the location semantic information is kept secure as the cloaking is done with semantically heterogeneous locations and the true location information is not delivered to the LBS applications. This paper proposes algorithms for learning location semantics and achieving semantically secure cloaking.

Reverse engineering is the process of discovering a high-level structure and its semantics from a lower-level structure. In order to prevent malicious use of reverse engineering against binaries, various techniques have been developed called binary obfuscation. Obfuscated binary is a transformed binary which retains original binary's executing behavior while its outer representation obstructs the reverse engineering. In this paper we propose three novel approaches to improve the binary obfuscation. First we propose a generalized binary obfuscation algorithm that covers any specific or whole part of a binary code by using confusing code and redirecting control-flow using exceptions. Second, we employ a data-mining method to make our obfuscated binary look like a normal binary. And third, we address the issue that the previous techniques could not be applied to Windows binaries by designing a new exception hooking mechanism in Windows. Experimental results show that our obfuscated binary can hide 60--90% of the original instructions from reverse engineering tools, while its execution slows down a little, and moreover the obfuscated binary's stealth can be guaranteed.

In most cases, the use of digital contents on several devices is blocked by digital rights management (DRM) technology to protect the rights of digital content owners, which is called as the DRM's walled garden strategy. This strategy has raised many legal, economical, and ethical problems. DRM interoperability can complement this strategy. However, there is no agreeable systematic interoperability scheme between various DRM systems. This problem cannot be solved without the cooperation and participation of both DRM technology providers and content providers. Some previous attempts to solve the DRM interoperability problem have suggested that both providers need to open parts of their security properties, without the assurance of a beneficial outcome. They were therefore reticent about participating. In this paper, we propose a secure mutual-profitable DRM interoperability scheme which minimizes disclosure of the security properties of DRM technology providers and content providers while preserving their profits. We use a designated proxy re-encryption scheme to allow the providers to designate a proxy which re-encrypts their digital contents and a neutral format scheme to enable format-independent translations. Moreover, we allow the providers to manage and trace their digital contents, and to request additional fees for interoperability services. We describe detailed protocols and analyze the scheme. We also introduce a prototype implementation.

Recently, P2P file sharing systems have been designed to enable peers to concurrently download files fragmented into small blocks from multiple sources to improve the download speed. If block corruption occurs during download, the corresponding block is downloaded again until the corruption does not occur any more. However, malicious peers share corrupt blocks intentionally, called "forged blocks," which cause significant waste of network bandwidth and delay in download completion. In this paper, we propose a method of excluding forged files that comprise forged blocks from the P2P systems. The method has an algorithm for systematically detecting forged files based on corruption reports given by peer agents and preventing the files from being searched by any further queries. Experimental results show that the proposed method sufficiently excludes forged files only, and is tolerable to false reports.

Power-aware scheduling problem has been a recent issue in cluster systems not only for operational cost due to electricity cost, but also for system reliability. As recent commodity processors support multiple operating points under various supply voltage levels, Dynamic Voltage Scaling (DVS) scheduling algorithms can reduce power consumption by controlling appropriate voltage levels. In this paper, we provide power-aware scheduling algorithms for bag-of-tasks applications with deadline constraints on DVS-enabled cluster systems in order to minimize power consumption as well as to meet the deadlines specified by application users. A bag-of-tasks application should finish all the sub-tasks before the deadline, so that the DVS scheduling scheme should consider the deadline as well. We provide the DVS scheduling algorithms for both time-shared and space-shared resource sharing policies. The simulation results show that the proposed algorithms reduce much power consumption compared to static voltage schemes.

Market-based resource management is becoming an emerging issue as the utilization of grid computing is growing rapidly, particularly in the business field. In this paper, we provide a new imprecise computation grid application model for flexible market-based resource management. Each job in a grid application has two parts: mandatory part for the minimum quality and optional part for additional computations. This application model can be applied to QoS-related grid applications and used in adaptive resource management. We also provide scheduling algorithms for resource allocation of IC grid applications. Simulation results show that better utility is achieved when users specify both mandatory and optional requirements.

Key issue in wireless real-time communications is to meet the real-time constraint with low energy consumption. In this paper, we propose an energy-efficient error correcting scheme for weakly hard real-time communications in wireless networks. A weakly hard read-time communication should send at least m messages during any window of k periods. The proposed scheme adaptively selects an error correcting code under the current communication status in order to meet the (m, k)-constraint and minimize the energy consumption. Simulation results show that the suggested scheme provides better performance in terms of the (m, k)- constraint meeting rate per unit energy consumption.

Since the amount of network traffic has rapidly increased with the WWW expansion, users have experienced a long latency when retrieving Web pages. To solve the latency problem, we propose a client-side prefetching mechanism, which reflects changes on Web document structures and utilizes information from the entrance pages of frequently visited Web sites. It starts by constructing link graphs by gathering usage information of visited Web sites, and predicts the next document to be referenced based on the overall displayed documents in the Web browser. We also manage entrance pages not to be easily replaced from the cache. Our simulation results show that it has a remarkably improved performance: an increased cache hit ratio (by 48%) and a high prefetching effect (by 297%), with a slightly increased network overhead compared to similar previous schemes.

The problem of finding an optimal product sequence for sequential multiplication of a chain of matrices (the matrix chain ordering problem, MCOP) is well-known. We consider the problem of finding an optimal product schedule for evaluating a chain of matrix products on a parallel computer (the matrix chain scheduling problem, MCSP). The difference between MCSP and MCOP is that MCOP pertains to a product sequence for single processor systems and MCSP pertains to a sequence of concurrent matrix products for parallel systems. The approach of parallelizing each matrix product after finding an optimal product sequence for single processor systems does not always guarantee minimum evaluation time on parallel systems since each parallelized matrix product may use processors inefficiently. We introduce a new processor scheduling algorithm for MCSP which reduces the evaluation time of a chain of matrix products on a parallel computer, even at the expense of a slight increase in the total number of operations. Given a chain of n matrices and a matrix product utilizing at most P/k processors in a P-processor system, the proposed algorithm approaches k(n-1)/(n+klog(k)-k) times the performance of parallel evaluation using the optimal sequence found for MCOP. Experiments performed on a Fujitsu AP1000 multicomputer also show that the proposed algorithm significantly decreases the time required to evaluate a chain of matrix products in parallel systems.

When a client requests a real-time connection that requires an excessive amount of resources and/or a very high level of QoS, the network service provider may have to reject the request, and only a small number of connections could be accepted. On the other hand, if the client requests only the minimum level of QoS, he may receive only a bare-bones service even when there are plenty of resources available. One way of utilizing resources efficiently is to specify flexible (elastic) QoS requirements that can be adapted to the availability of network resources. S.J. Han et al. (1997) proposed to allocate one primary channel and one or more backup channels to each dependable real-time (DR) connection. One drawback of this scheme is the severe reduction in number of DR connections that can be accommodated, due mainly to the need for reserving resources for backups. This is equivalent to wasting precious resources in the absence of faults as far as the system's ability of accepting DR connections is concerned. By using elastic QoS for this DR communication service, one can accept substantially more DR connections and improve the utilization of resources efficiently and significantly. We analyze the DR communication service with elastic QoS. Fault tolerance is achieved by allocating one backup channel to each DR connection. A Markov model is developed and used to analyze the average QoS level allotted to the primary channel of each DR connection. Our evaluation results show that the proposed Markov model accurately represents the behavior of DR connections with elastic QoS.

Fault-tolerant computer systems are being used increasingly in such applications as e-commerce, banking, and stock trading, where privacy and integrity of data are as important as the uninterrupted operation of the service provided. While much attention has been paid to the protection of data explicitly communicated over the Internet, there are also other sources of information leakage that must be addressed. This paper addresses one such source of information leakage caused by checkpointing, which is a common method used to provide continued operation in the presence of faults. Checkpointing requires communication of memory state information, which may contain sensitive data, over the network to a reliable backing store. Although the method of encrypting all of this memory state information can protect the data, such a simplistic method is an overkill that can result in a significant slowdown of the target application. This paper examines ways to combine the operations required to perform incremental checkpointing with those required to encrypt this memory state data. Analysis and experimentation on an actual system are used to show that the proposed secure checkpointing schemes are feasible and require a relatively low level of overhead.

Recently proposed probabilistic checkpointing has one drawback, naming aliasing. When analyzed, 64-bit signatures show negligible possibility of aliasing. But in practice, the shift-XOR signature generation function used with probabilistic checkpointing shows a high aliasing rate, which limits the practicality of probabilistic checkpointing. In this paper, two enhancements are considered to make probabilistic checkpointing more reliable. One is the signature generation function and the other is the recovery scheme. In the signature generation function part, we propose two signature generation functions: HALF for small block sizes (less than or equal to 256 bytes) and C-HALF(CRC combined HALF) for large block sizes (larger than 256 bytes), which have an aliasing probability similar to analytic results and small overhead. In the recovery scheme part, we propose a recovery scheme which ensures the safety of probabilistic checkpointing. To examine the correctness of previous checkpoints at recovery time, the proposed recovery scheme uses a spare node. We analyze the recovery scheme using a mathematical model. Also an optimal checkpoint interval is derived using the model.

In this paper we propose a real-time communication scheme that can be used in general point-to-point real-time multicomputer systems with wormhole switching. Real-time communication should satisfy the two requirements of predictability and priority handling. Since traditional wormhole switching does not support priority handling which is essential in real-time computing, flit-level preemption is adopted in our wormhole switching. Also, we develop an algorithm to determine the message transmission delay upper bound to predict worst-case message delay. Simulation results show that the delay upper bounds calculated using the proposed algorithm are very close to actual average message transmission delays for messages with high priorities.

In this paper, we consider the mesh with a single bus as a multi-computer topology that enhances the communication capability of the mesh and show that the mesh with a single bus has more salient properties than the mesh, the hypercube, and other mesh variants. These properties are small diameter, relatively small degree, small average distance, suitable for broadcasting, small initial data distribution time, etc. We propose a dynamic load distribution algorithm to utilize the enhanced communication capability of the mesh with a single bus. Also, asynchronous bus control and arbitration logic is designed to support the proposed algorithm efficiently. It is shown through simulation that the proposed dynamic load distribution is superior to the previous receiver-initiated diffusion method known as the best to-date. The proposed algorithm shows better total execution time of tasks and better processor utilization with a smaller number of task migrations.

This paper presents a new dynamic load balancing algorithm for hypercube multicomputers with faulty nodes. The emphasis in our method is on obtaining global load information and performing task migration using "short paths" in a synchronous manner so that a minimal amount of communication overhead is required. To accomplish this, we present an algorithm for constructing a new logical topology from a hypercube topology with faulty nodes. This new topology is used to obtain the global load information and to perform task migration. Simulation results are used to evaluate the performance of our dynamic load balancing method. The proposed strategy shows good performance in the case of a small number of faulty nodes when compared with previous methods.

Modeling the perfomance of space-shared multicomputers is a non-trivial task mainly due to difficulty in modeling the effect of external fragmentation on system performance. Mesh-connected multicomputers are hard to model in particular because of great variance in job sizes. Therefore, researchers have relied on simulation method to evaluate the mesh performance. We propose a novel modeling technique called hybrid method in this paper. The proposed technique utilizes simulation method to estimate the capacity of a system. Then, a queueing model with multiple servers is constructed using the system capacity as the number of servers in the queueing system. The technique is validated through simulation experiments. The results reveal that the hybrid method provides very close estimation of the mesh performance with very little overhead. The proposed technique can also be used for performance modeling of other multicomputers with different topologies.

In this paper, we present the problem of scheduling real-time jobs in a hypercube system and propose a scheduling algorithm. The goals of the proposed scheduling algorithm are to determine whether all jobs can complete their processing before their fixed deadlines in a hypercube system and to find such a schedule. Each job is associated with a computation time, a deadline, and a dimensional requirement. Determining a schedule such that all jobs meet before their respective fixed deadlines in a hypercube system when preemption is not allowed is an NP-complete problem. Hence, we present a heuristic scheduling algorithm for scheduling non-preemptable real-time jobs in a hypercube system. Finally, we evaluate the proposed algorithm using simulation.

In this paper, we consider a load-balancing process allocation method for fault-tolerant multicomputer systems that balances the load before as well as after faults start to degrade the performance of the system. In order to be able to tolerate a single fault, each process (primary process) is duplicated (i.e., has a backup process). The backup process executes on a different processor from the primary, checkpointing the primary process and recovering the process in the primary process fails. In this paper, we formalize the problem of load-balancing process allocation and propose a new process allocation method and analyze the performance of the proposed method. Simulations are used to compare the proposed method with a process allocation method that does not take into account the different load characteristics of the primary and backup processes. While both methods perform well before the occurrence of a fault, only the proposed method maintains a balanced load after the occurrence of such a fault.

Task-execution times are one of the most important parameters in scheduling tasks. Most scheduling algorithms are based on the assumption that either worst-case task-execution times are known to the scheduler or no information on execution times is available at all. While scheduling tasks based on worst-case execution times can guarantee to meet their timing requirements, it may lead to severe under-utilization of CPUs because worst-case execution times could be one or two orders of magnitude larger than the corresponding actual values. Scheduling tasks based on the execution time distribution (instead of worst-case execution times) is known to improve system utilization significantly. In this paper, we propose a model to predict task execution times in a distributed system. The model considers several factors which affect the execution time of each task. These factors are classified into two groups: intrinsic and extrinsic. The intrinsic factors control the flow within a task, while the extrinsic factors include communication and synchronization delays between tasks. By simplifying the extrinsic factors, we represent a distributed system with a simple queuing model. The proposed queuing model consists of two stations: one for computation and the other for communication and synchronization.

In a multicomputer that uses wormhole routing or virtual cut-through circuit switching, the communication delay in sending a message between two processors along a path A increases significantly if the message is "blocked" by another message using one of the channels in path A. Such "blocking" can only occur if there is contention for a common channel by two or more paths. In this paper, we consider the problem of selecting contention-free or minimum-contention paths for a set of communicating tasks that have been mapped onto nodes in a multicomputer, This problem is formalized and shown to be an NPhard problem. thus, a heuristic solution is proposed for general static interconnection networks. Simulations results show that our method performs significantly better than alternative methods for this problem.

We present an analytical model for the performance evaluation of hypercube computers. This analysis is aimed at modeling a deadlock-free wormhole routing scheme prevalent on second generation hypercube systems. Probability of blocking and average message delay are the two performance measures discussed. We start with the communication traffic to find the probability of blocking. The traffic analysis can capture any message destination distribution. Next, we find the average message delay that consists of two parts. The first part is the actual message transfer delay between any source and destination nodes. The second part of the delay is due to blocking caused by the wormhole routing scheme. The analysis is also extended to virtual cut-through routing and random wormhole routing techniques. The validity of the model is demonstrated by comparing analytical results with those from simulation.>

Recently, several variations of the hypercube have been proposed to enhance its performance and reliability. The folded hypercube is one of these variations, in which an extra link is added to each node providing a direct connection to the node located farthest from it. In this paper, we propose a new operation mode of the folded hypercube to enhance its performance and fault-tolerance. There are (/sub ksup n+1/) regular k-cubes within a folded hypercube of dimension n, denoted by FQ/sub n/. We introduce another type of hypercube, called the twisted hypercube, to improve the performance and fault tolerance of the folded hypercube. The problems of finding a subcube of given size in an FQ/sub n/ and routing messages within the subcube are addressed for the proposed operation mode. The advantages of the proposed operation mode over the regular-hypercube operation mode are analyzed in terms of dependability and robustness. The proposed operation mode is shown to make significant improvements over the regular-hypercube operation mode in both dependability and robustness. Because the new operation mode can be applied to only an (n-1)-subcube level for a given FQ/sub n/, we present general form of folded hypercube, thus enhancing the availability of subcubes of any dimension m>

Processor allocation and job scheduling are com plementary techniques to improve the performance of multiprocessors. It has been observed that all the hypercube allocation policies with the FCFS schedul ing show little performance difference. A greater im pact on the performance can be obtained by efficient job scheduling. This paper presents an effort in that direction by introducing a new scheduling algorithm called lazy scheduling for hypercubes. The motivation of this scheme is to eliminate the limitations of the FCFS scheduling. This is done by maintaining sep arate queues for different job sizes and delaying the allocation of a job if any other job(s) of the same di mension is(are) running in the system. Simulation studies show that the hypercube performance is dra matically enhanced by using the lazy scheme as com pared to the FCFS scheduling. Comparison with a re cently proposed scheme called scan indicates that the lazy scheme performs better than scan under a wide range of workloads.

Wormhole routing with the e-cube algorithm is an excellent solution for deadlock-free interprocess communication in healthy hypercubes. However, it does not work for injured hypercubes where some nodes and/or links are faulty. The authors propose a new deadlock-free routing scheme in an injured hypercube with the wormhole routing capability. All previously proposed schemes suggest the use of virtual channels to avoid the cycle of resource dependency. By contrast, the authors' scheme is based on the re-establishment of a routing path to the destination, but it does not always yield a shortest path between the source and destination. The proposed routing scheme uses either wormhole routing or staged routing, depending on the availability of one or more healthy (n-2)-cubes within an injured n-cube.>

A unified analytical model for computing the task-based dependability (TDB) of hypercube architectures is presented. A hypercube is deemed operational as long as a task can be executed on the system. The technique can compute both reliability and availability for two types of task requirements-I-connected model and subcube model. The I-connected TBD assumes that a connected group of at least I working nodes is required for task execution. The subcube TBD needs at least an m-cube in an n-cube, mor=I or x>or=2/sup m/) are working in an n-cube at time t by the conditional probability that the hypercube can satisfy any one of the two task requirements from x working nodes. Recursive models are proposed for the two types of task requirements to find the connection probability. The subcube requirement is extended to find multiple subcubes for analyzing multitask dependability. The analytical results are validated through extensive simulation.>

An analytical model for the performance evaluation of asynchronous hypercubes is presented. This analysis is aimed at modeling a deadlock-free wormhole routing scheme prevalent on second-generation hypercube systems. Probability of blocking and average message delay are discussed. The communication traffic to find the probability of blocking is the starting point. The traffic analysis can capture any message destination distribution. The average message delay that consists of two parts is found. The analysis is extended to virtual cut-through routing and random wormhole routing techniques. The validity of the model is demonstrated.>

In this paper, we present an analytical model for computing the dependability of hypercube systems. The model, referred to as task-based dependability (TBD), is developed under the assumption that a task needs at least an m-cube (m < n) in an n-cube for its execution. Two probabilistic terms are required for computing this dependability. The first is the probability of any x nodes working out of 2n nodes. The second term is a conditional probability that at least a connected m-cube exists among those x working nodes. This term is computed using a recursive expression. Two dependability measures, reliability and availability, are analyzed in this paper. A combinatorial enumeration is used in the reliability analysis, and a machine repairman model is used in the availability analysis to find the first probability. The machine repairman model is modified to capture imperfect coverage and imprecise repair. The TBD model is also extended to find multitask dependability. Numerical results are presented for n-cubes with different task requirements and are validated through extensive simulation. It is observed that an m-cube requirement is highly restrictive compared to the simple 2m-connected node requirement.

An efficient processor allocation policy is presented for hypercube computers. The allocation policy is called free list since it maintains a list of free subcubes available in the system. An incoming request of dimension k (2/sup k/ nodes) is allocated by finding a free subcube of dimension k or by decomposing an available subcube of dimension greater than k. This free list policy uses a top-down allocation rule in contrast to the bottom-up approach used by the previous bit-map allocation algorithms. This allocation scheme is compared to the buddy, gray code (GC), and modified buddy allocation policies reported for the hypercubes. It is shown that the free list policy is optimal in a static environment, as are the other policies, and it also gives better subcube recognition ability compared to the previous schemes in a dynamic environment. The performance of this policy, in terms of parameters such as average delay, system utilization, and time complexity, is compared to the other schemes to demonstrate its effectiveness. The extension of the algorithm for parallel implementation, noncubic allocation, and inclusion/exclusion allocation is also given.>