=Paper=
{{Paper
|id=Vol-190/paper-8
|storemode=property
|title=How Certain is Recommended Trust-Information
|pdfUrl=https://ceur-ws.org/Vol-190/paper08.pdf
|volume=Vol-190
|authors=Uwe Roth and Volker Fusenig
|dblpUrl=https://dblp.org/rec/conf/mtw/RothF06
}}
==How Certain is Recommended Trust-Information==
https://ceur-ws.org/Vol-190/paper08.pdf
Position Paper:
How Certain is Recommended Trust-Information?
Uwe Roth Volker Fusenig
University of Luxembourg University of Luxembourg
FSTC Campus Kirchberg FSTC Campus Kirchberg
6, rue Richard Coudenhove-Kalergi 6, rue Richard Coudenhove-Kalergi
L-1359 Luxembourg L-1359 Luxembourg
uwe.roth@uni.lu volker.fusenig@uni.lu
ABSTRACT Even more difficult is the attempt to find computable models of
Nowadays the concept of trust in computer communications starts trust, particularly if one tries to keep all psycho-sociological
to get more and more popular. While the idea of trust in human morality from the real life out of the model. But, apart of all these
interaction seems to be obvious and understandable it is very problems, some approaches have been introduced with more or
difficult to find adequate and precise definitions of the trust-term. less success.
Even more difficult is the attempt to find computable models of In this paper our focus lies in the question, how far recommended
trust, particularly if one tries to keep all psycho-sociological trust-information can be the base of a trust-decision. [1].
morality from the real life out of the model. But, apart of all these
problems, some approaches have been introduced with more or Our concept is based on directional direct trust relations between
less success. an entity and an opposite entity. Individual experiences are
essential for a direct trust relation. The trust-term in this paper is
In this paper our focus lies in the question, how far recommended associated only with direct-trust. Additionally we introduce
trust-information can be the base of a trust-decision. We introduce reliability as a probability for the reliable transmission of
trust-decisions as the final step of a randomly chosen path in a recommend trust-information.
decision-tree where reliability and certainty plays a big part in the
creation of the tree. One advantage of the procedure to induce the In order to be able to make trust-decisions on the base of
trust-decisions on the base of randomness lies in the higher recommended trust-information, our solution does not try to
resistance against false information from malicious entities condense the chains of recommendation to only one value, but
because there is a chance that paths through the tree will be keeps the information untouched. We introduce trust-decisions as
chosen which exclude information of these entities. the final step of a randomly chosen path in a decision-tree where
reliability and certainty plays a big part in the creation of the tree.
Besides the new approach of trust-decisions on the base of A trust-decision is done using the randomly chosen trust-
recommended trust-information, we show how far (meaning with information. Certainty indicates the probability of the procedure
how many recommenders) it is reasonable to recommend trust- to reach a reliable trust value inside a sub-tree of the decision-
information, we will give suggestions how to optimize the tree of tree.
reliability, certainty and trust, so that in an adequate time trust-
decisions are possible and we show the influence of bad and One advantage of the procedure to induce the trust-decisions on
malicious entities on the results of the trust-decision. the base of randomness lies in the higher resistance against false
information from malicious entities because there is a chance that
paths through the tree will be chosen which exclude information
Categories and Subject Descriptors of these entities.
G3 [Probability and Statistics]
Besides the new approach of trust-decisions on the base of
F2 [Analysis of Algorithms and Problem Complexity] recommended trust-information, we show how far (meaning with
how many recommenders) it is reasonable to recommend trust-
General Terms information, we will give suggestions how to optimize the tree of
Algorithms, Measurement, Reliability, Experimentation, Theory reliability, certainty and direct-trust, so that in an adequate time
trust-decisions are possible and we show the influence of bad and
malicious entities on the results of the trust-decision.
Keywords
Trust, Trust-Decision, Recommended Trust, Certainty
2. Related Work
1. INTRODUCTION Several approaches to handle direct trust relations on the base of
Nowadays the concept of trust in computer communications starts reputation exist. Dewan [2] builds up a routing strategy based on
to get more and more popular. While the idea of trust in human reputations. The reputation of a node A is the ratio of positive or
interaction seems to be obvious and understandable it is very negative behaviour. For example if A acts 80 times in a good way
difficult to find adequate and precise definitions of the trust-term. and 20 times in a bad way the calculated reputation is
80/(80+20)=0.8. He defines a threshold of reputation. The routing
algorithm prefers nodes with a reputation greater than this
Copyright is held by IW3C2. threshold. In return packets from nodes with a good reputation are
WWW 2006, May 22–26, 2006, Edinburgh, UK. favoured over packets from nodes with a bad reputation while
routing to the destination.
The trust model of Pirzada and McDonald [3] is an adaptation of First we need Entities do define the trustee and the trusted party
the model of Marsh [8]. During the calculation of the trust value of a direct-trust relation (def. 1 (1, 2)) If the number of individual
out of the experiences with a node a weight value of the experiences of the trustee is not worth to build a trust-relation the
transaction is taken into account. Every node defines his own direct-trust is not defined (def. 1 (3)). No recommended
weight value of a transaction, depending on his benefits. Also experiences but only new individual experiences may lead to new
routing is presented as a possible application of this trust model. direct-trust. This paper does not give a definition of the direct-
Beth [5] additionally presents the computation of trust based on trust and how the individual experiences have influence in the
recommendations. For that purpose he introduces recommenda- trust-model. But we show how to come to a trust-decision, if no
tion trust and direct trust. If a node A wants to establish a direct direct-trust exists, but only recommended direct-trust information.
trust relation to an unknown node B, A needs a third party C with The trust decision in our case is always a yes/no decision which
a direct trust value for B and A needs a recommendation trust depends on the trust relation in combination with the concrete
value for C. If there is more than one path from A to B the trust-question (def. 1 (4)).
calculated direct trust values of the different paths can be
combined to only one direct trust value. The problem of this
approach is the loss of information during the summarisation of
the direct trust values to only one value. For example Reiter [4]
showed a possible attack in the model of Beth. In this attack only
one bad node is able to manipulate the calculated trust by
inventing new nodes with extreme good or bad trust values.
Furthermore, it is impossible to recognize that all these trust Definitions 2.
values are built up by only one malicious node. This is because
the trust information is cut back. To justify the recommended information we introduce reliability
as the probability that the given trust-information was reliable
Later on several models for calculating trust on the base of (def. 2 (5)). If the past experiences have no statistically relevance
recommendations have been presented. Josang [6] computes trust or are outdated, the reliability is not defined (def. 2 (6))
with the help of subjective probability. In this model trust is
represented as an opinion. An opinion is a triple of believe b,
disbelieve d and uncertainty u, each in [0, 1] with b + d + u = 1. b, 0.7 0.8 0.5
d and u can be calculated out of the positive and negative
experiences concerning the target of the opinion. Out of this triple
A B C D
an expectation value of the opinion can be calculated. Josang
defines a couple of operations on opinions. One of these 0.9 0.6 0.7
operations is the calculation of trust based on recommendations.
Trust in class x of one entity A towards another entity B based on
recommendations is established if there is a third entity C so that 0.4
A has an opinion that C is a good recommender. C must have an X E Y
opinion that B is trustworthy in the trust class x and the computed
expectation value of the combination of this two opinions is above
a predefined level. For the correct computation of the operations 0.4
Reliability Trust
the dependencies of the opinions must be taken into account. So
the calculation of an opinion out of two opinions differs if the two Figure 1. Network of Relations
opinions rest upon of the same experiences or not. Therefore, the
storage of all trust-information is needed. To understand the process of a trust-decision let's start with the
short example of figure 1, where X tries to make a trustworthy
3. Trust-Decisions on the Base of decision towards Y. For that reason, the figure shows only direct
trust towards Y and the reliabilities, where no direct trust towards
Randomness Y is defined. Only E and D have direct-trust-relations towards Y.
But X has a set of reliable neighbours (def. 3 (7)).
Definitions 3.
With such a given network the next stage in the trust-decision-
Definitions 1.
process is the building of a decision-tree out of the network (fig.
2, next page). First of all, the tree represents all possible paths in
In our model of trust-relations and trust-decisions we try to keep the network from the entity X to a direct-trust-relations regarding
trust-information untouched as long as possible until we need to Y. The tree is extended by branches to undefined trust-relations
make a trustworthy decision. But first, we have to make some (⊥). These braches are inserted after each entity and represent the
definitions. possibility that the entity was not reliably.
entity
next
C 0.4 E 0.6 A 0.1
certainty or
uncertainty
0.6 0.4 0.9
entity
next
D E 0.3 B 0.3
certainty or
uncertainty
0.5 0.5 0.7 0.7
entity
next
C 0.2
certainty or
uncertainty
0.8
entity
next
D 0.5 E 0.3
certainty or
uncertainty
0.5 0.7
Figure 2. Decision-Tree
If a trust decision has to be done the tree is used to choose the Looking at definition 4 (11) shows that an absolute certainty is
used trust-relation by a random selection of the path. Starting given if a direct-trust-value exists. In this case, the direct-trust is
from the root of the tree the next edge is chosen randomly. This calculated using individual experiences and for these reasons
random selection must take the weight of the edges into account. defined as certain. On the other hand, absolute uncertainty exists
One important criterion in this decision-tree is a new certainty- if no direct-trust exists and no further entities with reliability that
value C (def. 4 (8-11)), telling how probable (certain) it is if a may recommend trust-information. The otherwise-alternative in
trust-decision is started to reach a direct-trust-relation and not definition 4 (11) will be specified later because different
calculation-strategies are possible.
"⊥".
The transformation of a trust-value-network (fig. 1) to the
The uncertainty in that decision lies in the fact that recommended
decision-tree (fig. 2) is best understood if the algorithm of the
information may be not reliably and therefore no prediction of the
trust-decision is clear.
given trust-information is possible.
Definitions 4. Definitions 5.
The trust decision in def. 5 (12, 13) is always a decision which complexity of the calculation is obviously exponential. Since the
depends on the trust relation in combination with the concrete calculations of the certainties are essential for the process of the
trust-question ϑ which tells if the trustee trusts the trusted. The decision-tree, the process itself has exponential complexity.
algorithm in def. 5 (14) start with the trustee entity (line [2]). It Let's go back one step and reconsider the meaning of the
runs a loop until an entity is reached with direct-trust regarding certainty-value of an entity towards a target-entity (def 4). This
the target entity (line [3]). If the termination condition has not value gives the probability not to make the trust-decision on the
been reached two things have to be done. First choose the next base of a undefined trust-relation, but on the base of a direct-trust-
entity (line [4]). This choice takes the certainty-value of the sub- relation. If we call the opposite of certainty uncertainty, the
tree of each entity as a weight into consideration. In the second uncertainty gives the lower bound of possibility to make the trust-
step, a random number is compared with the reliability of the decision with no secure information. The value is the lower bound
selected entity (line [5]). If the random value is smaller one because this probability is only reached, if all entities recommend
assumes the reliability of the entity. If the value is higher, one in good faith but the probability may be higher with malicious
assumes that the entity in not reliable and therefore any given entities. The higher the uncertainty the more useless is the start of
trust-information of the entity is expected as questionable. In this the decision-algorithm. Therefore, high certainty-values are the
case the trust-decision (decideTrust) has to be taken using an aim of the decision-process. But with exponential complexity the
undefined trust-relation ⊥ and the trust-question ϑ. This is in most calculation may be useless too.
cases a random decision.
In this section we try to reduce the complexity of calculation. For
To prevent loops, further choices may not take visited entities into this, we call the certainty on the base of the calculations in def 7
consideration (line [6]). The loop continues with the chosen entity the reference certainty-values. We try to reduce the complexity in
(line [6]). If a node with direct-trust relation has been reached two ways: The first solution limits the maximum number of hops
(line [3]), the trust-decision (directTrust) has to be taken using to the target-entity. The second solution limits the minimum
this selected direct-trust-relation and the trust-question (line [7]). certainty of a sub-tree. With these limitations, the calculated
Two things are still open at this point. First of all the final certainties will be higher because sub-trees will be removed with
definition of certainty in def 4 (11) has to be more precise and additional unreliability. In the next-subsections we try to find out,
secondly the way a choice is done in def 5 (15, line [04]). The how much the reductions lead to inaccurate certainty-values.
best way for the selection would be to choose always the next
entity with the highest certainty of the sub-tree. The calculation of 4.1 Maximum Hops
the certainty in def 4 (11) has to be adjusted in the following way: To limit the decision-tree to a maximal number of hops, some
definitions of def 4 have to be adjusted with a depth-factor:
Definitions 6.
But picking up always entities with the highest values has a big
disadvantage. In identical trust-decisions always the same entities
are involved. For that reasons this strategy would lead to a higher
sensitivity against malicious entities. A better way for the choice
would be to pick up entities by random, weighting them by the
certainty of the sub-tree. This would increase the resistance
against malicious entities because with a certain probability, ways
are chosen which pass these entities, if such ways exist. Definitions 8.
Therefore, the calculations of the certainty in def 4 (11) will be
adjusted with def 7 (17) using def 7 (16). To see the influence of these new restrictions on the certainty-
values several simulations have been run. Because of the
exponential complexity of the calculation of the reference
certainty values, the number of entities of a random network was
restricted to 20 entities with pre-initialised reliability of 0.5 to 1.
We assume that in real conditions most entities act fair and
therefore gain this high reliability.
The simulations with random networks have been run 30 times
and averages have been built. The results are displayed in figure 3
Definitions 7. (next page). The values of "without limitation" represent the
reference certainty. "Hops to target" gives the number of hops
until an entity is reached with direct-trust regarding the target.
4. Reducing the Complexity
As the calculation of the certainty of an entity towards a target-
entity depends on values of the certainties of the sub-tree (and
therefore on each possible loop free path to the target-entity), the
Figure 3. Simulation with Hop-Restriction Figure 4. Simulation with Certainty-Restriction
Watching the certainty values of the simulation without a branch only on the base of the product of the recommendation-
restriction, one can see that even with the high initial reliability values, if this "less-than"-certainty value falls below the limit.
values of 0.5 to 1 the certainty passes the 0.2-line after 8 hops To choose minimum certainties which have a similar effect than
already. This gives a clear indication that recommendation- the limitation of maximum hops one has to choose 0.4 to be
information is not the base of the trust-decision after very few comparable with 6-hop-limit and 0.3 to be similar to with an 8-
hop-distance (in the majority of the cases). A limitation to 8-hop- hop-limit (fig. 4).
recommended information from this point of view seems to be But compared to the limitation of the maximum hops this
rational at first sight. limitation is slightly less effective concerning the reduction of the
Let's see how the max-hop-restriction has influence in the computational period: In the case of a minimum certainty of 0.4
certainty. The certainty falls to zero, if the distance to the target- the calculation is only speed up by 34 (compared to 107 with 6-
entity is higher than the maximal number of hops. Limiting to 8- hop limitation) and at a minimum certainty of 0.3 by only 9
hop distance keeps the certainty-values in a 10%-region (compared to 14 with 8-hop limitation).
(absolute) from the reference value until this value passes the 0.2- Similar to the max-hop-limitation, this approach of reducing the
line. A restriction to 8-hops seems (from this point of view) complexity has no effect in worst-case running time. In dense
rational likewise. networks both methods will have nearly no effect.
How has the complexity changed with the restriction to max-hop-
distance? In worst case, if all entities are inside the max-hop- 5. The Influence of Malicious Entities
distance, the strategy has no effect. It is still exponential. But in One reason to make the trust-decision on the base of random
random conditions the restriction has a positive effect. In our choices using a decision-tree was the resistance against malicious
simulation with random trust-relation-networks the calculation entities. To prove this assumption another simulation series was
was with a 6-hop-limit 107-time faster and with an 8-hop-limit started.
14-time faster. Out of the 20 entities in the network, a number of malicious (or
bad) entities recommend false information. In one scenario, all
4.2 Minimum Certainty malicious entities recommend better reliability-values than given.
To limit the minimum certainty, only def 4 (10) has to be adjusted This enhances the chance to choose a fake sub-tree given by the
in the following manner: malicious entity. In the second scenario, all malicious entities
report worse reliability-values than given. This reduces the chance
to choose this sub-tree and in worse case the only possible paths
to a direct-trust-value. In figure 5 the results are reported. By the
(statistically seen) small number of runs, some results can only be
Definitions 9. explained with the unfavourable distribution of the malicious
entities in different simulation-scenarios. But some results can be
identified.
If the certainty of a branch falls below a given limit, its certainty
is set to zero. One problem in this definition lies in the fact that Obviously the influence of better values is smaller in this
the calculation of certainties of the sub-tree is still needed and simulation, because the initial reliability-values were already
therefore no benefit is given. But it is possible to cut down the high.
tree with breadth-first-search from the root of the tree, calculating The difference between the reference value and the manipulated
not with definite values but with "less-than" values. In best-case value can be interpreted as the probability that a malicious entity
the certainty of a sub-sub-tree may be 1. This value gives an was reached during the process of selecting a direct-trust-value.
upper bound, which will be adjusted if the next level of the
breadth-first-search is reached. At the end it is possible to remove
One problem with this certainty-value lies in the fact that its
calculation has exponential complexity and therefore can only be
declared as a reference value. Reducing the decision-tree by
limiting the max-hop-distance or by restricting the minimum
certainty have positive effects on the calculation-speed but have
still exponential complexity in the worst case.
7. REFERENCES
[1] Fusenig, Volker Computable Formalism of Trust in Ad hoc
Networking, Diploma Thesis, University of Trier, FB IV-
Computer Sciences, Germany, May 2005
[2] Dewan, P. and Dasgupta, P. Trusting Routers and Relays in
Ad hoc Networks, First International Workshop on Wireless
Security and Privacy (WiSr 2003) in conjunction with IEEE
2003 International Conference on Parallel Processing
Workshops (ICPP), Kahosiung, Taiwan, pp. 351-358,
Figure 5. Influence of Malicious Entities October 2003
Therefore this difference represents the probability that the trust- [3] Pirzada, A. and McDonald, C. Establishing Trust in Pure
decision was made on false information. Ad-hoc Networks, Proceedings of the 27th conference on
Australasian computer science, Volume 26 (ACSC2004),
This difference seems to be independent of the number of hops to Dunedin, New Zealand , pp. 47-54, 2004
the target-entity but is related to the number of malicious nodes.
But this is an expected behaviour: If more of the nodes are [4] Reiter, M. and Stubblebine, S. Authentication Metric
malicious, one might expect that in average more of the paths pass Analysis and Design, ACM Transactions on Information and
one malicious node. More important is the fact that in statistically System Security, Vol. 2, pages 138-158, 1999
paths are chosen, which do not pass these nodes. [5] Beth, T., Borcherding, M. and Klein, B. Valuation of Trust in
Open Networks, Proceedings of the 3rd European
6. Conclusions Symposium on Research in Computer Security (ESORICS),
In this paper we presented a strategy to make trust-decisions on Brighton, UK, pp. 3-18, Springer LNCS 875, 1994
the base of recommended direct-trust-information trying to
[6] Josang, A. A Subjective Metric of Authentication,
minimise the influence of malicious entities. This is done by using
Proceedings of the 5th European Symposium on Research in
all recommended direct-trust-information in a random selection
Computer Security (ESORICS'98), Springer LNCS 1485,
process and use only the finally chosen direct-trust-value to
1998
evaluate the trust-decision.
[7] Josang, A. A Logic for Uncertain Probabilities, International
Because of the randomness in this selection process, paths without
Journal of Uncertainty, Fuzziness and Knowledge-Based
the influence of malicious entities are chosen statistically. The
Systems, 9(3): 279-311, 2001
new introduced certainty-value gives an indicator of the
reasonability of trust-decisions on the base of the recommended [8] Marsh, S. Formalising Trust as a Computational Concept,
trust-information. One can state that decisions on such a base are PhD Thesis, University of Stirling, UK, 1994
unreasonable after a very short hop-distance towards the target (6-
8 hops), even under good conditions (very high recommendation-
trust-values).