Biblio

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? This problem was raised by Buss and Goldberg and Papadimitriou in the context of TFNP, search problems with a guaranteed solution. We examine the relationship between black-box complexity and white-box complexity for search problems with guaranteed solution such as the above Ramsey problem. We show that under the assumption that collision resistant hash function exist (which follows from the hardness of problems such as factoring, discrete-log and learning with errors) the white-box Ramsey problem is hard and this is true even if one is looking for a much smaller clique or independent set than the theorem guarantees. In general, one cannot hope to translate all black-box hardness for TFNP into white-box hardness: we show this by adapting results concerning the random oracle methodology and the impossibility of instantiating it. Another model we consider is the succinct black-box, where there is a known upper bound on the size of the black-box (but no limit on the computation time). In this case we show that for all TFNP problems there is an upper bound on the number of queries proportional to the description size of the box times the solution size. On the other hand, for promise problems this is not the case. Finally, we consider the complexity of graph property testing in the white-box model. We show a property which is hard to test even when one is given the program for computing the graph. The hard property is whether the graph is a two-source extractor.

The disclosure of an important yet sensitive link may cause serious privacy crisis between two users of a social graph. Only deleting the sensitive link referred to as a target link which is often the attacked target of adversaries is not enough, because the adversarial link prediction can deeply forecast the existence of the missing target link. Thus, to defend some specific adversarial link prediction, a budget limited number of other non-target links should be optimally removed. We first propose a path-based dissimilarity function as the optimizing objective and prove that the greedy link deletion to preserve target link privacy referred to as the GLD2Privacy which has monotonicity and submodularity properties can achieve a near optimal solution. However, emulating all length limited paths between any pair of nodes for GLD2Privacy mechanism is impossible in large scale social graphs. Secondly, we propose a Walk2Privacy mechanism that uses self-avoiding random walk which can efficiently run in large scale graphs to sample the paths of given lengths between the two ends of any missing target link, and based on the sampled paths we select the alternative non-target links being deleted for privacy purpose. Finally, we compose experiments to demonstrate that the Walk2Privacy algorithm can remarkably reduce the time consumption and achieve a very near solution that is achieved by the GLD2Privacy.

SVM has been one of the most popular machine learning method for the binary classification such as sentiment analysis and spam message filtering. We explored a word embedding method for the construction of a feature vector and the deep learning method for the binary classification. CBOW is used as a word embedding technique and feedforward neural network is applied to classify SMS messages into ham or spam. The accuracy of the two classification methods of SVM and neural network are compared for the binary classification. The experimental result shows that the accuracy of deep learning method is better than the conventional machine learning method of SVM-light in the binary classification.

Today's virtual switches not only support legacy network protocols and standard network management interfaces, but also become adapted to OpenFlow as a prevailing communication protocol. This makes them a core networking component of today's virtualized infrastructures which are able to handle sophisticated networking scenarios in a flexible and software-defined manner. At the same time, these virtual SDN data planes become high-value targets because a compromised switch is hard to detect while it affects all components of a virtualized/SDN-based environment.Most of the well known programmable virtual switches in the market are open source which makes them cost-effective and yet highly configurable options in any network infrastructure deployment. However, this comes at a cost which needs to be addressed. Accordingly, this paper raises an alarm on how attackers may leverage white box analysis of software switch functionalities to lunch effective low profile attacks against it. In particular, we practically present how attackers can systematically take advantage of static and dynamic code analysis techniques to lunch a low rate saturation attack on virtual SDN data plane in a cloud data center.

