1my8xam3pyno9ujrpsthxua.jpeg

Ampliación de Spark para mejorar el rendimiento en el manejo de múltiples términos de búsqueda

Foto de Aditya Chinchure en Unsplash

Durante el proceso de implementación de nuestro sistema de detección de intrusiones en producción en CCCS, observamos que muchas de las reglas de SigmaHQ utilizan listas muy importantes de patrones de búsqueda. Estas listas se utilizan para probar si un CommandLinecontiene una cadena determinada o si el CommandLinecomienza o termina con una subcadena determinada.

Estábamos particularmente interesados ​​en investigar las reglas que involucran condiciones «contiene», ya que sospechamos que estas condiciones podrían llevar mucho tiempo para que Spark las evalúe. A continuación se muestra un ejemplo de una regla Sigma típica:

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 regla completa sobre nombres de programas sospechosos se puede encontrar aquí
https://github.com/SigmaHQ/sigma/blob/master/rules/windows/process_creation/proc_creation_win_susp_progname.yml

La regla ilustra el uso de CommandLine|contains y de Image|endswith. Algunas reglas de Sigma tienen cientos de términos de búsqueda bajo un <field>|containscondición.

Aplicar reglas Sigma con Spark SQL

En CCCS, traducimos las reglas de Sigma en declaraciones ejecutables de Spark SQL. Para hacerlo, hemos ampliado el compilador SQL Sigma con un backend personalizado. Traduce la regla anterior en una declaración como esta:

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

Ejecutamos la declaración anterior en un trabajo de transmisión estructurado de Spark. En una sola pasada por los eventos, Spark evalúa múltiples (cientos) de reglas Sigma. El sigma_rules_map La columna contiene los resultados de la evaluación de todas estas reglas. Usando este mapa podemos determinar qué regla es un éxito y cuál no.

Como podemos ver, las reglas a menudo implican comparar el atributo del evento, como CommandLinea múltiples patrones de cuerdas.

Algunas de estas pruebas son coincidencias exactas, como CommandLine = ‘something’. Otros usan startswithy se representan como Imagepath LIKE ‘%\\poc.exe’.

Equals, startswithy endswith se ejecutan muy rápidamente ya que todas estas condiciones están ancladas en una posición particular en el atributo del evento.

Sin embargo, pruebas como contains se representan como CommandLine LIKE ‘%hound.ps1%’ lo que requiere que Spark escanee todo el atributo para encontrar una posible posición inicial para la letra ‘h’ y luego verifique si va seguida de la letra ‘o’, ‘u’, etc.

Internamente, Spark utiliza un UTF8String que toma el primer carácter, escanea el búfer y, si encuentra una coincidencia, compara los bytes restantes usando el matchAt función. Aquí está la implementación del UTF8String.contains función.

  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;
}

El equals, startswithy endswith condiciones también utilizan el matchAt función pero al contrario de contains estas condiciones saben dónde comenzar la comparación y, por lo tanto, se ejecutan muy rápidamente.

Para validar nuestra suposición de que contains La condición es costosa de ejecutar. Realizamos un experimento rápido y simple. Eliminamos todos los contains condiciones para las reglas de Sigma para ver cómo afectarían el tiempo general de ejecución. La diferencia fue significativa y nos animó a seguir la idea de implementar una función Spark Catalyst personalizada para manejar contains operaciones que involucran una gran cantidad de términos de búsqueda.

El algoritmo de Aho-Corasick

Un poco de investigación nos llevó a la Algoritmo de Aho-Corasick lo que parecía ser una buena opción para este caso de uso. El algoritmo de Aho-Corasick construye un árbol de prefijos (un trie) y puede evaluar muchos contains expresiones en una sola pasada sobre el texto a probar.

Aquí se explica cómo utilizar la implementación Java Aho-Corasick de Robert Bor disponible en github aquí 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)

Diseñando un aho_corasick_in Función de chispa

Nuestra función necesitará dos cosas: la columna que se probará y los patrones de búsqueda que se buscarán. Implementaremos una función con la siguiente firma:

boolean aho_corasick_in(string text, array<string> searches)

Modificamos nuestro compilador CCCS Sigma para producir declaraciones SQL que utilizan el aho_corasick_infunción en lugar de producir múltiples predicados LIKE con OR. En el resultado siguiente, notará el uso de la aho_corasick_in función. Pasamos el campo a probar y una serie de cadenas a buscar. Aquí está el resultado de nuestro compilador personalizado que maneja múltiples contains condiciones:

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

Observe cómo el aho_corasick_in La función recibe dos argumentos: el primero es una columna y el segundo es una matriz de cadenas. Implementemos ahora realmente el aho_corasick_infunción.

