Visible to the public Biblio

Found 12055 results

Journal Article
Hanford, Nathan, Ahuja, Vishal, Farrens, Matthew K., Tierney, Brian, Ghosal, Dipak.  2018.  A Survey of End-System Optimizations for High-Speed Networks. ACM Comput. Surv.. 51:54:1-54:36.

The gap is widening between the processor clock speed of end-system architectures and network throughput capabilities. It is now physically possible to provide single-flow throughput of speeds up to 100 Gbps, and 400 Gbps will soon be possible. Most current research into high-speed data networking focuses on managing expanding network capabilities within datacenter Local Area Networks (LANs) or efficiently multiplexing millions of relatively small flows through a Wide Area Network (WAN). However, datacenter hyper-convergence places high-throughput networking workloads on general-purpose hardware, and distributed High-Performance Computing (HPC) applications require time-sensitive, high-throughput end-to-end flows (also referred to as ``elephant flows'') to occur over WANs. For these applications, the bottleneck is often the end-system and not the intervening network. Since the problem of the end-system bottleneck was uncovered, many techniques have been developed which address this mismatch with varying degrees of effectiveness. In this survey, we describe the most promising techniques, beginning with network architectures and NIC design, continuing with operating and end-system architectures, and concluding with clean-slate protocol design.

Butun, I., Morgera, S.D., Sankar, R..  2014.  A Survey of Intrusion Detection Systems in Wireless Sensor Networks. Communications Surveys Tutorials, IEEE. 16:266-282.

Wireless Sensor Networking is one of the most promising technologies that have applications ranging from health care to tactical military. Although Wireless Sensor Networks (WSNs) have appealing features (e.g., low installation cost, unattended network operation), due to the lack of a physical line of defense (i.e., there are no gateways or switches to monitor the information flow), the security of such networks is a big concern, especially for the applications where confidentiality has prime importance. Therefore, in order to operate WSNs in a secure way, any kind of intrusions should be detected before attackers can harm the network (i.e., sensor nodes) and/or information destination (i.e., data sink or base station). In this article, a survey of the state-of-the-art in Intrusion Detection Systems (IDSs) that are proposed for WSNs is presented. Firstly, detailed information about IDSs is provided. Secondly, a brief survey of IDSs proposed for Mobile Ad-Hoc Networks (MANETs) is presented and applicability of those systems to WSNs are discussed. Thirdly, IDSs proposed for WSNs are presented. This is followed by the analysis and comparison of each scheme along with their advantages and disadvantages. Finally, guidelines on IDSs that are potentially applicable to WSNs are provided. Our survey is concluded by highlighting open research issues in the field.

Shin, Youngjoo, Koo, Dongyoung, Hur, Junbeom.  2017.  A Survey of Secure Data Deduplication Schemes for Cloud Storage Systems. ACM Comput. Surv.. 49:74:1–74:38.

Data deduplication has attracted many cloud service providers (CSPs) as a way to reduce storage costs. Even though the general deduplication approach has been increasingly accepted, it comes with many security and privacy problems due to the outsourced data delivery models of cloud storage. To deal with specific security and privacy issues, secure deduplication techniques have been proposed for cloud data, leading to a diverse range of solutions and trade-offs. Hence, in this article, we discuss ongoing research on secure deduplication for cloud data in consideration of the attack scenarios exploited most widely in cloud storage. On the basis of classification of deduplication system, we explore security risks and attack scenarios from both inside and outside adversaries. We then describe state-of-the-art secure deduplication techniques for each approach that deal with different security issues under specific or combined threat models, which include both cryptographic and protocol solutions. We discuss and compare each scheme in terms of security and efficiency specific to different security goals. Finally, we identify and discuss unresolved issues and further research challenges for secure deduplication in cloud storage.

Kaur, R., Singh, M..  2014.  A Survey on Zero-Day Polymorphic Worm Detection Techniques. Communications Surveys Tutorials, IEEE. 16:1520-1549.

