This paper studies MPC based decision graph inference (MDGI) where decision graphs (generalization of decision trees) are very popular machine learning models. In MDGI, a modeler holding a private model and a data owner holding private feature vectors jointly run model inference on each vector through an MPC protocol, which outputs the inference result without revealing the model or vector. Several noteworthy MDGI solutions have been proposed, but they remain unsatisfactory for large models due to the high communication cost of oblivious decision, the most complex component in MDGI. Oblivious decision securely evaluates binary tests (Boolean-valued functions) over features without revealing test type, parameter, feature index, or value. All constant-round oblivious decision protocols suffer from high communication costs due to bitwise encryption and transmission. Moreover, most support only one of the three common test types: threshold comparison, equality test, and set containment. We propose Homomorphic Lookup Table (HLT), a novel MPC technique for oblivious decision. HLT circumvents the bitwiseencryption and heavy-communication issue by adopting tablelookup-style computation and amortizing the cost of encrypted table transfer across many inferences. We carefully design the table structure and lookup rules, and integrate homomorphic encryption to optimize performance and support multiple test types. HLT achieves 78 × −4151× reduction in communication for oblivious decision, and is the first method to support all three common test types. Based on HLT, we design constant-round MDGI solutions for two widely used decision graphs: decision trees and scorecards. This is the first privacy-preserving solution for scorecards, and our decision tree solution reduces communication by 27 × −321×.

Path validation promises a necessary security add-on for future Internet architectures. It authenticates not only source identities but also the exact path where a packet forwards through. This offers users more flexibility and reliability in network services. Most existing solutions focus on single-path validation that pre-correlates a packet to a specific forwarding path. However, parallel transmissions in multipath routing tend to induce bursty traffic that is hardly validated in time by existing solutions. In this paper, we present SwiftParade as the first attempt toward anti-burst multipath validation. It proposes a composite validation technique that can simultaneously validate a group of packets likely from multiple different paths. This helps to amortize the validation overhead across packets of the entire group instead of imposing the validation overhead equally on every packet. To implement composite validation, SwiftParade further explores a noncommutative homomorphic asymmetric encryption scheme. We prove effectiveness and security of SwiftParade through theoretical analysis. We also conduct extensive experiments to evaluate SwiftParade performance. The results show that SwiftParade offers high efficiency and applicability to multipath validation with complex routing topologies. In comparison with the state-of-the-art multipath validation solution—Atlas, SwiftParade speeds up packet processing by 2.5×$\sim 8.3\times$and increases communication throughput by 2.8×$\sim 10.2\times$.

Cache side-channel attacks remain a stubborn source of cross-core secret leakage. Such attacks exploit the timing difference between cache hits and misses. Most defenses thus choose to prevent cache evictions. Given that two possible types of evictions—flush-based and conflict-based—use different architectural features, these defenses have to integrate hybrid defense strategies, incur OS modification, and sacrifice performance to completely throttle cache side-channel attacks. In this paper, we present TreasureCache against cache side-channel attacks without modifying OS or sacrificing performance. Instead of preventing cache evictions with various costs, we advocate to allow cache evictions as is and hide exploitable evictions in our specialized small eviction-hidden buffer. The buffer guarantees a fast hit time comparative to LLC hits. This instantly closes the timing gap between accessing exploitable blocks when they are in and out of the LLC. Moreover, with the help of our buffer, we no longer have to disable flush instructions or shared memory. A lightweight constant-time flush instruction can help TreasureCache to prevent both flush-based and conflict-based side-channel attacks. We validate TreasureCache security and performance through extensive experiments. With a hardware overhead of less than 0.5%, TreasureCache reduces the secret-leakage resolution by about 1,000 times without introducing any performance slowdown.

Oblivious RAM (ORAM) remains a bittersweet protection of memory access patterns because of its prohibitively high overhead. The root cause is that ORAM hides intended accesses among a sufficiently large number of dummy accesses. Most existing optimizations mitigate memory accesses using architectural enhancements (e.g., cache) yet few of them improve the efficiency of ORAM primitives per se. In this paper, we identify path-grained static scheduling as a fundamental ORAM performance bottleneck. We propose level-grained dynamic scheduling that directly optimizes ORAM primitives to boost efficiency. It enables ORAM to service more than one request per path and write paths batch wise. We can thus boost ORAM efficiency through handling queued requests as soon as possible and remove as many redundant accesses as possible. Since optimized memory accesses still target the same set of paths, dynamic scheduling preserves ORAM security. We implement dynamic scheduling through Hitchhiker ORAM. In comparison with the state-of-the-art primitive-optimized Fork Path ORAM, Hitchhiker ORAM yields 31.5% fewer memory accesses, 60.2% shorter latency, and 40.7% less energy consumption, being 2.5× faster. In comparison with the state-of-the-art architecture-optimized$\rho$, Hitchhiker ORAM is 1.5× faster and the integrated version—$\rho$-Hitchhiker ORAM is 2.0× faster.

Path validation has already been incrementally deployed in the Internet architecture. It secures packet forwarding by enabling end hosts to negotiate specific forwarding paths and enforcing on-path routers to prove their forwarding behaviors along these paths. Most existing path validation solutions target static paths, paying less attention to fully dynamic paths that support flexible routing. In this paper, we present Hummingbird as the first validation solution over fully dynamic paths. It features a hidden equal-probability sampling technique. Gaining efficiency via routers probabilistically sampling packets to validate, we craft the sampling probability such that each router validates a similar amount of packets given an unknown path length. We further hide the state of whether a packet has been sampled and validated using a lightweight, non-cryptographic scheme. This prevents attackers from differentiating and selectively mis-forwarding packets. We validate security and efficiency of Hummingbird through both theoretical proof and experimental evaluation.

Reliable Software-Defined Networking (SDN) should mitigate forwarding anomalies due to cross-plane rule inconsistencies. Most existing countermeasures either inject probe packets to infer forwarding correctness or collect packet traces to detect forwarding anomalies. They, however, cannot detect or filter forwarding anomalies for production packets in real time. In this paper, we propose RuleOut as the first attempt to automatically throttle SDN forwarding anomalies. It disambiguates dependent rules via augmenting their matching fields with unique tags. Leveraging source routing, we further bind each packet with the tag sequence corresponding to rules the packet should match. RuleOut thus renders each packet to match at most one rule on each switch. This completely addresses the root cause of forwarding ambiguity. To implement RuleOut, we develop a non-overlapping rule dependency graph, a series of algorithms for incremental rule update and tag generation upon it, and various optimization techniques toward scalability and efficiency. We prototype RuleOut on the Ryu controller and Open vSwitch and evaluate its performance over public rule sets such as Stanford, Internet2, and Airtel1. RuleOut can use tags of only several bits long to disambiguate thousands to millions of rules and generate tags fairly fast within a few milliseconds.

