Алгоритмы ускорения планирования траекторий выполнения программ при направленном тестировании

Во введении обоснована актуальность задач диссертационного исследо-
вания и кратко характеризуются предложенные автором решения. Активное
развитие аппаратно-программных решений и сложных интегрированных при-
ложений, происходящее в последние годы, значительно повысило требования
к качеству программного кода. Существующие методы и средства верифика-
ции и тестирования программ уже не позволяют гарантировать обнаружение
некорректности за приемлемое время. В целом, можно выделить два больших
класса подходов к верификации: формальную и динамическую. Первая подра-
зумевает формальное рассмотрение возможных сценариев работы программы,
представленной в виде модели, без её фактического исполнения. Достоин-
ством формальной верификации является теоретическая полнота покрытия всех
возможных ситуаций. Главными её недостатками является высокая вычисли-
тельная сложность. Динамическая верификация основана на тестировании, то
есть реальном исполнении программы с теми или иными входными данными
(стимулами) и автоматизированным наблюдении за процессом и результатами её
работы. Несмотря на сравнительно малую ресурсоёмкость и трудоёмкость, такой
подход имеет принципиальный недостаток – даже большое число разнообраз-
ных тестов не может гарантировать обнаружение всех типов сценариев, ведущих
к ошибкам.
Направленное тестирование сочетает достоинства формального и ди-
намического подхода. С одной стороны, оно подразумевает непосредственное
исполнение программы, а с другой – автоматическое планирование вариантов
последующих запусков теста на основе наблюдения за потоком управления
в программе при исполнении предыдущих запусков, а также на основе (возмож-
но, неполной) математической модели программы. Настоящая диссертационная
работа посвящена исследованию усовершенствований эвристических подходов
к ограничению набора планируемых траекторий при направленном тестирова-
нии программных систем без существенного снижения покрытия ветвей кода
тестами. Кроме тестирования ПО, предлагаемые подходы могут применяться
для исследования широкого класса моделей, описывающих многовариантные
последовательности событий (сценарии).
В первой главе рассматриваются основные направления исследований
и разработок в области верификации и тестирования дискретных систем в це-
лом и программ в частности, в основе которых лежит поиск контрпримеров
с помощью решения уравнений относительно входных переменных. Вначале
представлены методы абстракции, в которых реальное поведение сложной си-
стемы заменяется обобщениями, как правило, в виде гиперкубов в многомерном
пространстве значений входных переменных. Выбор таких кубов в современных
средствах верификации происходит итеративно на основе двух встречно на-
правленных конкурирующих процессов: абстракции и детализации (refinement).
Другим направлением упрощения верификации соблюдения требуемых свойств
x:=0

покрытие ветвей кода, %
y:=03

51015
a≠0
да05
нетx:=c10

да
b≠020
нетy:=x
ошибка
да25 ∞
y=350

010002000
нет
время тестирования, с

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

системы является построение индуктивных инвариантов. Таким инвариантом
называют выражение, которое (1) соблюдается в начальный момент работы
тестируемой системы и (2) соблюдается в момент i в предположении, что оно со-
блюдалось в предшествующий момент i − 1. Индуктивные методы, как правило,
более эффективны, чем непосредственное пошаговое моделирование абстра-
гированного поведения системы, в основном благодаря меньшему количеству
рассматриваемых шагов во времени. Самые эффективные алгоритмы такого ти-
па (IC3 – Incremental Construction of Inductive Clauses for Indubitable Correctness
– и его варианты) применяют итеративный процесс абстракции и уточнения не
к единственному выражению инварианта (индуктивно верному для любого но-
мера шага), а к набору отдельных инвариантов для каждого шага в диапазоне
0..k. Благодаря «встречному» поиску усиления инварианта (1) возможного раз-
вития состояния системы за i шагов и (2) некоторого условия, не приводящее за
k − i шагов к опровержению самого себя, число исследуемых вариантов сокра-
щается, и ответ достигается быстрее.

