CEL cost budgeting inconsistent rejections

[alexzielenski]

What happened?

I attempted to apply the following CRDs to kubernetes local cluster running from rev 759785e

stable.example.com_mapimmutablekeys.yaml

---
apiVersion: apiextensions.k8s.io/v1
kind: CustomResourceDefinition
metadata:
  annotations:
    controller-gen.kubebuilder.io/version: v0.9.2
  creationTimestamp: null
  name: mapimmutablekeys.stable.example.com
spec:
  group: stable.example.com
  names:
    kind: MapImmutableKeys
    listKind: MapImmutableKeysList
    plural: mapimmutablekeys
    singular: mapimmutablekeys
  scope: Namespaced
  versions:
  - name: v1
    schema:
      openAPIV3Schema:
        description: A map which does not allow set of keys to be changed after creation.
          But the values may be changed
        properties:
          apiVersion:
            description: 'APIVersion defines the versioned schema of this representation
              of an object. Servers should convert recognized schemas to the latest
              internal value, and may reject unrecognized values. More info: https://git.k8s.io/community/contributors/devel/sig-architecture/api-conventions.md#resources'
            type: string
          kind:
            description: 'Kind is a string value representing the REST resource this
              object represents. Servers may infer this from the endpoint the client
              submits requests to. Cannot be updated. In CamelCase. More info: https://git.k8s.io/community/contributors/devel/sig-architecture/api-conventions.md#types-kinds'
            type: string
          metadata:
            type: object
          values:
            additionalProperties:
              maxLength: 1
              type: string
            maxProperties: 1
            type: object
            x-kubernetes-validations:
            - message: Set of keys may not change
              rule: oldSelf.size() == self.size() && oldSelf.all(key, key in self)
        type: object
    served: true
    storage: true

stable.example.com_mapappendonlykeys.yaml

---
apiVersion: apiextensions.k8s.io/v1
kind: CustomResourceDefinition
metadata:
  annotations:
    controller-gen.kubebuilder.io/version: v0.9.2
  creationTimestamp: null
  name: mapappendonlykeys.stable.example.com
spec:
  group: stable.example.com
  names:
    kind: MapAppendOnlyKeys
    listKind: MapAppendOnlyKeysList
    plural: mapappendonlykeys
    singular: mapappendonlykeys
  scope: Namespaced
  versions:
  - name: v1
    schema:
      openAPIV3Schema:
        description: A map which does not allow keys to be removed or their values
          changed once set. New keys may be added, however.
        properties:
          apiVersion:
            description: 'APIVersion defines the versioned schema of this representation
              of an object. Servers should convert recognized schemas to the latest
              internal value, and may reject unrecognized values. More info: https://git.k8s.io/community/contributors/devel/sig-architecture/api-conventions.md#resources'
            type: string
          kind:
            description: 'Kind is a string value representing the REST resource this
              object represents. Servers may infer this from the endpoint the client
              submits requests to. Cannot be updated. In CamelCase. More info: https://git.k8s.io/community/contributors/devel/sig-architecture/api-conventions.md#types-kinds'
            type: string
          metadata:
            type: object
          values:
            additionalProperties:
              maxLength: 1
              type: string
            maxProperties: 1
            type: object
            x-kubernetes-validations:
            - message: Keys may not be removed and their values must stay the same
              rule: oldSelf.all(key, key in self && self[key] == oldSelf[key])
        type: object
        x-kubernetes-validations:
        - message: Value is required once set
          rule: '!has(oldSelf.values) || has(self.values)'
    served: true
    storage: true

Applying the CRDs:

$ kubectl apply -f stable.example.com_mapimmutablekeys.yaml
The CustomResourceDefinition "mapimmutablekeys.stable.example.com" is invalid: 
* spec.validation.openAPIV3Schema.properties[values].x-kubernetes-validations[0].rule: Forbidden: estimated rule cost exceeds budget by factor of more than 100x (try simplifying the rule, or adding maxItems, maxProperties, and maxLength where arrays, maps, and strings are declared)
* spec.validation.openAPIV3Schema.properties[values].x-kubernetes-validations[0].rule: Forbidden: contributed to estimated rule cost total exceeding cost limit for entire OpenAPIv3 schema
* spec.validation.openAPIV3Schema: Forbidden: x-kubernetes-validations estimated rule cost total for entire OpenAPIv3 schema exceeds budget by factor of more than 100x (try simplifying the rule, or adding maxItems, maxProperties, and maxLength where arrays, maps, and strings are declared)