One major goal of the AI security community is to securely and reliably produce and deploy deep learning models for real-world applications. To this end, data poisoning based backdoor attacks on deep neural networks (DNNs) in the production stage (or training stage) and corresponding defenses are extensively explored in recent years. Ironically, backdoor attacks in the deployment stage, which can often happen in unprofessional users' devices and are thus arguably far more threatening in real-world scenarios, draw much less attention of the community. We attribute this imbalance of vigilance to the weak practicality of existing deployment-stage backdoor attack algorithms and the insufficiency of real-world attack demonstrations. To fill the blank, in this work, we study the realistic threat of deployment-stage backdoor attacks on DNNs. We base our study on a commonly used deployment-stage attack paradigm - adversarial weight attack, where adversaries selectively modify model weights to embed backdoor into deployed DNNs. To approach realistic practicality, we propose the first gray-box and physically realizable weights attack algorithm for backdoor injection, namely subnet replacement attack (SRA), which only requires architecture information of the victim model and can support physical triggers in the real world. Extensive experimental simulations and system-level real- world attack demonstrations are conducted. Our results not only suggest the effectiveness and practicality of the proposed attack algorithm, but also reveal the practical risk of a novel type of computer virus that may widely spread and stealthily inject backdoor into DNN models in user devices. By our study, we call for more attention to the vulnerability of DNNs in the deployment stage.

Speculative execution attacks exploiting speculative execution to leak secrets have aroused significant concerns in both industry and academia. They mainly exploit covert or side channels over microarchitectural states left by mis-speculated and squashed instructions (i.e., transient instructions). Most such attacks target cache states. Existing cache-based defenses against speculative execution attacks fall into two categories, Invisible and Undo. Most Invisible defenses buffer execution metadata of speculative instructions and place them into the cache only if the speculatively executed instructions become determined. Motivated by the fact that mis-speculations are rare cases, Undo defenses allow speculative instructions to modify cache states. Upon a mis-speculation, they rollback cache states to the ones prior to the execution of transient instructions. However, Invisible defenses have been recently found insecure by the speculative interference attack. This calls for a deep security inspection of Undo defenses against speculative execution attacks.In this paper, we present unXpec as the first attack against Undo-based safe speculation. It exploits the secret-dependent timing channel exhibited through the rollback operations of Undo defenses. Specifically, the rollback process requires both invalidating cache lines brought into the cache by transient instructions and restoring evicted cache lines from the cache by transiently loaded data. This opens up a channel that encodes secret via the timing difference between when rollback involves much invalidation and restoration or not. We further leverage eviction sets to enforce more restoration operations. This yields a longer rollback time and thus a larger secret-dependent timing difference. We demonstrate the timing channel over the open-source CleanupSpec, a representative Undo solution. A single transient load can trigger a secret-dependent timing difference of 22 cycles (without eviction sets) of 32 cycles (with eviction sets), which is sufficiently exploitable for constructing a covert channel for speculative execution attacks. We run unXpec on the gem5 simulator with CleanupSpec enabled. The results show that unXpec can leak secrets at a high rate of 140 Kbps with an accuracy over 90%. Simply enforcing constant-time rollback to mitigate unXpec may induce an over 70% performance overhead.

Cache coherence states have recently been exploited to leak secrets through timing-channel attacks. The root cause lies in the fact that shared data in state Exclusive (E) and state Shared (S) are served from different cache layers. The state-of-the-art countermeasure—S-MESI—serves both E- and S-state shared data from the last-level cache (LLC) by explicitly synchronizing the Modified (M) state across private caches and the LLC. This has to sacrifice the silent upgrade feature that MESI introduces for speedup. Moreover, it enforces protection to not only exploitable shared data but also unshared data. This further slows down performance, especially for write-after-read intensive applications. In this paper, we propose SwiftDir to efficiently secure cache coherence against cover-channel attacks without overprotection. SwiftDir fundamentally narrows down the protection scope to write-protected data. Such exploitable shared data can be uniquely identified with the write-protection permission in the memory management unit (MMU) and do not necessarily transit to state M. We validate this idea through tracing system calls of shared libraries on Linux. We then investigate all three commercial cache architectures (i.e., PIPT, VIPT, and VIVT) and find it feasible to hitchhike the address translation process to transmit the write-protection information from the MMU to the coherence controller. Then SwiftDir enforces protection over only write-protected data by serving all requests toward them directly from the LLC with a constant latency. This not only simplifies how MESI handles write-protected data but also avoids how S-MESI overprotects them. Meanwhile, SwiftDir still preserves silent upgrade for efficient handling of unshared data. Extensive experiments demonstrate that our SwiftDir can secure cache coherence while outperforming not only secure SMESI but also unprotected MESI.

Following the principle of to set one's own spear against one's own shield, we study how to design adversarial completely automated public turing test to tell computers and humans apart (CAPTCHA) in this article. We first identify the similarity and difference between adversarial CAPTCHA generation and existing hot adversarial example (image) generation research. Then, we propose a framework for text-based and image-based adversarial CAPTCHA generation on top of state-of-the-art adversarial image generation techniques. Finally, we design and implement an adversarial CAPTCHA generation and evaluation system, called aCAPTCHA, which integrates 12 image preprocessing techniques, nine CAPTCHA attacks, four baseline adversarial CAPTCHA generation methods, and eight new adversarial CAPTCHA generation methods. To examine the performance of aCAPTCHA, extensive security and usability evaluations are conducted. The results demonstrate that the generated adversarial CAPTCHAs can significantly improve the security of normal CAPTCHAs while maintaining similar usability. To facilitate the CAPTCHA security research, we also open source the aCAPTCHA system, including the source code, trained models, datasets, and the usability evaluation interfaces.

Path validation has been explored as an indispensable security feature for the future Internet. Motivated by the Path-Aware Networking Research Group (PANRG) under the Internet Engineering Task Force (IETF) and Internet Research Task Force (IRTF), it gives end-hosts more control over packet forwarding and ensures that the forwarding history is verifiable. The main idea is to require that routers add proofs in packet headers for other routers to verify. We identify linear-scale proofs as the essential efficiency barrier of existing path validation solutions. In this paper, we propose Atomos to validate network paths with constant-size proofs. To this end, we construct a noncommutative homomorphic asymmetric-key encryption scheme. Asymmetric cryptography minimizes the number of proofs needed and saves time in processing proofs. The homomorphism we design yields constant-size proofs. It limits the header-space overhead and outperforms existing linear-scale counterparts when the path length exceeds a value that is usually small. Furthermore, the proposed encryption scheme is noncommutative so that any deviation from the forwarding path can be detected. We explore a series of design strategies for security and efficiency. The evaluation results show that Atomos yields not only shorter proofs but also faster validation than existing solutions.