Наконец, рассматриваются формально-динамическое и динамические ме-
тоды, объединенные идеей наблюдения за (реальным или симулируемым) пове-
дением тестируемой программы при различных вариантах входных стимулов.
Стратегии тестирования делятся на поведенческие и структурные . Первые рас-
сматривают тестируемый объект как «чёрный ящик», вторые же опираются на
знание внутренней логики объекта. Направленное тестирование стремится гар-
монично сочетать два перечисленных подхода. Например, основополагающая
идея метода DART (Directed Automated Random Testing) состоит в целена-
правленном изменении направления одного условного перехода по сравнению
с траекторией одного из предшествующих запусков. Для этого программа ин-
струментируется средствами, позволяющими наблюдать и документировать её
выполнение одновременно в конкретном и символическом виде (такое представ-
ление обозначается термином concolic, от “concrete” + “symbolic”).
Несмотря на различия подходов, упомянутых в обзоре, можно заметить,
что фокус оптимизации обычно направлен на решение статической системы
уравнений, описывающей тестируемую систему. Влияние многовариантности
самой системы, вызванной различными присваиваниями внутренних перемен-
ных программы, обычно рассматривается на уровне перебора комбинаций.1
Поскольку количество комбинаций такого перебора выходит за пределы вычис-
лительных возможностей для большинства реальных программ, предлагаются
различные эвристики для его ограничения. Наиболее системным и коррект-
ным решением является построение абстрактного дерева достижимости (ART –
Abstract reachability tree), в котором различные состояния выполнения програм-
мы с одинаковыми инвариантами (и только они) в идеальном случае сливаются
в одно состояние . Подобные идеи применяются и в рамках DART . В данном
классе решений можно найти ряд недостатков, адресованных в настоящем дис-
сертационном исследовании.
Вторая глава посвящена исследованию ускорения тестирования про-
грамм за счёт сокращения повторных обходов (реальтернаций) ветвей
условных переходов.
«Базовый» алгоритм направленного динамического тестирования исполь-
зует перебор по возможности всех путей выполнения программы. Такая необ-
ходимость вызвана тем, что условия переходов могут прямо или косвенно
содержать переменные, присваиваемые в коде, выполняемом или опускаемом
в зависимости от выбора направлений предшествующих переходов. Поэтому
символьный вид выражения условия может зависеть от предыдущих переходов,
отчего ветвь, недоступная при одном пути выполнения, может оказаться доступ-
ной при каком-либо другом. На рис. 1 показан простейший пример такого рода.
Если в первом запуске теста были выбраны значения x = 0, y = 1, а во втором –
x = 0, y = 1, зависимость условия ошибки от y не прослеживается, отчего ветвь
с ошибкой кажется недоступной (ее условие при x = 0 будет всегда ложно); все
остальные ветви успешно покрыты, поэтому тест выглядит успешно завершён-
ным. Только перебор всех четырёх комбинаций (x,y) даёт возможность найти
ошибку (при x = 1, y = 1). Хотя метод полного перебора путей универсален, его
сложность экспоненциальна относительно длины пути, что практически означа-
ет необходимость ограничения области поиска.

1 Это исторически связано с тем, что средства верификации изначально создавались для аппарат-