Zero-day polymorphic worms pose a serious threat to the Internet security. With their ability to rapidly propagate, these worms increasingly threaten the Internet hosts and services. Not only can they exploit unknown vulnerabilities but can also change their own representations on each new infection or can encrypt their payloads using a different key per infection. They have many variations in the signatures of the same worm thus, making their fingerprinting very difficult. Therefore, signature-based defenses and traditional security layers miss these stealthy and persistent threats. This paper provides a detailed survey to outline the research efforts in relation to detection of modern zero-day malware in form of zero-day polymorphic worms.

Kirsch, J., Goose, S., Amir, Y., Dong Wei, Skare, P..  2014.  Survivable SCADA Via Intrusion-Tolerant Replication. Smart Grid, IEEE Transactions on. 5:60-70.

Providers of critical infrastructure services strive to maintain the high availability of their SCADA systems. This paper reports on our experience designing, architecting, and evaluating the first survivable SCADA system-one that is able to ensure correct behavior with minimal performance degradation even during cyber attacks that compromise part of the system. We describe the challenges we faced when integrating modern intrusion-tolerant protocols with a conventional SCADA architecture and present the techniques we developed to overcome these challenges. The results illustrate that our survivable SCADA system not only functions correctly in the face of a cyber attack, but that it also processes in excess of 20 000 messages per second with a latency of less than 30 ms, making it suitable for even large-scale deployments managing thousands of remote terminal units.

Chiang, R., Rajasekaran, S., Zhang, N., Huang, H..  2014.  Swiper: Exploiting Virtual Machine Vulnerability in Third-Party Clouds with Competition for I/O Resources. Parallel and Distributed Systems, IEEE Transactions on. PP:1-1.

The emerging paradigm of cloud computing, e.g., Amazon Elastic Compute Cloud (EC2), promises a highly flexible yet robust environment for large-scale applications. Ideally, while multiple virtual machines (VM) share the same physical resources (e.g., CPUs, caches, DRAM, and I/O devices), each application should be allocated to an independently managed VM and isolated from one another. Unfortunately, the absence of physical isolation inevitably opens doors to a number of security threats. In this paper, we demonstrate in EC2 a new type of security vulnerability caused by competition between virtual I/O workloads-i.e., by leveraging the competition for shared resources, an adversary could intentionally slow down the execution of a targeted application in a VM that shares the same hardware. In particular, we focus on I/O resources such as hard-drive throughput and/or network bandwidth-which are critical for data-intensive applications. We design and implement Swiper, a framework which uses a carefully designed workload to incur significant delays on the targeted application and VM with minimum cost (i.e., resource consumption). We conduct a comprehensive set of experiments in EC2, which clearly demonstrates that Swiper is capable of significantly slowing down various server applications while consuming a small amount of resources.

Boloorchi, Alireza T., Samadzadeh, M. H., Chen, T..  2014.  Symmetric Threshold Multipath (STM): An Online Symmetric Key Management Scheme. Inf. Sci.. 268:489–504.

The threshold secret sharing technique has been used extensively in cryptography. This technique is used for splitting secrets into shares and distributing the shares in a network to provide protection against attacks and to reduce the possibility of loss of information. In this paper, a new approach is introduced to enhance communication security among the nodes in a network based on the threshold secret sharing technique and traditional symmetric key management. The proposed scheme aims to enhance security of symmetric key distribution in a network. In the proposed scheme, key distribution is online which means key management is conducted whenever a message needs to be communicated. The basic idea is encrypting a message with a key (the secret) at the sender, then splitting the key into shares and sending the shares from different paths to the destination. Furthermore, a Pre-Distributed Shared Key scheme is utilized for more secure transmissions of the secret’s shares. The proposed scheme, with the exception of some offline management by the network controller, is distributed, i.e., the symmetric key setups and the determination of the communication paths is performed in the nodes. This approach enhances communication security among the nodes in a network that operates in hostile environments. The cost and security analyses of the proposed scheme are provided.

Kaci, A., Kamwa, I., Dessaint, L.A., Guillon, S..  2014.  Synchrophasor Data Baselining and Mining for Online Monitoring of Dynamic Security Limits. Power Systems, IEEE Transactions on. 29:2681-2695.

