Visible to the public Biblio

Found 4059 results

Filters: Keyword is Resiliency  [Clear All Filters]
Afshari, Mehrdad, Su, Zhendong.  2016.  Building White-box Abstractions by Program Refinement. Proceedings of the 2016 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software. :74–81.

Abstractions make building complex systems possible. Many facilities provided by a modern programming language are directly designed to build a certain style of abstraction. Abstractions also aim to enhance code reusability, thus enhancing programmer productivity and effectiveness. Real-world software systems can grow to have a complicated hierarchy of abstractions. Often, the hierarchy grows unnecessarily deep, because the programmers have envisioned the most generic use cases for a piece of code to make it reusable. Sometimes, the abstractions used in the program are not the appropriate ones, and it would be simpler for the higher level client to circumvent such abstractions. Another problem is the impedance mismatch between different pieces of code or libraries coming from different projects that are not designed to work together. Interoperability between such libraries are often hindered by abstractions, by design, in the name of hiding implementation details and encapsulation. These problems necessitate forms of abstraction that are easy to manipulate if needed. In this paper, we describe a powerful mechanism to create white-box abstractions, that encourage flatter hierarchies of abstraction and ease of manipulation and customization when necessary: program refinement. In so doing, we rely on the basic principle that writing directly in the host programming language is as least restrictive as one can get in terms of expressiveness, and allow the programmer to reuse and customize existing code snippets to address their specific needs.

Shi, Yang, Wei, Wujing, He, Zongjian, Fan, Hongfei.  2016.  An Ultra-lightweight White-box Encryption Scheme for Securing Resource-constrained IoT Devices. Proceedings of the 32Nd Annual Conference on Computer Security Applications. :16–29.

Embedded devices with constrained computational resources, such as wireless sensor network nodes, electronic tag readers, roadside units in vehicular networks, and smart watches and wristbands, are widely used in the Internet of Things. Many of such devices are deployed in untrustable environments, and others may be easy to lose, leading to possible capture by adversaries. Accordingly, in the context of security research, these devices are running in the white-box attack context, where the adversary may have total visibility of the implementation of the built-in cryptosystem with full control over its execution. It is undoubtedly a significant challenge to deal with attacks from a powerful adversary in white-box attack contexts. Existing encryption algorithms for white-box attack contexts typically require large memory use, varying from one to dozens of megabytes, and thus are not suitable for resource-constrained devices. As a countermeasure in such circumstances, we propose an ultra-lightweight encryption scheme for protecting the confidentiality of data in white-box attack contexts. The encryption is executed with secret components specialized for resource-constrained devices against white-box attacks, and the encryption algorithm requires a relatively small amount of static data, ranging from 48 to 92 KB. The security and efficiency of the proposed scheme have been theoretically analyzed with positive results, and experimental evaluations have indicated that the scheme satisfies the resource constraints in terms of limited memory use and low computational cost.

Lou, Jian, Vorobeychik, Yevgeniy.  2016.  Decentralization and Security in Dynamic Traffic Light Control. Proceedings of the Symposium and Bootcamp on the Science of Security. :90–92.

Complex traffic networks include a number of controlled intersections, and, commonly, multiple districts or municipalities. The result is that the overall traffic control problem is extremely complex computationally. Moreover, given that different municipalities may have distinct, non-aligned, interests, traffic light controller design is inherently decentralized, a consideration that is almost entirely absent from related literature. Both complexity and decentralization have great bearing both on the quality of the traffic network overall, as well as on its security. We consider both of these issues in a dynamic traffic network. First, we propose an effective local search algorithm to efficiently design system-wide control logic for a collection of intersections. Second, we propose a game theoretic (Stackelberg game) model of traffic network security in which an attacker can deploy denial-of-service attacks on sensors, and develop a resilient control algorithm to mitigate such threats. Finally, we propose a game theoretic model of decentralization, and investigate this model both in the context of baseline traffic network design, as well as resilient design accounting for attacks. Our methods are implemented and evaluated using a simple traffic network scenario in SUMO.