ных систем и лишь впоследствии адаптировались для ПО.
В основе предлагаемой автором стратегии ограничения лежит гипотеза
о том, что для покрытия всех достижимых ветвей или создания ситуации в про-
грамме, выявляющей ошибку, достаточно изменить сравнительно небольшое
число условий переходов. Иными словами, цепочки зависимостей, подобные
изображённой на рис. 1, обычно включают в себя лишь небольшое количе-
ство переходов. Хотя выделение таких цепочек формальными методами в общем
случае весьма сложно, предположение об ограниченности их размера позво-
ляет свести число итераций поиска к полиномиальному относительно размера
программы вместо экспоненциального, ограничив число переходов, участвую-
щих в полном переборе, некоторым параметром Q. Технически это выражается
в ограничении числа планируемых направлений, отличных от направлений,
наблюдаемых при первом выполнении каждого соответствующего перехода
в рамках серии тестов. Квота не включает первичные посещения ветвей, так
как такие посещения непосредственно увеличивают покрытие; отсюда название
«ограничение реальтернаций».
«Строгое» ограничение числа реальтернаций константным параметром
представляет собой простейший (но наиболее интересный для исследования)
случай. Поскольку требуемое значение Q для ожидаемой полноты тестирова-
ния заранее неизвестно, целесообразно использовать приоритизацию тестов по
числу реальтернаций q (тесты с меньшим q выполняются в первую очередь). Сле-
дующим шагом является исследование оптимизации распределения повторных
обходов. В случае равномерного распределения (который был выбран в качестве
базового) достаточно применять к планируемым комбинациям переходов слу-
чайный фильтр с вероятностью (Q/A)q , где A – число возможных переходов, обе
ветви которых посещались. Альтернативные методы распределения повторных
обходов предполагали их концентрацию в корневой либо периферийных обла-
стях дерева ветвлений. Эксперименты показывают, что покрытие ветвей втором
случае в 96% случаев не снижается, хотя сложность поиска становится линей-
ной по отношению к размеру программы. Приемлемым компромиссом оказалось
равномерное распределение h = 1..2 реальтернаций при концентрации остав-
шейся квоты в хвосте траектории. Уже при h = 1, Q = 15 все доступные ветви
в тестовой подборке программ были покрыты. Заметим, что, хотя теоретиче-
ски порядок сложности тестирования может достигать N h˙2q , на практике из-за
неудовлетворимости условий большинства планируемых путей выполнения на-
блюдается «сжатие показателя»: N αh˙2αQ , α ≈ 0.35. На рис. 2 показан пример
покрытия ветвей кода в зависимости от времени теста.
Ветвления, выполняемые в различных итерациях тела цикла (в том числе
условный переход к следующей итерации) в базовом алгоритме DART считаются
различными условными переходами. В результате вся доступная квота реаль-
тернаций может быть израсходована в пределах небольшого числа инструкций
исходного кода. Автор предлагает эвристически ограничить число различимых
контекстов для каждого перехода в коде. Для цикла это может означать рас-
смотрение первых m итераций и одной итерации с «экстремально» большим
номером в качестве кандидатов для реальтернаций переходов.2 Стек вызовов
функций также порождает множественные контексты для одних и тех же ветв-
лений в исходном коде. Случай рекурсивного вызова по существу не отличается
от вышеупомянутого случая цикла. В общем случае автором предложено огра-
ничивать размер рассматриваемого фрагмента стека несколькими вершинными
элементами (относительно перехода, направление которого выбирается). Те-
стирование реальных примеров показало, что выбор такого числа равным 5
обеспечивает более 99.6% покрытия ветвей от возможного.
Однако такие агностические по отношению к зависимостям по данным
эвристики неизбежно допускают избыточные комбинации планируемых пере-
ходов, многократно превосходящие своим числом комбинации, существенные
для полноты покрытия ветвей. Теоретически, необходимо комбинировать ре-
альтернации только тогда, когда в результате возможно возникновение нового
символического выражения для условия перехода к ещё не покрытой ветви. Од-
нако в общем случае такая зависимость выявляется с низкой точностью. Автором
предложено использовать выявленные зависимости для регулирования разре-
шенного числа реальтернаций: для комбинаций предположительно независимых
переходов применяется меньшая квота Qi , а для зависимых – увеличенная Qd .
Эмпирически, для текущего тестирования средней программ-утилиты можно ре-
комендовать Qt ≈ 25 . . . 30, Qd ≈ 45 − 50.
Третья глава посвящена постановке и решению задачи о целесообразно-
сти альтернации единичного условного перехода.
Информация о зависимостях условий переходов от присваиваний перемен-
ных может быть достаточно легко получена в процессе тестирования, например,
путем одновременного динамического мониторинга доступа к адресам памяти
для чтения или записи данных и позиции в исполняемом коде. Однако, исполь-
зование таких зависимостей при планировании тестов сопряжено с проблемой
сложности – нужно обеспечить быстрый поиск точек ветвлений в графе управле-
ния, изменение порядка прохода которых потоком управления может приводить
к существенному для тестирования изменению символической формы вычисля-
емых в программе выражений, являющихся условиями переходов. Обозначим
вершины графа управления, посещение которых влияет на интересующие усло-
вия, как v1, v2 и т.д. Тогда планируемая траектория представляется в виде
отрезков S1, S2 и т.д., каждый из которых содержит соответствующую вершину
v и произвольное множество вершин, не принадлежащих последовательности R
и не влияющих на условия переходов:

T = [S1 ,S2 , . . . ], Si = [vi, x∗ ],(1)

2 Обычно нескольких первых итераций достаточно для выявления всех сценариев основного ал-

горитма тестируемой программы. Рассмотрение итерации с большим номером («много») позволяет
наблюдать реакцию программы на исчерпание каких-либо ресурсов, например, выделение новых
диапазонов индексов или участков памяти, сбор мусора.
а)
y’
yr1
y ’’
v2

б)
y’
yv2
y ’’r1

Рис. 3 –– Пример принятия решений о целесообразности (а) и необязательности
(б) альтернации

