Search

This paper presents fundamental results about how zero-curvature (paper) surfaces behave near creases and apices of cones. These entities are natural generalizations of the edges and vertices of piecewise-planar surfaces. Consequently, paper surfaces may furnish a richer and yet still tractable class of surfaces for computer-aided design and computer graphics applications than do polyhedral surfaces.

The fast access to data and high parallel processing in high-performance computing instigates an urgent demand on the improvement of the NVMe storage within modern data centers. However, the former NVMe virtualization's unsatisfactory performance demonstrates that NVMe devices are often underutilized within cloud platforms. An NVMe virtualization mechanism with high performance and device sharing has captured researchers and developers' attention. This paper introduces MDev-NVMe, a new virtualization solution for NVMe storage device with (1) full NVMe storage virtualization for VMs running native NVMe driver, (2) a mediated pass-through mechanism for NVMe management, and (3) adaptive configuration of active polling optimization to simultaneously achieve high throughput, low latency performance, and substantial device scalability. We practically implement the MDev-NVMe as a Linux kernel module. This paper subsequently evaluates MDev-NVMe with Intel OPTANE and P3600 SSD by comparing several mainstream NVMe virtualization mechanisms using application-level I/O benchmarks. MDev-NVMe with active polling can demonstrate a 142% improvement over native (interrupt-driven) throughput and over 2.5 × the Virtio throughput with only 70% native average latency and 31% Virtio average latency. Finally, the advantages of MDev-NVMe and the importance of adaptive polling are discussed, offering evidence that MDev-NVMe is a superior virtualization choice for cloud storage.

To mitigate the long write latency of NAND flash memory, solid-state drives (SSDs) typically use capacitor-powered SRAM or DRAM to realize internal nonvolatile write buffering. Due to the cost and size constraints, intra-SSD capacitors can only power a very small amount (e.g., 8 MB or 16 MB) of nonvolatile write buffer. As a result, most commercial SSDs simply use the few MBs of capacitor-powered write buffer in the first-in first-out (FIFO) manner without employing any advanced data eviction policy. This paper presents a set of design strategies across the application and storage device levels that can effectively leverage the very small intra-SSD write buffer to noticeably reduce the amount of data being physically written to NAND flash memory. These cross-layer design strategies are primarily geared towards mainstream applications (e.g., database and filesystem) that heavily involve logging/journaling operations. This paper discusses different strategies for realizing flash memory write traffic reduction through nominal application-level modifications, and presents solutions to accordingly manage the write buffer at small processing and memory resource usage inside SSDs. To evaluate the potential effectiveness, we carried out case studies based upon popular open-source relational databases and filesystem. With only 8 MB of intra-SSD capacitor-powered write buffer, our experimental results show that the developed design solutions can reduce up to 39.7, 36.5, and 52.9 percent of total NAND flash memory write traffic for MySQL, ext4 , and PostgreSQL, respectively.

The twelve papers in this special section focus on hardware security. This topic is becoming a significant challenge in modern computing systems. Recently discovered hardware vulnerabilities, such as Spectre and Meltdown, are striking evidence that today’s computing systems are untenable without deliberate consideration of the security aspects at the design time. The papers address various topics related to hardware security: secure-by-design architectures, secure speculative execution, secure system integration of untrusted chiplets, malware detection, program analysis using power side channels, architecture support for forensics, and efficient implementations of security modules.

Attribute-based encryption (ABE) has opened up a popular research topic in cryptography over the past few years. It can be used in various circumstances, as it provides a flexible way to conduct fine-grained data access control. Despite its great advantages in data access control, current ABE based access control system cannot satisfy the requirement well when the system judges the access behavior according to attribute comparison, such as “greater than $x$ ” or “less than $x$ ”, which are called comparable attributes in this paper. In this paper, based on a set of well-designed sub-attributes representing each comparable attribute, we construct a comparable attribute-based encryption scheme (CABE for short) to address the aforementioned problem. The novelty lies in that we provide a more efficient construction based on the generation and management of the sub-attributes with the notion of 0-encoding and 1-encoding. Extensive analysis shows that: Compared with the existing schemes, our scheme drastically decreases the storage, communication and computation overheads, and thus is more efficient in dealing with the applications with comparable attributes.

The in-memory cache system is a performance-critical layer in today’s web server architectures. Memcached is one of the most effective, representative, and prevalent among such systems. An important problem is on its memory allocation. The default design does not make the best use of the memory. It is unable to adapt when the demand changes, a problem known as slab calcification . This paper introduces locality-aware memory allocation (LAMA), which addresses the problem by first analyzing the locality of Memcached’s requests and then reassigning slabs to minimize the miss ratio or the average response time. By evaluating LAMA using various industry and academic workloads, the paper shows that LAMA outperforms existing techniques in the steady-state performance, the speed of convergence, and the ability to adapt to request pattern changes, and overcome slab calcification. The new solution is close to optimal, achieving over 98 percent of the theoretical potential. Furthermore, LAMA can also be adopted in resource partitioning to guarantee quality-of-service (QoS).

Nowadays, a significant part of all network accesses comes from embedded and battery-powered devices, which must be energy efficient. This paper demonstrates that a hardware (HW) implementation of network security algorithms can significantly reduce their energy consumption compared to an equivalent software (SW) version. The paper has four main contributions: (i) a new feature extraction algorithm, with low processing demands and suitable for hardware implementation; (ii) a feature selection method with two objectives—accuracy and energy consumption; (iii) detailed energy measurements of the feature extraction engine and three machine learning (ML) classifiers implemented in SW and HW—Decision Tree (DT), Naive-Bayes (NB), and k-Nearest Neighbors (kNN); and (iv) a detailed analysis of the tradeoffs in implementing the feature extractor and ML classifiers in SW and HW. The new feature extractor demands significantly less computational power, memory, and energy. Its SW implementation consumes only 22 percent of the energy used by a commercial product and its HW implementation only 12 percent. The dual-objective feature selection enabled an energy saving of up to 93 percent. Comparing the most energy-efficient SW implementation (new extractor and DT classifier) with an equivalent HW implementation, the HW version consumes only 5.7 percent of the energy used by the SW version.

