[FEATURE][POLICY]: Policy conflict detection and resolution

## Summary

Implement an intelligent policy conflict detection system that identifies contradictory, overlapping, or ambiguous policies across Cedar and OPA rule sets before deployment, preventing security gaps and access control inconsistencies.

## Parent Epic

- #2222 Epic: Policy-as-Code Security & Compliance Automation Platform

## Related Issues

- #2238 Policy GitOps & Version Control
- #2223 Unified Policy Decision Point (PDP)
- #2226 Policy Testing & Simulation Sandbox
- #1245 Security Clearance Levels Plugin

## Problem Statement

As policy sets grow in complexity, organizations face:
- **Silent Conflicts**: Two policies granting contradictory permissions
- **Shadowing**: More specific policies hidden by broader ones
- **Gaps**: Permission combinations not covered by any policy
- **Redundancy**: Duplicate rules wasting evaluation cycles
- **Order Dependencies**: Results changing based on evaluation order

Without automated conflict detection, policy changes can introduce subtle security vulnerabilities that are difficult to diagnose.

## Proposed Solution

### Architecture

```
┌─────────────────────────────────────────────────────────────────┐
│                  Policy Conflict Analyzer                       │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│   ┌─────────────┐     ┌─────────────┐     ┌─────────────┐      │
│   │   Policy    │────▶│   Parser &  │────▶│  Semantic   │      │
│   │   Loader    │     │  Normalizer │     │  Analyzer   │      │
│   └─────────────┘     └─────────────┘     └──────┬──────┘      │
│                                                   │             │
│                                                   ▼             │
│   ┌─────────────┐     ┌─────────────┐     ┌─────────────┐      │
│   │  Conflict   │◀────│  Rule Graph │◀────│   SAT/SMT   │      │
│   │  Reporter   │     │  Builder    │     │   Solver    │      │
│   └─────────────┘     └─────────────┘     └─────────────┘      │
│         │                                                       │
│         ▼                                                       │
│   ┌─────────────┐     ┌─────────────┐                          │
│   │  Resolution │────▶│  Suggestion │                          │
│   │    Engine   │     │  Generator  │                          │
│   └─────────────┘     └─────────────┘                          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘
```

### Conflict Types Detected

#### 1. Direct Contradictions
```yaml
# Policy A: Permit
- effect: Permit
  principal: Role::"employee"
  action: Action::"read_document"
  resource: Server::"docs"

# Policy B: Forbid (CONFLICT!)
- effect: Forbid
  principal: Role::"employee"  
  action: Action::"read_document"
  resource: Server::"docs"
```

#### 2. Shadowing (Specificity Issues)
```yaml
# Broad policy shadows specific one
- effect: Forbid
  principal: Role::"employee"
  action: Action::"*"           # Wildcard shadows...
  resource: Server::"payroll"

- effect: Permit
  principal: Role::"employee"
  action: Action::"view_own_payslip"  # ...this specific permission
  resource: Server::"payroll"
```

#### 3. Permission Gaps
```yaml
# No policy covers this combination:
# principal: Role::"contractor"
# action: Action::"submit_timesheet"  
# resource: Server::"hr-system"
# Result: Implicit deny (may be unintentional)
```

#### 4. Redundant Rules
```yaml
# Rule A
- effect: Permit
  principal: Role::"admin"
  action: Action::"*"
  resource: Server::"*"

# Rule B (redundant - already covered by A)
- effect: Permit
  principal: Role::"admin"
  action: Action::"delete"
  resource: Server::"documents"
```

### Core Components

#### 1. Policy Normalizer
```python
class PolicyNormalizer:
    """Convert policies to canonical form for analysis."""
    
    def normalize(self, policy: Policy) -> NormalizedPolicy:
        """Normalize policy to canonical representation."""
        return NormalizedPolicy(
            id=policy.id,
            effect=self._normalize_effect(policy.effect),
            principals=self._expand_principals(policy.principal),
            actions=self._expand_actions(policy.action),
            resources=self._expand_resources(policy.resource),
            conditions=self._normalize_conditions(policy.conditions),
            priority=policy.priority,
            source_engine=policy.engine  # cedar or opa
        )
    
    def _expand_principals(self, principal: str) -> set[str]:
        """Expand wildcards and role hierarchies."""
        if principal == "*":
            return self.role_registry.all_roles()
        
        if principal.startswith("Role::"):
            role = self._extract_role(principal)
            # Include role and all sub-roles
            return self.role_registry.expand_hierarchy(role)
        
        return {principal}
```

