There are number of Policies. Each Policy contains many ruleS. 
Policies are applied to the a user account. I want to find an algorithm
which can find conflicts (if exist) amongst the policies.

---

Request for Question Clarification by lazerfx-ga on 13 Aug 2002 02:41 PDT

Do you have any details about the policies themselves?  Without
exactly knowing the policies and their details, we really can't create
an algorythm that deals with the conflicts.

Also, what do you mean by 'algorythm'?  Are you talking about
psuedo-code, mathematical algorythms, or a computer program, or
something else altogether?

---

Clarification of Question by imasud-ga on 13 Aug 2002 18:31 PDT

I need a genral algorithm solution, it can be an psuedo-code, or
solution in plain words disccusing the solution.
- Policy have rules (one or more).
Example 
Policy 1:
Rule 1: You can access Database

Policy 2:
Rule 2: You cannot access Database

Both these pilicies are applied to a User "A".
Meaning he can and cannot access database, which is conflict.

This example does not mean that the algorithm is for the Database
access.
It can be for anything. I just want an algorithm which can find these
kind
of conflicts and then can find a way to resolve them.

Hello imasud,

Your question is still pretty open ended, so I'll give you a summary
of applications, methods, and techniques used to detect conflicts (or
inconsistent rules). In addition, you will probably need some method
to convert the rules into some form that can be used by the methods
described. I will try to point out some techniques for that with each
conflict detection method.

Resolution of the conflict is often not feasible without some human
intervention. The methods or algorithms may recommend a place to break
the conflict, but will generally not do that action by itself (unless
you program it to do so). The drawback of automatic conflict
resolution is that you may get unexpected behavior in the software due
to some unexpected combination of effects. However, I did include a
good reference on the use of production rules in databases as an
example of methods that may apply in your case.

Visual Threads

http://www.compaq.com/products/software/visualthreads/rules.html

This product from Compaq (was DEC, now HP) describes a number of
conditions that a concurrent program must meet to operate properly.
From the FAQ, it describes a method to collect data from the operating
program (overhead ranges from 2% to 400% increase in runtime). From
that data and some static analysis, it determines if one or more of a
number of rules are violated. The report would then highlight the
problems and suggest solutions (basically references to help files).
There is apparently a beta (free?) version for Linux you can download
for evaluation if you want to see how this product works.

Access Control List Analysis...

http://www-sal.cs.uiuc.edu/~steng/cs497_01/qian.ppt

This powerpoint presentation summarizes techniques used to analyze
rules in network access control lists and determines if the rules are
consistent, overlapping, or inconsistent. It introduces definitions
and operations on network addresses, you may need some similar
techniques for your rules to define what it means to be "in conflict".
It has some technical descriptions about half way through that
describe the methods in terms of groups and group operations (e.g.,
union, intersection). It also describes some methods to eliminate the
overlapping or redundant rules. An html version is in Google's cache
if you can't read the original powerpoint file (search for the title
above).

If-then-else framework part 3...

http://www.javaworld.com/javaworld/jw-06-2000/jw-0630-ifthenelse3_p.html

This is a mixture of technical presentation and Java source code to
describe a set of problems with complex systems and steps you can take
to automate checking for inconsistent rules. As an example, the phrase
FFTT can match patterns F*TT and FF*T which can lead to erroneous
operation of the program. This also describes the problems with a
large number of rules (can lead to very slow run times...).

Biological databases...

http://yam.med.yale.edu/~kei/kei_web/data_model_int.ppt

Another powerpoint presentation. This time looking at the problems
with different databases, comparing information between them and
*then* finding the inconsistent information (so it can be reconciled).
More focus on handling data with different schema than finding
conflicts.

Deriving Production Rules for Constraint Maintenance

http://citeseer.nj.nec.com/correct/93250

This is a paper that describes methods to maintain a database which is
subject to a series of constraints. It describes the use of
"production rules" to make corrections to the database. This may
provide some guidance in how to resolve the conflicts in your rules.

As you can see, there is a wide variety of applications that use
conflict detection and resolution. Some use of group theory and/or
methods such as "transitive closure" (i.e., taking a set of conditions
such as A->B, B->C, B->D, to derive A->C, A->D) will be helpful. A
good way to represent the rules is also needed - working from english
text will complicate matters.

I hope this provides a number of good examples. For further searches,
you can use phrases such as "inconsistent rules", "rule conflict",
algorithm, method, constraint, "remove redundant" and others to find
more examples. Let me know if you need some additional information
through the clarification request if needed.
 
  --Maniac

---

Request for Answer Clarification by imasud-ga on 20 Aug 2002 08:52 PDT

Hi,
I gave you very open question. I will try to be specific now. I am
looking
for Policies conflicts in  Distributed Systems and Networks. Each
Policy have rules. Each Group in a network are assinged different
policies.
I am intrested in finding conflicts and a way to resolve them.
Thank you for help
Imran

---

Clarification of Answer by maniac-ga on 21 Aug 2002 16:03 PDT

Hello Imasud,

You are asking for more detail about finding and resolving conflicts
in distributed network groups, policies, and rules.

