Analyzing Trust Management Impact to Optimal Adversarial Attacks in Recommender Systems

Ranking systems, such as those in product review sites, and various recommender systems usually employ user ratings to rank favorite items based on their quality and/or popularity. Since higher ranked items are more likely to be selected by customers and thus yield more revenues for their providers, the latter with unpopular and low quality items have strong incentives to try to strategically manipulate their ranking. However, rank manipulation attempts are also costly, especially in the presence of trust management mechanisms. This paper analyzes the cost-effectiveness of adversary attack strategies for manipulating these rankings from various perspectives and identifies the optimal adversary strategies. Particularly, we analyze the probability of a successful attack by an adversary in relation with (1) its computational and financial power to generate a certain number of fake identities and insert dishonest ratings to the systems, and (2) the capability of the trust mechanism employed to detect and eliminate malicious ratings. By means of extensive simulation experiments, we also estimate the impacts of the trust management mechanisms to the attack costs in a variety of settings and compare the probabilities of success under different attack strategies of the adversary to confirm our theoretical results. Additionally, we provide a preliminary analysis and experimental evaluation of the effectiveness of adversary attacks in case of multiple rival adversaries. Our research provides a new insight to the objective-oriented design of trust-based ranking systems and their attack resilience from an economic perspective.

Object-oriented approach for dynamic system modelling and simulation

Adel Besrour

Software engineering always cares to provide solutions for building applications as close as possible to what they should be, according to the requirements and the final users needs. Systems behavior simulation is a very common application to virtually reproduce and often predict the real-world behavior. Simulation is one of the most operational research tool in a large variety of engineering and scientific domains: Transport, telecommunication, medicine, chemical processes, physics, etc. The complexity of such application is relative to the increasing complexity of the systems. In this context, it is relevant to bring together different tools and formalisms such as markovian chain, Petri nets, etc., to improve the existent approaches and so to answer the simulations performances needs. The principle objective of this thesis is to bring together techniques from software engineering and safety engineering in order to improve the state of the art of modeling and simulation of dynamic systems in the industrial context. In addressing this objective, this work initially involves defining the essential limitations of the used formalisms, methods and tools regarding from one hand the software engineering modeling and simulation techniques and from the other hand the existent risk analysis methodologies. This work is conducted with respect to the problem of danger identification, considering the context of the complex systems behavior and their interaction with the human operator. In software engineering, it is well known that Petri/high-level nets have attractive characteristics to be used in systems simulation and behavior prediction such as the natural graphical representation, and their well-defined semantic. They are well-suited for the description of complex situations with concurrency (interleaving and true concurrency depending on the underlying semantics), conflict and confusion. However, the absence of structuring capabilities has been one of the main criticisms raised against Petri nets/high-level nets. Thus, there have been many attempts to introduce structuring principles in nets of this kind [BCM88] [Kie89] [JR91]. The attractive characteristics of Petri/high-level nets have prompted researchers to enrich these formalisms with object-oriented features. CO-OPN (Concurrent Object-Oriented Petri Net) approach, brings together the power of both Petri/high-level nets and object-orientation techniques, it has been devised so as to offer an adequate framework for the specification and design of large scale concurrent system [BG91]. CO-OPN, as a powerful modeling tool, has been used in a limited way to simulate systems. This work aims to provide a CO-OPN extension to allow a more realistic systems' simulation. Actually, its simulator semantic uses to be a suitable approach for modeling near closed systems and software components, because they need to loose coupling with external world. But, when we model more realistic problems like industrial processes, where human interaction is a relevant event, this approach is not sufficient to catch all system activity attributes. Moreover, the CO-OPN interpretation process does not allow interaction with the object internal states. This work provides a new solution to overcome CO-OPN simulation limitations and a set of prototypes to assist dynamic systems simulations. Furthermore, this work has been conducted in a Risk Analysis (RA) context, a domain where computer-based simulations research are of utmost interest. Actually, classical approaches used to address complex workplace hazard in a limited way, using checklists or sequence models. Moreover, the use of single oriented methods, such as AEA (man-oriented), FMEA (machine oriented) or HAZOP (process oriented), is not satisfactory to overcome the increasing sophistication of industrial processes. The automation of a part of the analysis process as well as the multiple-oriented approach allowed by dynamic modeling may indeed enhance significantly the analysis completeness and reduce the time analyzing time. This work, based on Object Oriented Petri net formalism (CO-OPN), propose an alternative multi-oriented approach where existent methods limitations have been criticized to develop a dynamic model, MORM (Man-machine Occupational Risk Modeling). A real industrial system (metal wire making process) has been specified to implement the different approach steps (system identification, model application, system simulation, system analysis).

EPFL2005

Effective Usage of Computational Trust Models in Rational Environments

Karl Aberer, Hung Le Vu

