Blind XPath Injection: Booleanización [II de III]

***************************************************************************************
- Blind XPath Injection: Booleanización [I de III]
- Blind XPath Injection: Booleanización [II de III]
- Blind XPath Injection: Booleanización [III de III]
***************************************************************************************

Una vez visto como se booleanizan los valores enteros y de tipo cadea, la pregunta es: ¿se puede optimizar este proceso de alguna forma? Vamos a analizar esto en los próximos puntos.

a) Booleanización de valores tipo texto con función contains

El algoritmo presentado utiliza, como optimizaciones en la booleanización de valores escalares de tipo texto y de tipo carácter, un sistema de búsqueda binaria. En el caso de la booleanización de valores de tipo texto se hace con un sistema de listas de cadenas de caracteres y su traslación a valores numéricos con la función translate. Ambos métodos son eficientes, sin embargo, la especificación de XPath 1.0 permite utilizar la función contains para conocer si un determinado carácter existe o no en una cadena de caracteres. Esto evitaría el uso de las cadenas numéricas y la función translate, bastaría con una llamada a la funcion:

boolean contains(string, string)

Por otro lado, esta reducción es bastante inocua en la complejidad total del algoritmo ya que su única ventaja es eliminar el uso de cadenas numéricas y dobles funciones, pero no hace menor el número de peticiones al servidor.

b) Reducción del juego de caracteres

Al igual que se puede realizar en los entornos de Blind LDAP Injection, es posible computar una fase de reducción del tamaño inicial de la lista mediante un recorrido lineal de todos los caracteres utilizando la función contains. Para ello, se debe estimar cuándo el coste de computar la reducción del juego de caracteres es asumible en términos de computación algorítimica frente a un cálculo directo.

A pesar de que esta fase de reducción parezca que genera una mejora evidente, esto no siempre tiene por qué ser así, con lo que hay que estimar que es más eficiente: Reducir el alfabeto y luego hacer la búsqueda binaria sobre el alfabeto reducido o directamente hacer la búsqueda binaria sobre el alfabeto sin reducir. Para estimar este valor, sin ninún conocimiento a priori, se puede utilizar, como estimador, la longitud de la cadena de caracteres a extraer.

El número de peticiones que hay que realizar para calcular un carácter depende del tamaño del juego de caracteres totales L. Así, el número de peticiones P será:

P = Log2(L)

Para una cadena C de longitud S, el número de peticiones será de P = S•(Log2(L)) y puede ser representado por una función lineal de pendiente Log2(L).


Figura 6: Número de peticiones en función del tamaño de cadena
Si se realiza una fase de reducción del juego de caracteres de L, para generar un conjunto L’ con los caracteres que están contenidos dentro de la cadena C, el número de peticiones P’ será de:

P’= L+S•(Log2(L’))

Asumiendo el peor caso, en el que en la cadena S no se repita ningún carácter, el tamaño de L’ será equivalente a S. Luego P’ será igual a S+S•Log2(S). Con lo que se obtendría una ganancia, a pesar de la fase previa de reducción de caracteres, cuando se cumpla que la reducción es suficientemente grande.

Suponiendo el peor de los casos, que sea que S sea igual o mayor que L y todos los caracteres de L estén en S, la curva resultante sería L+S•Log2(L).


Figura 7: Caso degenerado en el que L’ es igual a L
Sin embargo, si L’ es igual a S pero menor que L, para que hubiera una reducción del coste tras calcular la reducción del juego de caracteres inicial, debería cumplirse que:

L+S(Log2(S))>S•Log2(L)

Sin embargo, si L’ es igual a S, estas dos funciones nunca se cortan.


Figura 8: Caso en el que L’ es igual a S
Para que la reducción sea efectiva hay que fijarse en la siguiente gráfica que representa el punto de corte en el cual empezaría a ser eficiente el uso de la fase de reducción del juego de caracteres.


Figura 9: Puntos de corte
Como puede verse, si S es demasiado corta, puede darse el caso de que el número de peticiones necesarias para hacer la reducción del juego de caracteres sea mayor que el calcular directamente los valores.

Como consecuencia de esto queda claro que dependiendo de la relación entre S, L y el conjunto de caracteres resultante L’ que se genere tras la fase de reducción habrá dos puntos de corte que marcarán la zona donde será beneficioso en tiempo realizar dicha fase de reducción y las zonas en la que no. Estos son los puntos de corte A y B. Dependiendo de la relación entre S, L y L’ los puntos A y B deberán ser distintos. Para encontrar el valor de A y de B es necesario resolver la siguiente fórmula:

P’ ¿menor o mayor? P
L+S•(Log2(L’)) ¿menor o mayor que? S•(Log2(L))

Luego, el proceso de reducción de juego de caracteres sería beneficioso siempre que la relación entre S, L y L’ hagan que se cumpla esa condición.

Con el objetivo de establecer una solución predictiva comprobable empíricamente se puede construir un sistema que estime el tamñao esperado de L’ en función de S y L. Es decir, intentar obtener cuál es la longitud más probable de L’ en función de S y L, ambos conocidos en cada momento.

Para calcular el tamaño de L' esperado se pueden aplicar varias aproximaciones:

1) Utilizar algún valor estimado en función del idioma esperado del documento XML a extraer. Es sabido que cada idioma tiene un factor de repetición de caracteres y una estadística de uso para cada caracter. Para ello, para cada idioma se estimaría un factor K de redución del juego de caracteres en función de S. La siguiente imagen mostraría, para un K=0.5 y un L de 30, como es efectivo el proceso entre los valores 16 y 29.


Figura 10: Tabla de valores para un K=0.5


Figura 11: Gráfica de funciones para un K=0.5
2)Aprender del historico del documento. Para realizar esta comprobación se va asumir que cada carácter c de L tiene, a priori, más o menos prioridad de aparecer dependiendo del tipo de documento XML con que se esté trabajando. Esta premisa, no obstante, podría ser discutida si se conoce el tipo de dato que se almacena y el idioma en que se guarda para, previamente, y sin conocer ninguna característica del documento, estimar el valor de L’ en función de L y S. Con el fin de poder hacer el cálculo de K dinámico y ajustado para el tipo de documento en concreto con el que se está trabajando, se puede utilizar el siguiente algoritmo.

Algoritmo de cálculo de K de forma dinámica

1.- Se crear la lista K[i] que almacena, para cada posición, el número de palabras de longitud i y el porcentaje de reducción del alfabeto K obtenido empíricamente en media.

2.- Se crea la variable K_media que recoge el porcentaje de reducción k medio para el documento. Inicialmente se configura con valor 1.

3.- Para cada nueva cadena a descubrir se aplica se calcula su longitud S.

4.- Se busca el valor K[S]. Si no existe ninguno se utiliza K_media.

5.- Se decide si hay que reducir o no por medio de la fórmula.

L+S•(Log2(K[S]*S)) ¿es menor que? S•(Log2(L))

6.- Si se cumple se aplica proceso de reducción de L a L’

7.- Se obtiene la cadena y se calculan los valores reales de L’ y K en este caso.

8.- Se actualizan los valores de K[S] y K_media

El proceso descrito en este algoritmo queda representado en el siguiente diagrama.


Figura 12: Algoritmo para cálculo de K[S] de forma dinámica

***************************************************************************************
- Blind XPath Injection: Booleanización [I de III]
- Blind XPath Injection: Booleanización [II de III]
- Blind XPath Injection: Booleanización [III de III]
***************************************************************************************