When the system is in normal state, actual SCADA measurements of power transfers across critical interfaces are continuously compared with limits determined offline and stored in look-up tables or nomograms in order to assess whether the network is secure or insecure and inform the dispatcher to take preventive action in the latter case. However, synchrophasors could change this paradigm by enabling new features, the phase-angle differences, which are well-known measures of system stress, with the added potential to increase system visibility. The paper develops a systematic approach to baseline the phase-angles versus actual transfer limits across system interfaces and enable synchrophasor-based situational awareness (SBSA). Statistical methods are first used to determine seasonal exceedance levels of angle shifts that can allow real-time scoring and detection of atypical conditions. Next, key buses suitable for SBSA are identified using correlation and partitioning around medoid (PAM) clustering. It is shown that angle shifts of this subset of 15% of the network backbone buses can be effectively used as features in ensemble decision tree-based forecasting of seasonal security margins across critical interfaces.

Li, X., Deng, M., Wang, X., Li, H., Yu, M..  2019.  Synthesis and magnetic properties of Fe-doped CdS nanorods. Micro Nano Letters. 14:275–279.
Hexagonal CdS and Fe-doped CdS nanorods were synthesised by a facile hydrothermal method and characterised by X-ray diffraction, energy dispersive X-ray spectroscopy, UV-vis absorption, photoluminescence, and X-ray photoelectron spectroscopy. The magnetic properties of undoped and Fe-doped CdS nanorods were investigated at room temperature. The experimental results demonstrate that the ferromagnetism of the Fe-doped CdS nanorods differs from that of the undoped CdS nanorods. The remanence magnetisation (Mr) and the coercive field (Hc) of the Fe-doped CdS nanorods were 4.9 × 10-3 emu/g and 270.6 Oe, respectively, while photoluminescence properties were not influenced by doping. First-principle calculations show that the ferromagnetism in Fe-doped CdS nanocrystal arose not only from the Fe dopants but also from the Cd vacancies, although the main contribution was due to the Fe dopants.
Mozaffari-Kermani, M., Sur-Kolay, S., Raghunathan, A., Jha, N. K..  2015.  Systematic Poisoning Attacks on and Defenses for Machine Learning in Healthcare. IEEE Journal of Biomedical and Health Informatics. 19:1893–1905.

Machine learning is being used in a wide range of application domains to discover patterns in large datasets. Increasingly, the results of machine learning drive critical decisions in applications related to healthcare and biomedicine. Such health-related applications are often sensitive, and thus, any security breach would be catastrophic. Naturally, the integrity of the results computed by machine learning is of great importance. Recent research has shown that some machine-learning algorithms can be compromised by augmenting their training datasets with malicious data, leading to a new class of attacks called poisoning attacks. Hindrance of a diagnosis may have life-threatening consequences and could cause distrust. On the other hand, not only may a false diagnosis prompt users to distrust the machine-learning algorithm and even abandon the entire system but also such a false positive classification may cause patient distress. In this paper, we present a systematic, algorithm-independent approach for mounting poisoning attacks across a wide range of machine-learning algorithms and healthcare datasets. The proposed attack procedure generates input data, which, when added to the training set, can either cause the results of machine learning to have targeted errors (e.g., increase the likelihood of classification into a specific class), or simply introduce arbitrary errors (incorrect classification). These attacks may be applied to both fixed and evolving datasets. They can be applied even when only statistics of the training dataset are available or, in some cases, even without access to the training dataset, although at a lower efficacy. We establish the effectiveness of the proposed attacks using a suite of six machine-learning algorithms and five healthcare datasets. Finally, we present countermeasures against the proposed generic attacks that are based on tracking and detecting deviations in various accuracy metrics, and benchmark their effectiveness.

Zeng, Jing, Yang, Laurence T., Lin, Man, Shao, Zili, Zhu, Dakai.  2017.  System-Level Design Optimization for Security-Critical Cyber-Physical-Social Systems. ACM Trans. Embed. Comput. Syst.. 16:39:1–39:21.

