In the field of multiagent systems, trust and reputation systems are intended to assist agents in finding trustworthy partners with whom to interact. Earlier work of ours identified in theory a number of security vulnerabilities in trust and reputation systems, weaknesses that might be exploited by malicious agents to bypass the protections offered by such systems. In this work, we begin by developing the TREET testbed, a simulation platform that allows for extensive evaluation and flexible experimentation with trust and reputation technologies. We use this testbed to experimentally validate the practicality and gravity of attacks against vulnerabilities. Of particular interest are attacks that are collusive in nature: groups of agents (coalitions) working together to improve their expected rewards. But the issue of coalitions is not unique to trust and reputation; rather, it cuts across a range of fields in multiagent systems and beyond. In some scenarios, coalitions may be unwanted or forbidden; in others they may be benign or even desirable. In this document, we propose a method for detecting coalitions and identifying coalition members, a capability that is likely to be valuable in many of the diverse fields where coalitions may be of interest. Our method makes use of clustering in benefit space (a high-dimensional space reflecting how agents benefit others in the system) in order to identify groups of agents who benefit similar sets of agents. A statistical technique is then used to identify which clusters contain coalitions. Experimentation using the TREET platform verifies the effectiveness of this approach. A series of enhancements to our method are also introduced, which improve the accuracy and robustness of the algorithm. To demonstrate how this broadly-applicable tool can be used to address domain-specific problems, we focus again on trust and reputation systems. We show how, by incorporating our work into one such system (the existing Beta Reputation System), we can provide resistance to collusion. We conclude with a detailed discussion of the value of our work for a wide range of environments, including a variety of multiagent systems and real-world settings.

In the field of multiagent systems, trust and reputation systems are intended to assist agents in finding trustworthy partners with whom to interact. Earlier work of ours identified in theory a number of security vulnerabilities in trust and reputation systems, weaknesses that might be exploited by malicious agents to bypass the protections offered by such systems. In this work, we begin by developing the TREET testbed, a simulation platform that allows for extensive evaluation and flexible experimentation with trust and reputation technologies. We use this testbed to experimentally validate the practicality and gravity of attacks against vulnerabilities. Of particular interest are attacks that are collusive in nature: groups of agents (coalitions) working together to improve their expected rewards. But the issue of coalitions is not unique to trust and reputation; rather, it cuts across a range of fields in multiagent systems and beyond. In some scenarios, coalitions may be unwanted or forbidden; in others they may be benign or even desirable. In this document, we propose a method for detecting coalitions and identifying coalition members, a capability that is likely to be valuable in many of the diverse fields where coalitions may be of interest. Our method makes use of clustering in benefit space (a high-dimensional space reflecting how agents benefit others in the system) in order to identify groups of agents who benefit similar sets of agents. A statistical technique is then used to identify which clusters contain coalitions. Experimentation using the TREET platform verifies the effectiveness of this approach. A series of enhancements to our method are also introduced, which improve the accuracy and robustness of the algorithm. To demonstrate how this broadly-applicable tool can be used to address domain-specific problems, we focus again on trust and reputation systems. We show how, by incorporating our work into one such system (the existing Beta Reputation System), we can provide resistance to collusion. We conclude with a detailed discussion of the value of our work for a wide range of environments, including a variety of multiagent systems and real-world settings.

Empresas em cadeias de suprimentos têm como objetivo maximizar suas produtividades, e consequentemente seus lucros. Uma maneira de estudar o comportamento destas cadeias é simulá-las utilizando uma abordagem multi-agentes. Neste trabalho, adicionamos múltiplos agentes nos níveis de um modelo amplamente adotado na literatura, denominado Beer Game, para avaliar a eficiência local e global dos fornecedores. Para tal, utilizamos perfis distintos baseados em confiança ou em preço. Medimos o impacto de usar tais políticas de seleção no capital acumulado pelos agentes, e concluímos que as parcerias baseadas em confiança são recomendáveis em cenários com ampla disseminação de informações verdadeiras, enquanto que as baseadas em lucro são mais vantajosas em cenários marcados por pouca comunicação ou pelo espalhamento de informações falsas. / Companies in supply chains have the objective of maximizing their productivities, and consequently their profits. A way of to study the behavior of these chains is to simulate them using a multi-agent-based approach. In this work, we added multiple agents at the levels of a widely adopted model in the literature, called Beer Game, to evaluate the local and global performance of suppliers. To do this, we use distinct profiles based on trust or price. We measure the impact of using such selection policies on the agents\' profit, and we could conclude that trust-based partnerships are recommended in scenarios with wide dissemination of true information, while profit-based partnerships are most advantageous in scenarios marked by poor communication or spreading false information.

