walker_test.go

Documentation: k8s.io/kube-openapi/pkg/schemamutation

     1  /*
     2  Copyright 2019 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 schemamutation
    18  
    19  import (
    20  	"encoding/json"
    21  	"fmt"
    22  	"math"
    23  	"math/rand"
    24  	"reflect"
    25  	"regexp"
    26  	"strings"
    27  	"testing"
    28  	"time"
    29  
    30  	fuzz "github.com/google/gofuzz"
    31  	"k8s.io/kube-openapi/pkg/util/jsontesting"
    32  	"k8s.io/kube-openapi/pkg/util/sets"
    33  	"k8s.io/kube-openapi/pkg/validation/spec"
    34  )
    35  
    36  func fuzzFuncs(f *fuzz.Fuzzer, refFunc func(ref *spec.Ref, c fuzz.Continue, visible bool)) {
    37  	invisible := 0 // == 0 means visible, > 0 means invisible
    38  	depth := 0
    39  	maxDepth := 3
    40  	nilChance := func(depth int) float64 {
    41  		return math.Pow(0.9, math.Max(0.0, float64(maxDepth-depth)))
    42  	}
    43  	updateFuzzer := func(depth int) {
    44  		f.NilChance(nilChance(depth))
    45  		f.NumElements(0, max(0, maxDepth-depth))
    46  	}
    47  	updateFuzzer(depth)
    48  	enter := func(o interface{}, recursive bool, c fuzz.Continue) {
    49  		if recursive {
    50  			depth++
    51  			updateFuzzer(depth)
    52  		}
    53  
    54  		invisible++
    55  		c.FuzzNoCustom(o)
    56  		invisible--
    57  	}
    58  	leave := func(recursive bool) {
    59  		if recursive {
    60  			depth--
    61  			updateFuzzer(depth)
    62  		}
    63  	}
    64  	f.Funcs(
    65  		func(ref *spec.Ref, c fuzz.Continue) {
    66  			refFunc(ref, c, invisible == 0)
    67  		},
    68  		func(sa *spec.SchemaOrStringArray, c fuzz.Continue) {
    69  			*sa = spec.SchemaOrStringArray{}
    70  			if c.RandBool() {
    71  				c.Fuzz(&sa.Schema)
    72  			} else {
    73  				c.Fuzz(&sa.Property)
    74  			}
    75  			if sa.Schema == nil && len(sa.Property) == 0 {
    76  				*sa = spec.SchemaOrStringArray{Schema: &spec.Schema{}}
    77  			}
    78  		},
    79  		func(url *spec.SchemaURL, c fuzz.Continue) {
    80  			*url = spec.SchemaURL("http://url")
    81  		},
    82  		func(s *spec.Swagger, c fuzz.Continue) {
    83  			enter(s, false, c)
    84  			defer leave(false)
    85  
    86  			// only fuzz those fields we walk into with invisible==false
    87  			c.Fuzz(&s.Parameters)
    88  			c.Fuzz(&s.Responses)
    89  			c.Fuzz(&s.Definitions)
    90  			c.Fuzz(&s.Paths)
    91  		},
    92  		func(p *spec.PathItem, c fuzz.Continue) {
    93  			enter(p, false, c)
    94  			defer leave(false)
    95  
    96  			// only fuzz those fields we walk into with invisible==false
    97  			c.Fuzz(&p.Parameters)
    98  			c.Fuzz(&p.Delete)
    99  			c.Fuzz(&p.Get)
   100  			c.Fuzz(&p.Head)
   101  			c.Fuzz(&p.Options)
   102  			c.Fuzz(&p.Patch)
   103  			c.Fuzz(&p.Post)
   104  			c.Fuzz(&p.Put)
   105  		},
   106  		func(p *spec.Parameter, c fuzz.Continue) {
   107  			enter(p, false, c)
   108  			defer leave(false)
   109  
   110  			// only fuzz those fields we walk into with invisible==false
   111  			c.Fuzz(&p.Ref)
   112  			c.Fuzz(&p.Schema)
   113  			if c.RandBool() {
   114  				p.Items = &spec.Items{}
   115  				c.Fuzz(&p.Items.Ref)
   116  			} else {
   117  				p.Items = nil
   118  			}
   119  		},
   120  		func(s *spec.Response, c fuzz.Continue) {
   121  			enter(s, false, c)
   122  			defer leave(false)
   123  
   124  			// only fuzz those fields we walk into with invisible==false
   125  			c.Fuzz(&s.Ref)
   126  			c.Fuzz(&s.Description)
   127  			c.Fuzz(&s.Schema)
   128  			c.Fuzz(&s.Examples)
   129  		},
   130  		func(s *spec.Dependencies, c fuzz.Continue) {
   131  			enter(s, false, c)
   132  			defer leave(false)
   133  
   134  			// and nothing with invisible==false
   135  		},
   136  		func(p *spec.SimpleSchema, c fuzz.Continue) {
   137  			// gofuzz is broken and calls this even for *SimpleSchema fields, ignoring NilChance, leading to infinite recursion
   138  			if c.Float64() > nilChance(depth) {
   139  				return
   140  			}
   141  
   142  			enter(p, true, c)
   143  			defer leave(true)
   144  
   145  			c.FuzzNoCustom(p)
   146  		},
   147  		func(s *spec.SchemaProps, c fuzz.Continue) {
   148  			// gofuzz is broken and calls this even for *SchemaProps fields, ignoring NilChance, leading to infinite recursion
   149  			if c.Float64() > nilChance(depth) {
   150  				return
   151  			}
   152  
   153  			enter(s, true, c)
   154  			defer leave(true)
   155  
   156  			c.FuzzNoCustom(s)
   157  		},
   158  		func(i *interface{}, c fuzz.Continue) {
   159  			// do nothing for examples and defaults. These are free form JSON fields.
   160  		},
   161  	)
   162  }
   163  
   164  func TestReplaceReferences(t *testing.T) {
   165  	visibleRE, err := regexp.Compile("\"\\$ref\":\"(http://ref-[^\"]*)\"")
   166  	if err != nil {
   167  		t.Fatalf("failed to compile ref regex: %v", err)
   168  	}
   169  	invisibleRE, err := regexp.Compile("\"\\$ref\":\"(http://invisible-[^\"]*)\"")
   170  	if err != nil {
   171  		t.Fatalf("failed to compile ref regex: %v", err)
   172  	}
   173  
   174  	for i := 0; i < 1000; i++ {
   175  		var visibleRefs, invisibleRefs sets.String
   176  		var seed int64
   177  		var randSource rand.Source
   178  		var s *spec.Swagger
   179  		for {
   180  			visibleRefs = sets.NewString()
   181  			invisibleRefs = sets.NewString()
   182  
   183  			f := fuzz.New()
   184  			seed = time.Now().UnixNano()
   185  			//seed = int64(1549012506261785182)
   186  			randSource = rand.New(rand.NewSource(seed))
   187  			f.RandSource(randSource)
   188  
   189  			visibleRefsNum := 0
   190  			invisibleRefsNum := 0
   191  			fuzzFuncs(f,
   192  				func(ref *spec.Ref, c fuzz.Continue, visible bool) {
   193  					var url string
   194  					if visible {
   195  						// this is a ref that is seen by the walker (we have some exceptions where we don't walk into)
   196  						url = fmt.Sprintf("http://ref-%d", visibleRefsNum)
   197  						visibleRefsNum++
   198  					} else {
   199  						// this is a ref that is not seen by the walker (we have some exceptions where we don't walk into)
   200  						url = fmt.Sprintf("http://invisible-%d", invisibleRefsNum)
   201  						invisibleRefsNum++
   202  					}
   203  
   204  					r, err := spec.NewRef(url)
   205  					if err != nil {
   206  						t.Fatalf("failed to fuzz ref: %v", err)
   207  					}
   208  					*ref = r
   209  				},
   210  			)
   211  
   212  			// create random swagger spec with random URL references, but at least one ref
   213  			s = &spec.Swagger{}
   214  			f.Fuzz(s)
   215  
   216  			// clone spec to normalize (fuzz might generate objects which do not roundtrip json marshalling
   217  			var err error
   218  			s, err = cloneSwagger(s)
   219  			if err != nil {
   220  				t.Fatalf("failed to normalize swagger after fuzzing: %v", err)
   221  			}
   222  
   223  			// find refs
   224  			bs, err := s.MarshalJSON()
   225  			if err != nil {
   226  				t.Fatalf("failed to marshal swagger: %v", err)
   227  			}
   228  			for _, m := range invisibleRE.FindAllStringSubmatch(string(bs), -1) {
   229  				invisibleRefs.Insert(m[1])
   230  			}
   231  			if res := visibleRE.FindAllStringSubmatch(string(bs), -1); len(res) > 0 {
   232  				for _, m := range res {
   233  					visibleRefs.Insert(m[1])
   234  				}
   235  				break
   236  			}
   237  		}
   238  
   239  		t.Run(fmt.Sprintf("iteration %d", i), func(t *testing.T) {
   240  			mutatedRefs := sets.NewString()
   241  			mutationProbability := rand.New(randSource).Float64()
   242  			for _, vr := range visibleRefs.List() {
   243  				if rand.New(randSource).Float64() > mutationProbability {
   244  					mutatedRefs.Insert(vr)
   245  				}
   246  			}
   247  
   248  			origString, err := s.MarshalJSON()
   249  			if err != nil {
   250  				t.Fatalf("failed to marshal swagger: %v", err)
   251  			}
   252  			t.Logf("created schema with %d walked refs, %d invisible refs, mutating %v, seed %d: %s", visibleRefs.Len(), invisibleRefs.Len(), mutatedRefs.List(), seed, string(origString))
   253  
   254  			// convert to json string, replace one of the refs, and unmarshal back
   255  			mutatedString := string(origString)
   256  			for _, r := range mutatedRefs.List() {
   257  				mr := strings.Replace(r, "ref", "mutated", -1)
   258  				mutatedString = strings.Replace(mutatedString, "\""+r+"\"", "\""+mr+"\"", -1)
   259  			}
   260  			mutatedViaJSON := &spec.Swagger{}
   261  			if err := json.Unmarshal([]byte(mutatedString), mutatedViaJSON); err != nil {
   262  				t.Fatalf("failed to unmarshal mutated spec: %v", err)
   263  			}
   264  
   265  			// replay the same mutation using the mutating walker
   266  			seenRefs := sets.NewString()
   267  			walker := Walker{
   268  				RefCallback: func(ref *spec.Ref) *spec.Ref {
   269  					seenRefs.Insert(ref.String())
   270  					if mutatedRefs.Has(ref.String()) {
   271  						r, err := spec.NewRef(strings.Replace(ref.String(), "ref", "mutated", -1))
   272  						if err != nil {
   273  							t.Fatalf("failed to create ref: %v", err)
   274  						}
   275  						return &r
   276  					}
   277  					return ref
   278  				},
   279  				SchemaCallback: SchemaCallBackNoop,
   280  			}
   281  			mutatedViaWalker := walker.WalkRoot(s)
   282  
   283  			// compare that we got the same
   284  			if !reflect.DeepEqual(mutatedViaJSON, mutatedViaWalker) {
   285  				t.Errorf("mutation via walker differ from JSON text replacement (got A, expected B): %s", objectDiff(mutatedViaWalker, mutatedViaJSON))
   286  			}
   287  			if !seenRefs.HasAll(visibleRefs.List()...) {
   288  				t.Errorf("expected to see the same refs in the walker as during fuzzing. Not seen: %v", visibleRefs.Difference(seenRefs).List())
   289  			}
   290  			if shouldNotSee := seenRefs.Intersection(invisibleRefs); shouldNotSee.Len() > 0 {
   291  				t.Errorf("refs seen that the walker is not expected to see: %v", shouldNotSee.List())
   292  			}
   293  		})
   294  	}
   295  }
   296  
   297  func TestReplaceSchema(t *testing.T) {
   298  	for i := 0; i < 1000; i++ {
   299  		t.Run(fmt.Sprintf("iteration-%d", i), func(t *testing.T) {
   300  			seed := time.Now().UnixNano()
   301  			f := fuzz.NewWithSeed(seed).NilChance(0).MaxDepth(5)
   302  			rootSchema := &spec.Schema{}
   303  			f.Funcs(func(s *spec.Schema, c fuzz.Continue) {
   304  				c.Fuzz(&s.Description)
   305  				s.Description += " original"
   306  				if c.RandBool() {
   307  					// append enums
   308  					var enums []string
   309  					c.Fuzz(&enums)
   310  					for _, enum := range enums {
   311  						s.Enum = append(s.Enum, enum)
   312  					}
   313  				}
   314  				if c.RandBool() {
   315  					c.Fuzz(&s.Properties)
   316  				}
   317  				if c.RandBool() {
   318  					c.Fuzz(&s.AdditionalProperties)
   319  				}
   320  				if c.RandBool() {
   321  					c.Fuzz(&s.PatternProperties)
   322  				}
   323  				if c.RandBool() {
   324  					c.Fuzz(&s.AdditionalItems)
   325  				}
   326  				if c.RandBool() {
   327  					c.Fuzz(&s.AnyOf)
   328  				}
   329  				if c.RandBool() {
   330  					c.Fuzz(&s.AllOf)
   331  				}
   332  				if c.RandBool() {
   333  					c.Fuzz(&s.OneOf)
   334  				}
   335  				if c.RandBool() {
   336  					c.Fuzz(&s.Not)
   337  				}
   338  				if c.RandBool() {
   339  					c.Fuzz(&s.Definitions)
   340  				}
   341  				if c.RandBool() {
   342  					items := new(spec.SchemaOrArray)
   343  					if c.RandBool() {
   344  						c.Fuzz(&items.Schema)
   345  					} else {
   346  						c.Fuzz(&items.Schemas)
   347  					}
   348  					s.Items = items
   349  				}
   350  			})
   351  			f.Fuzz(rootSchema)
   352  			w := &Walker{SchemaCallback: func(schema *spec.Schema) *spec.Schema {
   353  				s := *schema
   354  				s.Description = strings.Replace(s.Description, "original", "modified", -1)
   355  				return &s
   356  			}, RefCallback: RefCallbackNoop}
   357  			newSchema := w.WalkSchema(rootSchema)
   358  			origBytes, err := json.Marshal(rootSchema)
   359  			if err != nil {
   360  				t.Fatalf("cannot marshal original schema: %v", err)
   361  			}
   362  			origJSON := string(origBytes)
   363  			mutatedWithString := strings.Replace(origJSON, "original", "modified", -1)
   364  			newBytes, err := json.Marshal(newSchema)
   365  			if err != nil {
   366  				t.Fatalf("cannot marshal mutated schema: %v", err)
   367  			}
   368  			if err := jsontesting.JsonCompare(newBytes, []byte(mutatedWithString)); err != nil {
   369  				t.Error(err)
   370  			}
   371  			if !strings.Contains(origJSON, `"enum":[`) {
   372  				t.Logf("did not contain enum, skipping enum checks")
   373  				return
   374  			}
   375  			// test enum removal
   376  			w = &Walker{SchemaCallback: func(schema *spec.Schema) *spec.Schema {
   377  				s := *schema
   378  				s.Enum = nil
   379  				return &s
   380  			}, RefCallback: RefCallbackNoop}
   381  			newSchema = w.WalkSchema(rootSchema)
   382  			newBytes, err = json.Marshal(newSchema)
   383  			if err != nil {
   384  				t.Fatalf("cannot marshal mutated schema: %v", err)
   385  			}
   386  			if strings.Contains(string(newBytes), `"enum":[`) {
   387  				t.Errorf("enum still exists in %q", newBytes)
   388  			}
   389  		})
   390  	}
   391  }
   392  
   393  func cloneSwagger(orig *spec.Swagger) (*spec.Swagger, error) {
   394  	bs, err := orig.MarshalJSON()
   395  	if err != nil {
   396  		return nil, fmt.Errorf("error marshaling: %v", err)
   397  	}
   398  	s := &spec.Swagger{}
   399  	if err := json.Unmarshal(bs, s); err != nil {
   400  		return nil, fmt.Errorf("error unmarshaling: %v", err)
   401  	}
   402  	return s, nil
   403  }
   404  
   405  // stringDiff diffs a and b and returns a human readable diff.
   406  func stringDiff(a, b string) string {
   407  	ba := []byte(a)
   408  	bb := []byte(b)
   409  	out := []byte{}
   410  	i := 0
   411  	for ; i < len(ba) && i < len(bb); i++ {
   412  		if ba[i] != bb[i] {
   413  			break
   414  		}
   415  		out = append(out, ba[i])
   416  	}
   417  	out = append(out, []byte("\n\nA: ")...)
   418  	out = append(out, ba[i:]...)
   419  	out = append(out, []byte("\n\nB: ")...)
   420  	out = append(out, bb[i:]...)
   421  	out = append(out, []byte("\n\n")...)
   422  	return string(out)
   423  }
   424  
   425  // objectDiff writes the two objects out as JSON and prints out the identical part of
   426  // the objects followed by the remaining part of 'a' and finally the remaining part of 'b'.
   427  // For debugging tests.
   428  func objectDiff(a, b interface{}) string {
   429  	ab, err := json.Marshal(a)
   430  	if err != nil {
   431  		panic(fmt.Sprintf("a: %v", err))
   432  	}
   433  	bb, err := json.Marshal(b)
   434  	if err != nil {
   435  		panic(fmt.Sprintf("b: %v", err))
   436  	}
   437  	return stringDiff(string(ab), string(bb))
   438  }
   439  
   440  func max(i, j int) int {
   441  	if i > j {
   442  		return i
   443  	}
   444  	return j
   445  }
   446
View as plain text