Hasegawa, Toru, Tara, Yasutaka, Ryu, Kai, Koizumi, Yuki.  2016.  Emergency Message Delivery Mechanism in NDN Networks. Proceedings of the 3rd ACM Conference on Information-Centric Networking. :199–200.

Emergency message delivery in packet networks is promising in terms of resiliency to failures and service delivery to handicapped persons. In this paper, we propose an NDN(Named Data Networking)-based emergency message delivery mechanism by leveraging multicasting and ABE (Attribute-Based Encryption) functions.

Rajabi, Arezoo, Bobba, Rakesh B..  2016.  A Resilient Algorithm for Power System Mode Estimation Using Synchrophasors. Proceedings of the 2Nd Annual Industrial Control System Security Workshop. :23–29.

Bulk electric systems include hundreds of synchronous generators. Faults in such systems can induce oscillations in the generators which if not detected and controlled can destabilize the system. Mode estimation is a popular method for oscillation detection. In this paper, we propose a resilient algorithm to estimate electro-mechanical oscillation modes in large scale power system in the presence of false data. In particular, we add a fault tolerance mechanism to a variant of alternating direction method of multipliers (ADMM) called S-ADMM. We evaluate our method on an IEEE 68-bus test system under different attack scenarios and show that in all the scenarios our algorithm converges well.

Chlela, Martine, Joos, Geza, Kassouf, Marthe.  2016.  Impact of Cyber-attacks on Islanded Microgrid Operation. Proceedings of the Workshop on Communications, Computation and Control for Resilient Smart Energy Systems. :1:1–1:5.

The prevalent integration of highly intermittent renewable distributed energy resources (DER) into microgrids necessitates the deployment of a microgrid controller. In the absence of the main electric grid setting the network voltage and frequency, the microgrid power and energy management becomes more challenging, accentuating the need for a centralized microgrid controller that, through communication links, ensures smooth operation of the autonomous system. This extensive reliance on information and communication technologies (ICT) creates potential access points and vulnerabilities that may be exploited by cyber-attackers. This paper first presents a typical microgrid configuration operating in islanded mode; the microgrid elements, primary and secondary control functions for power, energy and load management are defined. The information transferred from the central controller to coordinate and dispatch the DERs is provided along with the deployable communication technologies and protocols. The vulnerabilities arising in such microgrids along with the cyber-attacks exploiting them are described. The impact of these attacks on the microgrid controller functions was shown to be dependent on the characteristics, location and target of the cyber-attack, as well as the microgrid configuration and control. A real-time hardware-in-the loop (HIL) testing platform, which emulates a microgrid featuring renewable DERs, an energy storage system (ESS), a diesel generator and controllable loads was used as the case study in order to demonstrate the impact of various cyber-attacks.

Ibrahim, Ahmad, Sadeghi, Ahmad-Reza, Tsudik, Gene, Zeitouni, Shaza.  2016.  DARPA: Device Attestation Resilient to Physical Attacks. Proceedings of the 9th ACM Conference on Security & Privacy in Wireless and Mobile Networks. :171–182.

As embedded devices (under the guise of "smart-whatever") rapidly proliferate into many domains, they become attractive targets for malware. Protecting them from software and physical attacks becomes both important and challenging. Remote attestation is a basic tool for mitigating such attacks. It allows a trusted party (verifier) to remotely assess software integrity of a remote, untrusted, and possibly compromised, embedded device (prover). Prior remote attestation methods focus on software (malware) attacks in a one-verifier/one-prover setting. Physical attacks on provers are generally ruled out as being either unrealistic or impossible to mitigate. In this paper, we argue that physical attacks must be considered, particularly, in the context of many provers, e.g., a network, of devices. As- suming that physical attacks require capture and subsequent temporary disablement of the victim device(s), we propose DARPA, a light-weight protocol that takes advantage of absence detection to identify suspected devices. DARPA is resilient against a very strong adversary and imposes minimal additional hardware requirements. We justify and identify DARPA's design goals and evaluate its security and costs.

