1 /* 2 Copyright 2022 The Kubernetes Authors. 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 package validation 18 19 import ( 20 "fmt" 21 "math" 22 "sort" 23 24 "k8s.io/apiextensions-apiserver/pkg/apis/apiextensions" 25 structuralschema "k8s.io/apiextensions-apiserver/pkg/apiserver/schema" 26 "k8s.io/apiextensions-apiserver/pkg/apiserver/schema/cel/model" 27 "k8s.io/apimachinery/pkg/util/validation/field" 28 "k8s.io/apiserver/pkg/cel" 29 ) 30 31 // unbounded uses nil to represent an unbounded cardinality value. 32 var unbounded *uint64 = nil 33 34 // CELSchemaContext keeps track of data used by x-kubernetes-validations rules for a specific schema node. 35 type CELSchemaContext struct { 36 // withinValidationRuleScope is true if the schema at the current level or above have x-kubernetes-validations rules. typeInfo 37 // should only be populated for schema nodes where this is true. 38 withinValidationRuleScope bool 39 40 // typeInfo is lazily loaded for schema nodes withinValidationRuleScope and may be 41 // populated one of two possible ways: 42 // 1. Using a typeInfoAccessor to access it from the parent's type info. This is a cheap operation and should be 43 // used when a schema at a higher level already has type info. 44 // 2. Using a converter to construct type info from the jsonSchema. This is an expensive operation. 45 typeInfo *CELTypeInfo 46 // typeInfoErr is any cached error resulting from an attempt to lazily load typeInfo. 47 typeInfoErr error 48 49 // parent is the context of the parent schema node, or nil if this is the context for the root schema node. 50 parent *CELSchemaContext 51 // typeInfoAccessor provides a way to access the type info of this schema node from the parent CELSchemaContext. 52 // nil if not extraction is possible, or the parent is nil. 53 typeInfoAccessor typeInfoAccessor 54 55 // jsonSchema is the schema for this CELSchemaContext node. It must be non-nil. 56 jsonSchema *apiextensions.JSONSchemaProps 57 // converter converts a JSONSchemaProps to CELTypeInfo. 58 // Tests that check how many conversions are performed during CRD validation wrap DefaultConverter 59 // with a converter that counts how many conversion operations. 60 converter converter 61 62 // MaxCardinality represents a limit to the number of data elements that can exist for the current 63 // schema based on MaxProperties or MaxItems limits present on parent schemas, If all parent 64 // map and array schemas have MaxProperties or MaxItems limits declared MaxCardinality is 65 // an int pointer representing the product of these limits. If least one parent map or list schema 66 // does not have a MaxProperties or MaxItems limits set, the MaxCardinality is nil, indicating 67 // that the parent schemas offer no bound to the number of times a data element for the current 68 // schema can exist. 69 MaxCardinality *uint64 70 // TotalCost accumulates the x-kubernetes-validators estimated rule cost total for an entire custom resource 71 // definition. A single TotalCost is allocated for each CustomResourceDefinition and passed through the stack as the 72 // CustomResourceDefinition's OpenAPIv3 schema is recursively validated. 73 TotalCost *TotalCost 74 } 75 76 // TypeInfo returns the CELTypeInfo for this CELSchemaContext node. Returns nil, nil if this CELSchemaContext is nil, 77 // or if current level or above does not have x-kubernetes-validations rules. The returned type info is shared and 78 // should not be modified by the caller. 79 func (c *CELSchemaContext) TypeInfo() (*CELTypeInfo, error) { 80 if c == nil || !c.withinValidationRuleScope { 81 return nil, nil 82 } 83 if c.typeInfo != nil || c.typeInfoErr != nil { 84 return c.typeInfo, c.typeInfoErr // return already computed result if available 85 } 86 87 // If able to get the type info from the parent's type info, prefer this approach 88 // since it is more efficient. 89 if c.parent != nil { 90 parentTypeInfo, parentErr := c.parent.TypeInfo() 91 if parentErr != nil { 92 c.typeInfoErr = parentErr 93 return nil, parentErr 94 } 95 if parentTypeInfo != nil && c.typeInfoAccessor != nil { 96 c.typeInfo = c.typeInfoAccessor.accessTypeInfo(parentTypeInfo) 97 if c.typeInfo != nil { 98 return c.typeInfo, nil 99 } 100 } 101 } 102 // If unable to get the type info from the parent, convert the jsonSchema to type info. 103 // This is expensive for large schemas. 104 c.typeInfo, c.typeInfoErr = c.converter(c.jsonSchema, c.parent == nil || c.jsonSchema.XEmbeddedResource) 105 return c.typeInfo, c.typeInfoErr 106 } 107 108 // CELTypeInfo represents all the typeInfo needed by CEL to compile x-kubernetes-validations rules for a schema node. 109 type CELTypeInfo struct { 110 // Schema is a structural schema for this CELSchemaContext node. It must be non-nil. 111 Schema *structuralschema.Structural 112 // DeclType is a CEL declaration representation of Schema of this CELSchemaContext node. It must be non-nil. 113 DeclType *cel.DeclType 114 } 115 116 // converter converts from JSON schema to a structural schema and a CEL declType, or returns an error if the conversion 117 // fails. This should be defaultConverter except in tests where it is useful to wrap it with a converter that tracks 118 // how many conversions have been performed. 119 type converter func(schema *apiextensions.JSONSchemaProps, isRoot bool) (*CELTypeInfo, error) 120 121 func defaultConverter(schema *apiextensions.JSONSchemaProps, isRoot bool) (*CELTypeInfo, error) { 122 structural, err := structuralschema.NewStructural(schema) 123 if err != nil { 124 return nil, err 125 } 126 declType := model.SchemaDeclType(structural, isRoot) 127 if declType == nil { 128 return nil, fmt.Errorf("unable to convert structural schema to CEL declarations") 129 } 130 return &CELTypeInfo{structural, declType}, nil 131 } 132 133 // RootCELContext constructs CELSchemaContext for the given root schema. 134 func RootCELContext(schema *apiextensions.JSONSchemaProps) *CELSchemaContext { 135 rootCardinality := uint64(1) 136 r := &CELSchemaContext{ 137 jsonSchema: schema, 138 withinValidationRuleScope: len(schema.XValidations) > 0, 139 MaxCardinality: &rootCardinality, 140 TotalCost: &TotalCost{}, 141 converter: defaultConverter, 142 } 143 return r 144 } 145 146 // ChildPropertyContext returns nil, nil if this CELSchemaContext is nil, otherwise constructs and returns a 147 // CELSchemaContext for propertyName. 148 func (c *CELSchemaContext) ChildPropertyContext(propSchema *apiextensions.JSONSchemaProps, propertyName string) *CELSchemaContext { 149 if c == nil { 150 return nil 151 } 152 return c.childContext(propSchema, propertyTypeInfoAccessor{propertyName: propertyName}) 153 } 154 155 // ChildAdditionalPropertiesContext returns nil, nil if this CELSchemaContext is nil, otherwise it constructs and returns 156 // a CELSchemaContext for the properties of an object if this CELSchemaContext is an object. 157 // schema must be non-nil and have a non-nil schema.AdditionalProperties. 158 func (c *CELSchemaContext) ChildAdditionalPropertiesContext(propsSchema *apiextensions.JSONSchemaProps) *CELSchemaContext { 159 if c == nil { 160 return nil 161 } 162 return c.childContext(propsSchema, additionalItemsTypeInfoAccessor{}) 163 } 164 165 // ChildItemsContext returns nil, nil if this CELSchemaContext is nil, otherwise it constructs and returns a CELSchemaContext 166 // for the items of an array if this CELSchemaContext is an array. 167 func (c *CELSchemaContext) ChildItemsContext(itemsSchema *apiextensions.JSONSchemaProps) *CELSchemaContext { 168 if c == nil { 169 return nil 170 } 171 return c.childContext(itemsSchema, itemsTypeInfoAccessor{}) 172 } 173 174 // childContext returns nil, nil if this CELSchemaContext is nil, otherwise it constructs a new CELSchemaContext for the 175 // given child schema of the current schema context. 176 // accessor optionally provides a way to access CELTypeInfo of the child from the current schema context's CELTypeInfo. 177 // childContext returns a CELSchemaContext where the MaxCardinality is multiplied by the 178 // factor that the schema increases the cardinality of its children. If the CELSchemaContext's 179 // MaxCardinality is unbounded (nil) or the factor that the schema increase the cardinality 180 // is unbounded, the resulting CELSchemaContext's MaxCardinality is also unbounded. 181 func (c *CELSchemaContext) childContext(child *apiextensions.JSONSchemaProps, accessor typeInfoAccessor) *CELSchemaContext { 182 result := &CELSchemaContext{ 183 parent: c, 184 typeInfoAccessor: accessor, 185 withinValidationRuleScope: c.withinValidationRuleScope, 186 TotalCost: c.TotalCost, 187 MaxCardinality: unbounded, 188 converter: c.converter, 189 } 190 if child != nil { 191 result.jsonSchema = child 192 if len(child.XValidations) > 0 { 193 result.withinValidationRuleScope = true 194 } 195 } 196 if c.jsonSchema == nil { 197 // nil schemas can be passed since we call ChildSchemaContext 198 // before ValidateCustomResourceDefinitionOpenAPISchema performs its nil check 199 return result 200 } 201 if c.MaxCardinality == unbounded { 202 return result 203 } 204 maxElements := extractMaxElements(c.jsonSchema) 205 if maxElements == unbounded { 206 return result 207 } 208 result.MaxCardinality = uint64ptr(multiplyWithOverflowGuard(*c.MaxCardinality, *maxElements)) 209 return result 210 } 211 212 type typeInfoAccessor interface { 213 // accessTypeInfo looks up type information for a child schema from a non-nil parentTypeInfo and returns it, 214 // or returns nil if the child schema information is not accessible. For example, a nil 215 // return value is expected when a property name is unescapable in CEL. 216 // The caller MUST ensure the provided parentTypeInfo is non-nil. 217 accessTypeInfo(parentTypeInfo *CELTypeInfo) *CELTypeInfo 218 } 219 220 type propertyTypeInfoAccessor struct { 221 // propertyName is the property name in the parent schema that this schema is declared at. 222 propertyName string 223 } 224 225 func (c propertyTypeInfoAccessor) accessTypeInfo(parentTypeInfo *CELTypeInfo) *CELTypeInfo { 226 if parentTypeInfo.Schema.Properties != nil { 227 propSchema := parentTypeInfo.Schema.Properties[c.propertyName] 228 if escapedPropName, ok := cel.Escape(c.propertyName); ok { 229 if fieldDeclType, ok := parentTypeInfo.DeclType.Fields[escapedPropName]; ok { 230 return &CELTypeInfo{Schema: &propSchema, DeclType: fieldDeclType.Type} 231 } // else fields with unknown types are omitted from CEL validation entirely 232 } // fields with unescapable names are expected to be absent 233 } 234 return nil 235 } 236 237 type itemsTypeInfoAccessor struct{} 238 239 func (c itemsTypeInfoAccessor) accessTypeInfo(parentTypeInfo *CELTypeInfo) *CELTypeInfo { 240 if parentTypeInfo.Schema.Items != nil { 241 itemsSchema := parentTypeInfo.Schema.Items 242 itemsDeclType := parentTypeInfo.DeclType.ElemType 243 return &CELTypeInfo{Schema: itemsSchema, DeclType: itemsDeclType} 244 } 245 return nil 246 } 247 248 type additionalItemsTypeInfoAccessor struct{} 249 250 func (c additionalItemsTypeInfoAccessor) accessTypeInfo(parentTypeInfo *CELTypeInfo) *CELTypeInfo { 251 if parentTypeInfo.Schema.AdditionalProperties != nil { 252 propsSchema := parentTypeInfo.Schema.AdditionalProperties.Structural 253 valuesDeclType := parentTypeInfo.DeclType.ElemType 254 return &CELTypeInfo{Schema: propsSchema, DeclType: valuesDeclType} 255 } 256 return nil 257 } 258 259 // TotalCost tracks the total cost of evaluating all the x-kubernetes-validations rules of a CustomResourceDefinition. 260 type TotalCost struct { 261 // Total accumulates the x-kubernetes-validations estimated rule cost total. 262 Total uint64 263 // MostExpensive accumulates the top 4 most expensive rules contributing to the Total. Only rules 264 // that accumulate at least 1% of total cost limit are included. 265 MostExpensive []RuleCost 266 } 267 268 // ObserveExpressionCost accumulates the cost of evaluating a -kubernetes-validations rule. 269 func (c *TotalCost) ObserveExpressionCost(path *field.Path, cost uint64) { 270 if math.MaxUint64-c.Total < cost { 271 c.Total = math.MaxUint64 272 } else { 273 c.Total += cost 274 } 275 276 if cost < StaticEstimatedCRDCostLimit/100 { // ignore rules that contribute < 1% of total cost limit 277 return 278 } 279 c.MostExpensive = append(c.MostExpensive, RuleCost{Path: path, Cost: cost}) 280 sort.Slice(c.MostExpensive, func(i, j int) bool { 281 // sort in descending order so the most expensive rule is first 282 return c.MostExpensive[i].Cost > c.MostExpensive[j].Cost 283 }) 284 if len(c.MostExpensive) > 4 { 285 c.MostExpensive = c.MostExpensive[:4] 286 } 287 } 288 289 // RuleCost represents the cost of evaluating a single x-kubernetes-validations rule. 290 type RuleCost struct { 291 Path *field.Path 292 Cost uint64 293 } 294 295 // extractMaxElements returns the factor by which the schema increases the cardinality 296 // (number of possible data elements) of its children. If schema is a map and has 297 // MaxProperties or an array has MaxItems, the int pointer of the max value is returned. 298 // If schema is a map or array and does not have MaxProperties or MaxItems, 299 // unbounded (nil) is returned to indicate that there is no limit to the possible 300 // number of data elements imposed by the current schema. If the schema is an object, 1 is 301 // returned to indicate that there is no increase to the number of possible data elements 302 // for its children. Primitives do not have children, but 1 is returned for simplicity. 303 func extractMaxElements(schema *apiextensions.JSONSchemaProps) *uint64 { 304 switch schema.Type { 305 case "object": 306 if schema.AdditionalProperties != nil { 307 if schema.MaxProperties != nil { 308 maxProps := uint64(zeroIfNegative(*schema.MaxProperties)) 309 return &maxProps 310 } 311 return unbounded 312 } 313 // return 1 to indicate that all fields of an object exist at most one for 314 // each occurrence of the object they are fields of 315 return uint64ptr(1) 316 case "array": 317 if schema.MaxItems != nil { 318 maxItems := uint64(zeroIfNegative(*schema.MaxItems)) 319 return &maxItems 320 } 321 return unbounded 322 default: 323 return uint64ptr(1) 324 } 325 } 326 327 func zeroIfNegative(v int64) int64 { 328 if v < 0 { 329 return 0 330 } 331 return v 332 } 333 334 func uint64ptr(i uint64) *uint64 { 335 return &i 336 } 337