Cyber-physical-social systems (CPSS), an emerging computing paradigm, have attracted intensive attentions from the research community and industry. We are facing various challenges in designing secure, reliable, and user-satisfied CPSS. In this article, we consider these design issues as a whole and propose a system-level design optimization framework for CPSS design where energy consumption, security-level, and user satisfaction requirements can be fulfilled while satisfying constraints for system reliability. Specifically, we model the constraints (energy efficiency, security, and reliability) as the penalty functions to be incorporated into the corresponding objective functions for the optimization problem. A smart office application is presented to demonstrate the feasibility and effectiveness of our proposed design optimization approach.

Jiankun Hu, Pota, H.R., Song Guo.  2014.  Taxonomy of Attacks for Agent-Based Smart Grids. Parallel and Distributed Systems, IEEE Transactions on. 25:1886-1895.

Being the most important critical infrastructure in Cyber-Physical Systems (CPSs), a smart grid exhibits the complicated nature of large scale, distributed, and dynamic environment. Taxonomy of attacks is an effective tool in systematically classifying attacks and it has been placed as a top research topic in CPS by a National Science Foundation (NSG) Workshop. Most existing taxonomy of attacks in CPS are inadequate in addressing the tight coupling of cyber-physical process or/and lack systematical construction. This paper attempts to introduce taxonomy of attacks of agent-based smart grids as an effective tool to provide a structured framework. The proposed idea of introducing the structure of space-time and information flow direction, security feature, and cyber-physical causality is innovative, and it can establish a taxonomy design mechanism that can systematically construct the taxonomy of cyber attacks, which could have a potential impact on the normal operation of the agent-based smart grids. Based on the cyber-physical relationship revealed in the taxonomy, a concrete physical process based cyber attack detection scheme has been proposed. A numerical illustrative example has been provided to validate the proposed physical process based cyber detection scheme.

Kuang, Liwei, Yang, Laurence T., Rho, Seungmin(Charlie), Yan, Zheng, Qiu, Kai.  2016.  A Tensor-Based Framework for Software-Defined Cloud Data Center. ACM Trans. Multimedia Comput. Commun. Appl.. 12:74:1–74:23.

Multimedia has been exponentially increasing as the biggest big data, which consist of video clips, images, and audio files. Processing and analyzing them on a cloud data center have become a preferred solution that can utilize the large pool of cloud resources to address the problems caused by the tremendous amount of unstructured multimedia data. However, there exist many challenges in processing multimedia big data on a cloud data center, such as multimedia data representation approach, an efficient networking model, and an estimation method for traffic patterns. The primary purpose of this article is to develop a novel tensor-based software-defined networking model on a cloud data center for multimedia big-data computation and communication. First, an overview of the proposed framework is provided, in which the functions of the representative modules are briefly illustrated. Then, three models,—forwarding tensor, control tensor, and transition tensor—are proposed for management of networking devices and prediction of network traffic patterns. Finally, two algorithms about single-mode and multimode tensor eigen-decomposition are developed, and the incremental method is employed for efficiently updating the generated eigen-vector and eigen-tensor. Experimental results reveal that the proposed framework is feasible and efficient to handle multimedia big data on a cloud data center.

Gröndahl, Tommi, Asokan, N..  2019.  Text Analysis in Adversarial Settings: Does Deception Leave a Stylistic Trace? ACM Computing Surveys (CSUR). 52:45:1-45:36.

Textual deception constitutes a major problem for online security. Many studies have argued that deceptiveness leaves traces in writing style, which could be detected using text classification techniques. By conducting an extensive literature review of existing empirical work, we demonstrate that while certain linguistic features have been indicative of deception in certain corpora, they fail to generalize across divergent semantic domains. We suggest that deceptiveness as such leaves no content-invariant stylistic trace, and textual similarity measures provide a superior means of classifying texts as potentially deceptive. Additionally, we discuss forms of deception beyond semantic content, focusing on hiding author identity by writing style obfuscation. Surveying the literature on both author identification and obfuscation techniques, we conclude that current style transformation methods fail to achieve reliable obfuscation while simultaneously ensuring semantic faithfulness to the original text. We propose that future work in style transformation should pay particular attention to disallowing semantically drastic changes.

