Статистические методы распознавания клавиатурного почерка

II.

УДК 004.065

Ю.А. Брюхомицкий

СТАТИСТИЧЕСКИЕ МЕТОДЫ РАСПОЗНАВАНИЯ КЛАВИАТУРНОГО ПОЧЕРКА*

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

Клавиатурный почерк; биометрические параметры; статистическое распо-; ;

.

Yu. A. Bryukhomitsky STATISTICAL METHODS OF KEYSTROKE DYNAMICS ECOGNITION

We are discussing one of the possible approaches to the increase of keyboard-based authentication means, which differs from existing ones by a two-stage training procedure. It consists of estimation of keystroke feature distribution followed by operator estimation of probability densities. The advantage of this approach is based on the fact that it provides much higher asymptotical estimation precision and hence better keystroke authentication.

Keystroke dynamics; biometric features; statistical recognition; empirical distribution functions; operator estimation of probability densities.

Контроль доступа в компьютерные системы, реализуемый на основе анализа его клавиатурного почерка (КП), имеют ряд неоспоримых преимуществ. Главными из них являются: минимальная в классе биометрических средств стоимость, , -вами контроля доступа, в частности, парольными. К недостаткам биометрических средств этого класса принято относить: недостаточную для самостоятельного ис,

, .

В данной работе обсуждается один из возможных подходов к повышению точности клавиатурных средств аутентификации, основанный на использовании особенностей статистических методов распознавания.

Принцип аутентификации пользователя, претендующего на доступ в компьютерную систему по его КП, заключается в проведении анализа КП при вводе некоторой контрольной фразы и вынесении по результатам анализа соответствующего

. -

*

Работа выполнена при поддержке гранта РФФИ № 08-07-00117-а.

ляются особенности динамики работы на клавиатуре данного пользователя, представленные в виде совокупности контролируемых клавиатурных параметров. Анализ состоит в формировании текущих клавиатурных параметров идентифицировавшего себя пользователя и сравнении их с эталонными параметрами пользователя с тем же именем, сформированными ранее, на этапе его регистрации.

Отправной точкой при создании методов и средств аутентификации личности по КП является принятый способ представления и использования индивидуальных

. .

Пусть с клавиатуры пользователем за период времени Т вводится некоторая контрольная фраза, содержащая q символов. При вводе этой фразы произойдет г = q + р событий клавиатуры: q удержаний клавиш и р = q - 1 пауз между удержаниями. При большой скорости ввода возможны наложения времен удержания , -. , -цательные значения длительности пауз между удержаниями.

:

• Т - значение длительности удержания клавиши /, Т > 0;

• Т - алгебраическое значение длительности паузы между удержании-

У

ями клавиш I и ].

Процесс ввода некоторой контрольной фразы, в которой г = 11, q = 6, р = 5, иллюстрируется временной диаграммой (рис. 1).

Временная раскладка процесса клавиатурного ввода контрольной фразы в виде сочетаний длительностей удержания клавиш: Т1,Т2,Т3,...,Тп и длительностей пауз между удержаниями: Т12,Т23,Т34,...,Т^п_1)п индивидуальна для каждого пользователя и выступает в качестве эталона КП.

к--------------------------- Т ----------------------------->1

Рис. 1. Временная диаграмма процесса ввода контрольной фразы

Поставим в соответствие результату клавиатурного ввода контрольной фразы, временная диаграмма которой показана на рис.1, г-мерный вектор биометриче-

V = { }  =1,г ,

каждый компонент У| которого соответствует длительности любого очередного ( ), произошедшего за период Т. События клавиатуры, состоящие в наложении времен , -

ветствующих компонент вектора V. При таком представлении вектор биометрических параметров V можно рассматривать как образец КП данного пользователя.

Так, для временной диаграммы, показанной на рис. 1, вектор биометрических параметров будет иметь вид:

V = {v1, У2,...У11},

где

V! = Ть V2 = Т12; Vз = Т2; V4 = -Т23; V5 = Т3; V6 = Т34; V7 = Т4; ^ = Т45; V9 = Т5; Vlo = ^ V!! = Тб.

