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 {