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

- защитить авторский маркер в текстовом виде от внесения изменений извне;

- представить его в зашифрованном виде.

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

Преимущества данного метода: простота реализации, работа на уровне исходного кода.

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

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

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

Довольно широкое распространение получил второй метод защиты авторских маркеров от несанкционированного доступа. Суть его заключается в том, чтобы представить защищаемую информацию в виде, отличном от текстового. Такое представление достигается за счет использования различных алгоритмов шифрования. Тем самым Злоумышленнику затруднен поиск расположения в выполнимом файле авторской строки, форма представления которой ничем не отличается от остального кода программы. В то же время для отображения маркера в нормальном виде необходимо наличие в программе механизма дешифрования. Естественно, чем сложнее алгоритм шифрования, тем больше ресурсов придется затратить на его реализацию. Из-за большого разнообразия существующих довольно сложных алгоритмов эта тема подробно рассматриваться не будет.

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

`Автор Вильнев Н.А., Минск 1990',

заданная константой AuthorSt после побайтного применения операции XOR со значением $AA, преобразуется в строку

AutShSt = #42#8#72#4#64#138#28#2#1#70#7#91#8#138#39#132

#42#132#134#138#38#2#7#75#0#138'ыууъ'

Представим схему кодирования литеры `A', шифрование:

`A' -> #128 -> $80 XOR $AA = $2A -> #42,

и дешифрование:

#42 -> 2A XOR $AA = $80 -> #128 -> `A'

Небольшое усовершенствование в правой части при использовании операции XOR, а именно - добавление контекстной зависимости (вместо $AA использовать $AA+1) позволит повысить надежность данного вида защиты. Хорошие результаты в этом направлении могут быть получены при совмещении двух представленных методов защиты. Преимущество последнего метода заключается в использовании зашифрованного представления защищаемой информации в исполнительном файле, но при этом увеличивается доля "ручных" расчетов и в зависимости от алгоритма усложняется реализация. Нельзя не отметить, что оба рассмотренных метода защиты можно реализовать, не выходя за стандартные возможности используемого языка программирования.

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

- защиту от пошагового тестирования в сложных отладчиках;

- защиту от реассемблирования исполнительного файла в исходный текст на языке Ассемблер.

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

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

Задание по работе

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

Вариант 1

Защита программы на стадии выполнения:

запрос с требованием сообщить пароль (дважды);

реакция на неправильный ответ (уничтожить ряд файлов, уничтожить содержимое дискеты);

реакция на правильный ответ.

Вариант 2

Защита программы на стадии выполнения:

запросить фамилию;

проанализировать ответ, сверив его со списком фамилий в системе;

если введенная фамилия имеется в списке системы, продолжить работу;

если нет, то уничтожить ряд файлов.

Вариант 3

Защита авторского права:

вывод авторского маркера в верхнюю строку экрана при нажатии ALT+A

Вариант 4

Защита авторского маркера в текстовом виде от внесения изменений извне с помощью метода контрольных сумм:

проверка текущей контрольной суммы с эталонным значением;

реакция на несоответствие.

Вариант 5

Защита авторского маркера с помощью логической операции XOR:

побайтное применение операции XOR со значением $AA (шифрование и дешифрование).

Вариант 6

Защита данных:

Шифрование информации исходного файла (побайтное применение операции XOR с ключом в виде строки, веденной пользователем);

Декодирование для преобразования зашифрованного файла в исходном виде (побайтное применение операции XOR с ключом в виде строки, веденной пользователем);

Контрольные вопросы.

1. Что предполагает организационный аспект защиты готовых программных продуктов и данных?

2. Что предполагает технологический аспект защиты готовых программных продуктов и данных?

3. Привести примеры сценариев защиты программы на стадии выполнения.

4. Какая информация содержится в авторском маркере?

5. Какие три требования авторов должен знать пользователь при приобретении программного продукта?

6. В чем заключается метод контрольных сумм?

