Negotiation of Personal Information

Information, Rules, Constraints, and Facts

The following definitions will introduce the terms personal information, rules, and facts. These terms will be used later in order describe and define algorithms, and explain the concept of negotiating sets of information.

1. The finite set of personal information
contains all data elements , that can be the subject of negotiation.

In the context of negotiation, a data element is used as an identifier for a particular piece of information. A data element can represent any kind of information, such as a numeric value (e.g., a person's age), text (e.g., a person's name) and graphics (e.g., a person's image or fingerprint).

1. A rule r specifies the circumstances under which a set of information can be accessed. The rule r is defined by a pair
that denotes a set of information with , and a set of constraints defined on . Each constraint , represents a particular condition that must be met in order to get access to .

The constraints of a rule specify the conditions that must be met by the requestor. Constraints can be unary, or a relation on values for a single variable; binary, or a relation on values for a pair of variables; or n-ary, meaning that it simultaneously limits the possible values of n variables [Stefik95] . A simple example of a rule is to use the above definition in order to control access to various items. Let's assume a family sets up rules to control access to their cars. The rule

specifies that access to the dataset

can only be granted when the constraints are satisfied. In this case, it means that the convertible can only be driven by the parents when it is summer.

1. The facts f are associated with a request for information. The facts f are defined by a pair
. The set contains the data elements demanded by the requestor. The set denotes the conditions under which the elements of are requested. contains name-value pairs , in which denotes the name and the value of a particular item.

The facts formally describe a request for a set of data-elements and the conditions under which this request is made. The owner of the requested data-elements can evaluate the facts and match them against his rules. If the facts satisfy a rule, the owner may grant the requestor access to the requested information. An example of facts could look like

, which can be checked against the simple rule example ( ) as introduced above.

1. The set
denotes all possible combinations of facts of a particular domain. The domain represents the context, the possible name-value pairs, value ranges, and combinations of data elements of a particular application.

Rulesets and their Representation as Trees

The notion of a rule was introduced to define the conditions under which a set of information can be accessed. In order to express such constraints for various sets of information, more than one rule needs to be defined. Various rules are grouped together in rulesets.

1. A ruleset
denotes a set of rules.

In definitions and equations, we will use R throughout this document in order to refer to a ruleset. However, in order to visualize the concept of rules and rulesets we will also use a graphical representation of rulesets. According to Definition (2) on page 62 , a rule is a pair that defines constraints on a set of information. Instead of representing various rules by their definition, we want to use the notion of a tree to graphically express a ruleset. The following example demonstrates this.

Assume a person X has three rules to control access to three different sets of information:

These rules can be grouped into a ruleset

. As one can see, and specify the same constraint . Throughout this chapter we will represent rulesets like as trees 2 (see Figure 4-1 ).

Tree representation of a ruleset R.

Each of the three rules is represented by a path from the root

to one of the leafs of the tree (see arrows in Figure 4-1 on page 63 ). The leafs of the tree represent the data sets , with . The constraints lie in-between the root and the leafs. The tree representation is very useful in order to check the facts against the rules. This process is called rule evaluation.

Rule Evaluation

Rule evaluation is the process of matching facts against rules. When a rule was found that is matched by the facts, access to the requested information can be granted. In order to match a rule, the facts need to meet two requirements. Firstly, the facts must satisfy all of the rule's constraints.

1. The constraint-matching function
is a boolean function that indicates whether a name-value pair of the facts f matches a certain constraint of a rule r.

Definition (6) specifies two functions, one for unary constraints (6.1) and one for n-ary constraints (6.2) with

. In case of the latter represents a vector with n elements. (For simplicity, throughout the next sections we will only use the constraint-matching function for unary constraints.)

Secondly, the requested information as specified in the facts must be a subset of the information specified in the rule. This means, that the facts can only ask for data elements that are part of the rule's set of information. With this in mind, we can formally define the matching of a rule:

1. Given facts
match a rule , if:

To summarize the contents of Definition (7) , facts match a rule, when all of the rule's constraints are satisfied and the requested data elements (as specified in the facts) are covered by the rule. This has several implications. First of all, facts can contain more information than necessary to satisfy the constraints. Secondly, the rule can cover more data elements than requested in the facts.

A Sample Rule Evaluation

Before describing how the previous definitions of rules, facts and rule evaluation can be used for negotiation, we want to take a look at a sample rule evaluation. Assuming a family of four (parents, two children) owns three cars (e.g., a convertible, a truck, and a sedan) and wanted to set-up rules for the usage of these cars. The rules specify the circumstances under which a family member can access and use one of the cars:

The rules specify that the convertible can only be used by the parents when it is summer. The other vehicles can be used all year long, by any family member with a drivers license. These rules can now be used to control access to the familiy's vehicles. 3 Assume it is winter and one of the parents wants to use the convertible for a shopping trip. The facts of her request then is:

The service, which matches the facts against the rules, cannot grant her access to the convertible because it is winter. Because she cannot wait until summer arrives, she issues a new request, resulting in the facts:

Facts matches rule in ruleset.

The service grants her access to the truck, because the facts of her request match

. This is indicated with the shaded part of Figure 4-2 on page 66 . However, the mother needed to issue two requests in order to gain access to one of the vehicles. If the service would have been a little smarter it could have offered her one of the other cars (if available) right away, after her initial request could not be satisfied. In order to support such a smart behavior, i.e., negotiate with the requestor, the service needs to know how to create a reasonable counter-offer which the requestor can then accept or reject.

Metrics and Distances

Our approach to find a reasonable counter-offer is to measure the distance between the individual rules in the ruleset and the facts. The rule with the minimum distance is considered the closest rule and is used to produce a counter-offer. In order to do so, we need to define a metric which specifies the distance between a rule and facts. Based on this metric, we can then measure how well the facts match particular rules. In order to compute the rule with the minimum distance, it needs to be determined how well the facts satisfy the constraints of the rule and to what degree the sets of information of the rule and the facts overlap. Firstly, we define a function that measures to what degree the facts satisfy a rule constraint.

1. The function
denotes the distance between the constraint of an individual rule and the facts . It is defined, such that:

Secondly, we need to measure how well the set of information requested overlaps with the set of information covered by the rule.

1. The function
denotes the distance between sets of information of a rule r and facts f. It defines a quantitative measure of how well sets of information match:

We will call the distances of Definition (8) and Definition (9) the local distances, which are the basis to compute the overall distance between a rule and the complete facts. The functions for computing the local distances represent a set of functions with specific characteristics instead of a function that specifies how to do that. This was done in order to prevent limiting this concept to a particular field of applications. Real implementations of such functions highly depend on the context and characteristics (e.g., number of variables, constraint types, and value ranges) of the respective application.

1. The function
maps the distance between a rule , and facts onto the set of positive integers. is defined as follows:

The overall distance is computed by accumulating the local distances. The terms

and in Definition (10) are weights which are related to the n constraints and the information set of a rule. Weights can be used to emphasize the importance of local distances and allow to specify which parts of the rule are more important than others, while searching for the closest rule. This measure can now be used to determine a reasonable counter-proposal from facts and a ruleset. If the facts f are checked against a ruleset , and there is no such that , the rule with

best matches the facts. Facts that do not completely match a certain rule will cause the distance function to return a value greater than zero. The rule with the lowest distance to the facts is used to create a counter-offer. Throughout the remainder of this chapter, we will call such a rule the closest rule. The ruleset and the distance function

represent the negotiation knowledge base as introduced in Section 2.2.3.2 on page 16 .

Depth-First-Search

We now want to define a method for finding a counter-offer. The easiest way to do this is to compute the distances of all rules to the current facts, i.e. brute-force exhaustion search. The rule with the lowest distance will then be used to produce the counter-offer. Since this approach is not very efficient, we want to explain now a more efficient way to find the closest rule. Our approach is based on the idea to represent the ruleset as a tree as shown in Figure 4-1 on page 63 , and based on the way trees can be searched. We assume here that the reader is somewhat familiar with graph and trees. One of the basic methods for searching in trees is Depth-First-Search (DFS) [Stefik95] .

A Depth-First-Search (DFS).

In a DFS, the search processor tries to find a solution to the search problem by traversing the tree. At each level of the tree (including the root), the processor checks whether the current node is the solution. If so, DFS terminates and a solution (i.e., there can be more than one solution in the tree) was found. If the node does not represent a solution, the processor descends to the first child of the node, and then to the first successor of that node. If DFS reaches a leaf it backtracks to the nearest ancestor and tries the next child. This is called depth-first because DFS plunges quickly downward into search space (i.e., DFS visits child nodes before visiting sibling nodes). Figure 4-3 illustrates a DFS for a solution. The numbers in the nodes indicate the order in which the nodes are visited. Node number seven represents the solution.

DFS is the basis for our approach to find the closest rule. Each rule in a ruleset-tree lies on a path from the root of the tree to a leaf. Each node on this path represents a constraint or the information set of the particular rule. As defined in the previous sections, the distance between a rule and the facts is the sum of all local distances (e.g., constraints, sets of information). Using the concept of DFS, the distance between a rule and the facts can be computed while traversing the tree. Figure 4-4 illustrates how DFS can be used to find the closest rule. The text in the nodes specifies the local distance (e.g., constraint distance or information set distance). The distance between a rule and the facts is the sum of all local distances on a path. As one can see in Figure 4-4 , DFS will first descend down into the tree, all the way to the first leaf. At this leaf, the accumulated distance is the distance of the currently closest rule. From there, DFS proceeds but only visits nodes as long as the accumulative distance of local distances is less than the distance of the currently closest rule. The problem of this approach is that in order to get to the comparison criteria of a currently closest rule, the search process always needs to traverse the left-most path. This can be avoided with a slight modification of the search process.

Finding the closest rule (DFS).

Assume that we can parameterize DFS by defining a maximum distance for the closest rule. This search parameter specifies that the closest rule must have a smaller distance to the facts than specified by the maximum. We can use this maximum during the search process in order to skip parts of the tree in the search for the closest rule. This is called pruning and occurs when the accumulated local distances are greater than the specified maximum. The effect of our slight modification is shown in Figure 4-5 which illustrates that now the search process needs to visit fewer nodes. This can be especially important in larger rulesets in order to cut down the time spent on searching for the closest rule. However, the modification of the search for the closest rule could have the effect that a closest rule may not be found if its distance is greater than the maximum distance parameter. If no closest rule can be found, the service has to reject the request or search again with a modified maximum.

Finding the closest rule (DFS, maximum distance (<4) for closest rule).

Rule Types and Canonical Accept-Trees

APPEL rules (see Figure 3-3 on page 39 ) provide a way to define conditions under which the rule is matched by a P3P proposal, similar to the constraints of a rule in our framework. In addition to this, APPEL rules specify a behavior which specifies the next action to be taken by the user agent when the rule is matched. These behaviors are seamless-accept, seamless-reject, info-prompt, and warn-prompt. Whereas the rules with a seamless behavior are very useful for automated negotiation, the prompting behaviors require the interaction with the user. As you can see in our framework, rules define conditions under which a set of information is accessible. Thus, rules in our framework can be seen rules with a seamless-accept behavior. The respective ruleset is what we call a canonical accept-tree. Any rule in such a tree can be used to produce a counter-offer because it specifies acceptable conditions. In comparison, only APPEL rules with a seamless-accept behavior can be used to produce a counter-offer, all other rule types require user interaction or specify conditions under which a request should be rejected. Secondly, there is the issue of the structure of APPEL rulesets. The rules in an APPEL ruleset are ordered. APPEL rule evaluation checks the rules against a P3P proposal in the order in which they appear in the ruleset. When a rule is matched by the facts, rule evaluation terminates and the next action of the user agent is determined by the rule's behavior. Other rules are not checked anymore. Our framework does not support ordered rules, instead it provides a metric to measure the distance between a rule and the facts. Thus, we chose to consider only rules that allow a seamless completion of the transaction (e.g., seamless-accept, and seamless-reject). Furthermore, we consider the order in which these rules appear in the APPEL ruleset. The other kinds of APPEL rules are considered during rule evaluation, which is processed before negotiation.

Thirdly, there is a chance that reject- and accept-rules overlap. This means that a reject-rule and an accept-rule could be matched by the same facts. The higher ordered rule will be matched and there is no need for the other rule to cover such cases. Although APPEL allows overlapping rules, we expect APPEL applications to prevent a user from creating such rules, or at least inform the user about such conflicts. However, we take such conflicts into consideration when converting APPEL rulesets. Taking the above mentioned in mind, we designed an algorithm for the creation of canonical accept-trees from APPEL rulesets.

Algorithm

Figure 4-6 shows the three major steps of the algorithm. In the first step, we create an empty canonical accept-tree, i.e., a tree (with a root node) which does not contain any rules. In the second step, all accept- and reject-rules are extracted from the APPEL ruleset by maintaining the order in which they appear. In the third step, each extracted APPEL rule is transformed into an internal rule format, and added or merged into the tree, depending on the ruletype. The rules are processed in their reverse order. The result of this algorithm is a canonical accept tree which contains all the accept-rules of the APPEL ruleset, and does not conflict with any of the APPEL ruleset's reject-rules. This set of accept-rules represents our negotiation knowledge base, as shown Figure 2-2 on page 13 .

Algorithm to convert an APPEL ruleset into a canonical accept-tree.

Step 1: Create an empty canonical accept tree with a root node. Step 2: Extract all accept- and reject rules from APPEL ruleset. Step 3: For each extracted APPEL rule do in reverse order: (3.1) Transform APPEL rule into internal rule format. (3.2) if type of APPEL rule is reject then Merge rule into tree by checking it against the accept-rules in the tree. else Add rule to tree.

Now that we have introduced the rather generic algorithm, we want to take a closer look at some of the individual steps. Before an XML-encoded APPEL rule can be added to or merged into the tree, it needs to be transformed into the internal rule format. This format is simply a list of constraints and the set of data elements covered by the particular rule.

Transformation of APPEL rule into internal format.

<APPEL:RULE behavior="seamless-accept"> <P3P:PROP> <P3P:USES> <P3P:STATEMENT action="r" VOC:id="0"> <DATA:REF name="a"/> <DATA:REF name="b"/> </P3P:STATEMENT> </P3P:USES> </P3P:PROP> </APPEL:RULE>

action="r" VOC:id="0" DataSet={a,b}

Figure 4-7 on page 75 shows such a transformation. As one can see on the right side of Figure 4-7 , the list only contains those attributes of the rule that specify the constraints which need to be satisfied. For clarity, we omitted any attributes of other XML-elements than the P3P:STATEMENT-element. However, APPEL rules can also refer to other elements of a P3P proposal, in which case the respective element name will be included in the constraint. The same mechanism would be used for APPEL level 2 rules, which can contain constraints on elements that are not part of the P3P syntax. After a rule was transformed it can be added to the tree, if the rule is an accept-rule. Figure 4-8 on page 76 illustrates the process of adding two accept-rules in their reverse order to a canonical accept-tree. In the first step, the second rule of the APPEL ruleset is added to the empty tree. In the second step, the higher-order rule is added to the tree. In case the next rule to be processed is a reject-rule, the algorithm does not add but merges the rule into the tree. Merging a rule means to check the reject-rule against all accept-rules that were already in the tree. These checks are performed in order to resolve conflicts between reject- and accept-rules. Figure 4-9 on page 77 visualizes how a reject- and an accept-rule are merged into a tree when there is a conflict between the rules.

Adding accept-rule into canonical accept tree.

As one can see in Figure 4-9 , the accept rule in the tree and the reject rule could both be matched by the same P3P proposal, for example: 5

<P3P:PROP> <P3P:USES> <P3P:STATEMENT VOC:recpnt="0,1,2"> <DATA:REF name="c"/> <DATA:REF name="d"/> </P3P:STATEMENT> </P3P:USES> </P3P:PROP>

In order to resolve such conflicts, the accept rule in the tree is modified. This is done by modifying the rule's constraints, such that the accept rule does not conflict with the reject rule anymore. In case the sets of information of the reject-rule and the accept-rule are not identical, a new accept-rule is added to the tree.

Merging a reject-rule into canonical accept-tree.

The added accept-rule is a copy of the original accept rule with a modified set of information. Only those data elements that are not listed in the reject-rule are listed in the new accept-rule's set of information. Merging reject-rules the way we described above assures that all accept-rules in the tree can be used to produce counter-offers. None of these counter-offers will match a reject-rule because these cases are eliminated during the conversion of the APPEL ruleset.

Combinations of Sets of Information

For clarity, we omitted a special case that can occur when dealing with APPEL rulesets. As we have mentioned earlier, the P3P syntax allows multiple statement-blocks (i.e., the P3P:STATEMENT-element) in one P3P proposal and therefore, APPEL allows the same in a rule. This leads to the problems of how to deal with combinations of sets of information. During online transactions, a P3P proposal is sent by a Web server to inform the user about the site's privacy practices. This information is encoded in machine-readable form in one or more statement-blocks.

Adding rule with multiple statement-blocks and additional information.

Therefore, we decided to treat statement-blocks as the facts, i.e., each rule in a canonical accept tree refers to the constraints on a statement-block. A P3P proposal can also contain information about an assuring party (i.e., ASSURANCE-element), and a disclosure (i.e., VOC:DISCLOSURE-element). Thus, this information can be referenced in APPEL rules, for example that a rule requires the existence of a certain assuring third party before data can be given out. This information covers the whole proposal whereas the information in a statement-block covers only the content of the statement-block. The additional information will be linked to each of the proposal's statement-block and included in the canonical accept-tree (see Figure 4-10 on page 78 ).

Extracting Facts from P3P Proposals

Similar to the conversion of APPEL rules into canonical accept-rules, facts are extracted from P3P proposals by looking at the proposal's statement blocks and additional elements. Each statement-block produces separate facts, according to our framework, which contain the information from the statement-block and information valid for the whole proposal. Figure 4-11 illustrates the extraction of facts from a P3P proposal. Each of these facts will then be separately matched against the canonical accept-tree. In addition to the information contained in a P3P proposal, facts can contain other transaction-related information not included in the P3P message, such as the type of the connection (e.g., whether it is cryptographically secure).

Extracting facts from a P3P proposal.

<P3P:PROP ...> <P3P:USES> <P3P:STATEMENT action="r" VOC:id="0"> <DATA:REF name="a"/> <DATA:REF name="b"/> </P3P:STATEMENT> </P3P:USES> <P3P:USES> <P3P:STATEMENT action="rw" VOC:purp="0,1,2"> <DATA:REF name="c"/> <DATA:REF name="d"/> </P3P:STATEMENT> </P3P:USES> <P3P:ASSURANCE service="a URL"/> </P3P:PROP>

P3P:ASSURANCE, service="a URL" action="r" VOC:id="0" DataSet={a,b} P3P:ASSURANCE, service="a URL" action="rw" VOC:purp="0,1,2" DataSet={c,d}

Distance Functions and Weights

In order to measure the distance between the facts, extracted from a P3P proposal, and a rule in the canonical accept-tree, we need to define the distance functions and specify the weights. The distance functions are used to compute the local distances constraints and the facts, and the degree of overlap between the rule's data set and the facts' data set. We chose a relatively simple approach to compute these local distances.

1. The distance function
to compute the distance between the rule's data set and the data set (facts), is defined as follows:

This definition specifies that the distance is the number of all data elements in the facts' data-set minus the number of shared data elements, if the data sets share elements. Otherwise, this function will return a large number in order to indicate a large distance. This big-M-method is very useful in this context in order to indicate that the respective rule covers a completely different dataset.

In order to define a distance function

to compute the distance between a rule's constraint and the facts f, we need to distinguish the different kinds of constraints. The kind of the constraint depends on the value-matching method specified in the rule's constraint. The following table specifies the value will return depending on the constraint.

Definition of local distance function (constraints).

Constraint-Type	Distance computation method
Wildcard-Matching: VOC:id="*"	The returned value is always 0. The facts can contain any value.
Multi-Numeric Values (one or more): VOC:purp="2,3,4"	see . Example: VOC:purp="0,1,4,5" has a distance of to the rule value VOC:purp="2,3,4". If no shared values in t facts and rule constraint, the distance is M.
String value: service="http://www.ibm.com"	0, if value-pair in facts matches string M, otherwise

Sample Negotiation

We have described how to convert APPEL rulesets, how to extract facts from P3P proposals, and how to measure the distance between a rule and the facts. Now, we want to take a look at a sample negotiation. Assume we have the following ruleset:

Sample ruleset (canonical tree).

Also assume, the OPA received a P3P proposal that results in the following facts f:

VOC:purp="1,2,3,4" VOC:recpnt="1,2,3" action="r" VOC:id="0" DataSet={a,b,c,e,f,g,h}

The facts f do not match any of the two rules in Figure 4-12 because the data sets do not match completely and some of the constraints are not satisfied (e.g., VOC:purp). However, the rules could be used to offer a counter proposal. With the definitions of the local distance functions we get the distances of the facts f to both rules.

If all the weights are set to

, rule should be chosen in order to produce a counter-offer. This counter-offer would propose access to the data set under the conditions as specified in rule . One can also see that one of the local distances (i.e., VOC:purp) in this rule is larger than in rule .

Now, if the purpose of a transaction is more important to the user than other parameters, the user can express this simply by adjusting the weights. If he changes the weight for the purpose to

, rule has a smaller distance to the facts than and will be chosen to produce a counter-offer.

Whatever rule was chosen based on the weights, it will then be used to create a P3P proposal which then represents the counter-offer to be made. We now want to talk about how this counter-offer would look like. It is basically the reverse process of extracting the facts from a P3P proposal. In addition to this, the counter-offer will contain a reference to the rejected server-proposal, such that the respective Web server can relate the counter-offer to one of its own P3P proposals. Figure 4-13 illustrates how a counter offer would look like, produced from rule

.

Rejected P3P proposal vs. counter-offer with proposal-fingerprint.

Rejected Proposal <P3P:PROP ...> <P3P:USES> <P3P:STATEMENT VOC:purp="1,2,3,4" VOC:recpnt="1,2,3" action="r" VOC:id="0" <DATA:REF name="a"/> <DATA:REF name="b"/> <DATA:REF name="c"/> <DATA:REF name="e"/> <DATA:REF name="f"/> <DATA:REF name="g"/> <DATA:REF name="h"/> </P3P:STATEMENT> </P3P:USES> <ASSURANCE .../> </P3P:PROP>

Counter-Offer <P3P:PROP agreeID="<MD-5 of rejected Prop>" ...> <P3P:USES> <P3P:STATEMENT VOC:purp="0,1" VOC:recpnt="0,1,2" action="r" VOC:id="0" <DATA:REF name="e"/> <DATA:REF name="f"/> <DATA:REF name="g"/> <DATA:REF name="h"/> </P3P:STATEMENT> </P3P:USES> <ASSURANCE .../> </P3P:PROP>

The procedure of producing counter-offers can occur several times during a P3P transaction. The number of negotiation rounds allowed during a transaction limits the number of counter-offers to be produced. If this limit is reached during the transaction, either the user has to make a decision or the transaction should be finally rejected.