The computational trust paradigm supposes that it is possible to quantify trust relations that occur within some software systems. The paradigm covers a variety of trust systems, such as trust management systems, reputation systems and trust-based security systems. Di erent trust systems have di erent assumptions, and various trust models have been developed on top of these assumptions Typically, trust models are incomparable, or even mutually unintelligible; as a result their evaluation may be circular or biased. We propose a uni ed language to express the trust models and trust systems. Within the language, all trust models are comparable, and the problem of circularity or bias is mitigated. Moreover, given a complete set of assumptions in the language, a unique trust model is de ned.
if indeed a trust models adheres to the principles, then it can be described in our language. In this paper, we demonstrate the generality and validity of the principles within the computational trust paradigm. Moreover, we reformulate existing trust models into the universal language, both to show feasibility and to exemplify the approach.
The language to express the assumptions is a distribution over strategies for each class of users. An assumption about honest users must de ne exactly what the behaviour of an honest user can be, and the prior probability that a user is honest. (The di erent strategies need not be nite, or even countable.) The major bene t of the proposed format for assumptions, is that if the assumptions are su ciently strong, they de ne a trust model. We refer to the process of obtaining a trust model by merely formulating the assumptions as trust model synthesis. There are yet many hurdles to take before trust model synthesis leads to automated trust modelling in practice. We demonstrate, in this paper, both the potential of trust model synthesis (see Section 2) and the feasibility of trust model synthesis in practice (see Section 5).
The document is organised as follows: First we look at the concrete consequences of our proposal in Section 2. There, we also address the shortcomings of the traditional approaches, and motivate our alternative. Then we formally introduce the principles that the framework is built on, in Section 3. Finally, we discuss the feasibility of automated trust modelling in Section 5, and look ahead for possible future challenges and improvements in Section 6. 2
Existing trust models and trust systems are being improved by ongoing research and by superior implementations. We refer to the general notion of continuous improvement as the life cycle. The skeleton of the life cycle, is that rst a problem or shortcoming is identi ed, then a solution or idea is proposed, implemented, veri ed, and possibly accepted. There are some problems with the life cycle, that we address in this section. Throughout this section, we suppose that our three core principles (discussed in Section 3) are su cient to perform trust model synthesis (discussed in Section 5).
Figure 1 depicts the typical life cycle of trust models and trust systems. The two life cycles are tightly coupled.
The trust system life cycle starts with a set of requirements on a system. The requirements are implemented into a trust system. The implementation of the trust system asserts a certain trust model. Then, the trust system is executed. (Partial) runs of the system are analysed using a trust model (same or other). The empirical analysis may lead to updating the requirements (e.g. if a new attack is found) or to updating the trust model (e.g. if the trust model incorrectly models real users).
The trust model life cycle starts with a set of explicit assumptions, partially based on the requirements of the system. Based on the assumptions, a trust system can be formulated. Typically, the trust system introduces a set of implicit assumptions. The trust model can be theoretically analysed using simulation or veri cation. Its results may lead to identifying a correctness problem. Typically, correctness problems are addressed by updating the trust model, not the assumptions. Occasionally, the correctness problems leads to the identi cation of an implicit assumption. Another theoretical analysis is robustness evaluation, where at least one user may violate any assumptions made about him. Its results may lead to identifying a robustness problem. A robustness problem typically induces updating the assumptions.
Not all modellers follow the life cycle to the letter, but it is a reasonable description of how di erent factors in uence or determine others. Some research focusses only on particular phases. Ideally, their solutions can be reused across di erent settings. Unfortunately, the classic life cycle hinders this to some extent. For example, it may be di cult to publish a paper that merely identi es some problem, as the audience may expect a solution. Similarly, a solution may require an implementation, and an implementation may require an empirical evaluation, etc.
The life cycle of the trust system remain largely unchanged, except that it now includes an abstraction of the trust system. Note that the abstraction could be made after or before implementation. The trust model life cycle lacks implicit assumptions. The explicit assumptions and the trust model are one and the same. Unfortunately, there is no guarantee that the trust model is computationally feasible. We may be satis ed with trust values that are approximations of the true values predicted by the model. However, these approximations would need additional analysis. Correctness evaluation is no longer a necessity (unless we need approximations, in which case their analysis su ces), and robustness evaluation is streamlined.
Empirical, correctness and robustness evaluation. When it comes to theoretical evaluation, in the classic life cycle of trust systems, correctness evaluation of trust models is emphasised heavily as a motivation to use the trust model. Correctness evaluation allows one to ascertain that the model satis es the assumptions. It is performed under the assumptions made in the trust model, and the assumptions themselves are not scrutinised. This problem is known, and e orts to mitigate this problem are not novel. The ART testbed [2], for example, is a well-known example of a testbed designed to validate di erent trust models with a uni ed procedure.
However, fully general correctness evaluation methods cannot exist [8]. Even the ART testbed can only evaluate those trust models that relate to e-commerce, and then over a limited amount of aspects. More importantly, the ART testbed can only evaluate complete trust systems with trust models, that cover all aspects of e-commerce. It is not a tool that can validate partial models intended to solve speci c problems.
An alternative evaluation is empirical evaluation. Empirical evaluation su ers less from circularity issues. However, empirical data still requires interpretation, and is not immune to biased assumptions. Any healthy life cycle of trust systems must incorporate empirical data at some point. However, as our life cycle does not su er from the issue of circularity of correctness evaluation, empirical data is not necessary to show internal consistency. As a result, the empirical evaluation is much more loosely coupled to the theoretical evaluation. This allows researchers to specialise on speci c subproblems, rather than to force all research to directly translate to a complete trust system.
In our proposed life cycle, it is the assumptions themselves that are evaluated. Since, with trust model synthesis, the model is merely the assumptions, evaluating the trust model equates to evaluating the model assumptions. Note that with the classical approach, there may be implicit or ambiguous assumptions, meaning that evaluating the stated assumptions is insu cient. In our approach, the model assumptions must be assumptions about the behaviour of the agents { concrete and explicit. Our argument is that by forcing the model assumptions to be concrete and explicit, evaluation and comparison of the trust models is more transparent. 3
The three principles that we introduce to capture the paradigm of computational trust are: 1) a trust system is
a (timed) process with partially observable states, 2) users' behaviour is dictated by a (probabilistic) strategy
and 3) trust values re ect the user's possible behaviour based on evidence. Multi-agent systems, including trust
systems, typically satisfy (
A variation of each of the principles is present in many trust systems. Trust models typically treat trust systems as a process with some properties { speci cally what actions are possible at which time. When reasoning about a trust model, one must reason about what certain past actions of an agent say about future actions, and to do this, one must categorise users. The last principle is typically seen as a requirement, e.g. a \good" trust model provides trust values that re ect the user's behaviour. We are going to sever the ties with existing methods, and rigourously de ne the three principles, even if that excludes some existing models.
Principle 1: Trust System. Principle one is based on processes that can be expressed as deterministic labelled transition systems: De nition 1. A deterministic labelled transition system is a tuple (S; A; s0; t), where S is a set of states, A is a set of actions, s0 2 S is the initial state and t : S A ! S is the transition function.
Users u 2 U are agents that use the system. Users may fully, partially, or not observe particular actions. De nition 2. A blinding is a partial function : A
U 9 A.
When u cannot observe a, then (a; u) is unde ned. When u can only partially observe a, then (a; u) = a0, where a0 is the partial observation. We also allow blinding of traces, denoted with . In ( ; u), the elements a in are replaced by (a; u), if de ned, and omitted otherwise. Thus, ( ; u) provides the perspective of agent u, when the system trace is .
Based on the notion of deterministic labelled transition systems, blinding and users, we can formally de ne trust systems: De nition 3. A trust system is a tuple (S; U; A; s0; t; ), where S is a set of states, U is a set of users, A is a set of actions, s0 is the initial state, t : S U A ! S is the transition function and a blinding.
Principle 1 supposes that a real trust system can be represented as our abstract notion of trust system.
Principle 2: Strategies. The trust system is simply an automata with branching. We need to grant the users agency, which we provide in the form of a strategy. Strategy may refer to a rational strategy, as often assumed in game theory [6]. But a strategy may also refer to, e.g., a taste pro le { what are the odds that a user enjoys something.
In most trust systems, several agents may be allowed to perform an action at a given time. Quicker agents may have an advantage, so timing must play a role in the agents' strategies. We suppose that the time before an action happens is exponentially distributed { for its convenient properties. The exponential distribution has one parameter, which is the expected time until the action, called the rate { not to be confused with a (trust) rating.
Traces, users and actions are as de ned in the trust system. A (rated) move is an assignment of rates to actions, denoted A ! R>0. Every user u has a strategy, which dictates the moves of the user, given the circumstances. We use the notion of (blinded) traces to model the circumstances.
De nition 4. A strategy of a user is a function f : T A ! R>0. A behaviour of a user is a distribution over strategies, b : (T A ! R>0) ! [0; 1]. W.l.o.g. f 2 F = ff jb(f ) > 0g.
The strategy of a user is in the extensive form. That de nition has been chosen for maximal generality. In practice, models of users are often far simpler.
Remark 1. De nition 4 asserts that all users operate independently. To model Sybil attacks (or forms of collusion), the designer needs to allow a single user to operate multiple accounts. Any cooperative strategy of a set of users that all own a single account can be mimicked by a strategy of single user creating/owning multiple accounts.
Principle 3: Trust Values. The trust values should re ect the probabilities of the possible actions that a user may perform. In a simple trust model, for example, actions may be classi ed as \good" or \bad", and a trust value denotes the probability of \good". In more sophisticated models, more actions are available, and cannot generally be classi ed as just good or bad. We want our trust values to re ect the likelihood of all possibilities.
We propose to use behaviour (i.e. a distribution over strategies) as a trust value. Suppose that the user is
aware of the unblinded trace . Assuming discrete probability distributions, users can compute the rate of an
action a by u, as Pf2F b(f ) f ( ; a), and the probability as Pf2F b(f ) Pa0f2(A ;fa() ;a0) . (
The trust value can typically not be displayed as a single value. In special cases, a compact representation exists (e.g. in Subjective Logic [3], with three values). Usually, however, there is no human-friendly representation. 4
The format of assumptions that exist to support trust models is currently heterogeneous. There have been
statistical assumptions, axiomatic assumptions, logical assumptions and informal assumptions. The assumptions
are made about trust itself, the trust system, honesty and malice, and about behaviour. The principles cover
assumptions about the trust system (
In [11], the authors propose a way of dividing model assumptions into two groups. They introduce fundamental assumptions and simplifying assumptions. Fundamental assumptions are assumptions intended to re ect the nature of the object of study (in [11], \trustee and truster agents are self-interested" is an example). Simplifying assumptions are assumptions necessitated by practical limitations of the model (in [11], \the majority of thirdparties testimonies are reliable" is an example). Trust models cannot be formulated without a good deal of fundamental and simplifying assumptions on top of the three principles and a trust system.
Both fundamental assumptions and simplifying assumptions can be encoded into a selection of behaviours. The example simplifying assumption can be encoded by letting the behaviour of those agents that sometimes provide testimonies assign a probability of over 0:5, to those strategies that are reliable1. The example fundamental assumption { that users are self-interested { can be encoded by assigning no probability to dominated strategies. User will not have strategies where users can unilaterally increase their own pro t.
Without loss of generality, let C = fc0; c1; : : : g be a partition over U (thus every ui occurs in exactly one cj ). We call ci a class of users. For example, we may have a class of buyers and a class of sellers. For each class c, we must assume:
1By making encoding assumption into behaviour, we realise that we have an implicit assumption about what it means to be reliable. Forcing such implicit assumptions to be made explicit is an important bene t of our proposed approach. Here, an educated guess would be that reliable recommenders always provide truthful testimonies about objective events. Our language is a partition of users into classes, with a prior behaviour for each class of users. The language covers all the assumptions that a trust model needs to make (at least in combination with the three principles), and it ful lls the role of a trust model.
The important question is whether it is always possible to translate the assumptions from arbitrary format, to our language. Note that in the classic life cycle (Figure 1), a correctness evaluation is performed, typically using a simulation. All users in that model are simulated using agents with a de ned behaviour { the simulation code de nes the behaviour of the agents. That code must de ne, in all possible traces, what the behaviour of the agent is. Therefore, there exists a behaviour for a user, such that it acts exactly like the simulation. Thus, if there exists a trust model with a positive correctness evaluation, then there exists a set of assumptions in our language for the same trust model. 5
In order to do trust model synthesis, the modeller must supply a trust system and behaviour, according to
principles 1 and 2. Typically, the trust system is a given. The synthesised trust model can provide trust values,
according to principle 3. To illustrate the approach with an example:
Example 1. Take a simple system called MARKET(
There is only one buyer strategy. The rate for iniate(b; s) is 1, if the seller(s) has the highest probability of deliver(s; b) according to the buyer's trust value, and 0 otherwise. Letting the unit of time, e.g., be a week, then the buyer buys from a maximally reliable seller on average once per week. There are two seller strategies, honest and cheater, where, after initiate(s; b), the honest seller performs deliver(s; b) with rate 0:9 and betray(s; b) with rate 0:1, and the cheater vice versa. Both honest sellers and cheaters take, on average, a week to act, but the honest seller delivers with high probability, whereas the cheater betrays with high probability. After receiving deliver(s; b), b performs score(b; s; r) with rate r. and after betray(s; b), b performs score(b; s; r) with rate 6 r.
The two buyers are users of the trust system. The trust system facilitates interactions between buyers and sellers, by allowing buyers to initiate interactions and sellers to nalise them. Furthermore, the system allows buyers to send ratings, which the other buyers can use. The question is, what will happen in the system? What should a buyer do when given a set of ratings? What will a buyer do? The (synthesised) trust model can answer these questions.
Given the three principles, we can make exact predictions. Given a blinded trace , let r( ; u) be the
set of traces 0, such that ( 0; u) = . Assuming the set of actions A is nite (countable), r( ; u) is nite
(countable), and can be computed in at most nitely2 (countably) many steps. Using equation (
Remark 2. So far, we have not discussed the notions of rewards or goals. The reason is that goals are orthogonal to our approach. A modeller is simply asked how he expects the users to behave, and to write this down mathematically, and he can synthesise a trust model. However, in reality users do have goals, and their goals are relevant to other aspects than the synthesis. First, the modeller may expect the behaviour because of the goals. In Example 1, the fact that buyers select the most trustworthy seller re ects their goal of not being betrayed. The split between the two classes of sellers as honest and cheater also re ects that sellers may have two goals (to make money honestly, or to cheat). Second, the goals pop up in robustness analysis. If a strategy is found that achieves the goals far better than other strategy and/or harms other users in achieving their goals, then it may be prudent to add that strategy into the behaviour of users of that class. (Example 1 is not robust against a reputation lag 2As long as the probability of extremely large invisible subtraces is negligible. attack. A seller becomes the most trustworthy one, lets others buy from him, but wait with betraying until all four have made a purchase. Such a strategy can then be added to the behaviour of sellers.)
Although the problem is theoretically computable, the approach is nevertheless intractable in full generality. Observe the following challenges: behaviours with incomputable probability density, strategies encoding NP-hard problems, and statespace explosion (number of traces). These practical issues are, of course, to be expected. However, practical models typically have simple probabilities, strategies are not based on hard problems, and agents do not exploit the entire statespace.
To illustrate the practical computability, consider Example 1: In the system MARKET(
Implementation. The rst step towards real automated trust modelling, is a prototype tool. The simplest approach to such a tool is to transform the assumptions into a probabilistic automaton, and use probabilistic veri cation tools, such as PRISM [4], to automate the synthesis. Likely, general purpose tools are not su ciently powerful, and specialised tools need to be developed for simple, realistic models (e.g. Beta-type models [3]).
The problems that the special purpose tool would have to overcome, are similar to those of probabilistic veri cation tools. We cannot yet envision the precise challenges, but statespace reduction will be a necessity. We saw that for MARKET, probabilistic bisimulation [5] reduces the statespace from countably in nite to 1. More importantly, possible forms of statespace reduction exist for our purpose, such as: Letting the system signal partial information about an action (e.g. an e-market place could signal that a transaction occurred, even if it is unaware of the outcome), and generating equivalence classes over blinded traces.
The user of the synthesised trust model may not be interested in the exact probability values. If the user allows an absolute error , and there is an upper bound m to the rate of the outgoing actions, then the statespace can be trivially bounded to a nite size. Assuming all states have an outgoing rate of m, the probability that the length of the trace exceeds n, at time x, is exponentially distributed as e mn x. Given m; x; , it is always possible to pick n, such that e mn x < . Thus, by introducing a small error , we can restrict the traces to the traces of length at most n.
The authors are currently working on a tool that can do robustness veri cation for generic trust models. Robustness veri cation is an excellent way to nd new possible attacks, which, in turn, can help us construct behaviours that take into account future attacks and responses to defences.
Application. The theoretical concepts of trust model synthesis are surprisingly powerful. In order to judge the practical power of trust model synthesis, a real model should be encoded, synthesised and compared with the original. The second core principle forces the modeller to be explicit and concrete with model assumptions. This means that, e.g., \trust is transitive" is not a valid assumption, and should be replaced by assumptions about the behaviour of users. Finding a general, but concrete, translation of that assumption is an interesting challenge. A multitude of similar assumptions exist, which pose equally interesting challenges for the modeller.
Evalutation and Analysis. We have shortly addressed the notions of evaluation and analysis. Our approach to validation is complementary to the orthodox approach to validation (e.g. ART testbed [2]). Due to the concrete nature of the assumptions, they can directly be contrasted with reality. There is, however, always a degree of interpretation. How to minimise the e ect of interpretation is currently an open question.
The approach opens new doors for robustness analysis. In security analysis, it is common to reason about users that violate the assumptions of a security protocol, and to automatically verify the security of the protocol. The question is to what extend these methods can apply to our domain. Recent research indicates that such methods are feasible for the domain [7]. Attempting to automatically verify the impact of breaking the assumptions is a di cult challenge. 7
We have presented a novel approach to constructing trust models. The main advantage is the lack of hidden assumptions that may introduce unseen problems. The key contribution is a generic language to formulate assumptions about trust models. The language consists of describing the behaviour of (classes of) users. We have formulated 3 major principles that we argue apply to all trust systems. The validity of the language hinges on these principles. We have formulated how the design and construction of trust systems and models can be streamlined by our proposal. Finally, parts of the tasks of the trust system can be generated automatically, using trust model synthesis.
There are several ways in which the language can help in future research: One way is by providing a link towards automation helps researchers tackle problems that are more suitable to be address by computers. Furthermore, two mutually intelligible trust models can now be provided a common foundation for comparison. Finally, we hope that vague or hidden assumptions are eventually considered unacceptable, and our language is one of several approaches to bring rigour.