Implementación de la función catalizadora

No encontramos mucha documentación sobre cómo implementar las funciones de Catalyst, por lo que utilizamos el código fuente de las funciones existentes como referencia. tomamos el expresión regular(cadena, expresión regular) funciona como ejemplo porque precompila su patrón de expresión regular y luego lo usa al procesar filas. Esto es similar a construir previamente un trie Aho-Corasick y luego aplicarlo a cada fila.

Nuestra expresión de catalizador personalizada requiere dos argumentos. Es por tanto un BinaryExpression que tiene dos campos que Spark nombró left y right. Nuestro constructor AhoCorasickIn asigna el text argumento de columna para left campo y el searches matriz de cadenas para right campo.

La otra cosa que hacemos durante la inicialización de AhoCorasickIn es evaluar el cacheTrie campo. La evaluación prueba si el searches El argumento es una expresión plegable, es decir, una expresión constante. Si es así, lo evalúa y espera que sea una matriz de cadenas, que utiliza para llamar createTrie(searches).

El createTrie La función itera sobre las búsquedas y las agrega al trieBuilder y finalmente construye 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)
}

El nullSafeEval El método es el corazón de AhoCorasickIn. Spark llama a la función de evaluación para cada fila del conjunto de datos. En nullSafeEvalrecuperamos el cacheTrie y usarlo para probar el text argumento de cadena.

Evaluación del desempeño

Para comparar el desempeño de la aho_corasick_in función escribimos un pequeño script de evaluación comparativa. Comparamos el rendimiento de hacer múltiples LIKE operaciones versus una sola aho_corasick_in llamar.

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

Mismo experimento usando 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

Realizamos estos dos experimentos (como vs aho_corasick_in) con un text columna de 200 caracteres y varió el número de términos de búsqueda. Aquí hay un gráfico logarítmico que compara ambas consultas.

Imagen del autor

Este gráfico muestra cómo el rendimiento se degrada a medida que agregamos más términos de búsqueda a la consulta «ME GUSTA», mientras que la consulta que utiliza aho_corasick_in La función permanece relativamente constante a medida que aumenta el número de términos de búsqueda. En 100 términos de búsqueda, el aho_corasick_in La función se ejecuta cinco veces más rápido que varias declaraciones LIKE.

Descubrimos que utilizar Aho-Corasick solo es beneficioso después de 20 búsquedas. Esto puede explicarse por el costo inicial de construir el trie. Sin embargo, a medida que aumenta la cantidad de términos de búsqueda, ese costo inicial vale la pena. Esto contrasta con las expresiones LIKE, donde cuantas más expresiones LIKE agreguemos, más costosa será la consulta.

A continuación, establecimos el número de términos de búsqueda en 20 y variamos la longitud del text cadena. Observamos que tanto el LIKE como el aho_corasick_in La función tarda aproximadamente el mismo tiempo en varias longitudes de cadena. En ambos experimentos, el tiempo de ejecución depende de la duración del text cadena.

Imagen del autor

Es importante tener en cuenta que el costo incurrido para crear el trie dependerá de la cantidad de tareas de Spark en el plan de ejecución de consultas. Spark crea instancias de expresiones (es decir, crea instancias de nuevos objetos AhoCorasickIn) para cada tarea en el plan de ejecución. En otras palabras, si su consulta utiliza 200 tareas, se llamará al constructor AhoCorasickIn 200 veces.

En resumen, la estrategia a utilizar dependerá del número de términos. Construimos esta optimización en nuestro compilador Sigma. Por debajo de un umbral determinado (digamos 20 términos), genera declaraciones LIKE y por encima de este umbral genera una consulta que utiliza el aho_corasick_in función.

Por supuesto, este umbral dependerá de sus datos reales y de la cantidad de tareas en su plan de ejecución de Spark.

Nuestros resultados iniciales, realizados con datos de producción y reglas reales de SigmaHQ, muestran que aplicar el aho_corasick_in La función aumenta nuestra tasa de procesamiento (eventos por segundo) en un factor de 1,4 veces.

Imagen del autor

Conclusión

En este artículo, demostramos cómo implementar una función nativa de Spark. Esta expresión de Catalyst aprovecha el algoritmo Aho-Corasick, que puede probar muchos términos de búsqueda simultáneamente. Sin embargo, como ocurre con cualquier enfoque, existen compensaciones. El uso de Aho-Corasick requiere crear un trie (árbol de prefijos), que puede degradar el rendimiento cuando solo se utilizan unos pocos términos de búsqueda. Nuestro compilador utiliza un umbral (número de términos de búsqueda) para elegir la estrategia óptima, asegurando la ejecución de consultas más eficiente.