Математичні методи розпізнавання надзвичайних ситуацій в умовах невизначеності

MATHEMATICAL METHODS FOR THE RECOGNITION OF EMERGENCY EVENTS UNDER UNCERTAINTY

It has been shown that emergency events recognition systems exhibit various types of uncertainty: incomplete data streams, data stream errors, and inappropriate patterns of complex events. There were presented an overview of existing approaches for complex event recognition under uncertainty. It was noticed that the field of complex event recognition under uncertainty is relatively new and proposed to adopt methods of targeting activity recognition. It was shown that the streams of time-stamped derived events arriving at a complex event recognition system carry a certain degree of uncertainty and ambiguity. Information sources have to be heterogeneous, with data of different structures schemas and procedures of respond to corrupted data. Even for perfectly accurate sensors, the domain might be difficult to model precisely, thereby leading to another type of uncertainty. Thus, it is noted that it is important to consider methods for recognizing complex events that can be classified as uncertain, for this purpose, appropriate model objects were proposed. The analysis of key moments in the construction of complex recognition systems that are capable of working effectively under uncertainty included stochastic modeling, time representation models, and relational models. There were considered techniques based on automata, probabilistic graphical models, first-order logic, Petri Networks and Hidden Petri Networks. It is specified that the intermediate stage of the work of the corresponding algorithms should be the creation of a hierarchy of complex objects that are not always clearly defined. A number of limitations have been found regarding the syntax, models and performance used, which were compared with the specific variants of their implementation. An approach was proposed for the transition from a deterministic mathematical apparatus to a system of recognition of complex events under uncertainty conditions, through the introduction of the probability function of an event. The developed methodology allowed highlighting directions for investigation and estimating efficiency of the mathematical methods to be used.

Keywords: emergency events; uncertainty conditions; probabilistic logics; probabilistic automata; probabilistic graphical models; probabilistic Petri nets; hidden Petri networks.

Вступ

Розроблення систем розпізнавання складних подій (CER: Complex Event Recognition), зіставлення відповідних шаблонів є актуальним та нетривіальним математичним завданням. Згідно з базовою моделлю, що можна використати під час вирішення цього завдання (рисунок), на вхід такої системи подається потік даних про події, параметри яких є визначеними (SDE: Simple Derived Events), на основі яких комплекс CER ідентифікує складні події (CE: Complex Event) відповідно до попередньо заданих шаблонів (Artikis et al., 2012). Отже, окрему комплексну подію CEi можна визначити через зв'язки та обмеження, що накладаються на вхідний набір SDE та інші CE.

Модельними об'єктами роботи CER, що розробляються з метою розпізнавання надзвичайних ситуацій в умовах невизначеності, можуть бути алгоритми захисту мережевих ресурсів інформаційних систем (МРІС) від внутрішніх та зовнішніх кібернетичних загроз (Knapp, 2014; Zhang, 2016), морські системи моніторингу та боротьби з браконьєрством (Santipantakis, 2015), методики ведення військової розвідки (Candamo, 2015) тощо. Ці приклади наочно показують, що вхідний потік даних, що стосується CE (як-от протоколи системи моніторингу, результати аерокосмічної зйомки та ін.), не може бути безпосередньо використано для прийняття рішень. Отже, проміжним етапом роботи відповідних алгоритмів має бути створення ієрархії складних об'єктів CE, що не завжди піддаються чіткому визначенню.

Рисунок 1 Базова модель системи розпізнавання складних подій

1. Аналіз останніх досліджень і публікацій

Ц цій галузі свідчить про те, що розпізнавання складних подій способом зіставлення відповідних шаблонів розпізнавання подій призводить до різних типів невизначеностей від формування неповних та помилкових потоків даних до створення недосконалих складних моделей подій (Paschke et al., 2008; Brendel et al., 2011; Chuanfei et al., 2010; Fierens et al., 2015; Skarlatidis et al., 2015; Albanese et al., 2010; Khokhar et al., 2013; Selman et al., 2011; Artikis et al., 2010; Song et al., 2013; Lavee et al., 2013; Massimiliano et al., 2008).

У представлених роботах було розглянуто сучасний метод вирішення зазначеної проблеми, що базуються на теорії абстрактних автоматів (Paschke et al., 2008; Brendel et al., 2011; Chuanfei et al., 2010; Fierens et al., 2015), ймовірнісних графових моделях (Skarlatidis et al., 2015; Albanese et al., 2010; Khokhar et al., 2013), системах логіки числення предикатів першого порядку (Selman et al., 2011; Artikis et al., 2010; Song et al., 2013), а також мережах Петрі (Lavee et al., 2013; Massimiliano et al., 2008).

