<commit_before>// Copyright 2015 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 prog

import (
	"fmt"
	"math/rand"
	"sort"
	"sync"

	"github.com/google/syzkaller/sys"
)

// Calulation of call-to-call priorities.
// For a given pair of calls X and Y, the priority is our guess as to whether
// additional of call Y into a program containing call X is likely to give
// new coverage or not.
// The current algorithm has two components: static and dynamic.
// The static component is based on analysis of argument types. For example,
// if call X and call Y both accept fd[sock], then they are more likely to give
// new coverage together.
// The dynamic component is based on frequency of occurrence of a particular
// pair of syscalls in a single program in corpus. For example, if socket and
// connect frequently occur in programs together, we give higher priority to
// this pair of syscalls.
// Note: the current implementation is very basic, there is no theory behind any
// constants.

func CalculatePriorities(corpus []*Prog) [][]float32 {
	static := getStaticPrio()
	dynamic := calcDynamicPrio(corpus)
	for i, prios := range static {
		for j, p := range prios {
			dynamic[i][j] *= p
		}
	}
	return dynamic
}

var (
	staticOnce sync.Once
	staticPrio [][]float32
)

func getStaticPrio() [][]float32 {
	staticOnce.Do(func() {
		staticPrio = calcStaticPriorities()
	})
	return staticPrio
}

func calcStaticPriorities() [][]float32 {
	uses := make(map[string]map[int]float32)
	for _, c := range sys.Calls {
		noteUsage := func(weight float32, str string, args ...interface{}) {
			id := fmt.Sprintf(str, args...)
			if uses[id] == nil {
				uses[id] = make(map[int]float32)
			}
			old := uses[id][c.ID]
			if weight > old {
				uses[id][c.ID] = weight
			}
		}
		foreachArgType(c, func(t sys.Type, d ArgDir) {
			switch a := t.(type) {
			case sys.ResourceType:
				if a.Kind == sys.ResPid || a.Kind == sys.ResUid || a.Kind == sys.ResGid {
					// Pid/uid/gid usually play auxiliary role,
					// but massively happen in some structs.
					noteUsage(0.1, "res%v", a.Kind)
				} else if a.Subkind == sys.ResAny {
					noteUsage(1.0, "res%v", a.Kind)
				} else {
					noteUsage(0.2, "res%v", a.Kind)
					noteUsage(1.0, "res%v-%v", a.Kind, a.Subkind)
				}
			case sys.PtrType:
				if _, ok := a.Type.(sys.StructType); ok {
					noteUsage(1.0, "ptrto-%v", a.Type.Name())<commit_msg>prog: don't cache static priorities<commit_after>// Copyright 2015 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 prog

import (
	"fmt"
	"math/rand"
	"sort"

	"github.com/google/syzkaller/sys"
)

// Calulation of call-to-call priorities.
// For a given pair of calls X and Y, the priority is our guess as to whether
// additional of call Y into a program containing call X is likely to give
// new coverage or not.
// The current algorithm has two components: static and dynamic.
// The static component is based on analysis of argument types. For example,
// if call X and call Y both accept fd[sock], then they are more likely to give
// new coverage together.
// The dynamic component is based on frequency of occurrence of a particular
// pair of syscalls in a single program in corpus. For example, if socket and
// connect frequently occur in programs together, we give higher priority to
// this pair of syscalls.
// Note: the current implementation is very basic, there is no theory behind any
// constants.

func CalculatePriorities(corpus []*Prog) [][]float32 {
	static := calcStaticPriorities()
	dynamic := calcDynamicPrio(corpus)
	for i, prios := range static {
		for j, p := range prios {
			dynamic[i][j] *= p
		}
	}
	return dynamic
}

func calcStaticPriorities() [][]float32 {
	uses := make(map[string]map[int]float32)
	for _, c := range sys.Calls {
		noteUsage := func(weight float32, str string, args ...interface{}) {
			id := fmt.Sprintf(str, args...)
			if uses[id] == nil {
				uses[id] = make(map[int]float32)
			}
			old := uses[id][c.ID]
			if weight > old {
				uses[id][c.ID] = weight
			}
		}
		foreachArgType(c, func(t sys.Type, d ArgDir) {
			switch a := t.(type) {
			case sys.ResourceType:
				if a.Kind == sys.ResPid || a.Kind == sys.ResUid || a.Kind == sys.ResGid {
					// Pid/uid/gid usually play auxiliary role,
					// but massively happen in some structs.
					noteUsage(0.1, "res%v", a.Kind)
				} else if a.Subkind == sys.ResAny {
					noteUsage(1.0, "res%v", a.Kind)
				} else {
					noteUsage(0.2, "res%v", a.Kind)
					noteUsage(1.0, "res%v-%v", a.Kind, a.Subkind)
				}
			case sys.PtrType:
				if _, ok := a.Type.(sys.StructType); ok {
					noteUsage(1.0, "ptrto-%v", a.Type.Name())
{'fraction_non_alphanumeric': 0.12735556015738247, 'fraction_numerical': 0.011182439428453097, 'mean_word_length': 3.1854419410745236, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4840218', 'n_tokens_mistral': 1758, 'n_tokens_neox': 1562, 'n_words': 571}