The end-users communicating over a network path currently have no control over the path. For a better quality of service, the source node often opts for a superior (or premium) network path to send packets to the destination node. However, the current Internet architecture provides no assurance that the packets indeed follow the designated path. Network path validation schemes address this issue and enable each node present on a network path to validate whether each packet has followed the specific path so far. In this work, we introduce two notions of privacy— path privacy and index privacy —in the context of network path validation. We show that, in case a network path validation scheme does not satisfy these two properties, the scheme is vulnerable to certain practical attacks (that affect the privacy, reliability, neutrality and quality of service offered by the underlying network). To the best of our knowledge, ours is the first work that addresses privacy issues related to network path validation. We design PrivNPV, a privacy-preserving network path validation protocol, that satisfies both path privacy and index privacy. We discuss several attacks related to network path validation and how PrivNPV defends against these attacks. Finally, we discuss the practicality of PrivNPV based on relevant parameters.

RFID tags have been widely deployed to report valuable information about tagged objects or surrounding environment. To collect such information, the key is to avoid the tag-to-tag collision in the open wireless channel. Polling, as a widely used anti-collision protocol, provides a request-response way to interrogate tags. The basic polling however needs to broadcast the tedious tag ID (96 bits) to query a tag, which is time-consuming. For example, collecting only 1-bit information (e.g., battery status) but with 96-bit overhead is a great limitation. This paper studies how to design efficient polling protocols to collect tag information quickly. The basic idea is to minimize the length of the polling vector as well as to avoid useless communication. We first propose an efficient Hash polling protocol (HPP) that uses hash indices rather than tag IDs as the polling vector to query each tag. The length of the polling vector is dropped from 96 bits to no more than 16 bits (the number of tags is less than 100,000). We then propose a tree-based polling protocol (TPP) that avoids redundant transmission in HPP. By constructing a binary polling tree, TPP transmits only different postfix of the neighbor polling vectors; the same prefix is reserved without any retransmission. The result is that the length of the polling vector reduces to only 3.4 bits. Finally, we propose an incremental polling protocol (IPP) that updates the polling vector based on the difference in value between the current polling vector and the previous one. By sorting the indices and dynamically updating them, IPP drops the polling vector to 1.6 bits long, 60 times less than 96-bit IDs. Extensive simulation results show that our best protocol IPP outperforms the state-of-the-art information collection protocol.

Access patterns over untrusted memory have long been exploited to infer sensitive information like program types or even secret keys. Most existing obfuscation solutions hide real memory accesses among a sufficiently large number of dummy memory accesses. Such solutions lead to a heavy communication overhead and more often apply to the client/server scenario instead of the CPU/memory architecture. Sporadic obfuscation solutions strive for an affordable memory bandwidth cost at the expense of security degradation. For example, they may have to obfuscate accesses over a limited range of memory space to control the overhead.

Software-Defined Networking (SDN) greatly simplifies middlebox policy enforcement. Middleboxes need tag packet headers to avoid forwarding ambiguity on SDN switches. In this paper, we present a new attack, called middlebox-bypass attack, to breach SDN-based middlebox policy enforcement. Such an attack manipulates a compromised switch to locally tag attacking packets without handing them over to the attached middlebox for inspection. Existing SDN security solutions, however, cannot detect the middlebox-bypass attack under practical constraints of efficiency, robustness, and applicability. We design and implement FlowCloak, the first protocol for per-packet real-time detection and prevention of middlebox-bypass attacks. FlowCloak enables middleboxes to generate tags that are probabilistically unknown to an attacker and confines it to only random guessing. We propose a multi-tag verification technique to address the tradeoff between FlowCloak robustness and TCAM usage by tag verification rules on the egress switch. Experiment results show that dozens of verification rules can confine the attacking probability under 0.1 %. FlowCloak imposes only a 0.3 ms packet processing delay on middleboxes and no obvious delay on the egress switch.

SDN-based cloud has the merit of allowing more flexibility in network management, however, the security of network accessing and the correctness of network configuration in SDN-based cloud have not been effectively addressed yet. In this paper, SDNKeeper, a generic and fine-grained policy enforcement system in SDN-based cloud is proposed, which can defend against unauthorized attacks and avoid network resource misconfiguration. With the usage of SDNKeeper, numerous flexible network management policies can be created by administrators, which give administrators the discretionary room on controlling the network resources. To be specific, SDNKeeper can reject any unauthorized network access request at Northbound Interface (NBI), which located between application plane and control plane. Moreover, compared with other traditional policy-based access control systems, SDNKeeper is totally application-transparent and lightweight, which is easy to implement, deploy and runtime configure. Based on the prototype implementation and evaluation, we conclude that SDNKeeper can perform access control accurately with negligible computation overhead whilst the throughput degradation is still within the acceptable range.

Path authentication thwarts counterfeits in RFID-based supply chains. Its motivation is that tagged products taking invalid paths are likely faked and injected by adversaries at certain supply chain partners/steps. Existing solutions are path-grained in that they simply regard a product as genuine if it takes any valid path. Furthermore, they enforce distributed authentication by offloading the sets of valid paths to some or all steps from a centralized issuer. This not only imposes network and storage overhead but also leaks transaction privacy. We present StepAuth, the first step-grained path authentication protocol that is practically efficient for authenticating products with strict path bindings. We encode a path into a secret with minimum path visibility disclosure between adjacent steps. Carrying the secret, a product has to go through steps in the exact order as in the designated path to pass authentication. StepAuth enforces no tag computation and enables each step to locally verify path secrets without pre-offloaded valid-path sets. Toward an even higher security guarantee, StepAuth can hinder an adversary capable of compromising all steps from forging valid secrets. We make StepAuth practically efficient by taking advantage of nested encryption and hybrid encryption. To achieve a 128-b security for a practically long path of 100 steps, StepAuth generates a secret around 10 KB, which can be well supported by high-memory EPC Gen2 tags. Such secrets take StepAuth less than 1 s to encode and around 10 ms to verify.

