1	Formalization of Dynamic Trust and Uncertain Evidence for User Authorization Yuhui Zhong Department of Computer Sciences, Purdue University zhong@cs.purdue.edu Prof. Bharat Bhargava Support by NSF grant IIS-0209059 and IIS-0242840.
2	Motivation Authorization mechanisms are needed for secure information access by a large community of users in an open environment role assignment + RBAC Uncertain evidence is considered because: An evidence issuer may not be 100% sure about the evidence she testifies It may be difficult for her to precisely determine the degree of her belief Dynamic trust is needed because: Holding evidence does not necessarily certify a user’s good behavior Integrating dynamic trust with role assignment prevents a notorious user from gaining more privilege
3	Problem Statement Develop models and mechanisms for user authorization based on uncertain evidence and dynamic trusting belief This problem is investigated via three thrusts: Modeling dynamic trust Modeling uncertain evidence Integrating them with role assignment for user authorization
4	Trust enhanced role assignment architecture (TERA)
5	Trust enhanced role mapping server (TERM)
6	Outline of presentation Problem statement Overview of three research directions Ö Research tasks Related work Findings A trust model (detail) Uncertain evidence (discussed in prelim exam) Integrating them with role assignment (discussed in prelim exam) Conclusion and future work
7	Modeling dynamic trust (background) Trust is a multidimensional concept. Trusting belief is a major part of this research Trusting belief is context specific Trusting belief has two perspectives Action vs. information Building trusting belief is a subjective process no uniform criteria to evaluate a single observation no standard approach to update the trusting belief given an observation sequence This research studies the process of building trust via interactions between two entities After each interaction, a truster rates the performance of a trustee and updates her trusting belief about the trustee.
8	Modeling dynamic trust (Research tasks) Identifying the aspects of social trust that shall be included in the computational model Social model: five conceptual types Computational model: trusting beliefs Representing the concepts in social trust Trusting belief, context, strategies Developing mechanisms to build trusting belief The first-hand information (direct experience) The second-hand information (reputation & recommendation)
9	Related work (McKnight’s social trust model) Results from surveying more than 60 papers across a wide range of disciplines Five conceptual trust types Trusting behavior Trusting intention Trusting belief Competence, benevolence, integrity, predictability Institution-based trust Disposition to trust.
10	Relationship between McKnight’s model and TERA elements
11	Related work (Computational trust models) Formalizing Trust as a Computational Model [Marsh, Ph.D. Thesis'94] (University of Stirling) Trust Management Through Reputation Mechanisms [Zacharia/Maes, Applied Artificial Intelligence Journal'00] Reputation and Social Network Analysis [Sabater/Sierra, AAMAS'02] Supporting Trust in Virtual Communities [Abdul-Rahman/Hailes, HICSS'00] Distributed Reputation Management for Electronic Commerce [Yu/Singh, Computational intelligence'02] Computational Models of Trust and Reputation: Agents, Evolutionary Games, and Social Networks [Mui, Ph.D. Thesis'02] (MIT) Bayesian analysis
12	Research findings A computational trust model for user authorization is developed (chapter 3) Trusting belief, disposition to trust, and context are represented Trusting belief in competence and integrity: belief value & predictability Disposition to trust: policies & priori trusting beliefs Context: representation & functions relating contexts Four operations are defined. Belief formation: building trusting belief based on the direct experience with the trustee in the specific context Reputation aggregation: aggregating the trusting beliefs about the trustee from various trusters building and testing initial trusting beliefs building and testing continuous trusting beliefs
13	Research findings Methods and algorithms to implement four operations are designed. They are based on: Truster’s direct experience with the trustee in the specific context Reputation about the trustee in the specific context Truster’s direct experience with the trustee in similar contexts The most common belief about the trustees encountered in the specific context Truster's priori trusting belief For competence trusting belief, belief formation and two reputation aggregation methods are designed based on sampling theory. For integrity trusting belief, the BDES method is developed based on techniques in time series analysis Representations, methods and algorithms designed are implemented in reputation server and trust information management component of TERM server.
14	Observations Two sets of experiments are conducted to evaluate the methods to build trusting beliefs (chapter 4) The first set of experiments evaluates the performance of two competence reputation aggregation methods under two scenarios Reputation aggregation methods: CRE-K and CRE-A Scenarios The truster distribution satisfies the assumptions in CRE-A The assumptions do not hold Experiments compare the reputation values computed by each method
15	Observations Results show: (1) The CRE-K method works well under both scenarios; (2) The CRE-A method produces satisfactory results only if the required assumptions are satisfied; The second set of experiments evaluate the performance of BDES method with other three existing methods in terms of the accuracy of predictions generated under five behavior patterns. Behavior patterns: random, stable, trend, jumping, two phase Experiments compare the absolute and relative errors between real ratings and predictions generated by each method Results show: (1) For random behavior pattern, none of the evaluated methods is able to produce reasonable good results. (2) For stable behavior pattern, all methods produce similar good results. (3) For trend, jumping, or two-phase behavior patterns, BDES outperforms the other three ones.
16	Modeling uncertain evidence (Research tasks) Designing evidence representation that enables issuers or evidence relying parties to express their uncertain beliefs about the evidence Supporting subjectivity in evidence interpretation Translate an issuer’s belief to the belief of an relying party Combine evidence from different issuers. Developing method to infer uncertain belief Evidence conveys: belief about the ground atomic formula A = v_e Role assignment policy specifies: required belief about a policy expression Aθv_p θ: {>, <, =,≠, ≤, ≥, …} Infer belief about Aθv_pbased on belief about A = v_e
17	Related work (Formalisms to handle uncertain information) Certainty factors [Shortliffe'76] Bayes Network [Pearl'82, Jensen'96] Incidence calculus [Bundy'85] Probabilistic Logic [Nilsson'86] Fuzzy logic and possibility logic [Zadeh'75, Dubois/Lang/Prade'94] Dempster-Shafer Theory [Dampster'68, Shafer'76] Subjective Logic [Jøsang'01]
18	Research findings (Chapter 5) Evidence statement is designed to convey information and the associated uncertain beliefs. It is interpreted as a basic probability assignment on a focused frame of discernment in the Dampster-shaferian framework. An evidence rewriting rule is developed to translate uncertain beliefs It is based on the discounting operator
19	Research findings (Chapter 5) Three methods are developed for inferring uncertain belief about a policy expression under various circumstance Conservative estimation method: maximizes the disbelief and minimizes the belief Other two methods: estimate the expected value of an uncertain belief based on the principle of insufficient reason or priori probability mass function Representations, methods and algorithms designed are implemented in evidence rewriting and role assignment components of TERM server.
20	Authorization based on uncertain evidence and dynamic trust (Research tasks) Designing a declarative language that allows a policy maker to express the evidence and trust requirements for assigning a role Defining the evaluation semantic on how to make role-assignment decision based on the provided evidence set and policies. Developing algorithms based on the evaluation semantics Integrating the uncertain evidence, dynamic trust and role assignment and build an authorization framework for secure information access in open environments
21	Related work Role-based access control NIST RBAC proposals Reference implementation Role assignment Design of A Role-based Trust-management Framework, [Li/Mitchell/Winsborough, IEEE Symposium on Security and Privacy'02] Access Control Meets Public Key Infrastructure, Or: Assigning Roles to Strangers, [Herzberg/Mass/Mihaeli/Naor/Ravid, IEEE Symposium on Security and Privacy'00] (IBM) Using Digital Credentials on the World-Wide Web, [Winslett/Ching/Jones/Slepchin, Journal of Computer Security'97] (UIUC)
22	Research findings (Chapter 6) A role assignment policy definition language that allows a policy maker to specify the requirements on dynamic trust and uncertain evidence is developed The evaluation semantic is designed. An algorithm is developed based on the semantic for role assignment TERA framework is developed, which includes all the proposed methods and algorithms in this thesis. A prototype of TERA has been implemented
23	Outline of presentation Problem statement Research directions A trust model (detail) Ö Overview of trust model Build trusting belief in competence Build trusting belief in integrity Uncertain evidence (discussed in prelim exam) Integrating them with role assignment (discussed in prelim exam) Conclusion and future work
24	Trusting beliefs and context Trusting beliefs A truster’s subjective belief about certain attribute of a trustee Competence trust vs. integrity trust Competence trust: trustee’s capability Integrity trust: trustee is cooperative & honest Initial trust vs. continuous trust Initial trust: trusting belief formed before a truster and a trustee have interactions (in a specific context). Continuous trust: trusting belief formed after they interact. Measure: belief value & predictability Belief value: degree of belief, a number Î [0,1] Larger value, more trustworthy Predictability: confidence in the belief value, a number Î [0,1] Smaller predictability, more confident
25	Context Context A truster maintains one integrity trust per trustee A truster maintains one competence trust per trustee for each context Context is defined from the perspective of competence Context = <contextId, cType, cLevel> contextId: unique identifier cType: the type of competence needed by the context cLevel: measure of competence needed by the context
26	Context S_c: the universe of all types of competence of interest {C₁, C₂, …, C_n}. cType assumes a value from S_c Ex: {cooking, teaching, writing, …} M_c: the measurement of a competence type C_..cLevel assumes a value from M_cwhere cType = C. Ex: M_cooking = {bad, average, good, excellent} A partial order <: M´M® {true, false} A function dis: M ´M® [0,1] Context related functions
27	Representation of context and trusting belief
28	Four operations defined by the model Belief formation Reputation aggregation Build and test initial trust Build and test continuous trust
29	Implementation of operation 3 and 4 Methods to build a trusting belief are based on: Truster’s direct experience with the trustee in the specific context Reputation about the trustee in the specific context Truster’s direct experience with the trustee in similar contexts The most common belief about trustees encountered in the specific context Truster's priori trusting belief Discuss how to build initial competence trust Other cases are presented in chapter 3
30	Seven methods to build competence trust M1: Form trusting belief based on direct experience about u₁in the specific context c M2: Compute trusting belief based on direct experience about u₁ in contexts with higher requirement than c. Use the maximum belief value and minimum predictability Use hContxt function M3: Compute trusting belief based on direct experience about u₁ in contexts with lower requirement than c. Use the minimum belief value and maximum predictability. Use simLCTX function M4: Request u₁’s competence reputation in context c.
31	Seven methods to build competence trust M5: Use the most common belief value of t₁ about trustees encountered in c. Most common belief: mode of belief value histogram Use truster’s uncertainty handling policies in multimodal situation M6: Use the most common belief about all trustees encountered by all trusters in c. Considered only if M4 and M5 can not be used M7: Use priori competence trusting belief specified in the truster’s local or global profile.
32	Methods and their priorities A candidate method set: the methods considered in a specific situation A method is applicable : It is in the candidate method set Its precondition holds Priority of methods The order that methods are considered Partial order defined by the model. It is extended to a total order based on truster’s method preference policies
33
34	Testing tables
35	Global and local profiles Use to personalize trust model Each truster has one global profile and can have one local profile for each context. The content in a local profile overrides that in the global one. Content: Priori trusting beliefs Policies that affect building trusting beliefs Method preference policies Uncertainty handling policies Imprecision handling policies Parameters configuring methods to building trusting belief
36
37	Competence belief formation Assumption: Competence ratings are viewed as samples drawn from a distribution with steady mean and variance Competence belief formation is formulated as a parameter estimation problem Use normal distribution to approximate underlying distribution Competence belief value: Estimated mean It is also the mode & expected value Predictability: Construct a 90% confidence interval Interaction number < 45: Student distribution Otherwise: Normal distribution Length of confidence interval
38	Competence reputation aggregation Assumptions: Existence of a central reputation server Trusters are cooperative Based on trusting beliefs instead of ratings Trusters providing trusting beliefs are subjective Reputation aggregation methods shall eliminate the effect of subjectivity and output a result close to the trusting belief the reputation requester would have obtained if she had directly interacted with the trustee.
39	Competence reputation aggregation
40	Competence reputation aggregation Subjectivity of t_i(trusting belief provider) from the perspective of t_(reputation requester) is formulated as the deviations between means and variances of two rating sets given by t_iand t_ Use the following estimators
41	Analytical result If deviations are known and k is large For the first estimator of s_* (additivity of c2 + fisher’s result) For the estimator of m_* (central limit theorem)
42	Reputation aggregation method CRE-K The prerequisite: The reputation requester has a set of commonly rated trustees with each of the trusters who provide the trusting beliefs. Unknown deviations are determined by minimizing MSE of two sets of trusting beliefs This method use estimator
43	Reputation aggregation method CRE-A Assumptions: Deviations of means are independently drawn from an uniform distribution. Deviations on variance are independently drawn from one distribution. It is equally like that It is easy to verify
44	Reputation aggregation method CRE-A From the strong law of large numbers theorem This method use estimator
45	Integrity belief formation method Ratings are not from the same distribution. Integrity trusting belief is defined as prediction on a trustee’s next behavior based on previous ratings A prediction is verified by the next rating Predictability is defined as mean square error (MSE) between the previous predictions and ratings
46	BDES method BDES method is designed for prediction It considers the trend in behavior Common case: double exponential smoothing formula Initial condition:
47	BDES method (cont’) In the case a prediction ³ 1 or £ 0 Update α,β Belief value and predictability
48	Experimental study on BDES Goal: evaluate the accuracy of predictions generated by BDES method and other three methods under five behavior patterns. Experiments: Generate rating sequences based five behavior patterns Apply four methods on each rating sequence to get predictions Measure the accuracy of predictions for each behavior pattern Measurement: absolute and relative errors between predictions and ratings The distribution of errors is plotted using cumulative frequency figure.
49	Methods evaluated
50	Generate ratings based on behavior patterns Behavior patterns used in the experiments
51	Generate ratings based on behavior patterns Assumption: a rating is determined by the integrity trust about a trustee and is influenced by some unpredictable factors. The i^this generated using It falls into [f(i) – 0.1, f(i) + 0.1] with probability of 90%. 100 ratings are generated for each behavior pattern
52	Absolute errors under random pattern
53	Absolute errors under stable pattern
54	Absolute errors under trend pattern
55	Absolute errors under jumping patterns
56	Absolute errors under two-phase patterns
57	Conclusions For random behavior pattern, none of the evaluated methods is able to produce good results. For stable behaviors, all algorithms produce very good results. More than 94% of the predictions have an absolute error less than 0.2. For the trend, jumping, or two-phase behavior patterns, the BDES method outperforms the other three. Among its predictions, 93% to 99% have less than 0.2 absolute error. The corresponding percentages of the other methods are 10% to 40% lower depending the behavior patterns.
58	Outline of presentation Problem statement Research directions A trust model (detail) Uncertain evidence (discussed in prelim exam) Integrating them with role assignment (discussed in prelim exam) Conclusion and future work Ö
59	Thesis Contributions A computational trust model for user authorization Representations of social concepts Methods to build and test trusting beliefs Belief formation and reputation aggregation algorithms A guideline for the development of new adaptive trust building algorithms Impact Selecting co-operate partner, forming coalition, and choosing negotiation protocols or strategies in e-commerce Choosing reliable resources in peer-to-peer systems and designing secure protocols for ad hoc networks
60	Thesis Contributions Uncertain evidence for user authorization Evidence statement An evidence rewriting rule Three opinion inference methods User authorization based on dynamic trust and uncertain evidence A role assignment policy definition language The evaluation semantic TERA (trust-enabled role assignment) framework and prototype Impact Providing an adaptive authorization framework. Preventing misuse of enterprise information through authorized access Providing a test bed for experimental studies on user behavior, trusting building algorithm etc.
61	Other Research Results Counter measure of shill bidding An equilibrium bidding strategy for honest bidders in online English auction in a risk neutral setting A shill counteracting bidding strategy (SCBS) Study on preferable auction types in cheating environment Analytical comparison on English, first price sealed and Vickrey auctions from both sellers’ and bidders’ point of view for special cases Experimental study to explain the popularity of English auction over the Internet
62	Future Work Trust model Develop the methodology to evaluate different trust models Formulate and investigate the problem whether a dominant method exists for building trusting belief Investigate the problem of preventing and detecting attacks to reputation systems
63	Future work Role assignment Extend the role assignment policy declaration language to support more data types and operators Develop mechanisms to enforce the trust requirements throughout the lifetime of an assigned role Support static separation of duty with or without the role hierarchy
64	Future work Privacy and trust The problem is to quantify the tradeoff between privacy and trust Develop measures and mechanisms to assess privacy loss and trust gain Design algorithms to select a set of information that minimizes the loss of privacy while achieving the targeted trust level. Develop negotiation protocols between a client and server Develop PRETTY system