In policy matching subset intersect is incorrect

[Icarus9913]

What happened?

Went through the Subset Intersect method source codes, I found there's one case would be failed:

Entry("entry 66", testCase{
  s1: []core_rules.Tag{
    {Key: "key1", Value: "val1"},
    {Key: "key2", Value: "abc"},
  },
  s2: []core_rules.Tag{
    {Key: "key2", Value: "val2"},
    {Key: "key3", Value: "val3"},
  },
  intersect: false,
}),

In this case, there should not be one intersection but our codes would give us intersect: true

[Icarus9913]

kuma/pkg/plugins/policies/core/rules/rules.go

Lines 198 to 200 in 8659306

	if !ok {
	return true
	}

This should be continue

[lahabana]

What's the breaking change risk here? How likely are people to be relying on this behaviour?

[Icarus9913]

What's the breaking change risk here? How likely are people to be relying on this behaviour?

I need to assess it

[Icarus9913]

@lahabana I did lots of tests and analysis for this, but didn't find an impact on the customer usage side. I also used ci-full-matrix to run our e2e to test this and no errors were found.

But, this bug would generate the wrong rules for the issue: #12273 which is the sub-issue of the Compute function.

[lobkovilya]

I think the code works as expected. In your example:

s1: []core_rules.Tag{
  {Key: "key1", Value: "val1"},
  {Key: "key2", Value: "abc"},
},
s2: []core_rules.Tag{
  {Key: "key2", Value: "val2"},
  {Key: "key3", Value: "val3"},
},

these two sets have an intersection {key1: val1}

• {key1: val1} belongs to s1
• {key1: val1} belongs to s2 (because s2 doesn't have key1)

[Icarus9913]

I think the code works as expected. In your example:

s1: []core_rules.Tag{
  {Key: "key1", Value: "val1"},
  {Key: "key2", Value: "abc"},
},
s2: []core_rules.Tag{
  {Key: "key2", Value: "val2"},
  {Key: "key3", Value: "val3"},
},

these two sets have an intersection {key1: val1}

• {key1: val1} belongs to s1
• {key1: val1} belongs to s2 (because s2 doesn't have key1)

This is a little bit confused, in sets s1 and s2, they have the same key key2 but with different value. Isn't it contradictory?

[lobkovilya]

This is a little bit confused, in sets s1 and s2, they have the same key key2 but with different value. Isn't it contradictory?

Why is this contradictory? You need just 1 element that belongs to both s1 and s2 to have an intersection

[Icarus9913]

Also we have different behaviors once I modified the s1 key-values order. We can see the two Entry have the same tags-pair but just with different orders, in the end we got different results. Does the order matter?

	FEntry("entry 1", testCase{
		s1: []core_rules.Tag{
			{Key: "key2", Value: "abc"},
			{Key: "key1", Value: "val1"},
		},
		s2: []core_rules.Tag{
			{Key: "key2", Value: "val2"},
			{Key: "key3", Value: "val3"},
		},
		intersect: false,
	}),
	FEntry("entry 2", testCase{
		s1: []core_rules.Tag{
			{Key: "key1", Value: "val1"},
			{Key: "key2", Value: "abc"},
		},
		s2: []core_rules.Tag{
			{Key: "key2", Value: "val2"},
			{Key: "key3", Value: "val3"},
		},
		intersect: true,
	}),

[lobkovilya]

I think the code works as expected. In your example:

s1: []core_rules.Tag{
  {Key: "key1", Value: "val1"},
  {Key: "key2", Value: "abc"},
},
s2: []core_rules.Tag{
  {Key: "key2", Value: "val2"},
  {Key: "key3", Value: "val3"},
},

these two sets have an intersection {key1: val1}

• {key1: val1} belongs to s1
• {key1: val1} belongs to s2 (because s2 doesn't have key1)

Actually, you're right, my example here is incorrect. Since there are 3 keys in total (key1, key2 and key3) then the element of the intersection has to be in 3-dimensional space. But I have an example {key1: val1} of a 1-dimensional. And in 3-dimensional space there are actually no points (because key2 has different values), so no intersection between s1 and s2.

So the issue is correct, I'm going to review the PR.