Проведений аналіз вказав на актуальні підходи до математичного моделювання у цій галузі (Paschke et al., 2008; Brendel et al., 2011; Chuanfei et al., 2010; Fierens et al., 2015; Skarlatidis et al., 2015; Albanese et al., 2010; Khokhar et al., 2013; Selman et al., 2011; Artikis et al., 2010; Song et al., 2013; Lavee et al., 2013; Massimiliano et al., 2008), показав необхідність побудови цілісної методології розпізнавання надзвичайних ситуацій в умовах невизначеності, що в межах цієї роботи виділяється як невирішена частина загальної проблеми побудови комплексних систем CER.

Метою дослідження є визначення оптимального підходу під час побудови алгоритмів розпізнавання складних подій через аналіз обмежень, що накладають відповідні підходи та відповідності імовірнісних моделей статистичним даним.

Матеріали і методи дослідження. У роботі як матеріал дослідження використано статистичні дані з розпізнавання складних подій в умовах невизначеності різних типів: формування неповних потоків даних, формування помилкових потоків даних, похибки у створенні складних моделей подій тощо. Методи дослідження охоплювали розробку та аналіз роботи математичних моделей, що узагальнюють теорію абстрактних автоматів, ймовірнісні графові моделі, системи логіки числення предикатів першого порядку і мережі Петрі.

Базові підходи для розпізнавання надзвичайних ситуацій. Для ефективної роботи в умовах невизначеності необхідно мати уявлення - з якими типами невизначеності зазвичай мають справу під час розпізнавання подій, і розділити їх у такий спосіб на дві групи (Lavee et al., 2013; Artikis et al., 2012; Wasserkrug et al., 2006):

• невизначеність вхідних даних (data uncertainty);

• невизначеність шаблону (pattern uncertainty).

Як було зазначено вище, вхідні дані CER складаються з SDE, що за означенням у собі не можуть нести невизначеність, але їхній набір може бути неповним, що призводить до невизначеності вхідних даних під час побудови CE. Невизначеність вхідних даних зазвичай пов'язана з проблемами під час побудови апаратної частини системи моніторингу: дисфункціональності системи реєстрації або її невідповідність середовищу, в межах якого доводиться проводити реєстрацію, наприклад низька ефективність у разі виділення шумів. Невизначеність шаблону також пов'язана з неповнотою інформації про шаблон, що використовується системою CER, або проблемами з їх ефективним узагальненням та включенням у алгоритм аналізу. Отже, навіть за умов наявності повного набору SDE система CER здатна провести неправильне визначення надзвичайної ситуації, що призводить до появи другого типу невизначеності.

Ключові моменти, які треба визначити під час побудови систем CER, яка здатна ефективно працювати в умовах невизначеності, містять вибір таких компонентів:

• методи стохастичного моделювання (probabilistic modeling);

• моделі часового представлення (time representation);

• реляційні моделі (relational models).

Методи стохастичного моделювання полягають у попередній обробці вхідних даних з метою видалення або зменшення рівня шуму та інших складових, що не є функціональними під час побудови CE. Також методи цієї групи охоплюють зіставлення однотипних SDE та аналіз надійності їх джерела (Shet et al., 2007; Shet et al., 2011; Ginsberg, 1988), що зумовлює необхідність застосування нечітких множин (fuzzy set), наприклад: логічне програмування (Shet et al., 2007; Shet et al., 2011), двоґратчастий фреймворк (BF: Bilattice Framework) (Ginsberg, 1988) та теорію Демпстера-Шафера, що працює з неоднорідними подіями (Ma et al., 2010). Стохас- тичні моделі допомагають створити цілісну базу вхідних даних для аналізу комплексу CER, тому їх використовують у більшості систем розпізнавання.

Моделі представлення часу також охоплюють декілька підходів. Зокрема достатньо високу ефективність показують моделі неявного представлення часу (Implicit Representation). За такого підходу враховується порядок подій та співвідношення їх тривалості, але сам час як окрема змінна під час аналізу не використовується (Allen, 1984; Cervesato et al., 2000).

Під час побудови методології побудови CER необхідно враховувати цей підхід, хоча більшість моделей використовує очевидне представлення часу та часових обмежень, що може бути пов'язано зі специфікою роботи CER. Для SDE з очевидним часовим представленням можна було використовувати імовірнісні графові моделі, такі як прихована марковська модель та її розширення (Rabiner et al., 1986; Brand et al., 1997; Gong et al., 2003; Kersting et al., 2006), а також динамічні байєсівсь- кі мережі (Murphy et al., 2002) та умовні випадкові поля (CRF: Conditional Random Fields) (Lafferty et al., 2001).