Ghosh, Uttam, Dong, Xinshu, Tan, Rui, Kalbarczyk, Zbigniew, Yau, David K.Y., Iyer, Ravishankar K..  2016.  A Simulation Study on Smart Grid Resilience Under Software-Defined Networking Controller Failures. Proceedings of the 2Nd ACM International Workshop on Cyber-Physical System Security. :52–58.

Riding on the success of SDN for enterprise and data center networks, recently researchers have shown much interest in applying SDN for critical infrastructures. A key concern, however, is the vulnerability of the SDN controller as a single point of failure. In this paper, we develop a cyber-physical simulation platform that interconnects Mininet (an SDN emulator), hardware SDN switches, and PowerWorld (a high-fidelity, industry-strength power grid simulator). We report initial experiments on how a number of representative controller faults may impact the delay of smart grid communications. We further evaluate how this delay may affect the performance of the underlying physical system, namely automatic gain control (AGC) as a fundamental closed-loop control that regulates the grid frequency to a critical nominal value. Our results show that when the fault-induced delay reaches seconds (e.g., more than four seconds in some of our experiments), degradation of the AGC becomes evident. Particularly, the AGC is most vulnerable when it is in a transient following say step changes in loading, because the significant state fluctuations will exacerbate the effects of using a stale system state in the control.

Nicol, David M., Kumar, Rakesh.  2016.  Efficient Monte Carlo Evaluation of SDN Resiliency. Proceedings of the 2016 Annual ACM Conference on SIGSIM Principles of Advanced Discrete Simulation. :143–152.

Software defined networking (SDN) is an emerging technology for controlling flows through networks. Used in the context of industrial control systems, an objective is to design configurations that have built-in protection for hardware failures in the sense that the configuration has "baked-in" back-up routes. The objective is to leave the configuration static as long as possible, minimizing the need to have the controller push in new routing and filtering rules We have designed and implemented a tool that enables us to determine the complete connectivity map from an analysis of all switch configurations in the network. We can use this tool to explore the impact of a link failure, in particular to determine whether the failure induces loss of the ability to deliver a flow even after the built-in back-up routes are used. A measure of the original configuration's resilience to link failure is the mean number of link failures required to induce the first such loss of service. The computational cost of each link failure and subsequent analysis is large, so there is much to be gained by reducing the overall cost of obtaining a statistically valid estimate of resiliency. This paper shows that when analysis of a network state can identify all as-yet-unfailed links any one of whose failure would induce loss of a flow, then we can use the technique of importance sampling to estimate the mean number of links required to fail before some flow is lost, and analyze the potential for reducing the variance of the sample statistic. We provide both theoretical and empirical evidence for significant variance reduction.

Nisha, Dave, M..  2016.  Storage as a parameter for classifying dynamic key management schemes proposed for WSNs. 2016 International Conference on Computational Techniques in Information and Communication Technologies (ICCTICT). :51–56.

Real world applications of Wireless Sensor Networks such as border control, healthcare monitoring and target tracking require secure communications. Thus, during WSN setup, one of the first requirements is to distribute the keys to the sensor nodes which can be later used for securing the messages exchanged between sensors. The key management schemes in WSN secure the communication between a pair or a group of nodes. However, the storage capacity of the sensor nodes is limited which makes storage requirement as an important parameter for the evaluation of key management schemes. This paper classifies the existing key management schemes proposed for WSNs into three categories: storage inefficient, storage efficient and highly storage efficient key management schemes.

Kosek, A. M..  2016.  Contextual anomaly detection for cyber-physical security in Smart Grids based on an artificial neural network model. 2016 Joint Workshop on Cyber- Physical Security and Resilience in Smart Grids (CPSR-SG). :1–6.

This paper presents a contextual anomaly detection method and its use in the discovery of malicious voltage control actions in the low voltage distribution grid. The model-based anomaly detection uses an artificial neural network model to identify a distributed energy resource's behaviour under control. An intrusion detection system observes distributed energy resource's behaviour, control actions and the power system impact, and is tested together with an ongoing voltage control attack in a co-simulation set-up. The simulation results obtained with a real photovoltaic rooftop power plant data show that the contextual anomaly detection performs on average 55% better in the control detection and over 56% better in the malicious control detection over the point anomaly detection.