HOU, RUI, Han, Min, Chen, Jing, Hu, Wenbin, Tan, Xiaobin, Luo, Jiangtao, Ma, Maode.  2019.  Theil-Based Countermeasure against Interest Flooding Attacks for Named Data Networks. IEEE Network. 33:116—121.

NDN has been widely regarded as a promising representation and implementation of information- centric networking (ICN) and serves as a potential candidate for the future Internet architecture. However, the security of NDN is threatened by a significant safety hazard known as an IFA, which is an evolution of DoS and distributed DoS attacks on IP-based networks. The IFA attackers can create numerous malicious interest packets into a named data network to quickly exhaust the bandwidth of communication channels and cache capacity of NDN routers, thereby seriously affecting the routers' ability to receive and forward packets for normal users. Accurate detection of the IFAs is the most critical issue in the design of a countermeasure. To the best of our knowledge, the existing IFA countermeasures still have limitations in terms of detection accuracy, especially for rapidly volatile attacks. This article proposes a TC to detect the distributions of normal and malicious interest packets in the NDN routers to further identify the IFA. The trace back method is used to prevent further attempts. The simulation results show the efficiency of the TC for mitigating the IFAs and its advantages over other typical IFA countermeasures.

Lu, Sixing, Lysecky, Roman.  2017.  Time and Sequence Integrated Runtime Anomaly Detection for Embedded Systems. ACM Trans. Embed. Comput. Syst.. 17:38:1–38:27.

Network-connected embedded systems grow on a large scale as a critical part of Internet of Things, and these systems are under the risk of increasing malware. Anomaly-based detection methods can detect malware in embedded systems effectively and provide the advantage of detecting zero-day exploits relative to signature-based detection methods, but existing approaches incur significant performance overheads and are susceptible to mimicry attacks. In this article, we present a formal runtime security model that defines the normal system behavior including execution sequence and execution timing. The anomaly detection method in this article utilizes on-chip hardware to non-intrusively monitor system execution through trace port of the processor and detect malicious activity at runtime. We further analyze the properties of the timing distribution for control flow events, and select subset of monitoring targets by three selection metrics to meet hardware constraint. The designed detection method is evaluated by a network-connected pacemaker benchmark prototyped in FPGA and simulated in SystemC, with several mimicry attacks implemented at different levels. The resulting detection rate and false positive rate considering constraints on the number of monitored events supported in the on-chip hardware demonstrate good performance of our approach.

Arias Cabarcos, Patricia, Almenárez, Florina, Gómez Mármol, Félix, Mar\'ın, Andrés.  2014.  To Federate or Not To Federate: A Reputation-Based Mechanism to Dynamize Cooperation in Identity Management. Wirel. Pers. Commun.. 75:1769–1786.

Identity Management systems cannot be centralized anymore. Nowadays, users have multiple accounts, profiles and personal data distributed throughout the web and hosted by different providers. However, the online world is currently divided into identity silos forcing users to deal with repetitive authentication and registration processes and hindering a faster development of large scale e-business. Federation has been proposed as a technology to bridge different trust domains, allowing user identity information to be shared in order to improve usability. But further research is required to shift from the current static model, where manual bilateral agreements must be pre-configured to enable cooperation between unknown parties, to a more dynamic one, where trust relationships are established on demand in a fully automated fashion. This paper presents IdMRep, the first completely decentralized reputation-based mechanism which makes dynamic federation a reality. Initial experiments demonstrate its accuracy as well as an assumable overhead in scenarios with and without malicious nodes.

Dong Jin, Illinois Institute of Technology, Zhiyi Li, Illinois Institute of Technology, Christopher Hannon, Illinois Institute of Technology, Chen Chen, Argonne National Laboratory, Jianhui Wang, Argonne National Laboratory, Mohammad Shahidehpour, Illinois Institute of Technology, Cheol Won Lee, National Research Institute, South Korea.  2017.  Toward a Cyber Resilient and Secure Microgrid Using Software-Defined Networking. IEEE Transactions on Smart Grid. 8(5)

