Implementación de un algoritmo de aprendizaje para el análisis de series temporales

Implementación de un algoritmo de aprendizaje para el análisis de series temporales Implementation of a data mining algorithm for analyzing time series Directores: José Ignacio Requeno & Luis Llana Díaz Autores: Jorge Lasheras Martín (GIS) & Carlos Morán Alfonso (DG-MAT) Trabajo de fin de grado del Grado en Ingeniería de Computadores e Ingeniería Informática Facultad de Informática Universidad Complutense de Madrid Curso 2022-2023 Agradecimientos En primer lugar, queremos agradecer este TFG a nuestras familias y amigos, que siempre han estado ahí para escucharnos y apoyarnos, en los buenos tiempos y en los malos. Sin su constante apoyo, ni este TFG ni nuestras respectivas carreras hubieran sido posibles. En segundo lugar y no por ello menos importante, nos gustaría también agradecer el gran trabajo realizado por nuestros tutores, José Ignacio Requeno y Luis Llana, por su esfuerzo y dedicación. Este trabajo ha sido posible gracias a su cercanía, disposición, conocimientos, críticas constructivas y ayuda en general. I Time flies over us but leaves its shadow behind – Nathaniel Hawthorne Resumen El principal objetivo de este TFG es extender una herramienta para el análisis de series temporales introduciendo un nuevo algoritmo de minado de datos y evaluar su posterior aplicación para el análisis y extracción de patrones de comportamiento en un caso de estudio. Para llevar a cabo dicho análisis y poder examinar diferentes propiedades de estas señales, hemos usado lógica temporal o, más concretamente, una variante de la misma adaptada al análisis de propiedades de series temporales conocida como Signal Temporal Logic (STL). Esta extensión de la lógica temporal incorpora a la sintaxis de lógica de primer orden otros operadores que permiten la generalización de patrones sobre intervalos. El trabajo está dividido en tres fases: una fase de investigación, una fase de implementación de un nuevo algoritmo y su incorporación a una biblioteca de Python ya existente llamada ParetoLib, y una última fase de experimentación sobre datos reales. En particular, aplicaremos nuestra aproximación al análisis y detección de comportamientos (a)normales en el consumo eléctrico, registrados por contadores inteligentes osmart grids. Palabras Clave Lógica temporal Serie temporal Detección de anomalías Contadores inteligentes Interfaz gráfica Python II Abstract This project’s main purposes are extending the current functionality of a time series analysis tool by introducing a new data mining algorithm and testing said algorithm by using it to extract and analyse behaviour patterns on a case study. In order to accomplish these objectives, we used temporal logic or, to be more specific, we used a temporal logic variant specialized on analysing patterns in time series called Signal Temporal Logic (STL). STL is an extension of standard temporal logic whose syntax consists of the standard operators used in first order logic extended with a series of new logic operators that allow for pattern generalisation over intervals. The project has been divided in three different phases. Firstly, an investigation phase, followed by an implementation phase where we implemented the data mining algorithm and incorporated it to an existing library named ParetoLib and, lastly, an experimentation phase using real data. More specifically, we will apply our approach to the analysing and detecting possibly abnormal behaviour in the electrical consumption registered by smart meters or smart grids. Keywords Temporal logic Time series Anomalous behaviour detection Smart Grids Guided User Interface Python Índice general 1. Introducción 1 1.1. Sistemas ciberfísicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Motivación................................. 2 1.3. Objetivos ................................. 2 1.4. Organización temporal . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4.1. Comienzo y seguimiento del progreso del trabajo . . . . . . . . 3 1.4.2. Reparto del trabajo y dedicación . . . . . . . . . . . . . . . . 3 1.4.3. Fases del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5. Organización del documento . . . . . . . . . . . . . . . . . . . . . . . 6 2. Introduction 9 2.1. Cyber-physical system . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2. Objectives................................. 10 2.3. Timedistribution............................. 10 2.3.1. Start of the project and follow-up meetings . . . . . . . . . . . 10 2.3.2. Team management and project dedication . . . . . . . . . . . 10 2.3.3. Parts of the project . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4. Document Organization . . . . . . . . . . . . . . . . . . . . . . . . . 14 3. STL - Introducción y aplicación 17 3.1. LógicaTemporal ............................. 17 3.1.1. Preliminar - Lógica de primer orden y sus limitaciones . . . . 17 3.1.2. Lógicatemporal.......................... 18 Linear Temporal Logic (LTL) . . . . . . . . . . . . . . . . . . 18 MITL y las limitaciones de LTL . . . . . . . . . . . . . . . . . 21 3.2. STL .................................... 21 III IV ÍNDICE GENERAL 3.2.1. Señales y series temporales . . . . . . . . . . . . . . . . . . . . 22 3.2.2. Signal Temporal Logic (STL) . . . . . . . . . . . . . . . . . . 22 3.3. STL - Implementación de los operadores . . . . . . . . . . . . . . . . 23 3.3.1. STL - Operadores lógicos . . . . . . . . . . . . . . . . . . . . . 23 3.3.2. STL - Operadores cuantitativos . . . . . . . . . . . . . . . . . 24 STL estándar - Operadores cuantitativos . . . . . . . . . . . . 24 STL extendido - Manipulación de intervalos . . . . . . . . . . 24 3.4. StlEval................................... 25 3.4.1. Incorporación con ParetoLib . . . . . . . . . . . . . . . . . . . 25 4. Algoritmo de minería de propiedades STL paramétricas 27 4.1. Introducción al algoritmo de minado . . . . . . . . . . . . . . . . . . 27 4.2. Paso 1 - División de las celdas . . . . . . . . . . . . . . . . . . . . . . 30 4.2.1. Particiónfija ........................... 31 4.2.2. Partición dinámica . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3. Paso 2 - Encontrar la región de aceptación . . . . . . . . . . . . . . . 37 4.3.1. Uso de paralelización . . . . . . . . . . . . . . . . . . . . . . . 40 4.4. Paso 3 - Elección de los campeones . . . . . . . . . . . . . . . . . . . 42 4.4.1. Distancia de Hausdorff . . . . . . . . . . . . . . . . . . . . . . 42 4.4.2. Preparación de datos para el cálculo de la distancia de Hausdorff 43 4.4.3. Selección de campeones según la distancia de Hausdorff . . . . 45 5. Actualización de la interfaz gráfica 49 5.1. Nuevas funcionalidades . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.1.1. Nuevas opciones . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.1.2. Barrademenú .......................... 50 5.1.3. Mejora en la representación de la señal temporal . . . . . . . . 52 5.2. Bibliotecas utilizadas . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.2.1. PyQt5............................... 55 5.2.2. MatPlotLib ............................ 55 5.2.3. Pandas............................... 55 5.2.4. Seaborn .............................. 56 5.2.5. json ................................ 56 5.3. Guíadeuso ................................ 56 6. Detección de ataques en Smart Grids 61 6.1. Basededatos............................... 61 ÍNDICE GENERAL V 6.2. Preprocesado de los datos . . . . . . . . . . . . . . . . . . . . . . . . 62 6.3. Ataques: Definición y tipos . . . . . . . . . . . . . . . . . . . . . . . . 62 6.3.1. Estudios anteriores y razón de estudio de un nuevo método . . 65 6.4. Fase de experimentación: En profundidad . . . . . . . . . . . . . . . . 67 6.4.1. Preliminar - Fases de un experimento . . . . . . . . . . . . . . 68 6.4.2. Swap................................ 73 Primera aproximación - Acotación simple . . . . . . . . . . . . 73 Segunda aproximación - Acotación doble . . . . . . . . . . . . 75 Tercera aproximación - Acotación doble refinada . . . . . . . . 77 Cuarta aproximación - Solución parasitaria . . . . . . . . . . . 79 Resumen de resultados . . . . . . . . . . . . . . . . . . . . . . 81 6.4.3. FamiliaAverage.......................... 84 Primera aproximación - Triple acotación del rango de valores . 85 Segunda aproximación - Diferencia de acumulaciones . . . . . 86 Tercera aproximación - Combinando las dos anteriores . . . . 89 Cuarta aproximación - Distancias a la media . . . . . . . . . . 92 Resumen de resultados . . . . . . . . . . . . . . . . . . . . . . 94 6.4.4. FDIx................................ 99 Primera aproximación - Acumulaciones extremas . . . . . . . 100 Segunda aproximación - Rangos extremos 2.0 . . . . . . . . . 104 Tercera aproximación - Combinación de las dos anteriores . . . 108 Resumen de resultados . . . . . . . . . . . . . . . . . . . . . . 111 6.4.5. RSA[a,b].............................. 115 Primera aproximación - Acumulaciones extremas . . . . . . . 116 Segunda aproximación - Rangos extremos 2.0 . . . . . . . . . 118 Tercera aproximación - Combinación de las dos anteriores . . . 120 Resumen de resultados . . . . . . . . . . . . . . . . . . . . . . 122 7. Conclusiones y trabajo futuro 127 7.1. Conclusiones................................ 127 7.2. Trabajofuturo .............................. 128 7.2.1. Ampliar el repertorio de operadores de StlEval . . . . . . . . . 128 7.2.2. Ampliar y mejorar los experimentos realizados . . . . . . . . . 130 8. Final thoughts and future work 131 8.1. Finalthoughts............................... 131 8.2. Futurework................................ 132 VI ÍNDICE GENERAL 8.2.1. Adding new operators to StlEval’s repertoire . . . . . . . . . . 132 8.2.2. Improve and broaden the experimentation phase . . . . . . . . 134 A. Códigos STL 135 A.1.Swap.................................... 135 A.1.1. Primera aproximación - Acotación simple . . . . . . . . . . . . 135 A.1.2. Segunda aproximación - Acotación doble . . . . . . . . . . . . 135 A.1.3. Tercera aproximación - Acotación doble refinada . . . . . . . . 136 A.1.4. Cuarta aproximación - Solución parasitaria . . . . . . . . . . . 136 A.2.FamiliaAverage.............................. 136 A.2.1. Primera aproximación - Triple acotación del rango de valores . 136 A.2.2. Segunda aproximación - Diferencia de acumulaciones . . . . . 138 A.2.3. Tercera aproximación - Combinando las dos anteriores . . . . 138 A.2.4. Cuarta aproximación - Distancias a la media . . . . . . . . . . 138 A.3.FDIx.................................... 139 A.3.1. Primera aproximación - Acumulaciones extremas . . . . . . . 139 A.3.2. Segunda aproximación - Rangos extremos 2.0 . . . . . . . . . 140 Tercera aproximación - Combinación de las dos anteriores . . . 141 B. Resultados de los experimentos 143 B.1.Swap.................................... 145 B.1.1. Primera aproximación - Acotación simple . . . . . . . . . . . . 145 Sin intersección de regiones de aceptación . . . . . . . . . . . 145 Con intersección de regiones de aceptación . . . . . . . . . . . 146 B.1.2. Segunda aproximación - Acotación doble . . . . . . . . . . . . 147 Sin intersección de regiones de aceptación . . . . . . . . . . . 147 Con intersección de regiones de aceptación . . . . . . . . . . . 148 B.1.3. Tercera aproximación - Acotación doble refinada . . . . . . . . 149 Sin intersección de regiones de aceptación . . . . . . . . . . . 149 Con intersección de regiones de aceptación . . . . . . . . . . . 150 B.1.4. Cuarta aproximación - Solución parasitaria . . . . . . . . . . . 151 Sin intersección de regiones de aceptación . . . . . . . . . . . 151 Con intersección de regiones de aceptación . . . . . . . . . . . 152 B.2.FamiliaAverage.............................. 154 B.2.1. Primera aproximación - Triple acotación del rango de valores . 154 Con intersección de regiones de aceptación . . . . . . . . . . . 154 B.2.2. Segunda aproximación . . . . . . . . . . . . . . . . . . . . . . 155 ÍNDICE GENERAL VII Sin intersección de regiones de aceptación . . . . . . . . . . . 155 Con intersección de regiones de aceptación . . . . . . . . . . . 158 B.2.3. Tercera aproximación . . . . . . . . . . . . . . . . . . . . . . . 161 Sin intersección de regiones de aceptación . . . . . . . . . . . 161 Con intersección de regiones de aceptación . . . . . . . . . . . 163 B.2.4. Cuarta aproximación - Distancias a la media . . . . . . . . . . 166 Sin intersección de regiones de aceptación . . . . . . . . . . . 166 Con intersección de regiones de aceptación . . . . . . . . . . . 169 B.3.FDIx.................................... 173 B.3.1. Primera aproximación . . . . . . . . . . . . . . . . . . . . . . 173 Sin intersección de regiones de aceptación . . . . . . . . . . . 173 Con intersección de regiones de aceptación . . . . . . . . . . . 177 B.3.2. Segunda aproximación . . . . . . . . . . . . . . . . . . . . . . 181 Sin intersección de regiones de aceptación . . . . . . . . . . . 181 Con intersección de regiones de aceptación . . . . . . . . . . . 185 B.3.3. Tercera aproximación . . . . . . . . . . . . . . . . . . . . . . . 189 Sin intersección de regiones de aceptación . . . . . . . . . . . 189 Con intersección de regiones de aceptación . . . . . . . . . . . 193 B.4.RSA[a,b].................................. 198 B.4.1. Primera aproximación . . . . . . . . . . . . . . . . . . . . . . 198 Sin intersección de regiones de aceptación . . . . . . . . . . . 198 Con intersección de regiones de aceptación . . . . . . . . . . . 201 B.4.2. Segunda aproximación . . . . . . . . . . . . . . . . . . . . . . 205 Sin intersección de regiones de aceptación . . . . . . . . . . . 205 Con intersección de regiones de aceptación . . . . . . . . . . . 208 B.4.3. Tercera aproximación . . . . . . . . . . . . . . . . . . . . . . . 212 Sin intersección de regiones de aceptación . . . . . . . . . . . 212 Con intersección de regiones de aceptación . . . . . . . . . . . 215 C. Otros experimentos relevantes 219 C.1.Swap.................................... 220 C.1.1. Primera aproximación - Acotación simple . . . . . . . . . . . . 220 C.1.2. Tercera aproximación - Acotación doble refinada . . . . . . . . 221 C.2.FDIx.................................... 223 C.2.1. Tercera aproximación - Combinación de las dos anteriores . . . 223 D. Propiedades desechadas 225 6CAPÍTULO 1. INTRODUCCIÓN Figura 1.2: Diagrama de Gantt: segundo cuatrimestre 1.5. Organización del documento Hemos dividido este documento en dos capítulos dedicados a resolver los objetivos planteados en la sección anterior, un capítulo de introducción a lo que es STL, una conclusión y esta introducción. Es decir: 1. Un capítulo dedicado a explicar qué es STL y cómo lo hemos usado e incorporado en este trabajo. Entre los objetivos del trabajo como tal una explicación de STL no está incluida pero creemos pertinente sentar unas bases sobre lo que es STL y para qué lo hemos usado antes de profundizar en lo que ha consistido nuestro trabajo. 2. Un capítulo dedicado a toda la fase de implementación de los primeros meses del curso. Es decir, implementación del algoritmo de minado de propiedades 1.5. ORGANIZACIÓN DEL DOCUMENTO 7 STL paramétricas y el de elección de los campeones. Es decir, el primer de los objetivos del trabajo en general que hemos remarcado más arriba. 3. Un capítulo dedicado a toda la fase de experimentación del uso de propiedades STL paramétricas para detectar ataques en Smart Grids. Es decir, el segundo de los objetivos del trabajo subrayado más arriba. 4. Una conclusión que resuma todo lo hallado durante el trabajo y proponga posibles mejoras o trabajos para el futuro. 8 Chapter 2 Introduction 2.1. Cyber-physical system A cyber-physical system, also known as CPS, is a system in which a physical device is monitored and controlled in some way by a computer based algorithm. This algorithm can be easily represented by a Finite State Machine (FSM) by modelling each state after the desired behaviour expected of the physical device, with which it is able to communicate through a series of sensors. Relevant examples of this kind of system can be found all throughout our daily lives, ranging from smart grids and other such devices to the autopilot systems used to regulate the altitude and trajectory of a commercial plane or medical implants such as pacemakers. As such, guaranteeing these sort of systems work properly is pivotal because, otherwise, a small mistake could lead to the deaths of many people. There are various ways of verifying that a particular cyber physical system is working as intended, such as model checking methods and performing static source code analysis in search of errors. In this paper, however, we will be using runtime verification. We will analyse the execution traces of a particular supervised system and verify that said traces behave in accordance with a previously established “correct” behaviour. There are many different options to properly define a particular behaviour pattern and the one we have decided to use during this paper is STL (Signal Temporal Logic, see [13]), a particular type of temporal logic specialised in analysing analog signals, digitalised through a time series. 9 10 CHAPTER 2. INTRODUCTION 2.2. Objectives This project’s main objectives are: Broaden ParetoLib’s (a Python library dedicated to time series analysis through the use temporal logic) capabilities by implementing and incorporating a data mining algorithm that can learn behavioural patterns (represented by STL properties) by execution tracing. Update the said library’s already existing GUI by incorporating the new features. Use the previously mentioned algorithm in combination with real data from a particular case study in order to detect abnormal behaviours in the electrical consumption registered by smart meters and other smart grids. 2.3. Time distribution 2.3.1. Start of the project and follow-up meetings The project started on September 5th, 2022 and has been carried out by Jorge Lasheras Martín (GIS) and Carlos Morán Alfonso (DG-MAT) under the supervision of José Ignacio Requeno Jarabo and Luís Llana Díaz. It lasted for approximately 8 months and encompassed the entirety of the academic year. The methodology used to routinely check on the project’s progress was SCRUM, which we put into effect by performing weekly follow-up meetings in which we discussed all kinds of issues related to the project while sharing our own progress. In addition to these meetings, we have also used other task management and communication methods, such as using apps like Jira or Slack, which have provided the organization and agile communication between us and our superviors that we needed. 2.3.2. Team management and project dedication Both participants have put 3 hours a day in average into the project. Not only that, but 1800 new lines of code have been written, all of them in one of the following three categories: 2.3. TIME DISTRIBUTION 11 The implementation of the parametric STL data mining algorithm in combination with its incorporation into ParetoLib, the Python library dedicated to pattern analysis in time series (see [14]). Both members of the group participated in the implementation and Carlos incorporated it into ParetoLib. Updating ParetoLib’s GUI. Many of the updates were implemented by Jorge, but Carlos also did some work (specially on incorporating the previously mentioned data mining algorithm) Evaluating the data mining algorithm by performing experiments on a case study (see [12]). The experiments were performed by both Jorge and Carlos and the lines of code were written in Python and Bash scipts aimed at extracting and processing the data on one hand and facilitaing automating the process of performing said experiments. 2.3.3. Parts of the project We divide the project in its entirety into 7 distinct phases: Familiarising ourselves with the material, the tools and the work environment This phase was performed between mid September and early November. It was when we started to get acquainted with the materials and the work environment (temporal logic, STL, ParetoLib, etc.). We were given the necessary helping materials (articles, books, repositories, etc.) by our supervisors. Implementation of the mining algorithm This phase encompasses between mid September and mid October. It was when we implemented the data mining algorithm using parametric STL properties and all of its variants (parallel and sequential programming and static and dynamic exploration of the given search space). Implementation of the champions selection algorithm This phase encompasses between mid September and early November again. It was when the implementation of the champions selection algorithm was implemented, that is, the extraction of characteristic configurations or ideal parameter values for every scenario that was taken into consideration. Both the pseudocode for the data mining and the champions selection algorithms were extracted from [5]. 12 CHAPTER 2. INTRODUCTION Updating ParetoLib’s GUI At the same time that we were implementing the champions selection algorithm, we also updated the GUI in order to incorporate the new features brought by the data mining algorithm. Exploration of the different types of attacks on smart grids This phase encompasses between mid November 2022 to early February 2023. We had to investigate the different kinds of attacks on smart grids before starting the experimentation phase. Behaviour pattern extraction, mining and analysis using real data This phase encompasses between mid February and April. It was during this phase where we carried out the modeling and experimentation of attacks on smart grids as well as put our STL knowledge to use in order to determine new and better STL properties for each attack. We also conducted a deep and detailed analysis of the results we obtained from these experiments. Redacción del manuscrito de la memoria Lastly, this phase encompasses between late February and late May. It was during this phase were we collected the data and progress on the project and wrote them in this report For a better visualization of the different phases of the project and their distribution through time, this is this project’s Gantt chart: 2.3. TIME DISTRIBUTION 13 Figure 2.1: Gantt diagram: First semester 14 CHAPTER 2. INTRODUCTION Figure 2.2: Gantt diagram: Second semester 2.4. Document Organization We have divided this document in two chapters dedicated to solving the previously mentioned objectives, an introduction to STL and temporal logic at large, a general introduction for the project and a conclusion, that is: 1. A chapter dedicated to explaining what STL is and how we have used it during this project. Among this project’s objectives we neglected to mention an explanation of what STL is be we believe it is necessary to lay the groundwork of what temporal logic and STL are before further elaborating on what our contribution is. 2. A chapter dedicated to the implementation of both the data mining algorithm and the champions selection algorithm, that is, the first of the two main objectives mentioned above. 2.4. DOCUMENT ORGANIZATION 15 3. A chapter dedicated to the experimentation on smart grids using STL parametric properties. That is, the second of the above mentioned objectives. 4. A conclusion where we summarize the contents of the projects and where we can provide insight as to what the future of this project might hold. 22 CAPÍTULO 3. STL - INTRODUCCIÓN Y APLICACIÓN 3.2.1. Señales y series temporales En términos generales, llamamos señal a una muestra de la progresión de uno o más valores a lo largo de un intervalo de tiempo. Vemos entonces que, formalmente, una señal es una función f: [t1, t2]∈R→Rn. Como con una señal no se puede realizar ningún tipo de análisis (ya que el dominio de la función no es finito), necesitamos alguna manera de discretizar (o digitalizar) dicha señal. La manera que encontramos es mediante una serie temporal. Una serie temporal es un conjunto de pares de la forma (ti, xi), donde ties un instante de tiempo y xi=f(ti)es el valor de la señal en el instante ti(es decir, una serie temporal es un muestreo de la señal). Ilustramos ahora estas dos definiciones mediante un ejemplo gráfico. (1) Señal original (2) Señal digitalizada Es claro entonces que la digitalizacíon de una señal mediante una serie temporal define una serie de puntos finitos que, juntos, forman un intervalo. El tipo de lógica temporal que se encarga del modelado y monitorización de dichos intervalos es STL. 3.2.2. Signal Temporal Logic (STL) Signal Temporal Logic (en español, Lógica Temporal de Señales), más conocida como STL es un tipo de lógica temporal dedicada al modelado y monitorización de series temporales. Nos encontramos en una situación similar a la que establecimos más arriba con STL. Tenemos un conjunto de predicados a verificar Σy un número finito de estados sobre el que podemos aplicar los operadores vistos antes para LTL para verificar la veracidad o falsedad de los miembros de Σ(mediante el uso de una función 3.3. STL - IMPLEMENTACIÓN DE LOS OPERADORES 23 de evaluación S′: Σ → {true, false}asociada a dicho testado). Vemos, entonces, que la sintaxis de STL básica no cambia con respecto a la vista anteriormente para LTL. ϕ::= ⊤⊥¬ϕ1ϕ1∧ϕ2ϕ1∨ϕ2ϕ1⊕ϕ2ϕ1⇒ϕ2ϕ1⇔ϕ2G[a,b]ϕF[a,b]ϕ ϕ1U[a,b]ϕ2 Presentada la sintaxis básica de STL, procedemos a hablar ahora de la implementación de estos operadores. 3.3. STL - Implementación de los operadores 3.3.1. STL - Operadores lógicos Veamos entonces la implementación de los operadores mediante una muestra de la semántica de los mismos para una serie temporal de n puntos. Sean entonces ϕ, ϕ1, ϕ2∈ΣyS={Si: 0 ≤i≤n}el conjunto de funciones de evaluación asociadas a cada uno de los estados: ⊤:= true∀ϕ∈Σ, S ∈ S ⊥:= false∀ϕ∈Σ, S ∈ S ¬(ϕ) := ¬(S(ϕ)) ϕ1∧ϕ2:= m´ın(S(ϕ1), S(ϕ2)) ϕ1∨ϕ2:= m´ax(S(ϕ1), S(ϕ2)) ϕ1⊕ϕ2:= (S(ϕ1)∨S(ϕ2)) ∧(¬S(ϕ1)∨ ¬S(ϕ2)) ϕ1⇒ϕ2:= ¬S(ϕ1)∨S(ϕ2) ϕ1⇔ϕ2:= (S(ϕ1)⇒S(ϕ2)) ∧(S(ϕ2)⇒S(ϕ1)) ϕ1(t) = ϕ2(t) := S(ϕ1(t) = ϕ2(t)) ϕ1(t)≤ϕ2(t) := S(ϕ1(t)≤ϕ2(t)) ϕ1(t)≥ϕ2(t) := S(ϕ1(t)≥ϕ2(t)) ϕ1(t)< ϕ2(t) := S(ϕ1(t)< ϕ2(t)) ϕ1(t)> ϕ2(t) := S(ϕ1(t)> ϕ2(t)) 24 CAPÍTULO 3. STL - INTRODUCCIÓN Y APLICACIÓN G[a,b]ϕ:= b V i=a Si(ϕ)donde Sies la función de evaluación asociada al estado i F[a,b]ϕ:= ∃t1:a≤t1≤b, ¬t1 V i=a Si(ϕ)∧ b V j=t1+1 Sj(ϕ)! ϕ1U[a,b]ϕ2:= ∃t1:a≤t1≤b, t1 V i=a Si(ϕ1)∧ b V j=t1 Sj(ϕ2)! Presentada la sintaxis y la semántica de los operadores lógicos de STL, pasamos ahora a los operadores dedicados a la manipulación de datos escalares. 3.3.2. STL - Operadores cuantitativos STL estándar - Operadores cuantitativos Para garantizar la robustez semántica de los operadores lógicos vistos anteriormente y para que STL sea una herramienta funcional a nivel computacional, es necesario introducir operadores que puedan manipular de manera efectiva los datos escalares arrojados por la serie temporal que se está monitorizando. Estos operadores son los operadores aritméticos tradicionales (+, -, *, /). También es necesario, entonces, introducir una serie de operadores lógicos que nos sirvan para “booleanizar” los datos escalares y, por tanto, poder trabajar con ellos desde el punto de vista de STL. Estos operadores también nos son conocidos ya que son los relacionados con comparaciones numéricas (>,<,=,≥,≤). Sin embargo, estos operadores nos dejan muy poco margen de maniobra a la hora de manipular datos numéricos. Como ejemplo, no podemos hacer nada con intervalos de la misma manera que sí podemos con los operadores lógicos introducidos más arriba. Es aquí donde entra STL extendido. STL extendido - Manipulación de intervalos STL extendido (ver [15]) refuerza los operadores de STL estándar introduciendo nuevos operadores dedicados a extraer diversas propiedades de intervalos numéricos. Veamos ahora cuáles son estos nuevos operadores: m´axa,b ϕ: Representa el máximo valor de la señal ϕen el intervalo [a, b]. Es decir, 3.4. STLEVAL 25 ∃t1:a≤t1≤b, ϕ(t1)≥ϕ(t)∀t∈[a, b] m´ına,b ϕ: Representa el mínimo valor de la señal ϕen el intervalo [a, b]. Es decir, ∃t1:a≤t1≤b, ϕ(t1)≤ϕ(t)∀t∈[a, b] Rb aϕ: Representa el valor resultante de sumar todos los valores de la señal ϕen el intervalo [a, b]. Es decir, b P t=a ϕ(t). ∆ϕ(t0): Representa el valor de la derivada (o pendiente) de la señal ϕen un cierto instante t0(ver implementaciones de la integral y la derivada en [18]) Presentados ahora todos los operadores, pasamos ahora a presentar StlEval, una herramienta que implementa todos los operadores de STL extendido (lógicos y de manipulación de escalares) y los utiliza para devolver señales booleanas de las que podremos minar trazas de ejecución a lo largo del trabajo. 3.4. StlEval StlEval (ver [3]) es una herramienta desarrollada en C++ por Alexey Bakhirkin, Akshay Mambakan y José Ignacio Requeno que, dados una señal (en formato csv) y una propiedad STL, devuelve una señal booleana dependiendo de si un cierto punto de la señal cumple o no la especificación STL proporcionada. Como ya hemos mencionado, StlEval incorpora el parseo casi todos los operadores del repertorio de STL extendido, con el fin de facilitar la escritura de las propiedades STL. Veamos ahora cómo se encuentra incorporada esta herramienta dentro de ParetoLib. 3.4.1. Incorporación con ParetoLib StlEval ha sido incorporado en ParetoLib (ver [14]), una libreria de Python que permite el minado de propiedades STL (paramétricas y no paramétricas) utilizando como motor de análisis las implementaciones de STL extendido de StlEval, motor que es capaz de incorporar mediante el uso de ctypes, una bibilioteca de Python que sirve como ’puente’ entre C++ y Python (ayudando en la traducción de tipos especialmente). Finalmente, mediante el uso de unas estructuras llamadas oráculos que, a cada punto de la señal de entrada le asocia el valor de salida de StlEval (1 si 26 CAPÍTULO 3. STL - INTRODUCCIÓN Y APLICACIÓN se verifica la propiedad STL, 0 en caso contrario), es como se realiza la conversión a una señal booleana. Capítulo 4 Algoritmo de minería de propiedades STL paramétricas 4.1. Introducción al algoritmo de minado En este capítulo presentamos el algoritmo de minado diseñado para la clasificación de señales temporales (ver [5]). Consiste en un conjunto de métodos para la clasificación multiclase, es decir, una técnica de aprendizaje automático utilizada para predecir la pertenencia de una muestra a una categoría concreta. Nuestro enfoque para el diseño del método de aprendizaje se basa en la implementación de un sistema o modelo inteligente que sea capaz, a partir de unos datos previamente dados y sus etiquetas (que indican la pertenencia a una de las categorías), de aprender y mejorar. El objetivo es que el método pueda detectar y, por ende, aprender patrones, y a partir de estos patrones ser capaz de clasificar cualquier muestra en una categoría concreta. La idea general detrás de nuestro método se basa en que el sistema sea capaz de aprender a partir de ejemplos, en lugar de programar instrucciones específicas para cada uno de los escenarios que se pueden presentar al tratar los datos. El algoritmo de minería se basa en la existencia de un oráculo que clasifica instancias. Dado el dominio del problema y una muestra, el oráculo responde binariamente a las preguntas formuladas: es decir, devuelve verdadero ofalso. El algoritmo asume que el oráculo es una caja negra, por lo que puede aplicarse a cualquier sistema que 27 28CAPÍTULO 4. ALGORITMO DE MINERÍA DE PROPIEDADES STL PARAMÉTRICAS tenga un interfaz que devuelva cierto ofalso a las preguntas que realiza el algoritmo al oráculo sobre la pertenencia de una muestra a una clase. Por tanto, el algoritmo que vamos a implementar se encuadra dentro de los métodos de aprendizaje supervisado: el “modelo” aprende a partir de ejemplos de entrenamiento previamente etiquetados y utiliza la información para hacer predicciones de los nuevos datos sin etiquetar. En el proceso de entrenamiento del método, el algoritmo recibe un dominio del problema, considerado como el espacio de búsqueda, junto con un conjunto de datos etiquetados. A partir de esto, el algoritmo divide el espacio de búsqueda en dos bloques o regiones distintas: una región de aceptación yuna región de rechazo. El modelo resultante del aprendizaje es el dominio del problema (entendido como un espacio de búsqueda o mapa de configuraciones) particionado en estas dos regiones, y el objetivo es, partiendo de un conjunto de dominios, extraer de las regiones de aceptación aquellos puntos que maximizan la distancia de un dominio con respecto a el resto de dominios. En nuestro caso el oráculo usado para la clasificación se trata de un motor que evalúa propiedades STL con parámetros. Concretamente, el oráculo nos responderá si una muestra cumple o no con la propiedad STL, y en base a su respuesta se clasifica dicha muestra como válida. Para ello, durante el entrenamiento se ajustará una propiedad STL parametrizada. Una propiedad STL parametrizada es una fórmula de lógica temporal donde algunos de los valores numéricos de la expresión han sido reemplazados por variables. Una propiedad STL parametrizada permite definir una plantilla de comportamiento, es decir, especifica los patrones de comportamiento de una señal temporal utilizando una fórmula en lógica temporal de señales. La propiedad puede incluir uno o más parámetros ajustables para monitorizar el comportamiento descrito por la fórmula. El proceso de entrenamiento de una propiedad STL parametrizada se centra en ajustar los parámetros de la fórmula de lógica temporal con el objetivo de lograr detectar patrones de comportamiento en las señales temporales. El entrenamiento se enfoca en maximizar la capacidad de la propiedad STL de detectar estos patrones encontrando los valores óptimos de los parámetros. Un ejemplo de propiedad STL parametrizada puede ser el siguiente: G[0,p1]p2≤x0and F[p1,47]x0≥p3(4.1) 4.1. INTRODUCCIÓN AL ALGORITMO DE MINADO 29 Esta propiedad en lógica temporal es cierta para una señal temporal, en el rango de tiempo t∈[0, p1], si se cumple siempre que el valor de la señal ϕes siempre mayor al parámetro p2y se cumple que, a partir de un instante t2∈[p1,47] se cumple que el valor de la señal ϕen t∈[t2,47] es menor a p3. En este caso se usa los parámetros p1,p2yp3para monitorizar el comportamiento de la señal temporal. Es base a eso, dada una propiedad STL y unos parámetros previamente establecidos, el objetivo es lograr discriminar cierto comportamiento descrito por la fórmula STL. Esto se consigue dividiendo el espacio de búsqueda odominio en dos regiones, la región de aceptación y la región de rechazo o no inclusión. El dominio se trata del espacio de búsqueda definido por los parámetros asociados a la propiedad STL. Partimos de la premisa de que los valores de los parámetros se definen como intervalos con límites inferiores y superiores, de modo que el espacio de parámetros Poespacio de búsqueda es un hipercubo cerrado en Rntal que pi∈Rn. P= m Y i=1 [ai, bi](4.2) donde bi> ai,∀i∈1, ..., m, siendo m el número de parámetros definidos para la propiedad y por ende en número de dimensiones que tendrá el hipercubo. La región de aceptación odominio de validez es la región donde se cumplen todas las restricciones establecidas por la propiedad STL, se puede definir como la intersección del dominio de validez de todas las señales que pertenecen a la señal temporal. Por otra parte la región de rechazo es aquella en la que no se cumplen las restricciones establecidas por la propiedad STL. A la región que se encuentra entre ambas regiones la llamaremos frontera, y nos ayudará a identificar a partir de qué valores dentro del rango de los parámetros la propiedad ya no satisface la propiedad. Después de haber explicado los conceptos clave que se tratarán en todo el capítulo, procedemos a describir los pasos que se siguieron para el diseño e implementación del algoritmo. El primero paso será, para el espacio de búsqueda P, realizar una división de celdas. Una vez dividido el espacio de búsqueda, el segundo paso será comprobar para cada celda o subrectángulo si la propiedad STL se cumple para el subconjunto de valores de los parámetros. Luego, todas estas celdas se unirán para formar la región 30CAPÍTULO 4. ALGORITMO DE MINERÍA DE PROPIEDADES STL PARAMÉTRICAS Figura 4.1: Ejemplo de espacio de búsqueda Pdado los intervalos p1,p2yp3 de aceptación. El último paso será seleccionar para cada dominio de validez el valor que maximiza la distancia respecto al dominio de validez de las otras clases. Es decir, seleccionaremos los parámetros de configuración más representativos de los dominios de validez de cada clase, a los que denominaremos campeones. 4.2. Paso 1 - División de las celdas En el primer paso partimos de la lista de intervalos o parámetros sobre la cual se creará un rectángulo de dimensión D, que constituirá nuestro espacio de búsqueda, a este espacio le llamaremos P. Por tanto comenzamos creando un rectángulo de dimensión D, siendo Del número de parámetros previamente establecido. El tamaño del rectángulo será el indicado por los intervalos que definen el espacio de búsqueda, correspondiendo cada intervalo con un eje del rectángulo. Por tanto si por ej. nuestros parámetros son p1∈[0,10],p2∈[20,40] yp3∈[5,25] el rectángulo o espacio de búsqueda será como el de la Figura 4.1. Una vez tenemos el rectángulo estudiamos dos diferentes maneras de implementar 4.2. PASO 1 - DIVISIÓN DE LAS CELDAS 31 la partición del espacio de búsqueda en subrectángulos: la partición fija y la partición dinámica. La necesidad de estudiar una alternativa a la partición fija es reducir la carga de cálculos que se deben realizar para la clasificación de las celdas: al particionar el espacio Psiempre en nceldas, el coste computacional de la partición aumenta significativamente . La partición dinámica propone una solución a la sobrecarga de cálculos al ir dividiendo las celdas dependiendo de los resultados del oráculo para todas sus muestras. De esta manera, se logra disminuir la sobrecarga de cálculos y mejorar la eficiencia del proceso de clasificación. 4.2.1. Partición fija Se divide el espacio de parámetros Pen una espacio particionado P′que consiste en hipercubos cerrados alineados con los ejes, y que tienen todos el mismo tamaño. A estas subdivisiones las denominamos celdas. La partición se lleva a cabo a partir de un número de celdas nen que se quiere dividir el espacio P. Dado este número y el número de dimensiones dde P, calculamos el número de particiones kque tendrá cada eje del rectángulo a través de la fórmula: k=l10log10(n) dm(4.3) donde ktendrá el mismo valor para cada eje. Podemos observar que el número total de subrectángulos que se particionarán en el espacio Pserá una aproximación al número de celdas establecido por el usuario, ya que el número de celdas total será el exponente de kelevado al número de dimensiones de P. Esto es necesario ya que se desea hacer una partición del espacio Plo más uniforme posible, evitando que algunas celdas puedan estar sobre-representadas o sub-representadas. nceldas =kd(4.4) Una vez tenemos el número de particiones kpara los ejes, se realiza la partición del rectángulo en nceldas. Para el ej. anterior el nceldas inicial es 55 por lo que k= l10log10(55) 3m=⇒k= 4, por tanto nceldas se actualiza a nceldas = 43=⇒nceldas = 64 y quedaría un conjunto de subrectángulos como el de la Figura 4.2. 38CAPÍTULO 4. ALGORITMO DE MINERÍA DE PROPIEDADES STL PARAMÉTRICAS Figura 4.6: Ejemplo de ResultSet con su región de aceptación y de rechazo usando partición fija 4.3. PASO 2 - ENCONTRAR LA REGIÓN DE ACEPTACIÓN 39 Figura 4.7: Región de aceptación(izq) y de rechazo(dcha) del conjunto de resultados con partición fija Figura 4.8: Región de aceptación(izq) y de rechazo(dcha) del conjunto de resultados con partición dinámica 40CAPÍTULO 4. ALGORITMO DE MINERÍA DE PROPIEDADES STL PARAMÉTRICAS 4.3.1. Uso de paralelización Debido al alto coste computacional que supone encontrar la región de aceptación, implementamos versiones paralelas para su cálculo en las que se mejora significativamente el rendimiento y la velocidad en la creación del conjunto de resultados, especialmente cuando es necesario dividir el espacio de búsqueda Pen un número de celdas elevado. Para ello se ha hecho uso de la librería multiprocessing. Está librería está diseñada para la paralelización de procesos en Python. La librería admite la creación de procesos mediante una API similar al módulo de subprocesos (o threading) y ofrece concurrencia local para poder crear y ejecutar procesos en paralelo con el objetivo de mejorar el rendimiento de aplicaciones que necesitan realizar tareas computacionalmente costosas, como en nuestro caso es encontrar la región de aceptación. La librería utiliza subprocesos para lograr la paralelización: cada uno pertenece a un núcleo de CPU disponible del sistema y tiene su propio espacio de memoria, por lo que cada subproceso puede ejecutarse de manera independiente sin interferir con los otros subprocesos. Esto nos permite reducir el tiempo que conlleva encontrar la región de aceptación al aprovechar al máximo los recursos de la CPU. La clase Pool del módulo multiprocessing proporciona una forma conveniente de distribuir el trabajo en múltiples procesos. Para la partición fija, una vez tenemos el espacio de búsqueda dividido en nceldas, creamos un objeto Pool con nprocesos =número de CPU’s en el equipo. Una vez creado el objeto se envían las tareas a los diferentes procesos usando el método map(), que se encarga de distribuir el trabajo en los procesos disponibles. Después de dividir las tareas para clasificar las celdas en las distintas regiones, se utiliza el método join() para esperar a que se clasifiquen todas las celdas antes de crear el conjunto de resultados. En el caso de la partición dinámica, se sigue un proceso similar: primero se crea el objeto Pool con nprocesos, y luego se utiliza un bucle para verificar si ya se han definido las regiones de aceptación y rechazo necesarias o si se deben seguir dividiendo las celdas. La mejora de rendimiento al aplicar paralelización se puede observar en la Figura 4.9, donde el tiempo de ejecución se mide en segundos y, para este caso particular, la configuración de la máquina es de 4 cores o núcleos de CPU. 4.3. PASO 2 - ENCONTRAR LA REGIÓN DE ACEPTACIÓN 41 Figura 4.9: Ejemplo de coste temporal requerido para encontrar la región de aceptación utilizando paralelización vs el tiempo necesario sin paralelización 42CAPÍTULO 4. ALGORITMO DE MINERÍA DE PROPIEDADES STL PARAMÉTRICAS 4.4. Paso 3 - Elección de los campeones El último paso consiste en elegir los campeones de cada uno de los conjuntos de resultados con respecto al resto de conjuntos de resultados, esto es, elegimos la valoración que maximiza la distancia del dominio de validez de otras clases, que supone el punto más representativo de ese dominio. Para calcular la elección de los campeones implementamos la distancia de Hausdorff. 4.4.1. Distancia de Hausdorff Sean VyQdos subconjuntos del espacio de búsqueda P, la distancia de Hausdorff mide cuan lejos están uno de otro. Se define como la distancia máxima de un punto en uno de los subconjuntos al punto más cercano del otro subconjunto. Dado el espacio de búsqueda Py el par de subconjuntos no vacíos (V, Q)∈P, la distancia entre un punto v∈Vy el subconjunto Qse define como: d(v, Q) = ´ınf{dist(v, q)|q∈Q}(4.5) donde dist(v, q)es la distancia Euclidea entre los 2 puntos. Explicado en palabras, d(v, Q)escoge la menor distancia entre el punto vy el conjunto de puntos del subconjunto Q. Teniendo esto, calculamos la distancia de todos los puntos vdel subconjunto V tal que v∈V, y nos quedamos con aquel punto que maximiza la distancia al subconjunto Q. d(V, Q) = sup{dist(v, Q)|v∈V}(4.6) En otras palabras, distancia de Hausdorff se define como la distancia máxima de un punto en uno de los conjuntos al punto más cercano en el otro conjunto. Un ejemplo gráfico de como se calcula la distancia de Hausdorff entre los subconjuntos VyQlo tenemos en la Figura 4.10. Cabe destacar que la distancia de Hausdorff entre 2 subconjuntos no es simétrica, es decir, el punto en el subconjunto Vque maximiza la distancia al subconjunto 4.4. PASO 3 - ELECCIÓN DE LOS CAMPEONES 43 Figura 4.10: Ejemplo de distancia de Hausdorff entre los conjuntos V y Q Qpuede ser diferente del punto en el subconjunto Qque maximiza la distancia al subconjunto V, esto se debe a que la distancia entre los subconjuntos se mide de manera independiente. La asimetría de la distancia de Hausdorff se puede observar en la Figura 4.10, donde la distancia del conjunto V a Q es mayor a la distancia de Q a V, d(V, Q)> d(Q, V ). 4.4.2. Preparación de datos para el cálculo de la distancia de Hausdorff Una vez obtenemos el Conjunto de resultados oResultSet para cada una de las señales temporales previamente indicadas, procedemos a calcular su “campeón”, es decir, su punto v∈ResultSetVque maximiza la distancia con respecto a los demás conjuntos de resultados. Partiendo de una lista que contiene los ResultSet de cada señal temporal, calculamos para cada uno ellos su campeón en relación a el resto de los conjuntos de resultados. Implementaremos 2 métodos distintos para calcular el campeón, teniendo en cuenta la intersección entre las distintas regiones de aceptación y sin tenerla en cuenta. Primero, comprobamos que el tamaño de los conjuntos no sea 0, ya que supondría que los conjuntos de resultados son nulos ∅, por lo que no existiría campeón para ninguno de ellos. if len (self . yup) == 0 or sum ([ len (rs. yup) for rs in rs_list ]) == 0: return 0, None , None Después, creamos un conjunto que representa todas las celdas pertenecientes a las diferentes regiones de aceptación. Para ellos unimos todas las celdas de los conjuntos de resultados previamente obtenidos, eliminando la repetición de celdas iguales que se encuentran en regiones de aceptación de conjuntos de resultados diferentes. Dos 44CAPÍTULO 4. ALGORITMO DE MINERÍA DE PROPIEDADES STL PARAMÉTRICAS celdas son iguales cuando tienen las mismas dimensiones y pertenecen a la misma región. current_class_green_cells = set( self .yup) other_classes_green_cells = set() other_classes_green_cells_generator = (set(rs.yup ) for rs in rs_list ) other_classes_green_cells = other_classes_green_cells.union(* other_classes_green_cells_generator) Una vez que se han agrupado las celdas, creamos dos conjuntos: uno para almacenar los vértices de las celdas del conjunto de resultados para el que se va a calcular el campeón, y otro conjunto para almacenar los vértices de las celdas del resto de conjuntos de resultados. Después adaptamos los datos para que puedan ser leídos por la función directed_hausdorff y creamos dos nuevas listas, una para el conjunto actual y otra para el resto de conjuntos. Esto se consigue filtrando los puntos que pertenecen a diferentes conjuntos, de manera que la primera lista solo contiene los puntos que pertenecen exclusivamente a el conjunto estudiado actualmente y la otra solo contiene los puntos que pertenecen exclusivamente a el resto de conjuntos. current_class = self.vertices_yup() other_classes = set() other_classes_generator = ( yup . vertices () for yup in other_classes_green_cells) other_classes_generator = ( rs. vertices_yup () for rs in rs_list if rs != self ) other_classes = other_classes . union (* other_classes_generator ) current_class_list = list( current_class ) other_classes_list = list( other_classes ) Es importante tener en cuenta que al eliminar los vértices que pertenecen a ambos conjuntos, es posible que una de las listas quede vacía, por lo que es necesario verificar si las listas resultantes tienen elementos antes de continuar. if len ( current_class_list ) == 0 or len( other_classes_list ) == 0: return 0, None , None 4.4. PASO 3 - ELECCIÓN DE LOS CAMPEONES 45 4.4.3. Selección de campeones según la distancia de Hausdorff Por último calculamos los campeones haciendo uso de la función directed_hausdorff de la biblioteca scipy, que se encarga de calcular la distancia de Hausdorff entre dos conjuntos de puntos. La biblioteca scipy, es una biblioteca ampliamente utilizada que proporciona módulos para optimización, álgebra lineal, integración... La función acepta las dos listas de vértices del conjunto estudiado y la unión del resto de conjuntos y devuelve la distancia de Hausdorff junto con los puntos de ambos conjuntos que marcan la distancia. distance , current_index , index_other_classes = dhf ( current_class_list , other_classes_list ) otherdhf = dhf ( other_classes_list , current_class_list ) Es importante remarcar que, la distancia de Hausdorff entre dos conjuntos de puntos no es simétrica, por lo que es necesario calcular la distancia del conjunto actual respecto a la unión del resto de conjuntos y la distancia de este último respecto al conjunto actual, quedándonos con la que devuelva la mayor distancia, código 4.7. if otherdhf [0] > distance : distance , current_index , index_other_classes = otherdhf [0] , otherdhf [2] , otherdhf [1] Una vez obtenida la máxima distancia, la devolvemos junto con el par de puntos devueltos por la función de scipy, uno perteneciente a cada conjunto, que la componen como resultado. A continuación mostraremos el resultado de calcular los campeones gráficamente, para ello usaremos el espacio de búsqueda de la Figura 4.1, con nceldas = 200 para la partición fija y mostraremos los campeones para ambos tipos de particiones, Figura 4.11 y Figura 4.12. vertex_champion = current_class_list [ current_index ] self . champion = vertex_champion return distance , vertex_champion , other_classes_list [ index_other_classes] d(V, Q) = m´ax (sup{dist(v, Q)|v∈V},sup{dist(q, V )|q∈Q})(4.7) 46CAPÍTULO 4. ALGORITMO DE MINERÍA DE PROPIEDADES STL PARAMÉTRICAS Figura 4.11: Elección de campeones para partición fija, dados los dos conjuntos de resultados muestra los puntos que maximizan la distancia entre las regiones de aceptación 4.4. PASO 3 - ELECCIÓN DE LOS CAMPEONES 47 Figura 4.12: Elección de campeones para partición dinámica, dados los dos conjuntos de resultados muestra los puntos que maximizan la distancia entre las regiones de aceptación 54 CAPÍTULO 5. ACTUALIZACIÓN DE LA INTERFAZ GRÁFICA Figura 5.4: Ejemplo de interfaz gráfica un vez añadidos los cambios 5.2. BIBLIOTECAS UTILIZADAS 55 Matplotlib Pandas Seaborn json 5.2.1. PyQt5 La biblioteca PyQt5 está basada en la biblioteca gráfica Qt y sirve para realizar el diseño gráfico de la ventana principal de la aplicación desde Python. En nuestro caso, partiendo de la interfaz del trabajo anterior y respetando su diseño, hemos usado la biblioteca PyQt5 para añadir las nuevas opciones en el cuadro Options y añadido la Barra de Menú que proporciona una estructura organizada las funciones añadidas(Crear proyecto, Guardar, Abrir, ...). Para aprovechar al máximo PyQt5, utilizamos la herramienta Qt Designer. Esta herramienta nos permitió actualizar el diseño inicial de la interfaz, sobre la cual posteriormente anclamos manualmente las funcionalidades a los botones correspondientes. De esta manera, pudimos agilizar el proceso de diseño y desarrollo de la interfaz. 5.2.2. MatPlotLib La biblioteca MatPlotLib es una biblioteca ampliamente utilizada en Python para la generación de gráficos y visualización de datos. Proporciona una amplia gama de funciones y herramientas para crear diversos tipos de gráficos, desde simples gráficos de líneas y barras hasta gráficos más complejos. Se utiliza para generar los gráficos resultantes de las propiedades STL paramétricas, para representar las distintas señales temporales y para representar los espacios de búsqueda y los conjuntos de resultados. 5.2.3. Pandas La biblioteca Pandas es una biblioteca de Python ampliamente utilizada para el análisis y manipulación de datos. Proporciona estructuras de datos eficientes y fáciles de usar, así como herramientas para el procesamiento, limpieza y análisis de datos de manera rápida y eficiente. Utilizando la biblioteca Pandas, llevamos a cabo la transformación y almacenamiento de nuestras señales en una estructura de datos conocida como DataFrame. Este DataFrame nos permite manipular y analizar fácilmente los 56 CAPÍTULO 5. ACTUALIZACIÓN DE LA INTERFAZ GRÁFICA datos de las señales. Luego, utilizamos esta estructura de datos como entrada para los métodos de visualización gráfica de la señal, haciendo uso de la biblioteca Seaborn yMatPlotLib. 5.2.4. Seaborn La biblioteca Seaborn es una biblioteca de visualización basada en MatplotLib. Seaborn proporciona una interfaz de alto nivel con capacidad para generar visualizaciones sofisticadas. El uso que le damos en el proyecto es tanto estético como funcional. Lo utilizamos para dibujar las señales temporales a partir de los datos importados (parte estética y funcional), que facilita la visualización y la comprensión de los datos. Al poder representar las señales temporales gráficamente, se puede obtener una visión general de cómo cambia el comportamiento de la señal a lo largo del tiempo. También fue usada para la fase de experimentación para generar matrices de confusión, nos fue muy útil para evaluar el rendimiento del modelo y la calidad de las predicciones. 5.2.5. json La biblioteca json es una herramienta estándar en Python que proporciona funciones para manipular y trabajar con datos en formatos JSON (JavaScript Object Notation). Usamos este formato de datos para guardar las configuraciones de nuestro proyecto. La elección de utilizar json para guardar las configuraciones se basa en su naturaleza simple e intuitiva para el manejo de datos. 5.3. Guía de uso En esta sección, nos centraremos en explicar las partes más relevantes e interactivas de la interfaz gráfica de usuario. Después de haber instalado las dependencias de ParetoLib utilizando los scripts proporcionados por la biblioteca, podrás iniciar la interfaz gráfica ejecutando el siguiente comando desde el directorio principal del código del repositorio: 1( ParetoLibEnv ) user@pc :~ $ParetoLib / GUI /GUI .py Figura 5.5: Inicio de la interfaz gráfica de usuario de ParetoLib 5.3. GUÍA DE USO 57 Figura 5.6: Muestra de la parte de la interfaz donde se seleccionan los datos de entrada Una vez abierta la ventana, veremos los botones (Figura 5.6) y las opciones principales (Figura 5.7): STL specification: Permite seleccionar un archivo .stl que contiene una fórmula en STL. Al seleccionar el archivo, la descripción de la fórmula se muestra en una caja inferior en modo de solo lectura, es decir, no se puede modificar. Input signal: Permite seleccionar un archivo .csv que contiene la definición de la señal temporal. Una vez seleccionado aparece una representación gráfica de la señal en la caja “Signal” de la ventana. Parameters: Permite seleccionar un archivo .param que contiene los parámetros a estudiar y que se utilizan en la fórmula del archivo .stl seleccionado. Al elegir un archivo .param, aparecerán los parámetros seleccionados sin valor en una caja más abajo donde se podrán completar los intervalos de búsqueda (valor mínimo y máximo) para uno de los parámetros. Estos intervalos serán utilizados por la biblioteca ParetoLib para realizar el proceso de aprendizaje. (Figura 5.8) Parametric STL: : Permite seleccionar si evaluaremos una consulta STL paramétrica o no: en nuestro caso las clasificaciones siempre las haremos con fórmulas paramétricas. 58 CAPÍTULO 5. ACTUALIZACIÓN DE LA INTERFAZ GRÁFICA Figura 5.7: Muestra de la parte de la interfaz donde se seleccionan las opciones del algoritmo de minado Mining method: Permite seleccionar el método de minado para la clasificación de la señal temporal seleccionada, las opciones son “BBMJ19”, “BDMJ20” que pertenecen a los trabajos de años anteriores y “BMNN22” que corresponde con nuestro algoritmo de minado. Type Search: Permite seleccionar el tipo de búsqueda, que puede ser secuencial o paralela. Opt Level: Permite seleccionar el tipo de partición que se realizará sobre el espacio de búsqueda. Run: Permite ejecutar la consulta. Para llevar a cabo la consulta, se requieren los tres archivos de entrada mencionados anteriormente y los valores seleccionados de las opciones. Al hacer clic en este botón, se recopilan las rutas de los archivos de entrada, el rango de valores numéricos de los parámetros. Como resultado, se obtendrá el conjunto de resultados con las regiones clasificadas como falsas o verdaderas según los parámetros. A parte de poder ejecutar el algoritmo de minado para obtener el resultado con las regiones de aceptación y de rechazo, también es posible guardar la configuración: ficheros, parámetros y opciones seleccionadas, para poder hacer pruebas más adelante usando la misma configuración. Para guardar una configuración, se deben seguir los siguientes pasos: Crear el proyecto: Haz clic en el botón Create... New Project y proporciona un nombre para la configuración. Esto creará un nuevo proyecto en el que se 5.3. GUÍA DE USO 59 Figura 5.8: Muestra de la parte de la interfaz donde se seleccionan especifican los intervalos de los parámetros podrán guardar las opciones y ajustes. Seleccionar ficheros y parámetros: Dentro del proyecto, elige los archivos y parámetros relevantes que deseas guardar como parte de la configuración. Configurar opciones: Selecciona las opciones adicionales que deseas guardar junto con la configuración. Guardar el proyecto: Haz clic en "Guardar Proyecto... Guardar"para guardar la configuración. Esto almacenará todas las opciones, archivos y parámetros seleccionados en el archivo de configuración creado. Una vez que la configuración esté guardada, podrás volver a abrirla y cargar las opciones en el futuro mediante el botón Open... Load Project. Esto te permitirá recuperar la configuración guardada y continuar trabajando con las mismas opciones y ajustes previos. 60 Capítulo 6 Detección de ataques en Smart Grids Presentados en la sección anterior los algoritmos que hemos usado para el minado de propiedades STL proporcionados por los oráculos de ParetoLib y STLEval, procedemos a mostrar los resultados de los diversos experimentos que hemos realizado usando esas herramientas para distinguir el comportamiento normal de cualquier manipulación (algo que llamaremos comportamiento de ataque). Para ello, usaremos los datos de consumo eléctrico de diversos usuarios proporcionados por la base de datos de ISSDA-CER (ver [10]). Finalmente, realizaremos una discusión de los resultados obtenidos, de si estos mejoran o no los de otras aproximaciones más convencionales usando otros métodos de aprendizaje supervisado como k-NN o DBSCAN (ver [7]) 6.1. Base de datos Para la experimentación hemos usado dos conjuntos de datos, ambos registrados por la Comisión de Regulación de Energía Irlanda (ver [10]), que se encarga de regular los datos provenientes de los medidores avanzados de los sectores de electricidad y gas natural de Irlanda. Los consumos registrados del conjunto de datos de electricidad están categorizados como residenciales, pequeñas y medianas empresas y no clasificados, y consideran un período de 76 semanas de registro para 6445 medidores avanzados. En el caso de los consumos de gas natural se dividen en grupos de prueba y control, y considera un período de 78 semanas de registro para 1576 medidores avanzados. La frecuencia de las lecturas es la misma para ambos conjuntos y es cada media hora, por lo que se 61 62 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS contabilizan un total de 48 mediciones de consumo por día. 6.2. Preprocesado de los datos Originalmente, los datos están en un único fichero dividido en 3 columnas: Una para el ID de los usuario, otra para el momento en el tiempo en el que se midió el consumo y una tercera para el consumo propiamente dicho. Antes de comenzar los experimentos, tuvimos que depurar con el fin de adaptar estos datos al formato de series temporales soportado por ParetoLib para su posterior clasificación. Hicimos los siguientes cambios: Quitar la columna del ID de usuario: Durante los experimentos, solo necesitamos el ID del usuario para identificar el día con el que estamos trabajando y no dentro de los propios datos, donde solamente necesitamos la serie temporal de pares (ti, xi). Dividir los datos en días: Fragmentamos los ficheros de datos (que normalmente abarcaban los datos de todos los usuarios durante varias semanas) en días individuales para un usuario individual. Así, en lugar de tener un solo fichero con más de un millón de instantes de tiempo en los que se leyó el consumo, ahora tenemos varios ficheros separados donde que cada uno corresponde a un día y un usuario particular. División del dataset en días de entrenamiento y de test: Dividimos el dataset en una sección de entrenamiento y otra de test. En esta división original, dividimos el conjunto de datos en 80 % para entrenamiento y el 20% restante para test. 6.3. Ataques: Definición y tipos Asumiendo que los datos provenientes de la Comisión de Regulación de Energía Irlanda no han sido afectados por ataques integrados, hemos usado estos conjuntos de datos como un escenario válido para la experimentación, y lo denominaremos el comportamiento normal. Con el objetivo de detectar comportamientos anómalos que puedan indicar manipulaciones de la instalación, hemos manipulado estos datos y creado ficheros nuevos donde guardar estos nuevos datos, a los que llamaremos ataques. Los tipos de ataque que distinguimos son los siguientes (la definición de todos ellos proviene de [7]) 6.3. ATAQUES: DEFINICIÓN Y TIPOS 63 Los escenarios de ataque considerados son los siguientes: 1. False Data Injection (FDIx): Este ataque cambia cada medición de consumo del medidor por un porcentaje fijo de la medición x% : x∈N. Dependiendo del valor de x, el beneficiado es el consumidor (si x < 100) o el administrador (si x > 100). Hemos considerado varios escenarios de ataque de este tipo, tanto los que benefician al consumidor (ver 6.11) como los que benefician el administrador (ver 6.12). 2. Familia Average: Los datos son manipulados reemplazando cada medición por el valor c∗x, donde x es un valor inicial predeterminado y relacionado con una media aritmética y c∈[1−a, 1+a]elegido al azar para un a prefijado. Nosotros hemos realizado los experimentos fijando a= 1. Dependiendo del valor de x que se coja, estos ataques reciben un nombre diferente: Minimal avarage attack (MinAvg): x es la media mínima de todas las semanas del proceso de entrenamiento (ver 6.22). Average attack (Avg): x es el valor de la semana en la que se encuentra la medición a alterar (ver 6.21). 3. Random Scale Attack (RSA[a,b]): Los datos de un escenario RSA son manipulados reescalando cada consumo por la realización por una constante r∈[a, b], donde 0< a < b elegida al azar (ver 6.31). 4. Ataque de intercambio (Swap): Se parte del supuesto de que este ataque se basa en un acuerdo de tiempo de uso, en el cual el precio de la energía varía en función de los periodos de alta y baja demanda, que llamaremos picos y valles de consumo. El ataque consiste en intercambiar los consumos de energía entre los 2 períodos de consumo y valle, 6.32. 70 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS eran mejores para detectar cada tipo de ataque. Detección de errores: Al realizar las pruebas con único usuario, hemos podido depurar errores tanto en las propiedades STL como en el algoritmo BMNN22 de ParetoLib Mejorar consistencia: Como hemos mencionado, varios de los elementos del algoritmo de elaboración de las regiones de aceptación y elección de los campeones son probabilísticos y, por lo tanto, necesitamos una manera de hacer los experimentos más consistentes Adjuntamos a continuación una muestra del consumo del usuario 1143 en dos días distintos, ya que nos será de utilidad en el futuro Figura 6.4: Ejemplos de dos días de consumo normal del usuario 1143 Elección del espacio de búsqueda para ejecutar los experimentos Varias de las preguntas a las que tenemos que intentar dar respuesta durante la realización de los experimentos están relacionadas con el espacio de búsqueda. Aquí realizamos una pequeña lista con las soluciones que hemos propuesto ¿Cuántas dimensiones debe tener el espacio de búsqueda? En general, estamos buscando un número de dimensiones con el que podamos 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 71 modelar la mayor cantidad de información posible para poder así obtener campeones más significativos. Por otro lado el algoritmo usado para la elección de los campeones (con o sin intersección de regiones de aceptación) tiene asociado un coste computacional muy alto que escala mucho según aumentan las dimensiones incluso con las mejoras provenientes del uso de la aproximación probabilística del cálculo de la Distancia Hausdorff de la biblioteca scipy de Python. Tomando todo lo anterior en consideración y, añadiendo además que nos gustaría mostrar gráficamente los resultados que hemos ido obteniendo (y también los diferentes campeones y regiones de aceptación), hemos decidido usar un espacio de búsqueda de 3 dimensiones para todos los experimentos, identificadas como p1, p2, p3. Por tanto, el espacio de búsqueda para los experimentos será un cubo de R3de la forma C= [a, b]×[c, d]×[e, f] : p1∈[a, b], p2∈[c, d], p3∈[e, f] ¿Podemos usar el mismo espacio de búsqueda para todos los experimentos? Idealmente, deberíamos poder usar el mismo espacio de búsqueda para todos los experimentos. Esto es bastante más complicado de lo que podría parecer a primera vista (ver consumo de un día del usuario 1143 6.4.1) teniendo en cuenta la gran variabilidad en los consumos. Queremos, por lo tanto, encontrar un espacio de búsqueda en el que podamos encontrar una región de aceptación lo suficientemente grande como para poder encontrar un campeón representativo, pero no tan grande como para que no se introduzca ruido en el sistema. Nosotros hemos optado por realizar una exploración para estimar dónde se encuentra el intervalo ideal para cada propiedad. Clasificación de experimentos Hemos realizado varias aproximaciones para realizar la identificación de cada uno de los ataques. Después de examinar los resultados de cada uno de los tests realizados, haremos una pequeña discusión para elegir la mejor aproximación para cada ataque. Nuestros criterios para elegir la mejor aproximación van a ser los siguientes: Tasa de aciertos global alta y, en caso de no poder conseguirse, recall alto: Idealmente, preferimos separar completamente bien los ataques y que no halla fallos pero, en caso de haberlos, priorizaremos aquellas aproximaciones en las que 72 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS lo hayamos hecho ’demasiado bien’ (es decir, aquellas aproximaciones con más falsos positivos que falsos negativos) y en las que el error sea una sobreestimación Estabilidad a lo largo de los espacios de búsqueda: El propósito final es encontrar un espacio de búsqueda ideal donde los ataques puedan ser identificados. Para encontrar dicho intervalo, nos interesan aproximaciones cuya precisión no varíe en exceso a lo largo de los diversos espacios de búsqueda Buen clasificador para múltiples ataques: Otro de los propósitos finales es encontrar una propiedad “panacea"que sirva como clasificador de todos los ataques. Después de discutir todas las aproximaciones, veremos si existe alguna propiedad que sea buen clasificador para más ataques Parámetros para la realización de los experimentos Hemos optado finalmente por uniformizar los parámetros para la realización de los experimentos (a saber, días de entrenamiento y test y los espacios de búsqueda en los que hacer la exploración). Estos parámetros son los siguientes: Días de entrenamiento: 40 Días de test: 10 Intervalos: p1∈[0,47] yp2, p3∈[0, x] : x∈ {10,20,30,40,50,60,70,80,90,100} Finalmente, vemos los diferentes ataques y las aproximaciones tomadas 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 73 6.4.2. Swap Figura 6.5: Ejemplos de dos días de consumo normal del usuario frente al consumo manipulado mediante Swap Como indicamos en la sección anterior, el ataque de intercambio (o Swap, como nos referiremos a él a partir de ahora), supone un sistema de franjas horarias. De esta manera, existirá un intervalo del día en el que el precio del consumo será más barato al que llamaremos ’franja valle’ e, inversamente, existirá un intervalo en el que el consumo será más caro al que llamaremos ’franja pico’. Durante el desarrollo de nuestros experimentos con Swap hemos supuesto una sola franja valle desde las 00:00 hasta las 09:00 y una sola franja pico desde las 09:00 hasta las 00:00. Primera aproximación - Acotación simple Esta es nuestra primera aproximación a detectar este ataque. La propiedad STL usada es la siguiente: ϕ:= Zp1 0 x0≤p2∧Z47 p1 x0≤p3(6.1) Figura 6.6: Ver código STL en A.1.1 Explicada en palabras, esta propiedad separa las mediciones de un día en dos 74 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS intervalos, obtiene el valor acumulado de cada uno de dichos intervalos e intenta acotar ambos valores. Esta propiedad es el primer intento de explotar el hecho de que para Swap el valor acumulado de uno de los intervalos será mucho mayor que el del otro (ver figura 6.4.1). Los experimentos se han realizado con los siguientes parámetros: Veamos los resultados de los experimentos y tomaremos el mejor con y sin intersección de regiones de aceptación y a mostrar los dos mejores experimentos realizados. Figura 6.7: Estudio de los experimentos en diversos intervalos sin la intersección de regiones de aceptación (izquierda) y con ella (derecha) Las mejores soluciones se obtienen en diferentes intervalos dependiendo de si existe intersección entre regiones de aceptación o no, lo que nos sugiere que en ningún caso se está escogiendo el mismo campeón. Escogemos ahora los mejores espacios de búsqueda sin tener en cuenta la intersección entre regiones de aceptación y teniéndola en cuenta. Sin intersección de regiones de aceptación escogiendo como espacios de búsqueda CSwap = [0,47] ×[0,100] ×[0,100] para el caso en el que no tenemos en cuenta la intersección entre regiones de aceptación. Ver resultados del experimento en B.1.1. Con intersección de regiones de aceptación Escogemos C′ Swap = [0,47] × [0,50] ×[0,50] teniendo en cuenta la intersección entre regiones de aceptación. Ver resultados del experimento en B.1.1. Observamos que los resultados arrojados por esta propiedad son, en general, bastante mediocres. Es bastante mejor dejar fuera la intersección entre regiones de acep- 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 75 tación e, incluso en este caso, las soluciones encontradas son comparativamente no demasiado buenas (con respecto al resto de aproximaciones que veremos más adelante) y, además, los espacios de búsqueda en los que han sido encontradas son comparativamente mucho más grandes que el rango de valores de la señal con la que estamos trabajando, haciendo a esta propiedad que arroja resultados mediocres y que es computacionalmente costosa. Esto nos lleva entonces a la pregunta, ¿por qué la estamos mostrando? Porque nos sirve para introducir las herramientas que usaremos en aproximaciones sucesivas para separar el comportamiento normal del ataque Swap (la división de la señal en dos intervalos diferenciados, las cotas, etc.). Segunda aproximación - Acotación doble Traducimos matemáticamente esta propiedad como: ϕ:= Zp1 0 x0≥p2⇒Z47 p1 x0≤p3(6.2) Figura 6.8: Ver código en A.1.2 Con esta propiedad empieza a tomar forma la idea que queremos perseguir para diferenciar este ataque particular. Diferenciamos la señal en dos intervalos y calculamos la suma de los consumos en cada uno de ellos. Por la definición del ataque Swap establecida anteriormente, sabemos que el consumo durante la noche será, aparentemente, mucho mayor que durante el día. Es a partir de esta suposición que realizamos las acotaciones apropiadas. Los parámetros con los que hemos realizado los experimentos no varían con respecto a la aproximación anterior, es decir: Como en la aproximación anterior, procedemos a mostrar los resultados de realizar el mismo experimento a lo largo de diferentes espacios de búsquedas: 76 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Figura 6.9: Estudio de los experimentos en diversos intervalos sin la intersección de regiones de aceptación (izquierda) y con ella (derecha) Aunque más polarizadas, vemos que las soluciones son mucho mejores en general. Procedemos a mostrar ahora los resultados de los dos mejores experimentos Sin intersección de regiones de aceptación Para este caso particular, tomaremos como mejor experimento el recall más alto (pues la tasa global de aciertos se mantiene más o menos uniforme) y, por tanto, el espacio de búsqueda será el conjunto CSwap = [0,47] ×[0,20] ×[0,20]. Ver resultados del experimento en B.1.2. Con intersección de regiones de aceptación Si observamos los resultados obtenidos de realizar la exploración en busca del espacio de búsqueda mostrada anteriormente, vemos un patrón ligeramente extraño, y es que los recalls más altos se obtienen cuando la tasa global de aciertos es más baja. Es por esta razón por la que vamos a priorizar la tasa de aciertos global más alta y vamos a tomar ésta como el mejor experimento. Es decir, nuestro espacio de búsqueda es el conjunto CSwap = [0,47] ×[0,80] ×[0,80] (cabe decir que podríamos haber usado también C= [0,47] ×[0,10] ×[0,10] yC= [0,47] ×[0,30] ×[0,30]). Ver resultados del experimento en B.1.2. En conclusión, podemos observar que los resultados arrojados por esta propiedad son bastante mejores que los de la aproximación anterior (ver 6.4.2) pero sigue habiendo problemas, especialmente dos: No obtenemos resultados uniformes a lo largo de los espacios de búsqueda. 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 77 De hecho, los resultados son bastante susceptibles de cambiar drásticamente dependiendo del espacio de búsqueda usado. Esto no nos interesa porque, a la hora de elegir un espacio de búsqueda común a todos los ataques más adelante, no podemos tener la fiabilidad de que esta aproximación vaya a arrojar buenos resultados. Podemos tener problemas a la hora de trabajar con usuarios con hábitos “anómalos". Esta segunda aproximación solo se fija en que el consumo total en el primer tramo del día (por la noche y de madrugada) sea mayor que en el segundo, sin importar mucho más. Esto quiere decir que el comportamiento normal de un usuario que trabaje de noche por ejemplo se puede confundir con una manipulación. Nuestro siguiente objetivo ahora es mantener o mejorar la calidad de las soluciones obtenidas en esta aproximación mientras aumentamos la estabilidad de dichas soluciones a lo largo de los espacios de búsqueda. Tercera aproximación - Acotación doble refinada Matemáticamente, la traducción literal de esta propiedad sería ϕ:= Zp1 0 x0≥p2⇒Z47 p1 x0≤p3∧Z47 p1 x0≤p3⇒Zp1 0 x0≥p2(6.3) Sin embargo, para aquellos con ojo lógico seguramente será evidente que existe una manera equivalente pero mucho más sencilla de reescribir la ecuación 6.3 ϕ:= Zp1 0 x0≥p2⇔Z47 p1 x0≤p3(6.4) Figura 6.10: Ver resultados en A.1.3 Esta es la primera doble implicación que hemos utilizado pero no será la última así que necesita una explicación más larga de la de aproximaciones anteriores. Inme- 78 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS diantamente surge una pregunta muy evidente ¿Por qué usar la expresión 6.3 cuando 6.4 es equivalente y mucho menos enrevesada de escribir? La respuesta a esta pregunta se reduce a limitaciones de StlEval. Solo podemos usar operadores lógicos que StlEval pueda procesar y, a día de hoy, éstos son ∧,∨,¬,⇒así que, en vez de hacer directamente la doble implicación, debemos construirla nosotros usando equivalencias lógicas por el momento. Esto es algo que veremos más abajo también para el caso de la construcción de una disyunción exclusiva ⊕. Explicamos ahora la utilidad que hemos encontrado en el operador ⇔. En varias ocasiones, el problema que nos hemos encontrado es que sabemos cómo modelar bien el comportamiento de un ataque pero dicha modelización no es buena a la hora de detectar el comportamiento normal del usuario. La doble implicación ha sido una herramienta muy útil a este respecto por sus características. Como la proposición global solo será verdadera en el caso de que los dos predicados sean ambos verdaderos o ambos falsos, hemos podido modelar bien el comportamiento normal del usuario (en el caso particular de esta aproximación, si ambos predicados son falsos y, por lo tanto, el consumo es más o menos uniforme a lo largo del día) y el comportamiento del ataque Swap (si ambos predicados son verdaderos). Veremos más adelante que hemos explotado este tipo de razonamiento en varias ocasiones. Ahora, sin embargo, vemos los resultados de los experimentos a lo largo de diferentes espacios de búsqueda: Figura 6.11: Estudio de los experimentos en diversos intervalos sin la intersección de regiones de aceptación (izquierda) y con ella (derecha) Observamos resultados que, en general, son ligeramente mejores que los de la apro- 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 79 ximación anterior además de más uniformes, sobretodo en los espacios de búsqueda pequeños (donde nos interesa que haya mejores resultados porque reduce el coste computacional de la búsqueda). Vamos a mostrar ahora los dos mejores experimentos, empezando por quitar la intersección de regiones de aceptación. Sin intersección de regiones de aceptación Si analizamos los resultados obtenidos al despreciar la intersección de regiones de aceptación, vemos que la tasa global de aciertos más alta proviene de un experimento con un recall perfecto de 1 así que, en este caso, la decisión del mejor experimento es fácil. Nuestro espacio de búsqueda es CSwap = [0,47] ×[0,40] ×[0,40]. Ver resultados del experimento en B.1.3. Con intersección de regiones de aceptación De nuevo la decisión es fácil ya que vemos que la tasa global de aciertos más alta proviene de un experimento con un recall más alto. Nuestro espacio de búsqueda es CSwap = [0,47] ×[0,20] ×[0,20]. Ver resultados del experimento en B.1.3. Observamos resultados mucho mejores (sobretodo añadiendo la intersección de regiones de aceptación) en general. Además, éstos son más uniformes a lo largo del espacio de búsqueda en general. Esto es porque las regiones de aceptación están más claramente diferenciadas gracias a la doble implicación. Sin embargo, hay un problema heredado de la aproximación anterior que aún no hemos resuelto. Esta propiedad sigue sin discriminar entre un aumento normal del consumo durante la noche por parte de un usuario y un consumo anormal, por lo que un usuario con hábitos anómalos (un trabajador nocturno) podría seguir causando problemas a la hora de separar regiones de aceptación. Ofrecemos ahora nuestro intento de solucionar este problema manteniendo la calidad de las soluciones. Cuarta aproximación - Solución parasitaria Esta es la propiedad con la traducción matemática más complicada: ϕ:= G[0,p2](∆x0≤0) ⇒Zp1 0 x0≥Z47 p1 x0(6.5) Figura 6.12: Ver código STL en A.1.4 86 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Figura 6.16: Estudio de los experimentos en diversos intervalos teniendo en cuenta la intersección entre regiones de aceptación para Avg (izquierda), MinAvg (centro) y MaxAvg (derecha) Aunque lo pueda parecer, no hemos copiado por error la misma imagen tres veces. Esta propiedad arroja los mismos resultados, con los mismos campeones sea cual sea el miembro de la familia Average que estemos usando en cualquier momento. Además, los resultados son bastante uniformes. Sin embargo, esta aproximación deja de ser buena en cuanto nos fijamos en los resultados en si. Los resultados son uniformes, pero muy mediocres. Por otro lado, no tenemos resultados suprimiendo las regiones de aceptación, lo que nos indica que una de las regiones de aceptación de uno de los ataques es un subconjunto de la otra. Aún así, mostramos los resultados del mejor experimento. Aunque es un poco irrelevante el espacio de búsqueda que usemos, vamos a utilizar C= [0,47] ×[0,10] ×[0,10]. Ver resultados de los experimentos en B.2.1. Segunda aproximación - Diferencia de acumulaciones Una vez más, ofrecemos la traducción matemática literal de la propiedad: ϕ:= Zp1 2 0 x0−Zp1 p1 2 x0 ≤p2!∨ Zp1 2 0 x0−Zp1 p1 2 x0 ≥p3!!∧ ¬ Zp1 2 0 x0−Zp1 p1 2 x0 ≤p2!∨ ¬ Zp1 2 0 x0−Zp1 p1 2 x0 ≥p3!! (6.7) De nuevo un ojo lógico matemático se habrá dado cuenta de que esto se puede simplificar a lo siguiente: 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 87 ϕ:= Zp1 2 0 x0−Zp1 p1 2 x0 ≤p2!⊕ Zp1 2 0 x0−Zp1 p1 2 x0 ≥p3!(6.8) Figura 6.17: Ver código STL en A.2.2 Este es el otro método que hemos usado para separar el comportamiento normal del comportamiento de varios ataques, una disyunción exclusiva (operación XOR y denotada como ⊕). Una vez más, tenemos que recurrir a construcciones algo enrevesadas y equivalencias lógicas como 6.7 dado que StlEval no tiene incorporado un operador ⊕. Esta aproximación toma la noción de uniformidad de los intervalos producidos por Avg e intenta reinterpretarla. Vimos más arriba en el ejemplo de ataques Average (ver 6.14) que el rango de valores con el que estamos trabajando es pequeño. Esta aproximación intenta solventar el problema del tamaño del rango de valores trabajando con acumulaciones de los mismos. Veamos ahora el estudio en los espacios de búsqueda. Figura 6.18: Estudio de los experimentos en diversos espacios de búsqueda para Avg sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 88 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Figura 6.19: Estudio de los experimentos en diversos espacios de búsqueda para MinAvg sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Figura 6.20: Estudio de los experimentos en diversos espacios de búsqueda para MaxAvg sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Observamos que, para esta aproximación, obtenemos resultados muy distintos dependiendo de qué ataque estemos utilizando. Vemos también que excepto para el caso de MinAvg, que sigue conservando los resultados mediocres, mejoran ligeramente. Co- 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 89 menzamos a ver recalls de un valor relativamente alto y, en general, esta aproximación es mejor aunque está lejos de ser óptima. Mostramos ahora los mejores resultados para cada uno de los ataques, dependiendo de si tenemos en cuenta la intersección entre regiones de aceptación o no. Sin intersección de regiones de aceptación Echando un vistazo a las gráficas mostradas anteriormente, se han obtenido resultados muy dispares dependiendo del ataque que hemos tenido en cuenta. Es por esto que hemos escogido un espacio de búsqueda diferente para cada ataque. Concretamente, CAvg = [0,47] ×[0,40] ×[0,40] para Avg, CMinAvg = [0,47] ×[0,10] ×[0,10] para MinAvg y CMaxAvg = [0,47] × [0,30] ×[0,30] para MaxAvg. Ver resultados de los experimentos en B.2.2. Con intersección de regiones de aceptación Una vez más vemos que los resultados son muy dispares y debemos escoger diferentes espacios de búsqueda para cada uno de los ataques. De este modo, escogemos CAvg = [0,47]×[0,30]×[0,30] para Avg, CMinAvg = [0,47] ×[0,20] ×[0,20] para MinAvg y CMaxAvg = [0,47] ×[0,40] ×[0,40] para MaxAvg. Ver resultados de los experimentos en B.2.2. Aunque los resultados son ligeramente mejores que los de la aproximación anterior aunque siguen siendo bastante mediocres, sobretodo en el caso de MinAvg, que no ha mejorado prácticamente nada. Sin embargo, consideramos que ésta sigue siendo una buena aproximación a la hora de describir la forma de la señal generada por los ataques de la familia Average. Tercera aproximación - Combinando las dos anteriores Esta propiedad podemos traducirla matemáticamente como: ϕ:= Zp1 2 0 x0−Zp1 p1 2 x0 ≤p2!⇒m´ax [0,p1]x0−m´ın [0,p1] x0≤p3(6.9) Figura 6.21: Ver código STL en A.2.3 Teniendo en cuenta las dos aproximaciones anteriores, esta que presentamos ahora no necesita mucha más presentación. Estamos intentando combinar las dos aproximaciones anteriores para intentar mejorar los resultados obtenidos. Como veremos 90 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS más adelante, la mejora de resultados vuelve a ser mínima con respecto a la propiedad anterior, aunque existe. Primero, sin embargo, presentamos los resultados de la investigación a lo largo de varios espacios de búsqueda. Figura 6.22: Estudio de los experimentos en diversos espacios de búsqueda para Avg sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Figura 6.23: Estudio de los experimentos en diversos espacios de búsqueda para MinAvg teniendo en cuenta la intersección entre regiones de aceptación 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 91 Figura 6.24: Estudio de los experimentos en diversos espacios de búsqueda para MaxAvg sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Vemos que volvemos a tener problemas con las regiones de aceptación superpuestas (algo que se puede apreciar por el hecho de que al suprimir la intersección entre regiones obtenemos muchos menos resultados). Presentamos los mejores experimentos, primero suprimiendo la intersección entre regiones de aceptación. Sin intersección entre regiones de aceptación En este caso volvemos a carecer de resultados para MinAvg, mientras que la elección de los espacios de búsqueda para Avg y MaxAvg queda reducida a una sola opción, por lo que no tenemos más elección de espacios de búsqueda que CAvg = [0,47] ×[0,20] ×[0,20] para Avg y CMaxAvg = [0,47] ×[0,10] ×[0,10] para MaxAvg. Ver resultados de los experimentos en B.2.3. Con intersección de regiones de aceptación Si echamos otro vistazo a la investigación de los espacios de búsqueda ofrecida más arriba, está claro que tenemos más espacios donde elegir, aunque los resultados continúan siendo mediocres. Priorizando el recall más alto, escogemos los siguientes espacios de búsqueda: CAvg = [0,47] ×[0,50] ×[0,50] para Avg, CMinAvg = [0,47] ×[0,50] ×[0,50] para MinAvg y CMaxAvg = [0,47] ×[0,20] ×[0,20] para MaxAvg. Ver resultados de los experimentos en B.2.3. 92 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Un vistazo rápido a los resultados nos confirma lo que hemos observado más arriba, y es que esta aproximación, aunque marginalmente mejor que las anteriores, tampoco es del todo buena y es aquí donde queremos hacer un inciso que seguramente pueda parecer obvio. Echando un vistazo a la muestra de la familia Average ofrecida al inicio de esta sección (ver 6.14) y, más concretamente, al día 1 (en la imagen, a la derecha), se puede observar que puede existir comportamiento normal del usuario que, una vez digitalizado, nos da una serie temporal altamente uniforme, por lo que las tres primeras aproximaciones mostradas aquí no explotan tan bien la uniformidad de los ataques de la familia Average como creíamos y que, de hecho, dicha uniformidad puede ser perfectamente normal. Necesitamos entonces buscar otro enfoque bajo el que mirar esta familia de ataques. Cuarta aproximación - Distancias a la media Debido a la complejidad de esta propiedad, vamos a simplificarla un poco. Denotando ⊕como la disyunción lógica exclusiva (operación XOR) y la media de las mediciones en el intervalo [a, b]como µ[a,b]=Rb ax0 b−a+1 : ϕ:=G[0,p1]  x0−µ[0,p1] m´ax[0,p1] x0−m´ın[0,p1] x0 ≤p2 100⊕ G[0,p1]  x0−µ[0,p1] m´ax[0,p1] x0−m´ın[0,p1] x0 ≥p3 100(6.10) Figura 6.25: Ver código STL en A.2.4 Esta propiedad es nuestro intento de enfocar los ataques de la familia Average de otra manera. Vimos durante la definición de los ataques de la familia Average que, aunque multiplicada por una constante al azar, el valor inicial por el que se sustituye cada medición es el mismo. Lo que intentamos hacer con esta propiedad es detectar si las mediciones están todas cercanas a un valor (en este caso, acotando la diferencia entre una medición en particular y la media del intervalo en el que se encuentra), reescalar dicho valor para no tener problemas de rangos de valores (la razón por la que dividimos entre el rango de valores) e intentar acotarlo. Si el valor final obtenido es pequeño quiere decir que, en general, las mediciones están muy cercanas a un valor 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 93 y, por lo tanto, estamos ante una situación de ataque Average. En otro caso, estamos ante el comportamiento normal del usuario. Vemos el resultado de la exploración de los diferentes espacios de búsqueda usando esta propiedad. Figura 6.26: Estudio de los experimentos en diversos espacios de búsqueda para Avg sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Figura 6.27: Estudio de los experimentos en diversos espacios de búsqueda para MinAvg sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 94 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Figura 6.28: Estudio de los experimentos en diversos espacios de búsqueda para MaxAvg sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Observamos resultados muy mejorados, con o bien una precisión o bien un recall casi perfecto en todos los casos. Seguimos teniendo algún problema con MinAvg pero, en general, el resto de resultados son muchísimo mejores que los de las aproximaciones anteriores. Pasamos ahora a discutir los mejores espacios de búsqueda para los diversos ataques, primero sin tener en cuenta la intersección entre regiones de aceptación. Sin intersección de regiones de aceptación Todas las elecciones de los espacios de búsqueda deberían estar bastante claras. Escogemos CAvg = [0,47]×[0,40]×[0,40] para Avg, CMinAvg = [0,47]×[0,50]×[0,50] para MinAvg y CMaxAvg = [0,47]×[0,90]× [0,90] para MaxAvg. Ver resultados de los experimentos en B.2.4. Con intersección de regiones de aceptación Una vez más, las elecciones de los diversos espacios de búsqueda están bastante claros. Escogemos CAvg = [0,47] × [0,10]×[0,10] para Avg, CMinAvg = [0,47]×[0,30]×[0,30] para MinAvg y CMaxAvg = [0,47] ×[0,40] ×[0,40] para MaxAvg. Ver resultados de los experimentos en B.2.4. Resumen de resultados Resumimos ahora los resultados de los mejores experimentos de cada aproximación que hemos expuesto para cada uno de los tres ataques estudiados: 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 95 Aproximación ¿Intersección? Espacio de búsqueda Precision Recall Accuracy Triple acotación (ver 6.4.3) No N/A N/A N/A N/A Si [0,47] ×[0,10] ×[0,10] 0.5 0.5 0.5 Acumulaciones (ver 6.4.3) No [0,47] ×[0,40] ×[0,40] 0.57 0.85 0.6 Si [0,47] ×[0,30] ×[0,30] 0.55 0.85 0.57 Combinación (ver 6.4.3) No [0,47] ×[0,20] ×[0,20] 0.52 0.6 0.53 Si [0,47] ×[0,50] ×[0,50] 0.5 0.5 0.5 Distancias a la media (ver 6.4.3) No [0,47] ×[0,40] ×[0,40] 0.5 1 0.5 Si [0,47] ×[0,10] ×[0,10] 0.5 0.5 0.5 Cuadro 6.3: Resumen de resultados de las diferentes aproximaciones para Avg Aproximación ¿Intersección? Ataque Campeón Triple acotación (ver 6.4.3) No Normal N/A Avg N/A Si Normal (5.875, 6.875, 6.875) Avg (0, 1.25, 1.25) Acumulaciones (ver 6.4.3) No Normal (41.125, 5, 0) Avg (47, 40, 30) Si Normal (44.0625, 18.75, 13.125) Avg (41.125, 30, 3.75) Combinación (ver 6.4.3) No Normal (14.6875, 2.5, 0) Avg (47, 20, 5) Si Normal (44.0625, 25, 6.25) Avg (44.0625, 25, 0) Distancias a la media (ver 6.4.3) No Normal (23.5, 17.5, 0) Avg (35.25, 40, 0) Si Normal (23.5, 6.25, 0) Avg (47, 6.875, 0.625) Cuadro 6.4: Campeones de las diferentes aproximaciones para Avg 102 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Figura 6.32: Estudio de los experimentos en diversos espacios de búsqueda para FDI50 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Figura 6.33: Estudio de los experimentos en diversos espacios de búsqueda para FDI90 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 103 Figura 6.34: Estudio de los experimentos en diversos espacios de búsqueda para FDI150 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Descubrimos un resultado que, a priori, es sorprendente. Con lo expuesto al principio de esta sección sobre el ataque FDIx, lo que podríamos esperar sería que el ataque con las peores predicciones fuera FDI90 (por su similitud con respecto al comportamiento normal). Sin embargo, la exploración de los espacios de búsqueda nos sugiere que el ataque con las peores predicciones es FDI10. Este es un problema con el que nos vamos a encontrar en repetidas ocasiones y es debido a lo reducido del rango de valores de la señal. Escogemos ahora los espacios de búsqueda para mostrar los mejores experimentos. Procedemos ahora a elegir los mejores espacios de búsqueda dependiendo del ataque, empezando suprimiento la intersección entre regiones de aceptación. Sin intersección de regiones de aceptación Escogemos, por tanto, CF DI10 = [0,47] ×[0,10] ×[0,10] para FDI10, CF DI50 = [0,47] ×[0,50] ×[0,50] para FDI50, CF DI90 = [0,47]×[0,30]×[0,30] para FDI90 y CF DI150 = [0,47]×[0,20]×[0,20] para FDI150. Ver resultados de los experimentos en B.3.1. Con intersección de regiones de aceptación Tomamos CF DI10 = [0,47] × [0,10] ×[0,10] para FDI10, CF DI50 = [0,47] ×[0,20] ×[0,20] para FDI50, CF DI90 = [0,47] ×[0,10] ×[0,10] para FDI90 y CF DI150 = [0,47] ×[0,30] ×[0,30] para FDI150. Ver resultados de los experimentos en B.3.1. 104 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Observando los resultados globales obtenidos, no hay muchas sorpresas más. El ataque que mejor se distingue es FDI50 y el peor FDI10. Los resultados en general son buenos, al menos en nuestros parámetros (con esta propiedad hemos conseguido captar bien el comportamiento del ataque FDIx). Sin embargo, quedan muchos problemas por resolver aún. Estos problemas a los que nos enfrentamos ahora son, principalmente, dos: Esta aproximación ha resultado en una sobreestimación bastante importante: Esto es algo que es fácil observar en la altísima cantidad de falsos positivos observados en los resultados y nos indica que hemos captado demasiado bien el comportamiento de FDIx y es necesario reducir el tamaño de las regiones de aceptación. Esto, sin embargo, no es fácil teniendo en cuenta que debemos seguir captando el comportamiento de FDIx para la mayor cantidad de valores de x posible. Las malos resultados para FDIx con x bajo: Algo que podemos comprobar fácilmente viendo los mediocres resultados de FDI10 y nos indica que el rango de valores es demasiado pequeño como para ser captado por la propiedad. Esto podría solucionarse aumentando la resolución de la división de celdas del algoritmo de minado pero esta no es una solución factible porque aumentaría exponencialmente el coste temporal de dicho algoritmo. Debemos, entonces, intentar diseñar una propiedad que capte el comportamiento de FDIx sin tener en cuenta (de alguna manera) el rango de valores. Vamos a intentar resolver estos problemas con las dos siguientes aproximaciones Segunda aproximación - Rangos extremos 2.0 La traducción matemática de esta propiedad es la siguiente: ϕ:= 100 ·m´ın[0,p1] x0 m´ax[0,p1] x0 ≤p2⇔100 ·m´ın[0,p1] x0 m´ax[0,p1] x0 ≤p3(6.12) Figura 6.35: Ver código STL en A.3.2 Esta propiedad es nuestro primer intento de crear una propiedad que capte bien 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 105 el comportamiento de FDIx sin que importe el valor de x mientras que el rango de valores de la señal no sea relevante. Una manera de comprobar si el rango de valores de una cierta señal es muy ’extremo’ es calcular la diferencia entre el mínimo y el máximo. La aproximación que hemos tomado aquí es distinta, sin embargo. Con esta aproximación, queremos ver el ratio entre el mínimo y el máximo de los valores y expresarlo como porcentaje, con la idea de captar los valores FDIx para x bajos si este porcentaje se aproxima a 100 (el mínimo está muy cerca del máximo) y captar FDIx para x altos si ese porcentaje se aproxima a 0 (el mínimo está muy lejos del máximo). Explicada esta aproximación, vemos el resultado de la exploración de diversos intervalos de búsqueda. Figura 6.36: Estudio de los experimentos en diversos espacios de búsqueda para FDI10 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 106 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Figura 6.37: Estudio de los experimentos en diversos espacios de búsqueda para FDI50 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Figura 6.38: Estudio de los experimentos en diversos espacios de búsqueda para FDI90 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 107 Figura 6.39: Estudio de los experimentos en diversos espacios de búsqueda para FDI150 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Aunque la sobreestimación sigue existiendo, estamos consiguiendo de manera consistente un recall perfecto y, además, se percibe una mejoría notable para los ataques FDIx con x pequeño. Una vez más, escogemos los espacios mejores espacios de búsqueda para cada ataque, empezando por suprimir las regiones de aceptación. Sin intersección de regiones de aceptación Escogemos, CF DI10 = [0,47] × [0,60] ×[0,60] para FDI10, CF DI50 = [0,47] ×[0,10] ×[0,10] para FDI50, CF DI90 = [0,47] ×[0,30] ×[0,30] para FDI90 y CF DI150 = [0,47] ×[0,40] ×[0,40] para FDI150. Ver resultados de los experimentos en B.3.2. Con intersección de regiones de aceptación Tomamos CF DI10 = [0,47] × [0,60] ×[0,60] para FDI10, CF DI50 = [0,47] ×[0,10] ×[0,10] para FDI50, CF DI90 = [0,47] ×[0,20] ×[0,20] para FDI90 y CF DI150 = [0,47] ×[0,60] ×[0,60] para FDI150. Ver resultados de los experimentos en B.3.2. Un vistazo a los resultados nos confirma que la sobreestimación sigue existiendo y sigue siendo bastante acusada. Sin embargo, los resultados han mejorado notablemente con respecto a la aproximación anterior y ya podemos obtener un recall perfecto de manera consistente, haciendo esta aproximación muy fiable a la hora de descartar el ataque. Intentamos ahora reducir la sobreestimación mientras mantenemos la 108 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS fiabilidad de resultados que ya hemos conseguido. Tercera aproximación - Combinación de las dos anteriores La traducción matemática de esta propiedad es la siguiente: ϕ:= 100 ·m´ın[0,p1] x0 m´ax[0,p1] x0 ≤p2⇔Zp1 0 x0≥p3(6.13) Figura 6.40: Ver código en A.3.2 Vistas las dos aproximaciones anteriores, esta no necesita más explicación. Estamos combinando la información recopilada en las dos aproximaciones anteriores. Mostramos los resultados de la exploración de los espacios de búsqueda. Figura 6.41: Estudio de los experimentos en diversos espacios de búsqueda para FDI10 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 109 Figura 6.42: Estudio de los experimentos en diversos espacios de búsqueda para FDI50 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Figura 6.43: Estudio de los experimentos en diversos espacios de búsqueda para FDI90 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 110 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Figura 6.44: Estudio de los experimentos en diversos espacios de búsqueda para FDI150 sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Los resultados de la exploración de los espacios de búsqueda nos muestra que vamos por el buen camino. Esta propiedad consigue reducir notablemente la sobreestimación observada en aproximaciones anteriores, sobretodo para los valores pequeños de x. Procedemos ahora a escoger los mejores espacios de búsqueda. Sin intersección de regiones de aceptación Escogemos, CF DI10 = [0,47] × [0,60] ×[0,60] para FDI10, CF DI50 = [0,47] ×[0,30] ×[0,30] para FDI50, CF DI90 = [0,47] ×[0,30] ×[0,30] para FDI90 y CF DI150 = [0,47] ×[0,20] ×[0,20] para FDI150. Ver resultados de los experimentos en B.3.3. Con intersección de regiones de aceptación Tomamos CF DI10 = [0,47] × [0,30] ×[0,30] para FDI10, CF DI50 = [0,47] ×[0,10] ×[0,10] para FDI50, CF DI90 = [0,47] ×[0,10] ×[0,10] para FDI90 y CF DI150 = [0,47] ×[0,20] ×[0,20] para FDI150. Ver resultados de los experimentos en B.3.3. Confirmamos los resultados que ya sospechábamos. Hemos conseguido reducir la sobreestimación de las propiedades anteriores (sobretodo en los casos para FDI10 y FDI150). 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 111 Resumen de resultados Resumimos ahora los resultados de los mejores experimentos de cada aproximación que hemos expuesto para cada uno de los cuatro ataques estudiados: Aproximación ¿Intersección? Espacio de búsqueda Precision Recall Accuracy Acumulaciones extremas (ver 6.4.4) No [0,47] ×[0,10] ×[0,10] 1 0.2 0.6 Si [0,47] ×[0,10] ×[0,10] 0.5 1 0.5 Rangos extremos 2.0 (ver 6.4.4) No [0,47] ×[0,60] ×[0,60] 0.5 1 0.5 Si [0,47] ×[0,60] ×[0,60] 0.5 1 0.5 Combinación (ver 6.4.4) No [0,47] ×[0,60] ×[0,60] 0.67 1 0.75 Si [0,47] ×[0,30] ×[0,30] 0.9 0.9 0.9 Cuadro 6.9: Tabla de resultados de FDI10 Aproximación ¿Intersección? Ataque Campeón Acumulaciones (ver 6.4.4) No Normal (5.875, 0, 1.875) FDI10 (8.8125, 6.875, 10) Si Normal (11.75, 5, 6.25) FDI10 (11.75, 0.625, 10) Rangos extremos 2.0 (ver 6.4.4) No Normal (31.0625, (44.0625, 7.5, 0) FDI10 (41.125, 37.5, 7.5) Si Normal (11.75, 7.5, 0) FDI10 (11.75, 7.5, 3.75) Combinación (ver 6.4.4) No Normal (20.5625, 33.75, 0) FDI10 (0, 60, 0) Si Normal (17.625, 0, 15) FDI10 (23.5, 0, 1.875) Cuadro 6.10: Campeones de las diferentes aproximaciones para FDI10 118 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS aceptación. Sin intersección de regiones de aceptación Escogemos CRSA[0,1,0,8] = [0,47] × [0,40]×[0,40] para RSA[0.1,0.8], CRSA[0,5,3] = [0,47]×[0,10]×[0,10] para RSA[0.5,3] yCRSA[2,3] = [0,47]×[0,60]×[0,60] para RSA[2,3]. Ver resultados de los experimentos en B.4.1. Con intersección de regiones de aceptación Tomamos CRSA[0,1,0,8] = [0,47] × [0,20]×[0,20] para RSA[0.1,0.8], CRSA[0,5,3] = [0,47]×[0,20]×[0,20] para RSA[0.5,3] yCRSA[2,3] = [0,47]×[0,10]×[0,10] para RSA[2,3]. Ver resultados de los experimentos en B.4.1. Observamos un problema similar al que vimos cuando usamos esta misma aproximación para FDIx y es que observamos una sobreestimación bastante importante y que, aunque no sea necesariamente una sorpresa, creemos relevante mencionar las “similaridades” entre ambos ataques. Veamos si ocurre lo mismo con las siguientes dos aproximaciones. Segunda aproximación - Rangos extremos 2.0 Mostramos los resultados del estudio de los espacios de búsqueda: Figura 6.49: Estudio de los experimentos en diversos espacios de búsqueda para RSA[0.1,0.8] sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 119 Figura 6.50: Estudio de los experimentos en diversos espacios de búsqueda para RSA[0.5,3] sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Figura 6.51: Estudio de los experimentos en diversos espacios de búsqueda para RSA[2,3] sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Una vez más, observamos un comporamiento similar al de FDIx aunque más pronunciado en esta ocasión. Hemos conseguido una mejoría de los resultados, obteniendo un recall perfecto de manera consistente. Sin embargo, debemos buscar una aproxi- 120 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS mación todavía que reduzca la sobreestimación. Buscamos ahora los mejores espacios de búsqueda, primero sin tener en cuenta la intersección de regiones de aceptación. Sin intersección de regiones de aceptación Escogemos CRSA[0,1,0,8] = [0,47] × [0,40]×[0,40] para RSA[0.1,0.8], CRSA[0,5,3] = [0,47]×[0,90]×[0,90] para RSA[0.5,3] yCRSA[2,3] = [0,47]×[0,30]×[0,30] para RSA[2,3]. Ver resultados de los experimentos en B.4.2. Con intersección de regiones de aceptación Tomamos CRSA[0,1,0,8] = [0,47] × [0,20]×[0,20] para RSA[0.1,0.8], CRSA[0,5,3] = [0,47]×[0,50]×[0,50] para RSA[0.5,3] yCRSA[2,3] = [0,47]×[0,40]×[0,40] para RSA[2,3]. Ver resultados de los experimentos en B.4.2. Tercera aproximación - Combinación de las dos anteriores Veamos el estudio de los espacios de búsqueda: Figura 6.52: Estudio de los experimentos en diversos espacios de búsqueda para RSA[0.1,0.8] sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 121 Figura 6.53: Estudio de los experimentos en diversos espacios de búsqueda para RSA[0.5,3] sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Figura 6.54: Estudio de los experimentos en diversos espacios de búsqueda para RSA[2,3] sin tener en cuenta la intersección entre regiones de aceptación (izquierda) y teniéndola en cuenta (derecha) Aunque no es una mejora tan pronunciada como si lo fue en el caso de FDIx, vemos que esta propiedad también mejora bastante los resultados obtenidos en las dos aproximaciones anteriores, manteniendo la consistencia del recall casi perfecto 122 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS que veíamos en la aproximación anterior. Presentamos ahora los mejores espacios de búsqueda. Sin intersección de regiones de aceptación Escogemos CRSA[0,1,0,8] = [0,47] × [0,20]×[0,20] para RSA[0.1,0.8], CRSA[0,5,3] = [0,47]×[0,10]×[0,10] para RSA[0.5,3] yCRSA[2,3] = [0,47]×[0,40]×[0,40] para RSA[2,3]. Ver resultados de los experimentos en B.4.3. Con intersección de regiones de aceptación Tomamos CRSA[0,1,0,8] = [0,47] × [0,30]×[0,30] para RSA[0.1,0.8], CRSA[0,5,3] = [0,47]×[0,40]×[0,40] para RSA[0.5,3] yCRSA[2,3] = [0,47]×[0,20]×[0,20] para RSA[2,3]. Ver resultados de los experimentos en B.4.3. Resumen de resultados Ofrecemos, una vez más, los resultados resumidos de los mejores experimentos: Aproximación ¿Intersección? Espacio de búsqueda Precision Recall Accuracy Acumulaciones extremas (ver 6.4.5) No [0,47] ×[0,40] ×[0,40] 0.67 0.9 0.73 Si [0,47] ×[0,20] ×[0,20] 0.53 0.95 0.55 Rangos extremos 2.0 (ver 6.4.5) No [0,47] ×[0,40] ×[0,40] 0.5 1 0.5 Si [0,47] ×[0,20] ×[0,20] 0.5 1 0.5 Combinación (ver 6.4.5) No [0,47] ×[0,20] ×[0,20] 0.56 0.95 0.6 Si [0,47] ×[0,30] ×[0,30] 0.59 1 0.65 Cuadro 6.17: Tabla de resultados de RSA[0.1,0.8] 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 123 Aproximación ¿Intersección? Ataque Campeón Acumulaciones (ver 6.4.5) No Normal (8.8125, 5, 0) RSA[0.1,0.8] (20.5625, 40, 15) Si Normal (8.8125, 10, 20) RSA[0.1,0.8] (11.75, 5, 20) Rangos extremos 2.0 (ver 6.4.5) No Normal (41.125, 35, 5) RSA[0.1,0.8] (20.5625, 40, 32.5) Si Normal (32.3125, 8.75, 17.5) RSA[0.1,0.8] (35.25, 8.75, 20) Combinación (ver 6.4.5) No Normal (5.875, 7.5, 6.25) RSA[0.1,0.8] (0, 20, 2.5) Si Normal (23.5, 30, 5.625) RSA[0.1,0.8] (17.625, 30, 5.625) Cuadro 6.18: Campeones de las diferentes aproximaciones para RSA[0.1,0.8] Aproximación ¿Intersección? Espacio de búsqueda Precision Recall Accuracy Acumulaciones extremas (ver 6.4.5) No [0,47] ×[0,10] ×[0,10] 0.51 1 0.53 Si [0,47] ×[0,20] ×[0,20] 0.51 1 0.53 Rangos extremos 2.0 (ver 6.4.5) No [0,47] ×[0,30] ×[0,30] 0.53 1 0.55 Si [0,47] ×[0,20] ×[0,20] 0.53 1 0.55 Combinación (ver 6.4.5) No [0,47] ×[0,30] ×[0,30] 0.59 1 0.65 Si [0,47] ×[0,10] ×[0,10] 0.59 1 0.65 Cuadro 6.19: Tabla de resultados de RSA[0.5,3] 124 CAPÍTULO 6. DETECCIÓN DE ATAQUES EN SMART GRIDS Aproximación ¿Intersección? Ataque Campeón Acumulaciones (ver 6.4.5) No Normal (0, 7.5, 10) RSA[0.5,3] (5.875, 5.625, 8.75) Si Normal (0, 3.75, 20) RSA[0.5,3] (0, 10, 20) Rangos extremos 2.0 (ver 6.4.5) No Normal (26.4375, 16.875, 9.375) RSA[0.5,3] (26.4375, 30, 15) Si Normal (29.375, 6.25, 17.5) RSA[0.5,3] (32.3125, 11.25, 17.5) Combinación (ver 6.4.5) No Normal (5.875, 5.625, 30) RSA[0.5,3] (23.5, 5.625, 9.375) Si Normal (41.125, 7.5, 7.5) RSA[0.5,3] (23.5, 7.5, 7.5) Cuadro 6.20: Campeones de las diferentes aproximaciones para RSA[0.5,3] Aproximación ¿Intersección? Espacio de búsqueda Precision Recall Accuracy Acumulaciones extremas (ver 6.4.5) No [0,47] ×[0,60] ×[0,60] 0.64 0.9 0.7 Si [0,47] ×[0,10] ×[0,10] 0.51 1 0.53 Rangos extremos 2.0 (ver 6.4.5) No [0,47] ×[0,40] ×[0,40] 0.5 1 0.5 Si [0,47] ×[0,60] ×[0,60] 0.5 1 0.5 Combinación (ver 6.4.5) No [0,47] ×[0,20] ×[0,20] 0.53 1 0.55 Si [0,47] ×[0,20] ×[0,20] 0.71 1 0.8 Cuadro 6.21: Tabla de resultados de RSA[2,3] 6.4. FASE DE EXPERIMENTACIÓN: EN PROFUNDIDAD 125 Aproximación ¿Intersección? Ataque Campeón Acumulaciones (ver 6.4.5) No Normal (20.5625, 60, 37.5) RSA[2,3] (20.5625, 15, 3.75) Si Normal (0, 10, 3.75) RSA[2,3] (0, 9.375, 6.25) Rangos extremos 2.0 (ver 6.4.5) No Normal (47, 35, 5) RSA[2,3] (29.375, 25, 12.5) Si Normal (44.0625, 7.5, 37.5) RSA[2,3] (44.0625, 7.5, 26.25) Combinación (ver 6.4.5) No Normal (0, 20, 3.75) RSA[2,3] (5.875, 8.75, 16.25) Si Normal (23.5, 0, 20) RSA[2,3] (32.3125, 12.5, 20) Cuadro 6.22: Campeones de las diferentes aproximaciones para RSA[2,3] Dedicamos de nuevo esta sección final a realizar un análisis de los resultados obtenidos y determinar cuál de ellos es el mejor. Por tanto, debemos dar una respuesta satisfactoria a las siguientes preguntas: ¿Cuál es la mejor aproximación para diferenciar el ataque FDIx de un comportamiento normal? En general, hemos podido observar cómo el comportamiento de RSA[a,b] y el de FDIx es bastante similar y las tablas finales de resultados nos confirman esta hipótesis (ver 6.17, 6.19, 6.21). Por tanto, una vez más, es la tercera aproximación propuesta (la combinación de las dos anteriores) la que escogemos como mejor aproximación. En este caso es la que escogemos dado que puede que de resultados ligeramente peores a los que nos ofrecía para el caso FDIx pero es la que da los mejores resultados de manera uniforme. ¿Es preferible quitar o mantener la intersección entre regiones de aceptación? Elegida la propiedad óptima, simplemente debemos echar un vistazo a las tablas de resultados obtenidas para ver que, una vez más, es preferible tener en cuenta la intersección entre regiones de aceptación. 126 Capítulo 7 Conclusiones y trabajo futuro Para acabar este trabajo presentamos unas reflexiones sobre el cumplimiento de los objetivos establecidos en la introducción. Ofreceremos también algunas ideas para la continuidad de este proyecto que, en nuestra opinión, tiene bastante futuro. 7.1. Conclusiones Durante la introducción (ver 1) establecimos como objetivos globales del proyecto ampliar las prestaciones de ParetoLib introduciendo un nuevo algoritmo de minado de datos usando propiedades STL paramétricas y usar, entre otras cosas, dicho algoritmo para detectar comportamientos anómalos y manipulaciones en mediciones de smart grids. Además, teníamos como objetivo extra incorporar las funcionalidades asociadas al algoritmo de minado de datos a la previamente existente interfaz de usuario de ParetoLib. Vayamos paso por paso examinando el cumplimiento de cada objetivo. Implementación del algoritmo de minado de datos de propiedades STL paramétricas (ver 4.1): juzgamos que ha sido un éxito, ya que es capaz de extraer diversos tipos de comportamiento (algunos relativamente complejos) de series temporales mediante el uso de propiedades STL. Además, mediante la implementación de una versión paralela del algoritmo y de una partición dinámica de celdas a analizar, hemos conseguido disminuir el tiempo de computación y, al mismo tiempo, aumentar la precisión el análisis. Evaluación del algoritmo usando datos reales para la detección de manipulacio127 134 CHAPTER 8. FINAL THOUGHTS AND FUTURE WORK 8.2.2. Improve and broaden the experimentation phase The experiments we have performed, although comprehensive, were used in order to evaluate the data mining algorithm and build the foundations to elaborate a much more extensive experimentation phase in the future. It is during this final section where we propose ways to improve and broaden our results: Improve the training phase of certain types of attacks: If, once again, we take a look at the chapter dedicated to the experimentation phase (see 6), we will notice that the worst results have been obtained while detecting the attacks related to Average. One of the reasons we believe this has happened is because the training phase for the Average attack is not as correct as it should be. If, instead of choosing consecutive days in the training phase, we were able to pick days from different weeks, we would be able to obtain a much more diverse sample and, as such, the oracle would have more information to make the necessary predictions. Broaden the experimentation phase so that more users (even multiple users) are monitored: Although the experimentation phase with user 1143 has greatly contributed to a better understanding of the behaviours of the different attacks, it would also be crucial to broaden this experimentation phase further into more users even on ISSDA-CER’s database (see [10]) so that we are able to identify more abnormal normal behaviours on the users’ part (the example we have previously talked about is regarding users who work graveyard shifts). “Complicating” the problem: Our experimentation has been done using just the data regarding user electrical consumption. However, this is not the only discipline where our approach could be useful. Other examples include user gas consumption registered by smart grids or, more interestingly, the energy consumption by photovoltaic panels. This last case is interesting because it would introduce the idea of “liberating energy” to the system, in which the user releases energy they do not need into the network, generating a “negative measurement”. Apéndice A Códigos STL A.1. Swap A.1.1. Primera aproximación - Acotación simple 1(and 2(<= 3(On (0 p1) (Ix0)) 4p2 5) 6(<= 7(On (p1 47) (Ix0)) 8p3 9) 10 ) A.1.2. Segunda aproximación - Acotación doble 1(-> 2(>= 3(On (0 p1) (Ix0)) 4p2 5) 6(<= 7(On (p1 47) (Ix0)) 8p3 9) 10 ) 135 136 APÉNDICE A. CÓDIGOS STL A.1.3. Tercera aproximación - Acotación doble refinada 1(and 2(-> 3(>= 4(On (0 p1) (Ix0)) 5p2 6) 7(<= 8(On (p1 47) (Ix0)) 9p3 10 ) 11 ) 12 (-> 13 (<= 14 (On (p1 47) (Ix0)) 15 p3 16 ) 17 (>= 18 (On (0 p1) (Ix0)) 19 p2 20 ) 21 ) 22 ) A.1.4. Cuarta aproximación - Solución parasitaria 1(-> 2(G(0 p2) (<= (Dx0) 0)) 3(>= (On (0 p1) (Ix0)) (On (p1 47) (Ix0))) 4) A.2. Familia Average A.2.1. Primera aproximación - Triple acotación del rango de valores 1(G(0 inf ) 2(and 3(and 4(-> 5(<= 6(On (0 47) (- (Max x0) ( Min x0))) A.2. FAMILIA AVERAGE 137 7p1 8) 9(<= 10 (On (0 47) (- (Max x0) ( Min x0))) 11 p2 12 ) 13 ) 14 (-> 15 (<= 16 (On (0 47) (- (Max x0) ( Min x0))) 17 p2 18 ) 19 (<= 20 (On (0 47) (- (Max x0) ( Min x0))) 21 p1 22 ) 23 ) 24 ) 25 (and 26 (-> 27 (<= 28 (On (0 47) (- (Max x0) ( Min x0))) 29 p2 30 ) 31 (<= 32 (On (0 47) (- (Max x0) ( Min x0))) 33 p3 34 ) 35 ) 36 (-> 37 (<= 38 (On (0 47) (- (Max x0) ( Min x0))) 39 p3 40 ) 41 (<= 42 (On (0 47) (- (Max x0) ( Min x0))) 43 p2 44 ) 45 ) 46 ) 47 ) 48 ) 138 APÉNDICE A. CÓDIGOS STL A.2.2. Segunda aproximación - Diferencia de acumulaciones 1(and 2(or 3(<= 4(abs (- (On (0 p1 /2) (Ix0)) (On ( p1 /2 p1 ) (Ix0)))) 5p2 6) 7(>= 8(abs (- (On (0 p1 /2) (Ix0)) (On ( p1 /2 p1 ) (Ix0)))) 9p3 10 ) 11 ) 12 (or 13 (not 14 (<= 15 (abs (- (On (0 p1 /2) (Ix0)) (On ( p1 /2 p1 ) (Ix0)))) 16 p2 17 ) 18 ) 19 (not 20 (>= 21 (abs (- (On (0 p1 /2) (Ix0)) (On ( p1 /2 p1 ) (Ix0)))) 22 p3 23 ) 24 ) 25 ) 26 ) A.2.3. Tercera aproximación - Combinando las dos anteriores 1(-> 2(<= 3(abs (- (On (0 p1 /2) (Ix0)) (On ( p1 /2 p1 ) (Ix0)))) 4p2 5) 6(<= 7(On (0 p1) (- (Max x0) ( Min x0))) 8p3 9) 10 ) A.2.4. Cuarta aproximación - Distancias a la media A.3. FDIX 139 1(and 2(or 3(G(0 p1) 4(<= 5(/ (abs (- x0 (/ (On (0 p1) (Ix0)) (+ p1 1)))) (On (0 p1) (- (Max x0) (Min x0)))) 6(/ p2 100) 7) 8) 9(G(0 p1) 10 (>= 11 (/ (abs (- x0 (/ (On (0 p1) (Ix0)) (+ p1 1)))) (On (0 p1) (- (Max x0) (Min x0)))) 12 (/ p3 100) 13 ) 14 ) 15 ) 16 (or 17 (not 18 (G(0 p1) 19 (<= 20 (/ (abs (- x0 (/ (On (0 p1) (Ix0)) (+ p1 1)))) (On (0 p1) (- (Max x0) ( Min x0)))) 21 (/ p2 100) 22 ) 23 ) 24 ) 25 (not 26 (G(0 p1) 27 (>= 28 (abs (- x0 (/ (On (0 p1) (Ix0)) (+ p1 1)))) 29 (/ p3 100) 30 ) 31 ) 32 ) 33 ) 34 ) A.3. FDIx A.3.1. Primera aproximación - Acumulaciones extremas 1(and 140 APÉNDICE A. CÓDIGOS STL 2(-> 3(G(0 p1) 4(>= 5(On (0 p1) (Ix0)) 6p2 7) 8) 9(G(0 p1) 10 (>= 11 (On (0 p1) (Ix0)) 12 p3 13 ) 14 ) 15 ) 16 (-> 17 (G(0 p1) 18 (>= 19 (On (0 p1) (Ix0)) 20 p3 21 ) 22 ) 23 (G(0 p1) 24 (>= 25 (On (0 p1) (Ix0)) 26 p2 27 ) 28 ) 29 ) 30 ) A.3.2. Segunda aproximación - Rangos extremos 2.0 1(and 2(-> 3(<= 4(* (On (0 p1) (/ ( Min x0) (Max x0))) 100) 5p2 6) 7(<= 8(* (On (0 p1) (/ ( Min x0) (Max x0))) 100) 9p3 10 ) 11 ) 12 (-> A.3. FDIX 141 13 (<= 14 (* (On (0 p1) (/ ( Min x0) (Max x0))) 100) 15 p3 16 ) 17 (<= 18 (* (On (0 p1) (/ ( Min x0) (Max x0))) 100) 19 p2 20 ) 21 ) 22 ) Tercera aproximación - Combinación de las dos anteriores 1(and 2(-> 3(<= 4(* (On (0 p1) (/ ( Min x0) (Max x0))) 100) 5p2 6) 7(>= 8(On (0 p1) (Ix0)) 9p3 10 ) 11 ) 12 (-> 13 (>= 14 (On (0 p1) (Ix0)) 15 p3 16 ) 17 (<= 18 (* (On (0 p1) (/ ( Min x0) (Max x0))) 100) 19 p2 20 ) 21 ) 22 ) 142 Apéndice B Resultados de los experimentos Dedicamos este apéndice a los resultados de los experimentos realizados, con el fin de compactar el cuerpo principal de la memoria lo más posible. 143