#### 2. Conflict Detector
```python
class PolicyConflictDetector:
    """Detect conflicts between policies."""
    
    def analyze(
        self, 
        policies: list[NormalizedPolicy]
    ) -> ConflictReport:
        """Analyze policy set for conflicts."""
        conflicts = []
        
        # Build comparison pairs
        for i, policy_a in enumerate(policies):
            for policy_b in policies[i+1:]:
                # Check for overlap
                overlap = self._compute_overlap(policy_a, policy_b)
                
                if overlap.exists:
                    conflict = self._classify_conflict(
                        policy_a, policy_b, overlap
                    )
                    if conflict:
                        conflicts.append(conflict)
        
        # Detect gaps
        gaps = self._detect_permission_gaps(policies)
        
        # Detect redundancy
        redundant = self._detect_redundancy(policies)
        
        return ConflictReport(
            conflicts=conflicts,
            gaps=gaps,
            redundant_rules=redundant,
            analysis_timestamp=datetime.utcnow()
        )
    
    def _classify_conflict(
        self,
        a: NormalizedPolicy,
        b: NormalizedPolicy,
        overlap: Overlap
    ) -> Conflict | None:
        """Classify the type of conflict."""
        # Direct contradiction
        if a.effect != b.effect and overlap.is_complete:
            return Conflict(
                type=ConflictType.CONTRADICTION,
                severity=Severity.CRITICAL,
                policy_a=a,
                policy_b=b,
                overlap=overlap,
                description=f"Policies {a.id} and {b.id} have "
                           f"contradictory effects for same scope"
            )
        
        # Shadowing
        if self._shadows(a, b):
            return Conflict(
                type=ConflictType.SHADOWING,
                severity=Severity.WARNING,
                policy_a=a,
                policy_b=b,
                description=f"Policy {a.id} shadows {b.id}"
            )
        
        return None
```

#### 3. SAT/SMT Solver Integration
```python
class PolicySATSolver:
    """Use SAT solver for complex conflict detection."""
    
    def __init__(self):
        self.solver = z3.Solver()
    
    def find_conflicts(
        self, 
        policies: list[NormalizedPolicy]
    ) -> list[SATConflict]:
        """Use SMT solving for complex conflict detection."""
        # Encode policies as logical formulas
        formulas = [self._encode_policy(p) for p in policies]
        
        conflicts = []
        
        # Find contradictions
        for i, f1 in enumerate(formulas):
            for j, f2 in enumerate(formulas[i+1:], i+1):
                # Check if both can be satisfied simultaneously
                # with contradictory effects
                self.solver.push()
                self.solver.add(z3.And(
                    f1.applies,
                    f2.applies,
                    f1.effect != f2.effect
                ))
                
                if self.solver.check() == z3.sat:
                    model = self.solver.model()
                    conflicts.append(SATConflict(
                        policies=(policies[i], policies[j]),
                        counterexample=self._extract_example(model)
                    ))
                
                self.solver.pop()
        
        return conflicts
    
    def _encode_policy(self, policy: NormalizedPolicy) -> PolicyFormula:
        """Encode policy as Z3 formula."""
        principal_var = z3.String('principal')
        action_var = z3.String('action')
        resource_var = z3.String('resource')
        
        applies = z3.And(
            z3.Or([principal_var == p for p in policy.principals]),
            z3.Or([action_var == a for a in policy.actions]),
            z3.Or([resource_var == r for r in policy.resources])
        )
        
        effect = z3.Bool(f'effect_{policy.id}')
        
        return PolicyFormula(
            applies=applies,
            effect=effect if policy.effect == "Permit" else z3.Not(effect)
        )
```

#### 4. Resolution Suggester
```python
class ConflictResolutionSuggester:
    """Generate suggestions for resolving conflicts."""
    
    def suggest_resolution(
        self, 
        conflict: Conflict
    ) -> list[ResolutionSuggestion]:
        """Generate resolution suggestions for a conflict."""
        suggestions = []
        
        if conflict.type == ConflictType.CONTRADICTION:
            suggestions.extend([
                ResolutionSuggestion(
                    action="add_priority",
                    description="Add explicit priority to resolve order",
                    example=self._generate_priority_example(conflict)
                ),
                ResolutionSuggestion(
                    action="add_condition",
                    description="Add conditions to differentiate scope",
                    example=self._generate_condition_example(conflict)
                ),
                ResolutionSuggestion(
                    action="merge_policies",
                    description="Merge into single policy with clear intent",
                    example=self._generate_merge_example(conflict)
                )
            ])
        
        elif conflict.type == ConflictType.SHADOWING:
            suggestions.append(ResolutionSuggestion(
                action="reorder",
                description="Move specific policy before general one",
                example=self._generate_reorder_example(conflict)
            ))
        
        elif conflict.type == ConflictType.GAP:
            suggestions.append(ResolutionSuggestion(
                action="add_policy",
                description="Add explicit policy for uncovered case",
                example=self._generate_gap_fill_example(conflict)
            ))
        
        return suggestions
```

### Conflict Report Schema