The twelve papers in this special section focus on machine learning architectures and accelerators. Deep learning or deep neural networks (DNNs), as one of the most powerful machine learning techniques, has achieved extraordinary performance in computer vision and surveillance, speech recognition and natural language processing, healthcare and disease diagnosis, etc. Various forms of DNNs have been proposed, including Convolutional Neural Networks, Recurrent Neural Networks, Deep Reinforcement Learning, Transformer model, etc. Deep learning exhibits an offline training phase to derive the weight parameters from an excessive training dataset, as well as an online inference phase to perform classification/prediction/perception/ control tasks based on the trained model. The paper in this section aim to find a convergence of software and hardware/architecture. It aims at DNN algorithms, parallel computing, and compiler code generation techniques that are hardware/architecture friendly, as well as computer architectures that are universal and consistently highly performant on a wide range of DNN algorithms and applications. In this co-design and co-optimization framework we can mitigate the limitation of investigating in only a single direction, shedding some light on the future of embedded, ubiquitous artificial intelligence.

To cope with uncertainties and variations that emanate from hardware and/or application characteristics, dynamic power management (DPM) frameworks must be able to learn about the system inputs and environmental variations, and adjust the power management policy on the fly. In this paper, an online adaptive DPM technique is presented based on the model-free reinforcement learning (RL) method, which requires no prior knowledge of the state transition probability function and the reward function. In particular, this paper employs the temporal difference (TD) learning method for semi-Markov decision process (SMDP) as the model-free RL technique since the TD method can accelerate convergence and alleviate the reliance on the Markovian property of the power-managed system. In addition, a novel workload predictor based on an online Bayesian classifier is presented to provide effective estimation of the workload characteristics for the RL algorithm. Several improvements are proposed to manage the size of the action space for the learning algorithm, enhance its convergence speed, and dynamically change the action set associated with each system state. In the proposed DPM framework, power-latency tradeoffs of the power-managed system can be precisely controlled based on a user-defined parameter. Extensive experiments on hard disk drives and wireless network cards show that the maximum power saving without sacrificing any latency is 18.6 percent compared to a reference expert-based approach. Alternatively, the maximum latency saving without any power dissipation increase is 73.0 percent compared to the existing best-of-breed DPM techniques.

With increasing demands on cloud computing, protecting guest virtual machines (VMs) from malicious attackers has become critical to provide secure services. The current cloud security model with software-based virtualization relies on the invulnerability of the software hypervisor and its trustworthy administrator with the root permission. However, compromising the hypervisor with remote attacks or root permission grants the attackers with a full access capability to the memory and context of a guest VM. This paper proposes a HW-based approach to protect guest VMs even under an untrusted hypervisor. With the proposed mechanism, memory isolation is provided by the secure hardware, which is much less vulnerable than the software hypervisor. The proposed mechanism extends the current hardware support for memory virtualization based on nested paging with a small extra hardware cost. The hypervisor can still flexibly allocate physical memory pages to virtual machines for efficient resource management. In addition to the system design for secure virtualization, this paper presents a prototype implementation using system management mode. Although the current system management mode is not intended for security functions and thus limits the performance and complete protection, the prototype implementation proves the feasibility of the proposed design.

This paper presents a novel technique, called Zombie Chasing, for efficient flash management in solid state drives (SSDs). Due to the unique characteristics of NAND flash memory, SSDs need to accurately understand the liveness of the data stored in themselves. Recently, the TRIM command has been introduced to notify SSDs of dead data caused by file deletions, which otherwise could not be tracked by SSDs. This paper goes one step further and proposes a new liveness state, called the zombie state, to denote live data that will be dead shortly due to the corresponding dirty data in the buffer cache. We also devise new zombie-aware garbage collection algorithms which utilize the information about such zombie data inside SSDs. To evaluate Zombie Chasing, we implement zombie-aware garbage collection algorithms in the prototype SSD and modify the Linux kernel and the Oracle DBMS to deliver the information on the zombie data to the prototype SSD. Through comprehensive evaluations using our in-house micro-benchmark and the TPC-C benchmark, we observe that Zombie Chasing improves SSD performance effectively by reducing garbage collection overhead. Especially, our evaluation with the TPC-C benchmark on the Oracle DBMS shows that Zombie Chasing enhances the Transactions Per Second (TPS) value by up to 22% with negligible overhead.

Functionally equivalent web services can be composed to form more reliable service-oriented systems. However, the choice of fault tolerance strategy can have a significant effect on the quality-of-service (QoS) of the resulting service-oriented systems. In this paper, we investigate the problem of selecting an optimal fault tolerance strategy for building reliable service-oriented systems. We formulate the user requirements as local and global constraints and model the selection of fault tolerance strategy as an optimization problem. A heuristic algorithm is proposed to efficiently solve the optimization problem. Fault tolerance strategy selection for semantically related tasks is also investigated in this paper. Large-scale real-world experiments are conducted to illustrate the benefits of the proposed approach. The experimental results show that our problem modeling approach and the proposed selection algorithm make it feasible to manage the fault tolerance of complex service-oriented systems both efficiently and effectively.

The multi-level cell (MLC) NAND flash memory technology enables multiple bits of information to be stored in a memory cell, thus making it possible to increase the density of flash memory without increasing the die size. In MLC NAND flash memory, each memory cell can be programmed as a single-level cell or a multi-level cell at runtime because of its performance/capacity asymmetric programming property, which is called flexible programming in this paper. Therefore, MLC flash memory has a potential to achieve the high performance of SLC flash memory while preserving its maximum capacity. In this paper, we present a flexible flash file system, called FlexFS, which takes advantage of flexible programming. FlexFS divides a flash memory medium into SLC and MLC regions, and then dynamically changes two different types of regions to provide an optimal storage solution to end-users in terms of performance and capacity. FlexFS also provides a reasonable storage lifetime by managing the wearing rate of NAND flash memory, which is accelerated by the use of flexible programming. Our implementation of FlexFS in the Linux 2.6 kernel shows that it achieves the I/O performance comparable to SLC flash memory while guaranteeing the capacity of MLC flash memory in various real-world workloads.

