Estendere Spark per migliorare le prestazioni nella gestione di più termini di ricerca
Durante il processo di implementazione del nostro sistema di rilevamento delle intrusioni nella produzione presso CCCSabbiamo osservato che molte delle regole SigmaHQ utilizzano elenchi di modelli di ricerca molto considerevoli. Questi elenchi vengono utilizzati per verificare se a CommandLinecontiene una determinata stringa o se il file CommandLineinizia o termina con una determinata sottostringa.
Eravamo particolarmente interessati a indagare sulle regole che coinvolgono le condizioni “contiene”, poiché sospettavamo che la valutazione di queste condizioni potesse richiedere molto tempo a Spark. Ecco un esempio di una tipica regola Sigma:
detection:
selection_image:
- Image|contains:
- '\CVE-202'
- '\CVE202'
- Image|endswith:
- '\poc.exe'
- '\artifact.exe'
- '\artifact64.exe'
- '\artifact_protected.exe'
- '\artifact32.exe'
- '\artifact32big.exe'
- 'obfuscated.exe'
- 'obfusc.exe'
- '\meterpreter'
selection_commandline:
CommandLine|contains:
- 'inject.ps1'
- 'Invoke-CVE'
- 'pupy.ps1'
- 'payload.ps1'
- 'beacon.ps1'
- 'PowerView.ps1'
- 'bypass.ps1'
- 'obfuscated.ps1'
La regola completa sui nomi di programmi sospetti può essere trovata qui
https://github.com/SigmaHQ/sigma/blob/master/rules/windows/process_creation/proc_creation_win_susp_progname.yml
La regola illustra l'uso di CommandLine|contains e di Image|endswith. Alcune regole Sigma hanno centinaia di termini di ricerca sotto a <field>|containscondizione.
Applicazione delle regole Sigma con Spark SQL
A CCCStraduciamo le regole Sigma in istruzioni Spark SQL eseguibili. Per fare ciò abbiamo esteso il compilatore SQL Sigma con un backend personalizzato. Traduce la regola di cui sopra in una dichiarazione come questa:
select
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
Eseguiamo l'istruzione precedente in un processo di streaming strutturato Spark. In un singolo passaggio sugli eventi Spark valuta più (centinaia) di regole Sigma. IL sigma_rules_map La colonna contiene i risultati della valutazione di tutte queste regole. Usando questa mappa possiamo determinare quale regola è valida e quale no.
Come possiamo vedere, le regole spesso implicano il confronto degli attributi dell'evento, come ad esempio CommandLinea più schemi di corde.
Alcuni di questi test corrispondono a corrispondenze esatte, ad esempio CommandLine = ‘something’. Altri usano startswithe sono resi come Imagepath LIKE ‘%\\poc.exe’.
Equals, startswithE endswith vengono eseguiti molto rapidamente poiché queste condizioni sono tutte ancorate in una posizione particolare nell'attributo dell'evento.
Tuttavia, test come contains sono resi come CommandLine LIKE ‘%hound.ps1%’ che richiede a Spark di scansionare l'intero attributo per trovare una possibile posizione iniziale per la lettera “h” e quindi controllare se è seguita dalla lettera “o”, “u” ecc.
Internamente, Spark utilizza a UTF8String che prende il primo carattere, esegue la scansione del buffer e, se trova una corrispondenza, continua a confrontare i byte rimanenti utilizzando il comando matchAt funzione. Ecco l'implementazione del UTF8String.contains funzione.
public boolean contains(final 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;
}
IL equals, startswithE endswith condizioni utilizzano anche il file matchAt funzione ma contrariamente a contains queste condizioni sanno da dove iniziare il confronto e quindi vengono eseguite molto rapidamente.
Per convalidare la nostra ipotesi che contains condizione è costosa da eseguire, abbiamo condotto un esperimento semplice e veloce. Abbiamo rimosso tutto il contains condizioni per le regole Sigma per vedere come influirebbero sul tempo di esecuzione complessivo. La differenza è stata significativa e ci ha incoraggiato a perseguire l'idea di implementare una funzione Spark Catalyst personalizzata da gestire contains operazioni che coinvolgono un gran numero di termini di ricerca.
L'algoritmo Aho-Corasick
Un po' di ricerca ci ha portato al Algoritmo di Aho-Corasick che sembrava essere adatto a questo caso d'uso. L'algoritmo Aho-Corasick costruisce un albero di prefissi (un trie) e può valutarne molti contains espressioni in un unico passaggio sul testo da testare.
Ecco come utilizzare l'implementazione Java Aho-Corasick di Robert Bor disponibile su github qui https://github.com/robert-bor/aho-corasick
// create the trie
val triBuilder = Trie.builder()
triBuilder.addKeyword("test1")
triBuilder.addKeyword("test2")
trie = triBuilder.build()// apply the trie to some text
aTextColumn = "some text to scan for either test1 or test2"
found = trie.containsMatch(aTextColumn)
Progettare a aho_corasick_in Funzione scintilla
La nostra funzione avrà bisogno di due cose: la colonna da testare e i modelli di ricerca da cercare. Implementeremo una funzione con la seguente firma:
boolean aho_corasick_in(string text, array<string> searches)
Abbiamo modificato il nostro compilatore CCCS Sigma per produrre istruzioni SQL che utilizzano il file aho_corasick_infunzione anziché produrre più predicati ORed LIKE. Nell'output seguente noterai l'uso di aho_corasick_in funzione. Passiamo nel campo da testare e in un array di stringhe da cercare. Ecco l'output del nostro compilatore personalizzato che gestisce multipli contains condizioni:
select
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
Notare come aho_corasick_in la funzione riceve due argomenti: il primo è una colonna e il secondo è una matrice di stringhe. Ora implementiamo effettivamente il file aho_corasick_infunzione.
Implementazione della funzione catalizzatore
Non abbiamo trovato molta documentazione su come implementare le funzioni Catalyst, quindi abbiamo utilizzato come riferimento il codice sorgente delle funzioni esistenti. Abbiamo preso il espressione regolare(str, espressione regolare) funziona come esempio perché precompila il suo modello regexp e quindi lo utilizza durante l'elaborazione delle righe. Questo è simile alla pre-costruzione di un trie Aho-Corasick e quindi alla sua applicazione su ogni riga.
La nostra espressione catalizzatrice personalizzata accetta due argomenti. È quindi a BinaryExpression che ha due campi nominati da Spark left E right. Il nostro costruttore AhoCorasickIn assegna il file text argomento di colonna a left campo e il searches matrice di stringhe in right campo.
L'altra cosa che facciamo durante l'inizializzazione di AhoCorasickIn è valutare il file cacheTrie campo. I test di valutazione se il searches l'argomento è un'espressione pieghevole, cioè un'espressione costante. In tal caso, lo valuta e si aspetta che sia un array di stringhe, che utilizza per chiamare createTrie(searches).
IL createTrie la funzione esegue l'iterazione delle ricerche e le aggiunge al file trieBuilder e infine costruisce un Aho-Corasick Trie.
case class AhoCorasickIn(text: Expression, searches: Expression)
extends BinaryExpression
with CodegenFallback
with ImplicitCastInputTypes
with NullIntolerant
with Predicate {override def prettyName: String = "aho_corasick_in"
// Assign text to left field
override def left: Expression = text
// Assign searches to right field
override def right: Expression = searches
override def inputTypes: Seq(DataType) = Seq(StringType, ArrayType(StringType))
// Cache foldable searches expression when AhoCorasickIn is constructed
private lazy val cacheTrie: Trie = right 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.build()
}
protected def getTrie(searches: ArrayData) = if (cacheTrie == null) createTrie(searches) else cacheTrie
override protected def nullSafeEval(text: Any, searches: Any): Any = {
val trie = getTrie(searches.asInstanceOf(ArrayData))
trie.containsMatch(text.asInstanceOf(UTF8String).toString())
}
override protected def withNewChildrenInternal(
newLeft: Expression, newRight: Expression): AhoCorasickIn =
copy(text = newLeft, searches = newRight)
}
IL nullSafeEval è il cuore di AhoCorasickIn. Spark chiama la funzione eval per ogni riga nel set di dati. In nullSafeEvalrecuperiamo il cacheTrie e usarlo per testare il file text argomento di stringa.
Valutazione delle prestazioni
Per confrontare le prestazioni del aho_corasick_in funzione abbiamo scritto un piccolo script di benchmarking. Abbiamo confrontato le prestazioni di fare più cose LIKE operazioni rispetto ad una singola aho_corasick_in chiamata.
select
*
from (
select
text like '%' || uuid() || '%' OR
text like '%' || uuid() || '%' OR
text like '%' || uuid() || '%' OR
...
as result
from (
select
uuid()||uuid()||uuid()... as text
from
range(0, 1000000, 1, 32)
)
)
where
result = TRUE
Stesso esperimento utilizzando aho_corasick_in:
select
*
from (
select
aho_corasick_in(text, array(uuid(), uuid(),...) as result
from (
select
uuid()||uuid()||uuid()... as text
from
range(0, 1000000, 1, 32)
)
)
where
result = TRUE
Abbiamo eseguito questi due esperimenti (come vs aho_corasick_in) con a text colonna di 200 caratteri e variato il numero di termini di ricerca. Ecco un grafico logaritmico che confronta entrambe le query.
Questo grafico mostra come le prestazioni diminuiscono man mano che aggiungiamo più termini di ricerca alla query “MI PIACE”, mentre la query utilizza aho_corasick_in la funzione rimane relativamente costante all’aumentare del numero di termini di ricerca. A 100 termini di ricerca, il aho_corasick_in la funzione viene eseguita cinque volte più velocemente di più istruzioni LIKE.
Riteniamo che l'utilizzo di Aho-Corasick sia vantaggioso solo dopo 20 ricerche. Ciò può essere spiegato dal costo iniziale di costruzione del trie. Tuttavia, con l’aumento del numero di termini di ricerca, il costo iniziale viene ripagato. Ciò contrasta con le espressioni LIKE, dove più espressioni LIKE aggiungiamo, più costosa diventa la query.
Successivamente, impostiamo il numero di termini di ricerca su 20 e modifichiamo la lunghezza dei termini di ricerca text corda. Abbiamo osservato che sia il LIKE che aho_corasick_in la funzione impiega circa lo stesso tempo su varie lunghezze di stringa. In entrambi gli esperimenti il tempo di esecuzione dipende dalla lunghezza del text corda.
È importante notare che il costo sostenuto per creare il trie dipenderà dal numero di attività Spark nel piano di esecuzione della query. Spark istanzia le espressioni (ovvero: istanzia nuovi oggetti AhoCorasickIn) per ogni attività nel piano di esecuzione. In altre parole, se la query utilizza 200 attività, il costruttore AhoCorasickIn verrà chiamato 200 volte.
Per riassumere, la strategia da utilizzare dipenderà dal numero di termini. Abbiamo integrato questa ottimizzazione nel nostro compilatore Sigma. Al di sotto di una determinata soglia (diciamo 20 termini) esegue il rendering delle istruzioni LIKE e al di sopra di questa soglia esegue il rendering di una query che utilizza l'espressione aho_corasick_in funzione.
Naturalmente questa soglia dipenderà dai dati effettivi e dal numero di attività nel piano di esecuzione di Spark.
I nostri risultati iniziali, condotti su dati di produzione e regole SigmaHQ reali, mostrano che l'applicazione del aho_corasick_in la funzione aumenta la nostra velocità di elaborazione (eventi al secondo) di un fattore di 1,4x.
Conclusione
In questo articolo abbiamo dimostrato come implementare una funzione Spark nativa. Questa espressione Catalyst sfrutta l'algoritmo Aho-Corasick, che può testare molti termini di ricerca contemporaneamente. Tuttavia, come con qualsiasi approccio, ci sono dei compromessi. L'utilizzo di Aho-Corasick richiede la creazione di un trie (albero dei prefissi), che può ridurre le prestazioni quando vengono utilizzati solo pochi termini di ricerca. Il nostro compilatore utilizza una soglia (numero di termini di ricerca) per scegliere la strategia ottimale, garantendo l'esecuzione della query più efficiente.
Fonte: towardsdatascience.com
