Probabilistic approaches development for optimizing learning parameters procedure for testing models via the expectation-maximization method

Full Text

Введение

Применение вероятностных моделей фаззинга для решения задач тестирования веб-приложений позволяет в наибольшей степени решить задачу нахождения ошибок, возникающих в процессе функционирования программ. В основе данных моделей лежит возможность определения модулей фаззинга в виде узлов модели и задание им стохастических параметров. Наибольший интерес для моделирования процессов тестирования представляют динамические модели, позволяющие оценивать состояние процессов фаззинга на протяжении фиксированного временного интервала $(t;t+k)$ и дающие возможность накопления статистической и вероятностной информации относительно возникновения событий ошибок (свидетельств). В рамках данного исследования будем использовать байесовские сети (БС) как наиболее адаптированную модель представления процессов тестирования. Решение задачи разработки оптимальных алгоритмов обучения параметров БС связано с необходимостью повышения точности существующих алгоритмов, а также оптимизацией расчетов вероятностей с использованием логарифма правдоподобия, а также критериев Шварца и Акаике. Применение стохастического градиента, а также динамик Гамильтона и Ланжевена в сочетании с методом Монте-Карло с применением цепей Маркова позволяет оптимизировать процедуру расчета распределений по всем возможным переменным БС. Основной задачей исследования является разработка математических методов и инструментальных средств, направленных на оптимизацию алгоритмов обучения моделей фаззинга на основе метода ожидания-максимизации.

Результаты и обсуждение

Процедура обучения параметров байесовских сетей предназначена для определения вероятностных распределений для каждой из вершин в соответствии с обучающей выборкой $D={\left\{\left(X_k,Y_k\right)\right\}}_{k=1}^n$. $X=\left\{X_1,X_2,\dots ,X_n\right\}$ – множество вершин байесовских сетей, $Y=Parents\left(X_i\right)$ – родительские вершины, соответствующие переменным $X$. В таком случае вероятность соответствия переменной $X$ конкретному значению $\theta$ будет иметь следующий вид [1]:

$P\left(\theta \text{|}X\right)=P\left(X\text{|}\theta \right)P\left(\theta \right).$ (1)

С учетом того, что байесовская сеть представляет собой пару значений $\left\{X,G\right\}$ и $X=\left\{X_1,X_2,\dots ,X_n\right\}$, выражение (1) запишем в терминах байесовской сети:

$P\left(\theta \text{|}X\right)=\underset{i=1}{\overset{N}{}}P\left(X_i\text{|}\theta \right)P\left(\theta \right).$ (2)

Для получения полного совместного распределения параметров байесовской сети воспользуемся правилом апостериорного принятия решений. Тогда оценка параметра $\theta$ может быть получена за счет определения логарифма правдоподобия для каждой из переменных $X_{\text{i}}$ в соответствии с выражением (1) и (2). Получим [2, 3]:

${\theta }_{MAP}^G=P\left(\theta \text{|}X\right)=\arg \underset{\theta }{\max }logP\left(X\right|\theta )+\log P\left(\theta \right).$ (3)

Правило апостериорного принятия решений лежит в основе алгоритма ожидания максимизации (ОМ), предназначенного для обучения байесовских сетей со скрытыми параметрами. На этапе ожидания происходит замена скрытых переменных на значение их оценок, после чего вычисляется значение правдоподобия для параметров $\theta$. На этапе максимизации производится вычисление таблиц условных вероятностей для каждой из вершин байесовской сети в условиях полных данных. Заполнение скрытых данных производится за счет решения уравнения Гамильтона и дифференциального уравнения, формируемого на основе информационной матрицы Фишера. Рассмотрим алгоритм стохастического градиента в сочетании с динамикой Гамильтона.

Вектор градиента, соответствующий функции правдоподобия $\text{log}P\left(X\right|\theta )$, будет иметь следующий вид:

$\begin{array}{l}g\left(\theta ,X_i\right)=\nabla \log P\left(\theta \text{|}{X}_i\right),\\ G\left(\theta ,X\right)=\underset{i=1}{\overset{N}{}}g\left(\theta ,X_i\right).\end{array}$ (4)

Запишем уравнение Ланжевена на основе стохастического дифференциального уравнения Ито. С учетом градиента функции правдоподобия получим

$d\theta \left(t\right)=\nabla \log P\left(\theta \left(t\right)\right)dt+\sqrt{2}d{B}_t,$ (5)

где $B_t=\mathcal{N}\left(\mathrm{0,}I\right)$ – гауссовский процесс.

Применяя метод Стермера – Верле, получим решение уравнения (5), определяющее каждый следующий шаг для параметра ${\theta }_{t+1}$

$\begin{array}{l}{\theta }_{t+1}={\theta }_t+\frac{{ϵ}_t}{2} \nabla \text{log}P\left({\theta }_t\right)+\mathcal{N}\left(\mathrm{0,}{ϵ}_t\right),\\ {\theta }_t~P\left(\theta \right).\end{array}$ (6)

Введем обозначение градиента для ${\text{θ}}_{\text{MAP}}^{\text{G}}$ в соответствии с (4)

$g\left(\theta \right)=\nabla \log P\left(\theta \right)+\underset{i=1}{\overset{N}{}}\text{log}\left(X_i|\theta \right).$ (7)

Тогда перепишем выражение (6) с учетом введенных обозначений [5]

$\nabla {\theta }_{t+1}={\theta }_t+\frac{{ϵ}_t}{2}\left(\nabla \log P\left({\theta }_t\right)+\frac{n}{N}G\left(\theta ,X\right)\right)+\phi .$ (8)

Из выражения (8) следует, что при ${ϵ}_t\to 0$ наблюдаем снижение ошибки в решении уравнения Ланжевена. В таком случае общая сложность алгоритма стохастического градиента может быть снижена до $\text{O}\left(n\right), n<<N$ в отличие от алгоритма Метрополиса – Гастингса (МГ). Как показывает практика, выполнение ${ϵ}_t\to 0$ не всегда достижимо, как следствие, применение уравнения Гамильтона становится проблематичным. Для решения данной проблемы зададим ковариацию $g\left(\theta ,X\right)$ и выразим информацию Фишера для наблюдаемых переменных байесовской сети $X=\left\{X_1,X_2,\dots ,X_n\right\}$ через градиент функции $g\left(\text{θ},\text{X}\right)$ [4]:

$I\left(\theta ,X\right)=\mathbb{M}{\left[\frac{d}{d\theta }logP\left(\theta ,X\right)\right]}^2=\mathbb{M}{\left[g\left(\theta ,X\right)\right]}^2.$ (9)

Из выражения (9) следует, что чем выше значение математического ожидания в точке ${\theta }_0$, тем становится проще выделить значение $\text{θ}$ на фоне ${\theta }_0$ и точнее можно выполнить оценку параметра $\text{θ}$ при выполнении условия $\theta ={\theta }_0$. В таком случае информация Фишера $\text{I}\left(\text{θ},\text{X }\right)$ будет содержать полный набор сведений относительно параметра $\theta$, содержащихся в наблюдаемых переменных байесовской сети $X_1,X_2,\dots ,X_n$.