7. Как осуществляется шифрование информации?

3. Разработка программ оценки сложности программного обеспечения на базе отдельных метрик размера программ

Лабораторная работа №3

Цель работы: Изучить метрики размера программ и создать ПО для оценки сложности тестируемой программы.

Краткие теоретические сведения и методические указания к выполнению работы

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

Рис.1. Область применения метрической теории программ

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

Метрики всех четырех групп используют, главным образом, для прогнозирования и оценки сложности и корректности программ. К ним относят метрики Холстеда, Джилба, Маккейба, Майерса, Чепина и некоторые другие. Метрики внутримодульных и межмодульных связей являются основными характеристиками сложности программных комплексов в фазе проектирования. Аккумулируя поток управления и потока данных, метрики внутримодульных и межмодульных связей образуют шкалы функциональной прочности (связности) и сцепления модулей. Рассматривая сложность как антипод надежности, возможна косвенная оценка надежности по принципу: "чем меньше сложность, тем больше надежность". При этом задача проектирования надежного программного обеспечения сводится к достижению максимальной прочности и минимального сцепления модулей. Исторически первыми появились математические модели, представляющие метрики программ, основанных на анализе лексики и потока управления программ, реализующих заданный алгоритм. Типичными представителями таких метрик являются метрики Холстеда и Маккейба. Типичными представителями метрик, основанными на лексическом анализе, являются метрики Холстеда и Маккейба.

Метрика программмного обеспемчения (англ.software metric) - это мера, позволяющая получить численное значение некоторого свойства программного обеспечения или его спецификаций.

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

Характеристика качества программы - понятие, отражающее отдельные факторы, влияющие на качество программ и поддающиеся измерению.

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

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

Критерий должен:

1) численно характеризовать основную целевую функцию программы;

2) обеспечивать возможность определения затрат, необходимых для достижения требуемого уровня качества, а также степени влияния на показатель качества различных внешних факторов;

3) быть по возможности простым, хорошо измеримым и иметь малую дисперсию.

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

В исследовании метрик ПО различают два основных направления:

1) поиск метрик, характеризующих наиболее специфические свойства программ, т.е. метрик оценки самого ПО;

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

По виду информации, получаемой при оценке качества ПО метрики можно разбить на три группы:

1) метрики, оценивающие отклонение от нормы характеристик исходных проектных материалов. Они устанавливают полноту заданных технических характеристик исходного кода;

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

3) метрики, по которым принимается решение о соответствии конечного ПО заданным требованиям. Они позволяют оценить соответствие разработки заданным требованиям.

Основные направления применения метрик

В настоящее время в мировой практике используется несколько сотен метрик программ. Существующие качественные оценки программ можно сгруппировать по шести направлениям:

1) оценки топологической и информационной сложности программ;

2) оценки надежности программных систем, позволяющие прогнозировать отказовые ситуации;

3) оценки производительности ПО и повышения его эффективности путем выявления ошибок проектирования;

4) оценки уровня языковых средств и их применения;

5) оценки трудности восприятия и понимания программных текстов, ориентированные на психологические факторы, существенные для сопровождения и модификации программ;

4) оценки производительности труда программистов для прогнозирования сроков разработки программ и планирования работ по созданию программных комплексов.

Метрические шкалы

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

Метрики сложности программ

При оценке сложности программ, как правило, выделяют три основные группы метрик:

1) метрики размера программ;

2) метрики сложности потока управления программ;

3) метрики сложности потока данных программ.

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

Оценки первой группы наиболее просты и, очевидно, получили наибольшее распространение. Традиционной характеристикой размера программ является количество строк исходного текста. Однако при этом возникает ряд проблем. Одна из них - что считать строкой? 1) функциональные операторы? 2) операторы объявления переменных и функциональные операторы? 3) все операторы, включая комментарии? В дальнейшем под строкой понимается любой оператор программы, поскольку реально при оценке размера программы используется информация именно о количестве операторов. Это правильно, так как именно оператор, а не отдельно взятая строка является тем интеллектуальным "квантом" программы, опираясь на который можно строить метрики сложности её создания.

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