где V = {v1 , v2 , . . . }, R = {r1 , r2 , . . . } содержат вершины, влияющие через
присвоения на условия «интересных» ветвлений и еще не исследованные в та-
кой комбинации; x∗ – произвольная последовательность вершин, не входящих ни
в V , ни в R.
Теперь можно сформулировать «атомарную» задачу планирования пути:
имея целью посещение последовательности вершин v1 , v2 и т.д., следует ли
форсировать посещение ветви условного перехода, ведущей из вершины yi в вер-
шину yi0 при альтернативе y 00 ? Пусть D(v + ,V − ) –- функция на графе управления,
возвращающая множество вершин, доступных из v + по путям, не проходящим
через вершины из множества V − . Тогда утверждение «необходимо посетить yj0 »
эквивалентно выражению
vi+1 ∈ ξ(y 0 ,y 00 ,R)

ξ(y 0 ,y 00 ,R) ≡ D(y 0 ,R) D(y 00 ,R)(2)

На рис. 3 показаны примеры такой задачи о необходимости альтернации
перехода в вершине y. На верхнем рисунке альтернация (показанная жирной
пунктирной стрелкой) необходима, так как, следуя ретроспективной траектории,
показанной сплошными жирными стрелками, невозможно попасть в «интерес-
ную» вершину v2 , минуя «запрещённую» вершину r1 . На нижнем рисунке это
сделать можно независимо от выбора направления перехода в вершине y.
В практике анализа и компиляции программ широко применяется пред-
ставление участков графа управления программы в виде иерархии вложенных
гамаков. Такое представление помогает значительно упростить вычисление D.
ε = {1}
ε= ∅I ={2..5}
I ={1..8}
1ε = {4,5}
I ={6..8}
ε = {4}
I ={5}26ε = {4,5}
I ={7}
ε = {1}
I ={3..4}
358ε = {4,6}
7I ={8}

ε=∅
I ={4}
Рис. 4 –– Пример аннотирования графа управления

Однако, поскольку в реальных программах «идеальная» структура гамаков ис-
кажена (сравнительно малочисленными) передачами управления вовне гамака
(например, выход цикла в произвольной точке его тела или обработка исключе-
ния), в диссертационной работе предлагается использовать для представления
блоков кода квазигамаки, в которых, в отличие от гамаков, допускается более
одной выходной вершины. Назначение квазигамаков производится с помощью
остовного дерева. Экспериментальное подтверждение гипотезы об эффективно-
сти такого представления являлось одной из целей настоящего исследования.
В предлагаемом алгоритме вычисления D множество R(x) всех доступ-
ных из вершины x вершин графа управления распадается на два подмножества:
R(x) = I(x)∪ (x), где I(x) – множество узлов, содержащихся в конусе остовного
дерева со входной вершиной x; – множество узлов, не принадлежащих данному
конусу, соединенных входящим рёбрами хотя бы с одной вершиной, принадле-
жащей данному конусу.
Чтобы избежать увеличения сложности, связанного с несбалансированно-
стью остовного дерева, предлагается использовать дополнительное диадическое
дерево, построенное для полученной сортировки графа управления остов-
ным деревом. Обращение к диадическому дереву, которое гарантированно
сбалансировано, происходит только при наличии в конусе остовного дерева
«запрещённых» вершин, то есть членов множества V − . Для уменьшения числа
рассматриваемых интервалов диадического дерева оказалось целесообразным
частично выравнивать последнее с остовным деревом, допуская для этого огра-
ниченный дисбаланс.
Вычисление и хранение отдельных контейнеров для множеств внешних
вершин-получателей каждого конуса дерева внесло бы сложность порядка O(K ∗
N ) по времени и по размеру памяти, где K – средний размер множества, N –
число вершин. Чтобы уменьшить сложность до O(N log(K)), применяется куча
число итераций поиска
31030100300
число вершин в графе функции, содержащей начало поиска

(v+,v-:)предок и потомокв теле одной функциипроизвольно

Рис. 5 –– Число итераций поиска при вычислении ξ в зависимости от числа
вершин в графе функции, содержащей начало поиска (v + ). Высота столбиков
примерно пропорциональна частотности примеров