Empresas em cadeias de suprimentos têm como objetivo maximizar suas produtividades, e consequentemente seus lucros. Uma maneira de estudar o comportamento destas cadeias é simulá-las utilizando uma abordagem multi-agentes. Neste trabalho, adicionamos múltiplos agentes nos níveis de um modelo amplamente adotado na literatura, denominado Beer Game, para avaliar a eficiência local e global dos fornecedores. Para tal, utilizamos perfis distintos baseados em confiança ou em preço. Medimos o impacto de usar tais políticas de seleção no capital acumulado pelos agentes, e concluímos que as parcerias baseadas em confiança são recomendáveis em cenários com ampla disseminação de informações verdadeiras, enquanto que as baseadas em lucro são mais vantajosas em cenários marcados por pouca comunicação ou pelo espalhamento de informações falsas. / Companies in supply chains have the objective of maximizing their productivities, and consequently their profits. A way of to study the behavior of these chains is to simulate them using a multi-agent-based approach. In this work, we added multiple agents at the levels of a widely adopted model in the literature, called Beer Game, to evaluate the local and global performance of suppliers. To do this, we use distinct profiles based on trust or price. We measure the impact of using such selection policies on the agents\' profit, and we could conclude that trust-based partnerships are recommended in scenarios with wide dissemination of true information, while profit-based partnerships are most advantageous in scenarios marked by poor communication or spreading false information.

In electronic marketplaces, buying and selling agents may be used to represent buyers and sellers respectively. When these marketplaces are large, repeated transactions between traders may be rare. This makes it difficult for buying agents to judge the reliability of selling agents, discouraging participation in the market. A variety of trust and reputation systems have been proposed to help traders to find trustworthy partners. Unfortunately, as our investigations reveal, there are a number of common vulnerabilities present in such models---security problems that may be exploited by `attackers' to cheat without detection/repercussions. Inspired by these findings, we set out to develop a model of trust with more robust security properties than existing proposals. Our Trunits model represents a fundamental re-conception of the notion of trust. Instead of viewing trust as a measure of predictability, Trunits considers trust to be a quality that one possesses. Trust is represented using abstract trust units, or `trunits', in much the same way that money represents quantities of value. Trunits flow in the course of transactions (again, similar to money); a trader's trunit balance determines if he is trustworthy for a given transaction. Faithful execution of a transaction results in a larger trunit balance, permitting the trader to engage in more transactions in the future---a built-in economic incentive for honesty. We present two mechanisms (sets of rules that govern the operation of the marketplace) based on this model: Basic Trunits, and an extension known as Commodity Trunits, in which trunits may be bought and sold. Seeking to precisely characterize the protection provided to market participants by our models, we develop a framework for security analysis of trust and reputation systems. Inspired by work in cryptography, our framework allows security guarantees to be developed for trust/reputation models--provable claims of the degree of protection provided, and the conditions under which such protection holds. We focus in particular on characterizing buyer security: the properties that must hold for buyers to feel secure from cheating sellers. Beyond developing security guarantees, this framework is an important research tool, helping to highlight limitations and deficiencies in models so that they may be targeted for future investigation. Application of this framework to Basic Trunits and Commodity Trunits reveals that both are able to deliver provable security to buyers.