Размерно - ориентированные метрики (показатели оценки объема) LOC-оценка (Lines Of Code)

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

· общие трудозатраты (в человеко-месяцах, человеко-часах);

· объем программы (в тысячах строках исходного кода -LOC);

· стоимость разработки;

· объем документации;

· ошибки, обнаруженные в течение года эксплуатации;

· количество людей, работавших над изделием;

· срок разработки.

На основе этих данных обычно подсчитываются простые метрики для оценки производительности труда (KLOC/человеко-месяц) и качества изделия.

Эти метрики не универсальны и спорны, особенно это относится к такому показателю как LOC, который существенно зависит от используемого языка программирования.

Пример:

На наш взгляд оценка по количеству строк в коде влечёт за собой соблазн написать побольше строк, дабы взять побольше денег. Разумеется, об оптимизации в таком продукте никто уже думать не станет. Вспомним историю о том, как планетарный центр аутсорсинга - Индия, после того, как заказчики вменили им метрику LOC, на второй день показал удвоение и утроение строк кода.

Количество строк исходного кода (Lines of Code - LOC, Source Lines of Code - SLOC) является наиболее простым и распространенным способом оценки объема работ по проекту.

Изначально данный показатель возник как способ оценки объема работы по проекту, в котором применялись языки программирования, обладающие достаточно простой структурой: "одна строка кода = одна команда языка". Также давно известно, что одну и ту же функциональность можно написать разным количеством строк, а если возьмем язык высокого уровня (С++, Java), то возможно и в одной строке написать функционал 5-6 строк - это не проблема. И это было бы полбеды: современные средства программирования сами генерируют тысячи строк кода на пустяковую операцию.

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

В зависимости от того, каким образом учитывается сходный код, выделяют два основных показателя SLOC:

1) количество "физических" строк кода - SLOC (используемые аббревиатуры LOC, SLOC, KLOC, KSLOC, DSLOC) - определяется как общее число строк исходного кода, включая комментарии и пустые строки (при измерении показателя на количество пустых строк, как правило, вводится ограничение - при подсчете учитывается число пустых строк, которое не превышает 25% общего числа строк в измеряемом блоке кода).

2) количество "логических" строк кода - SLOC (используемые аббревиатуры LSI, DSI, KDSI, где "SI" - source instructions) - определяется как количество команд и зависит от используемого языка программирования. В том случае, если язык не допускает размещение нескольких команд на одной строке, то количество "логических" SLOC будет соответствовать числу "физических", за исключением числа пустых строк и строк комментариев. В том случае, если язык программирования поддерживает размещение нескольких команд на одной строке, то одна физическая строка должна быть учтена как несколько логических, если она содержит более одной команды языка. Для метрики SLOC существует большое число производных, призванных получить отдельные показатели проекта, основными среди которых являются:

1. число пустых строк;

2. число строк, содержащих комментарии;

3. процент комментариев (отношение строк кода к строкам комментария, производная метрика стилистики);

4. среднее число строк для функций (классов, файлов);

5. среднее число строк, содержащих исходный код для функций (классов, файлов);

6. среднее число строк для модулей.

Итого по SLOC

Потенциальные недостатки SLOC, на которые нацелена критика:

· некрасиво и неправильно сводить оценку работы человека к нескольким числовым параметрам и по ним судить о производительности. Менеджер может назначить наиболее талантливых программистов на сложнейший участок работы; это означает, что разработка этого участка займёт наибольшее время и породит наибольшее количество ошибок, из-за сложности задачи. Не зная об этих трудностях, другой менеджер по полученным показателям может решить, что программист сделал свою работу плохо;

· метрика не учитывает опыт сотрудников и их другие качества;