Sze, Wai Kit, Srivastava, Abhinav, Sekar, R..  2016.  Hardening OpenStack Cloud Platforms Against Compute Node Compromises. Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security. :341–352.

Infrastructure-as-a-Service (IaaS) clouds such as OpenStack consist of two kinds of nodes in their infrastructure: control nodes and compute nodes. While control nodes run all critical services, compute nodes host virtual machines of customers. Given the large number of compute nodes, and the fact that they are hosting VMs of (possibly malicious) customers, it is possible that some of the compute nodes may be compromised. This paper examines the impact of such a compromise. We focus on OpenStack, a popular open-source cloud plat- form that is widely adopted. We show that attackers com- promising a single compute node can extend their controls over the entire cloud infrastructure. They can then gain free access to resources that they have not paid for, or even bring down the whole cloud to affect all customers. This startling result stems from the cloud platform's misplaced trust, which does not match today's threats. To overcome the weakness, we propose a new system, called SOS , for hardening OpenStack. SOS limits trust on compute nodes. SOS consists of a framework that can enforce a wide range of security policies. Specifically, we applied mandatory access control and capabilities to con- fine interactions among different components. Effective confinement policies are generated automatically. Furthermore, SOS requires no modifications to the OpenStack. This has allowed us to deploy SOS on multiple versions of OpenStack. Our experimental results demonstrate that SOS is scalable, incurs negligible overheads and offers strong protection.

Zhang, Jun, Xiao, Xiaokui, Xie, Xing.  2016.  PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions. Proceedings of the 2016 International Conference on Management of Data. :155–170.

Given a set D of tuples defined on a domain Omega, we study differentially private algorithms for constructing a histogram over Omega to approximate the tuple distribution in D. Existing solutions for the problem mostly adopt a hierarchical decomposition approach, which recursively splits Omega into sub-domains and computes a noisy tuple count for each sub-domain, until all noisy counts are below a certain threshold. This approach, however, requires that we (i) impose a limit h on the recursion depth in the splitting of Omega and (ii) set the noise in each count to be proportional to h. The choice of h is a serious dilemma: a small h makes the resulting histogram too coarse-grained, while a large h leads to excessive noise in the tuple counts used in deciding whether sub-domains should be split. Furthermore, h cannot be directly tuned based on D; otherwise, the choice of h itself reveals private information and violates differential privacy. To remedy the deficiency of existing solutions, we present PrivTree, a histogram construction algorithm that adopts hierarchical decomposition but completely eliminates the dependency on a pre-defined h. The core of PrivTree is a novel mechanism that (i) exploits a new analysis on the Laplace distribution and (ii) enables us to use only a constant amount of noise in deciding whether a sub-domain should be split, without worrying about the recursion depth of splitting. We demonstrate the application of PrivTree in modelling spatial data, and show that it can be extended to handle sequence data (where the decision in sub-domain splitting is not based on tuple counts but a more sophisticated measure). Our experiments on a variety of real datasets show that PrivTree considerably outperforms the states of the art in terms of data utility.

Phull, Sona, Som, Subhranil.  2016.  Symmetric Cryptography Using Multiple Access Circular Queues (MACQ). Proceedings of the Second International Conference on Information and Communication Technology for Competitive Strategies. :107:1–107:6.

In order to provide secure data communication in present cyber space world, a stronger encryption technique becomes a necessity that can help people to protect their sensitive information from cryptanalyst. This paper proposes a novel symmetric block cipher algorithm that uses multiple access circular queues (MACQs) of variable lengths for diffusion of information to a greater extent. The keys are randomly generated and will be of variable lengths depending upon the size of each MACQ.A number of iterations of circular rotations, swapping of elements and XORing the key with queue elements are performed on each MACQ. S-box is used so that the relationship between the key and the cipher text remains indeterminate or obscure. These operations together will help in transforming the cipher into a much more complex and secure block cipher. This paper attempt to propose an encryption algorithm that is secure and fast.