(heap), построенная с использованием совместно графа выражений для различ-
ных её экземпляров. Автором разработан код для реализации таких куч.
Для изучения возможностей описанного подхода была разрабо-
тана специальная моделирующая система (код доступен по ссылке
https://github.io/cgsnap). Эксперименты продемонстрировали, что
сложность вычисления ξ в среднем не превышает 3..5 итераций для одной вер-
шины, входящей в V + (Рис. 5), что примерно в 10 раз меньше среднего числа
обрабатываемых узлов при непосредственном обходе графа (более 40).
Четвёртая глава посвящена алгоритму реконструкции графа управления
на основе трасс событий. В случае, если граф управления недоступен (напри-
мер, отсутствует исходный код приложения), для анализа возможных ошибок
и планирования тестов возможно использовать автомат, построенный на осно-
ве наблюдаемых путей выполнения программы.3
3 Построенный таким образом граф не обязательно соответствует ветвям кода, но представляет

собой пригодную для анализа генерализацию наблюдаемых последовательностей событий.
В основе предложенного алгоритма лежит оптимальное выравнивание
строк относительно графа автомата на основе расстояния редактирования. Алго-
ритм способен производить сравнительно точные модели на основе небольшого
по объёму множества обучающих данных. Каждая итерация обучения исполь-
зует текущую версию автомата и одну из строк-образцов в качестве модифи-
цируемого и константного операндов, соответственно. Алгоритм выравнивания
в принципе аналогичен алгоритму Нидлмана–Вунша , но имеет следующие ос-
новные отличия:
1. Разрешается рассмотрение любого ребра автомата (в том числе несу-
ществующего (перспективного), с фиксированным штрафом) в качестве
возможного перехода между позициями в первом операнде.
2. К рассматриваемым состояниям добавляются возможные новые со-
стояния, по одному для каждого символа строки-образца; решение
о включении новых состояний в автомат зависит от того, уменьшают
ли проходящие через них пути итоговое расстояние редактирования.
Обработка каждой строки y в процессе обучения включает построение
матрицы счетов выравнивания Si,j между префиксом строки и путём в автома-
те, где i ∈ 0..n,n + j – существующие или предполагаемые состояния автомата,
j ∈ 1..|y| – позиция в строке-образце. Чтобы найти максимальный счёт Si,j , про-
изводится трансфер счетов-кандидатов из элементов S∗,j−1 двумя способами:
1. через уже построенные ребра автомата, метки которых соответствуют
символу y j строки;
2. посредством «телепортации», то есть из любого состояния автомата,
включая перспективное состояние для позиции j − 1.
Фактически, для каждой строки строится взвешенный конечный транс-
дьюсер (weighted finite-state transducer (WFST)), преобразующий автомат в дан-
ную строку.4
В работе также рассматривается вариант алгоритма, в котором граф все-
гда соответствует автомату для какого либо регулярного выражения (РВ). РВ
являются стандартным способом представления выражений, обобщающих на-
боры последовательностей элементов. Обобщение трасс событий в виде РВ
сопряжено с принятием гипотез, которые не могут быть доказаны или опроверг-
нуты наблюдением конечного числа последовательностей (например, гипотеза
о неограниченности числа итераций цикла), поэтому неизбежно использова-
ние эвристических правил. Однако, поскольку структура программы (и, соот-
ветственно, её графа управления) в основном состоит из гамаков и циклов,
регулярные выражения являются эффективным способом генерализации трасс
выполнения программы. Предложено расширение синтаксиса РВ для менее за-
тратного учёта выходов потока управления из блоков кода.
В заключении перечислены важные составляющие проделанной работы:
4 Для уменьшения сложности число рассматриваемых входящих в каждое состояние WFST ребер

ограничивается константным гиперпараметром K, при этом строятся только ребра, доставляющие
наибольшие значения счета в данное Si,j .
1. Предложен и экспериментально подтверждён эвристический метод оп-
тимизации скорости направленного тестирования с помощью ограниче-
ния числа повторных обходов ветвей условных переходов. Исследована
динамика покрытия кода. В числе других предложен вариант метода,
учитывающий приблизительную информацию о зависимостях данных
в программе, получаемую при анализе траекторий выполнения тестов
и обращений к памяти.
2. Сформулирован критерий целесообразности посещения ветвей услов-
ного перехода, вычисляемый как дополнения множеств доступных по
альтернативным путям непокрытых ветвей графа управления. Разра-
ботана технология быстрого вычисления критерия и реализующее её
программное средство. Продемонстрирована эффективность использу-
емого алгоритма для выборки программ с открытым кодом.
3. Разработаны и экспериментально изучены алгоритмы аппроксимации
графа управления путем автоматического выравнивания последователь-
ностей событий, наблюдаемых при работе тестируемой программы.
В целом, были разработаны основные элементы технологии, позволяющей учи-
тывать зависимости по данным при планировании тестов в рамках парадигмы
направленного тестирования без неприемлемого роста затрат вычислитель-
ных ресурсов.