tools/syz-imagegen: rewrite combination generation

Introduce a new Filesystem parameter - the maximum number of resulting
seeds.

If the total number of flag combinations exceeds this number, switch to
generating a covering array (that is, make sure that all flag value
pairs are covered, or at least as many of them as possible).

3 files changed, 252 insertions, 19 deletions

diff --git a/tools/syz-imagegen/combinations.go b/tools/syz-imagegen/combinations.go
new file mode 100644
index 000000000..0be6d69ec
--- /dev/null
+++ b/tools/syz-imagegen/combinations.go
@@ -0,0 +1,168 @@
+// Copyright 2025 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package main
+
+import "sort"
+
+// CoveringArray returns an array of representative parameter value combinations.
+// The method considers parameters from the first to the last and first tries to
+// generate all possible combinations of their values.
+// If N != 0, the method eventually switches to ensuring that all value pairs
+// are represented, once all pairs are covered - all triples (aka Covering Array).
+func CoveringArray(params [][]string, n int) [][]string {
+	var ret [][]int
+	for paramID, param := range params {
+		if len(ret) == 0 {
+			ret = append(ret, []int{})
+		}
+		// If we can explore all combinations, do it.
+		if len(ret)*len(param) <= n || n == 0 {
+			var newRet [][]int
+			for value := range param {
+				for _, row := range ret {
+					newRet = append(newRet, extendRow(row, value))
+				}
+			}
+			ret = newRet
+			continue
+		}
+		cover := &pairCoverage{cover: map[pairCombo]struct{}{}}
+
+		// First, select a value for each row.
+		var newRet [][]int
+		for _, row := range ret {
+			bestValue, bestCount := 0, coverDelta{}
+			for valueID := range param {
+				newCount := cover.wouldCover(row, paramID, valueID)
+				if newCount.betterThan(bestCount) {
+					bestValue = valueID
+					bestCount = newCount
+				}
+			}
+			newRet = append(newRet, extendRow(row, bestValue))
+			cover.record(row, paramID, bestValue)
+		}
+
+		// Now that all previous combinations are preserved, we can (as long as
+		// we don't exceed N) duplicate some of the rows to cover more.
+		for len(newRet) < n {
+			var bestRow []int
+			bestValue, bestCount := 0, coverDelta{}
+			for _, row := range ret {
+				for valueID := range param {
+					newCount := cover.wouldCover(row, paramID, valueID)
+					if newCount.betterThan(bestCount) {
+						bestRow = row
+						bestValue = valueID
+						bestCount = newCount
+					}
+				}
+			}
+			if !bestCount.betterThan(coverDelta{}) {
+				break
+			}
+			newRet = append(newRet, extendRow(bestRow, bestValue))
+			cover.record(bestRow, paramID, bestValue)
+		}
+		ret = newRet
+	}
+	sort.Slice(ret, func(i, j int) bool {
+		rowA, rowB := ret[i], ret[j]
+		for k := 0; k < len(rowA); k++ {
+			if rowA[k] != rowB[k] {
+				return rowA[k] < rowB[k]
+			}
+		}
+		return false
+	})
+	var retStrings [][]string
+	for _, row := range ret {
+		var stringRow []string
+		for paramID, valueID := range row {
+			stringRow = append(stringRow, params[paramID][valueID])
+		}
+		retStrings = append(retStrings, stringRow)
+	}
+	return retStrings
+}
+
+type pairCoverage struct {
+	cover map[pairCombo]struct{}
+}
+
+type coverDelta struct {
+	pairs   int
+	triples int
+}
+
+func (c coverDelta) betterThan(other coverDelta) bool {
+	if c.pairs != other.pairs {
+		return c.pairs > other.pairs
+	}
+	return c.triples > other.triples
+}
+
+// By how much the coverage would increase if we append newVal to the row.
+// The first integer is the number of newly covered pairs of values,
+// the second integer is the number of newly covered triples of values.
+func (pc *pairCoverage) wouldCover(row []int, newID, newVal int) coverDelta {
+	var pairs, triples int
+	for _, item := range rowToPairCombos(row, false, newID, newVal) {
+		if _, ok := pc.cover[item]; !ok {
+			pairs++
+		}
+	}
+	for _, item := range rowToPairCombos(row, true, newID, newVal) {
+		if _, ok := pc.cover[item]; !ok {
+			triples++
+		}
+	}
+	return coverDelta{pairs, triples}
+}
+
+func (pc *pairCoverage) record(row []int, newID, newVal int) {
+	for _, item := range append(
+		rowToPairCombos(row, false, newID, newVal),
+		rowToPairCombos(row, true, newID, newVal)...) {
+		pc.cover[item] = struct{}{}
+	}
+}
+
+type pair struct {
+	pos   int
+	value int
+}
+
+type pairCombo struct {
+	first  pair
+	second pair
+	third  pair
+}
+
+func rowToPairCombos(row []int, triples bool, newID, newVal int) []pairCombo {
+	var ret []pairCombo
+	// All things being equal, we want to also favor more different values.
+	ret = append(ret, pairCombo{third: pair{newID + 1, newVal}})
+	for i := 0; i+1 < len(row); i++ {
+		if !triples {
+			ret = append(ret, pairCombo{
+				first: pair{i + 1, row[i]},
+				third: pair{newID + 1, newVal},
+			})
+			continue
+		}
+		for j := i + 1; j < len(row); j++ {
+			ret = append(ret, pairCombo{
+				first:  pair{i + 1, row[i]},
+				second: pair{j + 1, row[j]},
+				third:  pair{newID + 1, newVal},
+			})
+		}
+	}
+	return ret
+}
+
+func extendRow(row []int, newVal int) []int {
+	return append(append([]int{}, row...), newVal)
+}
diff --git a/tools/syz-imagegen/combinations_test.go b/tools/syz-imagegen/combinations_test.go
new file mode 100644
index 000000000..beefc4588
--- /dev/null
+++ b/tools/syz-imagegen/combinations_test.go
@@ -0,0 +1,57 @@
+// Copyright 2025 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package main
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestFullCombinations(t *testing.T) {
+	t.Run("empty", func(t *testing.T) {
+		assert.Len(t, CoveringArray([][]string{}, 0), 0)
+	})
+	t.Run("single", func(t *testing.T) {
+		assert.Equal(t, [][]string{
+			{"A", "B", "C"},
+		}, CoveringArray([][]string{
+			{"A"},
+			{"B"},
+			{"C"},
+		}, 0))
+	})
+	t.Run("binary", func(t *testing.T) {
+		assert.Equal(t, [][]string{
+			{"A", "B", "C"},
+			{"A", "B", "c"},
+			{"A", "b", "C"},
+			{"A", "b", "c"},
+			{"a", "B", "C"},
+			{"a", "B", "c"},
+			{"a", "b", "C"},
+			{"a", "b", "c"},
+		}, CoveringArray([][]string{
+			{"A", "a"},
+			{"B", "b"},
+			{"C", "c"},
+		}, 0))
+	})
+}
+
+func TestPairCombinations(t *testing.T) {
+	// Theoretically, there may be multiple correct answers.
+	// For now, let's keep the current algorithm's output so that if the code behavior changes unexpectedly,
+	// we'd notice.
+	assert.Equal(t, [][]string{
+		{"A", "B", "C"},
+		{"A", "b", "c"},
+		{"a", "B", "c"},
+		{"a", "b", "C"},
+	}, CoveringArray([][]string{
+		{"A", "a"},
+		{"B", "b"},
+		{"C", "c"},
+	}, 4))
+}
diff --git a/tools/syz-imagegen/imagegen.go b/tools/syz-imagegen/imagegen.go
index 0ef5f0901..98560fc86 100644
--- a/tools/syz-imagegen/imagegen.go
+++ b/tools/syz-imagegen/imagegen.go
@@ -25,6 +25,7 @@ import (
 	"os/exec"
 	"path/filepath"
 	"runtime"
+	"slices"
 	"strings"
 	"syscall"
 	"time"
@@ -53,6 +54,8 @@ type FileSystem struct {
 	MkfsFlags []string `json:"mkfs_flags"`
 	// Generate images for all possible permutations of these flag combinations.
 	MkfsFlagCombinations [][]string `json:"mkfs_flag_combinations"`
+	// Limit the resulting number of seeds (in case there are too many possible combinations).
+	MaxSeeds int `json:"max_seeds"`
 	// Custom mkfs invocation, if nil then mkfs.name is invoked in a standard way.
 	Mkfs func(img *Image) error
 }
@@ -758,10 +761,13 @@ func generateImages(target *prog.Target, flagFS string, list bool) ([]*Image, er
 		if flagFS != "" && !strings.Contains(","+flagFS+",", ","+fs.suffix()+",") {
 			continue
 		}
-		index := 0
-		enumerateFlags(target, &images, &index, fs, fs.MkfsFlags, 0)
+		newImages := enumerateFlags(target, fs)
+		images = append(images, newImages...)
 		if list {
-			fmt.Printf("%v [%v images]\n", fs.Name, index)
+			fmt.Printf("%v [%v images]\n", fs.Name, len(newImages))
+			for i, image := range newImages {
+				fmt.Printf("#%d: %q\n", i, image.flags)
+			}
 			continue
 		}
 		files, err := filepath.Glob(filepath.Join("sys", targets.Linux, "test", fs.filePrefix()+"_*"))
@@ -774,30 +780,32 @@ func generateImages(target *prog.Target, flagFS string, list bool) ([]*Image, er
 			}
 		}
 	}