$ kubectl apply -f stable.example.com_mapappendonlykeys.yaml
customresourcedefinition.apiextensions.k8s.io/mapappendonlykeys.stable.example.com created

Diff of two CRDs for convenience (red is nonworking, green is working):

8c8
<   name: mapimmutablekeys.stable.example.com
---
>   name: mapappendonlykeys.stable.example.com
12,15c12,15
<     kind: MapImmutableKeys
<     listKind: MapImmutableKeysList
<     plural: mapimmutablekeys
<     singular: mapimmutablekeys
---
>     kind: MapAppendOnlyKeys
>     listKind: MapAppendOnlyKeysList
>     plural: mapappendonlykeys
>     singular: mapappendonlykeys
21,22c21,22
<         description: A map which does not allow set of keys to be changed after creation.
<           But the values may be changed
---
>         description: A map which does not allow keys to be removed or their values
>           changed once set. New keys may be added, however.
43,44c43,44
<             - message: Set of keys may not change
<               rule: oldSelf.size() == self.size() && oldSelf.all(key, key in self)
---
>             - message: Keys may not be removed and their values must stay the same
>               rule: oldSelf.all(key, key in self && self[key] == oldSelf[key])
45a46,48
>         x-kubernetes-validations:
>         - message: Value is required once set
>           rule: '!has(oldSelf.values) || has(self.values)'

What did you expect to happen?

I expected both CRDs to be accepted by the apiserver.

How can we reproduce it (as minimally and precisely as possible)?

Apply the two CRDs from above.

Anything else we need to know?

/sig api-machinery
/triage accepted
/assign @DangerOnTheRanger

Kubernetes version

$ kubectl version
❯ kubectl version                                                                       main*​​ 
WARNING: This version information is deprecated and will be replaced with the output from kubectl version --short.  Use --output=yaml|json to get the full version.
Client Version: version.Info{Major:"1", Minor:"25+", GitVersion:"v1.25.0-beta.0.35+3a81341cfa6f7e-dirty", GitCommit:"3a81341cfa6f7e2ca1b9bfc195c567dcdfaa4dea", GitTreeState:"dirty", BuildDate:"2022-08-09T15:56:40Z", GoVersion:"go1.19rc2", Compiler:"gc", Platform:"darwin/arm64"}
Kustomize Version: v4.5.7
Server Version: version.Info{Major:"1", Minor:"25+", GitVersion:"v1.25.0-beta.0.35+3a81341cfa6f7e-dirty", GitCommit:"3a81341cfa6f7e2ca1b9bfc195c567dcdfaa4dea", GitTreeState:"dirty", BuildDate:"2022-08-09T15:50:06Z", GoVersion:"go1.19rc2", Compiler:"gc", Platform:"darwin/arm64"}

Cloud provider

N/A

OS version

No response

Install tools

No response

Container runtime (CRI) and version (if applicable)

No response

Related plugins (CNI, CSI, ...) and versions (if applicable)

No response

[alexzielenski]

self.size() == self.size() is also rejected

but after I removed oldSelf.size() == self.size() condition from the broken CRD, kubernetes permitted me to create it. So that's likely a good place to start looking

[jpbetz]

Looks like there the case where this happens is fairly specific. When a function that returns a single scalar result (e.g. size()) is the argument to a function where the cost depends on the sizes of the argument (e.g. equals()/==) the size is miscalculated as MaxInt and so the resulting cost is very high.

@DangerOnTheRanger is working on a fix.

Impacted use cases are comparison operator (==, >, <, >=, <=) where both operands are function calls returning a scalar. This includes size(), isSorted(), conversions, comparisons, ...

[DangerOnTheRanger]

Should be fixed by google/cel-go#571.

[liggitt]

is this a blocker for 1.25?

[jpbetz]

I don't think we should block 1.25 on this one. The practical situations are can happen are specific enough that I don't think waiting one more patch release is a big deal. We can fix in 1.25.1 and then backport (in cel-go we are going to backport the fix to the cel-go versions used by 1.24 and 1.23).