Reducing Efficiency of Connectivity-Splitting Attack on Newscast via Limited Gossip

in Proc. of the 19th European Event on Bio-Inspired Computation, EvoCOMNET 2016 (2016, March)

Newscast is aPeer-to-Peer, nature-inspired gossip-based data exchange protocol used for information dissemination and membership management in large-scale, agent-based distributed systems. The model ... [more ▼]

Newscast is aPeer-to-Peer, nature-inspired gossip-based data exchange protocol used for information dissemination and membership management in large-scale, agent-based distributed systems. The model follows a probabilistic scheme able to keep a self-organised, small-world equilibrium featuring a complex, spatially structured and dynamically changing environment. Newscast gained popularity since the early 2000s thanks to its inherent resilience to node volatility as the protocol exhibits strong self-healing properties. However, the original design proved to be surprisingly fragile in a byzantine environment subjected to cheating faults. Indeed, a set of recent studies emphasized the hard-wired vulnerabilities of the protocol, leading to an efficient implementation of a malicious client, where a few naive cheaters are able to break the network connectivity in a very short time. Extending these previous works, we propose in this paper a modification of the seminal protocol with embedded counter-measures, improving the resilience of the scheme against malicious acts without significantly affecting the original Newscast’s proper- ties nor its inherent performance. Concrete experiments were performed to support these claims, using a framework implementing all the solutions discussed in this work. [less ▲]

Cheating-Tolerance of Parallel and Distributed Evolutionary Algorithms in Desktop Grids and Volunteer Computing Systems

Doctoral thesis (2015)

This thesis analyses the fault-tolerant nature of Evolutionary Algorithms (EAs) executed in a distributed environment which is subjected to malicious acts. Such actions are a common problem in Desktop ... [more ▼]

This thesis analyses the fault-tolerant nature of Evolutionary Algorithms (EAs) executed in a distributed environment which is subjected to malicious acts. Such actions are a common problem in Desktop Grids and Volunteer Computing Systems (DGVCS’s) utilising idle resources shared by volunteers. Due to the vast computational and storage capabilities provided at a low cost, many large-scale research projects are carried out using such set-ups. However, this advantage is obtained at the expense of a challenging, error prone, heteroge neous and volatile environment of execution. In the volunteer-based systems, such as BOINC, the incentives offered to the contributors attract also malicious users, commonly called cheaters. A cheater typically seeks to obtain the rewards with little or no contribution at all. Additionally, this group may also include "crackers" or "black hat hackers" - users motivated by nothing more than a pure satisfaction from violating computer security. In this study we use and formalise cheating faults - a model for the behaviours described above, which are a subtype of byzantine (arbitrary) faults. They are mainly characterised by the alteration of outputs produced by some or all tasks forming a distributed execution. The approach differs from the arbitrary faults in its implementation, as usually they are introduced intentionally and from within the boundaries of a system. The innate fault resilience of EAs has been previously observed in the literature. However, this PhD manuscript offers the first, formal analysis of the impact of cheating faults in this area of optimisation techniques. In particular, the following contributions are proposed: - An in-depth formal analysis of the cheating-tolerance of parallel Evolutionary Algorithms (EAs), including proofs of convergence or non-convergence towards valid solutions in the presence of malicious acts. A step-wise approach is used, focusing firstly on the most simple variant of an EA that is still of theoretical and practical interest, i.e. a (1 + 1) EA. Then the results are extended to regular (population-based) EAs. The analysis shows that the selection mechanism is crucial to achieve convergence of EAs executed in malicious environments. - The extension of the study to cheating-resilience of spatially-structured Evolutionary Algorithms (EAs) and gossip protocols. More precisely, we analyse Evolvable Agent Model (EvAg) relying on Newscast protocol to define neighbourhoods in the evolution and the communication layers. There, we provide the necessary conditions for convergence of the algorithm in a hostile environment and we show that the evolutionary process may be affected only by tampering with the connectivity between the computing resources. After that, we design an effective connectivity-splitting attack which is able to defeat the protocol using very few naive cheaters. Finally, we provide a set of countermeasures which ultimately lead to a more robust solution. These results have been published in several international, peer-reviewed venues and well recognized international journals. By the variety of problems addressed by EAs, this study will hopefully promote their usage in the future developments around distributed computing platforms such as Desktop Grids and Volunteer Computing Systems or Cloud systems where the resources cannot be fully trusted. [less ▲]

Exploiting the Hard-wired Vulnerabilities of Newscast via Connectivity-splitting Attack

in Proc. of the IEEE Intl. Conf. on Network and System Security (NSS 2014) (2014, October)