To build a resilient and secure microgrid in the face of growing cyber-attacks and cyber-mistakes, we present a software-defined networking (SDN)-based communication network architecture for microgrid operations. We leverage the global visibility, direct networking controllability, and programmability offered by SDN to investigate multiple security applications, including self-healing communication network management, real-time and uncertainty-aware communication network verification, and specification-based intrusion detection. We also expand a novel cyber-physical testing and evaluation platform that combines a power distribution system simulator (for microgrid energy services) and an SDN emulator with a distributed control environment (for microgrid communications). Experimental results demonstrate that the SDN-based communication architecture and applications can significantly enhance the resilience and security of microgrid operations against the realization of various cyber threats.

McDaniel, P., Rivera, B., Swami, A..  2014.  Toward a Science of Secure Environments. Security Privacy, IEEE. 12:68-70.

The longstanding debate on a fundamental science of security has led to advances in systems, software, and network security. However, existing efforts have done little to inform how an environment should react to emerging and ongoing threats and compromises. The authors explore the goals and structures of a new science of cyber-decision-making in the Cyber-Security Collaborative Research Alliance, which seeks to develop a fundamental theory for reasoning under uncertainty the best possible action in a given cyber environment. They also explore the needs and limitations of detection mechanisms; agile systems; and the users, adversaries, and defenders that use and exploit them, and conclude by considering how environmental security can be cast as a continuous optimization problem.

McDaniel, P., Rivera, B., Swami, A..  2014.  Toward a Science of Secure Environments. Security Privacy, IEEE. 12:68-70.

The longstanding debate on a fundamental science of security has led to advances in systems, software, and network security. However, existing efforts have done little to inform how an environment should react to emerging and ongoing threats and compromises. The authors explore the goals and structures of a new science of cyber-decision-making in the Cyber-Security Collaborative Research Alliance, which seeks to develop a fundamental theory for reasoning under uncertainty the best possible action in a given cyber environment. They also explore the needs and limitations of detection mechanisms; agile systems; and the users, adversaries, and defenders that use and exploit them, and conclude by considering how environmental security can be cast as a continuous optimization problem.

Abdelzaher, T., Ayanian, N., Basar, T., Diggavi, S., Diesner, J., Ganesan, D., Govindan, R., Jha, S., Lepoint, T., Marlin, B. et al..  2018.  Toward an Internet of Battlefield Things: A Resilience Perspective. Computer. 51:24—36.

The Internet of Battlefield Things (IoBT) might be one of the most expensive cyber-physical systems of the next decade, yet much research remains to develop its fundamental enablers. A challenge that distinguishes the IoBT from its civilian counterparts is resilience to a much larger spectrum of threats.

Dutt, Nikil, Jantsch, Axel, Sarma, Santanu.  2016.  Toward Smart Embedded Systems: A Self-aware System-on-Chip (SoC) Perspective. ACM Trans. Embed. Comput. Syst.. 15:22:1–22:27.

Embedded systems must address a multitude of potentially conflicting design constraints such as resiliency, energy, heat, cost, performance, security, etc., all in the face of highly dynamic operational behaviors and environmental conditions. By incorporating elements of intelligence, the hope is that the resulting “smart” embedded systems will function correctly and within desired constraints in spite of highly dynamic changes in the applications and the environment, as well as in the underlying software/hardware platforms. Since terms related to “smartness” (e.g., self-awareness, self-adaptivity, and autonomy) have been used loosely in many software and hardware computing contexts, we first present a taxonomy of “self-x” terms and use this taxonomy to relate major “smart” software and hardware computing efforts. A major attribute for smart embedded systems is the notion of self-awareness that enables an embedded system to monitor its own state and behavior, as well as the external environment, so as to adapt intelligently. Toward this end, we use a System-on-Chip perspective to show how the CyberPhysical System-on-Chip (CPSoC) exemplar platform achieves self-awareness through a combination of cross-layer sensing, actuation, self-aware adaptations, and online learning. We conclude with some thoughts on open challenges and research directions.