Hardware Malware Detectors (HMDs) have recently been proposed to make systems more malware-resistant. HMDs use hardware features to detect malware as a computational anomaly. Several aspects of the detector construction have been explored, leading to detectors with high accuracy. In this paper, we explore whether malware developers can modify malware to avoid HMDs detection. We show that existing HMDs can be effectively reverse-engineered and subsequently evaded. Next, we explore whether retraining using evasive malware would help and show that retraining is limited. To address these limitations, we propose a new type of Resilient HMDs (RHMDs) that stochastically switch between different detectors. These detectors can be shown to be provably more difficult to reverse engineer based on recent results in probably approximately correct (PAC) learnability theory. We show that indeed such detectors are resilient to both reverse engineering and evasion, and that the resilience increases with the number and diversity of the individual detectors. Furthermore, we show that an optimal switching strategy between the RHMDs base detectors not only reduces misclassification on evasive malware but also maintains high classification accuracy on non-evasive malware. Our results demonstrate that these HMDs offer effective defense against evasive malware at low additional complexity

Temporal prefetchers are powerful because they can prefetch irregular sequences of memory accesses, but temporal prefetchers are commercially infeasible because they store large amounts of metadata in DRAM. This paper presents Triage, the first temporal data prefetcher that does not require off-chip metadata. Triage builds on two insights: (1) Metadata are not equally useful, so the less useful metadata need not be saved, and (2) for irregular workloads, it is more profitable to use portions of the LLC to store metadata than data. We also introduce novel schemes to identify useful metadata, to compress metadata, and to determine the fraction of the LLC to dedicate for metadata.

As one of most successful industrial realizations of Internet of Things, a smart grid is a smart IoT system that deploys widespread smart meters to capture fine-grained data on residential power usage. It suffers diverse privacy attacks, which seriously increases the risk of violating the privacy of customers. Although some solutions have been proposed to address this privacy issue, most of them mainly rely on a trusted party and focus on the sanitization of metering masurements. However, these solutions are vulnerable to advanced attacks. In this paper, we propose a decentralized mechanism for privacy-preserving computation in smart grid called DDP, which leaverages the differential privacy and extends the data sanitization from the value domain to the time domain. Specifically, we inject Laplace noise to the measurements at the end of each customer in a distributed manner, and then use a random permutation algorithm to shuffle the power measurement sequence, thereby enforcing differential privacy after aggregation and preventing the sensitive power usage mode informaton of the customers from being inferred by other parties. Extensive experiments demonstrate that DDP shows an outstanding performance in terms of privacy from the non-intrusive load monitoring (NILM) attacks and utility by using two different error analysis.

QoS routing plays a critical role in providing QoS support in the Internet. Most existing QoS routing algorithms employ the strategy of unidirectional search in route selection. Bidirectional search has been recognized as an effective strategy for fast route acquisition in identifying the shortest path connecting a pair of nodes. However, its efficiency has not been well established in the context of route selection subject to multiple additive constraints, which is in general NP-Complete. In this paper, we study how to employ bidirectional search to support efficient QoS routing subject to multiple additive constraints. The major contributions in this paper are as follows. First, we propose a $k$ shortest path algorithm using bidirectional search, whose complexity is deduced to be $O(\sqrt{k}\vert V \vert\lg (\vert V \vert) + k\vert E\vert)$ , where $\vert V \vert$ and $\vert E \vert$ represent the number of nodes and links in the network, respectively. Second, we show that bidirectional search can significantly accelerate the convergence of several existing QoS routing algorithms. Third, we propose a novel cost-effective bidirectional multi-constrained routing algorithm, which can greatly alleviate the forwarding state scalability issue by supporting stateless QoS routing in IP networks via IP tunneling or constraints-based alternate routing in MPLS networks via label stacks. It has the fastest known on-line running time $O(\vert V\vert)$ . Theoretical and simulation results are given to demonstrate the high performance of our proposed algorithm in identifying QoS-satisfied paths and also in efficient resource utilization as compared with existing algorithms.

For advanced features of next generation vehicles, the real-time programs in automotive embedded systems are dramatically increasing. For such large volume program codes, this paper proposes a novel framework to use high-density and low-cost nonvolatile memory, i.e., NAND flash memory, as a low-cost means of storing and executing hard real-time programs. Regarding this, one challenge is that NAND flash memory allows only 2 KB page-based read operations not per-byte random accesses, which requires RAM as working storage for code executions. This paper proposes two solutions, i.e., partitioned RAM solution and shared RAM solution, that minimize the RAM size required to deterministically guarantee the deadlines of all the hard real-time tasks. The proposed solutions are verified with the actual real-time programs for unmanned autonomous driving. To the best of our knowledge, this is the first work that allows us to use NAND flash memory for hard real-time program executions with the minimal usage of RAM.

File replication is widely used in structured P2P systems to avoid hot spots in servers and enhance file availability. The number of replicas and replication distance affect the file replication cost. These two elements and the replica update frequency determined in the file replication stage also affect the cost of subsequent consistency maintenance. However, most existing file replication protocols focus on improving file lookup efficiency without considering its cost and its subsequent influence on consistency maintenance. This paper studies the problem about how a server chooses files to replicate and where to replicate files to achieve low cost in both file replication and consistency maintenance stages without compromising the effectiveness of file replication. This paper presents a lightweight and Cooperative multifactOr considered file Replication Protocol (CORP) to achieve this goal. CORP simultaneously takes into account multiple factors including file popularity, update rate, node available capacity, file load, and node locality, aiming to minimize the number of replicas, update frequency, and replication distance. CORP also dynamically adjusts the number of replicas based on ever-changing file popularity and visit pattern. Extensive experimental results from simulation and PlanetLab real-world testbed demonstrate the efficiency and effectiveness of CORP in comparison with other file replication protocols. It dramatically reduces the overhead of both file replication and consistency maintenance. In addition, it exhibits high adaptiveness to skewed lookups and yields significant improvement in reducing overloaded nodes. Specifically, compared to the other replication protocols, CORP can reduce more than 71 percent of file replicas, 84 percent of overloaded nodes, 94 percent of consistency maintenance cost, and 72 percent of file replication and consistency maintenance latency.

