| // Copyright 2023 Google LLC | |
| // | |
| // Licensed under the Apache License, Version 2.0 (the "License"); | |
| // you may not use this file except in compliance with the License. | |
| // You may obtain a copy of the License at | |
| // | |
| // http://www.apache.org/licenses/LICENSE-2.0 | |
| // | |
| // Unless required by applicable law or agreed to in writing, software | |
| // distributed under the License is distributed on an "AS IS" BASIS, | |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| // See the License for the specific language governing permissions and | |
| // limitations under the License. | |
| package cel | |
| import ( | |
| "context" | |
| "fmt" | |
| "reflect" | |
| "regexp" | |
| "cel.dev/cel-go/common/ast" | |
| "cel.dev/cel-go/common/env" | |
| "cel.dev/cel-go/common/overloads" | |
| "cel.dev/cel-go/common/types" | |
| ) | |
| const ( | |
| durationValidatorName = "cel.validator.duration" | |
| regexValidatorName = "cel.validator.matches" | |
| timestampValidatorName = "cel.validator.timestamp" | |
| homogeneousValidatorName = "cel.validator.homogeneous_literals" | |
| nestingLimitValidatorName = "cel.validator.comprehension_nesting_limit" | |
| bindNestingLimitValidatorName = "cel.validator.bind_nesting_limit" | |
| regexProgramSizeLimitValidatorName = "cel.validator.regex_program_size_limit" | |
| // HomogeneousAggregateLiteralExemptFunctions is the ValidatorConfig key used to configure | |
| // the set of function names which are exempt from homogeneous type checks. The expected type | |
| // is a string list of function names. | |
| // | |
| // As an example, the `<string>.format([args])` call expects the input arguments list to be | |
| // comprised of a variety of types which correspond to the types expected by the format control | |
| // clauses; however, all other uses of a mixed element type list, would be unexpected. | |
| HomogeneousAggregateLiteralExemptFunctions = homogeneousValidatorName + ".exempt" | |
| ) | |
| var ( | |
| astValidatorFactories = map[string]ASTValidatorFactory{ | |
| nestingLimitValidatorName: func(val *env.Validator) (ASTValidator, error) { | |
| limit, err := validatorIntConfig(val, "limit") | |
| if err != nil { | |
| return nil, err | |
| } | |
| return ValidateComprehensionNestingLimit(limit), nil | |
| }, | |
| bindNestingLimitValidatorName: func(val *env.Validator) (ASTValidator, error) { | |
| limit, err := validatorIntConfig(val, "limit") | |
| if err != nil { | |
| return nil, err | |
| } | |
| return ValidateBindNestingLimit(limit), nil | |
| }, | |
| regexProgramSizeLimitValidatorName: func(val *env.Validator) (ASTValidator, error) { | |
| limit, err := validatorIntConfig(val, "limit") | |
| if err != nil { | |
| return nil, err | |
| } | |
| return ValidateRegexProgramSizeLimit(limit), nil | |
| }, | |
| durationValidatorName: func(*env.Validator) (ASTValidator, error) { | |
| return ValidateDurationLiterals(), nil | |
| }, | |
| regexValidatorName: func(*env.Validator) (ASTValidator, error) { | |
| return ValidateRegexLiterals(), nil | |
| }, | |
| timestampValidatorName: func(*env.Validator) (ASTValidator, error) { | |
| return ValidateTimestampLiterals(), nil | |
| }, | |
| homogeneousValidatorName: func(*env.Validator) (ASTValidator, error) { | |
| return ValidateHomogeneousAggregateLiterals(), nil | |
| }, | |
| } | |
| ) | |
| // ASTValidatorFactory creates an ASTValidator as configured by the input map | |
| type ASTValidatorFactory func(*env.Validator) (ASTValidator, error) | |
| // ASTValidators configures a set of ASTValidator instances into the target environment. | |
| // | |
| // Validators are applied in the order in which they are specified. | |
| // If an ASTValidator with the same name is already configured, it will be replaced. | |
| func ASTValidators(validators ...ASTValidator) EnvOption { | |
| return func(e *Env) (*Env, error) { | |
| for _, v := range validators { | |
| found := false | |
| for i, existing := range e.validators { | |
| if existing.Name() == v.Name() { | |
| e.validators[i] = v | |
| found = true | |
| break | |
| } | |
| } | |
| if !found { | |
| e.validators = append(e.validators, v) | |
| } | |
| } | |
| return e, nil | |
| } | |
| } | |
| // ASTValidator defines a singleton interface for validating a type-checked Ast against an environment. | |
| // | |
| // Note: the Issues argument is mutable in the sense that it is intended to collect errors which will be | |
| // reported to the caller. | |
| type ASTValidator interface { | |
| // Name returns the name of the validator. Names must be unique. | |
| Name() string | |
| // Validate validates a given Ast within an Environment and collects a set of potential issues. | |
| // | |
| // The ValidatorConfig is generated from the set of ASTValidatorConfigurer instances prior to | |
| // the invocation of the Validate call. The expectation is that the validator configuration | |
| // is created in sequence and immutable once provided to the Validate call. | |
| // | |
| // See individual validators for more information on their configuration keys and configuration | |
| // properties. | |
| Validate(*Env, ValidatorConfig, *ast.AST, *Issues) | |
| } | |
| // ConfigurableASTValidator supports conversion of an object to an `env.Validator` instance used for | |
| // YAML serialization. | |
| type ConfigurableASTValidator interface { | |
| // ToConfig converts the internal configuration of an ASTValidator into an env.Validator instance | |
| // which minimally must include the validator name, but may also include a map[string]any config | |
| // object to be serialized to YAML. The string keys represent the configuration parameter name, | |
| // and the any value must mirror the internally supported type associated with the config key. | |
| // | |
| // Note: only primitive CEL types are supported by CEL validators at this time. | |
| ToConfig() *env.Validator | |
| } | |
| // ValidatorConfig provides an accessor method for querying validator configuration state. | |
| type ValidatorConfig interface { | |
| GetOrDefault(name string, value any) any | |
| } | |
| // MutableValidatorConfig provides mutation methods for querying and updating validator configuration | |
| // settings. | |
| type MutableValidatorConfig interface { | |
| ValidatorConfig | |
| Set(name string, value any) error | |
| } | |
| // ASTValidatorConfigurer indicates that this object, currently expected to be an ASTValidator, | |
| // participates in validator configuration settings. | |
| // | |
| // This interface may be split from the expectation of being an ASTValidator instance in the future. | |
| type ASTValidatorConfigurer interface { | |
| Configure(MutableValidatorConfig) error | |
| } | |
| // validatorConfig implements the ValidatorConfig and MutableValidatorConfig interfaces. | |
| type validatorConfig struct { | |
| data map[string]any | |
| } | |
| // newValidatorConfig initializes the validator config with default values for core CEL validators. | |
| func newValidatorConfig() *validatorConfig { | |
| return &validatorConfig{ | |
| data: map[string]any{ | |
| HomogeneousAggregateLiteralExemptFunctions: []string{}, | |
| }, | |
| } | |
| } | |
| // GetOrDefault returns the configured value for the name, if present, else the input default value. | |
| // | |
| // Note, the type-agreement between the input default and configured value is not checked on read. | |
| func (config *validatorConfig) GetOrDefault(name string, value any) any { | |
| v, found := config.data[name] | |
| if !found { | |
| return value | |
| } | |
| return v | |
| } | |
| // Set configures a validator option with the given name and value. | |
| // | |
| // If the value had previously been set, the new value must have the same reflection type as the old one, | |
| // or the call will error. | |
| func (config *validatorConfig) Set(name string, value any) error { | |
| v, found := config.data[name] | |
| if found && reflect.TypeOf(v) != reflect.TypeOf(value) { | |
| return fmt.Errorf("incompatible configuration type for %s, got %T, wanted %T", name, value, v) | |
| } | |
| config.data[name] = value | |
| return nil | |
| } | |
| // ExtendedValidations collects a set of common AST validations which reduce the likelihood of runtime errors. | |
| // | |
| // - Validate duration and timestamp literals | |
| // - Ensure regex strings are valid | |
| // - Disable mixed type list and map literals | |
| func ExtendedValidations() EnvOption { | |
| return ASTValidators( | |
| ValidateDurationLiterals(), | |
| ValidateTimestampLiterals(), | |
| ValidateRegexLiterals(), | |
| ValidateHomogeneousAggregateLiterals(), | |
| ) | |
| } | |
| // ValidateDurationLiterals ensures that duration literal arguments are valid immediately after type-check. | |
| func ValidateDurationLiterals() ASTValidator { | |
| return newFormatValidator(overloads.TypeConvertDuration, 0, evalCall) | |
| } | |
| // ValidateTimestampLiterals ensures that timestamp literal arguments are valid immediately after type-check. | |
| func ValidateTimestampLiterals() ASTValidator { | |
| return newFormatValidator(overloads.TypeConvertTimestamp, 0, evalCall) | |
| } | |
| // ValidateRegexLiterals ensures that regex patterns are validated after type-check. | |
| func ValidateRegexLiterals() ASTValidator { | |
| return newFormatValidator(overloads.Matches, 0, compileRegex) | |
| } | |
| // ValidateHomogeneousAggregateLiterals checks that all list and map literals entries have the same types, i.e. | |
| // no mixed list element types or mixed map key or map value types. | |
| // | |
| // Note: the string format call relies on a mixed element type list for ease of use, so this check skips all | |
| // literals which occur within string format calls. | |
| func ValidateHomogeneousAggregateLiterals() ASTValidator { | |
| return homogeneousAggregateLiteralValidator{} | |
| } | |
| // ValidateComprehensionNestingLimit ensures that comprehension nesting does not exceed the specified limit. | |
| // | |
| // This validator can be useful for preventing arbitrarily nested comprehensions which can take high polynomial | |
| // time to complete. | |
| // | |
| // Note, this limit does not apply to comprehensions with an empty iteration range, as these comprehensions have | |
| // no actual looping cost. The cel.bind() utilizes the comprehension structure to perform local variable | |
| // assignments and supplies an empty iteration range, so they won't count against the nesting limit either. | |
| func ValidateComprehensionNestingLimit(limit int) ASTValidator { | |
| return nestingLimitValidator{limit: limit} | |
| } | |
| // ValidateBindNestingLimit ensures that cel.bind() macro nesting does not exceed the specified limit. | |
| // | |
| // This validator can be useful for preventing arbitrarily nested cel.bind() macro calls. | |
| func ValidateBindNestingLimit(limit int) ASTValidator { | |
| return bindNestingLimitValidator{limit: limit} | |
| } | |
| // ValidateRegexProgramSizeLimit ensures that regex pattern literals do not exceed the specified regex program size limit. | |
| func ValidateRegexProgramSizeLimit(limit int) ASTValidator { | |
| return regexProgramSizeLimitValidator{limit: limit} | |
| } | |
| type argChecker func(env *Env, call, arg ast.Expr) error | |
| func newFormatValidator(funcName string, argNum int, check argChecker) formatValidator { | |
| return formatValidator{ | |
| funcName: funcName, | |
| check: check, | |
| argNum: argNum, | |
| } | |
| } | |
| type formatValidator struct { | |
| funcName string | |
| argNum int | |
| check argChecker | |
| } | |
| // Name returns the unique name of this function format validator. | |
| func (v formatValidator) Name() string { | |
| return fmt.Sprintf("cel.validator.%s", v.funcName) | |
| } | |
| // ToConfig converts the ASTValidator to an env.Validator specifying the validator name. | |
| func (v formatValidator) ToConfig() *env.Validator { | |
| return env.NewValidator(v.Name()) | |
| } | |
| // Validate searches the AST for uses of a given function name with a constant argument and performs a check | |
| // on whether the argument is a valid literal value. | |
| func (v formatValidator) Validate(e *Env, _ ValidatorConfig, a *ast.AST, iss *Issues) { | |
| root := ast.NavigateAST(a) | |
| funcCalls := ast.MatchDescendants(root, ast.FunctionMatcher(v.funcName)) | |
| for _, call := range funcCalls { | |
| callArgs := call.AsCall().Args() | |
| if len(callArgs) <= v.argNum { | |
| continue | |
| } | |
| litArg := callArgs[v.argNum] | |
| if litArg.Kind() != ast.LiteralKind { | |
| continue | |
| } | |
| if err := v.check(e, call, litArg); err != nil { | |
| iss.ReportErrorAtID(litArg.ID(), "invalid %s argument", v.funcName) | |
| } | |
| } | |
| } | |
| func evalCall(env *Env, call, arg ast.Expr) error { | |
| ast := &Ast{impl: ast.NewAST(call, ast.NewSourceInfo(nil))} | |
| prg, err := env.Program(ast) | |
| if err != nil { | |
| return err | |
| } | |
| resCh := prg.ConcurrentEval(context.Background(), NoVars()) | |
| res := <-resCh | |
| return res.Err | |
| } | |
| func compileRegex(_ *Env, _, arg ast.Expr) error { | |
| pattern := arg.AsLiteral().Value().(string) | |
| _, err := regexp.Compile(pattern) | |
| return err | |
| } | |
| type homogeneousAggregateLiteralValidator struct{} | |
| // Name returns the unique name of the homogeneous type validator. | |
| func (homogeneousAggregateLiteralValidator) Name() string { | |
| return homogeneousValidatorName | |
| } | |
| // ToConfig converts the ASTValidator to an env.Validator specifying the validator name. | |
| func (v homogeneousAggregateLiteralValidator) ToConfig() *env.Validator { | |
| return env.NewValidator(v.Name()) | |
| } | |
| // Validate validates that all lists and map literals have homogeneous types, i.e. don't contain dyn types. | |
| // | |
| // This validator makes an exception for list and map literals which occur at any level of nesting within | |
| // string format calls. | |
| func (v homogeneousAggregateLiteralValidator) Validate(_ *Env, c ValidatorConfig, a *ast.AST, iss *Issues) { | |
| var exemptedFunctions []string | |
| exemptedFunctions = c.GetOrDefault(HomogeneousAggregateLiteralExemptFunctions, exemptedFunctions).([]string) | |
| root := ast.NavigateAST(a) | |
| listExprs := ast.MatchDescendants(root, ast.KindMatcher(ast.ListKind)) | |
| for _, listExpr := range listExprs { | |
| if inExemptFunction(listExpr, exemptedFunctions) { | |
| continue | |
| } | |
| l := listExpr.AsList() | |
| elements := l.Elements() | |
| optIndices := l.OptionalIndices() | |
| var elemType *Type | |
| for i, e := range elements { | |
| et := a.GetType(e.ID()) | |
| if isOptionalIndex(i, optIndices) { | |
| et = et.Parameters()[0] | |
| } | |
| if elemType == nil { | |
| elemType = et | |
| continue | |
| } | |
| if !elemType.IsEquivalentType(et) { | |
| v.typeMismatch(iss, e.ID(), elemType, et) | |
| break | |
| } | |
| } | |
| } | |
| mapExprs := ast.MatchDescendants(root, ast.KindMatcher(ast.MapKind)) | |
| for _, mapExpr := range mapExprs { | |
| if inExemptFunction(mapExpr, exemptedFunctions) { | |
| continue | |
| } | |
| m := mapExpr.AsMap() | |
| entries := m.Entries() | |
| var keyType, valType *Type | |
| for _, e := range entries { | |
| mapEntry := e.AsMapEntry() | |
| key, val := mapEntry.Key(), mapEntry.Value() | |
| kt, vt := a.GetType(key.ID()), a.GetType(val.ID()) | |
| if mapEntry.IsOptional() { | |
| vt = vt.Parameters()[0] | |
| } | |
| if keyType == nil && valType == nil { | |
| keyType, valType = kt, vt | |
| continue | |
| } | |
| if !keyType.IsEquivalentType(kt) { | |
| v.typeMismatch(iss, key.ID(), keyType, kt) | |
| } | |
| if !valType.IsEquivalentType(vt) { | |
| v.typeMismatch(iss, val.ID(), valType, vt) | |
| } | |
| } | |
| } | |
| } | |
| func inExemptFunction(e ast.NavigableExpr, exemptFunctions []string) bool { | |
| parent, found := e.Parent() | |
| for found { | |
| if parent.Kind() == ast.CallKind { | |
| fnName := parent.AsCall().FunctionName() | |
| for _, exempt := range exemptFunctions { | |
| if exempt == fnName { | |
| return true | |
| } | |
| } | |
| } | |
| parent, found = parent.Parent() | |
| } | |
| return false | |
| } | |
| func isOptionalIndex(i int, optIndices []int32) bool { | |
| for _, optInd := range optIndices { | |
| if i == int(optInd) { | |
| return true | |
| } | |
| } | |
| return false | |
| } | |
| func (homogeneousAggregateLiteralValidator) typeMismatch(iss *Issues, id int64, expected, actual *Type) { | |
| iss.ReportErrorAtID(id, "expected type '%s' but found '%s'", FormatCELType(expected), FormatCELType(actual)) | |
| } | |
| type nestingLimitValidator struct { | |
| limit int | |
| } | |
| // Name returns the name of the nesting limit validator. | |
| func (v nestingLimitValidator) Name() string { | |
| return nestingLimitValidatorName | |
| } | |
| // ToConfig converts the ASTValidator to an env.Validator specifying the validator name and the nesting limit | |
| // as an integer value: {"limit": int} | |
| func (v nestingLimitValidator) ToConfig() *env.Validator { | |
| return env.NewValidator(v.Name()).SetConfig(map[string]any{"limit": v.limit}) | |
| } | |
| // Validate implements the ASTValidator interface method. | |
| func (v nestingLimitValidator) Validate(e *Env, _ ValidatorConfig, a *ast.AST, iss *Issues) { | |
| root := ast.NavigateAST(a) | |
| comprehensions := ast.MatchDescendants(root, ast.KindMatcher(ast.ComprehensionKind)) | |
| if len(comprehensions) <= v.limit { | |
| return | |
| } | |
| for _, comp := range comprehensions { | |
| count := 0 | |
| e := comp | |
| hasParent := true | |
| for hasParent { | |
| // When the expression is not a comprehension, continue to the next ancestor. | |
| if e.Kind() != ast.ComprehensionKind { | |
| e, hasParent = e.Parent() | |
| continue | |
| } | |
| // When the comprehension has an empty range, continue to the next ancestor | |
| // as this comprehension does not have any associated cost. | |
| if isEmptyRangeComprehension(e) { | |
| e, hasParent = e.Parent() | |
| continue | |
| } | |
| // Otherwise check the nesting limit. | |
| count++ | |
| if count > v.limit { | |
| iss.ReportErrorAtID(comp.ID(), "comprehension exceeds nesting limit") | |
| break | |
| } | |
| e, hasParent = e.Parent() | |
| } | |
| } | |
| } | |
| type bindNestingLimitValidator struct { | |
| limit int | |
| } | |
| // Name returns the name of the cel.bind nesting limit validator. | |
| func (v bindNestingLimitValidator) Name() string { | |
| return bindNestingLimitValidatorName | |
| } | |
| // ToConfig converts the ASTValidator to an env.Validator specifying the validator name and the nesting limit | |
| // as an integer value: {"limit": int} | |
| func (v bindNestingLimitValidator) ToConfig() *env.Validator { | |
| return env.NewValidator(v.Name()).SetConfig(map[string]any{"limit": v.limit}) | |
| } | |
| type regexProgramSizeLimitValidator struct { | |
| limit int | |
| } | |
| // Name returns the name of the regex program size limit validator. | |
| func (v regexProgramSizeLimitValidator) Name() string { | |
| return regexProgramSizeLimitValidatorName | |
| } | |
| // ToConfig converts the ASTValidator to an env.Validator specifying the validator name and the limit. | |
| func (v regexProgramSizeLimitValidator) ToConfig() *env.Validator { | |
| return env.NewValidator(v.Name()).SetConfig(map[string]any{"limit": v.limit}) | |
| } | |
| // Validate implements the ASTValidator interface method. | |
| func (v bindNestingLimitValidator) Validate(e *Env, _ ValidatorConfig, a *ast.AST, iss *Issues) { | |
| root := ast.NavigateAST(a) | |
| comprehensions := ast.MatchDescendants(root, ast.KindMatcher(ast.ComprehensionKind)) | |
| var celBinds []ast.NavigableExpr | |
| for _, comp := range comprehensions { | |
| if isCelBind(comp) { | |
| celBinds = append(celBinds, comp) | |
| } | |
| } | |
| if len(celBinds) <= v.limit { | |
| return | |
| } | |
| for _, comp := range celBinds { | |
| count := 0 | |
| e := comp | |
| hasParent := true | |
| for hasParent { | |
| if isCelBind(e) { | |
| count++ | |
| if count > v.limit { | |
| iss.ReportErrorAtID(comp.ID(), "cel.bind exceeds nesting limit") | |
| break | |
| } | |
| } | |
| e, hasParent = e.Parent() | |
| } | |
| } | |
| } | |
| func (v regexProgramSizeLimitValidator) Validate(e *Env, _ ValidatorConfig, a *ast.AST, iss *Issues) { | |
| if v.limit <= 0 { | |
| return | |
| } | |
| root := ast.NavigateAST(a) | |
| callExprs := ast.MatchDescendants(root, ast.KindMatcher(ast.CallKind)) | |
| for _, call := range callExprs { | |
| c := call.AsCall() | |
| fn := c.FunctionName() | |
| if !isRegexFunctionName(fn) { | |
| continue | |
| } | |
| args := c.Args() | |
| var regexArgIndex int | |
| if (fn == overloads.Matches || fn == "matches") && c.Target() != nil { | |
| regexArgIndex = 0 | |
| } else { | |
| regexArgIndex = 1 | |
| } | |
| if len(args) <= regexArgIndex { | |
| continue | |
| } | |
| arg := args[regexArgIndex] | |
| if arg.Kind() != ast.LiteralKind { | |
| continue | |
| } | |
| pattern, ok := arg.AsLiteral().Value().(string) | |
| if !ok { | |
| continue | |
| } | |
| sz, err := types.RegexProgramSize(pattern) | |
| if err != nil { | |
| // Invalid regex literals are handled in a different validator. | |
| continue | |
| } | |
| if sz > v.limit { | |
| iss.ReportErrorAtID(arg.ID(), "regex program size %d exceeds limit of %d", sz, v.limit) | |
| } | |
| } | |
| } | |
| func isEmptyRangeComprehension(e ast.NavigableExpr) bool { | |
| if e.Kind() != ast.ComprehensionKind { | |
| return false | |
| } | |
| iterRange := e.AsComprehension().IterRange() | |
| return iterRange.Kind() == ast.ListKind && iterRange.AsList().Size() == 0 | |
| } | |
| func isCelBind(e ast.NavigableExpr) bool { | |
| if !isEmptyRangeComprehension(e) { | |
| return false | |
| } | |
| compre := e.AsComprehension() | |
| loopCond := compre.LoopCondition() | |
| loopStep := compre.LoopStep() | |
| return compre.IterVar() == unusedIterVar && | |
| loopCond.Kind() == ast.LiteralKind && loopCond.AsLiteral().Value() == false && | |
| loopStep.Kind() == ast.IdentKind && loopStep.AsIdent() == compre.AccuVar() | |
| } | |
| func isRegexFunctionName(fn string) bool { | |
| return fn == overloads.Matches || fn == "matches" || fn == "regex.extract" || fn == "regex.extractAll" || fn == "regex.replace" | |
| } | |
| func validatorIntConfig(val *env.Validator, configKey string) (int, error) { | |
| if limit, found := val.ConfigValue(configKey); found { | |
| // In case of protos, config value is of type google.protobuf.Value, which numeric values are always a double. | |
| if v, isDouble := limit.(float64); isDouble { | |
| if v != float64(int64(v)) { | |
| return 0, fmt.Errorf("invalid validator: %s, %s value is not a whole number: %v", val.Name, configKey, limit) | |
| } | |
| return int(v), nil | |
| } | |
| if v, isInt := limit.(int); isInt { | |
| return v, nil | |
| } | |
| return 0, fmt.Errorf("invalid validator: %s unsupported %s type: %v", val.Name, configKey, limit) | |
| } | |
| return 0, fmt.Errorf("invalid validator: %s missing %s", val.Name, configKey) | |
| } |