Schwichtenberg, Simon, Engels, Gregor.  2016.  Automatized Derivation of Comprehensive Specifications for Black-box Services. Proceedings of the 38th International Conference on Software Engineering Companion. :815–818.

Today, cloud vendors host third party black-box services, whose developers usually provide only textual descriptions or purely syntactical interface specifications. Cloud vendors that give substantial support to other third party developers to integrate hosted services into new software solutions would have a unique selling feature over their competitors. However, to reliably determine if a service is reusable, comprehensive service specifications are needed. Characteristic for comprehensive in contrast to syntactical specifications are the formalization of ontological and behavioral semantics, homogeneity according to a global ontology, and a service grounding that links the abstract service description and its technical realization. Homogeneous, semantical specifications enable to reliably identify reusable services, whereas the service grounding is needed for the technical service integration. In general, comprehensive specifications are not available and have to be derived. Existing automatized approaches are restricted to certain characteristics of comprehensiveness. In my PhD, I consider an automatized approach to derive fully-fledged comprehensive specifications for black-box services. Ontological semantics are derived from syntactical interface specifications. Behavioral semantics are mined from call logs that cloud vendors create to monitor the hosted services. The specifications are harmonized over a global ontology. The service grounding is established using traceability information. The approach enables third party developers to compose services into complex systems and creates new sales channels for cloud and service providers.

Argyros, George, Stais, Ioannis, Jana, Suman, Keromytis, Angelos D., Kiayias, Aggelos.  2016.  SFADiff: Automated Evasion Attacks and Fingerprinting Using Black-box Differential Automata Learning. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. :1690–1701.

Finding differences between programs with similar functionality is an important security problem as such differences can be used for fingerprinting or creating evasion attacks against security software like Web Application Firewalls (WAFs) which are designed to detect malicious inputs to web applications. In this paper, we present SFADIFF, a black-box differential testing framework based on Symbolic Finite Automata (SFA) learning. SFADIFF can automatically find differences between a set of programs with comparable functionality. Unlike existing differential testing techniques, instead of searching for each difference individually, SFADIFF infers SFA models of the target programs using black-box queries and systematically enumerates the differences between the inferred SFA models. All differences between the inferred models are checked against the corresponding programs. Any difference between the models, that does not result in a difference between the corresponding programs, is used as a counterexample for further refinement of the inferred models. SFADIFF's model-based approach, unlike existing differential testing tools, also support fully automated root cause analysis in a domain-independent manner. We evaluate SFADIFF in three different settings for finding discrepancies between: (i) three TCP implementations, (ii) four WAFs, and (iii) HTML/JavaScript parsing implementations in WAFs and web browsers. Our results demonstrate that SFADIFF is able to identify and enumerate the differences systematically and efficiently in all these settings. We show that SFADIFF is able to find differences not only between different WAFs but also between different versions of the same WAF. SFADIFF is also able to discover three previously-unknown differences between the HTML/JavaScript parsers of two popular WAFs (PHPIDS 0.7 and Expose 2.4.0) and the corresponding parsers of Google Chrome, Firefox, Safari, and Internet Explorer. We confirm that all these differences can be used to evade the WAFs and launch successful cross-site scripting attacks.

Eberly, Wayne.  2016.  Selecting Algorithms for Black Box Matrices: Checking For Matrix Properties That Can Simplify Computations. Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. :207–214.

Processes to automate the selection of appropriate algorithms for various matrix computations are described. In particular, processes to check for, and certify, various matrix properties of black-box matrices are presented. These include sparsity patterns and structural properties that allow "superfast" algorithms to be used in place of black-box algorithms. Matrix properties that hold generically, and allow the use of matrix preconditioning to be reduced or eliminated, can also be checked for and certified –- notably including in the small-field case, where this presently has the greatest impact on the efficiency of the computation.