Since the preliminary works of Kocher et al. in the nineties, studying and enforcing the resistance of cryptographic implementations against side channel analysis (SCA) is became a dynamic and prolific area of embedded security. Stochastic attacks, introduced by Schindler et al., form one of the main families of SCA and they offer a valuable alternative to template attacks which are known to be among the most efficient ones. However, stochastic attacks, as long as template attacks, have been initially designed for adversaries with a perfect copy of the target device in hand. Such a prerequisite makes them a pertinent tool when studying the implementations resistance against the most powerful adversaries, but it limits their pertinence as a cryptanalytic technique. Indeed, getting open access to a copy of the device under attack is difficult in practice and, even when possible, it remains difficult to exploit templates acquired on one device to attack another one. In light of this observation, several papers have been published to adapt stochastic attacks for contexts where the above prerequisite is no longer needed. They succeeded in defining practical attacks against unprotected implementations but no work was published until now to explain how stochastic attacks can be applied against secure implementations. In this paper, we deal with this issue. We first extend the previous analyses of stochastic attacks to highlight their core foundations. Then, we explain how they can be generalized to defeat first-order masking techniques, which are the main SCA countermeasures. Eventually, we illustrate the interest of the new attack by a series of experiments on simulated and real curves.

In this paper, we explore a new form of dissemination that arises in distributed, mission-critical applications called Flash Dissemination. This involves the rapid dissemination of rich information to a large number of recipients in a very short period of time. A key characteristic of Flash Dissemination is its unpredictability (e.g., natural hazards), but when invoked it must harness all possible resources to ensure timely delivery of information. Additionally, it must scale to a large number of recipients and perform efficiently in highly heterogeneous (data, network) and failure prone environments. We investigate a peer-based approach based on the simple principle of transferring dissemination load to information receivers using foundations from broadcast networks, gossip theory, and random networks. Gossip-based protocols are well known for being stateless, scalable, and fault-tolerant; however, their performance degrades as content size increases, because of the propagation of redundant gossip messages. In this paper, we propose Concurrent Random Expanding Walkers (CREW), a smart gossip protocol designed to maximize the speed of dissemination by transmitting data only as needed, and by exploiting both intra- and internode concurrency. CREW is designed to support both content and network heterogeneity and deal with transmission failures without sacrificing dissemination speed. We implemented CREW on top of a scalable middleware environment that allows for deployment across several platforms and developed optimizations without compromising on the stateless nature of CREW. We evaluated CREW empirically and compared it to optimized implementations of popular gossip and peer-based systems. Our experiments show that CREW significantly outperforms both traditional gossip and current large content dissemination systems while sustaining its performance in the presence of network errors.

This paper pursues RFID support for localization, aiming to pinpoint an object in 3D space. Given a set of RFID tags and/or readers deployed as reference points at known locations in a hexahedron (like shipping container or storage room), a passive and an active localization schemes are considered in this paper. Being the very first range-free 3D localization, our schemes depend solely on RFID tags and readers without other devices or sensors, and it avoids the need of distance estimation according to received wireless signal strength or phase difference. Our passive scheme locates an RFID tag attached to the target object, with both tags and readers as reference points. The active scheme locates an RFID reader, by iteratively determining a 3D sphere best covering the activated reference tags, referred to as the decision boundary optimization scheme (DeB). Results by simulations and testbed experiments using Alien RFID kits have been obtained, and they reveal that DeB outperforms its passive counterpart and achieves the localization error of 0.07 ft. Additionally, DeB yields better location accuracy and yet is much faster than a previous counterpart. With enhanced DeB (EDeB), accuracy of an object located near a hexahedron side or corner is improved considerably.

Solid state disks (SSDs) have many advantages over hard disk drives, including better reliability, performance, durability, and power efficiency. However, the characteristics of SSDs are completely different from those of hard disk drives with rotating disks. To achieve the full potential performance improvement with SSDs, operating systems or applications must understand the critical performance parameters of SSDs to fine-tune their accesses. However, the internal hardware and software organizations vary significantly among SSDs and, thus, each SSD exhibits different parameters which influence the overall performance. In this paper, we propose a methodology which can extract several essential parameters affecting the performance of SSDs, and apply the extracted parameters to SSD systems for performance improvement. The target parameters of SSDs considered in this paper are 1) the size of read/write unit, 2) the size of erase unit, 3) the size of read buffer, and 4) the size of write buffer. We modify two operating system components to optimize their operations with the SSD parameters. The experimental results show that such parameter-aware management leads to significant performance improvements for large file accesses by performing SSD-specific optimizations.

In large-scale computational Grids, discovery of heterogeneous resources as a working group is crucial to achieving scalable performance. This paper presents a resource management scheme including a hierarchical cycloid overlay architecture, resource clustering and discovery algorithms for wide-area distributed Grid systems. We establish program/data locality by clustering resources based on their physical proximity and functional matching with user applications. We further develop dynamism-resilient resource management algorithm, cluster-token forwarding algorithm, and deadline-driven resource management algorithms. The advantage of the proposed scheme lies in low overhead, fast and dynamism-resilient multiresource discovery. The paper presents the scheme, new performance metrics, and experimental simulation results. This scheme compares favorably with other resource discovery methods in static and dynamic Grid applications. In particular, it supports efficient resource clustering, reduces communications cost, and enhances resource discovery success rate in promoting large-scale distributed supercomputing applications.

Most prior research on policies has focused on correctness. While correctness is an important issue, the adoption of policy-based computing may be limited if the resulting systems are not implemented efficiently and thus perform poorly. To increase the effectiveness and adoption of policy-based computing, in this paper, we propose fast policy evaluation algorithms that can be adapted to support various policy languages. In this paper, we focus on XACML policy evaluation because XACML has become the de facto standard for specifying access control policies, has been widely used on web servers, and is most complex among existing policy languages. We implemented our algorithms in a policy evaluation system called XEngine and conducted side-by-side comparison with Sun Policy Decision Point (PDP), the industrial standard for XACML policy evaluation. The results show that XEngine is orders of magnitude faster than Sun PDP. The performance difference grows almost linearly with the number of rules in an XACML policy. To our best knowledge, there is no prior work on improving XACML policy evaluation performance. This paper represents the first step in exploring this unknown space.