We revisit Physical-Layer Network Coding (PLNC) and the reasons preventing it from becoming a staple in wireless networks. We identify its strong coupling to the Two-Way Relay Channel (TWRC) as key among them due to its requiring crossing traffic flows and two-hop node coordination. We introduce SE-PLNC, a Source-Encoded PLNC scheme that is traffic pattern independent and involves coordination only among one-hop neighbors, making it significantly more practical to adopt PLNC in multi-hop wireless networks. To accomplish this, SE-PLNC introduces three innovations: it combines bit-level with physical-level network coding, it shifts most of the coding burden from the relay to the source of the PLNC scheme, and it leverages multi-path relaying opportunities available to a particular traffic flow. We evaluate SE-PLNC using theoretical analysis, proof-of-concept implementation on a Universal Software Radio Peripherals (USRP) testbed, and simulations. The theoretical analysis shows the scalability of SE-PLNC and its efficiency in large ad-hoc networks while the testbed experiments its real-life feasibility. Large-scale simulations show that TWRC PLNC barely boosts network throughput while SE-PLNC improves it by over 30%.

We present a scalable dynamic analysis framework that allows for the automatic evaluation of the privacy behaviors of Android apps. We use our system to analyze mobile apps’ compliance with the Children’s Online Privacy Protection Act (COPPA), one of the few stringent privacy laws in the U.S. Based on our automated analysis of 5,855 of the most popular free children’s apps, we found that a majority are potentially in violation of COPPA, mainly due to their use of thirdparty SDKs. While many of these SDKs offer configuration options to respect COPPA by disabling tracking and behavioral advertising, our data suggest that a majority of apps either do not make use of these options or incorrectly propagate them across mediation SDKs. Worse, we observed that 19% of children’s apps collect identifiers or other personally identifiable information (PII) via SDKs whose terms of service outright prohibit their use in child-directed apps. Finally, we show that efforts by Google to limit tracking through the use of a resettable advertising ID have had little success: of the 3,454 apps that share the resettable ID with advertisers, 66% transmit other, non-resettable, persistent identifiers as well, negating any intended privacy-preserving properties of the advertising ID.

Phishing is a criminal offense which involves theft of user's sensitive data. The phishing websites target individuals, organizations, the cloud storage hosting sites and government websites. Currently, hardware based approaches for anti-phishing is widely used but due to the cost and operational factors software based approaches are preferred. The existing phishing detection approaches fails to provide solution to problem like zero-day phishing website attacks. To overcome these issues and precisely detect phishing occurrence a three phase attack detection named as Web Crawler based Phishing Attack Detector(WC-PAD) has been proposed. It takes the web traffics, web content and Uniform Resource Locator(URL) as input features, based on these features classification of phishing and non phishing websites are done. The experimental analysis of the proposed WC-PAD is done with datasets collected from real phishing cases. From the experimental results, it is found that the proposed WC-PAD gives 98.9% accuracy in both phishing and zero-day phishing attack detection.

The rapid growth and globalization of the integrated circuit (IC) industry put the threat of hardware Trojans (HTs) front and center among all security concerns in the IC supply chain. Current Trojan detection approaches always assume HTs are composed of digital circuits. However, recent demonstrations of analog attacks, such as A2 and Rowhammer, invalidate the digital assumption in previous HT detection or testing methods. At the system level, attackers can utilize the analog properties of the underlying circuits such as charge-sharing and capacitive coupling effects to create information leakage paths. These new capacitor-based vulnerabilities are rarely covered in digital testings. To address these stealthy yet harmful threats, we identify a large class of such capacitor-enabled attacks and define them as charge-domain Trojans. We are able to abstract the detailed charge-domain models for these Trojans and expose the circuit-level properties that critically contribute to their information leakage paths. Aided by the abstract models, an information flow tracking (IFT) based solution is developed to detect charge-domain leakage paths and then identify the charge-domain Trojans/vulnerabilities. Our proposed method is validated on an experimental RISC microcontroller design injected with different variants of charge-domain Trojans. We demonstrate that successful detection can be accomplished with an automatic tool which realizes the IFT-based solution.