Для получения клавиатурного эталона пользователя необходимо иметь серию, состоящую из Ь образцов КП, которая составит обучающую выборку для некоторого ^-класса

]={Уг}, г = 1Ь.

В общем случае в системе может быть зарегистрировано множество К = [к1, к2, ..., кМ} пользователей, каждый из которых будет представлен своим эталоном и будет соотнесен с определенным классом из множества классов 5 = {51, 52, ..., 5М}.

,

{А} на множество классов {5}.

Для формирования эталонов всех М легитимных пользователей потребуется соответственно М обучающих выборок

) ^

В режиме аутентификации неизвестный х-пользователь предъявляет обученной клавиатурной системе контроля доступа (КСКД) образец своего КП в виде

вектора биометрических параметров V(х) = { } ] = 1,г . Система должна на

основе вектора V(х) сформировать эталонное описание неизвестного х-класса, сравнить его с эталонами всех зарегистрированных в системе {к1, к2, ..., кМ} пользователей и по результатам сравнения вынести соответствующее аутентификаци-.

вектора V(х) на М+1 взаимоисключающих классов: М классов из множества 5 = {51, 52, ., 5М}, соответствующих зарегистрированным в системе пользователям и (М+1)-й класс, отведенный всем остальным пользователям, объединяемым понятием «чужие». При наличии процедуры предварительной авторизации пользователей задача упрощается и сводится к классификации вектора V(х) на два класса: 8С - «свой», то есть принадлежащий к какому-либо классу из множества {5}, и яч -«чужой», то есть не принадлежащий ни к одному классу из множества {5}.

Конечной целью обучения является формирование эталонных описаний клас.

правилах. Природа данных при анализе КП носит случайный характер, поэтому вид решающего правила может быть заимствован из теории статистических реше-

,

распределения и сравнению его с некоторым порогом С:

> с,,

к ('К) '

где кг (V! яг) - условная совместная г-мерная плотность вероятности выборочных значений { } ] = 1,г г при условии их принадлежности к классу 8;.

В том случае, если хотя бы с некоторым приближением вид закона распре де,

, .

обучения при этом является получение оценок параметров известного распределения, по которым затем вычисляются плотности вероятностей. Например, в ряде , -

,

,

получить хорошие результаты по точности аутентификации [1].

Более общим и сложным является случай, когда нет априорных сведений не только о параметрах, но и о законе распределения. Тогда применяются не параметрические методы распознавания. Целью обучения в такой ситуации является получение оценок условных плотностей вероятностей.

В задаче классификации клавиатурных биометрических параметров в силу ряда специфических причин, связанных с нестабильностью КП, допущение о « » -ции. Поэтому в тех случаях, когда указанные причины невозможно игнорировать, приходится обращаться к не параметрическим методам [2].

(1) -

ской классификации параметров КП состоит в том, что плотности кг (V | 5г) ап -риорно не известны и должны быть представлены своими оценками кг ( | яг),

полученными при обучении на основе образцов векторов {V}, г = 1, Ь .

Анализ наиболее распространенных непараметрических методов восстановления плотности вероятности с помощью гистограммных, парценовских, к бли-, , не обеспечивают точности оценивания при реальных конечных объемах обучающих выборок. Кроме того, ряд методов (р^ложений по базисным функциям, поли) -.

В такой ситуации целесообразно представлять исходные данные для принятия решений не оценками плотностей распределения кг ( | яг), а оценками

функций распределения ¥г (V | .?г) [3]. Основное преимущество такого подхода состоит в том, что появляется принципиальная возможность использования значений эмпирической функции распределения ¥г (V | .?г) во всех точках V области ее

определения. Как известно, оценивание плотности распределения возможно только на основе конечного множества наблюдений, при этом недостаток важной информации восполняется всевозможными допущениями (введение весовых функ-

ций, функций потенциала и т.п.), которые собственно и породили множество различных непараметрических методов. Между тем, функции распределения