Zhuo Hao, Yunlong Mao, Sheng Zhong, Li, L.E., Haifan Yao, Nenghai Yu.  2014.  Toward Wireless Security without Computational Assumptions #x2014;Oblivious Transfer Based on Wireless Channel Characteristics. Computers, IEEE Transactions on. 63:1580-1593.

Wireless security has been an active research area since the last decade. A lot of studies of wireless security use cryptographic tools, but traditional cryptographic tools are normally based on computational assumptions, which may turn out to be invalid in the future. Consequently, it is very desirable to build cryptographic tools that do not rely on computational assumptions. In this paper, we focus on a crucial cryptographic tool, namely 1-out-of-2 oblivious transfer. This tool plays a central role in cryptography because we can build a cryptographic protocol for any polynomial-time computable function using this tool. We present a novel 1-out-of-2 oblivious transfer protocol based on wireless channel characteristics, which does not rely on any computational assumption. We also illustrate the potential broad applications of this protocol by giving two applications, one on private communications and the other on privacy preserving password verification. We have fully implemented this protocol on wireless devices and conducted experiments in real environments to evaluate the protocol. Our experimental results demonstrate that it has reasonable efficiency.

Solomonik, Edgar, Carson, Erin, Knight, Nicholas, Demmel, James.  2017.  Trade-Offs Between Synchronization, Communication, and Computation in Parallel Linear Algebra Computations. ACM Trans. Parallel Comput.. 3:3:1–3:47.

This article derives trade-offs between three basic costs of a parallel algorithm: synchronization, data movement, and computational cost. These trade-offs are lower bounds on the execution time of the algorithm that are independent of the number of processors but dependent on the problem size. Therefore, they provide lower bounds on the execution time of any parallel schedule of an algorithm computed by a system composed of any number of homogeneous processors, each with associated computational, communication, and synchronization costs. We employ a theoretical model that measures the amount of work and data movement as a maximum over that incurred along any execution path during the parallel computation. By considering this metric rather than the total communication volume over the whole machine, we obtain new insights into the characteristics of parallel schedules for algorithms with nontrivial dependency structures. We also present reductions from BSP and LogGP algorithms to our execution model, extending our lower bounds to these two models of parallel computation. We first develop our results for general dependency graphs and hypergraphs based on their expansion properties, and then we apply the theorem to a number of specific algorithms in numerical linear algebra, namely triangular substitution, Cholesky factorization, and stencil computations. We represent some of these algorithms as families of dependency graphs. We derive their communication lower bounds by studying the communication requirements of the hypergraph structures shared by these dependency graphs. In addition to these lower bounds, we introduce a new communication-efficient parallelization for stencil computation algorithms, which is motivated by results of our lower bound analysis and the properties of previously existing parallelizations of the algorithms.

Pan, Weike, Yang, Qiang, Duan, Yuchao, Ming, Zhong.  2016.  Transfer Learning for Semisupervised Collaborative Recommendation. ACM Trans. Interact. Intell. Syst.. 6:10:1–10:21.

Users’ online behaviors such as ratings and examination of items are recognized as one of the most valuable sources of information for learning users’ preferences in order to make personalized recommendations. But most previous works focus on modeling only one type of users’ behaviors such as numerical ratings or browsing records, which are referred to as explicit feedback and implicit feedback, respectively. In this article, we study a Semisupervised Collaborative Recommendation (SSCR) problem with labeled feedback (for explicit feedback) and unlabeled feedback (for implicit feedback), in analogy to the well-known Semisupervised Learning (SSL) setting with labeled instances and unlabeled instances. SSCR is associated with two fundamental challenges, that is, heterogeneity of two types of users’ feedback and uncertainty of the unlabeled feedback. As a response, we design a novel Self-Transfer Learning (sTL) algorithm to iteratively identify and integrate likely positive unlabeled feedback, which is inspired by the general forward/backward process in machine learning. The merit of sTL is its ability to learn users’ preferences from heterogeneous behaviors in a joint and selective manner. We conduct extensive empirical studies of sTL and several very competitive baselines on three large datasets. The experimental results show that our sTL is significantly better than the state-of-the-art methods.