Transaction-level modeling (TLM) is the most promising technique to deal with the increasing complexity of modern embedded systems. However, modeling a complex system completely at transaction level could be inconvenient when IP cores are available on the market, since they are usually modeled at register transfer level (RTL). In this context, modeling and verification methodologies based on transactors allow designers to reuse RTL IPs into TLM-RTL mixed designs, thus guaranteeing a considerable saving of time. Practical advantages of such an approach are evident, but mixed TLM-RTL designs cannot completely provide the well-known effectiveness in terms of simulation speed provided by TLM. This paper presents a methodology to automatically abstract RTL IPs into equivalent TLM descriptions. To do that, the paper first proposes a formal definition of equivalence based on events, showing how such a definition can be applied to prove the correctness of a code manipulation methodology, such as code abstraction. Then, the paper proposes a technique to automatically abstract RTL IPs into TLM descriptions. Finally, the paper shows that the TLM descriptions obtained by applying the proposed technique are correct by construction, relying on the given definition of event-based equivalence. A set of experimental results is reported to confirm the effectiveness of the methodology.

Peer-to-peer (P2P) systems generate a major fraction of the current Internet traffic, and they significantly increase the load on ISP networks and the cost of running and connecting customer networks (e.g., universities and companies) to the Internet. To mitigate these negative impacts, many previous works in the literature have proposed caching of P2P traffic, but very few (if any) have considered designing a caching system to actually do it. This paper demonstrates that caching P2P traffic is more complex than caching other Internet traffic, and it needs several new algorithms and storage systems. Then, the paper presents the design and evaluation of a complete, running, proxy cache for P2P traffic, called pCache. pCache transparently intercepts and serves traffic from different P2P systems. A new storage system is proposed and implemented in pCache. This storage system is optimized for storing P2P traffic, and it is shown to outperform other storage systems. In addition, a new algorithm to infer the information required to store and serve P2P traffic by the cache is proposed. Furthermore, extensive experiments to evaluate all aspects of pCache using actual implementation and real P2P traffic are presented.

As new vulnerabilities on Windows systems are reported endlessly, it is more practical to stop polymorphic malicious code from exploiting these vulnerabilities by building an behavior-based monitor, rather than adopting a signature-based detection system or fixing these vulnerabilities. Many behavior-based monitors have been proposed for Windows systems to serve this purpose. Some of them hook high-level system APIs to detect the suspicious behaviors of code. However, they cannot detect malicious code that directly invokes Native APIs. In this paper, we present a novel security scheme that hooks Native APIs in the kernel mode. This method effectively prevents malicious code calling Native APIs directly. It introduces an average eight percent computation overhead into the system. Analyses and a series of experiments are given in the paper to support our claims.

The JPEG 2000 image compression standard is designed for a broad range of data compression applications. The discrete wavelet transformation (DWT), central to the signal analysis and important in the JPEG 2000, is quite susceptible to computer-induced errors. The errors can be spread to many output transform coefficients if the DWT is implemented by using lifting scheme. This paper proposes an efficient error tolerance scheme (ETS) to detect errors occurring in DWT. A pipeline-based DWT structure is also developed in this paper to speed up the error detection process. The proposed ETS design uses weighting sums of the DWT coefficients at the output compared with an equivalent check value derived from the input-data. With the proposed ETS design, the errors introduced at DWT can be effectively detected. Additionally, the results of error detection can be further analyzed and evaluated to show the capability of error tolerance. Some standard images are used as test samples to verify the feasibility of the proposed ETS design. Experimental results and comparisons show that the proposed ETS has good performance in error detection time and error tolerance capability.

Big data frameworks such as Apache Spark are becoming prominent to perform large-scale data analytics jobs. However, local or on-premise computing resources are often not sufficient to run these jobs. Therefore, public cloud resources can be hired on a pay-per-use basis from the cloud service providers to deploy a Spark cluster entirely on the cloud. Nevertheless, using only cloud resources can be costly. Hence, now-a-days, both local and cloud resources are used together to deploy a hybrid cloud computing cluster. However, scheduling jobs in a cluster deployed on hybrid cloud is challenging in the presence of various Service-Level Agreement (SLA) demands such as cost minimization and job deadline guarantee. Most of the existing works either consider a public or a locally deployed cluster and mainly focus on improving job performance in the cluster. In this paper, we propose efficient scheduling algorithms that leverage different cost models in a hybrid cloud deployed cluster to optimize the Virtual Machine (VM) usage cost for both local and cloud resources and maximize the job deadline meet percentage. The results show that our proposed algorithms are highly scalable and reduce the cost of VM usage of a hybrid cluster for up to 20%.

The emergence of cyber-physical systems (CPS) and internet of things (IoT) devices impose significant security and privacy concerns that necessitate robust monitoring and malware detection systems. This paper proposes PITEM, a framework for instruction-level monitoring and malware detection using electromagnetic (EM) side-channels. PITEM identifies instruction types with similar EM emanations using hierarchical clustering. To track all combinations of these instruction types, we generate EM signatures for all permutations of them. In testing, we predict the permutation class of testing traces by a matched-filter-like predictor. We test the performance on two devices (FPGA-based and ARM-based) with 50 MHz and 1 GHz clock frequencies. We achieve 95.67% and 87.35% accuracies for these devices for single execution of permutations. We note that the accuracy increases to 100% when permutation blocks are repeated. Furthermore, we test the limits of the system by tracking permutations of instructions of the same type. With sufficient bandwidth and number of repetitions, individual instructions can be resolved with 87.5% and 95.78% accuracies for these devices. The performance is evaluated for different relative signal-to-noise ratio (SNR) levels and performance is stable for relative SNR values > 15 dB. Finally, we demonstrate PITEMs ability to detect fine-grained malware with 99.89% accuracy.

Register window is an architectural technique that reduces memory operations required to save and restore registers across procedure calls. Its effectiveness depends on the size of the register file. Such register requirements are normally increased for out-of-order execution because it requires registers for the in-flight instructions, in addition to the architectural ones. However, a large register file has an important cost in terms of area and power and may even affect the cycle time. In this paper, we propose a software/hardware early register release technique that leverage register windows to drastically reduce the register requirements, and hence, reduce the register file cost. Contrary to the common belief that out-of-order processors with register windows would need a large physical register file, this paper shows that the physical register file size may be reduced to the bare minimum by using this novel microarchitecture. Moreover, our proposal has much lower hardware complexity than previous approaches, and requires minimal changes to a conventional register window scheme. Performance studies show that the proposed technique can reduce the number of physical registers to the number of logical registers plus one (minimum number to guarantee forward progress) and still achieve almost the same performance as an unbounded register file.