Але варто зазначити, що приховані той марковські моделі та CPF передбачають з визначеним набором об'єктів, тоді як у рамках побудови системи CER неможливо заздалегідь визначити всі можливі події вхідного потоку SDE (Kersting et al., 2006). Окрім цього, відсутність у рамках цих методів моделювання формального способу представлення подій та їх зв'язків ускладнює визначення CE і подальше генерування комплексом CER реляційних та ієрархічних структур. Тому в цій роботі в межах розроблення принципів побудови CER надаємо перевагу реляційним моделям.

Табл. 1 Елементи синтаксису алгебри подій системи CER

Побудова математичного апарату розпізнавання подій. Ключовим етапом побудови системи CER є математичне формулювання процесу виявлення шаблонів подій під час аналізу потоку SDE. За допомогою теорії складності обчислень можна виявити ті конструкції алгебри подій, що дають змогу знайти оптимальне співвідношення між ефективністю опису та складністю (Cervesato et al., 2000; Zhang et al., 2014).

У цій роботі пропонуємо використати такі елементи синтаксису (табл. 1):

• послідовність (Seq: Sequence): порядок слідування подій;

• диз'юнкція (Dis: Disjunction): наявність однієї з двох подій незалежно від часових співвідношень;

• кон'юнкція (Con: Conjunction): наявність обох подій;

• ітерація (Ite: Iteration): наявність N циклів повторення події, де N > 0 ;

• заперечення (Neg: Negation): відсутність події;

• умовний перехід (Sel: Selection): вибір події, атрибути якої задовольняють сукупності предикатів та відносин 0 між подіями;

• проекціювання (Pro: Projection): повернення події, значення атрибута якої пов'язане з підмножиною значень атрибутів похідної події (SE: Sub-event);

• відсікання (Win: Windowing): обмеження шаблону події попередньо визначеним часовим проміжком.

У табл. 1 наведено математичні вирази для елементів синтаксису алгебри подій системи CER, при цьому введено додаткові змінні. Так, для умовного переходу s0(CE) складної події, що є функцією атрибутів [ab a2.. .an ], визначається відповідність предикату 0 , а для pm(CE) - виділяється CE відповідно до підмножини m . Розроблений синтаксис дає змогу побудувати ієрархію подій, що може бути покладено в основу системи CER. Можливість ефективно визначати події на різних рівнях і описувати зв'язки між подіями не є тривіальним завданням. Отже, цей підхід допомагає визначити продуктивність та точність типових методів, на основі яких система моделює перехід подій низького рівня до високого рівня.

Однак розроблений математичний апарат є детерміністичним. Для роботи системи CER в умовах невизначеності необхідно додатково ввести функцію вірогідності події та її атрибутів відповідно до невизначеності вхідного потоку SDE та шаблонів. Нехай для події CE(ai,a2..an,t), що є функцією атрибутів [ai,a2...an] та часу t. Якщо вірогідність атрибутів такої функції визначається через Prob, тоді вірогідність наявності цієї події можна визначити як P+, а вірогідність відсутності - як P-- :

У реальних системах зазвичай маємо працювати з набором ймовірних значень для кожного з атрибутів ai :

Щодо стосується емпіричного визначення скінченному ймовірнісного простору (Probability Space), то його множина будується на основі аналізу частоти появи елементів вхідного потоку SDE, що мають бути визначені як дискретні випадкові величини.

Згідно з ймовірнісними правилами, CE маємо розглядати як набори подій, що визначаються через взаємні зв'язки та моменти часу, а отже, і відповідні вірогідності. Нехай у нас є подія CE0(A,t), де

A = [aba2..an] -

набір атрибутів, що може бути виражена через події CE1(A1, t1) та CE2(A2, t2) і оператор проекціювання:

Рrob :: CE A, t = р A= A2,T =T2 CE1( A1, t1); CE2( A2, t2) . (3)

У цій формі представлення, якщо CE1 передує CE2, CE0 , відбувається у момент t2 з вірогідністю Prob. Ймовірнісний простір, що містив CE1 і CE2, розширюється до CE0 , а отже, ймовірнісне правило варто розуміти як визначення умовної ймовірності виникнення CE0 з огляду на те, що події CE1 і CE2 відбулися згідно з тим порядком, що визначається шаблоном.

Часто для систем CER завдання полягає в обчисленні безумовних ймовірностей (marginal probability) CE, враховуючи наявний потік SDE. Розглянемо наступний приклад визначення безумовної ймовірності наявності коду кібернетичної атаки типу DDoS на інфраструктуру МРІС у фрагменті коду log A11 протягом визначеного проміжку часу, представленого у стандартному форматі T1 (години: хвилини: секунди), T2 (години: хвилини: секунди):

P DDoS log A11,13 : 22 : 08,13 : 22 : 28 | SDE ) . (4)