к ('к) содержат всю доступную информацию о классах образов, а их оценки

к ( яг) позволяют контролировать точность аппроксимации функций

К (V15,) при любых объемах Ь обучающей выборки. Однако непосредственно

использовать оценки Рг (V | 5,) в тесто оценок кг (V | 5,) при постр оении решающего правила не представляется возможным.

Для приведения исходных данных, представленных оценками функций распределения Рг (V | 5,), к традиционной структуре решающего правила (1) можно

перейти от оценок Рг (V | 5,) к оценкам кг (V | 5, ), исходя из определения плотности распределения кг (V15,) как производной от функции ¥г (V | 5,) [3].

В результате получаем двухэтапную процедуру обучения. На первом этапе по обучающим выборкам ^(,?1), ^(,?2),..., ^(м ) строятся эмпирические функции распределения Рг (V | 5, ) дая всех классов образов 5 = {51, 52, ., 5М}. На втором этапе по эмпирическим функциям Рг (V | 5,) формируются оценки плотностей вероятностей кг (V | 5,), которые и становятся эталонными описаниями классов.

Рассмотрим принципы реализации первого этапа обучения КСКД. Процесс формирования клавиатурного эталона образцов некоторого 8;-класса будем трактовать как многомерный случайный процесс Ф^) (мерности г), представляющий собой случайные изменения во времени признака V. При этом будем полагать (возможно, с некоторым приближением), что случайный процесс фф^^удовлетворяет условию эргодичности.

Для одномерного случайного процесса ф ) можно получить соответствующую ему оценку одномерной функции распределения клавиатурных параметров пользователя 5,-класса Рг | 5,) - как отношение суммарного времени пре-

Ф)

пи!и прицела

тельности реализации Т [3]:

бывания реализации случайного процесса ф)(^) под некоторым уровнем V к дли-

Кг ( ! )= Т Ък1к ,

где 4 - длительность к-го выброса процесса ф)(^) под уровнем V.

ф ’<

наблюдаемого по координате Vj вектора V, может быть такой, как показана на рис. 2.

Например, временная диаграмма одномерного случайного процесса ф ),

Т

Рис. 2. Временная диаграмма одномерного случайного процесса

На рис. 3 приведен график оценки функции распределения Рг V | 5,) случайного процесса Ф)(^), показанного на рис. 2.

0,5

Рис. 3. График функции распределения ¥г

Для многомерного случайного процесса фф) соответствующую ему оценку многомерной функции распределения Рг (V | 5,) биометрических параметров 5- -бывания реализации случайного процесса ) внутри области, ограниченной некоторой гиперплоскостью Р(У), к длительности реализации Т:

К О, )=т

где (к - длительность к-го выброса случайного процесса ) внутри о бласти,

ограниченной гиперплоскостью Р(У).

Доказано [3], что оценка (2) является несмещенной и состоятельной.

На этом заканчивается первый этап обучения КСКД.

На втором этапе обучения по эмпирическим функциям Рг (V | 5,) формируются оценки плотностей вероятностей кг ( | 5,), которые и становятся эталон-

V

1

V

0

1

2

3

4

5

ными описаниями классов. Непосредственный переход от Кг

по правилам численного дифференцирования неприемлем. Известные методы численного дифференцирования не обеспечивают требуемой сходимости, поскольку исходно являются некорректными (мадые вариации дифференцируемой

).

использование операторных оценок плотности вероятности кг (V | ), основан-

ных на аппроксимации оператора дифференцирования [3].

, -ности кг (V | 5,), сводятся к следующему. В г-мерном пространстве V биометрических параметров вводятся в рассмотрение точки

^^+тЬ,

где VeVг - произвольная точка пространства V, в которой делается оценка плоности );

Ъ=ке, е=(1, 1, ..., 1)т- единичный г-мерный вектор; т = -Ы, -Ы+1,...,Ы-1,Ы.

Величины к (шаг квантования) и N (количество шагов) являются дополни,

позволяют повысить точность приближения оценки ) К истинной

ПЛОТНОСТИ ) .

Множество точек {^1 образует в пространстве V гиперкубическую решетку, равномерно заполняющую гиперкуб со сторонами длиной 2Ш, точка V находится в центре гиперкуба. Точки Vm не обязательно совпадают с векторами обучающей выборки ^, . ..,^}.

Значения эмпирической функции распределения Рг (Vm) в точках Vm, т = 0,

