Repository: cilium/cilium
Pull request #22966 (2023-01-06 22:29:24)

policy: Fix Deny Precedence Bug
When the policy map state is created CIDRs
are now checked against one another to ensure
that deny-rules that supersede allow-rules
when they should.

Fixes: #15198

```release-note
policy: Promote Deny Policies from Beta to Stable
```


nathanjsweet: /test
maintainer-s-little-helper[bot]: Commit 8ea87dfda74a9fe4c6fc66d08f704c93d6712751 does not contain "Signed-off-by".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin
maintainer-s-little-helper[bot]: Commit 9cf5315f7e38d5c36a4f60f34958840e11a283e2 does not contain "Signed-off-by".

Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin
nathanjsweet: /test
nathanjsweet: /test
nathanjsweet: /test
christarazi: CI is looking good :tada: 
nbusseneau: @nathanjsweet Do you wish to address the comment nits from Jarno before we merge? I see that CI is green, so if you only do a comment edit I will be OK to merge as-is without re-running the CI.

Patch:
diff --git a/pkg/endpoint/bpf.go b/pkg/endpoint/bpf.go
index bef1ca20ce..272383b5f8 100644
--- a/pkg/endpoint/bpf.go
+++ b/pkg/endpoint/bpf.go
@@ -26,6 +26,8 @@ import (
 	"github.com/cilium/cilium/pkg/completion"
 	"github.com/cilium/cilium/pkg/controller"
 	"github.com/cilium/cilium/pkg/endpoint/regeneration"
+	"github.com/cilium/cilium/pkg/identity"
+	"github.com/cilium/cilium/pkg/labels"
 	"github.com/cilium/cilium/pkg/loadinfo"
 	"github.com/cilium/cilium/pkg/logging/logfields"
 	"github.com/cilium/cilium/pkg/maps/bwmap"
@@ -195,6 +197,21 @@ func (e *Endpoint) writeHeaderfile(prefix string) error {
 	return err
 }
 
+// policyIdentitiesLabelLookup is an implementation of the policy.Identites interface.
+type policyIdentitiesLabelLookup struct {
+	*Endpoint
+}
+
+// GetLabels implements the policy.Identites interface{} method GetLabels,
+// which allows Endpoint.addNewRedirectsFromDesiredPolicy to call `l4.ToMapState`
+// with a label cache. This enables `l4.ToMapstate` to look up CIDRs associated with
+// identites to make a final determination about whether they should even be inserted into
+// an Endpoint's policy map.
+func (p *policyIdentitiesLabelLookup) GetLabels(id identity.NumericIdentity) labels.LabelArray {
+	ident := p.allocator.LookupIdentityByID(context.Background(), id)
+	return ident.LabelArray
+}
+
 // addNewRedirectsFromDesiredPolicy must be called while holding the endpoint lock for
 // writing. On success, returns nil; otherwise, returns an error indicating the
 // problem that occurred while adding an l7 redirect for the specified policy.
@@ -301,7 +318,7 @@ func (e *Endpoint) addNewRedirectsFromDesiredPolicy(ingress bool, desiredRedirec
 				direction = trafficdirection.Egress
 			}
 
-			keysFromFilter := l4.ToMapState(e, direction)
+			keysFromFilter := l4.ToMapState(e, direction, &policyIdentitiesLabelLookup{e})
 
 			for keyFromFilter, entry := range keysFromFilter {
 				if oldEntry, ok := e.desiredPolicy.PolicyMapState[keyFromFilter]; ok {
diff --git a/pkg/ip/cidr.go b/pkg/ip/cidr.go
index 8d7548a392..653358120c 100644
--- a/pkg/ip/cidr.go
+++ b/pkg/ip/cidr.go
@@ -110,3 +110,23 @@ func IPsToNetPrefixes(ips []net.IP) []netip.Prefix {
 	}
 	return res
 }
+
+// NetsContainsAny checks that any subnet in the `a` subnet group *fully*
+// contains any of the subnets in the `b` subnet group.
+func NetsContainsAny(a, b []*net.IPNet) bool {
+	for _, an := range a {
+		aMask, _ := an.Mask.Size()
+		aIsIPv4 := an.IP.To4() != nil
+		for _, bn := range b {
+			bIsIPv4 := bn.IP.To4() != nil
+			isSameFamily := aIsIPv4 == bIsIPv4
+			if isSameFamily {
+				bMask, _ := bn.Mask.Size()
+				if bMask >= aMask && an.Contains(bn.IP) {
+					return true
+				}
+			}
+		}
+	}
+	return false
+}
diff --git a/pkg/policy/l4.go b/pkg/policy/l4.go
index 336b727b0b..a94b57fdac 100644
--- a/pkg/policy/l4.go
+++ b/pkg/policy/l4.go
@@ -473,7 +473,7 @@ func (l4 *L4Filter) GetListener() string {
 // To give priority for deny and L7 redirection (e.g., for visibility purposes), we use
 // DenyPreferredInsert() instead of directly inserting the value to the map.
 // PolicyOwner (aka Endpoint) is locked during this call.
-func (l4Filter *L4Filter) ToMapState(policyOwner PolicyOwner, direction trafficdirection.TrafficDirection) MapState {
+func (l4Filter *L4Filter) ToMapState(policyOwner PolicyOwner, direction trafficdirection.TrafficDirection, identities Identities) MapState {
 	port := uint16(l4Filter.Port)
 	proto := uint8(l4Filter.U8Proto)
 
@@ -531,7 +531,7 @@ func (l4Filter *L4Filter) ToMapState(policyOwner PolicyOwner, direction trafficd
 		entry := NewMapStateEntry(cs, l4Filter.DerivedFromRules, currentRule.IsRedirect(), isDenyRule, currentRule.GetAuthType())
 		if cs.IsWildcard() {
 			keyToAdd.Identity = 0
-			keysToAdd.DenyPreferredInsert(keyToAdd, entry)
+			keysToAdd.DenyPreferredInsert(keyToAdd, entry, identities)
 
 			if port == 0 {
 				// Allow-all
@@ -543,23 +543,23 @@ func (l4Filter *L4Filter) ToMapState(policyOwner PolicyOwner, direction trafficd
 			continue
 		}
 
-		identities := cs.GetSelections()
+		idents := cs.GetSelections()
 		if option.Config.Debug {
 			if isDenyRule {
 				logger.WithFields(logrus.Fields{
 					logfields.EndpointSelector: cs,
-					logfields.PolicyID:         identities,
+					logfields.PolicyID:         idents,
 				}).Debug("ToMapState: Denied remote IDs")
 			} else {
 				logger.WithFields(logrus.Fields{
 					logfields.EndpointSelector: cs,
-					logfields.PolicyID:         identities,
+					logfields.PolicyID:         idents,
 				}).Debug("ToMapState: Allowed remote IDs")
 			}
 		}
-		for _, id := range identities {
+		for _, id := range idents {
 			keyToAdd.Identity = id.Uint32()
-			keysToAdd.DenyPreferredInsert(keyToAdd, entry)
+			keysToAdd.DenyPreferredInsert(keyToAdd, entry, identities)
 		}
 	}
 
diff --git a/pkg/policy/mapstate.go b/pkg/policy/mapstate.go
index 02603d37fb..ef6642fb79 100644
--- a/pkg/policy/mapstate.go
+++ b/pkg/policy/mapstate.go
@@ -5,10 +5,12 @@ package policy
 
 import (
 	"fmt"
+	"net"
 
 	"github.com/sirupsen/logrus"
 
 	"github.com/cilium/cilium/pkg/identity"
+	"github.com/cilium/cilium/pkg/ip"
 	"github.com/cilium/cilium/pkg/labels"
 	"github.com/cilium/cilium/pkg/lock"
 	"github.com/cilium/cilium/pkg/logging/logfields"
@@ -45,6 +47,10 @@ const (
 // MapState is a state of a policy map.
 type MapState map[Key]MapStateEntry
 
+type Identities interface {
+	GetLabels(identity.NumericIdentity) labels.LabelArray
+}
+
 // Key is the userspace representation of a policy key in BPF. It is
 // intentionally duplicated from pkg/maps/policymap to avoid pulling in the
 // BPF dependency to this package.
@@ -76,6 +82,21 @@ func (k Key) IsEgress() bool {
 	return k.TrafficDirection == trafficdirection.Egress.Uint8()
 }
 
+// PortProtoIsBroader returns true if the receiver Key has broader
+// port-protocol than the argument Key. That is a port-protocol
+// that covers the argument Key's port-protocol and is larger.
+// An equal port-protocol will return false.
+func (k Key) PortProtoIsBroader(c Key) bool {
+	return k.DestPort == 0 && c.DestPort != 0 ||
+		k.Nexthdr == 0 && c.Nexthdr != 0
+}
+
+// PortProtoIsEqual returns true if the port-protocols of the
+// two keys are exactly equal.
+func (k Key) PortProtoIsEqual(c Key) bool {
+	return k.DestPort == c.DestPort && k.Nexthdr == c.Nexthdr
+}
+
 type Keys map[Key]struct{}
 
 type MapStateOwner interface{}
@@ -104,6 +125,9 @@ type MapStateEntry struct {
 	// dependents contains the keys for entries create based on this entry. These entries
 	// will be deleted once all of the owners are deleted.
 	dependents Keys
+
+	// cachedNets caches the subnets (if any) associated with this MapStateEntry.
+	cachedNets []*net.IPNet
 }
 
 // NewMapStateEntry creates a map state entry. If redirect is true, the
@@ -147,6 +171,60 @@ func (e *MapStateEntry) RemoveDependent(key Key) {
 	}
 }
 
+// HasDependent returns true if the 'key' is contained
+// within the set of dependent keys
+func (e *MapStateEntry) HasDependent(key Key) bool {
+	if e.dependents == nil {
+		return false
+	}
+	_, ok := e.dependents[key]
+	return ok
+}
+
+// getNets returns the most specific CIDR for an identity. For the "World" identity
+// it returns both IPv4 and IPv6.
+func (e *MapStateEntry) getNets(identities Identities, ident uint32) []*net.IPNet {
+	// Caching results is not dangerous in this situation as the entry
+	// is ephemerally tied to the lifecycle of the MapState object that
+	// it will be in.
+	if e.cachedNets != nil {
+		return e.cachedNets
+	}
+	id := identity.NumericIdentity(ident)
+	if id == identity.ReservedIdentityWorld {
+		e.cachedNets = []*net.IPNet{
+			{IP: net.IPv4zero, Mask: net.CIDRMask(0, net.IPv4len*8)},
+			{IP: net.IPv6zero, Mask: net.CIDRMask(0, net.IPv6len*8)},
+		}
+		return e.cachedNets
+	}
+	if identities == nil {
+		return nil
+	}
+	lbls := identities.GetLabels(id)
+	nets := make([]*net.IPNet, 0, 1)
+	var (
+		maskSize         int
+		mostSpecificCidr *net.IPNet
+	)
+	for _, lbl := range lbls {
+		if lbl.Source == labels.LabelSourceCIDR {
+			_, netIP, err := net.ParseCIDR(lbl.Key)
+			if err == nil {
+				if ms, _ := netIP.Mask.Size(); ms > maskSize {
+					mostSpecificCidr = netIP
+					maskSize = ms
+				}
+			}
+		}
+	}
+	if mostSpecificCidr != nil {
+		nets = append(nets, mostSpecificCidr)
+	}
+	e.cachedNets = nets
+	return nets
+}
+
 // AddDependent adds 'key' to the set of dependent keys.
 func (owner Key) AddDependent(keys MapState, key Key) {
 	if e, exists := keys[owner]; exists {
@@ -203,8 +281,8 @@ func (e MapStateEntry) String() string {
 // to deny entries, and L3-only deny entries over L3-L4 allows.
 // This form may be used when a full policy is computed and we are not yet interested
 // in accumulating incremental changes.
-func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry) {
-	keys.denyPreferredInsertWithChanges(newKey, newEntry, nil, nil)
+func (keys MapState) DenyPreferredInsert(newKey Key, newEntry MapStateEntry, identities Identities) {
+	keys.denyPreferredInsertWithChanges(newKey, newEntry, nil, nil, identities)
 }
 
 // addKeyWithChanges adds a 'key' with value 'entry' to 'keys' keeping track of incremental changes in 'adds' and 'deletes'
@@ -289,107 +367,139 @@ func (keys MapState) deleteKeyWithChanges(key Key, owner MapStateOwner, adds, de
 	}
 }
 
-// denyPreferredInsertWithChanges inserts a key and entry into the map by giving preference
-// to deny entries, and L3-only deny entries over L3-L4 allows.
+// entryIdentityIsSupersetOf compares two entries and keys to see if the primary identity contains
+// the compared identity. This means that either that primary identity is 0 (i.e. it is a superset
+// of every other identity), or one of the subnets of the primary identity fully contains or is
+// equal to one of the subnets in the compared identity (note:this covers cases like "reserved:world").
+func entryIdentityIsSupersetOf(primaryKey Key, primaryEntry MapStateEntry, compareKey Key, compareEntry MapStateEntry, identities Identities) bool {
+	// If the identities are equal then neither is a superset (for the purposes of our business logic).
+	if primaryKey.Identity == compareKey.Identity {
+		return false
+	}
+	return primaryKey.Identity == 0 && compareKey.Identity != 0 ||
+		ip.NetsContainsAny(primaryEntry.getNets(identities, primaryKey.Identity),
+			compareEntry.getNets(identities, compareKey.Identity))
+}
+
+// protocolsMatch checks to see if two given keys match on protocol.
+// This means that either one of them covers all protocols or they
+// are equal.
+func protocolsMatch(a, b Key) bool {
+	return a.Nexthdr == 0 || b.Nexthdr == 0 || a.Nexthdr == b.Nexthdr
+}
+
+// denyPreferredInsertWithChanges contains the most important business logic for policy insertions. It inserts
+// a key and entry into the map by giving preference to deny entries, and L3-only deny entries over L3-L4 allows.
 // Incremental changes performed are recorded in 'adds' and 'deletes', if not nil.
-func (keys MapState) denyPreferredInsertWithChanges(newKey Key, newEntry MapStateEntry, adds, deletes Keys) {
+// See https://docs.google.com/spreadsheets/d/1WANIoZGB48nryylQjjOw6lKjI80eVgPShrdMTMalLEw#gid=2109052536 for details
+func (keys MapState) denyPreferredInsertWithChanges(newKey Key, newEntry MapStateEntry, adds, deletes Keys, identities Identities) {
 	allCpy := allKey
 	allCpy.TrafficDirection = newKey.TrafficDirection
-	// If we have a deny "all" we don't accept any kind of map entry
+	// If we have a deny "all" we don't accept any kind of map entry.
 	if v, ok := keys[allCpy]; ok && v.IsDeny {
 		return
 	}
-
 	if newEntry.IsDeny {
-		// case for an existing allow L4-only and we are inserting deny L3-only
-		switch {
-		case newKey.DestPort == 0 && newKey.Nexthdr == 0 && newKey.Identity != 0:
-			l4OnlyAllows := MapState{}
-			for k, v := range keys {
-				if newKey.TrafficDirection == k.TrafficDirection &&
-					!v.IsDeny &&
-					k.Identity == 0 && (k.DestPort != 0 || k.Nexthdr != 0) {
-					// create a deny L3-L4 with the same allowed L4 port and proto
-					newKeyCpy := newKey
-					newKeyCpy.DestPort = k.DestPort
-					newKeyCpy.Nexthdr = k.Nexthdr
-					l3l4DenyEntry := NewMapStateEntry(newKey, newEntry.DerivedFromRules, false, true, AuthTypeNone)
-					keys.addKeyWithChanges(newKeyCpy, l3l4DenyEntry, adds, deletes)
-					// L3-only entries can be deleted incrementally so we need to track their
-					// effects on other entries so that those effects can be reverted when the
-					// identity is removed.
-					newEntry.AddDependent(newKeyCpy)
-					l4OnlyAllows[k] = v
-				}
+		for k, v := range keys {
+			// Protocols and traffic directions that don't match ensure that the policies
+			// do not interact in anyway.
+			if newKey.TrafficDirection != k.TrafficDirection || !protocolsMatch(newKey, k) {
+				continue
 			}
-			// Delete all L3-L4 if we are inserting a deny L3-only and
-			// there aren't allow L4-only for the existing deny L3-L4
-			for k := range keys {
-				if k.TrafficDirection == newKey.TrafficDirection &&
-					k.DestPort != 0 && k.Nexthdr != 0 &&
-					k.Identity == newKey.Identity {
-
-					kCpy := k
-					kCpy.Identity = 0
-					if _, ok := l4OnlyAllows[kCpy]; !ok {
-						keys.deleteKeyWithChanges(k, nil, adds, deletes)
+			if !v.IsDeny {
+				if entryIdentityIsSupersetOf(k, v, newKey, newEntry, identities) {
+					if newKey.PortProtoIsBroader(k) {
+						// If this iterated-allow-entry is a superset of the new-entry
+						// and it has a more specific port-protocol than the new-entry
+						// then an additional copy of the new-entry with the more
+						// specific port-protocol of the iterated-allow-entry must be inserted.
+						newKeyCpy := newKey
+						newKeyCpy.DestPort = k.DestPort
+						newKeyCpy.Nexthdr = k.Nexthdr
+						l3l4DenyEntry := NewMapStateEntry(newKey, newEntry.DerivedFromRules, false, true, AuthTypeNone)
+						keys.addKeyWithChanges(newKeyCpy, l3l4DenyEntry, adds, deletes)
+						// L3-only entries can be deleted incrementally so we need to track their
+						// effects on other entries so that those effects can be reverted when the
+						// identity is removed.
+						newEntry.AddDependent(newKeyCpy)
 					}
-				}
-			}
-		case allCpy == newKey:
-			// If we adding a deny "all" entry, then we will remove all entries
-			// from the map state for that direction.
-			for k := range keys {
-				if k.TrafficDirection == allCpy.TrafficDirection {
+				} else if (newKey.Identity == k.Identity ||
+					entryIdentityIsSupersetOf(newKey, newEntry, k, v, identities)) &&
+					(newKey.PortProtoIsBroader(k) || newKey.PortProtoIsEqual(k)) {
+					// If the new-entry is a superset (or equal) of the iterated-allow-entry and
+					// the new-entry has a broader (or equal) port-protocol then we
+					// should delete the iterated-allow-entry
 					keys.deleteKeyWithChanges(k, nil, adds, deletes)
 				}
-			}
-		default:
-			// Do not insert 'newKey' if the map state already denies traffic
-			// which is a superset of (or equal to) 'newKey'
-			newKeyCpy := newKey
-			newKeyCpy.DestPort = 0
-			newKeyCpy.Nexthdr = 0
-			v, ok := keys[newKeyCpy]
-			if ok && v.IsDeny {
-				// Found a L3-only Deny so we won't accept any L3-L4 policies
+			} else if (newKey.Identity == k.Identity ||
+				entryIdentityIsSupersetOf(k, v, newKey, newEntry, identities)) &&
+				k.DestPort == 0 && k.Nexthdr == 0 &&
+				!v.HasDependent(newKey) {
+				// If this iterated-deny-entry is a supserset (or equal) of the new-entry and
+				// the iterated-deny-entry is an L3-only policy then we
+				// should not insert the new entry (as long as it is not one
+				// of the special L4-only denies we created to cover the special
+				// case of a superset-allow with a more specific port-protocol).
+				//
+				// NOTE: This condition could be broader to reject more deny entries,
+				// but there *may* be performance tradeoffs.
 				return
+			} else if (newKey.Identity == k.Identity ||
+				entryIdentityIsSupersetOf(newKey, newEntry, k, v, identities)) &&
+				newKey.DestPort == 0 && newKey.Nexthdr == 0 &&
+				!newEntry.HasDependent(k) {
+				// If this iterated-deny-entry is a subset (or equal) of the new-entry and
+				// the new-entry is an L3-only policy then we
+				// should delete the iterated-deny-entry (as long as it is not one
+				// of the special L4-only denies we created to cover the special
+				// case of a superset-allow with a more specific port-protocol).
+				//
+				// NOTE: This condition could be broader to reject more deny entries,
+				// but there *may* be performance tradeoffs.
+				keys.deleteKeyWithChanges(k, nil, adds, deletes)
 			}
 		}
-
 		keys.addKeyWithChanges(newKey, newEntry, adds, deletes)
-		return
-	} else if newKey.Identity == 0 && newKey.DestPort != 0 {
-		// case for an existing deny L3-only and we are inserting allow L4-only
+	} else {
 		for k, v := range keys {
-			if newKey.TrafficDirection == k.TrafficDirection {
-				if v.IsDeny && k.Identity != 0 && k.DestPort == 0 && k.Nexthdr == 0 {
-					// create a deny L3-L4 with the same deny L3
-					newKeyCpy := newKey
-					newKeyCpy.Identity = k.Identity
-					l3l4DenyEntry := NewMapStateEntry(k, v.DerivedFromRules, false, true, AuthTypeNone)
-					keys.addKeyWithChanges(newKeyCpy, l3l4DenyEntry, adds, deletes)
-					// Mark the new entry as a dependent of 'v'
-					v.AddDependent(newKeyCpy)
-					keys[k] = v
+			// Protocols and traffic directions that don't match ensure that the policies
+			// do not interact in anyway.
+			if newKey.TrafficDirection != k.TrafficDirection || !protocolsMatch(newKey, k) {
+				continue
+			}
+			// NOTE: We do not delete redundant allow entries.
+			if v.IsDeny {
+				if entryIdentityIsSupersetOf(newKey, newEntry, k, v, identities) {
+					if k.PortProtoIsBroader(newKey) {
+						// If the new-entry is *only* superset of the iterated-deny-entry
+						// and the new-entry has a more specific port-protocol than the
+						// iterated-deny-entry then an additional copy of the iterated-deny-entry
+						// with the more specific port-porotocol of the new-entry must
+						// be added.
+						denyKeyCpy := k
+						denyKeyCpy.DestPort = newKey.DestPort
+						denyKeyCpy.Nexthdr = newKey.Nexthdr
+						l3l4DenyEntry := NewMapStateEntry(k, v.DerivedFromRules, false, true, AuthTypeNone)
+						keys.addKeyWithChanges(denyKeyCpy, l3l4DenyEntry, adds, deletes)
+						// L3-only entries can be deleted incrementally so we need to track their
+						// effects on other entries so that those effects can be reverted when the
+						// identity is removed.
+						v.AddDependent(denyKeyCpy)
+						keys[k] = v
+					}
+				} else if (k.Identity == newKey.Identity ||
+					entryIdentityIsSupersetOf(k, v, newKey, newEntry, identities)) &&
+					(k.PortProtoIsBroader(newKey) || k.PortProtoIsEqual(newKey)) &&
+					!v.HasDependent(newKey) {
+					// If the iterated-deny-entry is a superset (or equal) of the new-entry and has a
+					// broader (or equal) port-protocol than the new-entry then the new
+					// entry should not be inserted.
+					return
 				}
 			}
 		}
-		keys.addKeyWithChanges(newKey, newEntry, adds, deletes)
-		return
-	}
-	// branch for adding a new allow L3-L4
-
-	newKeyCpy := newKey
-	newKeyCpy.DestPort = 0
-	newKeyCpy.Nexthdr = 0
-	v, ok := keys[newKeyCpy]
-	if ok && v.IsDeny {
-		// Found a L3-only Deny so we won't accept any L3-L4 allow policies
-		return
+		keys.redirectPreferredInsert(newKey, newEntry, adds, deletes)
 	}
-
-	keys.redirectPreferredInsert(newKey, newEntry, adds, deletes)
 }
 
 // redirectPreferredInsert inserts a new entry giving priority to L7-redirects by
@@ -609,7 +719,7 @@ func (keys MapState) DetermineAllowLocalhostIngress() {
 			},
 		}
 		es := NewMapStateEntry(nil, derivedFrom, false, false, AuthTypeNone)
-		keys.DenyPreferredInsert(localHostKey, es)
+		keys.DenyPreferredInsert(localHostKey, es, nil)
 		if !option.Config.EnableRemoteNodeIdentity {
 			var isHostDenied bool
 			v, ok := keys[localHostKey]
@@ -620,7 +730,7 @@ func (keys MapState) DetermineAllowLocalhostIngress() {
 				},
 			}
 			es := NewMapStateEntry(nil, derivedFrom, false, isHostDenied, AuthTypeNone)
-			keys.DenyPreferredInsert(localRemoteNodeKey, es)
+			keys.DenyPreferredInsert(localRemoteNodeKey, es, nil)
 		}
 	}
 }
@@ -797,7 +907,7 @@ func (mc *MapChanges) AccumulateMapChanges(cs CachedSelector, adds, deletes []id
 
 // consumeMapChanges transfers the incremental changes from MapChanges to the caller,
 // while applying the changes to PolicyMapState.
-func (mc *MapChanges) consumeMapChanges(policyMapState MapState) (adds, deletes Keys) {
+func (mc *MapChanges) consumeMapChanges(policyMapState MapState, identities Identities) (adds, deletes Keys) {
 	mc.mutex.Lock()
 	adds = make(Keys, len(mc.changes))
 	deletes = make(Keys, len(mc.changes))
@@ -807,7 +917,7 @@ func (mc *MapChanges) consumeMapChanges(policyMapState MapState) (adds, deletes
 			// insert but do not allow non-redirect entries to overwrite a redirect entry,
 			// nor allow non-deny entries to overwrite deny entries.
 			// Collect the incremental changes to the overall state in 'mc.adds' and 'mc.deletes'.
-			policyMapState.denyPreferredInsertWithChanges(mc.changes[i].Key, mc.changes[i].Value, adds, deletes)
+			policyMapState.denyPreferredInsertWithChanges(mc.changes[i].Key, mc.changes[i].Value, adds, deletes, identities)
 		} else {
 			// Delete the contribution of this cs to the key and collect incremental changes
 			for cs := range mc.changes[i].Value.owners { // get the sole selector
diff --git a/pkg/policy/resolve.go b/pkg/policy/resolve.go
index 7f364fcce5..93399e7f2e 100644
--- a/pkg/policy/resolve.go
+++ b/pkg/policy/resolve.go
@@ -168,7 +168,7 @@ func (p *EndpointPolicy) computeDirectionL4PolicyMapEntries(policyMapState MapSt
 	for _, filter := range l4PolicyMap {
 		lookupDone := false
 		proxyport := uint16(0)
-		keysFromFilter := filter.ToMapState(p.PolicyOwner, direction)
+		keysFromFilter := filter.ToMapState(p.PolicyOwner, direction, p.SelectorCache)
 		for keyFromFilter, entry := range keysFromFilter {
 			// Fix up the proxy port for entries that need proxy redirection
 			if entry.IsRedirectEntry() {
@@ -188,7 +188,7 @@ func (p *EndpointPolicy) computeDirectionL4PolicyMapEntries(policyMapState MapSt
 					continue
 				}
 			}
-			policyMapState.DenyPreferredInsert(keyFromFilter, entry)
+			policyMapState.DenyPreferredInsert(keyFromFilter, entry, p.SelectorCache)
 		}
 	}
 }
@@ -200,7 +200,7 @@ func (p *EndpointPolicy) computeDirectionL4PolicyMapEntries(policyMapState MapSt
 func (p *EndpointPolicy) ConsumeMapChanges() (adds, deletes Keys) {
 	p.selectorPolicy.SelectorCache.mutex.Lock()
 	defer p.selectorPolicy.SelectorCache.mutex.Unlock()
-	return p.policyMapChanges.consumeMapChanges(p.PolicyMapState)
+	return p.policyMapChanges.consumeMapChanges(p.PolicyMapState, p.SelectorCache)
 }
 
 // AllowsIdentity returns whether the specified policy allows
diff --git a/pkg/policy/selectorcache.go b/pkg/policy/selectorcache.go
index 453c8bf54d..0b0620910b 100644
--- a/pkg/policy/selectorcache.go
+++ b/pkg/policy/selectorcache.go
@@ -1089,3 +1089,11 @@ func (sc *SelectorCache) RemoveIdentitiesFQDNSelectors(fqdnSels []api.FQDNSelect
 	sc.mutex.Unlock()
 	sc.releaseIdentityMappings(identitiesToRelease)
 }
+
+func (sc *SelectorCache) GetLabels(id identity.NumericIdentity) labels.LabelArray {
+	ident, ok := sc.idCache[id]
+	if !ok {
+		return labels.LabelArray{}
+	}
+	return ident.lbls
+}


Test patch:
diff --git a/pkg/ip/cidr_test.go b/pkg/ip/cidr_test.go
index 993d7b3f63..7408e4cb88 100644
--- a/pkg/ip/cidr_test.go
+++ b/pkg/ip/cidr_test.go
@@ -51,3 +51,42 @@ func TestIPToNetPrefix(t *testing.T) {
 
 	assert.Equal(t, netip.Prefix{}, IPToNetPrefix(nil))
 }
+
+func mustParseCIDR(t *testing.T, s string) *net.IPNet {
+	_, n, err := net.ParseCIDR(s)
+	assert.NoError(t, err)
+	return n
+}
+
+func TestNetsContainsAny(t *testing.T) {
+	tests := []struct {
+		name string
+		a    []*net.IPNet
+		b    []*net.IPNet
+		ret  bool
+	}{
+		{
+			name: "a contains b",
+			a:    []*net.IPNet{mustParseCIDR(t, "0.0.0.0/0")},
+			b:    []*net.IPNet{mustParseCIDR(t, "192.0.0.1/32")},
+			ret:  true,
+		},
+		{
+			name: "b contains a",
+			a:    []*net.IPNet{mustParseCIDR(t, "192.0.0.1/32")},
+			b:    []*net.IPNet{mustParseCIDR(t, "0.0.0.0/0")},
+		},
+		{
+			name: "a equals b",
+			a:    []*net.IPNet{mustParseCIDR(t, "192.0.0.1/32")},
+			b:    []*net.IPNet{mustParseCIDR(t, "192.0.0.1/32")},
+			ret:  true,
+		},
+	}
+
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			assert.Equal(t, tt.ret, NetsContainsAny(tt.a, tt.b))
+		})
+	}
+}
diff --git a/pkg/policy/distillery_test.go b/pkg/policy/distillery_test.go
index 75943874b9..3a9707d2b4 100644
--- a/pkg/policy/distillery_test.go
+++ b/pkg/policy/distillery_test.go
@@ -8,6 +8,7 @@ import (
 	"fmt"
 	"io"
 	stdlog "log"
+	"net/netip"
 	"strings"
 	"testing"
 
@@ -17,6 +18,7 @@ import (
 	"github.com/cilium/cilium/pkg/identity"
 	"github.com/cilium/cilium/pkg/identity/cache"
 	"github.com/cilium/cilium/pkg/labels"
+	"github.com/cilium/cilium/pkg/labels/cidr"
 	"github.com/cilium/cilium/pkg/policy/api"
 	"github.com/cilium/cilium/pkg/policy/trafficdirection"
 	"github.com/cilium/cilium/pkg/testutils"
@@ -364,14 +366,14 @@ func (d *policyDistillery) WithLogBuffer(w io.Writer) *policyDistillery {
 // entries for an endpoint with the specified labels.
 func (d *policyDistillery) distillPolicy(owner PolicyOwner, epLabels labels.LabelArray) (MapState, error) {
 	result := make(MapState)
-
+	selectorCache := d.Repository.GetSelectorCache()
 	endpointSelected, _ := d.Repository.GetRulesMatching(epLabels)
 	io.WriteString(d.log, fmt.Sprintf("[distill] Endpoint selected by policy: %t\n", endpointSelected))
 	if !endpointSelected {
 		allowAllIngress := true
 		allowAllEgress := false // Skip egress
 		result.AllowAllIdentities(allowAllIngress, allowAllEgress)
-		result.clearOwners()
+		result.clearCaches()
 		return result, nil
 	}
 
@@ -381,17 +383,17 @@ func (d *policyDistillery) distillPolicy(owner PolicyOwner, epLabels labels.Labe
 		Trace: TRACE_VERBOSE,
 	}
 	ingressL4.Logging = stdlog.New(d.log, "", 0)
-	io.WriteString(d.log, fmt.Sprintf("[distill] Evaluating L4 -> %s", epLabels))
+	io.WriteString(d.log, fmt.Sprintf("[distill] Evaluating L4 Ingress -> %s", epLabels))
 	l4IngressPolicy, err := d.Repository.ResolveL4IngressPolicy(&ingressL4)
 	if err != nil {
 		return nil, err
 	}
 
 	// Handle L4 ingress from each identity in the cache to the endpoint.
-	io.WriteString(d.log, "[distill] Producing L4 filter keys\n")
+	io.WriteString(d.log, "[distill] Producing L4 ingress filter keys\n")
 	for _, l4 := range l4IngressPolicy {
-		io.WriteString(d.log, fmt.Sprintf("[distill] Processing L4Filter (l4: %d/%s), (l3/7: %+v)\n", l4.Port, l4.Protocol, l4.PerSelectorPolicies))
-		for key, entry := range l4.ToMapState(owner, 0) {
+		io.WriteString(d.log, fmt.Sprintf("[distill] Processing ingress L4Filter (l4: %d/%s), (l3/7: %+v)\n", l4.Port, l4.Protocol, l4.PerSelectorPolicies))
+		for key, entry := range l4.ToMapState(owner, 0, selectorCache) {
 			var policyStr string
 			if entry.IsDeny {
 				policyStr = "deny"
@@ -399,22 +401,53 @@ func (d *policyDistillery) distillPolicy(owner PolicyOwner, epLabels labels.Labe
 				policyStr = "allow"
 			}
 			io.WriteString(d.log, fmt.Sprintf("[distill] L4 ingress %s %+v (parser=%s, redirect=%t)\n", policyStr, key, l4.L7Parser, entry.IsRedirectEntry()))
-			result.DenyPreferredInsert(key, entry)
+			result.DenyPreferredInsert(key, entry, selectorCache)
+		}
+	}
+	l4IngressPolicy.Detach(selectorCache)
+	result.clearCaches()
+
+	// Prepare the L4 policy so we know whether L4 policy may apply
+	egressL4 := SearchContext{
+		From:  epLabels,
+		Trace: TRACE_VERBOSE,
+	}
+	egressL4.Logging = stdlog.New(d.log, "", 0)
+	io.WriteString(d.log, fmt.Sprintf("[distill] Evaluating L4 Egress -> %s", epLabels))
+	l4EgressPolicy, err := d.Repository.ResolveL4EgressPolicy(&egressL4)
+	if err != nil {
+		return nil, err
+	}
+
+	// Handle L4 egress from each identity in the cache to the endpoint.
+	io.WriteString(d.log, "[distill] Producing L4 egress filter keys\n")
+	for _, l4 := range l4EgressPolicy {
+		io.WriteString(d.log, fmt.Sprintf("[distill] Processing egress L4Filter (l4: %d/%s), (l3/7: %+v)\n", l4.Port, l4.Protocol, l4.PerSelectorPolicies))
+		for key, entry := range l4.ToMapState(owner, 1, selectorCache) {
+			var policyStr string
+			if entry.IsDeny {
+				policyStr = "deny"
+			} else {
+				policyStr = "allow"
+			}
+			io.WriteString(d.log, fmt.Sprintf("[distill] L4 egress %s %+v (parser=%s, redirect=%t)\n", policyStr, key, l4.L7Parser, entry.IsRedirectEntry()))
+			result.DenyPreferredInsert(key, entry, selectorCache)
 		}
 	}
-	l4IngressPolicy.Detach(d.Repository.GetSelectorCache())
-	result.clearOwners()
+	l4EgressPolicy.Detach(selectorCache)
+	result.clearCaches()
 	return result, nil
 }
 
-// clearOwners removes CachedSelectors from MapStateEntries
+// clearCaches removes CachedSelectors and CachedNets from MapStateEntries
 // for testing purposes.  Table-driven testing pattern used for these
 // tests does not allow expected MapStateEntries to contain actual
 // CachedSelectors as those have not been inserted to the selector
 // cache at the time when the expectations are created.
-func (m MapState) clearOwners() {
+func (m MapState) clearCaches() {
 	for k, v := range m {
 		v.owners = make(map[MapStateOwner]struct{})
+		v.cachedNets = nil
 		m[k] = v
 	}
 }
@@ -1127,3 +1160,295 @@ func Test_AllowAll(t *testing.T) {
 		})
 	}
 }
+
+var (
+	ruleL3DenyWorld = api.NewRule().WithIngressDenyRules([]api.IngressDenyRule{{
+		IngressCommonRule: api.IngressCommonRule{
+			FromEntities: api.EntitySlice{api.EntityWorld},
+		},
+	}}).WithEgressDenyRules([]api.EgressDenyRule{{
+		EgressCommonRule: api.EgressCommonRule{
+			ToEntities: api.EntitySlice{api.EntityWorld},
+		},
+	}}).WithEndpointSelector(api.WildcardEndpointSelector)
+
+	cpyRule                   = *ruleL3DenyWorld
+	ruleL3DenyWorldWithLabels = (&cpyRule).WithLabels(labels.LabelWorld.LabelArray())
+	worldReservedID           = identity.ReservedIdentityWorld.Uint32()
+	mapKeyL3WorldIngress      = Key{worldReservedID, 0, 0, trafficdirection.Ingress.Uint8()}
+	mapKeyL3WorldEgress       = Key{worldReservedID, 0, 0, trafficdirection.Egress.Uint8()}
+	mapEntryDeny              = MapStateEntry{
+		ProxyPort:        0,
+		DerivedFromRules: labels.LabelArrayList{nil},
+		IsDeny:           true,
+		owners:           map[MapStateOwner]struct{}{},
+	}
+	mapEntryAllow = MapStateEntry{
+		ProxyPort:        0,
+		DerivedFromRules: labels.LabelArrayList{nil},
+		owners:           map[MapStateOwner]struct{}{},
+	}
+	worldLabelArrayList         = labels.LabelArrayList{nil, labels.LabelWorld.LabelArray()}
+	mapEntryWorldDenyWithLabels = MapStateEntry{
+		ProxyPort:        0,
+		DerivedFromRules: worldLabelArrayList,
+		IsDeny:           true,
+		owners:           map[MapStateOwner]struct{}{},
+	}
+
+	worldIPIdentity    = identity.NumericIdentity(16324)
+	worldCIDR          = api.CIDR("192.0.2.3/32")
+	lblWorldIP         = labels.ParseSelectLabelArray(fmt.Sprintf("%s:%s", labels.LabelSourceCIDR, worldCIDR))
+	ruleL3AllowWorldIP = api.NewRule().WithIngressRules([]api.IngressRule{{
+		IngressCommonRule: api.IngressCommonRule{
+			FromCIDR: api.CIDRSlice{worldCIDR},
+		},
+	}}).WithEgressRules([]api.EgressRule{{
+		EgressCommonRule: api.EgressCommonRule{
+			ToCIDR: api.CIDRSlice{worldCIDR},
+		},
+	}}).WithEndpointSelector(api.WildcardEndpointSelector)
+
+	worldSubnetIdentity = identity.NumericIdentity(16325)
+	worldSubnet         = api.CIDR("192.0.2.0/24")
+	worldSubnetRule     = api.CIDRRule{
+		Cidr: worldSubnet,
+	}
+	lblWorldSubnet   = cidr.GetCIDRLabels(netip.MustParsePrefix(string(worldSubnet)))
+	ruleL3DenySubnet = api.NewRule().WithIngressDenyRules([]api.IngressDenyRule{{
+		IngressCommonRule: api.IngressCommonRule{
+			FromCIDRSet: api.CIDRRuleSlice{worldSubnetRule},
+		},
+	}}).WithEgressDenyRules([]api.EgressDenyRule{{
+		EgressCommonRule: api.EgressCommonRule{
+			ToCIDRSet: api.CIDRRuleSlice{worldSubnetRule},
+		},
+	}}).WithEndpointSelector(api.WildcardEndpointSelector)
+	mapKeyL3SubnetIngress = Key{worldSubnetIdentity.Uint32(), 0, 0, trafficdirection.Ingress.Uint8()}
+	mapKeyL3SubnetEgress  = Key{worldSubnetIdentity.Uint32(), 0, 0, trafficdirection.Egress.Uint8()}
+
+	ruleL3DenySmallerSubnet = api.NewRule().WithIngressDenyRules([]api.IngressDenyRule{{
+		IngressCommonRule: api.IngressCommonRule{
+			FromCIDRSet: api.CIDRRuleSlice{api.CIDRRule{Cidr: worldCIDR}},
+		},
+	}}).WithEgressDenyRules([]api.EgressDenyRule{{
+		EgressCommonRule: api.EgressCommonRule{
+			ToCIDRSet: api.CIDRRuleSlice{api.CIDRRule{Cidr: worldCIDR}},
+		},
+	}}).WithEndpointSelector(api.WildcardEndpointSelector)
+
+	ruleL3AllowLargerSubnet = api.NewRule().WithIngressRules([]api.IngressRule{{
+		IngressCommonRule: api.IngressCommonRule{
+			FromCIDRSet: api.CIDRRuleSlice{api.CIDRRule{Cidr: worldSubnet}},
+		},
+	}}).WithEgressRules([]api.EgressRule{{
+		EgressCommonRule: api.EgressCommonRule{
+			ToCIDRSet: api.CIDRRuleSlice{api.CIDRRule{Cidr: worldSubnet}},
+		},
+	}}).WithEndpointSelector(api.WildcardEndpointSelector)
+
+	mapKeyL3SmallerSubnetIngress = Key{worldIPIdentity.Uint32(), 0, 0, trafficdirection.Ingress.Uint8()}
+	mapKeyL3SmallerSubnetEgress  = Key{worldIPIdentity.Uint32(), 0, 0, trafficdirection.Egress.Uint8()}
+
+	ruleL3L4Port8080ProtoAnyDenyWorld = api.NewRule().WithIngressDenyRules([]api.IngressDenyRule{
+		{
+			ToPorts: api.PortDenyRules{
+				api.PortDenyRule{
+					Ports: []api.PortProtocol{
+						{
+							Port:     "8080",
+							Protocol: api.ProtoAny,
+						},
+					},
+				},
+			},
+			IngressCommonRule: api.IngressCommonRule{
+				FromEntities: api.EntitySlice{api.EntityWorld},
+			},
+		},
+	}).WithEgressDenyRules([]api.EgressDenyRule{
+		{
+			ToPorts: api.PortDenyRules{
+				api.PortDenyRule{
+					Ports: []api.PortProtocol{
+						{
+							Port:     "8080",
+							Protocol: api.ProtoAny,
+						},
+					},
+				},
+			},
+			EgressCommonRule: api.EgressCommonRule{
+				ToEntities: api.EntitySlice{api.EntityWorld},
+			},
+		},
+	}).WithEndpointSelector(api.WildcardEndpointSelector)
+	mapKeyL3L4Port8080ProtoTCPWorldIngress  = Key{worldReservedID, 8080, 6, trafficdirection.Ingress.Uint8()}
+	mapKeyL3L4Port8080ProtoTCPWorldEgress   = Key{worldReservedID, 8080, 6, trafficdirection.Egress.Uint8()}
+	mapKeyL3L4Port8080ProtoUDPWorldIngress  = Key{worldReservedID, 8080, 17, trafficdirection.Ingress.Uint8()}
+	mapKeyL3L4Port8080ProtoUDPWorldEgress   = Key{worldReservedID, 8080, 17, trafficdirection.Egress.Uint8()}
+	mapKeyL3L4Port8080ProtoSCTPWorldIngress = Key{worldReservedID, 8080, 132, trafficdirection.Ingress.Uint8()}
+	mapKeyL3L4Port8080ProtoSCTPWorldEgress  = Key{worldReservedID, 8080, 132, trafficdirection.Egress.Uint8()}
+
+	mapKeyL3L4Port8080ProtoTCPWorldSNIngress  = Key{worldSubnetIdentity.Uint32(), 8080, 6, trafficdirection.Ingress.Uint8()}
+	mapKeyL3L4Port8080ProtoTCPWorldSNEgress   = Key{worldSubnetIdentity.Uint32(), 8080, 6, trafficdirection.Egress.Uint8()}
+	mapKeyL3L4Port8080ProtoUDPWorldSNIngress  = Key{worldSubnetIdentity.Uint32(), 8080, 17, trafficdirection.Ingress.Uint8()}
+	mapKeyL3L4Port8080ProtoUDPWorldSNEgress   = Key{worldSubnetIdentity.Uint32(), 8080, 17, trafficdirection.Egress.Uint8()}
+	mapKeyL3L4Port8080ProtoSCTPWorldSNIngress = Key{worldSubnetIdentity.Uint32(), 8080, 132, trafficdirection.Ingress.Uint8()}
+	mapKeyL3L4Port8080ProtoSCTPWorldSNEgress  = Key{worldSubnetIdentity.Uint32(), 8080, 132, trafficdirection.Egress.Uint8()}
+
+	ruleL3AllowWorldSubnet = api.NewRule().WithIngressRules([]api.IngressRule{{
+		ToPorts: api.PortRules{
+			api.PortRule{
+				Ports: []api.PortProtocol{
+					{
+						Port:     "8080",
+						Protocol: api.ProtoAny,
+					},
+				},
+			},
+		},
+		IngressCommonRule: api.IngressCommonRule{
+			FromCIDR: api.CIDRSlice{worldSubnet},
+		},
+	}}).WithEgressRules([]api.EgressRule{{
+		ToPorts: api.PortRules{
+			api.PortRule{
+				Ports: []api.PortProtocol{
+					{
+						Port:     "8080",
+						Protocol: api.ProtoAny,
+					},
+				},
+			},
+		},
+		EgressCommonRule: api.EgressCommonRule{
+			ToCIDR: api.CIDRSlice{worldSubnet},
+		},
+	}}).WithEndpointSelector(api.WildcardEndpointSelector)
+
+	ruleL3DenyWorldIP = api.NewRule().WithIngressDenyRules([]api.IngressDenyRule{{
+		IngressCommonRule: api.IngressCommonRule{
+			FromCIDR: api.CIDRSlice{worldCIDR},
+		},
+	}}).WithEgressDenyRules([]api.EgressDenyRule{{
+		EgressCommonRule: api.EgressCommonRule{
+			ToCIDR: api.CIDRSlice{worldCIDR},
+		},
+	}}).WithEndpointSelector(api.WildcardEndpointSelector)
+	mapKeyL4Port8080ProtoAnyWorldIPIngress       = Key{worldIPIdentity.Uint32(), 0, 0, trafficdirection.Ingress.Uint8()}
+	mapKeyL4Port8080ProtoAnyWorldIPEgress        = Key{worldIPIdentity.Uint32(), 0, 0, trafficdirection.Egress.Uint8()}
+	mapKeyL4Port8080ProtoTCPWorldIPIngress       = Key{worldIPIdentity.Uint32(), 8080, 6, trafficdirection.Ingress.Uint8()}
+	mapKeyL4Port8080ProtoTCPWorldIPEgress        = Key{worldIPIdentity.Uint32(), 8080, 6, trafficdirection.Egress.Uint8()}
+	mapKeyL4Port8080ProtoUDPWorldIPIngress       = Key{worldIPIdentity.Uint32(), 8080, 17, trafficdirection.Ingress.Uint8()}
+	mapKeyL4Port8080ProtoUDPWorldIPEgress        = Key{worldIPIdentity.Uint32(), 8080, 17, trafficdirection.Egress.Uint8()}
+	mapKeyL4Port8080ProtoSCTPWorldIPIngress      = Key{worldIPIdentity.Uint32(), 8080, 132, trafficdirection.Ingress.Uint8()}
+	mapKeyL4Port8080ProtoSCTPWorldIPEgress       = Key{worldIPIdentity.Uint32(), 8080, 132, trafficdirection.Egress.Uint8()}
+	mapEntryL4SubnetPort8080ProtoAnyIngressAllow = MapStateEntry{
+		ProxyPort:        0,
+		IsDeny:           true,
+		DerivedFromRules: labels.LabelArrayList{nil},
+		owners:           map[MapStateOwner]struct{}{},
+		dependents: Keys{
+			mapKeyL4Port8080ProtoTCPWorldIPIngress:  struct{}{},
+			mapKeyL4Port8080ProtoUDPWorldIPIngress:  struct{}{},
+			mapKeyL4Port8080ProtoSCTPWorldIPIngress: struct{}{},
+		},
+	}
+	mapEntryL4SubnetPort8080ProtoAnyEgressAllow = MapStateEntry{
+		ProxyPort:        0,
+		IsDeny:           true,
+		DerivedFromRules: labels.LabelArrayList{nil},
+		owners:           map[MapStateOwner]struct{}{},
+		dependents: Keys{
+			mapKeyL4Port8080ProtoTCPWorldIPEgress:  struct{}{},
+			mapKeyL4Port8080ProtoUDPWorldIPEgress:  struct{}{},
+			mapKeyL4Port8080ProtoSCTPWorldIPEgress: struct{}{},
+		},
+	}
+)
+
+func Test_EnsureDeniesPrecedeAllows(t *testing.T) {
+	identityCache := cache.IdentityCache{
+		identity.NumericIdentity(identityFoo): labelsFoo,
+		identity.ReservedIdentityWorld:        labels.LabelWorld.LabelArray(),
+		worldIPIdentity:                       lblWorldIP,                  // "192.0.2.3/32"
+		worldSubnetIdentity:                   lblWorldSubnet.LabelArray(), // "192.0.2.0/24"
+	}
+	selectorCache := testNewSelectorCache(identityCache)
+
+	tests := []struct {
+		test   string
+		rules  api.Rules
+		result MapState
+	}{
+		{"deny_world_no_labels", api.Rules{ruleL3DenyWorld, ruleL3AllowWorldIP}, MapState{
+			mapKeyL3WorldIngress: mapEntryDeny,
+			mapKeyL3WorldEgress:  mapEntryDeny,
+		}}, {"deny_world_with_labels", api.Rules{ruleL3DenyWorldWithLabels, ruleL3AllowWorldIP}, MapState{
+			mapKeyL3WorldIngress: mapEntryWorldDenyWithLabels,
+			mapKeyL3WorldEgress:  mapEntryWorldDenyWithLabels,
+		}}, {"deny_one_ip_with_a_larger_subnet", api.Rules{ruleL3DenySubnet, ruleL3AllowWorldIP}, MapState{
+			mapKeyL3SubnetIngress: mapEntryDeny,
+			mapKeyL3SubnetEgress:  mapEntryDeny,
+		}}, {"deny_part_of_a_subnet_with_an_ip", api.Rules{ruleL3DenySmallerSubnet, ruleL3AllowLargerSubnet}, MapState{
+			mapKeyL3SmallerSubnetIngress: mapEntryDeny,
+			mapKeyL3SmallerSubnetEgress:  mapEntryDeny,
+			mapKeyL3SubnetIngress:        mapEntryAllow,
+			mapKeyL3SubnetEgress:         mapEntryAllow,
+		}}, {"broad_deny_is_a_portproto_subset_of_a_specific_allow", api.Rules{ruleL3L4Port8080ProtoAnyDenyWorld, ruleL3AllowWorldIP}, MapState{
+			mapKeyL3L4Port8080ProtoTCPWorldIngress:    mapEntryDeny,
+			mapKeyL3L4Port8080ProtoTCPWorldEgress:     mapEntryDeny,
+			mapKeyL3L4Port8080ProtoUDPWorldIngress:    mapEntryDeny,
+			mapKeyL3L4Port8080ProtoUDPWorldEgress:     mapEntryDeny,
+			mapKeyL3L4Port8080ProtoSCTPWorldIngress:   mapEntryDeny,
+			mapKeyL3L4Port8080ProtoSCTPWorldEgress:    mapEntryDeny,
+			mapKeyL3SmallerSubnetIngress:              mapEntryAllow,
+			mapKeyL3SmallerSubnetEgress:               mapEntryAllow,
+			mapKeyL3L4Port8080ProtoTCPWorldSNIngress:  mapEntryDeny,
+			mapKeyL3L4Port8080ProtoTCPWorldSNEgress:   mapEntryDeny,
+			mapKeyL3L4Port8080ProtoUDPWorldSNIngress:  mapEntryDeny,
+			mapKeyL3L4Port8080ProtoUDPWorldSNEgress:   mapEntryDeny,
+			mapKeyL3L4Port8080ProtoSCTPWorldSNIngress: mapEntryDeny,
+			mapKeyL3L4Port8080ProtoSCTPWorldSNEgress:  mapEntryDeny,
+		}},
+		{"broad_allow_is_a_portproto_subset_of_a_specific_deny", api.Rules{ruleL3AllowWorldSubnet, ruleL3DenyWorldIP}, MapState{
+
+			mapKeyL3L4Port8080ProtoTCPWorldSNIngress:  mapEntryAllow,
+			mapKeyL3L4Port8080ProtoTCPWorldSNEgress:   mapEntryAllow,
+			mapKeyL3L4Port8080ProtoUDPWorldSNIngress:  mapEntryAllow,
+			mapKeyL3L4Port8080ProtoUDPWorldSNEgress:   mapEntryAllow,
+			mapKeyL3L4Port8080ProtoSCTPWorldSNIngress: mapEntryAllow,
+			mapKeyL3L4Port8080ProtoSCTPWorldSNEgress:  mapEntryAllow,
+
+			mapKeyL4Port8080ProtoAnyWorldIPIngress:  mapEntryL4SubnetPort8080ProtoAnyIngressAllow,
+			mapKeyL4Port8080ProtoAnyWorldIPEgress:   mapEntryL4SubnetPort8080ProtoAnyEgressAllow,
+			mapKeyL4Port8080ProtoTCPWorldIPIngress:  mapEntryDeny,
+			mapKeyL4Port8080ProtoTCPWorldIPEgress:   mapEntryDeny,
+			mapKeyL4Port8080ProtoUDPWorldIPIngress:  mapEntryDeny,
+			mapKeyL4Port8080ProtoUDPWorldIPEgress:   mapEntryDeny,
+			mapKeyL4Port8080ProtoSCTPWorldIPIngress: mapEntryDeny,
+			mapKeyL4Port8080ProtoSCTPWorldIPEgress:  mapEntryDeny,
+		}},
+	}
+	for _, tt := range tests {
+		repo := newPolicyDistillery(selectorCache)
+		for _, rule := range tt.rules {
+			if rule != nil {
+				_, _ = repo.AddList(api.Rules{rule})
+			}
+		}
+		t.Run(tt.test, func(t *testing.T) {
+			logBuffer := new(bytes.Buffer)
+			repo = repo.WithLogBuffer(logBuffer)
+			mapstate, err := repo.distillPolicy(DummyOwner{}, labelsFoo)
+			if err != nil {
+				t.Errorf("Policy resolution failure: %s", err)
+			}
+			if equal, err := checker.DeepEqual(mapstate, tt.result); !equal {
+				t.Logf("Policy Trace: \n%s\n", logBuffer.String())
+				t.Errorf("Policy test, %q, obtained didn't match expected for endpoint %s:\n%s", tt.test, labelsFoo, err)
+			}
+		})
+	}
+}
diff --git a/pkg/policy/fuzz_test.go b/pkg/policy/fuzz_test.go
index ff7d174ab1..62c6c71a36 100644
--- a/pkg/policy/fuzz_test.go
+++ b/pkg/policy/fuzz_test.go
@@ -47,7 +47,7 @@ func FuzzDenyPreferredInsert(f *testing.F) {
 		ff.GenerateStruct(&keys)
 		ff.GenerateStruct(&key)
 		ff.GenerateStruct(&entry)
-		keys.DenyPreferredInsert(key, entry)
+		keys.DenyPreferredInsert(key, entry, nil)
 	})
 }
 
diff --git a/pkg/policy/mapstate_test.go b/pkg/policy/mapstate_test.go
index fa1e8b368c..8543247860 100644
--- a/pkg/policy/mapstate_test.go
+++ b/pkg/policy/mapstate_test.go
@@ -9,6 +9,8 @@ import (
 	"gopkg.in/check.v1"
 
 	"github.com/cilium/cilium/pkg/checker"
+	"github.com/cilium/cilium/pkg/identity"
+	"github.com/cilium/cilium/pkg/identity/cache"
 	"github.com/cilium/cilium/pkg/labels"
 	"github.com/cilium/cilium/pkg/policy/trafficdirection"
 	"github.com/cilium/cilium/pkg/u8proto"
@@ -730,7 +732,7 @@ func (ds *PolicyTestSuite) TestMapState_DenyPreferredInsert(c *check.C) {
 		},
 	}
 	for _, tt := range tests {
-		tt.keys.DenyPreferredInsert(tt.args.key, tt.args.entry)
+		tt.keys.DenyPreferredInsert(tt.args.key, tt.args.entry, nil)
 		c.Assert(tt.keys, checker.DeepEquals, tt.want, check.Commentf(tt.name))
 	}
 }
@@ -1144,7 +1146,7 @@ func (ds *PolicyTestSuite) TestMapState_AccumulateMapChangesDeny(c *check.C) {
 			}
 			policyMaps.AccumulateMapChanges(cs, adds, deletes, x.port, x.proto, dir, x.redirect, x.deny, AuthTypeNone, nil)
 		}
-		adds, deletes := policyMaps.consumeMapChanges(policyMapState)
+		adds, deletes := policyMaps.consumeMapChanges(policyMapState, nil)
 		c.Assert(policyMapState, checker.DeepEquals, tt.state, check.Commentf(tt.name+" (MapState)"))
 		c.Assert(adds, checker.DeepEquals, tt.adds, check.Commentf(tt.name+" (adds)"))
 		c.Assert(deletes, checker.DeepEquals, tt.deletes, check.Commentf(tt.name+" (deletes)"))
@@ -1382,7 +1384,7 @@ func (ds *PolicyTestSuite) TestMapState_AccumulateMapChanges(c *check.C) {
 			}
 			policyMaps.AccumulateMapChanges(cs, adds, deletes, x.port, x.proto, dir, x.redirect, x.deny, x.authType, nil)
 		}
-		adds, deletes := policyMaps.consumeMapChanges(policyMapState)
+		adds, deletes := policyMaps.consumeMapChanges(policyMapState, nil)
 		c.Assert(policyMapState, checker.DeepEquals, tt.state, check.Commentf(tt.name+" (MapState)"))
 		c.Assert(adds, checker.DeepEquals, tt.adds, check.Commentf(tt.name+" (adds)"))
 		c.Assert(deletes, checker.DeepEquals, tt.deletes, check.Commentf(tt.name+" (deletes)"))
@@ -1940,7 +1942,7 @@ func (ds *PolicyTestSuite) TestMapState_AccumulateMapChangesOnVisibilityKeys(c *
 			}
 			policyMaps.AccumulateMapChanges(cs, adds, deletes, x.port, x.proto, dir, x.redirect, x.deny, AuthTypeNone, nil)
 		}
-		adds, deletes = policyMaps.consumeMapChanges(policyMapState)
+		adds, deletes = policyMaps.consumeMapChanges(policyMapState, nil)
 		// Visibilty redirects need to be re-applied after consumeMapChanges()
 		visOld = make(MapState)
 		for _, arg := range tt.visArgs {
@@ -1954,3 +1956,131 @@ func (ds *PolicyTestSuite) TestMapState_AccumulateMapChangesOnVisibilityKeys(c *
 		c.Assert(deletes, checker.DeepEquals, tt.deletes, check.Commentf(tt.name+" (deletes)"))
 	}
 }
+
+func (ds *PolicyTestSuite) TestMapState_DenyPreferredInsertWithSubnets(c *check.C) {
+	identityCache := cache.IdentityCache{
+		identity.ReservedIdentityWorld: labels.LabelWorld.LabelArray(),
+		worldIPIdentity:                lblWorldIP,                  // "192.0.2.3/32"
+		worldSubnetIdentity:            lblWorldSubnet.LabelArray(), // "192.0.2.0/24"
+	}
+
+	reservedWorldID := identity.ReservedIdentityWorld.Uint32()
+	worldIPID := worldIPIdentity.Uint32()
+	worldSubnetID := worldSubnetIdentity.Uint32()
+	selectorCache := testNewSelectorCache(identityCache)
+	type action uint16
+	const (
+		noAction = action(iota)
+		insertA  = action(1 << iota)
+		insertB
+		insertAWithBProto
+		insertBWithAProto
+
+		insertBoth            = insertA | insertB
+		canDeleteAInsertsBoth = insertBoth
+		canDeleteBInsertsBoth = insertBoth
+	)
+	// these tests are based on the sheet https://docs.google.com/spreadsheets/d/1WANIoZGB48nryylQjjOw6lKjI80eVgPShrdMTMalLEw#gid=2109052536
+	tests := []struct {
+		name                 string
+		aIdentity, bIdentity uint32
+		aIsDeny, bIsDeny     bool
+		aPort                uint16
+		aProto               uint8
+		bPort                uint16
+		bProto               uint8
+		outcome              action
+	}{
+		// deny-allow insertions
+		{"deny-allow: a superset a|b L3-only", reservedWorldID, worldSubnetID, true, false, 0, 0, 0, 0, insertA},
+		{"deny-allow: b superset a|b L3-only", worldIPID, worldSubnetID, true, false, 0, 0, 0, 0, insertBoth},
+		{"deny-allow: a superset a L3-only, b L4", reservedWorldID, worldSubnetID, true, false, 0, 0, 0, 6, insertA},
+		{"deny-allow: b superset a L3-only, b L4", worldIPID, worldSubnetID, true, false, 0, 0, 0, 6, insertBoth | insertAWithBProto},
+		{"deny-allow: a superset a L3-only, b L3L4", reservedWorldID, worldSubnetID, true, false, 0, 0, 80, 6, insertA},
+		{"deny-allow: b superset a L3-only, b L3L4", worldIPID, worldSubnetID, true, false, 0, 0, 80, 6, insertBoth | insertAWithBProto},
+		{"deny-allow: a superset a L4, b L3-only", reservedWorldID, worldSubnetID, true, false, 0, 6, 0, 0, insertBoth},
+		{"deny-allow: b superset a L4, b L3-only", worldIPID, worldSubnetID, true, false, 0, 6, 0, 0, insertBoth},
+		{"deny-allow: a superset a L4, b L4", reservedWorldID, worldSubnetID, true, false, 0, 6, 0, 6, insertA},
+		{"deny-allow: b superset a L4, b L4", worldIPID, worldSubnetID, true, false, 0, 6, 0, 6, insertBoth},
+		{"deny-allow: a superset a L4, b L3L4", reservedWorldID, worldSubnetID, true, false, 0, 6, 80, 6, insertA},
+		{"deny-allow: b superset a L4, b L3L4", worldIPID, worldSubnetID, true, false, 0, 6, 80, 6, insertBoth | insertAWithBProto},
+		{"deny-allow: a superset a L3L4, b L3-only", reservedWorldID, worldSubnetID, true, false, 80, 6, 0, 0, insertBoth},
+		{"deny-allow: b superset a L3L4, b L3-only", worldIPID, worldSubnetID, true, false, 80, 6, 0, 0, insertBoth},
+		{"deny-allow: a superset a L3L4, b L4", reservedWorldID, worldSubnetID, true, false, 80, 6, 0, 6, insertBoth},
+		{"deny-allow: b superset a L3L4, b L4", worldIPID, worldSubnetID, true, false, 80, 6, 0, 6, insertBoth},
+		{"deny-allow: a superset a L3L4, b L3L4", reservedWorldID, worldSubnetID, true, false, 80, 6, 80, 6, insertA},
+		{"deny-allow: b superset a L3L4, b L3L4", worldIPID, worldSubnetID, true, false, 80, 6, 80, 6, insertBoth},
+
+		// deny-deny insertions: Note: We do not delete all redundant deny-deny insertions that we could.
+		// We only delete entries redundant to L3-only port protocols, all other port-protocol supersets
+		// *do not* have this effect.
+		{"deny-deny: a superset a|b L3-only", worldSubnetID, worldIPID, true, true, 0, 0, 0, 0, insertA},
+		{"deny-deny: b superset a|b L3-only", worldSubnetID, reservedWorldID, true, true, 0, 0, 0, 0, insertB},
+		{"deny-deny: a superset a L3-only, b L4", worldSubnetID, worldIPID, true, true, 0, 0, 0, 6, insertA},
+		{"deny-deny: b superset a L3-only, b L4", worldSubnetID, reservedWorldID, true, true, 0, 0, 0, 6, insertBoth},
+		{"deny-deny: a superset a L3-only, b L3L4", worldSubnetID, worldIPID, true, true, 0, 0, 80, 6, insertA},
+		{"deny-deny: b superset a L3-only, b L3L4", worldSubnetID, reservedWorldID, true, true, 0, 0, 80, 6, insertBoth},
+		{"deny-deny: a superset a L4, b L3-only", worldSubnetID, worldIPID, true, true, 0, 6, 0, 0, insertBoth},
+		{"deny-deny: b superset a L4, b L3-only", worldSubnetID, reservedWorldID, true, true, 0, 6, 0, 0, insertB},
+		{"deny-deny: a superset a L4, b L4", worldSubnetID, worldIPID, true, true, 0, 6, 0, 6, canDeleteBInsertsBoth},
+		{"deny-deny: b superset a L4, b L4", worldSubnetID, reservedWorldID, true, true, 0, 6, 0, 6, canDeleteAInsertsBoth},
+		{"deny-deny: a superset a L4, b L3L4", worldSubnetID, worldIPID, true, true, 0, 6, 80, 6, canDeleteBInsertsBoth},
+		{"deny-deny: b superset a L4, b L3L4", worldSubnetID, reservedWorldID, true, true, 0, 6, 80, 6, insertBoth},
+		{"deny-deny: a superset a L3L4, b L3-only", worldSubnetID, worldIPID, true, true, 80, 6, 0, 0, insertBoth},
+		{"deny-deny: b superset a L3L4, b L3-only", worldSubnetID, reservedWorldID, true, true, 80, 6, 0, 0, insertB},
+		{"deny-deny: a superset a L3L4, b L4", worldSubnetID, worldIPID, true, true, 80, 6, 0, 6, insertBoth},
+		{"deny-deny: b superset a L3L4, b L4", worldSubnetID, reservedWorldID, true, true, 80, 6, 0, 6, canDeleteAInsertsBoth},
+		{"deny-deny: a superset a L3L4, b L3L4", worldSubnetID, worldIPID, true, true, 80, 6, 80, 6, canDeleteBInsertsBoth},
+		{"deny-deny: b superset a L3L4, b L3L4", worldSubnetID, reservedWorldID, true, true, 80, 6, 80, 6, canDeleteAInsertsBoth},
+		// allow-allow insertions do not need to be tests as they will all be inserted
+	}
+	for _, tt := range tests {
+		aKey := Key{Identity: tt.aIdentity, DestPort: tt.aPort, Nexthdr: tt.aProto}
+		aEntry := MapStateEntry{IsDeny: tt.aIsDeny}
+		bKey := Key{Identity: tt.bIdentity, DestPort: tt.bPort, Nexthdr: tt.bProto}
+		bEntry := MapStateEntry{IsDeny: tt.bIsDeny}
+		expectedKeys := MapState{}
+		if tt.outcome&insertA > 0 {
+			expectedKeys[aKey] = aEntry
+		}
+		if tt.outcome&insertB > 0 {
+			expectedKeys[bKey] = bEntry
+		}
+		if tt.outcome&insertAWithBProto > 0 {
+			aKeyWithBProto := Key{Identity: tt.aIdentity, DestPort: tt.bPort, Nexthdr: tt.bProto}
+			aEntryCpy := MapStateEntry{IsDeny: tt.aIsDeny}
+			aEntryCpy.owners = map[MapStateOwner]struct{}{aKey: {}}
+			aEntry.AddDependent(aKeyWithBProto)
+			expectedKeys[aKey] = aEntry
+			expectedKeys[aKeyWithBProto] = aEntryCpy
+		}
+		if tt.outcome&insertBWithAProto > 0 {
+			bKeyWithBProto := Key{Identity: tt.bIdentity, DestPort: tt.aPort, Nexthdr: tt.aProto}
+			bEntryCpy := MapStateEntry{IsDeny: tt.bIsDeny}
+			bEntryCpy.owners = map[MapStateOwner]struct{}{bKey: {}}
+			bEntry.AddDependent(bKeyWithBProto)
+			expectedKeys[bKey] = bEntry
+			expectedKeys[bKeyWithBProto] = bEntryCpy
+		}
+		outcomeKeys := MapState{}
+		outcomeKeys.DenyPreferredInsert(aKey, aEntry, selectorCache)
+		outcomeKeys.DenyPreferredInsert(bKey, bEntry, selectorCache)
+		c.Assert(outcomeKeys, checker.DeepEquals, expectedKeys, check.Commentf(tt.name))
+	}
+	// Now test all cases with different traffic directions.
+	// This should result in both entries being inserted with
+	// no changes, as they do not affect one another anymore.
+	for _, tt := range tests {
+		aKey := Key{Identity: tt.aIdentity, DestPort: tt.aPort, Nexthdr: tt.aProto}
+		aEntry := MapStateEntry{IsDeny: tt.aIsDeny}
+		bKey := Key{Identity: tt.bIdentity, DestPort: tt.bPort, Nexthdr: tt.bProto, TrafficDirection: 1}
+		bEntry := MapStateEntry{IsDeny: tt.bIsDeny}
+		expectedKeys := MapState{}
+		expectedKeys[aKey] = aEntry
+		expectedKeys[bKey] = bEntry
+		outcomeKeys := MapState{}
+		outcomeKeys.DenyPreferredInsert(aKey, aEntry, selectorCache)
+		outcomeKeys.DenyPreferredInsert(bKey, bEntry, selectorCache)
+		c.Assert(outcomeKeys, checker.DeepEquals, expectedKeys, check.Commentf("different traffic directions %s", tt.name))
+	}
+}