Atomic multicast is a communication primitive that delivers messages to multiple groups of processes according to some total order, with each group receiving the projection of the total order onto messages addressed to it. To be scalable, atomic multicast needs to be genuine, meaning that only the destination processes of a message should participate in ordering it. In this paper we propose a novel genuine atomic multicast protocol that in the absence of failures takes as low as 3 message delays to deliver a message when no other messages are multicast concurrently to its destination groups, and 5 message delays in the presence of concurrency. This improves the latencies of both the fault-tolerant version of classical Skeen's multicast protocol (6 or 12 message delays, depending on concurrency) and its recent improvement by Coelho et al. (4 or 8 message delays). To achieve such low latencies, we depart from the typical way of guaranteeing fault-tolerance by replicating each group with Paxos. Instead, we weave Paxos and Skeen's protocol together into a single coherent protocol, exploiting opportunities for white-box optimisations. We experimentally demonstrate that the superior theoretical characteristics of our protocol are reflected in practical performance pay-offs.

Network virtualization is a fundamental technology for datacenters and upcoming wireless communications (e.g., 5G). It takes advantage of software-defined networking (SDN) that provides efficient network management by converting networking fabrics into SDN-capable devices. Moreover, white-box switches, which provide flexible and fast packet processing, are broadly deployed in commercial datacenters. A white-box switch requires a specific and restricted packet processing pipeline; however, to date, there has been no SDN-based network hypervisor that can support the pipeline of white-box switches. Therefore, in this paper, we propose WhiteVisor: a network hypervisor which can support the physical network composed of white-box switches. WhiteVisor converts a flow rule from the virtual network into a packet processing pipeline compatible with the white-box switch. We implement the prototype herein and show its feasibility and effectiveness with pipeline conversion and overhead.

The economic progress of the Internet of Things (IoT) is phenomenal. Applications range from checking the alignment of some components during a manufacturing process, monitoring of transportation and pedestrian levels to enhance driving and walking path, remotely observing terminally ill patients by means of medical devices such as implanted devices and infusion pumps, and so on. To provide security, encrypting the data becomes an indispensable requirement, and symmetric encryptions algorithms are becoming a crucial implementation in the resource constrained environments. Typical symmetric encryption algorithms like Advanced Encryption Standard (AES) showcases an assumption that end points of communications are secured and that the encryption key being securely stored. However, devices might be physically unprotected, and attackers may have access to the memory while the data is still encrypted. It is essential to reserve the key in such a way that an attacker finds it hard to extract it. At present, techniques like White-Box cryptography has been utilized in these circumstances. But it has been reported that applying White-Box cryptography in IoT devices have resulted in other security issues like the adversary having access to the intermediate values, and the practical implementations leading to Code lifting attacks and differential attacks. In this paper, a solution is presented to overcome these problems by demonstrating the need of White-Box Cryptography to enhance the security by utilizing the cipher block chaining (CBC) mode.

Mobile payment has drawn considerable attention due to its convenience of paying via personal mobile devices at anytime and anywhere, and passcodes (i.e., PINs or patterns) are the first choice of most consumers to authorize the payment. This paper demonstrates a serious security breach and aims to raise the awareness of the public that the passcodes for authorizing transactions in mobile payments can be leaked by exploiting the embedded sensors in wearable devices (e.g., smartwatches). We present a passcode inference system, WristSpy, which examines to what extent the user's PIN/pattern during the mobile payment could be revealed from a single wrist-worn wearable device under different passcode input scenarios involving either two hands or a single hand. In particular, WristSpy has the capability to accurately reconstruct fine-grained hand movement trajectories and infer PINs/patterns when mobile and wearable devices are on two hands through building a Euclidean distance-based model and developing a training-free parallel PIN/pattern inference algorithm. When both devices are on the same single hand, a highly challenging case, WristSpy extracts multi-dimensional features by capturing the dynamics of minute hand vibrations and performs machine-learning based classification to identify PIN entries. Extensive experiments with 15 volunteers and 1600 passcode inputs demonstrate that an adversary is able to recover a user's PIN/pattern with up to 92% success rate within 5 tries under various input scenarios.