Оцінку апостеріорного максимуму імовірності (MAP: Maximum A Posteriori Inference) відповідно до певного інтервалу часу можна визначити як:

I DDoS = arg max1 P DDoS log A11, I | SDE . (5)

Останнім етапом побудови системи CER є спрощення математичного апарату з метою збільшення продуктивності комплексу. Для цього розробляються припущення, що надалі дають змогу отримувати приблизні висновки. Система при цьому може надавати відповіді за допомогою довірчих інтервалів або через можливість встановлення порогового значення типу CT (confidence threshold).

Класифікація методів CER згідно з синтаксисом алгебри подій. Розроблений синтаксис було запропоновано використати для аналізу чотирьох груп методів розпізнавання: методів автоматного програмування (au- tomata-based methods) (Paschke et al., 2008; Brendel et al., 2011; Chuanfei et al., 2010; Fierens et al., 2015), мережі Петрі (Lavee et al., 2013; Massimiliano et al., 2008), методи, які базуються на прихованих марковських моделях (Kersting et al., 2006), а також групу, що охоплює системи логіки першого порядку та імовірнісні графові моделі (Skarlatidis et al., 2015; Albanese et al., 2010; Khokhar et al., 2013; Selman et al., 2011; Artikis et al., 2010; Song et al., 2013).

Результати аналізу представлені в табл. 2-5 і містять дані про модель, функціональні елементи з кожного методів і можливість побудови ієрархічного набору CE (CE Hierarchies: CEH).

Методи автоматного програмування мають певні переваги під час побудови системи CER, оскільки вхід CER зазвичай розглядають у вигляді потоку (послідовностей подій), подібно до рядків символів на вході детермінованого скінченного автомату. При цьому CE описується аналогічно до SQL, причому оператор послідовності в такому описі відіграє центральну роль. Такий опис легко трансформувати в автоматі з потоком ББЕ на вході.

Табл. 2 Синтаксис алгебри подій методів автоматного

Табл. 3 Синтаксис систем логіки першого порядку та імовірнісних графових моделей

Табл. 4 Синтаксис методів розпізнавання на базі мереж Петрі

Табл. 5 Синтаксис методів, що базуються на прихованих марковських моделях

В імовірнісних версіях методів автоматного програмування повний набір ББЕ не може бути чітко визначеним, його елементи супроводжуються значеннями відповідних ймовірностей, що стосуються їх атрибутів та й самого факту їх наявності, і тільки після цього використовуються для визначення ймовірностей СЕ.

Інша група методів у роботі в умовах невизначеності базується на імовірнісних моделях графів. Ці моделі можуть бути представлені як мережі, вузли яких є випадковими величинами, а ребра кодують імовірнісні залежності. Два основних класи імовірнісних графічних моделей, що використовуються в CER:

• марковські мережі (неорієнтовані графи);

• байєсівські мережі (неорієнтовані графи).

Під час застосування у комплексі CER марковські мережі зазвичай поєднуються з системами логіки першого порядку і належать до марковських логічних мереж (MLN: Markov Logic Networks). Вузли MLN представляють логічні предикати, що виражається через відповідний математичний апарат представлення CE. Однак під час використання баєсівських мереж вузли представляють безпосередньо події (SDEs та CEs).

Мережі Петрі використовуються у CER для вирішення питань паралелізму та синхронізації. Формально мережу Петрі можна описати як двопарний граф (bipartite directed graph).

Остання група методів пов'язана з синтаксичними підходами у визначенні СЕ і здебільшого базується на прихованих марковських моделях. Ці підходи зазвичай перетворюють потік вхідних SDE у потік символів, на які можна застосувати правила, визначені користувачем. Правила визначаються через ймовірнісну граматику, щоб врахувати під час аналізу чинник невизначеності. Це може бути досягнуто способом присвоєння значення вірогідності кожному правилу виводу.

Висновки

Розроблена методологія дає змогу узагальнити досвід побудови CER через розробку універсального синтаксису для розпізнавання надзвичайних подій в умовах невизначеності через оператори, що використовуються у відповідних моделях. Показано, що під час аналізу має бути використано ієрархічний підхід, визначення моделі часового представлення (відповідно до моментів часу та часових інтервалів) і ймовірнісної моделі, що зумовлена необхідністю підтримки невизначеності вхідних даних та невизначеності шаблону, а також довірчого інтервалу чи порогового значення довіри до приблизних висновків, що виконуються системою розпізнавання.

На основі розробленої методології можна визначити оцінку ефективності та складності конкретного математичного методу розпізнавання надзвичайних ситуацій в умовах невизначеності, тобто продуктивності комплексу CER.

розпізнавання надзвичайний стохастичний шаблон

Перелік використаних джерел