62
Например, в архитектуре ARM по соглашению о вызовах параметры в
функцию передаются через 4 регистра: R0, R1, R2, R3. Поэтому инструкции
передачи аргументов в функцию транслируются через копирование значений из
виртуального регистра в соответствующий реальный программный код.
После фазы выбора инструкций осуществляется фаза распределения
регистров, позволяющая заменить виртуальные регистры реальными.
Между этими двумя фазами добавляется оптимизация по планированию
инструкций. Она позволяет реализовать алгоритм списочного планирования
(list scheduling). В состав оптимизации входит граф зависимости между
инструкциями с назначением их весов. После этого планировщик на основании
модели процессора формирует несколько инструкций. Для этого на каждом
такте формируется список доступных инструкций, у которых вычисление всех
аргументов завершилось. Далее из этого списка планировщиком выбирается
необходимое количество инструкций, имеющих наивысший приоритет.
Приведем пример процесса оптимизации на модели процессора ARM
Cortex-A8. На этом процессоре отсутствует аппаратное переупорядочивание
инструкций. Поэтому эффект от планирования будет существенным.
В процессорах Cortex-A8 находится 2 конвейера. Если между
инструкциями на разных конвейерах существует зависимость, то это приводит
простою конвейера.
В архитектуре ARM существует возможность адресации 16 регистров
общего назначения, при этом 4 регистра будут включать R15 - счетчик команд,
R14 - адрес возврата, R13 - указатель стека, R8 для адресации внутренних
данных программы Valgrind.
Кроме этого, регистры R0 и R3 будут участвовать в соглашении других
вызовов. Остальные 8 регистров будут использоваться произвольным образом.
Поскольку количество свободных регистров ограничено, то слишком
агрессивное переупорядочивание будет приводить к сбросу регистров памяти и
негативно отражаться на производительности программного обеспечения.
63
Поэтому планировщиком оценивается на каждом такте регистровое
влияние и планируются инструкции так, чтобы это влияние не превышало 6
регистров. Однако, эффект работы планировщика снижается, поскольку на
низкоуровневом представлении программы Valgrind вместе с обычными
командами ассемблера ARM использовались также виртуальные команды,
включающие реальные команды.
К тому же виртуальные команды оперируют с фиксированным набором
данных, что мешает планировщику оценивать текущее влияние регистров. Во-
вторых, алгоритм перераспределения регистров устроен так, что ему
необходимо использовать очередной виртуальный регистр, как реальный для
поиска свободного места.
В результате между инструкциями возникает зависимость, они не могут
выполняться параллельно на двух разных конвейерах.
Пример выполнения оптимизации в среде Valgrind с применением тестов
набора SPEC CPU2000 приведен в таблице 5.
Таблица 5 – Пример выполнения оптимизации в среде QEMU с
применением тестов набора SPEC CPU2000
Название теста
Тестирование без
оптимизации, с
Тестирование с
оптимизацией, с
%
164.gzip
754,45
775.98
3,73
175.vpr
728,84
719,84
1,23
176.gcc
459,47
459,95
-0,1
181.mcf
119,4
122,92
3,65
186.crafty
705,12
712,58
-1,06
197.parser
1709,33
1687,56
1,27
252.eon
1496,51
1490,66
0,39
253.perbmk
1173,34
1164,48
0,76
256.bzip2
665,53
681,51
4,17
300.twolf
1479,2
1467,94
0,76
Тестирование показало, что в результате использования программ SPEC
CPU2000 было получено ускорение до 3,3% (тесты 164.gzip, 181.mcf и
256.bzip). Это указывает, что выполнение оптимизации с помощью программы
64
Valgrind позволяет повысить эффективность и качество разработки
программного обеспечения.
Однако планировщик работает с виртуальными регистрами и считает, что
между ними инструкций нет. Поэтому алгоритм распределения регистров
должен быть модифицирован так, чтобы освобождался реальный регистр и
попадал в конец списка.
Для совершенствования статических методов анализа качества
программного обеспечения предлагаем ОАО «Аурат» автоматизировать
процессы модульного тестирования за счет генерации тестовых воздействий и
основанный на динамическом символьном выполнении программного
обеспечения с использованием машинных инструкций.
В основе этого подхода находится формирование тестовых воздействий
на основе определения фактических путей и символьных зависимостей
переменных, которые могут быть получены в предыдущих тестовых запусках.
Эффективность комбинирования методов статического и динамического
анализа качества программного кода подтверждается в работах многих авторов.
В настоящее время свое распространение получил инструмент
Check’N’Crash, в котором объединены инструменты статического анализа
ESC/Java и JCrasher генератор тестов, позволяющий извлекать определенные
значения свойств специфические для абстрактных условий ошибок найденных
статическим анализатором.
Рассматривая развитие методов обеспечения качества программных
продуктов, Кулева Ю. С. рекомендует использовать инструмент DSD-Crasherr,
включающий в свой состав методы проверки качества программного кода на
трех уровнях
61
:
- исполнения для динамического обнаружения заложенного поведения с
целью ограничения множества входных значений;
- статического анализа для выявления наиболее опасных ошибок;
61
Кулева Ю. С. Развитие методов обеспечения качества программных продуктов //Статья в
сборнике Инноватика, 2018. – С.491-494
65
- динамической верификации для обнаружения потенциальных ошибок и
проверки их достижимости.
Слайсинг программного обеспечения может применяться для
объединения динамического и статического методов анализа качества
программного обеспечения. Для осуществления слайсинга применяют
инструмент SANTE, в котором интегрированы инструменты для проведения
статистического анализа, позволяющего обнаружить ошибки в программном
коде и динамического анализа.
На основании этого генерация больших программных кодов сокращается,
а также ускоряется процесс оценки качества программного обеспечения.
Исследуя вопросы качества программного кода, Жуков В. К.
рекомендуют использовать подход остаточного исследования, в основе
которого находится динамический анализ как сервис для проведения
статистического анализа. Это позволяет подтвердить во время исполнения
программного кода истинность ошибки. В дополнение к этим инструментам
рекомендуют использовать инструменты, позволяющие объединить техники
контроля качества программного обеспечения, включающие статический и
динамический анализ программ
62
.
В работе Банчука Г. Г. предлагается объединить статистический анализ и
динамический для обнаружения подозрительных мест в программном коде. Для
реализации этого подхода можно использовать статический анализатор SVR, в
основе которого находится промышленный компилятор GCC
63
.
Статическим анализатором по программному коду формируется модель
для инструмента Moped, проверяющего свойства безопасности программного
кода. В результате определяется набор путей, приводящих к потенциальному
дефекту. На основании этого маршрута формируется блок входных данных и
62
Жуков В. К. Теория измерений: учеб. пособие / В. К. Жуков. – М.: Университеты России,
2016. – С.89
63
Банчук Г. Г. Теоретические аспекты оценки качества программных продуктов // Статья в
сборнике Информационно-аналитические системы и технологии, 2018. – С.40-50
66
производится проверка достижимости определенных состояний в программном
коде.
В Костина А. В. рассматривается подход, объединяющий статистический
и динамический анализ в инструменте JNuke. Этот инструмент позволяет
абстрагировать алгоритм работы анализатора и предоставить возможность
оценки различных свойств программного кода, вычисляемых статически и
предоставляемых через единый интерфейс
64
.
Идеи комбинирования динамического и статистического анализа
реализованы в инструменте SANTE, который позволят анализировать
исходный код на языке Си Farma-C и производить динамическое символьное
исполнение с целью построения тестовых наборов.
Компанией Microsoft Research для оценки качества программного кода
был представлен инструмент Yogi, интегрирующий статистический анализ
свойств безопасности и интерпретатор промежуточного представления
программ. Программа Yogi производит символьное выполнение программного
кода, а также его симуляцию с целью подтверждения найденных ошибок.
В работе Герасимова А. Ю. предлагается подход комбинации
статистических и динамических методов анализа для выявления уязвимостей
выхода за границы буфера в памяти. Во время проведения статистического
анализа определяется последовательность помеченных зависимостей между
входными данными и уязвимыми операциями, которые впоследствии
формируют функцию зависимостей между выявленными ошибками в
программном коде
65
.
В Лукина В. Н. рекомендуется использовать инструмент ConDroid,
позволяющий выполнять анализ программного кода продуктов работающих
под управлением операционной системы Android. Этот инструмент основ на
64
Костин А. В. Модель для оценивания функциональности систем машинного перевода //
Известия Российской академии науки, 2018. – С.158-172
65
Герасимов А. Ю. Обзор подходов к улучшению качества результатов статического анализа
программ // Труды системного программирования РАН, 2017. - № 3. – С.75-98
67
статистическом анализе программного кода и определения критических узлов в
программе с использованием динамического анализа
66
.
Метод динамического анализа в инструменте ConDroid представлен в
виде символьного исполнения определённого набора входных данных. При
этом итеративный динамический анализ для каждой операции определяет
выходные данные, которые в итоге позволяют привести программу в
исполнение.
Инструмент IntelliDroid объединяет методы динамического и
статического анализа и представляет результаты в формате байт-кода DEX.
Статистическим анализатором применяются данные о месте использования
стороннего API вместе с точками вызова и генерацией входных данных через
решатель формул, основанный на булевых ограничениях.
Еще одним инструментом, позволяющим генерировать тестовые
сценарии, выявлять критические ошибки является программа STAR, которая
используется для оценки качества программного обеспечения написанного на
JAVA.
В инструменте реализуется метод классификации утечки памяти за счет
совмещения статистического анализа и динамического символьного анализа.
Следовательно, в настоящее время многие специалисты производят
интеграцию методов статистического и динамического анализа программного
обеспечения, которая позволяет исключить неточности присущие методам
статического анализа и сложность характерную для методов динамического
анализа.
При тестировании будет производиться контроль работы программного
обеспечения с применением вставки инструментального кода. В этом случае
будет производиться:
- отслеживание типов и адресов выполняемых инструкций для
построения модели программы и сбора статистики по покрытию;
66
Лукин В. Н. Подготовка качественных программистов: проблемы обучения //
Моделирование и анализ данных, 2017. - №1. – С.29-41
68
- перехватываться обращения к памяти для определения численных и
символьных значений переменных. Переменные будут идентифицироваться в
соответствии с их адресами и типами;
- для каждой ячейки памяти будет выполняться сохранение как
символьного, так и численного значения. При невозможности предоставления
результатов операции в символьном виде можно будет использовать численное
значение;
- при разыменовании указателей будет применяться численное значение
указателя для определения символьного значения его по цели и адресу;
- можно будет установлено условие прохождения текущего пути в
символьном виде, на основе которого выбираются воздействия, позволяющие
проходить альтернативный тестовый путь.
В качестве тестируемого модуля выберем подпрограмму сортировки
массива, этот пример выбран из-за наглядности и простоты выполнения
операций по динамическому символьному выполнению.
Листинг программного кода имеет вид:
static void pointer_sort(int**a, int s) {
int i, j
assert (s>=0);
s=-1; if (!s) return;
for (i=0;i<s;i+=1){
int minj=0;int*minv=a[i];
for (i=0; i<s; j+=1){
if(*a[j]<*minv){minj=j; minv=a[j];}
}
if(*minv==13)return;
if(minj){int*tmp;tmp=a[i];a[i]=minv;a[oinj]=tmp;}}}
69
Необходимо отметить, что ветвление if (*minv==13) return; будет
обнаруживаться при символьном выполнении только в случае точного
отслеживания указателей, а при случайном тестировании с большей
вероятностью оно отображено не будет. Для выполнения модульного
тестирования рекомендуем специалистам ОАО «Аурат» использовать тест-
драйв, в котором необходимо указать входные переменные в момент начала и
окончания тестирования, вызов тестируемого модуля для проверки его
выходных параметров. Управление тестируемым модулем рекомендуем
производить на основании присваивания входных переменных значений из
текущего тестового значения.
При первом тестовом запуске система будет строить модель программы,
выбирать тестовое значение случайно. Построенная модель программы
представлена в виде множества, связанного по управлению инструкцией,
которой объединяются в базисные блоки. Модель тестируемой системы
приведена на рисунке 14.
Рисунок 14 - Модель тестируемой системы
70
В процессе эксперимента было выбрано следующее воздействие: size = 4,
a0 = 9, a1= 0 и a3 = 3. После тестового запуска было определено тестовое
покрытие ветвей, для этого был разработан взвешенный управляющий граф с
отображением весов дуг равных количеству передач в процессе тестирования.
Внешний вид взвешенного управляющего графа программы приведен на
рисунке 15.
Рисунок 15 – Внешний вид взвешенного управляющего графа программы
При первом запуске пройден тестовый путь, обходящий все вершины
управляющего графа.
При этом существуют три непокрытых дуги, соответствующие
альтернативным решениям 0,19; 2,19; 15,19. Их начальные вершины входят в
состав тестового пути. Выберем первую другу 0,19; символьные условия ее
прохождения будут равны:
0size
Для данной дуги выбирается тестовое
воздействие
12size
. При втором тестовом запуске производим присваивание
входной переменной
12size
. В этом случае будет срабатывать дуга 0,19. На
текущем пути не будет начальных вершин и непокрытых дуг, поэтому
выбираем следующую дугу 2,19. Символьное значение ее будет иметь
следующий вид:
.134
11201
aaaaasize
На основании этого
условия были выбраны тестовые воздействия:
.33,832,131,1810,4 aaaasize
71
В процессе эксперимента проводилось сравнение предложенной системой
с работой программы Valgrind, имеющей открытую систему CREST,
ориентированную на тестирование программного обеспечения.
Результаты сравнения случайного тестирования с помощью среды CREST
и предложенной системы приведены в таблице 6.
Таблица 6 – Результаты проведения сравнительных экспериментов
Тестирование
Предложенный
модуль
Система СREST
Случайное
тестирование
N
Cb
N
Cb
N
Cb
rbtree
6
1
0
0
13
1
qsort_std
3
1
0
0
3
1
qsort
5
1
8
1
13
0,94
series
6
1
8
1
0
0
psort*
4
1
9
0,94
4
0,94
sort*
4
1
9
0,93
4
0,93
psort
4
1
4
1
4
1
sort
4
1
4
1
4
1
В процессе тестирования определялось достигнутое покрытие ветвей.
Результаты экспериментов показывают, что тестируемый модуль позволяет
достичь большего тестового покрытия в сравнении с существующими
системами.
Для поиска ошибок и дефектов в программном коде и повышения
качества программного обеспечения рекомендуем реализовать метод фаззинга
преимуществом, которого является возможность получения входных данных
для воспроизведения дефектов.
Современные фаззеры позволяют найти большое количество аварийных
завершений во время работы программного обеспечения. Перспективным
направлением поиска ошибок является способ обнаружения ошибок и
включения в них входных данных с целью повторного предупреждения.
В основе этих подходов находится применение бинарного кода,
позволяющего осуществлять поиск ошибок в программном обеспечении, не
включающим исходные тексты. Для исправления ошибок разработчики