Based on your request, I still recommend a review of...

Access Control List Analysis
http://www-sal.cs.uiuc.edu/~steng/cs497_01/qian.ppt 

which describes algorithms to detect conflicting, overlapping, and
redundant rules in networks. This does not generalize to groups, and
the following references will focus more on network policy and the
relationships to groups.

Another site you may want to check out is...

Policy Research Group, DoC, Imperial College
http://www-dse.doc.ic.ac.uk/Research/policies/index.shtml

There are two items there that may be of particular interest:
  1. The call for papers for "Journal of Network and Systems
Management: Special Issue on Policy Based Management of Networks and
Services". One of the topics to be addressed is the last item titled
"Policy impact analysis, conflict detection and resolution."
  2. Ponder, A Policy Language for Distributed Systems Management.
This is free for download and includes compiler, policy editor, and
management toolkit.

You may want to contact that policy research group for more
information.

There is some good research material at

Delegation Logic: A Logic-based Approach to Distributed Authorization
http://citeseer.nj.nec.com/li00delegation.html

which has links to a 124 page dissertation that describes a number of
recent methods in authorization, trust, and resolving conflicts and
includes references to more on line information.
An older document (1995) that has a number of references to policy
related material and includes online pdf's is

Lecture Notes in Computer Science: Policies for Distributed Systems
and Networks
http://link.springer.de/link/service/series/0558/tocs/t1995.htm

I didn't try, but it appears you can download each section as a pdf.

On the related topic of IPSEC, is a paper titled

IPSec/VPN Security Policy: Correctness, Conflict Detection and
Resolution
http://www.itpapers.com/cgi/PSummaryIT.pl?paperid=28099&scid=284

You need to register (free) to Tech Republic to download the full
paper.

For more general references, you can try a search with phrases such as
group policy conflict distributed network.

As I was searching, I did run into some references to Microsoft
Windows. You did not indicate any specific interest in Windows, but
there is some good information for that operating system. For example,
specific to Windows NT information, there is a book titled

Windows NT Security 1/e
http://www.pearsonptg.com/book_detail/0,3771,0130839906,00.html

which costs about $50. Chapter five addresses system policies and
addresses identification and resolution of conflicts.

A Windows 2000 reference that addresses policies in brief is:

Windows 2000 Essential Reference
http://vig.pearsoned.com/store/product/1,3498,store-5180_isbn-073570869X_type-TOC_editmode-1,00.html

which is available for $24.50.

If your query is specific to Windows - I suggest a search using
phrases such as +group policy conflict windows.

I hope this clarification has been helpful.
  --Maniac

Maniac's comments are excellent.

I would add a couple of extras:

In your example, you said that in Policy 1, Rule 1, there is
permission, in Policy 2, Rule 2, there isn't permission..

You have to ask yourself this: What is the relationship between Policy
1 and Policy 2? Why is there one policy that says Go and another that
says Stop? In fact it's between policies that the "rules" lie. The
rules that you specified are really just statements of "state"..

There's some ways to deal with the interrelationships between the
policies (I'll be overlapping maniac here):

1. As Maniac said, Human intervention. When you have a conflict, you
present the problems clearly and easily and let some one choose the
answer.

2. Emergent Human intervention: as with human intervention, but you
allow the human to say that this will always be the answer to the
question, so the system doesn't have to ask again. What's happening
here is that the system learns the answers through human intervention
and ends up with simple automatic rules.

3. Policy Prioirty - the policies are in a tree, where policies at the
root are more important that policies in the leaves. So the system
always knows what to do. Easy to implement. Results aren't always
satisfactory.

4. Rule-based. You have rules governing the policies which (as maniac
said) use clear rule expressions to say who wins in a conflict. All
rules have actors - the variables used to calculate the results. The
actors might be time, user-groups, user-types, user profiles etc etc

5. Merged rules. A blend of a tree and rules.. for example you start
at the root of the tree and apply the rules. Then you traverse the
tree, merging the rules results at each node with the results from the
parents. So you need "sibiling" rules - between nodes at the same
level and "parent" rules - rules that merge the children's results
with the parents. A bit complex, perhaps - extremely messy to trace if
there's a problem!

You can then combine them to create fancy resolution: For instance, if
you mix "Emergent human intervention" with "Rules-based", you can set
a basic set of rules, allow user interaction to say "there's something
wrong with the rules" and doctor the rules based on past performance.

It goes on and on..

Getting back to your original example, the heuristics of your policy
system, whatever you do, should pick up the fact that there are two
identical policies, that have no rules between them or prioirty and
should say "Cannot resolve these policies"

Hope that shed some more light..

(me again)
One more thing:
Be wary of creating a general solution to all conflicts. Conflicts and
their rules are very specific to a given problem. You may end up
creating a massive beast of a rules engine which you believe handles
all conflicts. This does NOT get you away from more work! Why? Because
you end up having to "program" your engine in great detail about the
specifics of the problem! So no matter which way you do it (writing
specific code for your conflicts or writing a conflict engine), you'll
always end up with specific rules. So don't waste too much time
building the best conflict resolver ever, unless you want to sell it
as a product!!!