· искажение: процесс измерения может быть искажён за счёт того, что сотрудники знают об измеряемых показателях и стремятся оптимизировать эти показатели, а не свою работу. Например, если количество строк исходного кода является важным показателем, то программисты будут стремиться писать как можно больше строк и не будут использовать способы упрощения кода, сокращающие количество строк;

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

И главное помнить: метрика SLOC не отражает трудоемкости по созданию программы.

Пример:

В одной из компаний при внедрении применили данную метрику - считали строки кода. Руководитель организации был в отпуске, но по возвращении из него решил воспользоваться прозрачностью и трассируемостью изменений и посмотреть, как же идут дела в проектах у его менеджеров. И чтоб полностью войти в курс, опустился на самый низкий уровень (то есть не стал оценивать плотность дефектов, количество исправленных багов) - на уровень исходных текстов. Решил посчитать, кто и сколько строк написал. А чтоб было совсем весело - соотнести количество рабочих дней в неделю и количество написанного кода (логика проста: человек работал 40 часов в неделю, значит, должен много чего написать). Естественно, нашелся человек, который за неделю написал всего одну строку, даже не написал, а только откорректировал существующую…

Гневу руководителя не было предела - нашел бездельника! И плохо было бы программисту, если бы менеджер проекта не объяснил, что была найдена ошибка в программе, нашел ее VIP- клиент, ошибка влияет на бизнес клиента и ее нужно было срочно устранить, для этого был выбран вот этот конкретный исполнитель, который развернул стенд, залил среду клиента, подтвердил проявление ошибки и начал ее искать и устранять. Естественно, в конце концов, он поменял фрагмент кода, в котором было неправильное условие и все заработало.

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

К группе оценок размера программ можно отнести также и метрику Холстеда. За базу принят подсчёт количества операторов и операндов, используемых в программе, то есть определение размера программы.

Основу метрики Холстеда составляют четыре измеряемые характеристики программы:

-- число уникальных операторов программы, включая символы-разделители, имена процедур и знаки операций (словарь операторов);

-- число уникальных операндов программы (словарь операндов);

-- общее число операторов в программе;

-- общее число операндов в программе.

Опираясь на эти характеристики, получаемые непосредственно при анализе исходных текстов программы, Холстед вводит следующие оценки:

словарь программы

(1)

длину программы

(2)

объём программы

 (3)

Смысл оценок и очевиден, поэтому рассмотрим .

Количество символов, используемых при реализации некоего алгоритма, определяется в числе прочих параметров и словарём программы , представляющим собой минимально необходимое число символов, обеспечивающих реализацию алгоритма. Рассматривая эту оценку, некоторые авторы утверждают, что объём программы, выраженной формулой (3), характеризует "число двоичных разрядов, то есть бит, необходимых для записи программы". При этом речь идёт о физической длине программы в битах. Холстед не конкретизирует, что именно понимается под термином бит: логическая единица информации или физическая. Однако из последующих выводов относительно метрических характеристик понятности и уровня программы, в которых М. Холстед оперирует измерением объёма программ, можно сделать вывод, что под битом подразумевается логическая единица информации - символ, оператор, операнд, то есть то, чем непосредственно оперирует программист при создании программ.

Далее М. Холстед вводит - теоретический словарь программы, то есть словарный запас, необходимый для написания программы, с учётом того, что необходимая функция уже реализована в данном языке и, следовательно, программа сводится к вызову этой функции. Например, согласно М. Холстеду, возможное осуществление процедуры выделения простого числа могло бы выглядеть так:

CALL SIMPLE(x,y),

где y - массив численных значений, содержащий искомое число х.

Теоретический словарь в этом случае будет состоять из

:{CALL, SIMPLE(…)},=2

:{x,y},=2,

а его длина, определяемая как

, (4)

будет равняться 4.

Используя , Холстед вводит оценку :

, (5)

с помощью которой описывается потенциальный объём программы, соответствующий максимально компактному тексту программы, реализующей данный алгоритм.

На основании этих оценок вводятся "производные" характеристики, определяющие уже не размер программы, а её структуру и стилистику.

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

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

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

Рассмотрим метрику сложности программ, получившую название "подсчет точек пересечения", авторами которой являются М. Вудвард, М. Хенел и др. Метрика ориентирована на анализ программ, при создании которых использовалось неструктурное кодирование на таких языках, как язык ассемблера и фортран. Вводя эту метрику, ее авторы стремились оценить скорее взаимосвязи между физическими местоположениями управляющих переходов, чем просто их последовательность в программе. Удобство метрики в том, что ее легко представить численными соотношениями.

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

В графе программы, где каждому оператору соответствует вершина, то есть не исключены линейные участки, при передаче управления от вершины a и b номер оператора a равен , а номер оператора b - . Точка пересечения дуг появляется, если

&|

&. (6)

Иными словами, точка пересечения дуг возникает в случае выхода управления за пределы пары вершин рис. 2.

Рис. 2. Пример точки пересечения дуг графа программы

Количество точек пересечения дуг графа программы дает характеристику неструктурированности программы. Эта характеристика хорошо согласуется с определением Маккейба для отклонений от структурного построения программ.

Задание по работе

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

Вариант 1

Определить сложность по размеру программы. Посчитать количество строк исходного текста (под строкой понимать любой оператор программы). Посчитать метрику SLOC, основываясь на LOC-оценке (Lines Of Code).

Вариант 2

Определить размер программы используя метрику Холстеда (за базу принять подсчёт количества операторов и операндов, используемых в программе).

Вариант 3

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

Вариант 4

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

Вариант 5

Разработать программу оценки сложности ПО на основе метрики сложности программ, получившую название "подсчет точек пересечения".

Вариант 6

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

Контрольные вопросы

1. Что такое метрика программного обеспечения?

2. Дать определение понятия "качество ПО".

3. Дать определение характеристики качества программ.

4. Что такое критерий качества программы?

5. Перечислить характеристики критериев качества ПО?

6. Два основных направления в исследовании метрик ПО.

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

8. Назвать существующие качественные оценки программ.

9. Три основные группы метрик сложности программ.

10. Размерно-ориентированные метрики.

11. Дать понятие метрики М. Холстеда.

12. Дать понятие метрики Т. Джилба.

13. Определить метрику, получившую название "подсчет точек пересечения".

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

Лабораторная работа №4

Цель работы: Изучить метрики сложности потока управления программ.

Краткие теоретические сведения и методические указания к выполнению работы.

Метрики цикломатической сложности по Маккейбу

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

Метрики второй группы базируются на анализе управляющего графа программы. Представителем данной группы является метрика Маккейба.

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

Стало традиционным представление программ в виде управляющего ориентированного графа G=(V,E), где V - вершины, соответствующие операторам, Е - дуги, соответствующие переходам. В дуге (u,v)вершина v является исходной, а u - конечной. При этом u непосредственно следует за v, а v непосредственно предшествует u. Если путь от v до u состоит более чем из одной дуги, тогда u следует за v, а v предшествует u.

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

Для вычисления цикломатического числа Маккейба z(G) применяется формула

z(G)=e-v+2p, (7)

где е - число дуг ориентированного графа Q; v - число вершин; р - число компонентов связности графа.

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

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

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

Существует значительное количество модификаций показателя цикломатической сложности.

· "Модифицированная" цикломатическая сложность - рассматривает не каждое ветвление оператора множественного выбора (switch), а весь оператор как единое целое.

· "Строгая" цикломатическая сложность - включает логические операторы.

· "Упрощенное" вычисление цикломатической сложности - предусматривает вычисление не на основе графа, а на основе подсчета управляющих операторов.

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



Рис.1. Граф управления программы

Для программ, граф которой изображён на рис.1, цикломатическое число при е=10, v=8, p=1 определяется как z(G)=10-8+2=4. Таким образом, имеется сильно связный граф с четырьмя линейно независимыми контурами:

a-b-c-g-e-h-a;

a-b-c-e-h-a;

a-b-d-f-e-h-a;

a-b-d-e-h-a;

По определению управляющего графа программы, вершины (a-b) и (e-h) следовало бы объединить, но, по сути, это ничего не меняет, т.к. z остаётся без изменений:

z(G)=8-6+2=4.

Цикломатическое число зависит только от количества предикатов, сложность которых при этом не учитывается. Например, имеется два оператора условия:

IF X>0

THEN X=A

и

IF (X>0 & FLAG='1'B) !

(X=0) & FLAG='0'B)

THEN X=A;

ELSE;

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

Исходя из этого, Г. Майерс предложил расширение этой метрики. Суть подхода Г. Майерса состоит в представлении метрики сложности программ в виде интервала [z(G),z(G)+h]. Для простого предиката h=0 для n-местных предикатов h=n-1. Таким образом, первому оператору соответствует интервал [2,2], а второму [2,6].

Рис 2.Граф ветвления

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

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

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

Вершины первой группы назовем принимающими вершинами, а вершины второй - вершинами отбора.

Для получения оценки по методу граничных значений необходимо разбить граф G на максимальное число подграфов G', удовлетворяющих следующим условиям: вход в подграф осуществляется только через вершину отбора; каждый подграф включает вершину (называемую в дальнейшем нижней границей подграфа), в которую можно попасть из любой другой вершины подграфа. Например, вершина отбора соединенная сама с собой дугой-петлей, образует подграф (рис. 3, табл.1).

Рис. 3. Граф программы для анализа ее сложности методом граничных значений

Число вершин, образующих такой подграф, равно скорректированной сложности вершины отбора.

Таблица 1. Подграфы программы

Таблица 2. Скорректированная сложность вершин графа программы

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

, (8)

где - относительная граничная сложность программы; - абсолютная граничная сложность программы; - общее число вершин графа программы.

Таким образом, относительная граничная сложность программы равна . Преимущество метода граничных значений состоит в его чувствительности к конструктивному контексту программ. Это иллюстрирует пример (рис.5).

Рис. 5. Графы программ с одинаковым цикломатическим числом.

Приведенные на рис. 5. графы программ имеют следующие характеристики: циклическое число Маккейба Z(G); расширение Майерса для цикломатического числа Z'(G); количество точек пересечения; методику Джилба CL; относительную методику Джилба cl; уровень вложенности операторов условия CLI; метод граничных значений .

Таблица 3. Сравнение метрик сложности потока управления программ

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

К вариантам цикломатической меры сложности относят также меру Чена

М(G) = (V(G),C,Q),

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

Топологическая мера Чена выражает сложность программы числа пересечений границ между областями, образуемыми блок - схемой программы. Этот подход применим только к структурированным программам, допускающим лишь последовательное соединение управляющих конструкций. Для неструктурированных программ мера Чена существенно зависит от условных и безусловных переходов. В этом случае можно указать верхнюю и нижнюю границы меры. Верхняя - есть m+1, где m - число логических операторов при их гнездовой вложенности. Нижняя - равна 2. Когда управляющий граф программы имеет только одну компоненту связности, мера Чена совпадает с цикломатической мерой Маккейба.

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

N(G) = n *(G) + S Pi,

где n *(G) - модифицированная цикломатическая сложность, вычисленная так же, как и V(G), но с одним отличием: оператор CASE с n- выходами рассматривается как один логический оператор, а не как n - 1 операторов. Рi - глубина вложенности i - той предикатной вершины. Для подсчета глубины вложенности предикатных вершин используется число сфер влияния. Под глубиной вложенности понимается число всех сфер влияния предикатов, которые либо полностью содержатся в сфере рассматриваемой вершины, либо пересекаются с ней. Глубина вложенности увеличивается за счет вложенности не самих предикатов, а сфер влияния. Сравнительный анализ цикломатических и функциональных мер с обсуждаемой для десятка различных управляющих графов программы показывает, что при нечувствительности прочих мер этого класса, мера Пивоварского возрастает при переходе от последовательных программ к вложенным и далее к неструктурированным.

Задание по работе

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

Вариант 1

Оценить сложность программы вычислив цикломатическое число Маккейба z(G) (цикломатическая сложность графа программы):

z(G)=e-v+2p,

где е - число дуг ориентированного графа Q; v - число вершин; р - число компонентов связности графа.

Вариант 2

Оценить сложность программы используя расширение метрики Маккейба (подход Майерса - представлении метрики сложности программ в виде интервала [z(G),z(G)+h].).

Вариант 3

Оценка качества программ по метрике Чена

M(G) = (z(G), C, Q),

где z(G) - цикломатическая сложность Маккейба,

С - количество условий, необходимых для покрытия управляющего графа минимальным числом маршрутов,

Q - степень связности структуры программы и ее протяженности.

Вариант 4

Оценка качества программ по метрике Пивоварского:

N(G) = z*(G) + ,

где z*(G) - модифицированная цикломатическая сложность, вычисленная так же, как и z(G), но с одним отличием:

оператор Case с n- выходами рассматривается как один логический оператор, а не как n - 1 операторов.

Pi - глубина вложенности i - ой предикатной вершины.

Вариант 5

Оценка качества программ по метрике Шнадевида (число путей в управляющем графе)

S =

где Pi - глубина вложенности i-ой предикатной вершины.

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

Вариант 6

Оценка сложности программ по методу граничных значений.

Контрольные вопросы

1) Назвать метрики, которые являются представителями группы метрик сложности потока управления программ.

2) Что такое управляющий граф программы?

3) Что такое цикломатическая сложность графа?

4) Что такое сильносвязный граф?

5) Что такое "модифицированная" цикломатическая сложность графа?

6) Суть подхода Г.Майерса к расширению метрики Маккейба.

7) Оценка сложности программ по методу граничных значений.

8) Что такое отрицательная и положительная степени вершины графа.

9) Какие метрики можно отнести к вариантам цикломатической меры сложности программ?

10) С помощью какой метрики можно посчитать число путей в управляющем графе?

5. Разработка программ оценки сложности по на базе отдельных метрик сложности программ - метрик сложности потока данных

Лабораторная работа №5

Цель работы: изучить метрики сложности потока данных программ.

Краткие теоретические сведения и методические указания к выполнению работы.

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

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

Пара "модуль - глобальная переменная" обозначается как (p, r), где p - модуль, имеющий доступ к глобальной переменной r. В зависимости от наличия в программе реального обращения к переменной r формируются два типа пар "модуль - глобальная переменная": фактические и возможные.

Возможное обращение к r с помощью p показывает, что область существования r включает в себя p.

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

Отношение числа фактических обращений к возможным определяется

. (9)

Эта формула показывает приближенную вероятность ссылки произвольного модуля на произвольную глобальную переменную.

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

Покажем расчет метрики "модуль - глобальная переменная ". Пусть в программе имеются три глобальные переменные и три подпрограммы. Если предположить, что каждая подпрограмма имеет доступ к каждой из переменных, то мы получим девять возможных пар, т. е. = 9. Далее пусть первая программа обращается к одной переменной, вторая - к двум, а третья - не обращается ни к одной переменной. Тогда , .

Следующие две метрики сложности потока данных программ зарекомендовали себя с наилучшей стороны. Речь идет о спене и метрике Чепина.

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

Что дает эта метрика? Предположим, мы обнаружили в программе идентификатор, спен которого равен 100. Тогда при построении трассы программы по этому идентификатору, по крайней мере, 100 контролирующих утверждений, что усложняет тестирование и отладку.

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

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

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

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

2. М - модифицируемые или создаваемые внутри программы переменные.

3. С - переменные, участвующие в управлении работой программного модуля (управляющие переменные).

4. Т - не используемые в программе ("паразитные") переменные.

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

...