Embedded and real-time systems are increasingly common and complex, requiring formal specification and verification in order to guarantee their satisfaction of desirable safety and timing requirements. Real-Time Logic (RTL) has been used to capture both the specification (denoted by SP) of a real-time system and the desirable safety assertions (denoted by SA) with respect to this system specification. A verification procedure then determines whether the safety assertions hold with respect to the system specification. However, the satisfiability problem for RTL (i.e., "Can SP \rightarrow SA hold?rdquo), as well as for other first order logics, is undecidable. Consequently, efforts have been focused on identifying nontrivial classes of formulas sufficiently practical for describing industrial real-time systems for which the verification and debugging can be done via efficient heuristics. One such class of formulas is the so-called path RTL. The first contribution of this paper is to extend the existing path RTL class without sacrificing the time complexity of the traditional path RTL heuristic for verification. This implies that we can specify and verify real-time systems, which we were unable to do using the existing path RTL, in the extended path RTL. For real-time systems with large specifications, there is a lot of room for improvement in the algorithms used for verification and debugging. The second contribution of this paper is an efficient method to perform verification and debugging of real-time systems specifications using decomposition techniques. Our idea is to decompose the constraint graph, used in existing approaches, into independent subgraphs so that it is no longer necessary to analyze the entire specification at once, but rather its individual and smaller components. However, none of the above heuristics necessarily finds an ldquooptimal implication.rdquo After verifying SP \rightarrow SA and deploying the system implementing SP, performance changes as a result of power saving, faulty components, and cost saving in the processing platform for the tasks specified in SP affect the computation times of the specified tasks. This leads to a different but related SP, which would violate the original SP \rightarrow SA theorem if SA remains the same. It is desirable, therefore, to determine an optimal SP with the slowest possible computation times for its tasks such that the SA is still guaranteed. This is clearly a fundamental issue in the design and implementation of highly dependable real-time/embedded systems. The third contribution of this paper tackles this fundamental issue by describing a new method for relaxing SP and tightening SA such that SP \rightarrow SA is still a theorem. We have implemented this method in the Java-based DEVO-RTL tool and tested it on several industrial real-time systems. Experimental results show that only about 10 percent of the running time of the heuristic for the verification of SP \rightarrow SA is needed to find an optimal theorem.

In this paper, we present an approach for software rejuvenation based on automated self-healing techniques that can be easily applied to off-the-shelf application servers. Software aging and transient failures are detected through continuous monitoring of system data and performability metrics of the application server. If some anomalous behavior is identified, the system triggers an automatic rejuvenation action. This self-healing scheme is meant to disrupt the running service for a minimal amount of time, achieving zero downtime in most cases. In our scheme, we exploit the usage of virtualization to optimize the self-recovery actions. The techniques described in this paper have been tested with a set of open-source Linux tools and the XEN virtualization middleware. We conducted an experimental study with two application benchmarks (Tomcat/Axis and TPC-W). Our results demonstrate that virtualization can be extremely helpful for failover and software rejuvenation in the occurrence of transient failures and software aging.

Latency-insensitive (LI) systems are those which can function correctly in spite of delays along its connecting wires. This delay is assumed to be a multiple of the clock period. The paper presents a single-clock process algebraic model for such systems. It gives the definitions for LI computational blocks and LI connectors. Important properties for these are shown to be satisfied. Composition of such modules can be done by the parallel composition operator of the process algebra. Conditions are given to check for liveness and deadlock freedom of LI systems. Comparison of latency equivalence between streams of events can be done using the model and this leads to a method of proving latency-equivalent modules. The paper is a step toward high-level specification and verification of such systems. The work can be extended to address more complex interconnections by modeling the underlying finite-state machines.

In this paper, we introduce a timed extension of the extended finite state machines model. On one hand, we consider that (output) actions take time to be performed. This time may depend on several factors, such as the value of variables. On the other hand, our formalism allows us to specify time-outs. In addition to presenting our language, we develop a testing theory. First, we define 10 timed conformance relations and relate them. Second, we introduce a notion of timed test and define how to apply tests to implementations. Finally, we give an algorithm to derive sound and complete test suites with respect to the implementation relations presented in the paper. This paper represents an extended and improved version of [1].

Although many block replacement algorithms for buffer caches have been proposed to address the well-known drawbacks of the LRU algorithm, they are not robust and cannot maintain a consistent performance improvement over all workloads. This paper proposes a novel and simple replacement scheme, called the Robust Adaptive buffer Cache management schemE (RACE), which differentiates the locality of I/O streams by actively detecting access patterns that are inherently exhibited in two correlated spaces, that is, the discrete block space of program contexts from which I/O requests are issued and the continuous block space within files to which I/O requests are addressed. This scheme combines the global I/O regularities of an application and the local I/O regularities of individual files that are accessed in that application to accurately estimate the locality strength, which is crucial in deciding which blocks are to be replaced upon a cache miss. Through comprehensive simulations on 10 real-application traces, RACE is shown to have higher hit ratios than LRU and all other state-of-the-art cache management schemes studied in this paper.

Grid computing is a newly emerging technology aimed at large-scale resource sharing and global-area collaboration. It is the next step in the evolution of parallel and distributed computing. Due to the largeness and complexity of the grid system, its performance and reliability are difficult to model, analyze, and evaluate. This paper presents a model that relaxes some assumptions made in prior research on distributed systems that were inappropriate for grid computing. The paper proposes a virtual tree-structured model of the grid service. This model simplifies the physical structure of a grid service, allows service performance (execution time) to be efficiently evaluated, and takes into account data dependence and failure correlation. Based on the model, an algorithm for evaluating the grid service time distribution and the service reliability indices is suggested. The algorithm is based on Graph theory and probability theory. Illustrative examples and a real case study of the BioGrid are presented.

Many information processing and computing problems can be traced back to find the extreme value of a database or a function. Unfortunately, classical solutions suffer from high computational complexity if the database is unsorted or, equivalently, the function has many local minimum/maximum points. Proposed quantum computing-based solutions involve the repeated application of Grower's searching algorithm. In this paper, we introduce a new technique exploiting the parallel processing capabilities of quantum computing in a different way. We derive a special case of quantum counting - we call it quantum existence testing - which allows adapting the classical logarithmic search algorithm so that it is suitable for structured databases to unstructured ones. The paper analyzes the required number of database queries, the corresponding computational complexity, and the probability of error and their relationship

Grid computing is a recently developed technology. Although the developmental tools and techniques for the grid have been extensively studied, grid reliability analysis is not easy because of its complexity. This paper is the first one that presents a hierarchical model for the grid service reliability analysis and evaluation. The hierarchical modeling is mapped to the physical and logical architecture of the grid service system and makes the evaluation and calculation tractable by identifying the independence among layers. Various types of failures are interleaved in the grid computing environment, such as blocking failures, time-out failures, matchmaking failures, network failures, program failures, and resource failures. This paper investigates all of them to achieve a complete picture about grid service reliability. Markov models, queuing theory, and graph theory are mainly used to model, evaluate, and analyze the grid service reliability. Numerical examples are illustrated

The energy and cooling costs of Web server farms are among their main financial expenditures. This paper explores the benefits of dynamic voltage scaling (DVS) for power management in server farms. Unlike previous work, which addressed DVS on individual servers and on load-balanced server replicas, this paper addresses DVS in multistage service pipelines. Contemporary Web server installations typically adopt a three-tier architecture in which the first tier presents a Web interface, the second executes scripts that implement business logic, and the third serves database accesses. From a user's perspective, only the end-to-end response across the entire pipeline is relevant. This paper presents a rigorous optimization methodology and an algorithm for minimizing the total energy expenditure of the multistage pipeline subject to soft end-to-end response-time constraints. A distributed power management service is designed and evaluated on a real three-tier server prototype for coordinating DVS settings in a way that minimizes global energy consumption while meeting end-to-end delay constraints. The service is shown to consume as much as 30 percent less energy compared to the default (Linux) energy saving policy

In this paper, we present an efficient flash file system for flash memory storage. Flash memory, especially NAND flash memory, has become a major method for data storage. Currently, a block level translation interface is required between an existing file system and flash memory chips due to its physical characteristics. However, the approach of existing file systems on top of the emulating block interface has many restrictions and is, thus, inefficient because existing file systems are designed for disk-based storage systems. The flash file system proposed in this paper is designed for NAND flash memory storage while considering the existing file system characteristics. Our target performance metrics are the system booting time and garbage collection overheads, which are important issues in flash memory. In our experiments, the proposed flash file system outperformed other flash file systems both in booting time and garbage collection overheads.

Accurately predicting object lifetimes is important for improving memory management systems. Current garbage collectors make relatively coarse-grained predictions (e.g., "short-lived" versus "long-lived") and rely on application-independent heuristics related to the local characteristics of an allocation. This paper introduces a prediction method which is fully precise and makes its predictions based on application-specific training rather than application-independent heuristics. By "fully precise" we mean that the granularity of predictions is equal to the smallest unit of allocation. The method described is the first to combine high precision and efficiency in a single lifetime predictor. Fully precise prediction enables us, for the first time, to study zero-lifetime objects. The paper reports results showing that zero-lifetime objects comprise a significant fraction of object allocations in benchmark programs for the Java programming language and that they are correlated with their allocation context (the call stack and allocation site). Beyond zero-lifetime objects, the paper reports results on predicting longer lived objects, where, in some cases, it is possible to predict the lifetime of objects based on their allocation context (the call stack and allocation site) well. For the SPEC benchmark programs, the number of dynamically allocated objects whose call sites have accurate predictors ranges from 0.2 percent to 61 percent. This method could potentially improve the performance of garbage collectors. The paper proposes a death-ordered collector (DOC) and analyzes its implementation overheads and its best possible performance. The study shows how memory performance could be enhanced using the extra information provided by fully precise prediction.

Conceptual and algorithmic tools are developed as a foundation for a theory of scheduling complex computation-dags for Internet-based computing. The goal of the schedules produced is to render tasks eligible for allocation to remote clients (hence, for execution) at the maximum possible rate. This allows one to utilize remote clients well, as well as to lessen the likelihood of the "gridlock" that ensues when a computation stalls for lack of eligible tasks. Earlier work has introduced a formalism for studying this optimization problem and has identified optimal schedules for several significant families of structurally uniform dags. The current paper extends this work via a methodology for devising optimal schedules for a much broader class of complex dags, which are obtained via composition from a prespecified collection of simple building-block dags. The paper provides a suite of algorithms that decompose a given dag Gscr to expose its building blocks and an execution-priority relation xutri on building blocks. When the building blocks are appropriately interrelated under xutri the algorithms specify an optimal schedule for Gscr

The effects of the general-purpose precise interrupt mechanisms in use for the past few decades have received very little attention. When modern out-of-order processors handle interrupts precisely, they typically begin by flushing the pipeline to make the CPU available to execute handler instructions. In doing so, the CPU ends up flushing many instructions that have been brought in to the reorder buffer. In particular, these instructions may have reached a very deep stage in the pipeline - representing significant work that is wasted. In addition, an overhead of several cycles and wastage of energy (per exception detected) can be expected in refetching and reexecuting the instructions flushed. This paper concentrates on improving the performance of precisely handling software managed translation look-aside buffer (TLB) interrupts, one of the most frequently occurring interrupts. The paper presents a novel method of in-lining the interrupt handler within the reorder buffer. Since the first level interrupt-handlers of TLBs are usually small, they could potentially fit in the reorder buffer along with the user-level code already there. In doing so, the instructions that would otherwise be flushed from the pipe need not be refetched and reexecuted. Additionally, it allows for instructions independent of the exceptional instruction to continue to execute in parallel with the handler code. By in-lining the TLB interrupt handler, this provides lock-up free TLBs. This paper proposes the prepend and append schemes of in-lining the interrupt handler into the available reorder buffer space. The two schemes are implemented on a performance model of the Alpha 21264 processor built by Alpha designers at the Palo Alto Design Center (PADC), California. We compare the overhead and performance impact of handling TLB interrupts by the traditional scheme, the append in-lined scheme, and the prepend in-lined scheme. For small, medium, and large memory footprints, the overhead is quantified by comparing the number and pipeline state of instructions flushed, the energy savings, and the performance improvements. We find that lock-up free TLBs reduce the overhead of refetching and reexecuting the instructions flushed by 30-95 percent, reduce the execution time by 5-25 percent, and also reduce the energy wasted by 30-90 percent.

Continuous advances in silicon technology enable the development of complex system-on-chip as cooperation among digital signal processors (DPSs), general purpose processors (GPPs), and specific hardware components. The impact of this choice is not only limited to the target architecture, but also encompasses the overall system specification. It is thus crucial to manage such a complexity using high-level specification languages and a tool chain supporting the designer throughout a set of strategic decisions, such as the identification of a set of possible target architectures, the verification of the correctness of the specification, and the partitioning of the specification onto a set of computational resources. This paper addresses this type of problem by proposing a design flow supporting the system-level design of heterogeneous multiprocessor system-on-chip (MP-SoC), by extracting information from the system description (e.g., SystemC) - statically and in a fast manner - and by providing a set of quantitative measures correlating the type of executor, the functionality, and a timing estimation. Partitioning and architecture selection are built on top of this data and the final analysis of the selected hardware-software solution over the identified candidates is finally submitted to a timing verification via simulation. Note that the possibility of actually performing a comprehensive design space exploration, in general, is tightly influenced by the interaction between partitioning/architecture-selection and timing simulation in the design flow; for this reason, the description of this aspect is particularly emphasized in the presentation of the methodology. To show the applicability of the proposed methodology, two relevant case studies are described in the paper.

With more embedded systems networked, it becomes an important problem to effectively defend embedded systems against buffer overflow attacks. Due to the increasing complexity and strict requirements, off-the-shelf software components are widely used in embedded systems, especially for military and other critical applications. Therefore, in addition to effective protection, we also need to provide an approach for system integrators to efficiently check whether software components have been protected. In this paper, we propose the HSDefender (Hardware/Software Defender) technique to perform protection and checking together. Our basic idea is to design secure call instructions so systems can be secured and checking can be easily performed. In the paper, we classify buffer overflow attacks into two categories and provide two corresponding defending strategies. We analyze the HSDefender technique with respect to hardware cost, security, and performance. We experiment with our HSDefender technique on the simplescalar/ARM simulator with benchmarks from MiBench, an embedded benchmark suite. The results show that our HSDefender technique can defend a system against more types of buffer overflow attacks with less overhead compared with the previous work.

Web prefetching is based on Web caching and attempts to reduce user-perceived latency. Unlike on-demand caching, Web prefetching fetches objects and stores them in advance, hoping that the prefetched objects are likely to be accessed in the near future and such accesses would be satisfied from the caches rather than by retrieving the objects from the Web server. This paper reviews the popular prefetching algorithms based on popularity, good fetch, API characteristic, and lifetime, and then makes the following contributions: 1) The paper proposes a family of linear-time prefetching algorithms, objective-greedy prefetching, wherein each algorithm greedily prefetches those Web objects that most significantly improve the performance as per the targeted metric. 2) The hit rate-greedy and bandwidth-greedy algorithms are shown to be optimal for their respective objective metrics. A linear-time optimal prefetching algorithm that maximizes the H/B metric as the performance measure is proposed. 3) The paper shows the results of a performance analysis via simulations, comparing the proposed algorithms with the existing algorithms in terms of the respective objectives - the hit rate, bandwidth, and the H/B metrics. The proposed prefetching algorithms are seen to provide better objective-based performance than any existing algorithms. Further, H/B-greedy performs almost as well as H/B-optimal.

