Home

Международная конференция для специалистов по обеспечению качества программного обеспечения — SQA Days 2009 — прошла с 28 по 29 октября в Москве в рамках Международной восточно-европейской научно-практической конференции по программной инженерии (для специалистов по разработке программного обеспечения) — CEE-SECR 2009.

Портал Software-Testing.ru представляет серию интервью с участниками прошедшего мероприятия.

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

Марат Ахин, магистр техники и технологии, аспирант, преподает на кафедре компьютерных систем и программных технологий ФТК СПбГПУ.

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

Определим терминологию

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

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

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

Чтобы определить, какие именно тесты нужно запускать после внесения изменений, следует знать, какие тесты относятся к сделанным изменениями, а какие — нет.

В чем основная идея подхода?

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

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

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

Как это реализовано?

У нас есть две версии исходного кода программы: до и после модификации. Для них строится модель в виде абстрактного синтаксического дерева (Abstract Syntax Tree, AST), и дальнейший анализ выполняется над данными AST.

Чтобы определить, что именно изменилось в программе, необходимо эти два дерева сравнить.

Допустим, что у нас есть дерево, в котором поменялись какие-то листья.

Простейший пример — пусть у нас была функция, которая возвращала «b/c», а потом мы добавили проверку вида «Если «с = 0», то следует кинуть исключение «Деление на нуль».

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

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

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

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

Насколько эффективным получается такой подход?

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

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

А если внесена новая функциональность?

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

У нас был практический пример тестирования системы, для которой было около 600 юнит-тестов, — после анализа изменений на одной из ревизий оказалось, что для регрессионного тестирования достаточно выполнить всего один-единственный регрессионный юнит-тест.

Сколько ресурсов требуется для определения разницы AST? По времени, например...

Затраты на выполнение анализа AST сравнимы с затратами на выполнение нескольких юнит-тестов.

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

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

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

В других работах в качестве модели программы используют граф-потока управления (Control Flow Graph, CFG), получая вместе со всеми его преимуществами крайне сложную задачу непосредственно построения CFG, которая для некоторых языков практически неразрешима. Так, наличие в языке C такой сущности как «указатель на функцию» приводит к тому, что первое использование вызова функции через указатель переводит задачу построения CFG в задачу полноценного статического анализа программы, которая на несколько порядков сложнее.

Идея именно нашей работы заключалась в том, чтобы попытаться найти «золотую середину», которая просто работала бы. Как нам кажется — это у нас получилось.

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

У этого подхода есть ограничения?

Конечно.

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

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

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

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

Интервью брал Алексей Лупан.

На постсоветском пространстве ежегодная конференция «Software Quality Assurance Days» (SQA Days) считается одним из крупнейших событий в области обеспечения качества программного обеспечения. Сайт конференции: www.it-conf.ru