Biblio
Let G be a finite connected graph, and let ρ be the spectral radius of its universal cover. For example, if G is k-regular then ρ=2√k−1. We show that for every r, there is an r-covering (a.k.a. an r-lift) of G where all the new eigenvalues are bounded from above by ρ. It follows that a bipartite Ramanujan graph has a Ramanujan r-covering for every r. This generalizes the r=2 case due to Marcus, Spielman and Srivastava (2013). Every r-covering of G corresponds to a labeling of the edges of G by elements of the symmetric group Sr. We generalize this notion to labeling the edges by elements of various groups and present a broader scenario where Ramanujan coverings are guaranteed to exist. In particular, this shows the existence of richer families of bipartite Ramanujan graphs than was known before. Inspired by Marcus-Spielman-Srivastava, a crucial component of our proof is the existence of interlacing families of polynomials for complex reflection groups. The core argument of this component is taken from Marcus-Spielman-Srivastava (2015). Another important ingredient of our proof is a new generalization of the matching polynomial of a graph. We define the r-th matching polynomial of G to be the average matching polynomial of all r-coverings of G. We show this polynomial shares many properties with the original matching polynomial. For example, it is real rooted with all its roots inside [−ρ,ρ].
Randomness is a vital resource for modern-day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high-quality random numbers generated securely. Here, we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: cryptographic level of security, tolerating a constant level of imprecision in devices, requiring only unit size quantum memory (for each device component) in an honest implementation, and allowing a large natural class of constructions for the protocol. In conjunction with a recent work by Chung et al. [2014], it also leads to robust unbounded expansion using just 2 multipart devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the Rényi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements and a method for simulating trusted measurements with untrusted devices.
As web applications is becoming more prominent due to the ubiquity of web services, web applications have become main targets for attackers. In order to steal or leak sensitive user data managed by web applications, attackers exploit a wide range of input validation vulnerabilities such as SQL injection, path traversal (or directory traversal), cross-site scripting (XSS), etc. This paper propose a technique that can verify input values of Java-based web applications using static bytecode instrumentation and runtime input validation. The technique searches for target methods or object constructors in compiled Java class files, and statically inserts bytecode modules. At runtime, the instrumented bytecode modules validate input values of the targets, and take countermeasure against malicious inputs. The proposed technique can mitigate the input validation vulnerabilities in Java-based web applications without source codes. To evaluate the effectiveness of the proposed technique, experiments are carried out with an insecure web application maintained by OWASP WebGoat Project. The experimental results show that the proposed technique successfully mitigates input validation vulnerabilities such as SQL injection and path traversal.
This paper presents a detection and containment mechanism for fast self-propagating network worm malware. The detection part of the mechanism uses two categories of network host activities to identify worm behaviour in a network. Upon an identified worm activity in a network, a data-link containment system is used to isolate the internal source of infection, and a network level containment system is used to block inbound worm datagrams. The mechanism has been demonstrated using a software prototype. A number of worm experiments have been conducted to evaluate the prototype. The empirical results show the effectiveness of the developed mechanism in containing fast network worm malware at an early stage with almost no false positives.
We propose the first verifier-local revocation scheme for privacy-enhancing attribute-based credentials (PABCs) that is practically usable in large-scale applications, such as national eID cards, public transportation and physical access control systems. By using our revocation scheme together with existing PABCs, it is possible to prove attribute ownership in constant time and verify the proof and the revocation status in the time logarithmic in the number of revoked users, independently of the number of all valid users in the system. Proofs can be efficiently generated using only offline constrained devices, such as existing smart-cards. These features are achieved by using a new construction called \$n\$-times unlinkable proofs. We show the full cryptographic description of the scheme, prove its security, discuss parameters influencing scalability and provide details on implementation aspects. As a side result of independent interest, we design a more efficient proof of knowledge of weak Boneh-Boyen signatures, that does not require any pairing computation on the prover side.
Content-based routing (CBR) is a powerful model that supports scalable asynchronous communication among large sets of geographically distributed nodes. Yet, preserving privacy represents a major limitation for the wide adoption of CBR, notably when the routers are located in public clouds. Indeed, a CBR router must see the content of the messages sent by data producers, as well as the filters (or subscriptions) registered by data consumers. This represents a major deterrent for companies for which data is a key asset, as for instance in the case of financial markets or to conduct sensitive business-to-business transactions. While there exists some techniques for privacy-preserving computation, they are either prohibitively slow or too limited to be usable in real systems. In this paper, we follow a different strategy by taking advantage of trusted hardware extensions that have just been introduced in off-the-shelf processors and provide a trusted execution environment. We exploit Intel's new software guard extensions (SGX) to implement a CBR engine in a secure enclave. Thanks to the hardware-based trusted execution environment (TEE), the compute-intensive CBR operations can operate on decrypted data shielded by the enclave and leverage efficient matching algorithms. Extensive experimental evaluation shows that SGX adds only limited overhead to insecure plaintext matching outside secure enclaves while providing much better performance and more powerful filtering capabilities than alternative software-only solutions. To the best of our knowledge, this work is the first to demonstrate the practical benefits of SGX for privacy-preserving CBR.
The market of wearable healthcare monitoring devices has exploded in recent years as healthcare consciousness has increased. These types of devices usually consist of several biosensors, which can be worn on human bodies, such as the head, arms, and feet. The health status of a user can be analyzed according to the user's real-time vital signs that are collected from different biosensors. Due to personal medical data being transmitted through a wireless network, the data have to be encrypted. In this paper, a key agreement protocol for biosensors within Wireless Body Sensor Networks (WBSN) has been proposed based on the n-Party Diffie-Hellman key exchange protocol. In order to prevent the man-in-the-middle attacks, we have used Advance Encryption Standard (AES) encryption with Electrocardiography-based (ECG-based) keys to secure the key exchange procedures. The security and performance analysis show the feasibility of the proposed method.
Proliferation of electronics and their increasing connectivity pose formidable challenges for information security. At the most fundamental level, nanostructures and nanomaterials offer an unprecedented opportunity to introduce new approaches to securing electronic devices. First, we discuss engineering nanomaterials, (e.g., carbon nanotubes (CNTs), graphene, and layered transition metal dichalcogenides (TMDs)) to make unclonable cryptographic primitives. These security primitives not only can supplement existing solutions in silicon integrated circuits (ICs) but can also be used for emerging applications in flexible and wearable electronics. Second, we discuss security engineering of advanced nanostructures such as reactive materials.
Sego is a hypervisor-based system that gives strong privacy and integrity guarantees to trusted applications, even when the guest operating system is compromised or hostile. Sego verifies operating system services, like the file system, instead of replacing them. By associating trusted metadata with user data across all system devices, Sego verifies system services more efficiently than previous systems, especially services that depend on data contents. We extensively evaluate Sego's performance on real workloads and implement a kernel fault injector to validate Sego's file system-agnostic crash consistency and recovery protocol.
Smart Spaces are composed of heterogeneous sensors and devices that collect and share information. This information may contain personal information of the users. Thus, securing the data and preserving the privacy are of paramount importance. In this paper, we propose techniques for information security and privacy protection for Smart Spaces based on the Smart-M3 platform. We propose a) a security framework, and b) a context-aware role-based access control scheme. We model our access control scheme using ontological techniques and Web Ontology Language (OWL), and implement it via CLIPS rules. To evaluate the efficiency of our access control scheme, we measure the time it takes to check the access rights of the access requests. The results demonstrate that the highest response time is approximately 0.2 seconds in a set of 100000 triples. We conclude that the proposed access control scheme produces low overhead and is therefore, an efficient approach for Smart Spaces.
The average computer user is no longer restricted to one device. They may have several devices and expect their applications to work on all of them. A challenge arises when these applications need the cryptographic private key of the devices' owner. Here the device owner typically has to manage keys manually with a "keychain" app, which leads to private keys being transferred insecurely between devices – or even to other people. Even with intuitive synchronization mechanisms, theft and malware still pose a major risk to keys. Phones and watches are frequently removed or set down, and a single compromised device leads to the loss of the owner's private key, a catastrophic failure that can be quite difficult to recover from. We introduce Shatter, an open-source framework that runs on desktops, Android, and Android Wear, and performs key distribution on a user's behalf. Shatter uses threshold cryptography to turn the security weakness of having multiple devices into a strength. Apps that delegate cryptographic operations to Shatter have their keys compromised only when a threshold number of devices are compromised by the same attacker. We demonstrate how our framework operates with two popular Android apps (protecting identity keys for a messaging app, and encryption keys for a note-taking app) in a backwards-compatible manner: only Shatter users need to move to a Shatter-aware version of the app. Shatter has minimal impact on app performance, with signatures and decryption being calculated in 0.5s and security proofs in 14s.
We introduce a model for differentially private analysis of weighted graphs in which the graph topology (υ,ε) is assumed to be public and the private information consists only of the edge weights ω : ε → R+. This can express hiding congestion patterns in a known system of roads. Differential privacy requires that the output of an algorithm provides little advantage, measured by privacy parameters ε and δ, for distinguishing between neighboring inputs, which are thought of as inputs that differ on the contribution of one individual. In our model, two weight functions w,w' are considered to be neighboring if they have l1 distance at most one. We study the problems of privately releasing a short path between a pair of vertices and of privately releasing approximate distances between all pairs of vertices. We are concerned with the approximation error, the difference between the length of the released path or released distance and the length of the shortest path or actual distance. For the problem of privately releasing a short path between a pair of vertices, we prove a lower bound of Ω(textbarυtextbar) on the additive approximation error for fixed privacy parameters ε,δ. We provide a differentially private algorithm that matches this error bound up to a logarithmic factor and releases paths between all pairs of vertices, not just a single pair. The approximation error achieved by our algorithm can be bounded by the number of edges on the shortest path, so we achieve better accuracy than the worst-case bound for pairs of vertices that are connected by a low-weight path consisting of o(textbarυtextbar) vertices. For the problem of privately releasing all-pairs distances, we show that for trees we can release all-pairs distances with approximation error \$O(log2.5textbarυtextbar) for fixed privacy parameters. For arbitrary bounded-weight graphs with edge weights in [0,M] we can brelease all distances with approximation error Õ(√textgreater(textbarυtextbarM).
This paper proposes a novel measure for edge significance considering quantity propagation in a graph. Our method utilizes a pseudo propagation process brought by solving a problem of a load balancing on nodes. Edge significance is defined as a difference of propagation in a graph with an edge to without it. The simulation compares our proposed method with the traditional betweenness centrality in order to obtain differences of our measure to a type of centrality, which considers propagation process in a graph.
Cloud computing is rapidly reshaping the server administration landscape. The widespread use of virtualization and the increasingly high server consolidation ratios, in particular, have introduced unprecedented security challenges for users, increasing the exposure to intrusions and opening up new opportunities for attacks. Deploying security mechanisms in the hypervisor to detect and stop intrusion attempts is a promising strategy to address this problem. Existing hypervisor-based solutions, however, are typically limited to very specific classes of attacks and introduce exceedingly high performance overhead for production use. In this paper, we present Slick (Storage-Level Intrusion ChecKer), an intrusion detection system (IDS) for virtualized storage devices. Slick detects intrusion attempts by efficiently and transparently monitoring write accesses to critical regions on storage devices. The low-overhead monitoring component operates entirely inside the hypervisor, with no introspection or modifications required in the guest VMs. Using Slick, users can deploy generic IDS rules to detect a broad range of real-world intrusions in a flexible and practical way. Experimental results confirm that Slick is effective at enhancing the security of virtualized servers, while imposing less than 5% overhead in production.
Providing a global understanding of privacy is crucial, because everything is connected. Nowadays companies are providing their customers with more services that will give them more access to their data and daily activity; electricity companies are marketing the new smart meters as a new service with great benefit to reduce the electricity usage by monitoring the electricity reading in real time. Although the users might benefit from this extra service, it will compromise the privacy of the users by having constant access to the readings. Since the smart meters will provide the users with real electricity readings, they will be able to decide and identify which devices are consuming energy in that specific moment and how much it will cost. This kind of information can be exploited by numerous types of people. Unauthorized use of this information is an invasion of privacy and may lead to much more severe consequences. This paper will propose an algorithm approach for the comparison and analysis of Smart Meter data readings, considering the time and temperature factors at each second to identify the use patterns at each house by identifying the appliances activities at each second in time complexity O(log(m)).
Wearable devices, such as smartwatches, are furnished with state-of-the-art sensors that enable a range of context-aware applications. However, malicious applications can misuse these sensors, if access is left unaudited. In this paper, we demonstrate how applications that have access to motion or inertial sensor data on a modern smartwatch can recover text typed on an external QWERTY keyboard. Due to the distinct nature of the perceptible motion sensor data, earlier research efforts on emanation based keystroke inference attacks are not readily applicable in this scenario. The proposed novel attack framework characterizes wrist movements (captured by the inertial sensors of the smartwatch worn on the wrist) observed during typing, based on the relative physical position of keys and the direction of transition between pairs of keys. Eavesdropped keystroke characteristics are then matched to candidate words in a dictionary. Multiple evaluations show that our keystroke inference framework has an alarmingly high classification accuracy and word recovery rate. With the information recovered from the wrist movements perceptible by a smartwatch, we exemplify the risks associated with unaudited access to seemingly innocuous sensors (e.g., accelerometers and gyroscopes) of wearable devices. As part of our efforts towards preventing such side-channel attacks, we also develop and evaluate a novel context-aware protection framework which can be used to automatically disable (or downgrade) access to motion sensors, whenever typing activity is detected.
Security testing is a pivotal activity in engineering secure software. It consists of two phases: generating attack inputs to test the system, and assessing whether test executions expose any vulnerabilities. The latter phase is known as the security oracle problem. In this work, we present SOFIA, a Security Oracle for SQL-Injection Vulnerabilities. SOFIA is programming-language and source-code independent, and can be used with various attack generation tools. Moreover, because it does not rely on known attacks for learning, SOFIA is meant to also detect types of SQLi attacks that might be unknown at learning time. The oracle challenge is recast as a one-class classification problem where we learn to characterise legitimate SQL statements to accurately distinguish them from SQLi attack statements. We have carried out an experimental validation on six applications, among which two are large and widely-used. SOFIA was used to detect real SQLi vulnerabilities with inputs generated by three attack generation tools. The obtained results show that SOFIA is computationally fast and achieves a recall rate of 100% (i.e., missing no attacks) with a low false positive rate (0.6%).
This paper presents SplitBox, an efficient system for privacy-preserving processing of network functions that are outsourced as software processes to the cloud. Specifically, cloud providers processing the network functions do not learn the network policies instructing how the functions are to be processed. First, we propose an abstract model of a generic network function based on match-action pairs. We assume that this function is processed in a distributed manner by multiple honest-but-curious cloud service providers. Then, we introduce our SplitBox system for private network function virtualization and present a proof-of-concept implementation on FastClick, an extension of the Click modular router, using a firewall as a use case. Our experimental results achieve a throughput of over 2 Gbps with 1 kB-sized packets on average, traversing up to 60 firewall rules.
Complex simulations and numerical experiments typically rely on a number of parameters and have an associated score function, e.g. with the goal of maximizing accuracy or minimizing computation time. However, the influence of each individual parameter is often poorly understood a priori and the joint parameter space can be difficult to explore, visualize and optimize. We model this space as an N-dimensional black-box tensor and apply a cross approximation strategy to sample it. Upon learning and compactly expressing this space as a surrogate visualization model, informative subspaces are interactively reconstructed and navigated in the form of charts, images, surface plots, etc. By exploiting efficient operations in the tensor train format, we are able to produce diagrams such as parallel coordinates, bivariate projections and dimensional stacking out of highly-compressed parameter spaces. We demonstrate the proposed framework with several scientific simulations that contain up to 6 parameters and billions of tensor grid points.
In this paper, we have mentioned a method to find the performance of projectwhich detects various web - attacks. The project is capable to identifying and preventing attacks like SQL Injection, Cross – Site Scripting, URL rewriting, Web server 400 error code etc. The performance of system is detected using the system attributes that are mentioned in this paper. This is also used to determine efficiency of the system.
Anonymous communication systems are vulnerable to long term passive "intersection attacks". Not all users of an anonymous communication system will be online at the same time, this leaks some information about who is talking to who. A global passive adversary observing all communications can learn the set of potential recipients of a message with more and more confidence over time. Nearly all deployed anonymous communication tools offer no protection against such attacks. In this work, we introduce TASP, a protocol used by an anonymous communication system that mitigates intersection attacks by intelligently grouping clients together into anonymity sets. We find that with a bandwidth overhead of just 8% we can dramatically extend the time necessary to perform a successful intersection attack.
Securely pairing wearables with another device is the key to many promising applications, such as mobile payment, sensitive data transfer and secure interactions with smart home devices. This paper presents Touch-And-Guard (TAG), a system that uses hand touch as an intuitive manner to establish a secure connection between a wristband wearable and the touched device. It generates secret bits from hand resonant properties, which are obtained using accelerometers and vibration motors. The extracted secret bits are used by both sides to authenticate each other and then communicate confidentially. The ubiquity of accelerometers and motors presents an immediate market for our system. We demonstrate the feasibility of our system using an experimental prototype and conduct experiments involving 12 participants with 1440 trials. The results indicate that we can generate secret bits at a rate of 7.84 bit/s, which is 58% faster than conventional text input PIN authentication. We also show that our system is resistant to acoustic eavesdroppers in proximity.
The widespread adoption of Location-Based Services (LBSs) has come with controversy about privacy. While leveraging location information leads to improving services through geo-contextualization, it rises privacy concerns as new knowledge can be inferred from location records, such as home/work places, habits or religious beliefs. To overcome this problem, several Location Privacy Protection Mechanisms (LPPMs) have been proposed in the literature these last years. However, every mechanism comes with its own configuration parameters that directly impact the privacy guarantees and the resulting utility of protected data. In this context, it can be difficult for a non-expert system designer to choose appropriate configuration parameters to use according to the expected privacy and utility. In this paper, we present a framework enabling the easy configuration of LPPMs. To achieve that, our framework performs an offline, in-depth automated analysis of LPPMs to provide the formal relationship between their configuration parameters and both privacy and the utility metrics. This framework is modular: by using different metrics, a system designer is able to fine-tune her LPPM according to her expected privacy and utility guarantees (i.e., the guarantee itself and the level of this guarantee). To illustrate the capability of our framework, we analyse Geo-Indistinguishability (a well known differentially private LPPM) and we provide the formal relationship between its &epsis; configuration parameter and two privacy and utility metrics.
Machine-based tracking is a type of behavior that extracts information on a user's machine, which can then be used for fingerprinting, tracking, or profiling purposes. In this paper, we focus on JavaScript-oriented machine-based tracking as JavaScript is widely accessible in all browsers. We find that coarse features related to JavaScript access, cookie access, and URL length subdomain information can perform well in creating a classifier that can identify these machine-based trackers with 97.7% accuracy. We then use the classifier on real-world datasets based on 30-minute website crawls of different types of websites – including websites that target children and websites that target a popular audience – and find 85%+ of all websites utilize machine-based tracking, even when they target a regulated group (children) as their primary audience.
Traditionally, network and system configurations are static. Attackers have plenty of time to exploit the system's vulnerabilities and thus they are able to choose when to launch attacks wisely to maximize the damage. An unpredictable system configuration can significantly lift the bar for attackers to conduct successful attacks. Recent years, moving target defense (MTD) has been advocated for this purpose. An MTD mechanism aims to introduce dynamics to the system through changing its configuration continuously over time, which we call adaptations. Though promising, the dynamic system reconfiguration introduces overhead to the applications currently running in the system. It is critical to determine the right time to conduct adaptations and to balance the overhead afforded and the security levels guaranteed. This problem is known as the MTD timing problem. Little prior work has been done to investigate the right time in making adaptations. In this paper, we take the first step to both theoretically and experimentally study the timing problem in moving target defenses. For a broad family of attacks including DDoS attacks and cloud covert channel attacks, we model this problem as a renewal reward process and propose an optimal algorithm in deciding the right time to make adaptations with the objective of minimizing the long-term cost rate. In our experiments, both DDoS attacks and cloud covert channel attacks are studied. Simulations based on real network traffic traces are conducted and we demonstrate that our proposed algorithm outperforms known adaptation schemes.