pkg/subsystem: extract subsystems from a crash list

For now, let's use a straightforward approach:
1) Extract all subsystems for each guilty path and syz reproducer.
2) If there are both parents and children in the list, remove parents.
3) Count the remaining subsystems.
4) Pick the ones that appear most often.

4 files changed, 218 insertions, 16 deletions

diff --git a/pkg/subsystem/entity/entities.go b/pkg/subsystem/entity/entities.go
index bca218ebe..9d1d8e5a5 100644
--- a/pkg/subsystem/entity/entities.go
+++ b/pkg/subsystem/entity/entities.go
@@ -12,6 +12,23 @@ type Subsystem struct {
 	Parents     []*Subsystem
 }
 
+// ReachableParents returns the set of subsystems reachable from the current one.
+func (subsystem *Subsystem) ReachableParents() map[*Subsystem]struct{} {
+	ret := make(map[*Subsystem]struct{})
+	var dfs func(node *Subsystem)
+	dfs = func(node *Subsystem) {
+		if _, visited := ret[node]; visited {
+			return
+		}
+		for _, p := range node.Parents {
+			ret[p] = struct{}{}
+			dfs(p)
+		}
+	}
+	dfs(subsystem)
+	return ret
+}
+
 // PathRule describes the part of the directory tree belonging to a single subsystem.
 type PathRule struct {
 	IncludeRegexp string
diff --git a/pkg/subsystem/extractor.go b/pkg/subsystem/extractor.go
new file mode 100644
index 000000000..e54086b29
--- /dev/null
+++ b/pkg/subsystem/extractor.go
@@ -0,0 +1,74 @@
+// Copyright 2023 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 subsystem
+
+import (
+	"github.com/google/syzkaller/pkg/subsystem/entity"
+)
+
+// Extractor deduces the subsystems from the list of crashes.
+type Extractor struct {
+	raw rawExtractorInterface
+}
+
+// Crash represents the subset of the available crash information that's required for
+// subsystem inference.
+type Crash struct {
+	GuiltyPath string
+	SyzRepro   []byte
+}
+
+// rawExtractorInterface simplifies testing.
+type rawExtractorInterface interface {
+	FromPath(path string) []*entity.Subsystem
+	FromProg(progBytes []byte) []*entity.Subsystem
+}
+
+func MakeExtractor(list []*entity.Subsystem) *Extractor {
+	return &Extractor{raw: makeRawExtractor(list)}
+}
+
+func (e *Extractor) Extract(crashes []*Crash) []*entity.Subsystem {
+	// First put all subsystems to the same list.
+	subsystems := []*entity.Subsystem{}
+	for _, crash := range crashes {
+		if crash.GuiltyPath != "" {
+			subsystems = append(subsystems, e.raw.FromPath(crash.GuiltyPath)...)
+		}
+		if len(crash.SyzRepro) > 0 {
+			subsystems = append(subsystems, e.raw.FromProg(crash.SyzRepro)...)
+		}
+	}
+
+	// If there are both parents and children, remove parents.
+	ignore := make(map[*entity.Subsystem]struct{})
+	for _, entry := range subsystems {
+		for p := range entry.ReachableParents() {
+			ignore[p] = struct{}{}
+		}
+	}
+
+	// And calculate counts.
+	counts := make(map[*entity.Subsystem]int)
+	maxCount := 0
+	for _, entry := range subsystems {
+		if _, ok := ignore[entry]; ok {
+			continue
+		}
+		counts[entry]++
+		if counts[entry] > maxCount {
+			maxCount = counts[entry]
+		}
+	}
+
+	// Pick the most prevalent ones.
+	ret := []*entity.Subsystem{}
+	for entry, count := range counts {
+		if count < maxCount {
+			continue
+		}
+		ret = append(ret, entry)
+	}
+	return ret
+}
diff --git a/pkg/subsystem/extractor_test.go b/pkg/subsystem/extractor_test.go
new file mode 100644
index 000000000..5dedd0b1a
--- /dev/null
+++ b/pkg/subsystem/extractor_test.go
@@ -0,0 +1,126 @@
+// Copyright 2023 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 subsystem
+
+import (
+	"reflect"
+	"testing"
+
+	"github.com/google/syzkaller/pkg/subsystem/entity"
+	"github.com/stretchr/testify/assert"
+)
+
+func TestExtractor(t *testing.T) {
+	// Objects used in tests.
+	fsPath := "fs/"
+	extProg, nfsProg := []byte("ext prog"), []byte("nfs prog")
+	fs := &entity.Subsystem{Name: "fs"}
+	ext := &entity.Subsystem{Name: "ext", Parents: []*entity.Subsystem{fs}}
+	nfs := &entity.Subsystem{Name: "nfs", Parents: []*entity.Subsystem{fs}}
+	// Tests themselves.
+	tests := []struct {
+		name    string
+		crashes []*Crash
+		want    []*entity.Subsystem
+	}{
+		{
+			name: `Make sure it works fine with just a single path`,
+			crashes: []*Crash{
+				{
+					GuiltyPath: fsPath,
+				},
+			},
+			want: []*entity.Subsystem{fs},
+		},
+		{
+			name: `Make sure a child shadows its parent`,
+			crashes: []*Crash{
+				{
+					GuiltyPath: fsPath,
+				},
+				{
+					GuiltyPath: fsPath,
+					SyzRepro:   extProg,
+				},
+			},
+			want: []*entity.Subsystem{ext},
+		},
+		{
+			name: `Two equally present children`,
+			crashes: []*Crash{
+				{
+					GuiltyPath: fsPath,
+				},
+				{
+					GuiltyPath: fsPath,
+					SyzRepro:   extProg,
+				},
+				{
+					GuiltyPath: fsPath,
+					SyzRepro:   nfsProg,
+				},
+			},
+			want: []*entity.Subsystem{nfs, ext},
+		},
+		{
+			name: `One child is more present than another`,
+			crashes: []*Crash{
+				{
+					GuiltyPath: fsPath,
+				},
+				{
+					GuiltyPath: fsPath,
+					SyzRepro:   extProg,
+				},
+				{
+					GuiltyPath: fsPath,
+					SyzRepro:   nfsProg,
+				},
+				{
+					GuiltyPath: fsPath,
+					SyzRepro:   extProg,
+				},
+			},
+			want: []*entity.Subsystem{ext},
+		},
+	}
+	extractor := &Extractor{
+		raw: &testRawExtractor{
+			perPath: map[string][]*entity.Subsystem{
+				fsPath: {fs},
+			},
+			perProg: []progSubsystems{
+				{extProg, []*entity.Subsystem{ext}},
+				{nfsProg, []*entity.Subsystem{nfs}},
+			},
+		},
+	}
+	for _, test := range tests {
+		ret := extractor.Extract(test.crashes)
+		assert.ElementsMatch(t, ret, test.want, test.name)
+	}
+}
+
+type testRawExtractor struct {
+	perPath map[string][]*entity.Subsystem
+	perProg []progSubsystems
+}
+
+type progSubsystems struct {
+	prog []byte
+	ret  []*entity.Subsystem
+}
+
+func (e *testRawExtractor) FromPath(path string) []*entity.Subsystem {
+	return e.perPath[path]
+}
+
+func (e *testRawExtractor) FromProg(progBytes []byte) []*entity.Subsystem {
+	for _, obj := range e.perProg {
+		if reflect.DeepEqual(progBytes, obj.prog) {
+			return obj.ret
+		}
+	}
+	return nil
+}
diff --git a/pkg/subsystem/linux/parents.go b/pkg/subsystem/linux/parents.go
index 40ba10b7f..5c66782c1 100644
--- a/pkg/subsystem/linux/parents.go
+++ b/pkg/subsystem/linux/parents.go
@@ -35,8 +35,7 @@ func transitiveReduction(list []*entity.Subsystem) {
 	for _, s := range list {
 		removeParents := map[*entity.Subsystem]bool{}
 		for _, p := range s.Parents {
-			reachable := reachableParents(p)
-			for otherP := range reachable {
+			for otherP := range p.ReachableParents() {
 				removeParents[otherP] = true
 			}
 		}
@@ -50,20 +49,6 @@ func transitiveReduction(list []*entity.Subsystem) {
 	}
 }
 
-// reachableParents lists all entity.Subsystem entries reachable from the given one.
-func reachableParents(start *entity.Subsystem) map[*entity.Subsystem]bool {
-	ret := make(map[*entity.Subsystem]bool)
-	var dfs func(node *entity.Subsystem)
-	dfs = func(node *entity.Subsystem) {
-		for _, p := range node.Parents {
-			ret[p] = true
-			dfs(p)
-		}
-	}
-	dfs(start)
-	return ret
-}
-
 // loopsExist is a helper method that verifies that the resulting graph has no loops.
 func loopsExist(list []*entity.Subsystem) bool {
 	type graphNode struct {