In electronic marketplaces, buying and selling agents may be used to represent buyers and sellers respectively. When these marketplaces are large, repeated transactions between traders may be rare. This makes it difficult for buying agents to judge the reliability of selling agents, discouraging participation in the market. A variety of trust and reputation systems have been proposed to help traders to find trustworthy partners. Unfortunately, as our investigations reveal, there are a number of common vulnerabilities present in such models---security problems that may be exploited by `attackers' to cheat without detection/repercussions. Inspired by these findings, we set out to develop a model of trust with more robust security properties than existing proposals. Our Trunits model represents a fundamental re-conception of the notion of trust. Instead of viewing trust as a measure of predictability, Trunits considers trust to be a quality that one possesses. Trust is represented using abstract trust units, or `trunits', in much the same way that money represents quantities of value. Trunits flow in the course of transactions (again, similar to money); a trader's trunit balance determines if he is trustworthy for a given transaction. Faithful execution of a transaction results in a larger trunit balance, permitting the trader to engage in more transactions in the future---a built-in economic incentive for honesty. We present two mechanisms (sets of rules that govern the operation of the marketplace) based on this model: Basic Trunits, and an extension known as Commodity Trunits, in which trunits may be bought and sold. Seeking to precisely characterize the protection provided to market participants by our models, we develop a framework for security analysis of trust and reputation systems. Inspired by work in cryptography, our framework allows security guarantees to be developed for trust/reputation models--provable claims of the degree of protection provided, and the conditions under which such protection holds. We focus in particular on characterizing buyer security: the properties that must hold for buyers to feel secure from cheating sellers. Beyond developing security guarantees, this framework is an important research tool, helping to highlight limitations and deficiencies in models so that they may be targeted for future investigation. Application of this framework to Basic Trunits and Commodity Trunits reveals that both are able to deliver provable security to buyers.

No

This thesis investigates both theoretical and practical aspects of the design and analysis of iterative algorithms for trust and reputation management and recommender systems. It also studies the application of iterative trust and reputation management mechanisms in ad-hoc networks and P2P systems. First, an algebraic and iterative trust and reputation management scheme (ITRM) is proposed. The proposed ITRM can be applied to centralized schemes, in which a central authority collects the reports and forms the reputations of the service providers (sellers) as well as report/rating trustworthiness of the (service) consumers (buyers). It is shown that ITRM is robust in filtering out the peers who provide unreliable ratings. Next, the first application of Belief Propagation algorithm, a fully iterative probabilistic algorithm, on trust and reputation management (BP-ITRM) is proposed. In BP-ITRM, the reputation management problem is formulated as an inference problem, and it is described as computing marginal likelihood distributions from complicated global functions of many variables. However, it is observed that computing the marginal probability functions is computationally prohibitive for large scale reputation systems. Therefore, the belief propagation algorithm is utilized to efficiently (in linear complexity) compute these marginal probability distributions. In BP-ITRM, the reputation system is modeled by using a factor graph and reputation values of the service providers (sellers) are computed by iterative probabilistic message passing between the factor and variable nodes on the graph. It is shown that BP-ITRM is reliable in filtering out malicious/unreliable reports. It is proven that BP-ITRM iteratively reduces the error in the reputation values of service providers due to the malicious raters with a high probability. Further, comparison of BP-ITRM with some well-known and commonly used reputation management techniques (e.g., Averaging Scheme, Bayesian Approach and Cluster Filtering) indicates the superiority of the proposed scheme both in terms of robustness against attacks and efficiency. The introduction of the belief propagation and iterative message passing methods onto trust and reputation management has opened up several research directions. Thus, next, the first application of the belief propagation algorithm in the design of recommender systems (BPRS) is proposed. In BPRS, recommendations (predicted ratings) for each active user are iteratively computed by probabilistic message passing between variable and factor nodes in a factor graph. It is shown that as opposed to the previous recommender algorithms, BPRS does not require solving the recommendation problem for all users if it wishes to update the recommendations for only a single active user using the most recent data (ratings). Further, BPRS computes the recommendations for each user with linear complexity, without requiring a training period while it remains comparable to the state of art methods such as Correlation-based neighborhood model (CorNgbr) and Singular Value Decomposition (SVD) in terms of rating and precision accuracy. This work also explores fundamental research problems related to application of iterative and probabilistic reputation management systems in various fields (such as ad-hoc networks and P2P systems). A distributed malicious node detection mechanism is proposed for delay tolerant networks (DTNs) using ITRM which enables every node to evaluate other nodes based on their past behavior, without requiring a central authority. Further, for the first time. the belief propagation algorithm is utilized in the design and evaluation of distributed trust and reputation management systems for P2P networks. Several schemes are extensively simulated and are compared to demonstrate the effectiveness of the iterative algorithms and belief propagation on these applications.