Computational reputation-based trust models using statistical learning have been intensively studied for distributed systems where peers behave maliciously. However practical applications of such models in environments with both malicious and rational behaviors are still very little understood. In this paper, we study the relation between their accuracy measures and their ability to enforce cooperation among participants and discourage selfish behaviors. We provide theoretical results that show the conditions under which cooperation emerges when using computational trust models with a given accuracy and how cooperation can be still sustained while reducing the cost and accuracy of those models. Specifically, we propose a peer selection protocol that uses a computational trust model as a dishonesty detector to filter out unfair ratings. We prove that such a model with reasonable misclassification error bound in identifying malicious ratings can effectively build trust and cooperation in the system, considering rationality of participants. These results reveal two interesting observations. First, the key to the success of a reputation system in a rational environment is not a sophisticated trust learning mechanism, but an effective identity management scheme to prevent whitewashing behaviors. Second, given an appropriate identity management mechanism, a reputation-based trust model with a moderate accuracy bound can be used to enforce cooperation effectively in systems with both rational and malicious participants. As a result, in heterogeneous environments where peers use different algorithms to detect misbehavior of potential partners, cooperation may still emerge. We verify and extend these theoretical results to a variety of settings involving honest, malicious and strategic players through extensive simulation. These results will enable a much more targeted, cost-effective and realistic design for decentralized trust management systems, such as needed for peer-to-peer, electronic commerce or community systems.

2011

Reliability Analysis of Data Storage Systems

Vinodh Venkatesan

Modern data storage systems are extremely large and consist of several tens or hundreds of nodes. In such systems, node failures are daily events, and safeguarding data from them poses a serious design challenge. The focus of this thesis is on the data reliability analysis of storage systems and, in particular, on the effect of different design choices and parameters on the system reliability. Data redundancy, in the form of replication or advanced erasure codes, is used to protect data from node failures. By storing redundant data across several nodes, the surviving redundant data on surviving nodes can be used to rebuild the data lost by the failed nodes if node failures occur. As these rebuild processes take a finite amount of time to complete, there exists a nonzero probability of additional node failures during rebuild, which eventually may lead to a situation in which some of the data have lost so much redundancy that they become irrecoverably lost from the system. The average time taken by the system to suffer an irrecoverable data loss, also known as the mean time to data loss (MTTDL), is a measure of data reliability that is commonly used to compare different redundancy schemes and to study the effect of various design parameters. The theoretical analysis of MTTDL, however, is a challenging problem for non-exponential real-world failure and rebuild time distributions and for general data placement schemes. To address this issue, a methodology for reliability analysis is developed in this thesis that is based on the probability of direct path to data loss during rebuild. The reliability analysis is detailed in the sense that it accounts for the rebuild times involved, the amounts of partially rebuilt data when additional nodes fail during rebuild, and the fact that modern systems use an intelligent rebuild process that will first rebuild the data having the least amount of redundancy left. Through rigorous arguments and simulations it is established that the methodology developed is well-suited for the reliability analysis of real-world data storage systems. Applying this methodology to data storage systems with different types of redundancy, various data placement schemes, and rebuild constraints, the effect of the design parameters on the system reliability is studied. When sufficient network bandwidth is available for rebuild processes, it is shown that spreading the redundant data corresponding to the data on each node across a higher number of other nodes and using a distributed and intelligent rebuild process will improve the system MTTDL. In particular, declustered placement, which corresponds to spreading the redundant data corresponding to each node equally across all other nodes of the system, is found to potentially have significantly higher MTTDL values than other placement schemes, especially for large storage systems. This implies that more reliable data storage systems can be designed merely by changing the data placement without compromising on the storage efficiency or performance. The effect of a limited network rebuild bandwidth on the system reliability is also analyzed, and it is shown that, for certain redundancy schemes, spreading redundant data across more number of nodes can actually have a detrimental effect on reliability. It is also shown that the MTTDL values are invariant in a large class of node failure time distributions with the same mean. This class includes the exponential distribution as well as the real-world distributions, such as Weibull or gamma. This result implies that the system MTTDL will not be affected if the failure distribution is changed to a corresponding exponential one with the same mean. This observation is also of great importance because it suggests that the MTTDL results obtained in the literature by assuming exponential node failure distributions may still be valid for real-world storage systems despite the fact that real-world failure distributions are non-exponential. In contrast, it is shown that the MTTDL is sensitive to the node rebuild time distribution. A storage system reliability simulator is built to verify the theoretical results mentioned above. The simulator is sufficiently complex to perform all required failure events and rebuild tasks in a storage system, to use real-world failure and rebuild time distributions for scheduling failures and rebuilds, to take into account partial rebuilds when additional node failures occur, and to simulate different data placement schemes and compare their reliability. The simulation results are found to match the theoretical predictions with high confidence for a wide range of system parameters, thereby validating the methodology of reliability analysis developed.

EPFL2012