Batselier, Kim, Chen, Zhongming, Liu, Haotian, Wong, Ngai.  2016.  A Tensor-based Volterra Series Black-box Nonlinear System Identification and Simulation Framework. Proceedings of the 35th International Conference on Computer-Aided Design. :17:1–17:7.

Tensors are a multi-linear generalization of matrices to their d-way counterparts, and are receiving intense interest recently due to their natural representation of high-dimensional data and the availability of fast tensor decomposition algorithms. Given the input-output data of a nonlinear system/circuit, this paper presents a nonlinear model identification and simulation framework built on top of Volterra series and its seamless integration with tensor arithmetic. By exploiting partially-symmetric polyadic decompositions of sparse Toeplitz tensors, the proposed framework permits a pleasantly scalable way to incorporate high-order Volterra kernels. Such an approach largely eludes the curse of dimensionality and allows computationally fast modeling and simulation beyond weakly nonlinear systems. The black-box nature of the model also hides structural information of the system/circuit and encapsulates it in terms of compact tensors. Numerical examples are given to verify the efficacy, efficiency and generality of this tensor-based modeling and simulation framework.

Doerr, Carola, Lengler, Johannes.  2016.  The (1+1) Elitist Black-Box Complexity of LeadingOnes. Proceedings of the Genetic and Evolutionary Computation Conference 2016. :1131–1138.

One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us understand how algorithmic choices such as the population size, the variation operators, or the selection rules influence the optimization time. One example for such a result is the Ω(n log n) lower bound for unary unbiased algorithms on functions with a unique global optimum [Lehre/Witt, GECCO 2010], which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, almost no non-trivial bounds are known for other restricted models. Proving such bounds therefore remains to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of LeadingOnes and prove that its (1+1) elitist black-box complexity is Ω(n2), a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of LeadingOnes is thus considerably larger than its unrestricted one, which is known to be of order n log log n [Afshani et al., 2013].

Bagnères, Lénaïc, Zinenko, Oleksandr, Huot, Stéphane, Bastoul, Cédric.  2016.  Opening Polyhedral Compiler's Black Box. Proceedings of the 2016 International Symposium on Code Generation and Optimization. :128–138.

While compilers offer a fair trade-off between productivity and executable performance in single-threaded execution, their optimizations remain fragile when addressing compute-intensive code for parallel architectures with deep memory hierarchies. Moreover, these optimizations operate as black boxes, impenetrable for the user, leaving them with no alternative to time-consuming and error-prone manual optimization in cases where an imprecise cost model or a weak analysis resulted in a bad optimization decision. To address this issue, we propose a technique allowing to automatically translate an arbitrary polyhedral optimization, used internally by loop-level optimization frameworks of several modern compilers, into a sequence of comprehensible syntactic transformations as long as this optimization focuses on scheduling loop iterations. This approach opens the black box of the polyhedral frameworks enabling users to examine, refine, replay and even design complex optimizations semi-automatically in partnership with the compiler.

Natanzon, Assaf, Winokur, Alex, Bachmat, Eitan.  2016.  Black Box Replication: Breaking the Latency Limits. Proceedings of the 9th ACM International on Systems and Storage Conference. :9:1–9:9.

Synchronous replication is critical for today's enterprise IT organization. It is mandatory by regulation in several countries for some types of organizations, including banks and insurance companies. The technology has been available for a long period of time, but due to speed of light and maximal latency limitations, it is usually limited to a distance of 50-100 miles. Flight data recorders, also known as black boxes, have long been used to record the last actions which happened in airplanes at times of disasters. We present an integration between an Enterprise Data Recorder and an asynchronous replication mechanism, which allows breaking the functional limits that light speed imposes on synchronous replication.

Doerr, Benjamin, Doerr, Carola, Yang, Jing.  2016.  Optimal Parameter Choices via Precise Black-Box Analysis. Proceedings of the Genetic and Evolutionary Computation Conference 2016. :1123–1130.