+	for i, image := range images {
+		image.index = i
+	}
 	return images, nil
 }
 
-func enumerateFlags(target *prog.Target, images *[]*Image, index *int, fs FileSystem, flags []string, flagsIndex int) {
-	if flagsIndex == len(fs.MkfsFlagCombinations) {
-		*images = append(*images, &Image{
+func enumerateFlags(target *prog.Target, fs FileSystem) []*Image {
+	var images []*Image
+	for _, flags := range CoveringArray(fs.MkfsFlagCombinations, fs.MaxSeeds) {
+		imageFlags := slices.Clone(fs.MkfsFlags)
+		for _, rawFlag := range flags {
+			for _, f := range strings.Split(rawFlag, " ") {
+				if f == "" {
+					continue
+				}
+				imageFlags = append(imageFlags, f)
+			}
+		}
+		images = append(images, &Image{
 			target: target,
 			fs:     fs,
-			flags:  append([]string{}, flags...),
-			index:  *index,
+			flags:  imageFlags,
 			done:   make(chan error, 1),
 		})
-		*index++
-		return
-	}
-	for _, flag := range fs.MkfsFlagCombinations[flagsIndex] {
-		flags1 := flags
-		for _, f := range strings.Split(flag, " ") {
-			if f != "" {
-				flags1 = append(flags1, f)
-			}
-		}
-		enumerateFlags(target, images, index, fs, flags1, flagsIndex+1)
 	}
+	return images
 }
 
 func (img *Image) generate() error {