```python
@dataclass
class ConflictReport:
    """Comprehensive conflict analysis report."""
    
    summary: ConflictSummary
    conflicts: list[Conflict]
    gaps: list[PermissionGap]
    redundant_rules: list[RedundantRule]
    suggestions: list[ResolutionSuggestion]
    
    # Metrics
    total_policies_analyzed: int
    analysis_duration_ms: int
    conflict_count_by_severity: dict[Severity, int]
    
    def to_markdown(self) -> str:
        """Generate markdown report."""
        return f"""
# Policy Conflict Analysis Report

## Summary
- **Total Policies**: {self.total_policies_analyzed}
- **Critical Conflicts**: {self.conflict_count_by_severity.get(Severity.CRITICAL, 0)}
- **Warnings**: {self.conflict_count_by_severity.get(Severity.WARNING, 0)}
- **Permission Gaps**: {len(self.gaps)}
- **Redundant Rules**: {len(self.redundant_rules)}

## Critical Conflicts
{self._format_conflicts(Severity.CRITICAL)}

## Warnings
{self._format_conflicts(Severity.WARNING)}

## Permission Gaps
{self._format_gaps()}

## Suggested Resolutions
{self._format_suggestions()}
"""
```

### Configuration

```yaml
plugins:
  - name: "PolicyConflictDetector"
    kind: "policy_conflict.plugin.PolicyConflictDetector"
    version: "0.1.0"
    hooks: ["policy_pre_deploy", "policy_validate"]
    config:
      analysis:
        detect_contradictions: true
        detect_shadowing: true
        detect_gaps: true
        detect_redundancy: true
        use_sat_solver: true  # For complex analysis
        
      thresholds:
        block_on_critical: true
        block_on_warning: false
        max_gaps_allowed: 10
        
      reporting:
        format: markdown
        include_suggestions: true
        notify_on_conflict:
          - slack:#policy-alerts
```

### REST API

```
POST /api/v1/policies/analyze           # Analyze policy set
GET  /api/v1/policies/conflicts         # Get current conflicts
GET  /api/v1/policies/gaps              # Get permission gaps
POST /api/v1/policies/validate          # Validate before deploy
GET  /api/v1/policies/redundancy        # Get redundant rules
```

## Acceptance Criteria

- [ ] Detects direct contradictions between Permit/Forbid policies
- [ ] Identifies shadowing relationships
- [ ] Reports permission gaps with examples
- [ ] Finds redundant/duplicate rules
- [ ] Generates resolution suggestions
- [ ] Blocks deployment on critical conflicts (configurable)
- [ ] Supports both Cedar and OPA policies
- [ ] Provides markdown and JSON reports
- [ ] Integrates with GitOps pipeline (#2238)

## Implementation Phases

### Phase 1: Basic Detection
- Policy parser and normalizer
- Direct contradiction detection
- Simple overlap computation

### Phase 2: Advanced Analysis
- Shadowing detection
- Gap analysis
- SAT solver integration

### Phase 3: Resolution Engine
- Suggestion generator
- Auto-fix for simple conflicts
- Priority recommendation

### Phase 4: Integration
- GitOps pipeline hook
- CI/CD gate
- Dashboard visualization

## Security Considerations

- Conflict reports may reveal policy structure
- RBAC required for conflict analysis API
- Rate limiting on analysis endpoints
- Audit logging for conflict resolutions

## Dependencies

- #2223 Unified PDP (for policy parsing)
- #2238 Policy GitOps (for deployment gates)
- Z3 SMT solver (optional, for complex analysis)

## References

- [Amazon Zelkova](https://aws.amazon.com/blogs/security/protect-sensitive-data-in-the-cloud-with-automated-reasoning-zelkova/)
- [AWS IAM Access Analyzer](https://docs.aws.amazon.com/IAM/latest/UserGuide/what-is-access-analyzer.html)
- [Formal Methods for Policy Analysis](https://www.microsoft.com/en-us/research/publication/formal-analysis-of-access-control-policies/)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[FEATURE][POLICY]: Policy conflict detection and resolution #2239

Summary

Parent Epic

Related Issues

Problem Statement

Proposed Solution

Architecture

Conflict Types Detected

1. Direct Contradictions

2. Shadowing (Specificity Issues)

3. Permission Gaps

4. Redundant Rules

Core Components

1. Policy Normalizer

2. Conflict Detector

3. SAT/SMT Solver Integration

4. Resolution Suggester

Conflict Report Schema

Configuration

REST API

Acceptance Criteria

Implementation Phases

Phase 1: Basic Detection

Phase 2: Advanced Analysis

Phase 3: Resolution Engine

Phase 4: Integration

Security Considerations

Dependencies

References

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

[FEATURE][POLICY]: Policy conflict detection and resolution #2239

Description

Summary

Parent Epic

Related Issues

Problem Statement

Proposed Solution

Architecture

Conflict Types Detected

1. Direct Contradictions

2. Shadowing (Specificity Issues)

3. Permission Gaps

4. Redundant Rules

Core Components

1. Policy Normalizer

2. Conflict Detector

3. SAT/SMT Solver Integration

4. Resolution Suggester

Conflict Report Schema

Configuration

REST API

Acceptance Criteria

Implementation Phases

Phase 1: Basic Detection

Phase 2: Advanced Analysis

Phase 3: Resolution Engine

Phase 4: Integration

Security Considerations

Dependencies

References

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions