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

Последовательный поиск

Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента. Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В, а Si - количество сравнений, необходимое для его поиска, то

n

Max{А} = max{ Si, i=1,n }; Avg{А} = Pi Si.

i=1

Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядке их расположения, пока не найдется элемент равный V. Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел за пределы списка. Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.

Бинарный поиск

Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка.

Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.

Интерполяционный поиск

Алгоритм, называемый интерполяционным поиском: Если известно, что К лежит между Kl и Ku, то следующую пробу делаем на расстоянии (u-l)(K-Kl)/(Ku-Kl) от l, предполагая, что ключи являются числами, возрастающими приблизительно в арифметической прогрессии.

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

Самоорганизующиеся файлы

Закон Парето или Принцип Парето в наиболее общем виде формулируется как «20 % усилий дают 80 % результата, а остальные 80 % усилий — лишь 20 % результата».

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

,

где — число в диапазоне от 0 до 1,

k — значение величины (в нашем случае — количество обращений к данной записи),

р — количество записей, к которым происходит k обращений,

с — нормализующий коэффициент (правило "80—20" соответствует = = log80/log20 = 0,1386) или его частному случаю, распределению Зипфа: р = c / k.

Одним из следствий закона Парето является концепция «самоорганизующегося файла» — для ускорения поиска в несортированном массиве предлагается передвигать записи ближе к началу массива. Если обращения к массиву распределены в соответствии с законом Зипфа, наиболее востребованные записи концентрируются в начале массива и поиск ускоряется в c/lnN раз, где N — размер массива, а с — константа, зависящая от используемой стратегии перемещения элементов.

Основные понятия защиты информации (субъекты, объекты, доступ, граф доступов, информационные потоки). Постановка задачи построения защищённой автоматизированной системы. Ценность информации.

 

Информация — сведения (сообщения, данные) независимо от формы их предоставления. (ФЗ «Об информации, информационных технологиях и о защите информации» №149-ФЗ от 27.07.2006)

Защищаемая информация — информация, являющаяся предметом собственности и подлежащая защите в соответствии с требованиями правовых документов или требованиями, устанавливаемыми собственником информации.

Примечание: Собственником информации может быть — государство, юридическое лицо, группа физических лиц, отдельное физическое лицо.

Защита информации — деятельность по предотвращению утечки защищаемой информации, несанкционированных и непреднамеренных воздействий на защищаемую информацию. (ГОСТ Р 50922-2006. Защита информации. Основные термины и определения)

Доступ к информации —возможность получения информации и ее использования. (ФЗ «Об информации, информационных технологиях и о защите информации» №149-ФЗ от 27.07.2006)

Согласно РД ГТК. Защита от несанкционированного доступа к информации. Термины и определения (30.03.1993):

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

Правила разграничения доступа (ПРД) — совокупность правил, регламентирующих права доступа субъектов доступа к объектам доступа.

Субьект доступа — лицо или процесс, действия которого регламентируются правилами разграничения доступа.

Объект доступа — единица информационного ресурса автоматизированной системы, доступ к которой регламентируется правилами разграничения доступа.

Матрица доступа — таблица, отображающая правила разграничения доступа.

 

В теории защиты информации также имеются следующие определения:

Объект доступа – пассивная сущность, используемая для хранения или получения информации.

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

 

Граф доступов – граф, который определяет доступ субъектов к объектам.

 

Можно сформулировать следующие аксиомы защищенных АС:

Аксиома 1. В защищенной АС всегда присутствует активная компонента (субъект), выполняющая контроль операций субъектов над объектами. Данная компонента фактически отвечает за реализацию некоторой политики безопасности.

Аксиома 2. Для выполнения в защищенной АС операций над объ­ектами необходима дополнительная информация (и наличие содержа­щего ее объекта) о разрешенных и запрещенных операциях субъектов с объектами.

Аксиома 3. Все вопросы безопасности информации описываются доступами субъектов к объектам.
Аксиома 4. Субъекты в АС могут быть порождены только актив­ной компонентой (субъектами) из объектов.

Определение: Потоком информации между объектом Оm и объ­ектом Oj называется произвольная операция над объектом Oj, реали­зуемая в субъекте Si и зависящая от Оm.

В определении подчеркнуто, что поток инфор­мации рассматривается не между субъектом и объектом, а между объ­ектами. Активная роль субъекта выражается в реализации данного потока.

 

Постановка задачи построения защищённой автоматизированной системы

АС — система, состоящая из персонала и комплекса средств автоматизации его деятельности, реализующая информационную технологию выполнения установленных функций. (ГОСТ 34.003-90. Автоматизированные системы. Термины и определения.)

Защищенная автоматизированная система — автоматизированная система, в которой реализован комплекс средств защиты. (РД ГТК. Защита от несанкционированного доступа к информации. Термины и определения (30.03.1993))

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

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

Система защиты информации — совокупность органов и/или исполнителей, используемая ими техника защиты информации, а также объекты защиты, организованные и функционирующие по правилам, установленным соответствующими правовыми, организационно-распорядительными и нормативными документами по защите информации. (ГОСТ Р 50922-2006. Защита информации. Основные термины и определения)

Ценность информации

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

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

Информация, искаженно представляющая действительность (недостоверная информация), может нанести владельцу значи­тельный материальный и моральный ущерб. Если информация искажена умышленно, то ее называют дезинформацией.

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

Для обозначения ценности конфиденциальной коммерческой информации используются три категории:

- «коммерческая тайна - строго конфиденциально»;

- «коммерческая тайна - конфиденциально»;

- «коммерческая тайна».

Используется и другой подход к градации ценности коммер­ческой информации:

- «строго конфиденциально - строгий учет»;

- «строго конфиденциально»;

- «конфиденциально».

Ценность информации изменяется во времени.

Распространение информации и ее использование приводят к изменению ее ценности и цены. Характер изменения ценности во времени зависит от вида информации. В большинстве случаев ценность со временем уменьшается – информация стареет.

Старение информации Се можно представить выражением вида:

где - ценность информации в момент ее возникновения (создания);

t- время от момента возникновения информации до момента ее использования;

t_жц - продолжительность жизненного цикла информации (от момента возникновения до момента устаревания).

Следовательно, за время жизненного цикла ценность информации уменьшается до 0.1 первоначальной величины.

В зависимости от продолжительности жизненного цикла коммерческая информация классифицируется следующим образом:

- оперативно-тактическая, теряющая ценность примерно по 10% в день;

- стратегическая информация, ценность которой убывает примерно 10% в месяц.

Информация покупается и продается.

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

Информация м.б. получена тремя путями:

- проведением НИР.;

- покупкой информации;

- противоправным добыванием информации.

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

При копировании, не изменяющем информационные параметры носителя, количество информации не меняется, а цена снижается.

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

Угрозы безопасности информации. Угрозы конфиденциальности, целостности, доступности автоматизированных систем. Понятие политики безопасности. Дискреционная политика безопасности. Мандатная политика безопасности. Мандатная политика целостности.

 

Безопасность информации – состояние защищенности информации, при котором обеспечены ее конфиденциальность, доступность и целостность. (ГОСТ Р 50922-2006. Защита информации. Основные термины и определения.)

Безопасность информации – состояние защищенности информации, обрабатываемой средствами вычислительной техники или автоматизированной системы, от внутренних или внешних угроз. (РД ГТК. Защита от несанкционированного доступа к информации. Термины и определения (30.03.1993))

Кофиденциальность – обязательное для выполнения лицом, получившим доступ к определенной информации, требование не передавать такую информацию третьим лицам без согласия ее обладателя. (ФЗ «Об информации, информационных технологиях и о защите информации» №149-ФЗ от 27.07.2006)

Целостность информации – способность средства вычислительной техники или автоматизированной системы обеспечивать неизменность информации в условиях случайного и (или) преднамеренного искажения (разрушения). (РД ГТК. Защита от несанкционированного доступа к информации. Термины и определения (30.03.1993))

Доступность информации – состояние информации, при котором субъекты, имеющие право доступа, могут реализовать их беспрепятственно. (Рекомендации по стандартизации «Информационные технологии. Основные термины и определения в области технической защиты информации» (Р 50.1.053-2005))

 

Угроза безопасности информации – совокупность условий и факторов, создающих потенциальную или реально существующую опасность нарушения конфиденциальности, доступности и (или) целостности информации. (ГОСТ Р 50922-2006. Защита информации. Основные термины и определения.)

Выделяют три группы угроз:

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

Угроза нарушения целостности. Предполагает любое незапланированное и несанкционированное изменение информации, хранящейся в системе или передаваемой из одной системы в другую. Санкционированными изменениями считаются те, которые сделаны уполномоченными лицами с обоснованной целью (например, запланированное изменение документов или базы данных). Целостность может быть нарушена в результате преднамеренных и непреднамеренных действий человека, а также – в результате возникновения случайной ошибки программного или аппаратного обеспечения.

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

 

Политика безопасности информации в организации – совокупность документированных правил, процедур, практических приемов или руководящих принципов в области безопасности информации, которыми руководствуется организация в своей деятельности. (ГОСТ Р 50922-2006. Защита информации. Основные термины и определения.)

 

Дискреционная политика безопасности – политика безопасности осуществляемая на основании заданного администратором множества разрешенных отношений доступа.

Основой дискреционной политики безопасности яв­ляется дискреционное управление доступом, которое определяется двумя свойствами:

- все субъекты и объекты должны быть идентифицированы;

- права доступа субъектов к объектам определяются на основа­нии некоторого внешнего по отношению к системе правила (заранее не закладывается в систему).

Достоинства: относительно простая реализация механизмов за­щиты. (Большинство распространенных в настоящее время АС обеспечивают выполнение положений именно дан­ной ПБ).

Пример реализации дискреционной политики в АС – матрица доступов, строки которой соответствуют субъектам доступа системы, а столбцы – объектам; элементы матрицы характеризуют права доступа.

Недостаток: статичность модели - не учитывает динамику из­менений состояния АС, не накладывает ограничений на состояния системы.

При использовании данной политики перед МБО (монитором безопасности объектов), который при санкциони­ровании доступа субъектов к объектам руководствуется некоторым набором правил, стоит алгоритмически неразрешимая задача: проверить приведут ли его действия к нарушению безопасности или нет.

В то же время имеются модели АС, реализующих дискреционную политику безопасности (например, модель Take-Grant), которые предоставляют алгоритмы проверки безопасности.

Так или иначе, матрица доступов не является тем механизмом, кото­рый бы позволил реализовать ясную и четкую систему защиты информации в АС.

 

Мандатная политика безопасности – политика безопасности основанная на совокупности предоставления доступа, определенного на множестве атрибутов безопасности субъекта и объекта.

Основу мандатной (полномочной) политики безопасности составляет мандатное управление доступом, которое подразумевает, что:

- все субъекты и объекты системы должны быть однозначно идентифицированы;

- задан линейно упорядоченный набор меток секретности;

- каждому объекту системы присвоена метка секретности, определяющая ценность содержащейся в нем информации - его уровень секретности в АС;

- каждому субъекту системы присвоена метка секретности, определяющая уровень доверия к нему в АС - максимальное значение метки секретности объектов, к которым субъект имеет доступ; метка секретности субъекта называется его уровнем доступа.

Основная цель мандатной политики безопасности – предотвращение утечки информации от объектов с высоким уровнем доступа к объектам с низким уровнем доступа, т.е. противодействие возникновению в АС информационных каналов сверху вниз.

Достоинство МПБ – более высокая степень надежности, правила ясны и понятны. Это связано с тем, что МБО такой системы должен отслеживать не только правила доступа субъектов системы к объектам, но и состояния самой АС. Таким образом, каналы утечки в системах данного типа не заложены в нее непосредственно (что мы наблюдаем в положениях предыдущей политики безопасности), а могут появиться только при практической реализации системы вследствие ошибок разработчика. В дополнении к этому правила мандатной политики безопасности более ясны и просты для понимания разработчиками и пользователями АС, что также является фактором, положительно влияющим на уровень безопасности системы.

Недостатки – реализация систем с политикой безопасности данного типа довольно сложна и требует значительных ресурсов вычислительной системы.

В качестве примера модели АС, реализующих мандатную политику безопасности можно привести - модель Белла-Лапалуда. В рамках данной модели доказывается важное утверждение, указывающее на принципиальное отличие систем, реализующих мандатную защиту, от систем с дискреционной защитой: если начальное состояние системы безопасно, и все переходы системы из состояния в состояние не нарушают ограничений, сформулированных политикой безопасности, то любое состояние системы безопасно.