Erweiterung von Spark für verbesserte Leistung bei der Verarbeitung mehrerer Suchbegriffe
Während der Einführung unseres Intrusion Detection Programs in der Produktion bei CCCShaben wir festgestellt, dass viele der SigmaHQ-Regeln sehr umfangreiche Pay attention mit Suchmustern verwenden. Diese Pay attention werden verwendet, um zu testen, ob ein CommandLineeine bestimmte Zeichenfolge enthält oder CommandLinebeginnt mit oder endet mit einer bestimmten Teilzeichenfolge.
Wir waren besonders daran interessiert, die Regeln mit „enthält“-Bedingungen zu untersuchen, da wir vermuteten, dass die Auswertung dieser Bedingungen für Spark zeitaufwändig sein könnte. Hier ist ein Beispiel für eine typische Sigma-Regel:
detection:
selection_image:
- Picture|comprises:
- 'CVE-202'
- 'CVE202'
- Picture|endswith:
- 'poc.exe'
- 'artifact.exe'
- 'artifact64.exe'
- 'artifact_protected.exe'
- 'artifact32.exe'
- 'artifact32big.exe'
- 'obfuscated.exe'
- 'obfusc.exe'
- 'meterpreter'
selection_commandline:
CommandLine|comprises:
- 'inject.ps1'
- 'Invoke-CVE'
- 'pupy.ps1'
- 'payload.ps1'
- 'beacon.ps1'
- 'PowerView.ps1'
- 'bypass.ps1'
- 'obfuscated.ps1'
Die vollständige Regel zu verdächtigen Programmnamen finden Sie hier
https://github.com/SigmaHQ/sigma/blob/grasp/guidelines/home windows/process_creation/proc_creation_win_susp_progname.yml
Die Regel veranschaulicht die Verwendung von CommandLine|comprises und von Picture|endswith. Einige Sigma-Regeln haben Hunderte von Suchbegriffen unter einem <subject>|comprisesZustand.
Anwenden von Sigma-Regeln mit Spark SQL
Bei CCCSübersetzen wir Sigma-Regeln in ausführbare Spark-SQL-Anweisungen. Dazu haben wir den SQL Sigma-Compiler um ein benutzerdefiniertes Backend erweitert. Es übersetzt die obige Regel in eine Anweisung wie diese:
choose
map(
'Suspicious Program Names',
(
(
(
Imagepath LIKE '%cve-202%'
OR Imagepath LIKE '%cve202%'
)
OR (
Imagepath LIKE '%poc.exe'
OR Imagepath LIKE '%artifact.exe'
...
OR Imagepath LIKE '%obfusc.exe'
OR Imagepath LIKE '%meterpreter'
)
)
OR (
CommandLine LIKE '%inject.ps1%'
OR CommandLine LIKE '%invoke-cve%'
OR CommandLine LIKE '%pupy.ps1%'
...
OR CommandLine LIKE '%encode.ps1%'
OR CommandLine LIKE '%powercat.ps1%'
)
)
) as sigma_rules_map
Wir führen die obige Anweisung in einem Spark Structured Streaming-Job aus. In einem einzigen Durchlauf über die Ereignisse wertet Spark mehrere (Hunderte) Sigma-Regeln aus. Die sigma_rules_map Die Spalte enthält die Auswertungsergebnisse aller dieser Regeln. Mithilfe dieser Karte können wir feststellen, welche Regel ein Treffer ist und welche nicht.
Wie wir sehen, beinhalten die Regeln oft den Vergleich von Ereignisattributen, wie z. B. CommandLinezu mehreren Zeichenfolgenmustern.
Einige dieser Assessments sind exakte Übereinstimmungen, wie zum Beispiel CommandLine = ‘one thing’Andere verwenden startswithund werden wiedergegeben als Imagepath LIKE ‘%poc.exe’.
Equals, startswithUnd endswith werden sehr schnell ausgeführt, da diese Bedingungen alle an einer bestimmten Place im Attribut des Ereignisses verankert sind.
Allerdings können Assessments wie comprises werden wiedergegeben als CommandLine LIKE ‘%hound.ps1%’ Dazu muss Spark das gesamte Attribut scannen, um eine mögliche Startposition für den Buchstaben „h“ zu finden und dann zu prüfen, ob darauf der Buchstabe „o“, „u“ usw. folgt.
Intern verwendet Spark eine UTF8String Das Programm greift das erste Zeichen, durchsucht den Puffer und vergleicht, wenn es eine Übereinstimmung findet, die restlichen Bytes mit dem matchAt Funktion. Hier ist die Implementierung der UTF8String.comprises Funktion.
public boolean comprises(last UTF8String substring) {
if (substring.numBytes == 0) {
return true;
}byte first = substring.getByte(0);
for (int i = 0; i <= numBytes - substring.numBytes; i++) {
if (getByte(i) == first && matchAt(substring, i)) {
return true;
}
}
return false;
}
Der equals, startswithUnd endswith Bedingungen verwenden auch die matchAt Funktion, aber im Gegensatz zu comprises Diese Bedingungen wissen, wo der Vergleich beginnen muss, und werden daher sehr schnell ausgeführt.
Um unsere Annahme zu bestätigen, dass comprises Bedingung ist teuer in der Ausführung, wir haben ein schnelles und einfaches Experiment durchgeführt. Wir haben alle entfernt comprises Bedingungen für die Sigma-Regeln, um zu sehen, wie sich dies auf die Gesamtausführungszeit auswirken würde. Der Unterschied battle signifikant und ermutigte uns, die Idee der Implementierung einer benutzerdefinierten Spark Catalyst-Funktion zur Handhabung weiter zu verfolgen comprises Operationen mit einer großen Anzahl von Suchbegriffen.
Der Aho-Corasick-Algorithmus
Ein wenig Recherche führte uns zu der Aho-Corasick-Algorithmus was für diesen Anwendungsfall intestine geeignet schien. Der Aho-Corasick-Algorithmus erstellt einen Präfixbaum (einen Trie) und kann viele comprises Ausdrücke in einem einzigen Durchgang über den zu testenden Textual content.
So verwenden Sie die Aho-Corasick Java-Implementierung von Robert Bor, die hier auf GitHub verfügbar ist https://github.com/robert-bor/aho-corasick
// create the trie
val triBuilder = Trie.builder()
triBuilder.addKeyword("test1")
triBuilder.addKeyword("test2")
trie = triBuilder.construct()// apply the trie to some textual content
aTextColumn = "some textual content to scan for both test1 or test2"
discovered = trie.containsMatch(aTextColumn)
Entwerfen einer aho_corasick_in Spark-Funktion
Unsere Funktion benötigt zwei Dinge: die zu testende Spalte und die zu suchenden Suchmuster. Wir implementieren eine Funktion mit der folgenden Signatur:
boolean aho_corasick_in(string textual content, array<string> searches)
Wir haben unseren CCCS Sigma-Compiler modifiziert, um SQL-Anweisungen zu erzeugen, die den aho_corasick_inFunktion, anstatt mehrere ORed LIKE-Prädikate zu erzeugen. In der Ausgabe unten werden Sie die Verwendung der aho_corasick_in Funktion. Wir übergeben das zu testende Feld und ein Array von Zeichenfolgen, nach denen gesucht werden soll. Hier ist die Ausgabe unseres benutzerdefinierten Compilers, der mehrere comprises Bedingungen:
choose
map(
'Suspicious Program Names',
(
(
(
Imagepath LIKE '%cve-202%'
OR Imagepath LIKE '%cve202%'
)
OR (
Imagepath LIKE '%poc.exe'
OR Imagepath LIKE '%artifact.exe'
...
OR Imagepath LIKE '%meterpreter'
)
)
OR (
aho_corasick_in(
CommandLine,
ARRAY(
'inject.ps1',
'invoke-cve',
...
'hound.ps1',
'encode.ps1',
'powercat.ps1'
)
)
)
)
) as sigma_rules_map
Beachten Sie, wie die aho_corasick_in Funktion erhält zwei Argumente: das erste ist eine Spalte und das zweite ist ein String-Array. Lassen Sie uns nun die aho_corasick_inFunktion.
Implementierung der Katalysatorfunktion
Wir fanden nicht viel Dokumentation zur Implementierung von Catalyst-Funktionen, additionally verwendeten wir stattdessen den Quellcode vorhandener Funktionen als Referenz. Wir nahmen die regulärer Ausdruck(str, regulärer Ausdruck) Funktion als Beispiel, da sie ihr Regexp-Muster vorkompiliert und es dann bei der Verarbeitung von Zeilen verwendet. Dies ist vergleichbar mit dem Vorkompilieren eines Aho-Corasick-Tries und dessen anschließender Anwendung auf jede Zeile.
Unser benutzerdefinierter Katalysatorausdruck nimmt zwei Argumente an. Es ist additionally ein BinaryExpression welches zwei Felder hat, die Spark benannt hat left Und proper. Unser AhoCorasickIn Konstruktor weist den textual content Spaltenargument für left Feld und das searches String-Array in proper Feld.
Das andere, was wir während der Initialisierung von AhoCorasickIn tun, ist die Auswertung der cacheTrie Feld. Die Auswertung prüft, ob das searches argument ist ein faltbarer Ausdruck, additionally ein konstanter Ausdruck. Wenn ja, wird es ausgewertet und es wird erwartet, dass es sich um ein String-Array handelt, das zum Aufrufen verwendet wird createTrie(searches).
Der createTrie Funktion iteriert über die Suchvorgänge und fügt sie dem trieBuilder und erstellt schließlich einen Aho-Corasick-Trie.
case class AhoCorasickIn(textual content: Expression, searches: Expression)
extends BinaryExpression
with CodegenFallback
with ImplicitCastInputTypes
with NullIntolerant
with Predicate {override def prettyName: String = "aho_corasick_in"
// Assign textual content to left subject
override def left: Expression = textual content
// Assign searches to proper subject
override def proper: Expression = searches
override def inputTypes: Seq(DataType) = Seq(StringType, ArrayType(StringType))
// Cache foldable searches expression when AhoCorasickIn is constructed
personal lazy val cacheTrie: Trie = proper match {
case p: Expression if p.foldable => {
val searches = p.eval().asInstanceOf(ArrayData)
createTrie(searches)
}
case _ => null
}
protected def createTrie(searches: ArrayData): Trie = {
val triBuilder = Trie.builder()
searches.foreach(StringType, (i, s) => triBuilder.addKeyword(s.toString()))
triBuilder.construct()
}
protected def getTrie(searches: ArrayData) = if (cacheTrie == null) createTrie(searches) else cacheTrie
override protected def nullSafeEval(textual content: Any, searches: Any): Any = {
val trie = getTrie(searches.asInstanceOf(ArrayData))
trie.containsMatch(textual content.asInstanceOf(UTF8String).toString())
}
override protected def withNewChildrenInternal(
newLeft: Expression, newRight: Expression): AhoCorasickIn =
copy(textual content = newLeft, searches = newRight)
}
Der nullSafeEval Methode ist das Herzstück von AhoCorasickIn. Spark ruft die eval-Funktion für jede Zeile im Datensatz auf. In nullSafeEvalwir holen die cacheTrie und testen Sie damit die textual content Zeichenfolgenargument.
Bewertung der Leistung
Zum Vergleich der Leistung der aho_corasick_in Funktion haben wir ein kleines Benchmarking-Skript geschrieben. Wir haben die Leistung mehrerer Assessments verglichen. LIKE Operationen im Vergleich zu einer einzelnen aho_corasick_in Anruf.
choose
*
from (
choose
textual content like '%' || uuid() || '%' OR
textual content like '%' || uuid() || '%' OR
textual content like '%' || uuid() || '%' OR
...
as end result
from (
choose
uuid()||uuid()||uuid()... as textual content
from
vary(0, 1000000, 1, 32)
)
)
the place
end result = TRUE
Dasselbe Experiment mit aho_corasick_in:
choose
*
from (
choose
aho_corasick_in(textual content, array(uuid(), uuid(),...) as end result
from (
choose
uuid()||uuid()||uuid()... as textual content
from
vary(0, 1000000, 1, 32)
)
)
the place
end result = TRUE
Wir führten diese beiden Experimente (wie vs aho_corasick_in) mit einem textual content Spalte mit 200 Zeichen und variierte die Anzahl der Suchbegriffe. Hier ist ein logarithmisches Diagramm, das beide Abfragen vergleicht.
Dieses Diagramm zeigt, wie die Leistung nachlässt, wenn wir der Abfrage „LIKE“ weitere Suchbegriffe hinzufügen, während die Abfrage mit aho_corasick_in Funktion bleibt relativ konstant, wenn die Anzahl der Suchbegriffe zunimmt. Bei 100 Suchbegriffen ist die aho_corasick_in Die Funktion wird fünfmal schneller ausgeführt als mehrere LIKE-Anweisungen.
Wir haben festgestellt, dass die Verwendung von Aho-Corasick erst nach mehr als 20 Suchvorgängen von Vorteil ist. Dies lässt sich durch die anfänglichen Kosten für die Erstellung des Tries erklären. Mit zunehmender Anzahl der Suchbegriffe zahlen sich diese Vorabkosten jedoch aus. Dies steht im Gegensatz zu den LIKE-Ausdrücken, bei denen die Abfrage umso teurer wird, je mehr LIKE-Ausdrücke wir hinzufügen.
Als nächstes setzten wir die Anzahl der Suchbegriffe auf 20 und variierten die Länge der textual content Zeichenfolge. Wir haben festgestellt, dass sowohl LIKE als auch aho_corasick_in Funktion dauert bei verschiedenen Stringlängen etwa gleich lange. In beiden Experimenten ist die Ausführungszeit abhängig von der Länge des textual content Zeichenfolge.
Es ist wichtig zu beachten, dass die Kosten für die Erstellung des Tries von der Anzahl der Spark-Aufgaben im Abfrageausführungsplan abhängen. Spark instanziiert Ausdrücke (d. h. instanziiert neue AhoCorasickIn-Objekte) für jede Aufgabe im Ausführungsplan. Mit anderen Worten: Wenn Ihre Abfrage 200 Aufgaben verwendet, wird der AhoCorasickIn-Konstruktor 200 Mal aufgerufen.
Zusammenfassend lässt sich sagen, dass die zu verwendende Strategie von der Anzahl der Begriffe abhängt. Wir haben diese Optimierung in unseren Sigma-Compiler eingebaut. Unter einem bestimmten Schwellenwert (sagen wir 20 Begriffe) werden LIKE-Anweisungen ausgegeben, und über diesem Schwellenwert wird eine Abfrage ausgegeben, die die aho_corasick_in Funktion.
Dieser Schwellenwert hängt natürlich von Ihren tatsächlichen Daten und der Anzahl der Aufgaben in Ihrem Spark-Ausführungsplan ab.
Unsere ersten Ergebnisse, die wir mit Produktionsdaten und echten SigmaHQ-Regeln durchgeführt haben, zeigen, dass die Anwendung der aho_corasick_in Funktion erhöht unsere Verarbeitungsrate (Ereignisse professional Sekunde) um den Faktor 1,4.
Abschluss
In diesem Artikel haben wir gezeigt, wie man eine native Spark-Funktion implementiert. Dieser Catalyst-Ausdruck nutzt den Aho-Corasick-Algorithmus, der viele Suchbegriffe gleichzeitig testen kann. Wie bei jedem Ansatz gibt es jedoch auch hier Kompromisse. Die Verwendung von Aho-Corasick erfordert den Aufbau eines Tries (Präfixbaum), was die Leistung beeinträchtigen kann, wenn nur wenige Suchbegriffe verwendet werden. Unser Compiler verwendet einen Schwellenwert (Anzahl der Suchbegriffe), um die optimale Strategie auszuwählen und so die effizienteste Abfrageausführung sicherzustellen.