Artificial Neural networks (ANNs) are widely used to solve classification problems for many machine learning applications. When errors occur in the computational units of an ANN implementation due to for example radiation effects, the result of an arithmetic operation can be changed, and therefore, the predicted classification class may be erroneously affected. This is not acceptable when ANNs are used in many safety-critical applications, because the incorrect classification may result in a system failure. Existing error-tolerant techniques usually rely on physically replicating parts of the ANN implementation or incurring in a significant computation overhead. Therefore, efficient protection schemes are needed for ANNs that are run on a processor and used in resource-limited platforms. A technique referred to as Selective Neuron Re-Computation (SNRC), is proposed in this paper. As per the ANN structure and algorithmic properties, SNRC can identify the cases in which the errors have no impact on the outcome; therefore, errors only need to be handled by re-computation when the classification result is detected as unreliable. Compared with existing temporal redundancy-based protection schemes, SNRC saves more than 60 percent of the re-computation (more than 90 percent in many cases) overhead to achieve complete error protection as assessed over a wide range of datasets. Different activation functions are also evaluated. This research was supported by the National Science Foundation Grants CCF-1953961 and 1812467, by the ACHILLES project PID2019-104207RB-I00 and the Go2Edge network RED2018-102585-T funded by the Spanish Ministry of Science and Innovation and by the Madrid Community research project TAPIR-CM P2018/TCS-4496. Publicado

Serverless computing is becoming a promising paradigm for Distributed Deep Neural Network (DDNN) training in the cloud, as it allows users to decompose complex model training into a number of $functions$ without managing virtual machines or servers. Though provided with a simpler resource interface ( $i.e.,$ function number and memory size), inadequate function resource provisioning (either under-provisioning or over-provisioning) easily leads to $unpredictable$ DDNN training performance in serverless platforms. Our empirical studies on AWS Lambda indicate that, such $unpredictable performance$ of serverless DDNN training is mainly caused by the resource bottleneck of Parameter Servers (PS) and small local batch size. In this paper, we design and implement $\lambda DNN$ , a cost-efficient function resource provisioning framework to provide predictable performance for serverless DDNN training workloads, while saving the budget of provisioned functions. Leveraging the PS network bandwidth and function CPU utilization, we build a $lightweight$ analytical DDNN training performance model to enable our design of $\lambda DNN$ resource provisioning strategy, so as to guarantee DDNN training performance with serverless functions. Extensive prototype experiments on AWS Lambda and complementary trace-driven simulations demonstrate that, $\lambda DNN$ can deliver predictable DDNN training performance and save the monetary cost of function resources by up to 66.7%, compared with the state-of-the-art resource provisioning strategies, yet with an acceptable runtime overhead.