We propose WristUnlock, a novel technique that uses a wrist wearable to unlock a smartphone in a secure and usable fashion. WristUnlock explores both the physical proximity and secure Bluetooth connection between the smartphone and wrist wearable. There are two modes in WristUnlock with different security and usability features. In the WristRaise mode, the user raises his smartphone in his natural way with the same arm carrying the wrist wearable; the smartphone gets unlocked if the acceleration data on the smartphone and wrist wearable satisfy an anticipated relationship specific to the user himself. In the WristTouch mode, the wrist wearable sends a random number to the smartphone through both the Bluetooth channel and a touch-based physical channel; the smartphone gets unlocked if the numbers received from both channels are equal. We thoroughly analyze the security of WristUnlock and confirm its high efficacy through detailed experiments.

The need for sensors to deliver, communicate, collect, alert, and share information in various applications has made wireless sensor networks very popular. However, due to its limited resources in terms of computation power, battery life and memory storage of the sensor nodes, it is challenging to add security features to provide the confidentiality, integrity, and availability. Blockchain technology ensures security and avoids the need of any trusted third party. However, applying Blockchain in a resource-constrained wireless sensor network is a challenging task because Blockchain is power, computation, and memory hungry in nature and demands heavy bandwidth due to control overheads. In this paper, a new routing and a private communication Blockchain framework is designed and tested with Constant Bit rate (CBR). The proposed Load Balancing Multi-Hop (LBMH) routing shares and enhances the battery life of the Cluster Heads and reduce control overhead during Block updates, but due to limited storage and energy of the sensor nodes, Blockchain in sensor networks may never become a reality unless computation, storage and battery life are readily available at low cost.

Wireless Sensor Networks (WSNs) are important and becoming more important as we integrate wireless sensor networks and the internet with different things, which has changed our life, and it is affected everywhere in our life like shopping, storage, live monitoring, smart home etc., called Internet of Things (IoT), as any use of the network physical devices that included in electronics, software, sensors, actuators, and connectivity which makes available these things to connect, collect and exchange data, and the most importantly thing is the accuracy of the data that has been collected in the Internet of Things, detecting sensor data with faulty readings is an important issue of secure communication and power consumption. So, requirement of energy-efficiency and integrity of information is mandatory.

Today's smart-grids have seen a clear rise in new ways of energy generation, transmission, and storage. This has not only introduced a huge degree of variability, but also a continual shift away from traditionally centralized generation and storage to distributed energy resources (DERs). In addition, the distributed sensors, energy generators and storage devices, and networking have led to a huge increase in attack vectors that make the grid vulnerable to a variety of attacks. The interconnection between computational and physical components through a largely open, IP-based communication network enables an attacker to cause physical damage through remote cyber-attacks or attack on software-controlled grid operations via physical- or cyber-attacks. Transactive Energy (TE) is an emerging approach for managing increasing DERs in the smart-grids through economic and control techniques. Transactive Smart-Grids use the TE approach to improve grid reliability and efficiency. However, skepticism remains in their full-scale viability for ensuring grid reliability. In addition, different TE approaches, in specific situations, can lead to very different outcomes in grid operations. In this paper, we present a comprehensive web-based platform for evaluating resilience of smart-grids against a variety of cyber- and physical-attacks and evaluating impact of various TE approaches on grid performance. We also provide several case-studies demonstrating evaluation of TE approaches as well as grid resilience against cyber and physical attacks.

Plenty of methods applied in system identification, while those based on data-driven are increasingly popular. Usually we ignore the absence of outliers among the system to be modeled, but it is unreachable in reality. To improve the precision of identification towards system with outliers, advantageous approaches with robustness are needed. This study analyzes the superiority of weighted Least Square Support Vector Machine Regression (LS-SVMR) in the field of system identification under random outliers, and compare it with LS-SVMR mainly.

