Multiple namespaced schema doesn't like cross namespace action membership/principals

[tomlikestorock]

Before opening, please confirm:

• I have searched for duplicate or closed issues.
• I have read the guide for submitting bug reports.
• I have done my best to include a minimal, self-contained set of instructions for consistently reproducing the issue.

Bug Category

Schemas and Validation

Describe the bug

When a schema contains multiple namesapces, it is possible to generate an in operator hierarchy respect error that claims one of the namespace's actions are not a descendant of the others.

This manifests when one of the actions that is a transitive member of the other namespace's actions specifies an appliesTo that points to the other namespace as well.

This might not be a bug, it may be an edge case that I'm not aware of.

Expected behavior

Create a schema with two namespaces, entities and actions in each NS1, NS2. NS2 will have entities that are members of NS1's entities, and NS2 will have actions that are direct and transitive members of NS1's actions.

Have an action in NS2 be a transitive member of an NS1 action group, and specify that NS2's action applies to a principal type within NS1.

Reproduction steps

1. Create the repro files as in this issue
2. Run the following command: cedar validate --schema repro.cedarschema.json --policies repro.policy.txt --deny-warnings

Code Snippet

repro.cedarschema.json

{
    "NS1": {
        "entityTypes": {
            "PrincipalEntity": {},
            "SystemEntity1": {},
            "SystemEntity2": {
                "memberOfTypes": [
                    "SystemEntity1"
                ]
            }
        },
        "actions": {
            "Group1": {
                "appliesTo": {
                    "principalTypes": [],
                    "resourceTypes": []
                }
            }
        }
    },
    "NS2": {
        "entityTypes": {
            "SystemEntity1": {
                "memberOfTypes": [
                    "NS1::SystemEntity2"
                ]
            }
        },
        "actions": {
            "Group1": {
                "memberOf": [
                    {"id": "Group1", "type": "NS1::Action"}
                ],
                "appliesTo": {
                    "principalTypes": [],
                    "resourceTypes": []
                }
            },
            "Action1": {
                "memberOf": [
                    {"id": "Group1"}
                ],
                "appliesTo": {
                    "principalTypes": [
                        "NS1::PrincipalEntity"
                    ],
                    "resourceTypes": [
                        "NS2::SystemEntity1"
                    ]
                }
            }
        }
    }
}

repro.policy.txt

permit(
    principal in NS1::PrincipalEntity::"user1",
    action in NS1::Action::"Group1",
    resource in NS1::SystemEntity1::"entity1"
);

Log output

Validation Failed
Validation Errors:
validation error on `policy `policy0``: operands to `in` do not respect the entity hierarchy. `NS2::Action` is not a descendant of `NS1::Action`

NOTE:
Remove the entire "appliesTo" in NS2::Action::Action1 and get this:

Validation Failed
Validation Errors:
validation error on `policy `policy0``: policy is impossible. The policy expression evaluates to false for all valid requests

Additional configuration

No response

Operating System

No response

Additional information and screenshots

No response

[john-h-kastner-aws]

Looked into this and I can confirm this is a bug in the validator. They're two things going on here.

• First, the validator gives the expression action in NS1::Action::"Group1" the type Bool when it could give it type True. This is correct, but imprecise. Directly increasing precision here while maintaining backwards compatibility is problematic unless we first implement Move ImpossiblePolicy from error to warning #539. This part of the issue actually applies to actions even within the same namespace, but on it's own it would hardly be a noticeable issue.
• Second, typechecking for in has a condition where it must either conclude that the type of the in is either True or False, or the entity type on the LHS must be one of the permissible decedent entity types for the type entity type on the RHS. The bug is that we do not consider that an entity having type NS2::Action may be a descendant of an entity with type NS2::Action. We can fix this condition without any backwards compatibly issues. This could also be resolved if we ditch the invalid hierarchy error entirely in Remove HierarchyNotRespected validation error #638.

[john-h-kastner-aws]

Fixed by #704. Unfortunately not in time for the recent 3.1 release, but this will go out in a future 3.2.