"Cloud" is a common metaphor for an Internet accessible infrastructure (e.g., data storage and computing hardware) that is hidden from users. Cloud computing makes data truly mobile and a user can simply access a chosen cloud with any internet accessible device. In cloud computing, IT-related capabilities are provided as services, accessible without requiring detailed knowledge of the underlying technology. Thus, many mature technologies are used as components in cloud computing, but still there are many unresolved and open problems. This special issue includes articles addressing the state-of-the-art in strengthening performance and security and cloud computing. Eight representative research articles were carefully selected based on the original presentations at the 2016 International Conference on Cloud Computing and Big Data (CloudCom-Asia'16). The objective of this conference is to bring together researchers who work on cloud computing and related technologies. According to whether its research theme relates more to performance or security, the accepted papers are briefly described in the remaining part of this section. Task scheduling is critical for guaranteeing cloud performance. In the past years, more and more business-to-consumer and enterprise applications start running in the heterogeneous cloud. Such cloud bag-of-tasks (BoT) applications are usually budget-constrained and their scheduling is an essential problem for cloud provider. The problem is even more complex and challenging when the accurate knowledge about task execution time is unknown in advance. Focusing on these challenges, Tang et al1 build a cloud resource management architecture and stochastic task model, which divides cloud task into two execution parts. Then they deduce BoT applications schedule length and total cost according to heterogenous clouds online feedback information. They further formulate this stochastic scheduling problem as a linear programming problem and propose a time and cost multi-objective stochastic task scheduling genetic algorithm, which can find Pareto-optimal schedules for stochastic cloud task that meet its budget constraint. With the rapid development of Internet and cloud computing, the high performance requirements for data center networks (DCNs) are increasing for meeting the need of users. A large number of data need to be processed and shared among servers in a data center. Recently, multicast traffic in DCNs has attracted much attention from academia due to the fact that multicast traffics have the dominating advantages for group communications in DCNs. Therefore, the appropriate multicast traffic scheduling in data center networks cannot only improve network efficiency but also save network resources. Li et al2 propose a multicast scheduling algorithm to appropriately schedule flows to achieve traffic load balance so that network blocking can be avoided. In order to reduce the network blocking, they propose an efficient blocking cost-driven multicast scheduling algorithm in fat-tree DCNs. The paper establishes the blocking model of multicast network based on multicast network state and presents the blocking probability at the next time-slot, which can reduce the scheduling delay of multicast traffic. Furthermore, the paper presents also an optimal selection mechanism of feasible links based on the given link blocking probability at the next time-slot. In order to study cloud performance from a more comprehensive perspective, Wang et al3 investigate how to decide key parameters in service-oriented cloud computing systems to improve the system's performance and maximize the service provider's profit. The paper proposes a multiple game model to formulate the critical parameters decision process. For games among different participators, different rules are used to estimate corresponding key parameters. The proposed MG model can achieve Pareto-optimal equilibrium point, and its efficiency in dynamically deciding key parameters in CCSs are demonstrated by simulation results. Underlying infrastructure plays also a vital role for cloud performance. Newly emerging networking paradigms like Software-Defined Networking (SDN) promises more advances like flexibility and efficiency to cloud management. He et al4 propose NetCore-M language, a high abstraction level programming language for SDN. It can support for packet drop and conflicts detection. NetCore-M language provides a more abstract programming language for network configuration in data center. Specifically, the paper describes in detail the syntax, semanteme, and implementation of NetCore-M language as well as network policy conflict. Besides, this paper verifies that the modified multi-policies combination algorithm can effectively detect policy conflicts based on the implementation of the Pyretic project. Security of applications in multi-cloud collaborative environments is a major concern in today's distributed computing environment. Multi-cloud collaborative environments are highly heterogeneous. The security issues in such environments most commonly arise due to the use of ineffective access control mechanisms. The primary goal of Attribute-based Access Control (ABAC) as an access control model is to fulfill the requirements of highly heterogeneous environments such as multi-cloud environment. There are two major challenges for a system employing ABAC. The first is to determine suitable attributes for users and resources in the system. Formation of the correct set of ABAC rules is another major challenge. John et al5 investigate the development of two alternative approaches for deriving the minimum number of ABAC rules in a multi-cloud environment. In the first approach, they consider forming a minimal set of positive authorizations only. The second approach shows the advantage of developing negative authorizations along with positive authorizations. Together, these two contributions extend the current state-of-the-art in cloud security. With the advent of cloud computing, more and more consumers prefer to use the cloud services with the pay-as-you-consume mode. The cloud storage brings about great convenience to users, who store data in cloud and access to it using the smart devices anytime and anywhere. Consumers' information should be encrypted to guarantee the data privacy. Flexible searching on ciphertext is a critical challenge to be solved for effective data utilization. Yang et al6 propose a novel semantic keyword searchable proxy re-encryption scheme for secure cloud storage. The scheme is quantum attack resistant, while most of the available searchable encryption schemes are not. It not only supports exact keyword search, but also synonym keyword search. Moreover, the data owner is capable to delegate his search right to another user using the proxy re-encryption mechanism. In the generation process of re-encryption key, the delegator and delegate do not need to interactive with each other. The scheme is also collusion resistant. Under the learning with errors hardness problem, this scheme is proved secure in standard model. Wu et al7 investigates how to prohibit massive Twitter spams from cloud. This paper leveraged the massive posts information from social network platforms especially Twitter. Learning from millions of text-based tweets (Twitter messages), algorithms were generated to detect social spammers who propagate suspicious information. The authors developed an innovative spam detection method in Twitter using deep learning techniques, which may contribute to the field in terms of protecting cyber security. They put forward a new Twitter spam detection method based on deep learning to address the problems of existing methods. A series of empirical and theoretical analysis have been adopted to prove the outperformance of the proposed method. These studies will contribute to future analysis and optimization on Twitter spam detection. Meanwhile, more and more client applications for cloud are based on mobile devices. Thus, the security of mobile operating systems is crucial for securing the cloud applications. Qiang et al8 embark on solving the covert channel issues in smartphone operating systems, which may lead to furtive data transmission between applications with different permissions that might threaten users' privacy. The authors propose a general method that can detect covert channel attacks at runtime without impacting the accessibility of shared resources in the system. The method allows users to describe and audit the target covert channels in the application layer as well as the OS layer, by making use of Java hooks and kernel audit tool auditd. The main idea of the method is to track and audit the use of system resources known as potential covert channel variables and impose interferences on those channels to reduce their capacity once violations are detected. They implement a prototype framework to audit and interfere covert communication in both the application layer and the native layer of Android. The experimental results demonstrate that the proposed method can effectively reduce the data rate of user-defined covert channels while the overhead is negligible. The papers presented in this special issue provide research articles related to recent advances in cloud computing. In particular, these research articles aim to strengthen cloud performance and security, from various aspects including task scheduling and underlying SDN infrastructure. We hope that the readers of this special issue will benefit from the research ideas and concepts presented in these research articles. The guest editors of this special issue would like to express their special thanks to all of the authors who submitted their papers to this special issue and to all reviewers who contribute to the paper selection process. We would also like to deeply thank Professor Geoffrey C. Fox, the Editor-in-Chief, for providing the opportunity to publish this special issue and for offering continuous support, encouragement, and guidance throughout this publishing project.

Software-defined networking (SDN) promises unprecedentedly flexible network management but it is susceptible to forwarding faults. Such faults originate from data-plane rules with missing faults and priority faults. Yet existing fault detection ignores priority faults, because they are not discovered on commercial switches until recently. In this paper, we present RuleScope, a more comprehensive solution for inspecting SDN forwarding. RuleScope offers a series of accurate and efficient algorithms for detecting and troubleshooting rule faults. They inspect forwarding behavior using customized probe packets to exercise data-plane rules. The detection algorithm exposes not only missing faults but also priority faults and the troubleshooting algorithm uncover actual forwarding states of data-plane flow tables. Both of them help track real-time forwarding status and benefit reliable network monitoring. Furthermore, toward fast inspection of dynamic networks, we propose incremental algorithms for rapidly evolving network policies to amortize detection and troubleshooting overhead without sacrificing accuracy. Experiments with our prototype on the Ryu SDN controller and Pica8 P-3297 switch show that the RuleScope achieves accurate fault detection on 320-entry flow tables with a cost of 1500+ probe packets within 16 s.

An RFID system can greatly improve the efficiency of tagged object inventory setup and update. It is necessary to periodically take stock of tags and update the inventory accordingly (i.e., deleting absent tags and adding new tags) in dynamic scenarios such as warehouses and shopping malls. Fast tag stocktaking is critical for the dynamic RFID system management. Previous work can take stock of tags by either collecting IDs of all the tags in the system, which is known to be inefficient, or broadcasting a long indicator vector to save tag identification time, which is not compatible with current commercial-off-the-shelf (COTS) tags. In this paper, we propose HARN, a protocol that can quickly take stock of tags in dynamic RFID systems but is compatible with COTS RFID tags and easily applied in a real RFID system. HARN uses only one more hash in the standard EPC C1G2 protocol. It leverages the new hash to generate the random number (RN) for a tag that can be used for both channel contention and known tag recognition, which can save the tedious ID transmission from known tags to readers and greatly speed up the stocktaking of tags. Simulation results demonstrate that HARN improves stocktaking throughput by up to 3.8x when compared to the state-of-the-art solutions in dynamic RFID systems.

Software-dehned network (SDN) is deemed to enable more dynamic management of data center networks that promptly respond to network events with changes in network policies. Although the SDN controller architecture is increasingly optimized for swift policy updates, the data plane, especially the prevailing TCAM-based flow tables on physical SDN switches, remains unoptimized for fast rule updates, and is gradually becoming the primary bottleneck along the policy update pipeline. In this paper, we present RuleTris, the hrst SDN update optimization framework that minimizes rule update latency for TCAM-based switches. RuleTris employs the dependency graph (DAG) as the key abstraction to minimize the update latency. RuleTris efhciently obtains the DAGs with novel dependency preserving algorithms that incrementally build rule dependency along with the compilation process. Then, in the guidance of the DAG, RuleTris optimizes the rule updates in TCAM to avoid unnecessary entry moves, which are the main cause of TCAM update inefhciency. We prove that RuleTris generates TCAM updates with the minimum number of TCAM entry moves. In evaluation, RuleTris achieves a median of <;12ms and 90-percentile of <;15ms the end-to-end per-rule update latency on our hardware prototype, outperforming the state-of-the-art composition compiler CoVisor by ~20 times.

Software-Defined Networking (SDN) promises un-precedentedly flexible network management but it is susceptible to forwarding faults. Such faults originate from data-plane rules with missing faults and priority faults. Yet existing fault detection ignores priority faults because they are not discovered on commercial switches until recently. In this paper, we present RuleScope, a more comprehensive solution for inspecting SDN forwarding. RuleScope offers a series of accurate and efficient algorithms for detecting and troubleshooting rule faults. They inspect forwarding behavior using customized probe packets to exercise data-plane rules. The detection algorithm exposes not only missing faults but also priority faults. Beyond simply detecting rule faults, the troubleshooting algorithms uncover actual data-plane flow tables. They help track real-time forwarding status and benefit reliable network monitoring. We explore various techniques for enhancing algorithm efficiency without sacrificing inspection accuracy. Experiments with our prototype on the Ryu SDN controller and Pica8 P-3297 switch show that RuleScope achieves accurate and efficient forwarding inspection with limited bandwidth and packet-switching overhead.

Tag scanning is an important issue to dynamically manage tag IDs in radio frequency identification (RFID) systems. Different from tag identification that collects IDs of all the tags, tag scanning first verifies whether or not a responding tag has already been identified and retrieves its ID when the answer is yes, and collects the tag's ID only when it is unidentified. In this paper, we present the first study on spot scanning with a handheld reader, which aims to scan tags in the reader's interrogation range at an arbitrarily specified position in the system. Existing studies mainly focus on continuous scanning, and they are highly time inefficient in performing spot scanning. The inefficiency stems from the small overlap between tag populations in different spot scanning operations, in which case existing solutions cannot efficiently recognize unidentified tags. We develop a novel technique called LOCK to efficiently recognize unidentified tags even when the overlapped tags are few. LOCK does not simply use a tag's reply slot index but also compact short responses from tags to efficiently distinguish unidentified tags from identified ones. The valuable compact short responses are firstly investigated, which are the keys for efficient tag identification in the paper. Based on LOCK, three tag scanning protocols are proposed to solve the spot scanning problem. Simulation results show that, for spot scanning, our best protocol reduces per tag scanning time by up to 70 percent when compared with the state-of-the-art solution. Moreover, the proposed protocols can also be employed to perform continuous scanning with better time efficiency than the best existing solutions.

Online social networks (OSNs) are extremely popular among Internet users. However, spam originating from friends and acquaintances not only reduces the joy of Internet surfing but also causes damage to less security-savvy users. Prior countermeasures combat OSN spam from different angles. Due to the diversity of spam, there is hardly any existing method that can independently detect the majority or most of OSN spam. In this paper, we empirically analyze the textual pattern of a large collection of OSN spam. An inspiring finding is that the majority (e.g., 76.4% in 2015) of the collected spam is generated with underlying templates. Based on the analysis, we propose tangram, an OSN spam filtering system that performs online inspection on the stream of user-generated messages. Tangram extracts the templates of spam detected by existing methods and then matching messages against the templates toward the accurate and the fast spam detection. It automatically divides the OSN spam into segments and uses the segments to construct templates to filter future spam. Experimental results on Twitter and Facebook data sets show that tangram is highly accurate and can rapidly generate templates to throttle newly emerged campaigns. Furthermore, we analyze the behavior of detected OSN spammers. We find a series of spammer properties-such as spamming accounts are created in bursts and a single active organization orchestrates more spam than all other spammers combined-that promise more comprehensive spam countermeasures.

Recently, there has been growing interest in indoor localization, because numerous applications depend on the rapid and accurate position estimation of tagged objects. While RFID-based indoor localization is attractive, the need for a large-scale and high-density deployment of readers and reference tags is costly. Being the range-free localization, our schemes depend solely on mobile readers without reference tags or other devices, and it avoids the need of distance estimation according to RSSI or phase difference. We propose two novel algorithms, continuous scanning and category-based scheduling, for locating single and multiple tagged objects, respectively. Our primary experimental results show that the system can achieve high time efficiency and localization accuracy.

The radio frequency identification (RFID) technology is greatly revolutionizing applications such as warehouse management and inventory control in retail industry. In large RFID systems, an important and practical issue is tag searching: Given a particular set of tags called wanted tags, tag searching aims to determine which of them are currently present in the system and which are not. As an RFID system usually contains a large number of tags, the intuitive solution that collects IDs of all the tags in the system and compares them with the wanted tag IDs to obtain the result is highly time inefficient. In this paper, we design a novel technique called testing slot, with which a reader can quickly figure out which wanted tags are absent from its interrogation region without tag ID transmissions. The testing slot technique thus greatly reduces transmission overhead during the searching process. Based on this technique, we propose two protocols to perform time-efficient tag searching in practical large RFID systems containing multiple readers. In our protocols, each reader first employs the testing slot technique to obtain its local searching result by iteratively eliminating wanted tags that are absent from its interrogation region. The local searching results of readers are then combined to form the final searching result. The proposed protocols outperform existing solutions in both time efficiency and searching precision. Simulation results show that, compared with the state-of-the-art solution, our best protocol reduces execution time by up to 60 percent, meanwhile promotes the searching precision by nearly an order of magnitude.

Cloning attacks seriously impede the security of radio-frequency identification (RFID) applications. This paper tackles deterministic clone detection for anonymous RFID systems without tag identifiers (IDs) as a priori. Existing clone detection protocols either cannot apply to anonymous RFID systems due to necessitating the knowledge of tag IDs or achieve only probabilistic detection with a few clones tolerated. This paper proposes three protocols—BASE, DeClone, and DeClone+—toward fast and deterministic clone detection for large anonymous RFID systems. BASE leverages the observation that clone tags make tag cardinality exceed ID cardinality. DeClone is built on a recent finding that clone tags cause collisions that are hardly reconciled through rearbitration. For DeClone to achieve detection certainty, this paper designs breadth first tree traversal toward quickly verifying unreconciled collisions and hence the cloning attack. DeClone+ further incorporates optimization techniques that promise faster clone detection when clone ratio is relatively high. The performance of the proposed protocols is validated through analysis and simulation. This paper also suggests feasible extensions to enrich their applicability to distributed design.

Radio-Frequency Identification (RFID) technology brings revolutionary changes to many fields like retail industry. One important research issue in large RFID systems is the identification of unknown tags, i.e., tags that just entered the system but have not been interrogated by reader(s) covering them yet. Unknown tag identification plays a critical role in automatic inventory management and misplaced tag discovery, but it is far from thoroughly investigated. Existing solutions either trivially interrogate all the tags in the system and thus are highly time inefficient due to re-identification of already identified tags, or use probabilistic approaches that cannot guarantee complete identification of all the unknown tags. In this paper, we propose a series of protocols that can identify all of the unknown tags with high time efficiency. We develop several novel techniques to quickly deactivate already identified tags and prevent them from replying during the interrogation of unknown tags, which avoids re-identification of these tags and consequently improves time efficiency. To our knowledge, our protocols are the first non-trivial solutions that guarantee complete identification of all the unknown tags. We illustrate the effectiveness of our protocols through both rigorous theoretical analysis and extensive simulations. Simulation results show that our protocols can save up to 70 percent time when compared with the best existing solutions.

In online social networks (OSNs), spam originating from friends and acquaintances not only reduces the joy of Internet surfing but also causes damage to less security-savvy users. Prior countermeasures combat OSN spam from different angles. Due to the diversity of spam, there is hardly any existing method that can independently detect the majority or most of OSN spam. In this paper, we empirically analyze the textual pattern of a large collection of OSN spam. An inspiring finding is that the majority (63.0%) of the collected spam is generated with underlying templates. We therefore propose extracting templates of spam detected by existing methods and then matching messages against the templates toward accurate and fast spam detection. We implement this insight through Tangram, an OSN spam filtering system that performs online inspection on the stream of user-generated messages. Tangram automatically divides OSN spam into segments and uses the segments to construct templates to filter future spam. Experimental results show that Tangram is highly accurate and can rapidly generate templates to throttle newly emerged campaigns. Specifically, Tangram detects the most prevalent template-based spam with 95.7% true positive rate, whereas the existing template generation approach detects only 32.3%. The integration of Tangram and its auxiliary spam filter achieves an overall accuracy of 85.4% true positive rate and 0.33% false positive rate.

Radio-Frequency Identification (RFID) technology has fostered many object monitoring systems. Along with this trend, tagged objects' value and privacy become a primary concern. A corresponding important problem is to verify the intactness of a set of tagged objects without leaking tag identifiers (IDs). However, existing solutions necessitate the knowledge of tag IDs. Without tag IDs as a priori, this paper studies intactness verification in anonymous RFID systems. We identify three critical solution requirements, that is, deterministic verification, anonymity preservation, and scalability. We propose Cardiff and Divar, two crypto-free, lightweight protocols that isolate tag IDs from intactness verification and satisfy solution requirements. Cardiff explores tag cardinality as intactness proof while Divar leverages Direct-Sequence Spread Spectrum (DSSS) enabled RFID. Both analytical and simulation results demonstrate that Cardiff and Divar can satisfy the requirements of accuracy, privacy, and scalability.

Radio Frequency Identification (RFID) has dramatically streamlined supply chain management by automatically monitoring and tracking commodities. Considering the proliferation of RFID data volume, distributed storage is more applicable and scalable than centralized storage for distributed query processing. Traditional distributed RFID data storage requires each distribution center to locally store raw RFID data, leading to data redundancy, storage and query inefficiency. In this paper, we design an efficient distributed storage model by leveraging Bloom filters to save storage space and improve query efficiency. Meanwhile, we establish corresponding query processing schemes to locally support existence queries and path queries, which are two kinds of most popular queries in the supply chain management. A local query can be completed with constant time complexity regardless of data volume. Experiments demonstrate that our storage model outperforms the traditional one in terms of both space and time efficiency.

Tag identification is the most fundamental problem in Radio Frequency Identification (RFID) systems. Time efficiency is the top quality of service (QoS) metric in RFID tag identification. Traditional tag scanning approaches suffer from low time efficiency because they need to transmit tag IDs that are usually very long (e.g., 96 bits). In this paper, we investigate how to employ handheld readers to improve the time efficiency of tag identification and provide flexibility to scan tags on different purposes. A fast and flexible tag scanning mechanism called LOCK is proposed, which combines both the information and the replying slot index of a tag's response. In LOCK, tags transmit only short responses instead of tag IDs. Based on LOCK, we propose two novel tag scanning protocols that progressively add new techniques on top of one another to improve the time efficiency. Compared to the state-of-the-art solution in literature, our best protocol reduces scanning time by up to 53 percent.

Cloning attacks seriously impede the security of Radio-Frequency Identification (RFID) applications. In this paper, we tackle deterministic clone detection for anonymous RFID systems without tag identifiers (IDs) as a priori. Existing clone detection protocols either cannot apply to anonymous RFID systems due to necessitating the knowledge of tag IDs or achieve only probabilistic detection with a few clones tolerated. We propose two protocols, BASE and DeClone, toward fast and deterministic clone detection for large anonymous RFID systems. BASE leverages the observation that clone tags make tag cardinality exceed ID cardinality. DeClone is built on a recent finding that clone tags cause collisions that are hardly reconciled through re-arbitration. For DeClone to achieve detection certainty, we design breadth first tree traversal toward quickly verifying unreconciled collisions and hence the cloning attack. We validate their detection performance through analysis and simulation. The results show that BASE delivers faster detection for small systems while DeClone for large ones especially when clone ratio increases.

In wireless sensor networks, an important research problem is to use a few anchor nodes with known locations to derive the locations of other nodes deployed in the sensor field. A category of solutions for this problem is the iterative localization, which sequentially merges the elements in a network to finally locate them. Here, a network element is different from its definition in iterative trilateration. It can be either an individual node or a group of nodes. For this approach, we identify a new problem called inflexible body merging, whose objective is to align two small network elements and generate a larger element. It is more generalized than the traditional tools of trilateration and patch stitching and can replace them as a new merging primitive. We solve this problem and make the following contributions. Our primitive can tolerate ranging noise when merging two network elements. It adopts an optimization algorithm based on rigid body dynamics and relaxing springs. Our primitive improves the robustness against flip ambiguities. It uses orthogonal regression to detect the rough collinearity of nodes in the presence of ranging noise, and then enumerate flip ambiguities accordingly. We present a condition to indicate when we can apply this primitive to align two network elements. This condition can unify previous work and thus achieve a higher percentage of localizable nodes. All the declared contributions have been validated by both theoretical analysis and simulation results.

Blocker tags are initially introduced to protect regular tags in certain ID ranges, called blocking ranges, from unwanted scanning in RFID systems. But if misused, blocker tags can cause blocking attacks that corrupt the communication between interfered regular tags and readers. Previous approaches can only detect blocking behavior. However, they cannot distinguish malicious blocking from legitimate blocking that can be perfectly allowed to protect customer's privacy. To solve the problem, we carry out the first attempt in the paper to detect real blocking attacks by identifying malicious blocking ranges from authorized ones in a system. We present two pioneer probe-based protocols that can accurately identify malicious blocking ranges in popular tree-based RFID systems, and get rid of their impact before performing RFID applications. We validate the efficacy of the two protocols through theoretical analysis and simulation experiments. The results show that our protocols can identify blocking ranges very fast even when the blocker tag percentage is very low, for example, dozens of blocker tags among tens of thousands of regular tags. Our protocols deliver also a faster blocker tag detection than previous detection methods; our best protocol reduces detection time by over 90% compared with the state-of-the-art detection method.

Radio-Frequency Identification (RFID) technology has successfully proven its potential for locating objects in a 3-dimensional (3D) space. Current RFID-based 3D localization is built on the ethos of striving for accuracy. This paper takes the first step toward efficient localization with high time efficiency and energy efficiency, which are important for accelerating positioning operation and prolonging system lifetime. To this end, we propose leveraging known locations of deployed reference readers and reference tags to probe as a few reference tags as sufficient for localization. Counter-intuitively, localization using fewer reference tags promises rather higher efficiency yet without necessarily sacrificing accuracy. We design efficient passive scheme and efficient active scheme for both typical RFID-based 3D localization scenarios, locating a target tag using reference readers/tags and locating a target reader using reference tags. We evaluate their performance through quantitative analysis and extensive simulation. The results show that the proposed schemes outperform existing schemes in time efficiency and energy efficiency by over 95% on average.

SUMMARY As radio frequency identification (RFID) tags become more ubiquitously available, they will stay in dynamic environments where tags can freely enter or leave RFID readers' interrogation range. With such a dynamic tag population, there arises a problem of population monitoring, whose purpose is to identify themissing tagsthat have departed from the reading range and thenew tagsthat have newly entered. This problem is a new problem which cannot be well solved by the conventional tag identification protocols. In this paper, we first show that this traditional approach is inefficient, because it collects all the tag IDs in each scan and ignores the ready‐for‐use knowledge of the tag population in a previous scan. To be more efficient, we present three protocols: (i) a baseline protocol that improves the traditional tag identification protocol by optimizing its length of random number used for collision detection; (ii) a novel one‐phase protocol with easy labor to identify exactly the new tags and the missing tags by fully utilizing the knowledge of previous tag population; and (iii) a hybrid protocol that smartly combines the baseline protocol and the one‐phase protocol. Its purpose is to deal with the situation that the knowledge of previous tag population is highly inconsistent with the current tag population. This hybrid protocol, as shown by our analysis, can improve the tag monitoring accuracy by 25%, and improve the time efficiency by 55.3%, as compared with a recent work (called two‐phase protocol), which also identifies the population changes. Copyright © 2012 John Wiley & Sons, Ltd.

Cloning attacks threaten radio-frequency identification (RFID) applications but are hard to prevent. Existing cloning attack detection methods are enslaved to the knowledge of tag identifiers (IDs). Tag IDs, however, should be protected to enable and secure privacy-sensitive applications in anonymous RFID systems. In a first step, this paper tackles cloning attack detection in anonymous RFID systems without requiring tag IDs as a priori. To this end, we leverage unreconciled collisions to uncover cloning attacks. An unreconciled collision is probably due to responses from multiple tags with the same ID, exactly the evidence of cloning attacks. This insight inspires GREAT, our pioneer protocol for cloning attack detection in anonymous RFID systems. We evaluate the performance of GREAT through theoretical analysis and extensive simulations. The results show that GREAT can detect cloning attacks in anonymous RFID systems fairly fast with required accuracy. For example, when only six out of 50,000 tags are cloned, GREAT can detect the cloning attack in 75.5 s with a probability of at least 0.99.

In wireless sensor networks, a critical system service is the localization service that determines the locations of geographically distributed sensor nodes. The raw data used by this service are the distance measurements between neighboring nodes and the position knowledge of anchor nodes. However, these raw data may contain outliers that strongly deviate from their true values, which include both the outlier distances and the outlier anchors. These outliers can severely degrade the accuracy of the localization service. Therefore, we need a robust localization algorithm that can reject these outliers. Previous studies in this field mainly focus on enhancing multilateration with outlier rejection ability, since multilateration is a primitive operation used by localization service. But patch merging, a powerful operation for increasing the percentage of localizable nodes in sparse networks, is almost neglected. We thus propose a robust patch merging operation that can reject outliers for both multilateration and patch merging. Based on this operation, we further propose a robust network localization algorithm called RobustLoc . This algorithm makes two major contributions. (1) RobustLoc can achieve a high percentage of localizable nodes in both dense and sparse networks. In contrast, previous methods based on robust multilateration almost always fail in sparse networks with average degrees between 5 and 7. Our experiments show that RobustLoc can localize about 90% of nodes in a sparse network with 5.5 degrees. (2) As far as we know, RobustLoc is the first to uncover the differences between outlier distances and outlier anchors. Our simulations show that RobustLoc can reject colluding outlier anchors reliably in both convex and concave networks.

Piece-related algorithms, including piece revelation, selection, and queuing, play a crucial role in the BitTorrent (BT) protocol, because the BT system can be viewed as a market where peers trade their pieces with one another. During the piece exchanging, a peer selects some pieces revealed by neighbors, and queues them up for downloading. In this paper, we provide a deep understanding of these algorithms, and also propose some improvements to them. Previous study has shown that the piece revelation strategy is vulnerable to under-reporting. We provide a game-theoretic analysis for this selfish gaming, and propose a distributed credit method to prevent it. Existing piece selection strategies, though long believed to be good enough, may fail to balance piece supply and demand. We propose a unified strategy to shorten the download time of peers by applying utility theory. The design of the piece queuing algorithm has a conflict with that of piece selection strategy, because it is not possible to assume that the queued requests for a selected piece can always be available on multiple neighbors. We give a possible fix to address the conflict by allowing peers to dynamically manage their unfulfilled requests. To evaluate the performance of the proposed algorithms, we run several experiments in a live swarm. Our primary results show that they can achieve fast individual and system-wide download time.

Tag cloning attacks threaten a variety of Radio Frequency Identification (RFID) applications but are hard to prevent. To secure RFID applications that confine tagged objects in the same RFID system, this paper studies the cloned-tag identification problem. Although limited existing work has shed some light on the problem, designing fast cloned-tag identification protocols for applications in large-scale RFID systems is yet not thoroughly investigated. To this end, we propose leveraging broadcast and collisions to identify cloned tags. This approach relieves us from resorting to complex cryptography techniques and time-consuming transmission of tag IDs. Based on this approach, we derive a time lower bound on cloned-tag identification and propose a suite of time-efficient protocols toward approaching the time lower bound. The execution time of our protocol is only 1.4 times the value of the time lower bound, being up to 91% less than that of the existing protocol. The proposed protocols may benefit also RFID applications that distribute tagged objects across multiple places.

The RFID technology greatly improves efficiency of many applications including inventory control, object tracking, and supply chain management. In such applications, it is common that new objects are added into the system or existing objects are misplaced in wrong regions. When this happens, fast and complete identification of such tags is very important. We name this problem unknown tag identification, as these tags appear to be unknown by the reader(s) currently covering them. In this paper, we propose a series of protocols to identify unknown tags completely and fast. In these protocols, we develop several novel techniques to efficiently resolve collisions caused by known tags when identifying unknown tags, which greatly improve the time efficiency. To our knowledge, this is the first work that completely identify all the unknown tags with deterministic approaches. Simulation results show the superior performance of the proposed protocols: Compared with a baseline method which collects IDs of all the tags in the system, our best protocol reduces the execution time by 63% in average and by 85% at most.

Radio-Frequency Identification (RFID) technology brings many innovative applications. Of great importance to RFID applications in production economics is misplaced-tag pinpointing (MTP), because misplacement errors fail optimal inventory placement and thus significantly decrease profit. The existing MTP solution [1], originally proposed from a data-processing perspective, collects and processes a large amount of data. It suffers from time inefficiency (and energy-inefficiency as well if active tags are in use). The problem of finding efficient solutions for the MTP problem from the communication protocol design perspective has never been investigated before. In this paper, we propose a series of protocols toward efficient MTP solutions in large RFID systems. The proposed protocols detect misplaced tags using reader positions instead of tag positions to guarantee the efficiency and scalability as system scale grows, because RFID readers are much fewer than tags. Considering applications that employ active tags, we further propose a solution requiring responses from only a subset of tags in favor of energy saving. We also design a distributed protocol that enables each reader to independently detect misplaced tags. We then investigate how to apply the proposed protocols in scenarios with tag mobility. To evaluate the proposed protocols, we analyze their optimal performances to demonstrate their efficiency potential and also conduct extensive simulation experiments. The results show that the proposed protocols can significantly increase the time efficiency and the energy efficiency by over 70 percent on average when compared with the best existing work.

As RFID tags become more ubiquitously available, e.g., in a supermarket, it is necessary to monitor larger-scale tag populations in a dynamic environment to get updated tag information. This paper considers the problem of monitoring a dynamic tag population, to identify both the missing tags and new tags. Traditional approach can solve the problem by collecting all tag IDs in the current population, which could be slow because it ignores the knowledge of the tag population in a previous scan. To be more efficient, this paper presents two protocols: (1) a baseline protocol with optimized length of random number bits, (2) an improved one-phase protocol with easy labor to identify only the new and missing tags in ALOHA frames by fully utilizing previous tag population knowledge. Our analysis shows that the one-phase protocol can improve the monitoring accuracy by 25% and improve the time efficiency by 55%, as compared with the two-phase protocol proposed in a recent paper which also identifies population changes.

The Radio-Frequency Identification (RFID) technology has stimulated many innovative applications. Misplaced-tag pinpointing (MTP) is important to RFID applications in production economics because optimal inventory placement can significantly increase profit. Previous research from the database perspective needs to process a large amount of data which is time-consuming to collect (and energy-consuming if active tags are used). How to efficiently address the MTP problem from the protocol design perspective however has not been investigated. In this paper, we propose a series of protocols toward efficient MTP solution in large RFID systems. The proposed protocols detect misplaced tags based on reader positions instead of tag positions to guarantee the efficiency and scalability as system scale grows, because the number of readers is much smaller than that of tags. Considering applications to employ more and more popular active tags, we further propose a solution requiring responses from only partial tags in favor of energy saving. We analyze the optimal performances of proposed protocols to demonstrate their efficiency potential and conduct extensive simulation experiments to evaluate their performance under various scenarios. The results show that the proposed protocols can significantly increase the time efficiency and the energy efficiency by over 70% on average when compared with the state of the art.