Dynamic spectrum access enabled by cognitive radio networks are envisioned to drive the next generation wireless networks that can increase spectrum utility by opportunistically accessing unused spectrum. Due to the policy constraint that there could be no interference to the primary (licensed) users, secondary cognitive radios have to continuously sense for primary transmissions. Typically, sensing reports from multiple cognitive radios are fused as stand-alone observations are prone to errors due to wireless channel characteristics. Such dependence on cooperative spectrum sensing is vulnerable to attacks such as Secondary Spectrum Data Falsification (SSDF) attacks when multiple malicious or selfish radios falsify the spectrum reports. Hence, there is a need to quantify the trustworthiness of radios that share spectrum sensing reports and devise malicious node identification and robust fusion schemes that would lead to correct inference about spectrum usage. In this work, we propose an anomaly monitoring technique that can effectively capture anomalies in the spectrum sensing reports shared by individual cognitive radios during cooperative spectrum sensing in a multi-channel distributed network. Such anomalies are used as evidence to compute the trustworthiness of a radio by its neighbours. The proposed anomaly monitoring technique works for any density of malicious nodes and for any physical environment. We propose an optimistic trust heuristic for a system with a normal risk attitude and show that it can be approximated as a beta distribution. For a more conservative system, we propose a multinomial Dirichlet distribution based conservative trust framework, where Josang*s Belief model is used to resolve any uncertainty in information that might arise during anomaly monitoring. Using a machine learning approach, we identify malicious nodes with a high degree of certainty regardless of their aggressiveness and variations introduced by the pathloss environment. We also propose extensions to the anomaly monitoring technique that facilitate learning about strategies employed by malicious nodes and also utilize the misleading information they provide. We also devise strategies to defend against a collaborative SSDF attack that is launched by a coalition of selfish nodes. Since, defense against such collaborative attacks is difficult with popularly used voting based inference models or node centric isolation techniques, we propose a channel centric Bayesian inference approach that indicates how much the collective decision on a channels occupancy inference can be trusted. Based on the measured observations over time, we estimate the parameters of the hypothesis of anomalous and non-anomalous events using a multinomial Bayesian based inference. We quantitatively define the trustworthiness of a channel inference as the difference between the posterior beliefs associated with anomalous and non-anomalous events. The posterior beliefs are updated based on a weighted average of the prior information on the belief itself and the recently observed data. Subsequently, we propose robust fusion models which utilize the trusts of the nodes to improve the accuracy of the cooperative spectrum sensing decisions. In particular, we propose three fusion models: (i) optimistic trust based fusion, (ii) conservative trust based fusion, and (iii) inversion based fusion. The former two approaches exclude untrustworthy sensing reports for fusion, while the last approach utilizes misleading information. All schemes are analyzed under various attack strategies. We propose an asymmetric weighted moving average based trust management scheme that quickly identifies on-off SSDF attacks and prevents quick trust redemption when such nodes revert back to temporal honest behavior. We also provide insights on what attack strategies are more effective from the adversaries* perspective. Through extensive simulation experiments we show that the trust models are effective in identifying malicious nodes with a high degree of certainty under variety of network and radio conditions. We show high true negative detection rates even when multiple malicious nodes launch collaborative attacks which is an improvement over existing voting based exclusion and entropy divergence techniques. We also show that we are able to improve the accuracy of fusion decisions compared to other popular fusion techniques. Trust based fusion schemes show worst case decision error rates of 5% while inversion based fusion show 4% as opposed majority voting schemes that have 18% error rate. We also show that the proposed channel centric Bayesian inference based trust model is able to distinguish between attacked and non-attacked channels for both static and dynamic collaborative attacks. We are also able to show that attacked channels have significantly lower trust values than channels that are not– a metric that can be used by nodes to rank the quality of inference on channels.