In classical runtime analysis it has been observed that certain working principles of an evolutionary algorithm cannot be understood by only looking at the asymptotic order of the runtime, but that more precise estimates are needed. In this work we demonstrate that the same observation applies to black-box complexity analysis. We prove that the unary unbiased black-box complexity of the classic OneMax function class is n ln(n) – cn ± o(n) for a constant c between 0.2539 and 0.2665. Our analysis yields a simple (1+1)-type algorithm achieving this runtime bound via a fitness-dependent mutation strength. When translated into a fixed-budget perspective, our algorithm with the same budget computes a solution that asymptotically is 13% closer to the optimum (given that the budget is at least 0.2675n).

Buzdalov, Maxim.  2016.  An Algorithm for Computing Lower Bounds for Unrestricted Black-Box Complexities. Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion. :147–148.

Finding and proving lower bounds on black-box complexities is one of the hardest problems in theory of randomized search heuristics. Until recently, there were no general ways of doing this, except for information theoretic arguments similar to the one of Droste, Jansen and Wegener. In a recent paper by Buzdalov, Kever and Doerr, a theorem is proven which may yield tighter bounds on unrestricted black-box complexity using certain problem-specific information. To use this theorem, one should split the search process into a finite number of states, describe transitions between states, and for each state specify (and prove) the maximum number of different answers to any query. We augment these state constraints by one more kind of constraints on states, namely, the maximum number of different currently possible optima. An algorithm is presented for computing the lower bounds based on these constraints. We also empirically show improved lower bounds on black-box complexity of OneMax and Mastermind.

Hahn, Florian, Kerschbaum, Florian.  2016.  Poly-Logarithmic Range Queries on Encrypted Data with Small Leakage. Proceedings of the 2016 ACM on Cloud Computing Security Workshop. :23–34.

Privacy-preserving range queries allow encrypting data while still enabling queries on ciphertexts if their corresponding plaintexts fall within a requested range. This provides a data owner the possibility to outsource data collections to a cloud service provider without sacrificing privacy nor losing functionality of filtering this data. However, existing methods for range queries either leak additional information (like the ordering of the complete data set) or slow down the search process tremendously by requiring to query each ciphertext in the data collection. We present a novel scheme that only leaks the access pattern while supporting amortized poly-logarithmic search time. Our construction is based on the novel idea of enabling the cloud service provider to compare requested range queries. By doing so, the cloud service provider can use the access pattern to speed-up search time for range queries in the future. On the one hand, values that have fallen within a queried range, are stored in an interactively built index for future requests. On the other hand, values that have not been queried do not leak any information to the cloud service provider and stay perfectly secure. In order to show its practicability we have implemented our scheme and give a detailed runtime evaluation.

Karbab, ElMouatez Billah, Debbabi, Mourad, Derhab, Abdelouahid, Mouheb, Djedjiga.  2016.  Cypider: Building Community-based Cyber-defense Infrastructure for Android Malware Detection. Proceedings of the 32Nd Annual Conference on Computer Security Applications. :348–362.

The popularity of Android OS has dramatically increased malware apps targeting this mobile OS. The daily amount of malware has overwhelmed the detection process. This fact has motivated the need for developing malware detection and family attribution solutions with the least manual intervention. In response, we propose Cypider framework, a set of techniques and tools aiming to perform a systematic detection of mobile malware by building an efficient and scalable similarity network infrastructure of malicious apps. Our detection method is based on a novel concept, namely malicious community, in which we consider, for a given family, the instances that share common features. Under this concept, we assume that multiple similar Android apps with different authors are most likely to be malicious. Cypider leverages this assumption for the detection of variants of known malware families and zero-day malware. It is important to mention that Cypider does not rely on signature-based or learning-based patterns. Alternatively, it applies community detection algorithms on the similarity network, which extracts sub-graphs considered as suspicious and most likely malicious communities. Furthermore, we propose a novel fingerprinting technique, namely community fingerprint, based on a learning model for each malicious community. Cypider shows excellent results by detecting about 50% of the malware dataset in one detection iteration. Besides, the preliminary results of the community fingerprint are promising as we achieved 87% of the detection.