±1, ..., образуют поверхность в (г+1)-мерном пространстве, которая аппроксимируется затем гиперплоскостью Б^). Параметры гиперплоскости Б^) рассчитываются из условия минимума суммы квадратов отклонений Б^) от Ег (гт):

2Ш=-N [(V,) - 0(У)] ^ ШІП.

(г = 1) -

ванности компонент вектора V полное выражение оценки плотности вероятности

к(у) в точке V имеет вид

\ ^ т • К

М'(У )= 3Лш

^ш=- N

N (N +1)(2 N + 1)И

г- -

:

.

Аналогичную оценку можно получить и для общего случая, при наличии корреляции между компонентами вектора V. При этом по каждой мерности

= 1, г выбирается свой размер шага к и количество шагов N. Эти выражения [3] - . ,

при одновременном выполнении условий к —> 0 N —> х среднеквадратичная ошибка аппроксимации оператора дифференцирования сходится к нулю.

,

Кг

в сравнении с другими известными непараметрическими методами оценивания плотности вероятности, а также методами прямого численного дифференцирования функций распределения Рг (V | 5,) дает более высокую асимптотическую точность оценивания плотности Кг (v!s1).

Имея оценки ПЛОТНОСТИ Кг (V | 5, ), 5, = 51, ям , можно строить решающее

правило для принятия аутентификационного решения.

с = К г

К г

где Кг (V | эх) - оценка плотности распределения биометрических параметров

Г

и.

V ) неизвестного пользователя;

(V | эс) - оценка плотности распределения биометрических параметров

Г

«своего» пользователя. ,

* =

, апёе N > N1-;

*\, апёе N < N

где С - значение порога, выбираемое с учетом ошибок первого рода.

Предложенный подход к аутентификации пользователей по КП отличается от известных наличием двухэтапной процедуры обучения. На первом этапе по обучающим выборкам строятся эмпирические функции распределения клавиатурных

,

оценки плотностей вероятностей, которые и становятся эталонными описаниями классов. Основное преимущество такого подхода состоит в том, что значения эмпирической функции распределения известны во всех точках области ее определения, что невозможно при прямом оценивании плотности распределения. Использование операторных оценок плотности распределения клавиатурных параметров в сравнении с другими непараметрическими методами дает существенно более

высокую асимптотическую точность оценивания плотности, а в конечном итоге и точность клавиатурной аутентификации.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

3. Брюхомицкий Ю.А., Казарин М.Н. Параметрическое обучение биометрических систем контроля доступа / Вестник компьютерных и информационных технологий. - М.: Изд-во Машиностроение, 2006. - № 2 (20). - С. 6-13.

4. Брюхомицкий Ю.А. Классификация нестационарных вероятностных

биометрических параметров личности // Известия ЮФУ. Технические науки. - 2008. - №8 (85) - С. 147 - 154.

5. Фомин ЯЛ., Тарловский ГР. Статистическая теория распознавания образов. - М.: Радио и связь, 1986. - 264 с.

Брюхомицкий Юрий Анатольевич

Технологический институт Федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет»

. .

E-mail: bya@tsure.ru.

347928, . , . , 2.

Тел.: 8 (8634) 371-905.

Кафедра безопасности информационных технологий; доцент.

Bryukhomitsky Yuri Anatolyevich

Taganrog Institute of Technology - Federal State-Owned Educational Establishment of

Higher Vocational Education “Southern Federal University”.

E-mail: bya@tsure.ru.

2, Chekhova st., Taganrog, 347928, Russia.

Phone: +7 (8634) 371-905.

Department of IT-Security; associate professor.

УДК 681.324

Г.Э. Абрамов

МОДЕЛЬ АНОМАЛЬНОГО ПОВЕДЕНИЯ СИСТЕМЫ НА ОСНОВЕ ВЕРОЯТНОСТНЫХ СУФФИКСНЫХ ДЕРЕВЬЕВ

Описывается метод применения вероятностных суффиксных деревьев для обнаружения аномального поведения программ. Используется «отпечаток» нормального поведения приложении с целью в дальнейшем обнаружить аномальное поведение как нечто, отклоняющееся от модели. В качестве основной модели используется вероятностные суффиксные деревья.

Вероятностное суффиксное дерево; РБТ, обнаружение аномального .