Newscast is a model for information dissemination and mem- bership management in large-scale, agent-based distributed systems. It deploys a simple, peer-to-peer data exchange protocol. The Newscast pro ... [more ▼]

Newscast is a model for information dissemination and mem- bership management in large-scale, agent-based distributed systems. It deploys a simple, peer-to-peer data exchange protocol. The Newscast pro- tocol forms an overlay network and keeps it connected by means of an epidemic algorithm, thus featuring a complex, spatially structured, and dynamically changing environment. It has recently become very popu- lar due to its inherent resilience to node volatility as it exhibits strong self-healing properties. In this paper, we analyze the robustness of the Newscast model when executed in a distributed environment subjected to malicious acts. More precisely, we evaluate the resilience of Newscast against cheating faults and demonstrate that even a few naive cheaters are able to defeat the protocol by breaking the network connectivity. Concrete experiments are performed using a framework that implements both the protocol and the cheating model considered in this work. [less ▲]

On the Resilience of the Newscast Protocol in the Presence of Cheaters

Presentation (2014, March)

Hash function generation by means of Gene Expression Programming

in Intl. Conf. on Cryptography and Security System (CSS’12) (2012, September), XII(3), 37-53

Cryptographic hash functions are fundamental primitives in modern cryptography and have many security applications (data integrity checking, cryptographic protocols, digital signatures, pseudo random ... [more ▼]

Cryptographic hash functions are fundamental primitives in modern cryptography and have many security applications (data integrity checking, cryptographic protocols, digital signatures, pseudo random number generators etc.). At the same time novel hash functions are designed (for instance in the framework of the SHA-3 contest organized by the National Institute of Standards and Technology (NIST)), the cryptanalysts exhibit a set of statistical metrics (propagation criterion, frequency analysis etc.) able to assert the quality of new proposals. Also, rules to design "good" hash functions are now known and are followed in every reasonable proposal of a new hash scheme. This article investigates the ways to build on this experiment and those metrics to generate automatically compression functions by means of Evolutionary Algorithms (EAs). Such functions are at the heart of the construction of iterative hash schemes and it is therefore crucial for them to hold good properties. Actually, the idea to use nature-inspired heuristics for the design of such cryptographic primitives is not new: this approach has been successfully applied in several previous works, typically using the Genetic Programming (GP) heuristic [1]. Here, we exploit a hybrid meta-heuristic for the evolutionary process called Gene Expression Programming (GEP) [2] that appeared far more e?cient computationally speaking compared to the GP paradigm used in the previous papers. In this context, the GEPHashSearch framework is presented. As it is still a work in progress, this article focuses on the design aspects of this framework (individuals de?nitions, ?tness objectives etc.) rather than on complete implementation details and validation results. Note that we propose to tackle the generation of compression functions as a multi-objective optimization problem in order to identify the Pareto front i.e. the set of non-dominated functions over the four ?tness criteria considered. If this goal is not yet reached, the ?rst experimental results in a mono-objective context are promising and open the perspective of fruitful contributions to the cryptographic community [less ▲]

Convergence Analysis of Evolutionary Algorithms in the Presence of Crash-Faults and Cheaters

in Computers and Mathematics with Applications (2012), 64(12), 3805-3819

This paper analyzes the fault-tolerance nature of Evolutionary Algorithms (EAs) when executed in a distributed environment subjected to malicious acts. More precisely, the inherent resilience of EAs ... [more ▼]

This paper analyzes the fault-tolerance nature of Evolutionary Algorithms (EAs) when executed in a distributed environment subjected to malicious acts. More precisely, the inherent resilience of EAs against two types of failures is considered: (1) crash faults, typically due to resource volatility which lead to data loss and part of the computation loss; (2) cheating faults, a far more complex kind of fault that can be modeled as the alteration of output values produced by some or all tasks of the program being executed. This last type of failure is due to the presence of cheaters on the computing platform. Most often in Global Computing (GC) systems such as BOINC, cheaters are attracted by the various incentives provided to stimulate the volunteers to share their computing resources: cheaters typically seek to obtain rewards with little or no contribution to the system. In this paper, the Algorithm-Based Fault Tolerance (ABFT) aspects of EAs against the above types of faults is characterized. Whereas the inherent resilience of EAs has been previously observed in the literature, for the first time, a formal analysis of the impact of the considered faults over the executed EA including a proof of convergence is proposed in this article. By the variety of problems addressed by EAs, this study will hopefully promote their usage in the future developments around distributed computing platform such as Desktop Grids and Volunteer Computing Systems or Cloud systems where the resources cannot be fully trusted. [less ▲]