Repository: ossf/package-analysis (go)

Issue:
Replace identifier length statistics with length counts in obfuscation detection
Rather than summarising length statistics, providing raw counts of the lengths of all identifiers in a file would be able to identify cases of obfuscation where identifiers are randomly generated strings all with the same length

Pull request:
Change string and identifier length statistics into proper count data in obfuscation.Signals
Fixes #517 

Signed-off-by: Max Fisher <maxfisher@google.com>

Patch:
diff --git a/internal/staticanalysis/obfuscation/compute_signals.go b/internal/staticanalysis/obfuscation/compute_signals.go
index d0fc540..5c5e1ed 100644
--- a/internal/staticanalysis/obfuscation/compute_signals.go
+++ b/internal/staticanalysis/obfuscation/compute_signals.go
@@ -15,7 +15,7 @@ import (
 // - Stats summary of symbol (string) entropies
 // - Entropy of all symbols concatenated together
 func characterAnalysis(symbols []string) (
-	lengthSummary stats.SampleStatistics,
+	lengthCounts map[int]int,
 	entropySummary stats.SampleStatistics,
 	combinedEntropy float64,
 ) {
@@ -29,7 +29,7 @@ func characterAnalysis(symbols []string) (
 		lengths = append(lengths, len(s))
 	}
 
-	lengthSummary = stats.Summarise(lengths)
+	lengthCounts = stats.CountDistinct(lengths)
 	entropySummary = stats.Summarise(entropies)
 	combinedEntropy = stringentropy.CalculateEntropy(strings.Join(symbols, ""), nil)
 	return
@@ -50,11 +50,11 @@ func ComputeSignals(rawData RawData) Signals {
 	signals := Signals{}
 
 	literals := utils.Transform(rawData.StringLiterals, func(s token.String) string { return s.Value })
-	signals.StringLengthSummary, signals.StringEntropySummary, signals.CombinedStringEntropy =
+	signals.StringLengths, signals.StringEntropySummary, signals.CombinedStringEntropy =
 		characterAnalysis(literals)
 
 	identifierNames := utils.Transform(rawData.Identifiers, func(i token.Identifier) string { return i.Name })
-	signals.IdentifierLengthSummary, signals.IdentifierEntropySummary, signals.CombinedIdentifierEntropy =
+	signals.IdentifierLengths, signals.IdentifierEntropySummary, signals.CombinedIdentifierEntropy =
 		characterAnalysis(identifierNames)
 
 	return signals
@@ -62,10 +62,10 @@ func ComputeSignals(rawData RawData) Signals {
 
 func NoSignals() Signals {
 	return Signals{
-		StringLengthSummary:       stats.NoData(),
+		StringLengths:             map[int]int{},
 		StringEntropySummary:      stats.NoData(),
 		CombinedStringEntropy:     math.NaN(),
-		IdentifierLengthSummary:   stats.NoData(),
+		IdentifierLengths:         map[int]int{},
 		IdentifierEntropySummary:  stats.NoData(),
 		CombinedIdentifierEntropy: math.NaN(),
 	}
@@ -74,10 +74,10 @@ func NoSignals() Signals {
 // RemoveNaNs replaces all NaN values in this object with zeros
 func RemoveNaNs(s Signals) Signals {
 	replaced := Signals{
-		StringLengthSummary:       s.StringLengthSummary.ReplaceNaNs(0),
+		StringLengths:             s.StringLengths,
 		StringEntropySummary:      s.StringEntropySummary.ReplaceNaNs(0),
 		CombinedStringEntropy:     s.CombinedStringEntropy,
-		IdentifierLengthSummary:   s.IdentifierLengthSummary.ReplaceNaNs(0),
+		IdentifierLengths:         s.IdentifierLengths,
 		IdentifierEntropySummary:  s.IdentifierEntropySummary.ReplaceNaNs(0),
 		CombinedIdentifierEntropy: s.CombinedIdentifierEntropy,
 	}
diff --git a/internal/staticanalysis/obfuscation/data.go b/internal/staticanalysis/obfuscation/data.go
index 69c7b94..bb64c14 100644
--- a/internal/staticanalysis/obfuscation/data.go
+++ b/internal/staticanalysis/obfuscation/data.go
@@ -17,12 +17,37 @@ type RawData struct { // TODO rename to FileData
 	Comments       []token.Comment
 }
 
-type Signals struct {
-	StringLengthSummary       stats.SampleStatistics
-	StringEntropySummary      stats.SampleStatistics
-	CombinedStringEntropy     float64
-	IdentifierLengthSummary   stats.SampleStatistics
-	IdentifierEntropySummary  stats.SampleStatistics
+type Signals struct { // TODO rename to FileSignals
+	// StringLengths is a map from length (in characters) to number of
+	// string literals in the file having that length. If a length key is
+	// missing, it is assumed to be zero.
+	StringLengths map[int]int
+
+	// StringEntropySummary provides sample statistics for the set of entropy
+	// values calculated on each string literal. Character probabilities for the
+	// entropy calculation are estimated empirically from aggregated counts
+	// of characters across all string literals in the file.
+	StringEntropySummary stats.SampleStatistics
+
+	// CombinedStringEntropy is the entropy of the string obtained from
+	// concatenating all string literals in the file together. It may be used
+	// to normalise the values in StringEntropySummary
+	CombinedStringEntropy float64
+
+	// IdentifierLengths is a map from length (in characters) to number of
+	// identifiers in the file having that length. If a length key is missing,
+	// it is assumed to be zero.
+	IdentifierLengths map[int]int
+
+	// IdentifierEntropySummary provides sample statistics for the set of entropy
+	// values calculated on each identifier. Character probabilities for the
+	// entropy calculation are estimated empirically from aggregated counts
+	// of characters across all identifiers in the file.
+	IdentifierEntropySummary stats.SampleStatistics
+
+	// CombinedIdentifierEntropy is the entropy of the string obtained from
+	// concatenating all identifiers in the file together. It may be used to
+	// normalise the values in IdentifierEntropySummary
 	CombinedIdentifierEntropy float64
 }
 
@@ -61,11 +86,11 @@ func (rd RawData) String() string {
 
 func (s Signals) String() string {
 	parts := []string{
-		fmt.Sprintf("string length: %s", s.StringLengthSummary),
+		fmt.Sprintf("string lengths: %v", s.StringLengths),
 		fmt.Sprintf("string entropy: %s", s.StringEntropySummary),
 		fmt.Sprintf("combined string entropy: %f", s.CombinedStringEntropy),
 
-		fmt.Sprintf("identifier length: %s", s.IdentifierLengthSummary),
+		fmt.Sprintf("identifier lengths: %v", s.IdentifierLengths),
 		fmt.Sprintf("identifier entropy: %s", s.IdentifierEntropySummary),
 		fmt.Sprintf("combined identifier entropy: %f", s.CombinedIdentifierEntropy),
 	}
diff --git a/internal/staticanalysis/obfuscation/stats/sample_statistics.go b/internal/staticanalysis/obfuscation/stats/sample_statistics.go
index 9c1e74a..7ad0718 100644
--- a/internal/staticanalysis/obfuscation/stats/sample_statistics.go
+++ b/internal/staticanalysis/obfuscation/stats/sample_statistics.go
@@ -207,3 +207,11 @@ func Summarise[T RealNumber](sample []T) SampleStatistics {
 	q := quartiles(sample)
 	return SampleStatistics{Size: l, Mean: m, Variance: v, Skewness: s, Quartiles: q}
 }
+
+func CountDistinct[T constraints.Integer](sample []T) map[T]int {
+	counts := make(map[T]int, 0)
+	for _, t := range sample {
+		counts[t] += 1
+	}
+	return counts
+}


Test patch:
diff --git a/internal/staticanalysis/obfuscation/compute_signals_test.go b/internal/staticanalysis/obfuscation/compute_signals_test.go
index 0426705..6f9e6e1 100644
--- a/internal/staticanalysis/obfuscation/compute_signals_test.go
+++ b/internal/staticanalysis/obfuscation/compute_signals_test.go
@@ -1,6 +1,7 @@
 package obfuscation
 
 import (
+	"reflect"
 	"strings"
 	"testing"
 
@@ -18,10 +19,9 @@ func symbolEntropySummary(symbols []string) stats.SampleStatistics {
 	return stats.Summarise(entropies)
 }
 
-func symbolLengthSummary(symbols []string) stats.SampleStatistics {
+func symbolLengthCounts(symbols []string) map[int]int {
 	lengths := utils.Transform(symbols, func(s string) int { return len(s) })
-	return stats.Summarise(lengths)
-
+	return stats.CountDistinct(lengths)
 }
 
 func compareSummary(t *testing.T, name string, expected, actual stats.SampleStatistics) {
@@ -30,18 +30,24 @@ func compareSummary(t *testing.T, name string, expected, actual stats.SampleStat
 	}
 }
 
+func compareCounts(t *testing.T, name string, expected, actual map[int]int) {
+	if !reflect.DeepEqual(expected, actual) {
+		t.Errorf("%s summary did not match.\nExpected: %v\nActual: %v\n", name, expected, actual)
+	}
+}
+
 func testSignals(t *testing.T, signals Signals, stringLiterals []token.String, identifiers []token.Identifier) {
 	literals := utils.Transform(stringLiterals, func(s token.String) string { return s.Value })
 	identifierNames := utils.Transform(identifiers, func(i token.Identifier) string { return i.Name })
 	expectedStringEntropySummary := symbolEntropySummary(literals)
-	expectedStringLengthSummary := symbolLengthSummary(literals)
+	expectedStringLengthSummary := symbolLengthCounts(literals)
 	expectedIdentifierEntropySummary := symbolEntropySummary(identifierNames)
-	expectedIdentifierLengthSummary := symbolLengthSummary(identifierNames)
+	expectedIdentifierLengthSummary := symbolLengthCounts(identifierNames)
 
 	compareSummary(t, "String literal entropy", expectedStringEntropySummary, signals.StringEntropySummary)
-	compareSummary(t, "String literal lengths", expectedStringLengthSummary, signals.StringLengthSummary)
+	compareCounts(t, "String literal lengths", expectedStringLengthSummary, signals.StringLengths)
 	compareSummary(t, "Identifier entropy", expectedIdentifierEntropySummary, signals.IdentifierEntropySummary)
-	compareSummary(t, "Identifier lengths", expectedIdentifierLengthSummary, signals.IdentifierLengthSummary)
+	compareCounts(t, "Identifier lengths", expectedIdentifierLengthSummary, signals.IdentifierLengths)
 
 	expectedStringCombinedEntropy := stringentropy.CalculateEntropy(strings.Join(literals, ""), nil)
 	if !utils.FloatEquals(expectedStringCombinedEntropy, signals.CombinedStringEntropy, 1e-4) {
diff --git a/internal/staticanalysis/obfuscation/stats/sample_statistics_test.go b/internal/staticanalysis/obfuscation/stats/sample_statistics_test.go
index 152edc6..20f267b 100644
--- a/internal/staticanalysis/obfuscation/stats/sample_statistics_test.go
+++ b/internal/staticanalysis/obfuscation/stats/sample_statistics_test.go
@@ -2,6 +2,7 @@ package stats
 
 import (
 	"math"
+	"reflect"
 	"testing"
 )
 
@@ -113,3 +114,30 @@ func TestSummary7(t *testing.T) {
 		t.Errorf("Expected summary: %v\nactual summary %v\n", expected, actual)
 	}
 }
+
+func TestCountDistinct1(t *testing.T) {
+	data := []int{1, 2, 3, 4, 3, 2, 1, 2}
+	actual := CountDistinct(data)
+	expected := map[int]int{1: 2, 2: 3, 3: 2, 4: 1}
+	if !reflect.DeepEqual(actual, expected) {
+		t.Errorf("Expected counts: %v\nactual counts %v\n", expected, actual)
+	}
+}
+
+func TestCountDistinct2(t *testing.T) {
+	data := []int{1}
+	actual := CountDistinct(data)
+	expected := map[int]int{1: 1}
+	if !reflect.DeepEqual(actual, expected) {
+		t.Errorf("Expected counts: %v\nactual counts %v\n", expected, actual)
+	}
+}
+
+func TestCountDistinct3(t *testing.T) {
+	data := []int{}
+	actual := CountDistinct(data)
+	expected := map[int]int{}
+	if !reflect.DeepEqual(actual, expected) {
+		t.Errorf("Expected counts: %v\nactual counts %v\n", expected, actual)
+	}
+}