Отметим, что в большинстве случаев информация $I\left( \theta ,X \right)$ имеет непосредственную зависимость от параметризации. В таком случае можно получить альтернативную запись выражения (9). Для этого введем следующие предположения: $\text{Ω}$ – некоторый бесконечный (конечный) интервал; множество $A=\{X:P\left(\text{θ},\text{X}\right)>0\}$, формируемое из распределения $P\left(\text{θ},\text{X}\right)$; для всех переменных $X\in A$ и $\theta \in \text{Ω}$ существует производная $P^{\text{'}}\left(\text{θ},\text{X}\right)=dP\left(\text{θ},\text{X}\right)/d\theta$.

Если условие $A=\{X:P\left(\text{θ},\text{X}\right)>0\}$ выполняется и производная по $\theta$ относительно меры $\mu$ стоящая под знаком интеграла

$\int P\left(\theta ,X\right)d\mu \left(X\right)=1.$ (10)

дифференцируема, получим равенство нулю математического ожидания от $P^{\text{'}}\left(\theta /X\right)$

$\mathbb{M}\left[\frac{d}{d\theta }P\left(\theta ,X\right)\right]=0.$ (11)

Следовательно,

$I\left(\theta ,X\right)=\mathbb{D}\left(\frac{d}{d\theta }P\left(\theta ,X\right)\right).$ (12)

Если существует вторая производная от логарифма правдоподобия $\text{log}P\left(\theta \text{|}X\right)$ относительно параметра $\theta$ и вторая производная по $\theta$ вычисляется путем повторного дифференцирования выражения, стоящего под знаком интеграла (10), выражение для $\text{I}\left(\text{ θ},\text{X }\right)$ может быть записано в следующем обобщенном виде

$I\left(\theta ,X\right)=-\mathbb{M}\left(\frac{d^2}{d^2\theta }logP\left(\theta ,X\right)\right)=-\mathbb{M}\left(H\left(\theta ,X\right)\right),$ (13)

где $\text{H}\left(\text{θ},\text{X}\right)$ – матрица Гессе, соответствующая функции правдоподобия $\text{log}P\left(\text{θ},\text{X}\right)$.

Так как наблюдения $X_1,X_2,\dots ,X_n$ являются независимыми, тогда для $I\left(\theta ,X\right)$ справедливо следующее выражение:

$I_n\left(\theta ,X\right)=n{I}_1\left(\theta ,X\right).$ (14)

Для выражения (14) получим аппроксимацию информации Фишера в следующем виде:

$I^{\text{'}}\left(\theta ,X\right)=\underset{n}{}g\left(\theta ,X\right)g{\left(\theta ,X\right)}^T.$ (15)

Выражение (15) носит название эмпирической информации Фишера, соответствующей распределению $P\left(\theta ,X\right)$. В таком случае для больших значений $n$ в соответствии с центральной предельной теоремой получим

$\begin{array}{l}\overline{G}\left({\theta }_t,X_n\right)=\mathcal{N}\left(\mathbb{M}\left[G\left({\theta }_t,X\right)\right],\frac{1}{n}cov\left(G\left({\theta }_t,X\right)\right)\right),\\ \overline{G}\left({\theta }_t,X_n\right)=\frac{G\left({\theta }_t,X_n\right)}{N}.\end{array}$ (16)

С учетом того, что ковариация $\text{cov}\left(\text{G}\left({\theta }_{\text{t}},X\right)\right)$ определяется в соответствии с информацией Фишера, получим следующие приближенные значения с учетом определенного ранее выражения (14)

$\begin{array}{l}ncov\left(G\left({\theta }_t,X\right)\right)\approx I_n,\\ n\mathbb{M}\left[G\left({\theta }_t,X\right)\right]\approx G_n\left({\theta }_t,X_n\right).\end{array}$ (17)

В таком случае второе слагаемое выражения (16) приведем к следующему виду

$\begin{array}{l}\nabla \log P\left({\theta }_t\right)+\frac{n}{N}\overline{G}\left({\theta }_t,X_n\right)=\pi +{\phi }^{\text{'}},\\ \pi =\nabla \log P\left({\theta }_t\right)+G_n\left({\theta }_t,X_n\right)\\ {\phi }^{\text{'}}=\mathcal{N}\left(\mathrm{0,}\frac{n}{N}{I}_N^{-1}\right).\end{array}$ (18)

В соответствии с правилом апостериорного вывода первые два слагаемых, стоящих в правой части уравнения (18), соответствуют градиенту логарифма апостериорного распределения

$\log P\left({\theta }_t\text{|}{X}_N\right)=\nabla \log P\left({\theta }_t\right)+G_n\left({\theta }_t,X_n\right).$ (19)

Воспользовавшись теоремой Бернштейна фон Мизеса, получим важные следствия асимптотической теории байесовского вывода, заключающиеся в близости апостериорного распределения к нормальному. Пусть $P_n\left(\text{θ}\right|\left\{{\text{X}}_1,{\text{X}}_2,\dots ,{\text{X}}_{\text{N}}\right\})$ – апостериорное распределение параметра $\text{θ}$ при наличии наблюдений ${\text{X}}_1,{\text{X}}_2,\dots ,{\text{X}}_{\text{N}}$, формируемых в соответствии с $P_{\text{θ}}$ и начальным распределением $P_{{\text{θ}}_0}$ на множестве параметров $\text{Θ}\in ℝ$. Если ${\text{X}}_1,{\text{X}}_2,\dots ,{\text{X}}_{\text{N}}$– случайные выборки, полученные согласно распределению $P_{{\text{θ}}_0}$, то для апостериорного распределения вероятностей $P_n\left(\text{θ}\right|\left\{{\text{X}}_1,{\text{X}}_2,\dots ,{\text{X}}_{\text{N}}\right\})$ будет справедлива теорема Бернштейна фон Мизеса:

$\begin{array}{l}{P}_{{\theta }_0}^n\underset{\theta }{\sup }\left|P_n\left(\theta \right|\left\{X_1,X_2,\dots ,X_N\right\}-\mathcal{N}\left(\theta ,I_N^{-1}\right)\right|\to \mathrm{0,}\\ P_n\left(\theta \right|\left\{X_1,X_2,\dots ,X_N\right\}\approx \mathcal{N}\left(\theta ,I_N^{-1}\right).\end{array}$ (20)

Если теорема Бернштейна фон Мизеса выполнима для распределения $P_n\left(\text{θ}\right|\left\{{\text{X}}_1,{\text{X}}_2,\dots ,{\text{X}}_{\text{N}}\right\})$, то для градиента функции правдоподобия будет справедливо следующее выражение [5]:

$\begin{array}{l}\nabla \log P\left({\theta }_t\right)=\nabla \log P\left({\theta }_t|X_N\right)+G\left(\theta ,X\right),\\ \nabla \log P\left({\theta }_t|X_N\right)=-I_N\left({\theta }_t-{\theta }_0\right).\end{array}$ (21)

Перепишем выражение (8) с учетом выражений (18) и (21)

$\begin{array}{l}\nabla {\theta }_{t+1}={\theta }_t+\frac{{ϵ}_t}{2}\left(-I_N\left({\theta }_t-{\theta }_0\right)\right)+\phi +\xi ,\\ \xi \approx \mathcal{N}\left(\mathrm{0,}\frac{{{ϵ}_t}^2}{4}\frac{n}{N}{I}_N^{-1}\right).\end{array}$ (22)

Обобщая формулы (18) и (22), получим значения дисперсии $\text{Q}$ для нормального распределения $\mathcal{N}\left(\mathrm{0,}\text{ Q}\right)$ для больших и малых значений шага ${ϵ}_t$

$Q=\left\{\begin{array}{c}{ϵ}_t,{ϵ}_t\to 0 \\ {ϵ}_t- \frac{{{ϵ}_t}^2}{4}\frac{n}{N}{I}_N^{-1},{ϵ}_t\to \infty \end{array}\right..$ (23)

Наряду с определением параметров нормального распределения необходимо произвести расчет информационной матрицы Фишера $-{\text{I}}_{\text{N}}\left({\text{θ}}_{\text{t}}-{\text{θ}}_0\right)$. Для этого воспользуемся определенной ранее эмпирической информацией Фишера и запишем оценку ${\widehat{I}}_{\mathrm{1,}t}$

${\widehat{I}}_{\mathrm{1,}t}\left(\theta ,X\right)=\frac{1}{t}{\widehat{I}}_{\mathrm{1,}t}\left(\theta ,X\right)+\frac{1}{t}{I}^{\text{'}}\left({\theta }_t,X_t^n\right).$ (24)

В таком случае можно провести замену ${\text{I}}_{\text{N}}$ на соответствующую ей оценку ${\widehat{I}}_{\mathrm{1,}t}\left(\text{θ},\text{X }\right)$.

По результатам выполнения алгоритма стохастического градиента и расчета информационных матриц для каждого шага уравнения (22) получим необходимый набор выборок, в наибольшей степени согласованный с обучающим множеством $D$. Для описания этапа максимизации запишем полное совместное распределение байесовской сети со скрытыми переменными.

На этапе максимизации производится вычисление максимальной оценки нижней границы логарифма правдоподобия, но уже с учетом того, что распределение по всем скрытым переменным уже известно и определено в соответствии с алгоритмами стохастического градиента, описанного выше. Тогда оценка максимального правдоподобия параметра $\text{θ}$ на этапе максимизации будет иметь следующий вид [6, 7]:

$\begin{array}{l}{\theta }^{\text{'}}=arg\underset{{\theta }^{\text{'}}}{\max }\left(\underset{H}{}q\left(\theta ;H\right)\log \left(\frac{P\left(E,X\text{|}\theta \right)}{q\left(\theta ;X\right)}\right)\right),\\ q\left(\theta ;H\right)=\frac{P(E,X|\theta )}{{\displaystyle \sum _{H}P(E,X|\theta )}}=\frac{P(E,X|\theta )}{P\left(E\right|\theta )}=P\left(X\text{|}E,\theta \right),\end{array}$ (25)

где E и X – множество наблюдаемых и скрытых переменных байесовской сети соответственно.

Для оценки точности формирования распределения вероятностей по всем вершинам байесовской сети на основе алгоритма ОМ рассмотрим его сходимость. На этапе максимизации видно, что полученные распределения должны удовлетворять условию регулярности (гладкости и монотонности). Для этого определим для данного распределения дистанцию Кульбака – Лейблера (КЛ). С помощью дистанции КЛ [8] установим факт близости двух распределений $f_{\theta }\left(E\right|X)$ и ${f_{\theta }}^{\text{'}}\left(E\right|X)$, полученных в результате использования классического алгоритма ОМ и алгоритма ОМ с применением стохастического градиента в сочетании с информационной матрицей Фишера (ОМ и СГФ)

$D_{KL}\left(f,f^{\text{'}}\right)=\int f_{\theta }\left(H\right|X)\log \frac{f_{\theta }\left(H\right|X)}{{f_{\theta }}^{\text{'}}\left(H\right|X)}dH.$ (26)

Выражение (33) можно переписать в виде разности двух математических ожиданий для функций $f$ и $f^{\text{'}}$ соответственно, при этом полагаем, что $\text{X}$ и $E$ являются случайными переменными по отношению к рассматриваемому истинному распределению $f$ [9]:

$\begin{array}{l}{D}_{KL}\left(f,f^{\text{'}}\right)=F(H,X)=E_f\left[\log f_{\theta }\left(H\right|X)\right]-E_{f^{\text{'}}}\left[\log {f_{\theta }}^{\text{'}}\left(H\text{|}X\right)\right],\\ F(H,X)=\int f_{\theta }\left(H\text{|}X\right)\log f_{\theta }\left(H\text{|}X\right)dH-\int f_{\theta }\left(H\text{|}X\right)\log {f_{\theta }}^{\text{'}}\left(H\text{|}X\right)dH\end{array}$. (27)

С практической точки зрения в данной работе дистанция Кульбака –Лейблера используется для верификации представленного подхода к обучению параметров байесовской сети на основе алгоритма ОМ и стохастического градиента по сравнению с классическим алгоритмом ОМ и ОМ с применением алгоритма Метрополиса – Гастингса. Это дает возможность оценить степень точности получения распределения по всем скрытым переменным $f^{\text{'}}$ и при необходимости произвести настройку разработанного алгоритма.

В рамках проведения экспериментальной части исследования рассмотрим байесовскую сеть тестирования «инъекций» веб-приложений. Структурно «инъекции» делятся на следующие основные категории: SQL, команд и кода. Данные типы «инъекций» возникают в веб-приложениях, взаимодействующих с реляционными базами данных, а также имеющих функциональные возможности по динамическому выполнению системных команд.

Для оценки эффективности приложенных математических алгоритмов обучения произведем сравнения существующих подходов к обучению параметров ДБС «Инъекции». Для этого воспользуемся распределенной системой Spark, функционирующей в облачной среде Yandex Cloud, состоящей из 6 узлов со следующей аппаратной конфигурацией: 2 процессора Intel Xeon-Platinum 2.5 GHz 16 ядер, 128 GB ОЗУ, жесткий диск 10 TB. Максимальное число обучающих выборок $\text{D}=1000000$ размерностью в 500 ГБ. Для проведения сравнения рассмотрим алгоритмы ожидания максимизации (ОМ), ожидания максимизации на основе алгоритма Метрополиса – Гастингса (ОМ и МГ) и с применением стохастического градиента в сочетании с информационной матрицей Фишера (ОМ и СГФ).

Таблица – Сравнение производительности алгоритмов обучения ДБС «Инъекции»

Из сравнительных характеристик алгоритмов таблицы 1 видно, что разработанный алгоритм на основе ОМ и СГФ обладает оптимальной производительностью вне зависимости от размера обучающей выборки. На рисунке приведем значение дистанции КЛ для каждого из алгоритмов ОМ, ОМ и МГ, ОМ и СГФ.

Рисунок – Значение дистанции Кульбака – Лейблера для алгоритмов ОМ, ОМ и МГ, ОМ и СГФ в зависимости от размера выборки D

На рисунке эталонным является распределение, полученное по результатам обучения параметров ДБС в режиме полного наблюдения, в этом случае обучающая выборка будет являться полной.

Заключение и выводы

Моделирование интеллектуальных средств тестирования приложений на основе моделей БС и ДБС непрерывно связано с созданием и совершенствованием алгоритмов обучения и вероятностного вывода, предназначенных для оптимизации механизмов тестирования и создания адаптивных механизмов для анализа возникающих ошибок. В исследовании затронуты основные проблемы, связанные с моделированием процессов тестирования в виде моделей ДБС, а также решения задач обучения, направленных на получение априорных значений для начального распределения, а также определение переходных вероятностей для смежных временных срезов сети. Результатом проведенного исследования является разработка алгоритма обучения, расширяющего функциональные возможности ОМ и позволяющего в значительной степени повысить интенсивность и качество обучения параметров БС и ДБС со скрытыми переменными. Проведена оценка эффективности каждого из алгоритмов в зависимости от объема обучающей выборки, используемой в процессе получения распределения $P\left(X\text{|}E,\theta \right)$.

Практические расчеты экспериментальной части доказывают правильность предложенных подходов к решению задачи обучения параметров БС и ДБС. Повышение точности формирования распределения по всем скрытым переменным в первую очередь связано с применением матрицы Фишера, позволяющей аккумулировать все сведения относительно параметров $\theta ={\theta }_1,{\theta }_2,\dots ,{\theta }_n,$ содержащихся в выборке $D$ относительно наблюдаемых переменных $E=E_1,E_2,\dots ,E_n$. В таком случае апостериорное распределение $P\left(X\text{|}E,\theta \right)$ будет согласованным относительно $E$ с учетом $\theta$ для выборки $D$. Предложенный алгоритм обладает хорошей сходимостью к истинному распределению при небольшом объеме обучающей выборки и позволяет оптимизировать существующие подходы обучения байесовских сетей в условиях частичной наблюдаемости.

About the authors

Pavel V. Polukhin

Author for correspondence.
Email: alfa_force@bk.ru

Candidate of Technical Sciences, Lecturer of the Faculty of Applied Mathematics, Informatics and Mechanics

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Figure – The value of the Kullback – Leibler distance for the OHMS, ohms and MG, OHMS and GFS algorithms, depending on the sample size D

Download (74KB)

Indexing metadata