Email privacy is of crucial importance. Existing email encryption approaches are comprehensive but seldom used due to their complexity and inconvenience. We take a new approach to simplify email encryption and improve its usability by implementing receiver-controlled encryption: newly received messages are transparently downloaded and encrypted to a locally-generated key; the original message is then replaced. To avoid the problem of moving a single private key between devices, we implement per-device key pairs: only public keys need be synchronized via a simple verification step. Compromising an email account or server only provides access to encrypted emails. We implemented this scheme on several platforms, showing it works with PGP and S/MIME, is compatible with widely used mail clients and email services including Gmail, has acceptable overhead, and that users consider it intuitive and easy to use.

In AI Matters Volume 4, Issue 2, and Issue 4, we raised the notion of the possibility of an AI Cosmology in part in response to the "AI Hype Cycle" that we are currently experiencing. We posited that our current machine learning and big data era represents but one peak among several previous peaks in AI research in which each peak had accompanying "Hype Cycles". We associated each peak with an epoch in a possible AI Cosmology. We briefly explored the logic machines, cybernetics, and expert system epochs. One of the objectives of identifying these epochs was to help establish that we have been here before. In particular we've been in the territory where some application of AI research finds substantial commercial success which is then closely followed by AI fever and hype. The public's expectations are heightened only to end in disillusionment when the applications fall short. Whereas it is sometimes somewhat of a challenge even for AI researchers, educators, and practitioners to know where the reality ends and hype begins, the layperson is often in an impossible position and at the mercy of pop culture, marketing and advertising campaigns. We suggested that an AI Cosmology might help us identify a single standard model for AI that could be the foundation for a common shared understanding of what AI is and what it is not. A tool to help the layperson understand where AI has been, where it's going, and where it can't go. Something that could provide a basic road map to help the general public navigate the pitfalls of AI Hype.

Network attacks continue to pose threats to missions in cyber space. To prevent critical missions from getting impacted or minimize the possibility of mission impact, active cyber defense is very important. Mission impact graph is a graphical model that enables mission impact assessment and shows how missions can be possibly impacted by cyber attacks. Although the mission impact graph provides valuable information, it is still very difficult for human analysts to comprehend due to its size and complexity. Especially when given limited resources, human analysts cannot easily decide which security measures to take first with respect to mission assurance. Therefore, this paper proposes to apply a ranking algorithm towards the mission impact graph so that the huge amount of information can be prioritized. The actionable conditions that can be managed by security admins are ranked with numeric values. The rank enables efficient utilization of limited resources and provides guidance for taking security countermeasures.

To experimentally study the characteristics of ultrasonic sensors, a wideband air-coupled ultrasonic transducer, wideband electromagnetic dynamic acoustic transducer (WEMDAT), is designed and fabricated. Characterisation methods, including electrical impedance analysis, laser Doppler vibrometry and pressure-field microphone measurement, are used to examine the performance of the WEMDAT, which have shown that the transducer has a wide bandwidth ranging approximately from 47 kHz to 145 kHz and a good directivity with a beam angle of around 20˚ with no evident side lobes. A 40 kHz commercial flexural ultrasonic transducer (FUT) is then taken as an example to receive ultrasonic waves in a pitch-catch configuration to evaluate the performance of the WEMDAT as an acoustic source. Experiment results have demonstrated that the WEMDAT can maintain the most of the frequency content of a 5 cycle 40 kHz tone burst electric signal and convert it into an ultrasonic wave for studying the dynamic characteristic and the directivity pattern of the ultrasonic receiver. A comparison of the dynamic characteristics between the transmitting and the receiving processes of the same FUT reveals that the FUT has a wider bandwidth when operating as an ultrasonic receiver than operating as a transmitter, which indicates that it is necessary to quantitatively investigate the receiving process of an ultrasonic transducer, demonstrating a huge potential of the WEMDAT serving as a standard acoustic source for ultrasonic sensors for various air-coupled ultrasonic applications.