Mit der zunehmenden Verbreitung mobiler Endgeräte und Dienste ergeben sich auch neue Herausforderungen für ihre Sicherheit. Diese lassen sich nur teilweise mit herkömmlichen Sicherheitsparadigmen und -mechanismen meistern. Die Gründe hierfür sind in den veränderten Voraussetzungen durch die inhärenten Eigenschaften mobiler Systeme zu suchen. Die vorliegende Arbeit thematisiert am Beispiel von Wireless LANs die Entwicklung von Sicherheitsmechanismen für drahtlose Ad-hoc- und Infrastrukturnetze. Sie stellt dabei den umfassenden Schutz der einzelnen Endgeräte in den Vordergrund, die zur Kompensation fehlender infrastruktureller Sicherheitsmaßnahmen miteinander kooperieren. Den Ausgangspunkt der Arbeit bildet eine Analyse der Charakteristika mobiler Umgebungen, um grundlegende Anforderungen an eine Sicherheitslösung zu identifizieren. Anhand dieser werden existierende Lösungen bewertet und miteinander verglichen. Der so gewonnene Einblick in die Vor- und Nachteile präventiver, reaktiver und angriffstoleranter Mechanismen führt zu der Konzeption einer hybriden universellen Rahmenarchitektur zur Integration beliebiger Sicherheitsmechanismen in einem kooperativen Verbund. Die Validierung des Systementwurfs erfolgt anhand einer zweigeteilten prototypischen Implementierung. Den ersten Teil bildet die Realisierung eines verteilten Network Intrusion Detection Systems als Beispiel für einen Sicherheitsmechanismus. Hierzu wird eine Methodik beschrieben, um anomalie- und missbrauchserkennende Strategien auf beliebige Netzprotokolle anzuwenden. Die Machbarkeit des geschilderten Ansatzes wird am Beispiel von infrastrukturellem WLAN nach IEEE 802.11 demonstriert. Den zweiten Teil der Validierung bildet der Prototyp einer Kooperations-Middleware auf Basis von Peer-to-Peer-Technologien für die gemeinsame Angriffserkennung lose gekoppelter Endgeräte. Dieser kompensiert bisher fehlende Mechanismen zur optimierten Abbildung des Overlay-Netzes auf die physische Struktur drahtloser Netze, indem er nachträglich die räumliche Position mobiler Knoten in die Auswahl eines Kooperationspartners einbezieht. Die zusätzlich definierte Schnittstelle zu einem Vertrauensmanagementsystem ermöglicht die Etablierung von Vertrauensbeziehungen auf Kooperationsebene als wichtige Voraussetzung für den Einsatz in realen Umgebungen. Als Beispiel für ein Vertrauensmanagementsystem wird der Einsatz von Reputationssystemen zur Bewertung der Verlässlichkeit eines mobilen Knotens diskutiert. Neben einem kurzen Abriss zum Stand der Forschung in diesem Gebiet werden dazu zwei Vorschläge für die Gestaltung eines solchen Systems für mobile Ad-hoc-Netze gemacht. / The increasing deployment of mobile devices and accompanying services leads to new security challenges. Due to the changed premises caused by particular features of mobile systems, these obstacles cannot be solved solely by traditional security paradigms and mechanisms. Drawing on the example of wireless LANs, this thesis examines the development of security mechanisms for wireless ad hoc and infrastructural networks. It places special emphasis on the comprehensive protection of each single device as well as compensating missing infrastructural security means by cooperation. As a starting point this thesis analyses the characteristics of mobile environments to identify basic requirements for a security solution. Based on these requirements existing preventive, reactive and intrusion tolerant approaches are evaluated. This leads to the conception of a hybrid and universal framework to integrate arbitrary security mechanisms within cooperative formations. The resulting system design is then validated by a twofold prototype implementation. The first part consists of a distributed network intrusion detection system as an example for a security mechanism. After describing a methodology for applying anomaly- as well as misuse-based detection strategies to arbitrary network protocols, the feasibility of this approach is demonstrated for IEEE 802.11 infrastructural wireless LAN. The second part of the validation is represented by the prototype of a P2P-based cooperation middleware for collaborative intrusion detection by loosely coupled devices. Missing mechanisms for the improved mapping of overlay and physical network structures are compensated by subsequently considering the spatial position of a mobile node when choosing a cooperation partner. Furthermore, an additional interface to an external trust management system enables the establishment of trust relationships as a prerequisite for a deployment in real world scenarios. Reputation systems serve as an example of such a trust management system that can be used to estimate the reliability of a mobile node. After outlining the state of the art, two design patterns of a reputation system for mobile ad hoc networks are presented.