Security engineers have been fighting with C compilers for years. A careful programmer would test for null pointer dereferencing or division by zero; but the compiler would fail to understand, and optimize the test away. Modern compilers now have dedicated options to mitigate this. But when a programmer tries to control side effects of code, such as to make a cryptographic algorithm execute in constant time, the problem remains. Programmers devise complex tricks to obscure their intentions, but compiler writers find ever smarter ways to optimize code. A compiler upgrade can suddenly and without warning open a timing channel in previously secure code. This arms race is pointless and has to stop. We argue that we must stop fighting the compiler, and instead make it our ally. As a starting point, we analyze the ways in which compiler optimization breaks implicit properties of crypto code; and add guarantees for two of these properties in Clang/LLVM. Our work explores what is actually involved in controlling side effects on modern CPUs with a standard toolchain. Similar techniques can and should be applied to other security properties; achieving intentions by compiler commands or annotations makes them explicit, so we can reason about them. It is already understood that explicitness is essential for cryptographic protocol security and for compiler performance; it is essential for language security too. We therefore argue that this should be only the first step in a sustained engineering effort.

The increasing adoption of 3D printing in many safety and mission critical applications exposes 3D printers to a variety of cyber attacks that may result in catastrophic consequences if the printing process is compromised. For example, the mechanical properties (e.g., physical strength, thermal resistance, dimensional stability) of 3D printed objects could be significantly affected and degraded if a simple printing setting is maliciously changed. To address this challenge, this study proposes a model-free real-time online process monitoring approach that is capable of detecting and defending against the cyber-physical attacks on the firmwares of 3D printers. Specifically, we explore the potential attacks and consequences of four key printing attributes (including infill path, printing speed, layer thickness, and fan speed) and then formulate the attack models. Based on the intrinsic relation between the printing attributes and the physical observations, our defense model is established by systematically analyzing the multi-faceted, real-time measurement collected from the accelerometer, magnetometer and camera. The Kalman filter and Canny filter are used to map and estimate three aforementioned critical toolpath information that might affect the printing quality. Mel-frequency Cepstrum Coefficients are used to extract features for fan speed estimation. Experimental results show that, for a complex 3D printed design, our method can achieve 4% Hausdorff distance compared with the model dimension for infill path estimate, 6.07% Mean Absolute Percentage Error (MAPE) for speed estimate, 9.57% MAPE for layer thickness estimate, and 96.8% accuracy for fan speed identification. Our study demonstrates that, this new approach can effectively defend against the cyber-physical attacks on 3D printers and 3D printing process.

As a frequent participant in eSociety, Willeke is often preoccupied with paperwork because there is no easy to use, affordable way to act as a qualified person in the digital world. Confidential interactions take place over insecure channels like e-mail and post. This situation poses risks and costs for service providers, civilians and governments, while goals regarding confidentiality and privacy are not always met. The objective of this paper is to demonstrate an alternative architecture in which identifying persons, exchanging information, authorizing external parties and signing documents will become more user-friendly and secure. As a starting point, each person has their personal data space, provided by a qualified trust service provider that also issues a high level of assurance electronic ID. Three main building blocks are required: (1) secure exchange between the personal data space of each person, (2) coordination functionalities provided by a token based infrastructure, and (3) governance over this infrastructure. Following the design science research approach, we developed prototypes of the building blocks that we will pilot in practice. Policy makers and practitioners that want to enable Willeke to get rid of her paperwork can find guidance throughout this paper and are welcome to join the pilots in the Netherlands.

Security experts often recommend using password-management tools that both store passwords and generate random passwords. However, research indicates that only a small fraction of users use password managers with password generators. Past studies have explored factors in the adoption of password managers using surveys and online store reviews. Here we describe a semi-structured interview study with 30 participants that allows us to provide a more comprehensive picture of the mindsets underlying adoption and effective use of password managers and password-generation features. Our participants include users who use no password-specific tools at all, those who use password managers built into browsers or operating systems, and those who use separately installed password managers. Furthermore, past field data has indicated that users of built-in, browser-based password managers more often use weak and reused passwords than users of separate password managers that have password generation available by default. Our interviews suggest that users of built-in password managers may be driven more by convenience, while users of separately installed tools appear more driven by security. We advocate tailored designs for these two mentalities and provide actionable suggestions to induce effective password manager usage.