Труды Института системного программирования РАН. Том 17. 2009 г

Предисловие Очередной сборник трудов Института системного программирования почти полностью (но не совсем) посвящен проблематике тестирования компьютерных программных и аппаратных средств. В статье В. В. Кулямина «Организация сложных тестовых наборов» рассматриваются различные способы организации и структуризации сложных тестовых наборов. Анализируются основные проблемы эксплуатации и развития тестов, для решения которых необходимо введение дополнительной структуры. Рассматриваются три базовых техники структуризации тестов — выделение модулей, определение квалификаторов и введение конфигурационных параметров. В статье Д.В. Силакова и А.В. Хорошилова «Методы обеспечения переносимости ПО» обсуждается проблема переносимости приложений между программно-аппаратными платформами. Предлагается обзор подходов к решению этой проблеме, появившихся за время развития ИТ, а также анализ преимуществ и недостатков каждого из них. Рассматриваются области применения существующих решений. Статья Н.В. Пакулина и С.А. Смолова «Применение технологии UniTESK для функционального тестирования инфаструктурного ПО Грид» посвящена вопросам тестирования инфраструктурного программного обеспечения (ИПО, middleware) Грид-систем на соответствие стандарту. В статье рассматривается разработка тестовых наборов для ИПО Грид средствами технологии автоматизированного тестирования UniTESK. Приведены результаты тестирования программного пакет Globus Toolkit 4.2 на соответствие базовому стандарту WSRF 1.2. П.Н. Яковенко и А.В. Сапожников представили статью «Инфраструктура тестирования веб-сервисов на базе технологии TTCN-3 и платформы .NET», в которой обсуждаются вопросы тестирования веб-сервисов с использованием технологии TTCN-3. Рассматривается отображение языка WSDL в TTCN-3, основанное на синхронном (процедурном) взаимодействии тестового сценария с веб-сервисом. Предлагается подход к реализации универсального тестового адаптера средствами рефлексии, предоставляемыми платформой .NET, и средой поддержки времени выполнения языка TTCN-3. В статье А.В. Баранцева, С.В. Грошева и В.А. Омельченко «Генерация оптимизированных для ручного выполнения сценариев тестирования приложений с графическим интерфейсом пользователя» описывается решение задачи построения последовательностей действий пользователя, оптимизированных для ручного выполнения, на основе модели в виде диаграммы состояний и переходов. В статье М.В. Архиповой и С.В. Зеленова «Направленная генерация тестовых данных для анализаторов статической семантики» представлен метод 5

SemaTESK автоматической генерации множеств тестов для фронт-эндов в трансляторах. Метод ориентирован на тестирование анализаторов статической семантики. Предложенный метод специфицирования статической семантики позволяет формализовать неформальные требования, содержащиеся в нормативных документах (например, в стандартах). Метод SemaTESK был успешно применен в ряде проектов, в том числе по тестированию анализаторов статической семантики языков C и Java. В статье Д.Н. Воробьева и А.С. Камкина «Генерация тестовых программ для подсистемы управления памятью микропроцессора» рассматривается методика генерации тестовых программ, предназначенных для функционального тестирования подсистемы управления памятью микропроцессора. Предлагаемая методика основана на формальной спецификации инструкций, работающих с памятью, и устройств подсистемы, включая буфер трансляции адресов и кэш-память. Для генерации тестовых программ в предлагаемом подходе используются комбинаторные техники — тестовые воздействия на микропроцессор представляются в виде цепочек инструкций небольшой длины, составленных из различных сочетаний тестовых ситуаций. Статья Я.С. Губенко, А.С. Камкина и М.М. Чупилко «Сравнительный анализ современных технологий разработки тестов для моделей аппаратного обеспечения» посвящена сравнению современных подходов к разработке функциональных тестов для моделей аппаратуры: AVM (Advanced Verification Methodology) от компании Mentor Graphics, OVM (Open Verification Methodology) — совместной разработки Mentor Graphics и Cadence Design Systems — и технологии UniTESK (Unified TEsting and Specification tool Kit), разработанной в Институте системного программирования РАН. В статье Е. В. Корныхина «Генерация тестовых данных для системного функционального тестирования микропроцессоров с учетом кэширования и трансляции адресов» рассматривается задача генерации тестовых данных для системного функционального тестирования микропроцессоров (core-level verification), а именно задача построения тестовой программы по заданной ее абстрактной форме (тестовому шаблону). Для решения этой задачи в работе предложен алгоритм, сводящий ее к задаче разрешения ограничений. Статья И.Б Бурдонова и А.С. Косачева «Полное тестирование с открытым состоянием ограниченно недетерминированных систем» посвящена описанию подхода к проблеме полноты тестирования, под которым понимается проверка соответствия реализации требованиям, описываемым спецификацией. Тестирование полное, если оно обнаруживает все возможные ошибки в реализации. Для практического применения тестирование должно заканчиваться за конечное время. Требования полноты и конечности тестирования в общем случае взаимно противоречат друг другу. Однако для ограниченных классов реализаций и спецификаций, а также при использовании дополнительных тестовых возможностей, удаётся построить 6

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

7

Организация сложных тестовых наборов В. В. Кулямин [email protected] Аннотация. Статья посвящена различным способам организации и структуризации сложных тестовых наборов. Анализируются основные проблемы эксплуатации и развития тестов, для решения которых необходимо введение дополнительной структуры. Рассматриваются три базовых техники структуризации тестов — выделение модулей, определение квалификаторов и введение конфигурационных параметров.

1. Введение Современное программное обеспечение (ПО) очень сложно, и сложность его постоянно возрастает. Это вызвано естественным стремлением человечества к развитию, к решению новых, все более сложных задач и, соответственно, постоянно возрастающими требованиями к функциональности и удобству используемых на практике программных систем. Поэтому рост сложности практически значимого ПО стоит рассматривать не как проблему, нечто нежелательное, а как объективный фактор, один из вызовов, стоящих перед способностями человека к познанию законов окружающей действительности и умению использовать их. Сложные программные системы требуют соответствующих их сложности и масштабируемых методов обеспечения надежности и качества. Единственным практически работающим подходом к созданию надежных программных систем является метод корректирующих уточнений, при котором система строится постепенно из небольших частей, при этом каждый компонент системы, каждая их группа и система в целом проходят многочисленные проверки, позволяющие выявлять расхождения с требованиями и шаг за шагом устранять их. Для проверки выполнения требований и обнаружения ошибок чаще всего используется тестирование. Однако, с ростом сложности систем, сложность разработки и поддержки в рабочем состоянии тестовых наборов для них растет гораздо быстрее. Современные методы разработки ПО позволяют с разумными трудозатратами создавать системы объемом до десятков миллионов строк кода [1,2], хотя еще двадцать лет назад эта планка была на уровне десятков тысяч строк. В то же время используемые на практике техники создания тестов за это время 9

увеличили свою масштабируемость лишь примерно на порядок, хотя тестовый набор для сложной программной системы сам по себе также является сложной системой. Возникающее расхождение между масштабами систем, которые мы можем создать, и систем, которые мы в состоянии аккуратно проверить, грозит увеличением количества сбоев в ПО и ущерба от них. О масштабах возникающих проблем говорят хотя бы следующие цифры, относящиеся к различным программным продуктам компании Microsoft. Тестовый набор для текстового редактора Microsoft Word XP содержал около 35 тысяч тестов [3], а для Windows XP — более 2-х миллионов. Если в разработке Windows NT 4.0 участвовало около 800 служащих компании, а в ее тестировании — около 700, то у Windows 2000 было около 1400 разработчиков и 1700 тестировщиков, т.е. соотношение программистов и тестировщиков поменялось на обратное [4]. Еще более важным фактором увеличения сложности тестовых наборов является необходимость их развития, следующего за развитием тестируемой системы. Любое практически значимое ПО проходит достаточно долгую эволюцию, постепенно расширяя и изменяя свои функции и пользовательский интерфейс. Соответственно, для снижения затрат на сопровождение и обеспечение большей предсказуемости этого развития аналогичный путь должен проходить и тестовый набор. Но в него вносить изменения сложнее, чем в проверяемую систему, — помимо связей между отдельными его частями, необходимо учитывать и связи с подсистемами и модулями тестируемого ПО, их отдельными функциями и проверяемыми свойствами. Наиболее значимый вклад в масштабируемость технологий создания и эксплуатации тестов вносит используемая организация тестовых наборов. Количество тестов в тестовых наборах для современного ПО довольно велико и продолжает увеличиваться. Кроме того, часто тесты связаны друг с другом разнообразными зависимостями, которые не всегда выделены явно, но должны учитываться при сопровождении тестов и внесении в них изменений. Проблемам организации сложных тестовых наборов и подходам к их решению и посвящена данная статья.

2. Проблемы организации тестовых наборов При тестировании всегда используется конечный набор тестов, даже в определении тестирования в SWEBOK [5] сказано, что оно проводится в конечном наборе ситуаций. Однако не менее важен другой аспект тестирования, также зафиксированный в этом определении, — необходимость сделать выводы о качестве проверяемой системы и потребность в том, чтобы такие выводы были достоверными. Чтобы обеспечить достоверность выводов по результатам тестирования, оно должно проводиться так, чтобы все существенные аспекты поведения тестируемой системы и все факторы, способные повлиять на его корректность, были хоть как-то затронуты. Для сложного программного обеспечения таких аспектов и факторов очень много, 10

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

•

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

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

Очень часто в больших наборах тестов одни и те же их элементы используются многократно. Например, проверка реакции системы на одни и те же действия обычно одинакова, генерация тестовых данных для разных операций может выполняться одними и теми же процедурами. Все это приводит к потребности обеспечения многократного использования одних и тех же решений, которые стоит оформлять в виде отдельных компонентов. Таким образом выделяются тестовые оракулы — компоненты, чья задача состоит в проверке корректности поведения тестируемой системы в ответ на воздействия определенного типа, возникающие в различных тестах. Генераторы тестовых данных тоже часто становятся отдельными компонентами, которые можно использовать в разных тестах. Возможные виды компонентов тестовых систем обсуждаются в профиле универсального языка моделирования UML для разработки тестов (UML 2.0 Testing Profile [6-10]), в предложениях общей архитектуры инструментов тестирования, сформулированных в проекте AGEDIS [1113], а также в работах, посвященных технологии UniTESK [14-16]. Техники выделения модулей в модульных тестах (unit tests), как общего характера, так и связанные с подходом к разработке на основе тестирования (test driven development, TDD), обсуждаются в книгах [17,18].

•

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

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

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

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

Тестовые варианты облегчают разработчикам анализ возникающих ошибок. Хотя основной целью тестирования является только обнаружение ошибок, а не их локализация, результаты тестирования только в виде вердиктов «ошибок нет» или «ошибки есть» никому не 11

12

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

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

o

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

•

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

o

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

o

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

•

Задачи, связанные с удобством анализа результатов тестирования. o

Предоставление достаточно полной информации о найденных ошибках, включающей, как минимум, следующее. 13

14

ƒ

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

ƒ

Какая проверка зафиксировала ошибку, что именно было сочтено некорректным, какое требование при этом проверялось.

ƒ

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

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

Задачи, связанные с удобством модификации тестового набора. o

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

o

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

o

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

o

•

Классификация тестов. Классификация может проводиться по разным критериям. ƒ

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

ƒ

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

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

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

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

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

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

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

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

случае, если проверяемые ими элементы выполняют свои основные функции правильно.

тестируемой

системы

3.3. Модульность Самой мощной техникой структуризации тестового набора является выделение в нем модулей, ответственных за решение разнообразных задач, возникающих во время работы теста. Простейший способ выделения таких компонентов — определение групп тестовых вариантов, ответственных за проверку определенных элементов тестируемой системы или же некоторых аспектов требований к ней. Эти группы могут образовать иерархию, в которой группы верхнего уровня далее разбиваются на подгруппы, и т. п. При такой организации тестов выделение основных групп возможно еще на ранней стадии создания тестового набора, что позволяет эффективно распределять усилия по его разработке в большой команде. Однако более полезным с точки зрения обеспечения многократного использования одного и того же кода является выделение модулей внутри самих тестовых вариантов. Наиболее четко могут быть выделены следующие виды компонентов. • При тестировании достаточно широко используются компоненты, решающие задачи системного характера, не специфические именно для тестов. Они применяются для организации взаимодействия между другими компонентами теста и обеспечивают гибкое и точное управление ходом тестирования. К таким компонентам можно отнести планировщики хода теста [9] или диспетчеры, управляющие синхронизацией действий распределенных тестовых агентов, таймеры, используемые для отсчета времени, специализированные компоненты для мониторинга событий определенных видов, а также компоненты, отвечающие за запись информации в трассу теста. •

18

Тестовые адаптеры (test adapters). Компоненты-адаптеры необходимы для привязки теста к тестируемым интерфейсам, если эти интерфейсы могут меняться без изменения их функциональности или если один и тот же тест предназначен для тестирования различных систем, реализующих одни и те же функции. Адаптер реализует абстрактный интерфейс, с которым работает тест, на основе одного из реальных интерфейсов, позволяя остальным компонентам теста не зависеть от конкретного синтаксиса реальных интерфейсов. Тестовые адаптеры — один из наиболее широко используемых видов компонентов теста. Адаптеры используются и в UniTESK под именем медиаторов [14], и при разработке тестов на TTCN для их привязки к конкретным тестируемым системам. В UML Testing Profile адаптеры не

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

•

Тестовые заглушки (test stubs). Заглушки используются при тестировании отдельных компонентов, модулей или групп модулей, для работы которых необходимы другие компоненты, если эти другие компоненты недоступны (еще не разработаны) или просто не используются, чтобы не усложнять тестирование и анализ его результатов. Заглушка реализует интерфейс одного из отсутствующих компонентов, заменяя его в ходе теста. В качестве результатов заглушки обычно возвращают произвольные значения — постоянные или сгенерированные случайным образом. Однако иногда используются "умные заглушки" (smart stubs), реализующие какую-то часть функций заменяемого модуля или специфические сценарии его работы. Поскольку заглушки часто возникают при модульном тестировании, в книге [18] различным видам заглушек посвящена отдельная глава. В сообществе, связанном с разработкой на основе тестирования (TDD), заглушки предпочитают называть «фиктивными объектами» (mock objects, mocks) или «тестовыми дубликатами» (test doubles). Более точно, в терминологии [18] тестовые дубликаты могут относиться к различным видам. o

Фальшивый объект (fake object). Это простой тестовый дубликат, способный принимать обращения из тестируемой системы и выдавать какие-то результаты в ответ на них, все равно какие, лишь бы происходило корректное взаимодействие.

o

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

o

Тестовый шпион (test spy). Это разновидность дубликата, которая умеет протоколировать сделанные к ней обращения из тестируемой системы, чтобы проверить их правильность в конце теста.

o

Фиктивный объект (mock object). Отличается от шпиона только тем, что выполняет проверки корректности производимых к нему обращений прямо в ходе работы теста, а не в его конце.

данных, обычно одного типа. Выгода от их использования появляется при необходимости создавать разнообразные объекты одного типа данных в разных тестах. Генераторы тестовых данных сложной структуры обычно делаются составными. Например, генератор значений комплексных чисел можно построить из двух генераторов действительных чисел — для вещественной и для мнимой частей. Генератор сложных документов удобно строить в виде системы из взаимодействующих генераторов отдельных частей таких документов — заголовков, отдельных полей и разделов, отдельных фраз и слов. В технологи UniTESK такого рода компоненты названы итераторами [14]. В профиле UML для разработки тестов [9] они названы селекторами данных (data selector). Селекторы могут использовать контейнеры данных (data pool), хранящие определенный набор данных, выбор из которых может производиться селектором по дополнительным правилам. •

Генераторы тестовых данных. Роль их, как видно из названия, состоит в построении некоторого набора 19

Тестовые оракулы (test oracles) или просто оракулы. Тестовый оракул [14,19,20] — компонент, ответственный за вынесение вердикта о соответствии или несоответствии поведения системы требованиям. Работа оракула часто в большой степени зависит от конкретной тестовой ситуации, от сценария данного теста. Однако оракул для сложного сценария часто получается некоторой композицией проверок корректности его отдельных действий. Проверки корректности работы отдельных операций гораздо проще использовать многократно в разных тестах и удобнее применять для отслеживания более точной информации об ошибке, например, точного нарушенного требования или конкретной операции, выполненной с ошибкой. Поэтому удобно определить оракул типа событий или оракул операции, которые привязываются к событиям соответствующего типа или к вызовам определенной операции и выносят вердикт о том, насколько поведение системы при возникновении событий такого типа или при различных обращениях к этой операции соответствует требованиям. Другая возможная разновидность таких оракулов — ограничения целостности данных. Они относятся к некоторому типу данных и должны проверяться каждый раз, когда данные такого типа передаются в тестируемую систему или принимаются от нее. Поскольку данные сами по себе не активны, а лишь используются в вызываемых операциях и возникающих событиях, обычно ограничения целостности данных используются всеми оракулами операций и событий, в которых затрагивается соответствующий тип данных. Выделение таких модульных оракулов оправдано двумя факторами. o

20

Требования формулируются, в основном, именно в отношении различных типов данных, типов событий или операций. Поэтому

будет найдена корректная или не будет показано, что подходящей последовательности нет, что означает ошибку. Другим примером является арбитр, один из компонентов, определяемых в профиле UML для разработки тестов [9]. Однако он играет только роль посредника, позволяя тестовым агентам, выносящим свои вердикты на основе доступной им информации, обмениваться данными об этих вердиктах друг с другом.

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

•

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

Кроме описанных выше оракулов, могут использоваться более сложные, композиционные оракулы. Они возникают в тех случаях, когда для вынесения вердикта о корректности поведения системы в некоторой ситуации требуется нетривиальный анализ многих разных его аспектов, который неудобно проводить в рамках одного компонента. Например, при оценке корректности данных достаточно сложной структуры, таких как XML-документы или программы на языках программирования, или даже документы, в которых может быть смешано несколько языков, проводить такую проверку в рамках одного компонента крайне неудобно — он становится крайне сложным, неудобным для модификаций и сопровождения. В таком случае ограничения целостности данных разбиваются на группы ограничений, относящихся только к определенным конструкциям, и правила корректного связывания конструкций, и для каждой такой группы можно иметь отдельный компонент, проверяющий ее ограничения. Общий оракул для документа в целом получается как некоторая композиция этих компонентов. Композиционные оракулы применяются и при тестировании распределенных систем. При этом обычно используют набор тестовых агентов, каждый из которых отслеживает поведение только одного компонента системы или небольшой их группы. Он сам может выносить вердикт о корректности событий, касающихся отслеживаемых компонентов, в том числе, используя оракулы отдельных событий. Однако к поведению системы в целом могут при этом предъявляться требования, которые ни один из таких агентов не в состоянии проверить самостоятельно. Тогда их проверка организуется в отдельном компоненте, который получает необходимую ему информацию от всех тестовых агентов. Примером такого составного оракула является сериализатор в технологии UniTESK [15,21], который проверяет правильность набора событий в соответствии с семантикой чередования, убеждаясь, что наблюдаемое поведение системы соответствует возникновению этих событий в некотором порядке (все равно в каком). Для этого он вызывает оракулы отдельных событий в разных последовательностях, пока не 21

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

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

тестируемой системы. Однако большинство инструментов управления тестами поддерживает использование только предопределенного набора квалификаторов, которые не могут быть расширены. Пока только HP/Mercury TestDirector [22] имеет возможность добавления пользовательских квалификаторов, которые можно затем использовать для построения специфических отчетов — группировки или отбрасыванию результатов тестов по значениям квалификатора. Более сложно с имеющимися подходами к управлению тестами интегрируются использование системы конфигурационных параметров, а также выделение разнообразных модулей и их многократное использование в тестах. Конфигурационные параметры можно использовать только в виде дополнительных квалификаторов, что далеко не всегда удобно, особенно для динамически устанавливаемых параметров. Проблема выделения различных модулей в сложных тестах стоит наиболее остро. Только в последние 5 лет появилось несколько подходов [6,11,14,18] к разработке тестов, уделяющих этому аспекту достаточно внимания. В то же время, общим элементом этих подходов, да и то не всех, можно считать выделение заглушек, адаптеров, генераторов тестовых данных и некоторых общесистемных компонентов тестов. Выделение более разнообразного набора модулей, включающего оракулы отдельных операций и событий, с одной стороны, является необходимым для повышения управляемости и гибкости современных сложных тестовых наборов, но с другой стороны, усложняет ряд традиционных видов деятельности — конфигурирование тестового набора и анализ обнаруживаемых им ошибок. Для разрешения возникающих проблем необходимо разработать новые техники решения соответствующих задач в модульных тестовых наборах.

[10] http://www.fokus.fraunhofer.de/u2tp/. [11] A. Hartman, K. Nagin. Model Driven Testing — AGEDIS Architecture Interfaces and Tools. Proceedings of the 1-st European Conference on Model Driven Software Engineering, Nuremburg, Germany, December 2003. [12] A. Hartman. AGEDIS Final Project Report, 2004. http://www.agedis.de/documents/FinalPublicReport%28D1.6%29.PDF. [13] http://www.agedis.de/. [14] I. Bourdonov, A. Kossatchev, V. Kuliamin, A. Petrenko. UniTesK Test Suite Architecture. Proceedings of FME’2002, Kopenhagen, Denmark, LNCS 2391:77-88, Springer, 2002. [15] V. V. Kuliamin, A. K. Petrenko, N. V. Pakoulin, A. S. Kossatchev, I. B. Bourdonov. Integration of Functional and Timed Testing of Real-time and Concurrent Systems. Proceedings of PSI’2003, Novosibirsk, Russia, LNCS 2890:450-461, Springer, 2003. [16] В. В. Кулямин, А. К. Петренко, А. С. Косачев, И. Б. Бурдонов. Подход UniTesK к разработке тестов. Программирование, 29(6):25-43, 2003. [17] К. Бек. Экстремальное программирование: разработка через тестирование. СПб.: Питер, 2003. [18] G. Meszaros. xUnit Test Patterns: Refactoring Test Code. Addison-Wesley, 2007. [19] D. Peters, D. Parnas. Using Test Oracles Generated from Program Documentation. IEEE Transactions on Software Engineering, 24(3):161-173, 1998. [20] L. Baresi, M. Young. Test Oracles. Tech. Report CIS-TR-01-02. http://www.cs.uoregon.edu/~michal/pubs/oracles.html. [21] А. В. Хорошилов. Спецификация и тестирование систем с асинхронным интерфейсом. Препринт 12 ИСП РАН, 2006. [22] http://www.mercury.com/us/products/quality-center/testdirector/.

Литература [1] V. Maraia. The Build Master: Microsoft's Software Configuration Management Best Practices. Addison-Wesley Professional, 2005. [2] G. Robles. Debian Counting. http://libresoft.dat.escet.urjc.es/debian-counting/. [3] Ю. Гуревич, Microsoft Research. Устное сообщение. 2004. [4] M. Lucovsky. Windows, a Software Engineering Odyssey. 4-th Usenix Windows Systems Symposium, 2000. http://www.usenix.org/events/usenix-win2000/invitedtalks/lucovsky_html/. [5] Software Engineering Body of Knowledge, 2004. http://www.swebok.org/ironman/pdf/SWEBOK_Guide_2004.pdf. [6] I. Schieferdecker; Z. R. Dai, J. Grabowski. The UML 2.0 Testing Profile and its Relation to TTCN-3. IFIP 15-th Int. Conf. on Testing Communicating Systems — TestCom 2003, Cannes, France, May 2003. [7] A. Cavarra. The UML Testing Profile. An Overview. 2003. http://www.agedis.de/documents/TheUMLTestingProfile.pdf. [8] Z. R. Dai. UML 2.0 Testing Profile. In M. Broy et al.,eds. Model-Based testing of Reactive Systems. Advanced Lectures. LNCS 3472:497-521, Springer, 2005. [9] UML Testing Profile, 2005. http://www.omg.org/docs/formal/05-07-07.pdf.

23

24

Методы обеспечения переносимости ПО Д. В. Силаков, А.В. Хорошилов {silakov, khoroshilov}@ispras.ru Аннотация. Статья посвящена проблеме переносимости приложений между программно-аппаратными платформами. Предлагается обзор подходов к решению этой проблеме, появившихся за время развития ИТ, а также анализ преимуществ и недостатков каждого из них. Рассматриваются области применения существующих решений.

1. Введение Проблема переносимости приложений между различными программноаппаратными платформами ненамного моложе собственно компьютерных программ. Еще в конце шестидесятых годов озабоченность некоторых сотрудников AT&T Labs проблемой переносимости ОС UNIX на новые аппаратные платформы привела к созданию языка Си. Темпы развития компьютерной индустрии таковы, что проблемы сорокалетней давности кажутся достаточно простыми и решаемыми, по сравнению с тем, что мы имеем сегодня. Стремительное развитие связанных с компьютерами отраслей приводит к постоянному появлению новых программно-аппаратных платформ, информационных систем, и т.п., в то время как устаревшие комплексы уходят в небытие. Производители ПО, как правило, заинтересованы в быстром переносе своих продуктов на новые системы, чтобы захватить соответствующую долю рынка. Если приложение изначально проектировалось с оглядкой на возможность портирования, то этот процесс может оказаться существенно дешевле создания нового продукта. Будет проще и конечным пользователям, которые в новой системе увидят то же самое приложение, с которым работали раньше, что также способствует популярности продукта. В некоторых случаях большое внимание переносимости приложений уделяется и производителями платформ, на которых эти приложения выполняются — например, одним из принципиальных аспектов при разработке IBM мэйнфрейма System/S370 в конце 60х-начале 70х годов было сохранение обратной совместимости с System/S360, с целью упростить миграцию приложений своих клиентов [1]. Обратная совместимость с 25

System/S360 сохранялась на протяжении всего жизненного цикла System/S370; более того, сохраняется она и в ее последователях — System/S390 и zSeries. Однако далеко не все производители столь щепетильны, и далеко не все платформы могут похвастаться столь длительным сроком жизни. Нередко с рынка уходят не только сами системы, но и их создатели, так что труднодоступными становятся не только сами системы, но и все сведения об их архитектуре. Исчезновение тех или иных платформ приводит к появлению унаследованного ПО — программных продуктов, необходимых для функционирования той или иной организации, но требующих для работы устаревшей программно-аппаратной платформы. В случае выхода из строя аппаратного обеспечения может оказаться, что найти ему замену очень сложно, дорого, а иногда и попросту невозможно, так как устаревшая ОС не работает на современном оборудовании (либо по причине принципиальных отличий архитектуры, либо по более прозаическим причинам — например, ввиду отсутствия необходимых драйверов). Для многих предприятий задача переноса таких приложений в более современное окружение является крайне актуальной [2,3].

2. Примеры из современности Несмотря на то, что о проблеме переносимости известно достаточно давно и ее решению посвящено множество работ и исследований, постоянно возникают ситуации, когда выясняется, что данному вопросу вовремя не было уделено должное внимание и это привело к неприятным последствиям. Рассмотрим несколько реальных примеров таких ситуаций. В начале 2000-х годов компания Borland решила обратить свой взор на ОС Linux и выпустила среду разработки Kylix — аналог Delphi и C++ Builder. Такой шаг был изначально положительно оценен Linux-сообществом (даже несмотря на то, что Kylix не являлся продуктом с открытым исходным кодом, а бесплатной была только базовая версия системы) — в то время в этой ОС не было сравнимых по функциональности аналогов упомянутых программ. Однако в основе Kylix лежал исходный код соответствующих сред разработки для ОС Windows, а для запуска на Linux использовался эмулятор wine[4]. Как показала практика, такой прямолинейный перенос, как использование эмулятора, не привел к созданию конкурентноспособного продукта — довольно быстро выяснилось, что wine не является достаточно надежным, чтобы гарантировать его стабильность [5]. Разработчикам приходилось иметь дело как с ошибками в своих программах, так и с некорректным поведением эмулятора. Ввиду закрытости проекта сложно оценить, насколько затратен был бы перенос программ на использование «родных» библиотек Linux; но основываясь на том факте, что работа над Kylix была заморожена, можно предположить, что задача оказалась слишком ресурсоемка. Другой пример недальновидного подхода к этому вопросу проявился в ходе организации проекта по разработке пакета свободного программного 26

обеспечения (СПО) для образовательных учреждений России. Практически все программное обеспечение, которое разрабатывалось по заказу Министерства образования РФ в последние годы было предназначено для работы исключительно на платформе Microsoft Windows. Поэтому при внедрении пакета СПО на основе операционной системы Linux большая часть разработанных ранее образовательных программ оказалась недоступна, и только часть из них удавалось запустить с помощью эмулятора wine [4]. Схожие проблемы возникали и в стане разработчиков web-приложений. Известно несколько случаев, когда при разработке интернет-сервисов заказчик ограничивался требованием совместимости с браузером Internet Explorer, а через некоторое время под давлением клиентов был вынужден дорабатывать ПО для поддержки набирающего популярность Mozilla Firefox. Например, на основе опроса пользователей приложения Tasktop о желаемых нововведениях, проведенного в 2008 году, выяснилось, что наиболее востребованными являются поддержка ОС Linux и браузера Firefox. Реализация этих свойств стала приоритетным направлением разработки, и была представлена пользователям уже в ноябре 2008 года, в Tasktop 1.3 [6]. Отметим, что добавление такого нетривиального свойства, как поддержка новой операционной системы, не заняло много времени, поскольку основная часть приложения написана на интерпретируемом языке Java, а виртуальные машины для исполнения этого кода существуют как в Windows, так и в Linux. Более того, разработчики Tasktop планируют портировать свой продукт и на MacOS — ввиду наличия в этой ОС виртуальной машины Java, такая задача также не представляется слишком сложной. Приведенные примеры демонстрируют, что изначальная нацеленность на создание переносимого продукта позволяет достаточно безболезненно портировать его на платформы, поддержка которых изначально не планировалась (либо которых просто не существовало в момент начала разработки). Это позволяет производителям не оставаться в стороне от стремительного развития рынка и своевременно реагировать на запросы пользователей. В то же время невнимание к проблеме переносимости может привести к различным негативным техническим, экономическим и политическим последствиям: − проблемам с поддержкой ПО в долгосрочной перспективе; − сокращению доступных рынков и недополучению прибыли; − попаданию в зависимость от одного поставщика. Как мы уже отметили, проблема известна давно, и за время эволюции программного обеспечения появилось достаточно много подходов к созданию приложений, переносимых между различными системами. Рассмотрим те из них, что представляются наиболее популярными. 27

3. Переиспользование бинарных файлов Перенос приложения на новую программно-аппаратную платформу может пройти безболезненно для разработчиков, если старая и новая системы совместимы на бинарном уровне, то есть новая система поддерживает двоичный интерфейс приложений (Application Binary Interface, ABI), что позволяет использовать старые двоичные файлы приложения без каких-либо изменений. Можно выделить две основные составляющие ABI: 1. форматы исполняемых файлов и библиотек; 2. набор библиотек и их функций, предоставляемых системой. Совместимость форматов является критичной для возможности использовать двоичные файлы без изменений. При этом формат файлов достаточно сильно связан с аппаратной частью платформы, на которой функционирует система в силу технических причин (разный размер указателей, различный порядок нумерации разрядов и т.п.) в общем случае сложно достичь совместимости систем, работающих на различных архитектурах. Что касается наборов библиотек и их функций, то их полной идентичности в различных системах ожидать трудно, однако во многих случаях пересечение множеств предоставляемых функций является достаточно большим. Многие производители операционных систем в настоящее время заботятся об обратной совместимости своих продуктов на бинарном уровне — гарантируется, что приложение, работающее в некоторой версии ОС, будет работать без перекомпиляции в более новых версиях системы на той же аппаратной архитектуре. В ряде случаев поддерживается возможность запуска приложений, написанных для той же системы, но на другой платформе — так, операционная система MacOS X, работающая на компьютерах Apple с процессорами Intel, использует динамический транслятор Rosetta для выполнения программ, предназначенных для машин с процессорами PowerPC [7]. Однако пользоваться такой возможностью следует с осторожностью. Во многих случаях совместимость обеспечивается за счет некоторого дополнительного слоя совместимости между системой и приложением, который может и не гарантировать полной совместимости — так, уже упомянутая Rosetta позволяет исполнять код для процессоров G3, G4 и AltiVec, но не для G5. Кроме того, дополнительный компонент системы является дополнительным потенциальным источником ошибок, а использование посредника в общем случае снижает производительность. Например, процессор Itanium способен выполнять код, созданный для платформы x86, однако производительность его в этом случае может уступать оригинальному x86 процессору с такой же тактовой частотой [8].

28

4. Переиспользование исходного кода К сожалению, в большинстве случаев совместимость на бинарном уровне выполняется в рамках систем одного производителя, однако лишь немногие системы способны загружать исполняемые файлы, предназначенные для выполнения на платформах других поставщиков. Альтернативой использованию одних и тех же бинарных файлов явилось использование одного и того же исходного кода для сборки приложения на различных системах. Исторически, возможность переноса исходного кода между различными платформами появилась не сразу. В те времена, когда программы писались на ассемблере конкретной аппаратной платформы, добиться компиляции приложения на системе с другой архитектурой было практически нереально. Существенной подвижкой в этом направлении стало создание высокоуровневых языков программирования, не привязанных к конкретной архитектуре и позволяющих использовать одни и те же конструкции на различных системах. Например, именно озабоченность некоторых сотрудников AT&T Labs проблемой переносимости ОС UNIX на новые аппаратные платформы привела к созданию языка Си. Для обеспечения возможности использования одного и того же кода целевые системы должны предоставлять компиляторы для соответствующего языка программирования, вместе с необходимыми библиотеками. Естественно, что компиляторы для различных систем создаются различными производителями и могут достаточно сильно отличаться друг от друга. Такие отличия следует учитывать при написании кода. Частично эта задача облегчается следованием международных стандартов, разработанных для многих языков программирования. Однако далеко не все компиляторы поддерживают стандарты в полном объеме (хотя, как правило, не поддерживаются некоторые специфические конструкции языка, в плане же предоставления библиотечных функций ситуация гораздо лучше). Другой проблемой является относительная узость стандартов — несмотря на наличие во многих из них перечня функций, которые должны предоставляться любой удовлетворяющей стандарту средой разработки, эти перечни не описывают существенную часть функциональности, которая могла бы быть полезна при создании приложений — например, функции графического интерфейса, либо функции работы с мультимедиа. Помимо стандартов языков программирования, существуют стандарты, описывающие интерфейс прикладных программ (API, Application Programming Interface) — например, POSIX. Однако такие стандарты также, достаточно узки, и являются недостаточными для написания большинства приложений. В случае, если необходимая приложению функциональность не охватывается ни одним из стандартов, могут быть использованы продукты сторонних 29

разработчиков, существующие на всех целевых системах и предоставляющие необходимые возможности. Такой продукт выступает в роли медиатора между приложением и операционной системой, скрывая от приложения процесс взаимодействия с последней. Характерным примером подобных продуктов являются кросс-платформенные библиотеки графического интерфейса пользователя — такие, как Qt, Gtk или wxWidgets. Реализация этих библиотек присутствует во всех основных операционных системах (FreeBSD, Linux, Windows, MacOS), а функции API, доступные программистам, практически идентичны для всех платформ. Кроме того, либеральность лицензий позволяет использовать эти библиотеки при создании достаточно большого спектра приложений. Если же медиатора, способного удовлетворить нужды разработчиков, не нашлось, то может быть целесообразно создать свой собственный, который можно будет использовать во многих продуктах компании. Такой подход оправдан, если можно четко выделить функциональность, которую должен предоставлять медиатор, и отделить реализацию этой функциональности от остальных частей продукта. Так, разработчики Mozilla в свое время решили создать собственный набор библиотек поддержки различных стандартов безопасности (в результате появился набор Network Security Services, NSS), а также собственную кросс-платформенную библиотеку, реализующую достаточно низкоуровневые функции (работы с потоками, памятью, вводомвыводом и т.п.). Результатом второй инициативы стало создание библиотеки NSPR (NetScape Portable Runtime). Отметим, что поскольку и NSS, и NSPR, являются продуктами с открытым исходным кодом, их использование в настоящее время не ограничивается проектами, разрабатываемыми Mozilla Foundation.

5. Использование интерпретируемого кода Еще одним подходом к обеспечению переносимости приложений является написание программного кода на интерпретируемых языках, использование которых не подразумевает создания исполняемых файлов в формате целевой операционной системы. Вместо этого интерпретатор последовательно считывает и выполняет инструкции непосредственно из текста программы. Прямолинейная интерпретация достаточно неэффективна — у интерпретатора практически нет возможностей для оптимизации кода. Для повышения эффективности во многих языках (Java, Perl, Python, семейство .NET) исходный код сначала транслируется в некоторое промежуточное представление (байт-код), который уже подается на вход интерпретатору. Стадия получения байт-кода фактически является разновидностью компиляции, и при ее осуществлении могут выполняться различные оптимизирующие преобразования. Однако и в этом случае зачастую не удается достигнуть производительности, присущей «родным» для системы приложениям, 30

поскольку определенная часть времени тратится на разбор байт-кода и транслирование его в вид, подходящий для исполнения в целевой среде. Большей производительности удается достигнуть при использовании компиляции “на лету” (Just In Time compilation), когда байт-код транслируется в машинный код во время работы программы. Однако разработчикам JITкомпиляторов также приходится идти на компромисс между временем, уходящим на оптимизацию, и эффективностью получаемого кода, в результате чего производительность приложений может уступать коду, создаваемому “обычными” компиляторами. Кроме того, использование данной технологии увеличивает потребление памяти приложением, поскольку оттранслированный код также хранится в оперативной памяти. Также следует иметь в виду, что эффективность реализации интерпретаторов, также как и JIT-компиляторов, на различных платформах может отличаться.

6. Использование эмуляторов ABI Говоря о бинарной переносимости, мы уже упомянули, что в ряде случаев операционная система может обеспечивать бинарную совместимость с другой системой за счет дополнительного слоя совместимости. При этом большинство существующих реализаций ограничивается обеспечением совместимости в рамках систем одного производителя. Из других примеров можно выделить поддержку запуска исполнимых файлов Linux в системе FreeBSD. Сам Linux также имел поддержку запуска исполнимых файлов других UNIX-систем, хотя эта функциональность не оказалась востребованной. В то же время существует много продуктов сторонних разработчиков, позволяющих загружать файлы других операционных систем путем использования транслятора, способного загружать файлы требуемого формата, преобразуя вызовы функций, осуществляемые внутри файла, в соответствующие вызовы текущей ОС (фактически, такой транслятор реализует ABI старой системы в новой системе). В качестве примера можно привести wine [4], предназначенный для запуска Windows-приложений в Linux, а также cygwin [9], обеспечивающий переносимость в обратную сторону. При этом, например wine достаточно легко использовать как часть приложения, не полагаясь на его доступность в целевой системе. Недостатком использования такого рода эмуляторов является потенциальная неполнота реализации интерфейса, необходимого приложению. Так, разработчики того же wine ориентируются на публично доступную информацию об API Windows (например, стандарт ECMA-234); так что если приложение использует какие-то недокументированные возможности этой ОС, то попытка его запуска в wine может оказаться неудачной. 31

Отметим, что для достижения высокой производительности программыэмуляторы зачастую используют достаточно низкоуровневые способы взаимодействия с системой, что, в свою очередь, ограничивает их собственную переносимость. Так, тот же wine содержит достаточно много кода на языке ассемблера архитектуры x86. Соответственно, использование этого эмулятора возможно либо в непосредственно x86 системах, либо в системах, предоставляющих возможность запуска x86 приложений. Поэтому при стремлении охватить большое число различных программно-аппаратных платформ, может возникнуть необходимость разных эмуляторов на различных системах. Кроме того, в определенных ситуациях прямолинейное использование эмуляторов по определению дает менее эффективные продукты, чем те, что используют «родные» средства целевой системы. В качестве примера можно привести уже упоминавшуюся ранее среду разработки Borland Kylix для Linux, основанную на использовании эмулятора wine. Косвенно использование эмулятора в этом случае означает использование тех же методик создания программ, которые применяются в исходной системе — ОС Windows. Однако, как показала практика, эмуляция этих методик не выдерживает конкуренции с аналогичными средствами ОС Linux — в частности, с компилятором GCC (прежде всего, в плане производительности программ, получаемых с помощью среды Kylix).

7. Виртуализация Альтернативой эмуляции ABI некоторой системы является запуск копии такой системы внутри основной ОС, с использованием программ, эмулирующих аппаратное обеспечение — виртуальных машин. На такой машине устанавливается операционная система и другое окружение, необходимое приложению, а само приложение запускается уже в родной для него среде. Возможность запуска приложения на виртуальной машине зависит, в основном, от возможностей самой машины, нежели от разработчиков приложения. Тем не менее, программы, работающие с аппаратурой напрямую, могут встретить определенные трудности, поскольку им будет предоставлен доступ к устройствам виртуальной машины, а не непосредственно компьютера. Такая особенность ограничивает, например, возможность работы с графическими ускорителями изнутри виртуальных машин. В общем случае использование виртуальной машины достаточно ресурсоемко — ведь помимо собственно приложения, ресурсы компьютера потребляются самой машиной, а также работающими внутри нее программами, необходимыми для функционирования приложения (например, операционной системой). Поэтому выигрыш в производительности достигается, как правило, только в случае запуска машин, эмулирующих достаточно маломощные платформы на более производительных системах. 32

Проблеме производительности виртуальных машин уделялось много внимания еще в 70-е годы. Впервые требования, которым должна удовлетворять аппаратная архитектура машины, чтобы на ней можно было эффективно реализовать виртуализацию, были сформулированы Попеком и Голдбергом в 1974 году [10]. Основное требование сводится к разделению всех инструкций по разным уровням привилегий; при этом все инструкции, способные изменить состояние ресурсов виртуальной машины, а также инструкции, поведение которых зависит от конфигурации этих ресурсов, должны быть привилегированными. Монитор виртуальных машин (Virtual Machine Monitor, VMM — программная прослойка, занимающаяся распределением физических ресурсов между работающими виртуальными машинами), сам работая с наивысшими привилегиями, может перехватывать эти инструкции и эмулировать их поведение в соответствии со своими потребностями. Все непривилегированные инструкции должны выполняться непосредственно на аппаратуре. Поскольку доля привилегированных инструкций, как правило, невелика, то и затраты на их эмуляцию будут малы. Несмотря на то, что работа Голдберга и Попека посвящена машинам третьего поколения (IBM 360, Honeywell 6000, DEC PDP-10), сформулированные в ней требования справедливы и сегодня. Однако, для большинства современных архитектур приведенное выше требование не выполняется — существуют непривилегированные инструкции, влияющие на конфигурацию ресурсов либо зависящие от нее. В частности, для «классической» архитектуры x86 к числу таких инструкций относятся такие популярные инструкции, как push/pop, call, jmp и другие (более подробно данная проблема рассмотрена в [11]). Безусловно, построение виртуальной машины возможно и при наличии таких инструкций. Существуют подходы по определению и перехвату необходимых инструкций в процессе работы программы; по такому принципу работают популярные продукты типа VirtualBox [12] и VMWare [13], старающиеся напрямую выполнять все инструкции, для которых это возможно. Тем не менее, необходимость дополнительного отслеживания выполняемых инструкций может замедлить производительность программ внутри виртуальной машины по сравнению с «живой» системой. Отметим, что осознание разработчиками важности виртуализации привело к появлению расширений от Intel (Intel Virtualization Technology [14]) и AMD (AMD Virtualization [15]) для ее поддержки на платформах x86 и x86-64, которые позволяют либо вовсе избавится, либо существенно снизить число перехватываемых и эмулируемых инструкций. Альтернативным методом борьбы с «вредоносными» инструкциями является паравиртуализация, основанная на внесении изменений в гостевую операционную систему перед ее запуском в виртуальной среде; известным примером машин, работающих по принципу паравиртуализации, является Xen [16]. Однако в реальной жизни такая модификация не всегда доступна 33

конечным пользователям. Существуют и гибридные подходы — например, проект vBlades для Itanium [17]. Стоит обратить внимание и на экономическую составляющую использования виртуальной машины конечным пользователям — в ряде случаев стоимость операционной системы и компонентов окружения, которые необходимо установить, может быть довольна значительна. Поэтому достаточно редки ситуации, когда производители сами советуют использовать виртуальные машины для запуска своих программ в системах, не поддерживаемых напрямую. Примерами исключений являются различные специфические системы, безопасное функционирование которых требует запуска в изолированной среде. Например, обучающая система Linuxgym [18] распространяет клиентскую часть в виде образа VMware, содержащего Ubuntu Linux с предустановленными необходимыми компонентами.

8. Использование Web-технологий Становящиеся с каждым годом все популярнее web-технологии также могут быть использованы для повышения переносимости программных продуктов. Можно выделить два основных способа построения приложений, использующих эти технологии: − создание полностью локального приложения, располагающегося на машине пользователя, и использующего web-браузер для взаимодействия с ним; − реализация приложения в виде сервиса; при этом серверная и клиентская части приложения могут быть разнесены на разные машины. Такое разделение довольно условно, поскольку в первом случае приложение также, как правило, имеет серверную и клиентскую части, и может допускать подключение клиентов с других машин. Например, подобным образом устроен Web-интерфейс сервера печати CUPS (Common Unix Printing System), который может быть использован для настройки принтеров как на локальной, так и удаленных машинах. В любом случае, использование web-браузера и сопутствующих инструментов облегчает задачу разработки графического интерфейса пользователя. Программа может либо создавать HTML-представление интерфейса, непосредственно интерпретируемое браузером, либо использовать технологии типа Flash, Silverlight и JavaFX, позволяющие создавать интерактивные файлы, для воспроизведения которых достаточно наличия соответствующего проигрывателя на целевой платформе. Зачастую такой проигрыватель встраивается в браузер как расширение. Однако хотелось бы подчеркнуть, что во многих ситуациях требования к среде, где функционирует серверная части приложения, существенно более 34

строгие, чем требования к клиентской системе. Последние зачастую сводятся к требованию наличия браузера, поддерживающего определенные возможности. Для серверной же части может требоваться вполне конкретная программно-аппаратная платформа. Использование web-браузера для отрисовки графического интерфейса имеет как преимущества, так и недостатки. К преимуществам, помимо упомянутого выше снижения затрат на разработку, стоит отнести возможность настройки интерфейса пользователем по своему вкусу — изменением шрифтов, масштаба страницы и т.п. Основной недостаток подхода является следствием его достоинств — в разных браузерах одна и та же страница может отображаться по-разному — как вследствие пользовательских настроек, так и из-за особенностей конкретного браузера. Безусловно, существуют различные стандарты на HTML, CSS, JavaScript и прочие элементы, используемые при отображении web-документов, однако разные браузеры соответствуют этим стандартам в разной степени [19]. Поэтому разработчикам приходится либо проводить тестирование на различных браузерах [20], либо ограничиваться поддержкой только некоторых из них. Для автоматизации процесса тестирования существуют различные свободно доступные инструменты — например, сервис BrowserShots [21] позволяет получить снимки экрана с видом заданной страницы в различных браузерах (на данный момент доступно более 80) в Linux, Mac OS и Windows. Также отметим, необходимость создания больших распределенных систем привела к созданию архитектур, более сложных, чем клиент-серверная, и подразумевающих взаимодействие множества компонентов различной структуры. Исследования проблем разработки сложных программных комплексов привели к разработке парадигм, подразумевающих разбиение системы на отдельные компоненты, которые взаимодействуют друг с другом по строго определенным протоколам. При таком подходе каждый компонент не только может работать на отдельной машине, но также разрабатываться независимо от других. При этом (в идеале) процесс переноса компонента на другую платформу либо замена его на альтернативную реализацию никак не затрагивает других частей системы. К одной из первых попыток описания механизма взаимодействия компонентов распределенной системы можно отнести спецификацию CORBA (Common Object Request Broker Architecture), разработанную консорциумом OMG [22]. Однако CORBA в силу ряда причин не снискала большой популярности, и в настоящее время гораздо больший интерес проявляется к web-сервисам, использующим протоколы обмена сообщениями на базе XML. При проектировании сложных распределенных программных комплексов используется парадигма сервисно-ориентированной архитектуры (Serviceoriented architecture, SOA [23]); при этом программные комплексы часто реализуются как набор web-сервисов. 35

9. Заключение Если невнимание к проблеме переносимости приводит к негативным последствиям и существует множество путей по ее решению, то возникает вопрос: так почему же ИТ индустрия не переориентируется на разработку переносимого ПО? Несложно догадаться, что разработка переносимого ПО имеет свои недостатки. Среди рассмотренных видов переносимости приложений очень привлекательным с точки зрения разработчиков является перенос непосредственно бинарных файлов на новую систему, позволяющий при относительно небольших затратах (в основном уходящих на тестирование) получить на новой системе приложение, имеющее всю необходимую функциональность. При этом потери в производительности если и возникают, то совсем небольшие. Однако для любой ОС число платформ, совместимых с ней на бинарном уровне, достаточно невелико. Использование эмуляторов может расширить их круг, но эмулятор — дополнительный потенциальный источник ошибок, который при этом может и не предоставлять всех необходимых функций. Потенциально больший охват дает переносимость исходного кода. Сложность портирования в этом случае может варьироваться в зависимости от того, насколько такая возможность учитывалась при разработке приложения; полезной с этой точки зрения является ориентация на различные интерфейсные стандарты, регламентирующие взаимодействие приложения с окружающей средой. Но существующие стандарты охватывают достаточно небольшую функциональность; в ряде случаев может помочь использование кросс-платформенных библиотек, другой же альтернативой является использование интерпретируемых языков. Спецификации таких языков не привязаны к конкретной платформе и можно полагаться на то, что интерпретаторы на разных системах поддерживают один и тот же набор функций. Среди недостатков подхода можно выделить меньшую производительность по сравнению с бинарным кодом. Архитектура SOA затрагивает более сложную проблему организации сложных программных комплексов, предлагая строить их в виде набора достаточно изолированных компонентов, каждый из которых может работать на своей собственной платформе и в случае необходимости может быть перенесен на другую (либо заменен на альтернативную реализацию). Использование виртуальных машин также не требует больших усилий со стороны разработчиков ПО, хотя этот способ достаточно накладен, как в смысле производительности, так и ввиду необходимости иметь лицензии на все используемые операционные системы. Применение виртуализации оправдано в тех случаях, когда перенос приложения каким-то другим способом представляется экономически неэффективным. В частности, это относится ко многим унаследованным системам, для которых портирование 36

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

Примеры

Ориентация на стандарты

Ряд утилит GNU (tar, wget и др.), написанные с ориентацией на POSIX

Медиаторы сторонних разработчиков

Skype — использование библиотеки Qt для реализации GUI

Собственные медиаторы

Mozilla Firefox — использование собственных кроссплатформенных библиотек NSS (Network Security Services) для поддержки различных стандартов безопасности

Эмуляция

Google Picasa — применение wine для работы в Linux

Виртуализация

Linuxgym — клиент распространяется в виде образа VMware

Таблица 1. Примеры использования различных подходов к обеспечению функционирования приложений как в Windows, так и в Linux. Вопрос обеспечения переносимости следует рассматривать в самом начале проекта, на стадии проектирования и выбора технологий и инструментов, которые будут использованы при его реализации. К сожалению, вряд ли можно сформулировать универсальное правило выбора средств для увеличения переносимости – такой выбор сильно зависит от конкретных требований, предъявляемых к приложению. На взгляд авторов, в настоящее время потенциально наибольший охват дает использование интерпретируемых языков – многие интерпретаторы работают на достаточно большом числе программно-аппаратных платформ. Естественно, использование таких языков имеет свои недостатки, и для ряда приложений может оказаться неприемлемым. Следующим по масштабу «охвата», на наш взгляд, идет использование кроссплатформенных библиотек и других медиаторов. Однако медиаторов, реализующих нужную функциональность, может и не существовать, а разработка 37

собственных – оказаться достаточно трудоемким процессом. Тем не менее, даже при отказе от поддержки нескольких систем ввиду отсутствия средств и при ориентации на одну конкретную платформу, стоит строить архитектуру приложения таким образом, чтобы по возможности отделить части, использующие специфические для данной платформы интерфейсы и сервисы. Подводя итоги, отметим, что возможны ситуации, когда отказ от обеспечения переносимости разрабатываемого ПО оправдан; например, с достаточно большой долей вероятности такой выбор будет выгоден в краткосрочной перспективе. Однако при создании продуктов, которые планируется поддерживать в течении достаточно длительного периода, обеспечение переносимости может оказаться одним из ключевых факторов успеха. Повышение мобильности приложения в общем случае всегда связано с увеличением расходов на его разработку; однако чем раньше об этой проблеме задумаются разработчики и архитекторы, тем меньше будет стоимость переноса приложения на новую платформу. Литература [1] James D. Mooney. "Bringing Portability to the Software Process". // Technical Report TR 97-1, Dept. of Statistics and Computer Science, West Virginia University, Morgantown WV, 1997. [2] Ian Sommerville. Software Engineering, 8th Edition, Addison Wesley, 2006. [3] Wikipedia, the free encyclopedia. IBM System/370. http://en.wikipedia.org/wiki/System/370 [4] Wine - Open Source implementation of the Windows API. http://www.winehq.org/ [5] Borland's Net Loss Desaster. // Архив дискуссионного листа «borland.public.delphi.non-technical». Август 2005. http://coding.derkeiler.com/pdf/Archive/Delphi/borland.public.delphi.nontechnical/2005-08/msg01903.pdf [6] Ryan Slobojan. Tasktop 1.3: Support Added for Firefox and Linux. // InfoQueue News. Nov 12, 2008. http://www.infoq.com/news/2008/11/tasktop-13 [7] Apple Rosetta. http://www.apple.com/rosetta/ [8] Андрей Ященко. 64-x битные процессоры. // 3DNews, 7 августа 2003. http://www.3dnews.ru/cpu/cpu-64/index2.htm [9] Cygwin - Linux-like environment for Windows. http://www.cygwin.com/ [10] Gerald J. Popek, Robert P. Goldberg. Formal Requirements for Virtualizable Third Generation Architectures. // Communications of the ACM, Volume 17, Issue 7, July 1974, pp. 412-421. [11] Крис Касперски. Аппаратная виртуализация или эмуляция "без тормозов". http://www.insidepro.com/kk/159/159r.shtml [12] Virtual Box. http://www.virtualbox.org [13] VMware. http://www.vmware.com [14] Matias Zabaljauregui. Hardware Assisted Virtualization. Intel Virtualization Technology. Buenos Aires, June 2008. http://linux.linti.unlp.edu.ar/kernel/wiki/images/f/f1/Vtx.pdf [15] AMD Virtualization. http://www.amd.com/us-en/0,,3715_15781,00.html

38

[16] Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebarger, Ian Pratt and Andrew Warfield. Xen and the Art of Virtualization. // Proceedings of the 19th Symposium on Operating Systems Principles, October 2003. [17] Daniel J. Magenheimer, Thomas W. Christian. vBlades: Optimized Paravirtualization for the Itanium Processor Family. // Proceedings of the 3rd Virtual Machine Research & Technology Symposium. May, 2004. pp 73–82, USENIX. [18] Linuxgym Teaching System. http://www.linuxgym.com/ [19] Tom Dahm. Browser Compatibility Tutorial. http://www.netmechanic.com/products/Browser-Tutorial.shtml [20] Browser Tests, Services and Compatibility Test Suites. // Smashing Magazine, October 2007. http://www.smashingmagazine.com/2007/10/02/browser-tests-services-andcompatibility-test-suites/ [21] http://browsershots.org/ [22] OMG CORBA 3.0. http://www.omg.org/ technology/documents/formal/corba_2.htm [23] Ben Margolis, Joseph Sharpe. SOA for the Business Developer: Concepts, BPEL, and SCA. MC Press, 2007.

39

Применение технологии UniTESK для функционального тестирования инфаструктурного ПО Грид Н.В. Пакулин, С.А. Смолов {npak, ssedai}@ispras.ru Аннотация. В статье рассматриваются вопросы тестирования инфраструктурного программного обеспечения (ИПО, middleware) Грид-систем на соответствие стандарту. Грид-системы в настоящий момент являются одним из приоритетных направлений в вычислительной технике. Потому первоочередной задачей становится эффективное использование их преимуществ, что неразрывно связано с проблемой переносимости программного обеспечения Грид-систем. Одним из наиболее простых решений этой проблемы является введение стандартов на программные комплексы. Следовательно, соответствие стандарту представляется одним из основных требований, предъявляемых к системе, а потому его выполнение должно быть подтверждено с высокой достоверностью. В статье рассматривается разработка тестовых наборов для ИПО Грид средствами технологии автоматизированного тестирования UniTESK. Приведены результаты тестирования программного пакет Globus Toolkit 4.2 на соответствие базовому стандарту WSRF 1.2.

1. Введение Грид (англ. grid – решетка, сеть) – это согласованная, открытая и стандартизованная компьютерная среда, которая обеспечивает гибкое, безопасное и скоординированное использование вычислительных ресурсов и данных. Термин “Грид” появился в начале 1990-х гг. в сборнике “The Grid: Blueprint for a new computing infrastructure” [1] под редакцией Яна Фостера как метафора о такой же легкости доступа к вычислительным ресурсам, как и к электрической сети (англ. power grid). Создание Грид-систем было продиктовано необходимостью повышения вычислительных мощностей ресурсов. Так как требования к точности получаемых результатов и скорости работы вычислительных комплексов неуклонно растут, то возникает вопрос: как удовлетворить таким требованиям с наименьшими затратами? Один из возможных способов разрешения данной проблемы заключается в объединении различных ресурсов в одну систему. Причем необходимо, чтобы “объединенный” ресурс работал как единое целое даже при отсутствии централизованного управления. Не должна также 41

оказывать никакого отрицательного влияния на работоспособность системы и разнородность ресурсов, хотя особенности каждого из ресурсов также должны учитываться (для оптимизации времени выполнения). Что же касается конечного пользователя, то он может и не иметь никакого понятия о том, как именно устроена система. Зато предполагается возможность коллективного разделяемого режима доступа к ресурсам и связанным с ними услугами в рамках глобально распределенных виртуальных организаций, состоящих из предприятий и отдельных специалистов, совместно использующих общие ресурсы. Согласно Яну Фостеру, Грид-система [2] (далее ГС) – это система, которая: а) координирует использование ресурсов при отсутствии централизованного управления этими ресурсами; б) использует стандартные, открытые и универсальные протоколы и интерфейсы; в) нетривиальным образом обеспечивает высококачественное обслуживание. ГС, следуя определению, является универсальной инфраструктурой обработки и хранения распределенных данных, в которой функционируют различные службы, называемые Грид-сервисами. Последние не только позволяют решать конкретные задачи, но и могут предоставлять определенные услуги, например поиск ресурсов, сбор информации об их состоянии, хранение и доставка данных. Ясно также, что из определения проистекает высокая специфичность соответствующего ПО ГС. Особого внимания заслуживает второй пункт определения. В нём указано, что различные ГС могут и должны поддерживать стандартные протоколы и интерфейсы, несмотря на расхождения в архитектуре или особенности реализации. Иными словами, любая ГС должна соответствовать определенному набору стандартов. Цель стандартизации ГС – обеспечить переносимость вычислительных приложений между различными Гридами, в том числе построенных на различных инфраструктурных программных пакетах.

1.1. Стандартизация Грид Реализации ГС начали появляться с 1995 года, когда появился инфраструктурный программный пакет Globus Toolkit, ныне являющийся дефакто стандартом ГС. Он был выпущен организацией Globus Alliance [3] – крупнейшим международным консорциумом в области Грид. В 1997 году был начат европейский проект по созданию программного пакета для ГС, приведший к созданию ИПО UNICORE[4]. В 2004 году под эгидой проекта EGEE (Enabling Grids for E-sciencE) был выпущен пакет gLite[5]. С появлением большого числа несовместимых между собой реализаций ИПО Грид необходимость унификации и стандартизации стала актуальной, и началась активная работа над созданием стандартов Грид. В 2004 году 42

компания OASIS объявила о выходе стандарта WSRF [7] (Web Services Resource Framework), а в 2005 году Global Grid Forum – о стандарте OGSA [6] (Open Grid Services Architecture). В том же 2005 году компания Microsoft выпустила ещё один стандарт, определяющий управление разнородными ресурсами – WS-Management[8]. Таким образом в настоящее время действуют три группы стандартов для ИПО Грид.

1.2. Вопросы тестирования реализаций Грид Одной из особенностей предметной области является наличие ряда, вообще говоря, несовместимых стандартов и нескольких независимых реализаций. Заметим, что в данной работе не решается задача анализа адекватности стандартов, т.е. не только не утверждается, но и не проверяется гипотеза о том, что реализации, соответствующие одному и тому же стандарту, совместимы. Однако ясно, что весьма актуальной задачей является тестирование реализации на соответствие стандарту. Также стоит отметить, что в предметной области имеет место специфичность средств взаимодействия пользовательских приложений и самой ГС – в данном случае это Грид- и Web-сервисы, а также удаленные вызовы процедур. Webсервис[10] – это программная система, идентифицируемая строкой URI (Uniform Resource Identifier – некоторая последовательность, однозначно определяющая физический или абстрактный ресурс), чьи общедоступные интерфейсы определены на языке XML (eXtensible Markup Language – расширяемый язык разметки, предоставляющий возможность хранения структурированных данных для обмена ими между программами). Описание этой программной системы может быть найдено другими программными системами, причем последние могут с ней взаимодействовать, обмениваясь сообщениями в формате XML с помощью протоколов Интернета (например, SOAP[13]) . Наиболее распространенными подходами к тестированию ГС являются следующие: 1. Модульное тестирование (Unit testing) – тестирование различных модулей исходного кода ПО. При таком подходе тесты пишутся для каждой нетривиальной функции или метода в отдельности. В частности, разработчики ИПО Globus toolkit широко используют JUnit для проверки реализации. 2.

Интеграционное тестирование (Integration testing, оно же тестирование взаимодействия) – тестирование выполнения приложений на сборке ИПО Грид. Типичными примерами интеграционных тестовых сценариев являются пересылки больших массивов данных и проведение типовых расчетов[9]. 43

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

1.3. Технология автоматизированного тестирования UniTESK С 1994 года в ИСП РАН разрабатывается технология автоматизированного тестирования UniTESK, которая с успехом использовалась для тестирования различных классов программных систем – программных интерфейсов, телекоммункационных протоколов, аппаратного обеспечения. Доступ к ИПО Грид реализуется посредством различных механизмов удаленных вызовов процедур и служебных протоколов, что близко к области применимости UniTESK, поэтому данная технология была выбрана в качестве технологической платформы для разработки тестов. Мы не будем здесь подробно описывать данную технологию, а остановимся лишь на основных этапах разработки тестов с её применением. Разработка тестов с применением технологии UniTESK ведется в следующие 7 этапов: 1. анализ требований и их формализация, построение формальных спецификаций; 2.

формулировка требований к качеству тестирования;

3.

разработка покрытие;

4.

привязка тестовых сценариев к конкретной целевой системе посредством разработки медиаторов;

5.

получение готового тестового набора (трансляция и компиляция тестов);

6.

отладка и исполнение тестов;

7.

анализ результатов тестирования.

тестовых

сценариев,

реализующих

заданное

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

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

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

области

2.

разработка медиаторов для оказания воздействий на ИПО Грид;

Рассмотрим характерные особенности стандартов, использующихся при разработке ИПО Грид: OGSA и WSRF. Стандарт OGSA описывает инфраструктурное ПО (далее ИПО) OGSI (Open Grid Services Infrastructure), занимающее “промежуточное” положение между приложениями пользователей и непосредственно вычислительными ресурсами. Это означает, что приложения не могут взаимодействовать с ресурсами напрямую, а только с ИПО. Таким образом, от пользователей скрывается внутренняя структура ГС, и им совершенно нет нужды вникать в детали реализации вычислений на самих ресурсах, приложение взаимодействует только с этой промежуточной средой. В основе архитектуры OGSI лежит понятие Грид-сервиса, который представляет собой механизм удаленных вызовов, разработанный специально для Globus Toolkit версии 3. Посредством удаленного доступа к методам Грид-сервиса приложение получает определенный вид обслуживания. Таким образом, унифицируются различные функции: доступа к вычислительным ресурсам, ресурсам хранения, базам данных и к любой программной обработке данных. Однако, при всех своих достоинствах, концепция грид-сервисов имеет ряд недостатков. Во-первых, само понятие Грид-сервиса недостаточно формализовано, а это означает, что в различных реализациях Грид-сервисами могут быть совершенно разные, зачастую даже несовместимые сущности. Вовторых, наиболее близким аналогом Грид-систем можно считать Web. Соответственно, представляется разумным обеспечить их совместимость, чего столь специфичное решение, как Грид-сервисы, дать не может. Одновременно с разработкой стандарта OGSA, в 2004 году консорциум OASIS предложил стандарт WSRF. Он также описывает некоторое ИПО, в основе которого, однако, лежат уже не Грид- а Web-сервисы. А в 2005 году был опубликован стандарт WS-Management, фактически, представляющий собой протокол для управления серверами, устройствами, и приложениями, основанный на использовании всё тех же Web-сервисов. В последней версии Globus Toolkit разработчики отказались от использования Грид-сервисов в пользу Web-сервисов. За основу была взята спецификация WSRF. Соответственно, областью определения данной работы является именно ИПО, основанное на Web-сервисах, так как на этой концепции базируются наиболее широко используемые реализации ИПО Грид. 45

3.

разработка тестовых сценариев для ИПО Грид.

1.4. Стандарты OGSA и определения задачи

WSRF.

Ограничение

2. Формализация требований к реализациям ИПО Грид 2.1. Регламентирующие документы реализациям ИПО Грид

и

требования

к

Как упоминалось во введении, в настоящее время при разработке ИПО Грид используются два семейства стандартов: OGSA и WSRF. Рассмотрим особенности формализации требований указанных стандартов. При изучении стандарта OGSA оказалось, что: 1. стандарт носит описательный характер, требования нечётко выражены; 2.

стандарт практически не содержит функциональных требований;

3.

в стандарте не приводятся описания форматов сообщений и протоколов удаленного обращения к сервисам;

4.

стандарт признан устаревшим по сравнению с новыми подходами к организации удаленных вызовов, основанных на Web-сервисах.

По этим причинам стандарт OGSA не подходит в качестве основы для разработки формальных спецификации и основанного на них тестового набора. Стандарт WSRF больше подходит для формализации. Стандарт содержит 5 спецификаций: 1. WS-BaseFaults – определяет формат сообщений об ошибках и механизм их обработки;

46

2.

WS-Resource – определяет само понятие WS-Resource, форматы сообщений и семантику сервисов управления ресурсом;

3.

WS-ResourceLifetime – определяет механизмы прекращения существования WS-Resource;

4.

WS-ResourceProperties – определяет, как WS-Resource связан с

интерфейсом, описывающим Web-сервис, а также позволяет извлекать, изменять и уничтожать свойства WS-ресурса; 5.

WS-ServiceGroup – определяет интерфейс к набору гетерогенных Web-сервисов.

Рассмотрим понятие ресурса (Resource) и WS-ресурса (WS-Resource), введенных в WS-Resource. Ресурс – это логическая сущность, обладающая следующими характеристиками: 1. идентифицируемость; 2.

наличие “времени жизни”;

3.

наличие множества (быть может пустого) свойств, представимых в XML InfoSet [14].

Теперь перейдем к понятию WS-ресурса. WS-ресурс представляет собой композицию ресурса и Web-сервиса, посредством вызова методов или полей которого осуществляется доступ к ресурсу. WS-ресурс также должен быть идентифицируемым (роль идентификатора должен играть XML элемент типа EndpointReference, описание которого содержится в стандарте WSAddressing[15]), а множество свойств ресурса, ассоциированного с сервисом, – представимым в XML InfoSet. Стандарт WSRF весьма удобен для анализа по причине его структурированности. Так, например, большая их часть функциональных требований снабжена ключевыми словами стандарта RFC 2119 [10] – MUST, SHOULD, MAY. Кроме того, большинство требований снабжено блоками объяснений и примерами, написанными на псевдокоде, имеющем много общего с языком WSDL 2.0 [11] описания Web-сервисов. Отдельные части стандарта имеют различные уровни обязательности в градации RFC 2119. А именно: WS-ресурс обязан (MUST) реализовывать требования спецификаций WS-Resource и WS-ResourceProperties, ему следует (SHOULD) руководствоваться требованиями WS-BaseFaults и он может (MAY) удовлетворять требованиям WS-ResourceLifetime. Следовательно, при создании тестового набора наиболее пристальное внимание нужно уделить именно первым двум обязательным спецификациям. Действительно, такой подход существенно упрощает как структуру тестового набора, так и его размер, при этом сохраняя корректность тестов как решения задачи соответствия. Итак, спецификация WS-Resource содержит определения ресурса и WSресурса. Также она содержит описания двух сообщений об ошибках, которые WS-ресурс может (MAY) возвращать в ответ на запросы. Что же касается спецификации WS-ResourceProperties, то в ней описан следующий способ хранения свойств WS-ресурса. Каждое свойство WS-ресурса представляет собой XML-элемент, полями которого являются уникальное имя свойства (в 47

терминах спецификации WS-ResourceProperties – QName), значение свойства и, возможно, служебные параметры. Все свойства ресурса объединены в некоторую композицию, называемую Resource Property Document (далее RPD), имеющую собственный идентификатор. Иными словами, свойства ресурса являются дочерними элементами по отношению к некоторому корневому элементу – фактически, идентификатору RPD. Вместе с тем не указывается, каким именно образом сервис должен реализовывать свой RPD. В спецификации WS-ResourceProperties описаны следующие обмены сообщениями: 1. GetResourcePropertyDocument – получение всех свойств WSресурса; 2.

GetResourceProperty – получение определенного свойства WSресурса;

3.

GetMultipleResourceProperties – получение нескольких свойств WS-ресурса;

4.

QueryResourceProperties – выяснение структуры свойств WSResource и выполнение запросов к RPD и вычислений над его элементами (отдельно указывается диалект, на котором записано вычисляемое выражение, примером такого диалекта может служить язык XPath[16]);

5.

PutResourcePropertyDocument – замена всего RPD WS-ресурса “новым” RPD;

6.

SetResourceProperties – изменение нескольких свойств WSресурса (фактически, некоторая композиция следующих трех обменов сообщениями);

7.

InsertResourceProperties – добавление новых свойств WS-ресурса;

8.

UpdateResourceProperties – изменение значений свойств WSресурса;

9.

DeleteResourceProperties – удаление свойств WS-ресурса.

В ходе анализа стандартов были выделены 325 функциональных требований, из них 29 относятся к спецификации WS-BaseFaults, 12 – к WS-Resource, 51 – к WS-ResourceLifetime, 159 – к WS-ResourceProperties, 73 – к WSServiceGroup.

2.2. Разработка формальной спецификации Каждый обмен сообщениями в WSRF представляет собой пару где в качестве ответа может быть сообщение с возвращаемым значением или сообщение об ошибке. Тем самым обмены сообщениями WSRF 48

можно представить как вызовы функций с возвращаемым значением, а сообщения об ошибках моделировать как исключения. Благодаря этому в рассматриваемом методе формализации требований к ИПО Грид Web-сервис моделируется как объект некоторого класса, а обмены сообщениями между клиентом ИПО и реализацией представляются как вызовы методов объекта. Модельное состояние сервиса формализуется как набор полей объекта. Такой способ моделирования неявно подразумевает синхронный сценарий взаимодействия между клиентом и сервисом: после отправки запроса клиент ожидает ответа. Не допускаются сценарии, в которых клиент может послать серию запросов, не дожидаясь ответов. Однако, анализ сценариев использования Грид-систем показал, что большинство современных клиентских приложений разрабатываются в синхронной парадигме. Более того, сам стандарт WSRF описывает семантику поведения сервиса в синхронном стиле. По этим причинам в рассматриваемом методе к формализации требований мы моделируем обмены сообщениями между клиентом и ИПО Грид как процедурные вызовы. В модельное состояние ресурса необходимо включить переменные для представления свойств ресурса и окружения: 1. EndpointReference – модель идентификатора WS-ресурса, т.н. ссылка на конечную точку, удовлетворяющая требованиям стандарта WS-Addressing адресации Web-сервисов; 2.

ResourcePropertyDocument – модель RPD WS-ресурса как множества элементов, моделирующие отдельные свойства (properties) ресурса;

3.

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

4.

CurrentTime – переменная, определяющая текущее системное время;

5.

TerminationTime – переменная, определяющая прекращения существования WS-ресурса.

время

Наличие первого поля определяется требованием спецификации WS-Resource об идентифицируемости. Что же касается второго и третьего пунктов, то на них стоит остановиться поподробнее. Свойство ресурса как элемента RPD в спецификации моделируется классом со следующими полями: идентификатор-имя свойства (QName), значение свойства и минимальное количество его включений в RPD. Наличие последнего поля продиктовано рядом требований стандарта, касающихся тех свойств WS-ресурса, у которых оно является нулевым, т.е. наличие этого свойства, вообще говоря, необязательно. 49

Что касается третьего пункта, то его наличие связано со спецификой организации стандарта WSRF 1.2. Дело в том, что требования стандарта, находящиеся даже в одной и той же его части, совершенно необязательно имеют один и тот же “ранг” в градации RFC 2119, т.е. ключевые слова в них различные. В таблице 1 изображено распределение требований по частям стандарта в зависимости от их “ранга”: WS-Base Faults

WSResource

WS-Resource WS-Resource WS-Service Properties Lifetime Group

17

6

115

30

41

SHOULD 1

0

12

8

15

MAY

6

32

13

17

MUST

11

Таблица 1. Распределение требований по отдельным частям стандарта WS-RF. Таким образом, в спецификации было формализовано около половины всех требований стандарта WSRF (порядка 160 требований), и порядка 60% содержащихся в частях WS-Resource, WS-ResourceLifetime и WSResourceProperties стандарта WSRF требований. Реализация остальных требований осуществлялась в медиаторе. Стоит также упомянуть о полях CurrentTime и TerminationTime класса WSResourceSpecification. Они используются для формализации требований “времени жизни” из спецификации WS-Resource, а также с требований спецификации WS-ResourceLifetime. Сигнатура метода, моделирующего отдельный обмен сообщений стандарта WSRF, определяется структурой сообщений запросов и ответов. Запросы представляются в виде набора параметров спецификационного метода, ответы представляются как возвращаемые значения метода, а сообщения об ошибках моделируются исключениями. Всё множество требований можно разделить на две основные группы: синтаксические и функциональные. Синтаксические требования налагают ограничения на структуру сообщений и связи между полями одного сообщения. Функциональные требования представляют собой ограничения на функциональность обработки запросов и связь между содержимым запроса и ответом на запрос. Функциональные требования к реализациям WSRF представляют собой описания простых операций, таких как изменение значения поля ресурса, добавление или удаление свойств (операции с множеством), детерминированных и полностью определенных. Такие требования в рамках предлагаемого метода моделируются в явном виде с использованием блоков update, поддерживаемых в реализации UniTESK – инструменте JavaTESK. update-блок содержит инструкции, которые явным образом изменяют 50

значения полей модельного состояния в соответствии с текстом требования стандарта. WS-Base WSFaults Resource

WS-Resource WS-Resource Properties Lifetime

WS-Service Group

Синтаксис

27

1

50

12

5

Семантика

2

11

109

39

68

следующие обмены SetResourceProperties.

сообщениями

–

PutResourceProperties,

4. Разработка тестового сценария Следующим этапом разработки тестового набора являлась разработка тестовых сценариев. Тестовым сценариям в технологии UniTESK отводится немаловажная роль. Как уже указывалось ранее, для их построения используется конечно-автоматная модель целевого ПО. При таком выборе модели актуальны ответы на следующие вопросы: 1. Как вычислять состояния тестируемой системы?

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

3. Разработка медиатора Основная функция медиатора, как компонента тестового набора, – это установление соответствия между модельным объектом (объектом спецификационного класса) и целевой системой. В случае тестирования ИПО Грид возможность непосредственного доступа к полям и методам системы отсутствует, потому воздействовать на ГС можно было лишь посредством отправки соответствующих сообщений-запросов, а реакции принимать – обрабатывая отклики. Соответственно, главной функцией медиатора является генерация сообщений-запросов и разбор сообщений-откликов с целью выявления полезной информации о выполнении операции. В рассматриваемом методе медиаторы преобразуют параметры вызова спецификационного метода в XML сообщение, преобразуют в сообщение протокола SOAP/HTTP и отсылают его в целевую систему по установленному TCP соединению. Полученные ответы медиатор разбирает, проверяет соответствие ответа синтаксическим требованиям и формирует возвращаемое значение спецификационной функции. Одна из особенностей разработки медиаторов для ИПО Грид заключается в том, что существующие реализации (в частности, Globus Toolkit 4.2) не удовлетворяют синтаксическим требованиям стандарта. Для проведения тестирования потребовалась адаптация медиаторов под нарушения стандарта, допускаемых реализацией. К примеру, Globus Toolkit 4.2 реализует один из последних предварительных проектов стандарта (draft) и поддерживает устаревшее пространство имен XML элементов (namespace); в результате реализация отвергала запросы, сформированные в соответствии со стандартом. Также путем анализа исходного кода ИПО ГС Globus Toolkit 4.2, а также ряда экспериментов было выяснено, что реализацией не поддерживаются 51

2.

Как осуществляются переходы между состояниями?

3.

Как задается автомат теста и как производится обход графа переходов автомата?

Ответ на первый вопрос не может быть дан, исходя только из общих соображений. Для каждой целевой системы состояние должно быть смоделировано с учётом её особенностей и требований, предъявляемых к качеству тестового набора вообще. В случае ИПО Грид в качестве объекта тестирования выступает WS-ресурс. Основной его характеристикой выступает, очевидно, RPD, как наиболее полно описывающая ресурс сущность. Следовательно, RPD может быть предъявлен в качестве описателя состояния WS-ресурса. Однако, такой подход является избыточным, а тестовые сценарии на его основе, вообще говоря, могут выполняться неопределенно долгое время. Действительно, представим себе, что WS-ресурс обладает n свойствами, каждое из которых может принимать только значение “1”, и пусть изначально его RPD пуст. Рассмотрим конечный автомат, построенный на основе такого ресурса, причем в качестве модели состояния будем использовать его RPD, а в качестве переходов – два метода: add и remove, обозначающие, соответственно добавление нового свойства и удаление некоторого старого. Тогда из начального состояния автомат сможет перейти в n состояний, соответственно, образуется 2n дуг на графе состояний. Из состояний “ранга 1” (т.е. таких, при которых RPD WS-ресурса содержит 2

только одно свойство), которых ровно Cn , в состояния “ранга 2” уже будет 2 * n * C n2 = n * (n − 1)

“ранга 2 * C n2

3”, * C n3

переходов. Из состояний “ранга 2” в состояния

которых 2

имеется

Cn3

переходов

уже

будет

5

2

= (n − 1) * (n − 2) * (n − 3) ∼ n при больших n. Это означает, что n

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

точки зрения тестирования методов add и remove совершенно необязательно обходить все ребра такого графа (т.к. все свойства такого WS-ресурса с “точки зрения” данных методов эквивалентны). Достаточно обработать лишь некоторые (например, ребра, идущие из состояния, в котором все n свойств WS-ресурса равны 1 и ребра, идущие из начального состояния). Потому в ряде случаев представляется разумным выбирать другую модель состояния тестируемой системы. При разработке тестового сценария для тестирования соответствия ИПО Грид стандарту WSRF в качестве идентификатора состояния автомата теста мы предлагаем использовать мощность RPD WS-ресурса, т.е. количество свойств WS-ресурса. С одной стороны, такой способ существенно уменьшает размер предполагаемого графа состояний а, следовательно, и время работы тестов. С другой стороны, при таком задании состояния сохраняется детерминированность графа, что принципиально для корректной работы обходчика UniTESK. Ответ на второй вопрос традиционен для большинства приложений UniTESK – переходы между состояниями автомата осуществляются посредством подачи стимулов в целевую систему. В качестве стимулов в случае построения тестового набора для ИПО Грид выступают, естественно, вызовы медиаторных методов. Последние же представляют собой не что иное, как отправки соответствующих XML-сообщений целевому ресурсу. Теперь перейдем к обсуждению третьего вопроса – заданию автомата теста. Так как используется синхронная модель целевой системы, то для каждого спецификационного метода можно задать отдельный сценарный метод, который будет перебирать параметры метода и вызывать (неявно) медиатор для оказания тестового воздействия и оракул для проверки правильности возвращаемого значения.

5. Опыт практического тестирования реализации ИПО Грид Представленный выше метод к разработки тестовых наборов для ИПО Грид использовался при создании тестового набора для проверки соответствия реализаций ИПО Грид стандарту WSRF.

5.1. Обзор целевой системы Объектом тестирования в данной работе является программный пакет Globus Toolkit 4.2. Ниже перечислены основные компоненты данного инструментария: 1) Компоненты поддержки времени выполнения (Common runtime components): 1. C Core Utilities – обеспечение переносимости; 2. C WS Core – поддержка разработки Web-сервисов и выполнения клиентских приложений на C; 53

3. 4. 5. 6. 7.

Java WS Core – поддержка разработки Web-сервисов и выполнения клиентских приложений на Java; CoG jglobus – поддержка безопасности и выполнения не Webсервисной части Java; Core WS Schema – поддержка схемы стандартов WSRF и WSN; Python Core – разработка и исполнение WS и не-WS клиентских приложений на языке Python; XIO – расширяемые библиотеки ввода-вывода на С.

2) Управление данными (Data Management): 1. GridFTP – протокол передачи файлов; 2. OGSA-DAI – инфраструктура, основанная только на java-сервисах, для получения доступа к ресурсам и интеграции их в Грид; 3. Reliable File Transfer – технология надежной передачи файлов, основанная на Web-сервисах; 4. Replica Location – технология копирования и обнаружения данных; 5. Data Replication – технология идентификации групп файлов в среде Грид, и их локального копирования. 3) Управление выполнением (Execution Management): 1. GRAM – обнаружение местоположения, инициализация выполнения, наблюдение за работой и завершение удаленных задач на Гридресурсах; 2. GridWay – коллективное использование вычислительных ресурсов; 3. MPICH-G2 – реализация стандарта MPI [16]. 4) Информационные сервисы (Information Services): 1. MDS4 – технология для слежения за ресурсами и их поиска, включающая сервисы индексирования и триггеры. 5) Компоненты безопасности (Security): 1. C Security – технология поддержки безопасности; 2. CAS\SAML Utilities – технология, относящиеся к авторизации сообществом; 3. Delegation Service – технология, предоставляющая хосту учетные данные; 4. GSI-OpenSSH – модифицированная версия OpenSSH[18], которая поддерживает аутентификацию сертификатов и их предоставление, удаленный зарегистрированный доступ и сервис передачи файлов; 5. MyProxy – технология хранения и извлечения учетных данных из репозитория. Остановимся на некоторых принципиальных особенностях архитектуры Globus Toolkit 4.2. Сервисно-ориентированная архитектура. Globus Toolkit 4.2 создан для поддержки приложений, в которых множества сервисов взаимодействуют посредством стандартных протоколов. ПО включает и сами сервисы полностью, и библиотеки, реализующие стандартные протоколы. 54

Сервисы инфраструктуры. Globus Toolkit 4.2 включает встроенные сервисы для организации, наблюдения, управления и контроля доступа к таким элементам инфраструктуры, как ресурсы данных и вычислительные ресурсы. Web-сервисы. Globus Toolkit 4.2 использует протоколы стандартных Webсервисов и механизмы описания сервисов, обнаружения, контроля доступа, аутентификации и авторизации. Контейнеры. ПО Globus Toolkit 4.2 включает компоненты, которые могут быть использованы для конструирования контейнеров для “помещения” в них Web-сервисов, написанных на Java, C, или Python. Безопасность. Подсистема безопасности выполняет задачи защиты сообщений, аутентификации, авторизации и передачи полномочий. Компоненты. Компоненты Globus Toolkit 4.2 не отвечают, вообще говоря, нуждам конечного пользователя напрямую: большинство из них выступает скорее как TCP\IP библиотека или реализация Web-сервера, чем как Webбраузер. Вместо этого, Globus Toolkit 4.2 предоставляет широкий диапазон компонент и инструментов, которые обеспечивают высокоуровневые возможности, необходимые определенным сообществам пользователей. Согласно утверждению Globus Alliance, компонент Globus Toolkit 4.2 Java WS Core реализует требования стандарта WSRF. В работе задача тестирования соответствия решалась именно для этого компонента. В рамках Java WS Core Web-сервис – это просто Java-объект, а поддерживаемые им обмены сообщениями соответствуют методам класса. Для вызова методов класса следует посылать сервисам XML-сообщения по протоколу SOAP/HTTP. Стоит также заметить, что в реализации возможны передача сообщений как с применением шифрования, так и без него.

бессмысленно, т.к. новое свойство может быть добавлено даже в RPD мощности 0), а затем с помощью одноименного медиаторного метода отправляется искомое XML-сообщение. В данном сценарии случайным образом генерируется имя свойства и его значение (с помощью функций класса java.util.Random). В некотором смысле аналогичен ему сценарий для метода UpdateResourceProperties – также устанавливается верхний предел мощности RPD WS-ресурса, но вместе с ним устанавливается и нижний предел (т.к. невозможно изменить значение свойства у WS-ресурса, который не обладает ни одним свойством). Далее с помощью одноименного медиаторного метода отправляется XML-сообщение. Новое значение свойства также генерируется случайно. Наконец, сценарий для обмена сообщениями DeleteResourceProperties таков: устанавливается нижний предел мощности RPD WS-ресурса, а затем вызывается одноименный медиаторный метод. Как и в сценарии для обмена GetResourceProperty, имя удаляемого свойства WS-ресурса не произвольно, а является именем элемента массива, в который конвертируется RPD с помощью метода toArray() библиотеки java.util.Set. Соответствующий граф состояний тестируемой системы имеет следующий вид (Рис.1):

5.2. Тестирование реализации Разработанный с помощью инструмента JavaTESK тестовый сценарий включает сценарии для семи методов (они же сценарные методы): GetResourcePropertyDocument, GetResourceProperty, GetMultipleResourceProperties Insert-, Update- и DeleteResourceProperties, а также ImmediateDestroy. Сценарий для GetResourceProperty предельно прост: в нём устанавливаются нижний и верхний пределы мощности RPD WS-ресурса, и пока мощность находится в заданном диапазоне, выбирается один из элементов RPD, т.е. некоторое свойство WS-ресурса. Имя свойства выбирается не произвольно, а как поле элемента массива, в который конвертируется RPD. Осуществляется это посредством применения метода toArray() библиотеки java.util.Set. Запрос искомого свойства осуществляется с помощью вызова одноименного медиаторного метода. Аналогичны сценарии для методов GetResourcePropertyDocument и GetMultipleResourceProperties. Сценарий для InsertResourceProperties тоже несложен: в нём устанавливается только верхний предел мощности RPD WS-ресурса (нижний устанавливать 55

Рис.1. Граф состояний тестируемой системы Дуги, соответствующие переходам, приводящим к увеличению номера состояния, соответствуют вызовам сценарного метода InsertResourceProperties, обратные – DeleteResourceProperties, а циклические – вызовам методов GetResourcePropertyDocument, GetResourceProperty, GetMultipleResourceProperties. Стоит пояснить, почему именно 7 вышеуказанных обменов сообщениями были выбраны в качестве основных для написания соответствующего генератора XML-сообщений. В процессе разработки тестового набора 56

предполагалось, что с его помощью будут протестированы сервисы контейнера компонента Java WS Core инструментария Globus Toolkit 4.0. По умолчанию, всего в контейнере содержится 34 Web-сервисов, из которых 23 поддерживают некоторые обмены сообщениями из разделов WSResourceProperties и WS-ResourceLifetime стандарта WSRF. В частности, все они поддерживают обмен типа GetResourceProperty, 9 – ImmediateDestroy а также Insert-, Update- и DeleteResourceProperties, 14 – QueryResourceProperties, 13 – GetMultipleResourceProperties, и 7 – SetTerminationTime (обмен сообщениями из раздела WS-ResourceLifetime стандарта WSRF, соответствующий установке времени окончания работы WS-ресурса). Соответственно, данные 7 обменов сообщениями являлись как достаточно простыми в смысле написания спецификационных методов (чего нельзя сказать, к примеру, об обмене QueryResourceProperties), так и позволяли в полной мере провести тестирование соответствия стандарту WSRF 1.2. Отдельный сценарий был реализован для метода ImmediateDestroy. В этом сценарии просто вызывается соответствующий медиаторный метод. Соответствующий граф состояний таков(Рис.2):

Рис 2. Граф состояний для сценария ImmediateDestroy Переход здесь всего 1, результатом выполнения сценарного метода является уничтожение WS-ресурса (состояние “Destroyed”).

5.3. Результаты тестирования В данной работе была протестирована реализация ИПО ГС Globus Toolkit 4.0 средствами технологии UniTESK (JavaTESK). В качестве результатов тестирования выступали сгенерированные инструментом отчеты о покрытии требований. Всего было покрыто 60% функциональности, в чём данный тестовый набор не уступает тестам, применяемым разработчиками Globus Toolkit'а; последние для оценки качества тестирования измеряют покрытие тестами кода с помощью инструментов JUnit и Clover, и данные инструменты позволили разработчикам установить, что их юнит-тесты покрывают 60% функциональности компонента Java WS Core. Однако, как уже говорилось ранее, эти тесты ничего не могут сообщить о соответствии реализации Globus Toolkit 4.0 какому-либо стандарту. Таким образом, существующие и разработанные тесты не только дополняют друг друга, но и позволяют с разных точек зрения рассматривать реализацию. 57

В разработанный тестовый набор не вошли спецификации и тесты для необязательных требований спецификации WS-ServiceGroup и требования к операции QueryResourceProperties. При тестировании реализации были выявлены несоответствия семантическим требованиям стандарта WSRF 1.2 в обменах сообщениями InsertResourceProperties и UpdateResourceProperties. В частности, эти методы позволяют добавлять или изменять значения свойств WS-ресурса с разными идентификаторами (QName), что запрещается требованиями стандарта.

6. Существующие методы и подходы тестирования ИПО Грид В 2006-м году Европейский институт стандартизации телекоммуникаций (ETSI) организовал экспертную группу по разработке тестового набора для тестирования совместимости ИПО Грид [23,24]. Метод, разрабатываемый в ETSI, основывается на разработке большого числа тестов (test cases) на языке TTCN-3. Каждый тест предназначен для проверки отдельной цели тестирования – тестовой ситуации, сформулированной полуформально на языке TPL (Test Purpose Language). В настоящее время ведется выделение целей тестирования. Прототип тестового набора для ИПО Грид на языке TTCN3 представлен в работе [25]. Тестовый набор не связан с каким-либо стандартом для ИПО Грид. Вместо проверки требований стандарта тестовый набор проверяет применимость Грид в типовых сценариях использования – постановки вычислительной задачи в очередь, выполнение задачи на одном из вычислительных узлов, доставка результатов вычисления клиенту. В рамках проекта построения распределенной системы EGEE обработки экспериментальных данных с Большого адронного коллайдера проводилось тестирование пакета gLite, разработанного в CERN. В качестве основного метода тестирования используется интеграционное тестирование – выполнение задач по пересылке крупных массивов данных[26]. В случае тестирования gLite этот метод тестирования оправдан, так как основное назначение EGEE – быстрая передача больших объемов данных с датчиков коллайдера в вычислительные системы. Задачу обеспечения совместимости с другими ИПО Грид разработчики EGEE не ставят. Подход к тестированию ИПО Грид, близкий к представленному в данной статье, развивается в работе [27]. Авторы предлагают использовать формализм автоматов с абстрактным состоянием (Abstract State Machine, ASM) и автоматически генерировать тестовые последовательности из обхода автомата модели. Вопросы анализа стандартов ИПО Грид, выделения требований и построения формальной модели требований не рассматриваются. 58

7. Заключение В данной работе решалась задача тестирования соответствия реализации ИПО ГС Globus Toolkit 4.2 стандарту систем управления распределенными ресурсами WSRF 1.2. Данный стандарт был проанализирован и на его основе составлен его каталог требований. Также была исследована структура и интерфейсы компонента Java WS Core программного пакета Globus Toolkit 4.2. На основе полученных данных был разработан тестовый набор для указанного программного пакета с применением технологии тестирования UniTESK (JavaTESK) и проведено тестирование. Тестирование показало, что реализация Globus Toolkit 4.2 соответствует стандарту WSRF, хотя выявило отсутствие выполнения ряда необязательных требований, как семантических, так и синтаксических. Также тестирование показало, что технология UniTESK применима для тестирования ИПО ГС, в частности, имеют место следующие особенности её применения: 1. Обмены сообщениями с Web-сервисами естественным образом моделируются спецификационными функциями; 2.

Для разработки тестового набора нужна библиотека классов для автоматизации построения различных (в том числе некорректных) сообщений Web-сервисов.

В рамках данной работы были получены следующие результаты: 1. показана применимость технологии UniTESK для разработки тестовых наборов для инфраструктурного программного обеспечения (ИПО, middleware) Грид-систем; 2.

разработан метод формализации требований и разработки тестов для стандартов ИПО Грид, основанных на архитектуре Webсервисов;

3.

разработан прототип тестового набора для проверки соответствия реализаций ИПО Грид базовому стандарту WSRF версии 1.2: a.

проведен анализ базового стандарта WSRF, составлен каталог требований;

b.

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

c.

проведено исследование реализации, на основе которого разработан медиатор;

d.

разработан тестовый набор для реализации ИПО ГС Globus Toolkit 4.0 средствами технологии UniTESK (JavaTESK);

59

e.

проведено тестирование реализации ИПО ГС Globus Toolkit 4.0;

f.

при тестировании реализации был обнаружен ряд несоответствий базовому стандарту WSRF.

В качестве направлений для дальнейшей работы мы рассматриваем разработку тестового набора, проверяющего специфические требования к сервисам ИПО Грид, такие как сервис передачи больших массивов данных, сервис создания и управления вычислительными задачами и др. Литература [1] Ian Foster The Grid: Blueprint for a New Computing Infrastructure. — Morgan Kaufmann Publishers. — ISBN 1-55860-475-8 [2] Ян Фостер. Что такое грид? http://gridclub.ru/library/publication.2004-1129.5830756248/publ_file/ [3] Веб-сайт консорциума Globus Alliance. http://globus.org/ [4] Пакет ИПО Грид UNICORE http://www.unicore.eu/ [5] Пакет ИПО Грид gLite. http://glite.web.cern.ch/glite/ [6] Open Grid Services Architechture http://www.ogf.org/documents/GFD.80.pdf [7] Web Service Resource Framework http://www.oasis-open.org/committees/tc_home.php?wg_abbrev=wsrf [8] WS-Management standard. http://msdn2.microsoft.com/en-us/library/aa384470.aspx [9] В.В. Галактионов, Н.А. Кутовский Тестирование GT4 в ОИЯИ. http://lit.jinr.ru/Reports/annual-report05/gt4-48.pdf [10] RFC 2119 Key words for use in RFCs to Indicate Requirement Levels. http://www.ietf.org/rfc/rfc2119.txt [11] Web Services Description Language ver. 2.0 http://www.w3.org/TR/wsdl20/ [12] Web Services Activity конрциума W3. http://www.w3.org/2002/ws/ [13] Single Object Access Protocol. http://www.w3.org/TR/soap/ [14] XML Information Set. http://www.w3.org/TR/xml-infoset/ [15] Web Services Addressing. http://www.w3.org/Submission/ws-addressing/ [16] XML Path Language (XPath). http://www.w3.org/TR/xpath [17] A Message-Passing Interface Standard (MPI). http://www.mpi-forum.org/docs/mpi-11-html/mpi-report.html [18] OpenSSH project. http://www.openssh.org/ [19] А.В. Баранцев, И.Б. Бурдонов, А.В. Демаков, С.В. Зеленов, А.С. Косачев, В.В. Кулямин, В.А. Омельченко, Н.В. Пакулин, А.К. Петренко, А.В. Хорошилов. Подход UniTESK к разработке тестов: достижения и перспективы. Труды Института системного программирования РАН, №5, 2004. URL: http://www.citforum.ru/SE/testing/UniTesK [20] Bertrand Meyer. Applying 'Design by Contract'. IEEE Computer, vol. 25, No. 10, October 1992, pp. 40-51. [21] Software Testing Framework JUnit. http://www.junit.org/ [22] Code Coverage Analysis “Clover”. http://www.atlassian.com/software/clover/ [23] S. Schulze. Achieving Grid Interoperability: The ETSI Approach. The 20th Open Grid Forum - OGF20/EGEE 2nd User Forum. Manchester, UK. May 7 - 11, 2007

60

[24] GRID Activity. European Telecommunication Standardization Institute. http://www.etsi.org/WebSite/Technologies/GRID.aspx [25] T.Rings, H.Neukirchen, J.Grabowski. Testing Grid ApplicationWorkflows Using TTCN-3. First International Conference on Software Testing, Verification, and Validation, ICST 2008, Lillehammer, Norway, April 9-11, 2008. [26] E.Slabospitskaya, V.Petukhov, and G.Grosdidier. Glite I/O Storm Testing in EDG-LCG Framework. Nuclear Electronics and Computing 2005. Varna, Bulgaria, 12-18 September 2005. [27] Lamch, D.; Wyrzykowski, R. Specification, Analysis and Testing of Grid Environments Using Abstract State Machines. International Symposium on Parallel Computing in Electrical Engineering, 2006. PAR ELEC 2006. 13-17 Sept. 2006 Pages:116 - 120

61

Инфраструктура тестирования вебсервисов на базе технологии TTCN-3 и платформы .NET П.Н. Яковенко, А.В. Сапожников [email protected] [email protected] Аннотация. Работа посвящена вопросам тестирования веб-сервисов с использованием технологии TTCN-3. Рассматривается отображение языка WSDL в TTCN-3, основанное на синхронном (процедурном) взаимодействии тестового сценария с веб-сервисом. Предлагается подход реализации универсального тестового адаптера средствами рефлексии, предоставляемыми платформой .NET, и средой поддержки времени выполнения языка TTCN-3. Результатом работы явилась разработка прототипа системы автоматизации тестирования веб-сервисов.

1. Введение Веб-сервисы – технология построения распределенных систем, базирующаяся на языке XML и открытых коммуникационных протоколах. Идеи, лежащие в основе веб-сервисов, восходят к технологии удаленного вызова процедур (RPC), разработанной компанией SUN Microsystems в рамках проекта сетевой файловой системы. В дальнейшем эти идеи получили развитие в технологиях CORBA, DCOM и др. Принципиальное отличие веб-сервисов от альтернативных подходов организации взаимодействия сетевых приложений состоит в том, что технология веб-сервисов ориентирована на слабосвязанную интеграцию разнородных программных систем. В основу понятия «веб-сервис» заложены несколько базовых принципов [1], которые в совокупности отличают веб-сервис от других категорий серверного программного обеспечения. Среди них следует отметить слабую связанность веб-сервиса с клиентскими приложениями, самодокументируемость вебсервиса посредством его WSDL [2] спецификации, сетевое взаимодействие с использованием общепринятых, открытых протоколов. Слабая связанность систем предполагает минимизацию зависимостей между логикой работы взаимодействующих сторон. Чем меньше клиентская сторона выдвигает предположений о стабильности программного интерфейса, предоставляемого сервером, о его доступности во время работы клиента, о неизменности структуры и содержимого сообщений, передаваемых между 63

клиентом и сервером, тем в большей степени система является слабосвязанной. Технология веб-сервисов предоставляет ряд существенных возможностей для организации слабосвязанной архитектуры, впрочем степень связанности каждой конкретной реализации во многом определяется допущениями, принятыми на вооружение разработчиками сервиса. Веб-сервис представляет собой программную систему, расположенную на сетевом компьютере и идентифицируемую строкой URI [3] (единообразный идентификатор ресурса) уникальным образом. Полная спецификация интерфейсов веб-сервиса и способов доступа к нему описывается на языке WSDL. Этот «паспорт» веб-сервиса представляет собой XML документ, в котором можно выделить две части. Первая, абстрактная (платформонезависимая), описывает в структурированном виде сигнатуры операций, предоставляемых веб-сервисом, и типы данных формальных параметров и исключений. Вторая часть WSDL документа, содержит платформо-зависимые привязки (binding) типов данных и операций к конкретным форматам кодирования и коммуникационным протоколам, и другую специфическую информацию (например, номер порта), необходимую программе для получения доступа к веб-сервису и взаимодействия с ним. Веб-сервисы, как и любые другие программные системы, необходимо тестировать. Растущее распространение веб-сервисов и их использование в промышленных приложениях, обуславливает необходимость создания эффективных методик тестирования. В этой работе предлагается подход к автоматизации тестирования веб-сервисов, построенный на базе технологии TTCN-3 [9,10]. Мы считаем обоснованным применение TTCN-3 для тестирования веб-сервисов в силу того, что оба языка WSDL и TTCN-3 следуют единому подходу разделения спецификации (веб-сервиса и тестового сценария) на зависящие и независящие от платформы уровни. Это позволяет разрабатывать платформо-независимые TTCN-3 тесты по абстрактной части WSDL спецификации веб-сервиса и учитывать платформо-зависимые аспекты доступа к сервису (привязки) на уровне адаптации тестов [12,13]. Преимущества тестирования веб-сервисов с использованием технологии TTCN-3 обсуждаются также в работе [4]. В [5] авторы исследуют вопросы тестирования веб-сервисов, иcпользующих протокол SOAP [8], и предлагают правила импорта XML конструкций для языка TTCN-3, которые могут быть использованы для автоматической генерации TTCN-3 деклараций по XML схеме. Работы [6,7] независимо предлагают два варианта правил преобразования WSDL конструкций в TTCN-3 и механизм взаимодействия тестового сценария с веб-сервисом на базе обмена сообщениями. Однако архитектурные подходы, принятые в этих работах, усложняют разработку и сопровождение тестовых сценариев: в [6] сгенерированные TTCN-3 декларации размещаются в одном модуле, а в [7] авторы выносят часть служебной информации, относящейся к сетевому взаимодействию, на уровень TTCN-3 кода. 64

В данной работе мы рассматриваем возможность построения системы автоматизации тестирования веб-сервисов на базе технологии TTCN-3, в которой все платформо-зависимые аспекты взаимодействия тестовой системы с веб-сервисом выносятся на уровень адаптации тестов, а обработка привязок веб-сервиса делегируется сторонним средствам. Статья организована следующим образом. В разделе 2 мы предлагаем отображение языка WSDL в язык TTCN-3, предусматривающее синхронное (процедурное) обращение к операциям веб-сервиса. В разделе 3 описывается схема работы тестового адаптера, использующего для взаимодействия с веб-сервисом медиаторы, генерируемые средствами платформы .NET. В разделе 4 изложена архитектура предлагаемой инфраструктуры тестирования. В разделе 5 подводятся итоги работы.

2. Отображение языка WSDL в TTCN-3 Тестирование веб-сервиса при помощи технологии TTCN-3 предполагает наличие трех составляющих: статической, динамической и времени выполнения. Статическая часть состоит из набора TTCN-3 модулей, отражающих интерфейс веб-сервиса, и содержит декларации типов данных, сигнатуры операций, определения портов и пр. Совокупность тестовых сценариев образует динамическую составляющую. И, наконец, составляющая времени выполнения представляет собой реализацию интерфейсов TRI [14] и TCI [15], обеспечивающую коммуникационное взаимодействие тестовых сценариев с веб-сервисом. Наличие формального отображения конструкций языка WSDL в конструкции TTCN-3 дает возможность автоматизировать построение первой (статической) и третьей (времени выполнения) составляющих по WSDL документу. К сожалению, WSDL не предоставляет достаточно информации для генерации тестовых сценариев. Сценарии должны либо создаваться тестировщиком вручную на языке TTCN-3, либо генерироваться на базе какой-либо графической нотации (например, диаграмм последовательностей языка UML) или формальной спецификации поведения веб-сервиса. Одной из сложностей, с которой мы столкнулись при разработке отображения, является отсутствие возможности в языке TTCN-3 определять пользовательские области видимости. Как показал анализ WSDL спецификаций нескольких промышленных веб-сервисов, прямое отображение WSDL документа в один TTCN-3 модуль неминуемо приведет к конфликтам имен. Для разрешения таких конфликтов, необходимо либо модифицировать имена объектов в процессе трансляции, либо распределять одноименные TTCN-3 декларации по разным единицам трансляции (модулям). Предлагаемое в этой работе отображение комбинирует оба варианта, отдавая приоритет модульной структуре, в частности отдельный модуль генерируется для каждой целевой области видимости языка XML, каждой привязки вебсервиса и каждого элемента service WSDL документа. 65

WSDL спецификация заимствует правила определения типов из языка XML Schema. Типы данных, определяемые для формальных параметров вебсервиса, возвращаемых значений и исключений описываются внутри элемента WSDL документа, который в свою очередь может определять и импортировать несколько XML схем. В целом типы, задаваемые XML схемой, преобразуются в TTCN-3 декларации согласно правилам, определенным в девятой части TTCN-3 стандарта [11]. Основное отличие применяемого нами отображения заключается в другом распределении XML схем по TTCN-3 модулям, при котором отдельный TTCN-3 модуль создается для каждого целевого пространства имен (targetNamespace). Это позволяет сохранить именование объектов между WSDL и TTCN-3 кодом и избежать добавления префиксов (пространств имен XML) к TTCN-3 идентификаторам. Элемент WSDL документа Тип данных Раздел сообщения

Тэг WSDL

Сообщение



Исключение



Операция Тип порта Привязка



Сервис



Порт



Декларация TTCN-3 Тип данных TTCN-3. Формальный параметр или возвращаемое значение сигнатуры. Раскрывается в набор формальных параметров сигнатуры. Исключение в определении сигнатуры. Сигнатура. Порт процедурного типа. Отдельный модуль. Содержит сигнатуры и типы портов. Компонентный тип. Размещается в отдельном модуле. Порт. Размещается внутри определения компонентного типа.

Таблица 1. Соответствие WSDL элементов и TTCN-3 деклараций. Каждое целевое пространство имен отображается в отдельный TTCN-3 модуль с именем идентичным префиксу целевого пространства. Это относится как к схемам, определенным непосредственно в WSDL документе, так и ко всем импортированным схемам. Для каждой привязки (элемент ) формируется отдельный TTCN-3 модуль, в который транслируются декларации сообщений (), их разделы (), операции (), исключения () и типы портов (). Наконец, каждый сервис (элемент ) вместе с определениями портов () также транслируется в отдельный модуль. Типы данных (элемент ) обрабатываются согласно стандартному отображению языка XML Schema в TTCN-3. Правила трансляции остальных элементов WSDL документа 66

приведены в таблице 1. Привязки веб-сервиса к конкретным протоколам передачи данных (например, SOAP и HTTP) игнорируются в процессе трансляции WSDL документа; их обработка рассмотрена в следующем разделе. В таблице 2 приведен пример трансляции WSDL спецификации веб-сервиса. Типы Request и Response размещаются в модуле tns в соответствии с префиксом целевого пространства имен. Привязка (элемент ) Jobs порождает отдельный модуль bindingJobs (значение атрибута name с добавлением префикса binding). В этом модуле находятся определения сигнатуры Get, которая соответствует одноименной операции веб-сервиса, и порт процедурного типа portJobs. Раздел p входного сообщения In отображается во входной параметр сигнатуры, а соответствующий раздел сообщения Out – в возвращаемое значение сигнатуры. Определение сервиса (элемент ) порождает отдельный модуль с именем serviceJobsWs. Порт (элемент ) p1 соответствует компонентному типу языка TTCN-3. В эту компоненту помещается TTCN-3 порт (точка доступа к компоненте) c фиксированным именем P. Тип этого порта определяется исходя из значения атрибута binding. module tns 1 и S > 1).

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

Величина E называется уровнем ассоциативности кэш-памяти. Пусть физический адрес имеет разрядность m. В большинстве случаев при обращении к кэш-памяти с параметрами 〈S = 2s, B = 2b, E〉 физический адрес интерпретируется следующим образом: биты [0, …, b-1] определяют позицию байта внутри блока данных, [b, …, b+s–1] — номер множества и, наконец, [b+s, …, m] — тэг. Для определения, имеет место попадание или промах, по физическому адресу вычисляется номер множества, после чего для каждой строки этого множества осуществляется сравнение тэга адреса, по которому осуществляется обращение, с тэгом, хранящимся в строке. Если для одной из строк сравнение истинно, значит, имеет место кэш-попадание, и в блоке данных этой строки на соответствующей позиции находятся требуемые данные.

2

3

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

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

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

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

Тестовая программа представляет собой последовательность тестовых вариантов. Каждый тестовый вариант содержит тестовое воздействие — специально подготовленную цепочку инструкций, предназначенную для создания определенной ситуации в работе микропроцессора. Тестовое воздействие предваряется инициализирующими инструкциями и может завершаться тестовым оракулом — инструкциями, проверяющими корректность состояния микропроцессора после выполнения тестового воздействия. Таким образом, структуру тестовой программы можно описать с помощью формулы test = {〈initi, actioni, posti〉}i=1,n, где initi — это инициализирующие инструкции, actioni — тестовое воздействие, posti — тестовый оракул. Ниже приведен фрагмент тестовой программы для микропроцессора с системой команд MIPS64 [3], который включает один тестовый вариант. ///// Инициализирующие инструкции ///// // Инициализация регистров инструкции 1: // загрузка виртуального адреса в базовый регистр a0 // a0[base]=0xffffffff81af1590 ori a0, zero, 0xffff dsll a0, a0, 16 ori a0, a0, 0xffff dsll a0, a0, 16 ori a0, a0, 0xa1af dsll a0, a0, 16 ori a0, a0, 0x1590

3.1. Используемый метод генерации тестовых программ В предлагаемом подходе построение тестовых программ осуществляется автоматически на основе формальной спецификации подсистемы управления памятью. Цель генерации задается с помощью критерия тестового покрытия, выделяющего набор тестовых ситуаций для инструкций, работающих с памятью. Тестовые программы строятся путем целенаправленного перебора всевозможных сочетаний тестовых ситуаций для цепочек инструкций ограниченной длины. Общее описание используемого метода генерации тестовых программ доступно в работе [2]. Идея метода основана на предположении, что поведение микропроцессора зависит от множества выполняемых инструкций (состояние конвейера), зависимостей между ними (через регистры или память) и событий, возникающих при выполнении инструкций (исключения, попадания/промахи в кэш и т.п.). Генератору на вход подаются формальные спецификации инструкций – в нашем случае инструкций, работающих с памятью (типа загрузки и сохранения). Кроме того генератору даются описания возможных тестовых ситуаций и зависимостей между инструкциями, а также параметры управления генерацией, например, длина генерируемых цепочек инструкций. 123

// Инициализация памяти для инструкции 1 ori a1, zero, 0xdead sw a1, 0(a0) // Инициализация регистров инструкции 2: // загрузка виртуального адреса в базовый регистр t1 // t1[base]=0xffffffff81c49598 ... // Инициализация памяти для инструкции 2 ... // Инициализация кэша L1 для инструкции 1: // помещение данных в кэш L1 lw t0, 0(a0)

124

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

// Инициализация кэша L1 для инструкции 2: // вытеснение данных из кэша L1 ... //////// Тестовое воздействие //////// // // lw sw

Зависимость между инструкциями 1 и 2: L1IndexEqual=false v0, 0(a0) // L1Hit=true a2, 0(t1) // L1Hit=false

////////// Тестовый оракул ////////// // Тестовый оракул для инструкции 1 ori t1, zero, 0xdead // Ошибочное завершение bne v0, t1, error_found nop // Тестовый оракул для инструкции 2 ... Тестовое воздействие состоит из двух инструкций: lw, осуществляющей загрузку слова, и sw, которая сохраняет слово по указанному адресу. Для наглядности тестовые ситуации для этих инструкций затрагивают только кэшпамять первого уровня (L1): первая инструкция вызывает попадание в кэш, вторая — промах. Несколько слов о вспомогательных инструкциях, используемых в примере. Инструкция ori осуществляет побитовое ИЛИ значения второго регистра с 16 битным значением, заданным в третьем операнде, результат записывается в первый регистр; инструкция dsll сдвигает значение второго регистра влево на заданное число разрядов и сохраняет результат в первом регистре; bne — это инструкция условного перехода (переход осуществляется в случае неравенства значений регистров).

3.2. Формальная памятью

спецификация

подсистемы

управления

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

• уровень ассоциативности; • число множеств; • функция вычисления тэга; • функция вычисления индекса; • структура блока данных; • управляющие биты; • стратегия замещения данных при промахе. В используемом генераторе тестовых программ для разработки формальных спецификаций используется язык программирования Java. Нами разработана библиотека абстрактных классов, позволяющая путем механизма наследования и перегрузки методов (соответствующих указанным выше параметрам) получать спецификации основных устройств MMU. Объекты полученных спецификационных классов можно использовать для определения семантики инструкций, вызывая необходимые интерфейсные методы (чтение, запись и т.п.). Моделирование подсистемы управления памятью позволяет генератору автоматически строить цепочки инициализирующих инструкций, приводящих микропроцессор в соответствующее тестовой ситуации состояние.

3.3. Типы тестовых ситуаций для подсистемы управления памятью Под тестовой ситуацией для инструкции понимается ограничение на значения входных операндов и состояние микропроцессора перед началом выполнения инструкции. Множество возможных тестовых ситуаций выявляется на основе анализа описания архитектуры микропроцессора. При тестировании MMU структура тестовых ситуаций определяется функциональностью подсистемы, связанной с обработкой запросов к памяти. Например, на первом этапе обработки определяется сегмент адресного пространства, к которому относится виртуальный адрес: если сегмент является отображаемым, трансляция адреса осуществляется с помощью TLB; в противном случае вычисление физического адреса производится в обход буфера трансляции адресов. Для данного этапа определены две тестовые ситуации: Mapped = true и Mapped = false. Далее, если виртуальный адрес является отображаемым, возможны две альтернативные ситуации: TLBHit = true, когда страница виртуальной памяти находится в TLB (попадание), и TLBHit = false, когда страницы в буфере нет (промах). 126

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

Mapped — отображаемый/неотображаемый сегмент виртуальной памяти;

•

Cached — кэшируемый/некэшируемый сегмент виртуальной памяти;

•

TLBHit — попадание/промах в TLB;

•

Valid — бит достоверности секции TLB;

•

L1Hit — попадание/промах в кэш-память L1;

•

L2Hit — попадание/промах в кэш-память L2.

Mapped

TLBHit

L1Hit

Valid

L2Hit

L1Hit

(TLB[i]G or (TLB[i]ASID = EntryHiASID)) При тщательном тестировании рассматриваются все комбинации значений истинности элементарных условий (exclusive condition coverage) или только те комбинации, когда значение истинности одного условия влияет на значение истинности всего выражения (MC/DC, Modified Condition/Decision Coverage) [4].

для

подсистемы

управления

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

L2Hit

EntryEqual — совпадение строк внутри множества; ƒ

o Рис. 1. Иерархия тестовых ситуаций

BlockEqual — совпадение данных внутри строки;

EntryReplace — обращение к данным, строка с которыми была вытеснена из буфера предшествующей инструкцией; ƒ

127

выражения,

((TLB[i]VPN2 and not (TLB[i]Mask)) = (vaSEGBITS-1..13 and not (TLB[i]Mask))) and

•

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

основе

(TLB[i]R = va63..62) and

3.4. Типы зависимостей памятью

На Рис. 1 элементарные ситуации структурированы в виде дерева (пунктирная дуга соответствует значению false, сплошная — значению true). Результирующая тестовая ситуация для инструкции соответствует пути от корня до листовой вершины.

Cached

микропроцессоре, можно детализировать на вычисляющего признак попадания в строку TLB [3]:

BlockEqual — совпадение данных внутри строки.

В целом для подсистемы управления памятью можно выделить следующие типы элементарных зависимостей: • 128

VAEqual — совпадение виртуальных адресов;

•

VPNEqual — совпадение номеров страниц виртуальной памяти;

•

PAEqual — совпадение физических адресов;

•

PFNEqual — совпадение номеров страниц физической памяти;

•

L1IndexEqual — совпадение множеств кэш-памяти L1;

•

L2IndexEqual — совпадение множеств кэш-памяти L2;

•

L1Replace — совпадение тэга кэш-памяти L1 с тэгом данных, которые были вытеснены из кэш-памяти предшествующей инструкцией;

•

L2Replace — совпадение тэга кэш-памяти L2 с тэгом данных, которые были вытеснены из кэш-памяти предшествующей инструкцией.

Как отмечалось в силу иерархической организации памяти зависимости по адресам имеют многоуровневую структуру. Фрагмент дерева возможных зависимостей представлен на Рис. 2 (пунктирная дуга соответствует значению false, сплошная — значению true). Результирующая зависимость между инструкциями соответствует пути от корня до листовой вершины. VAEqual

VPNEqual

PAEqual

4. Сравнение с существующими подходами VPNEqual

PFNEqual

PFNEqual

PAEqual

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

PFNEqual

PAEqual

PAEqual

Рис. 2. Фрагмент иерархии зависимостей по адресам

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

Нам известен только один подход к автоматизированному построению тестовых программ для MMU, использующий формальные спецификации подсистемы, — DeepTrans, разработка исследовательской лаборатории IBM в г. Хайфе (IBM Haifa Research Lab) [5]. Эта методика нацелена на тестирование части подсистемы, отвечающей за преобразование виртуальных адресов. В DeepTrans используется язык спецификации, специально созданный для моделирования механизмов трансляции адресов. В спецификации процесс преобразования адреса представляется в виде ориентированного ациклического графа. Вершины графа соответствуют отдельным стадиям трансляции адреса, ребра — переходам между стадиями. Из каждой вершины может выходить несколько дуг, каждая из которых помечена своим условием перехода. Подход DeepTrans предполагает ручную разработку шаблонов тестовых программ, но в шаблонах можно указывать тестовые ситуации, связанные с трансляцией адресов, извлеченные из спецификации. На основе шаблонов генератор Genesys-Pro путем разрешения ограничений строит набор тестовых программ [6, 7, 8]. Сравнение DeepTrans (в паре с генератором Genesys-Pro) с используемым нами подходом (MicroTESK) приводится в таблице 1.

130

Сравниваемая характеристика

DeepTrans (Genesys-Pro)

MicroTESK

Поддержка пользовательских шаблонов тестовых программ

MicroTESK позволяет Genesys-Pro описывать лишь предоставляет развитый сравнительно простые язык описания шаблонов шаблоны тестовых тестовых программ программ

Поддержка автоматической генерации тестовых шаблонов

Автоматическая генерация тестовых шаблонов не поддерживается

Поддерживается автоматическая генерация несложных тестовых шаблонов

Поддержка описания тестовых ситуаций

Присутствует

Присутствует

Поддержка описания зависимостей по адресам

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

Поддерживается описание сложных зависимостей по адресам

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

DeepTrans предоставляет специальный декларативный язык описания механизмов трансляции

В MicroTESK реализована библиотека классов на языке Java, моделирующая устройства MMU

Поддержка генерации самопроверяющих тестов

Присутствует

Присутствует

Таблица 1. Сравнение DeepTrans с MicroTESK Как видно из сравнения, в DeepTrans упор сделан на ручную разработку шаблонов тестовых программ, но при этом разработчику тестов предоставляются развитые средства описания шаблонов. В нашем подходе тестовые шаблоны генерируются автоматически, систематическим образом. Кроме того, в используемом нами подходе поддерживается описание сложных зависимостей по адресам.

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

инструкций: lb (загрузка байта), ld (загрузка двойного слова), sb (сохранение байта) и sd (сохранение двойного слова). Структура используемых тестовых ситуаций и зависимостей была близка к описанной в статье, но были дополнительно учтены управляющие биты в TLB и наличие микро-TLB — промежуточного буфера, содержащего записи, по которым были последние обращения. В результате тестирования было найдено несколько критических ошибок в подсистеме управления кэш-памятью, которые не были обнаружены с помощью тестовых программ, сгенерированных случайно.

6. Заключение Тестирование подсистемы управления памятью микропроцессора является нетривиальной задачей, которую практически невозможно решить без применения методов автоматизации. В статье был рассмотрен подход к автоматической генерации тестовых программ для MMU. В отличие от распространенных на практике методов, предлагаемый подход имеет высокий уровень автоматизации и является систематичным. Сгенерированные тестовые программы могут содержать встроенные проверки (тестовые оракулы), что делает их пригодными для тестирования не только моделей микропроцессоров, написанных на языках описания аппаратуры, но и готовых микросхем. Литература [1] http://en.wikipedia.org/wiki/Memory_management_unit. [2] А.С. Камкин. Генерация тестовых программ для микропроцессоров. Труды Института системного программирования РАН, 2008. [3] MIPS64™ Architecture For Programmers. Revision 2.0. MIPS Technologies Inc., June 9, 2003. [4] K.J. Hayhurst, D.S. Veerhusen, J.J. Chilenski, and L.K. Rierson. A Practical Tutorial on Modified Condition/Decision Coverage. Report NASA/TM-2001-210876, NASA, USA, May 2001. [5] A. Adir, R. Emek, Y. Katz, A. Koyfman. DeepTrans – A Model-Based Approach to Functional Verification of Address Translation Mechanisms. Microprocessor Test and Verification: Common Challenges and Solutions, 2003. [6] http://www.haifa.ibm.com/projects/verification/GenesysPresent/index.htm. [7] A. Adir, E. Almog, L. Fournier, E. Marcus, M. Rimon, M. Vinov, A. Ziv. Genesys-Pro: Innovations in Test Program Generation for Functional Processor Verification. Design and Test of Computers, 2004. [8] M. Behm, J. Ludden, Y. Lichtenstein, M. Rimon, M. Vinov. Industrial Experience with Test Generation Languages for Processor Verification. Design Automation Conference, 2004.

132

Сравнительный анализ современных технологий разработки тестов для моделей аппаратного обеспечения Я.С. Губенко, А.С. Камкин, М.М. Чупилко {jacob, kamkin, chupilko}@ispras.ru Аннотация. Работа представляет собой сравнительный анализ современных подходов к разработке функциональных тестов для моделей аппаратуры: AVM (Advanced Verification Methodology) от компании Mentor Graphics, OVM (Open Verification Methodology) — совместной разработки Mentor Graphics и Cadence Design Systems — и технологии UniTESK (Unified TEsting and Specification tool Kit), разработанной в Институте системного программирования РАН. В статье анализируются сильные и слабые стороны различных подходов, сопоставляются архитектуры тестовых систем, даются рекомендации по развитию технологии UniTESK и ее унификации с методологией OVM, набирающей все большее распространение и претендующей на то, чтобы стать стандартом в области тестирования моделей аппаратного обеспечения.

1. Введение Увеличение сложности аппаратного обеспечения неизбежно влечет за собой развитие технологий разработки тестов. В настоящее время сложность аппаратуры достигла такого уровня, что ее тестирование немыслимо без применения методов автоматизации. Такие методы позволяют разрабатывать тестовые системы, которые автоматически генерируют тестовые последовательности, оценивают правильность поведения системы и собирают информацию о достигнутом уровне тестового покрытия. Однако следует понимать, что автоматизация это далеко не все, что требуется от современной технологии разработки тестов. В условиях постоянного изменения требований и непрерывной доработки проектов огромное значение приобретают такие характеристики технологии, как возможность повторного использования тестов и возможность создания тестов, устойчивых к изменениям реализации. Существующие подходы к построению тестовых систем, такие как AVM (Advanced Verification Methodology), URM (Universal Reuse Methodology), OVM (Open Verification Methodology) и UniTESK (Unified TEsting and Specification tool Kit), в той или иной степени решают обозначенные задачи, но многообразие 133

существующих подходов усложняет взаимодействие между разными группами разработчиков. Стандартизация технологий разработки тестов является необходимым шагом в развитии полупроводниковой индустрии. Появление стандартов создаст предпосылки для отчуждения тестов, что окажет стимулирующее воздействие на рынок готовых компонентов (IPs, Intellectual Property Cores). Если тесты к компоненту аппаратного обеспечения разработаны с использованием общепринятого подхода, сторонние инженеры могут без труда разобраться в них и при необходимости дополнить. В последнее время в области тестирования моделей аппаратуры все большее распространение получает технология OVM, совместно разработанная компаниями Mentor Graphics и Cadence Design Systems. Предшественниками OVM являются два основных подхода: AVM (от Mentor Graphics) и URM (от Cadence Design Systems). В данной работе технология OVM вместе со своими предшественниками сравнивается с технологией UniTESK, разработанной в Институте системного программирования РАН. В статье анализируются сильные и слабые стороны указанных подходов, сопоставляются архитектуры тестовых систем, даются рекомендации по развитию инструментов UniTESK и их унификации с подходом OVM. Статья состоит из семи разделов, включая введение и заключение. Во втором разделе вводятся основные понятия, используемые в различных технологиях. Третий, четвертый и пятый разделы посвящены обзору технологий AVM, OVM и UniTESK соответственно. В этих разделах описываются основные принципы указанных подходов и архитектуры тестовых систем. Шестой раздел содержит сравнительный анализ рассматриваемых технологий. В седьмом разделе делается заключение, в котором даются рекомендации по развитию технологии UniTESK.

2. Основные понятия Под моделями аппаратного обеспечения в данной статье понимаются программные модели цифровых устройств, описанные на специальных языках. Такие языки можно разбить на две разновидности: - языки описания аппаратуры (HDLs, Hardware Description Languages), с помощью которых разрабатываются модели уровня регистровых передач (RTL, Register Transfer Level). Среди таких языков можно выделить Verilog [1] и VHDL [2]; - языки проектирования системного уровня (system-level design languages), позволяющие описывать аппаратную систему на более высоком уровне абстракции и поддерживающие разработку программной части системы. К таким языкам относятся SystemC [3] и SystemVerilog [4].

134

В дальнейшем для удобства будем называть языками описания аппаратуры или HDL-языками обе указанные разновидности языков. Рассматриваемые в статье технологии нацелены на автоматизацию разработки тестов для моделей аппаратного обеспечения и создание тестовых систем с высоким уровнем повторного использования и устойчивых к изменениям реализации. Перед описанием технологий AVM, OVM и UniTESK (технология URM, упомянутоя во введении, не описывается в виду почти полного отсутствия документации по ней) отметим следующее. В названии подходов AVM и OVM содержится слово «методология», в то время как UniTESK, по мнению ее создателей, является технологией. В рамках данной статьи мы не различаем эти два термина и понимаем под ними совокупность принципов, методов и инструментов для разработки набора тестов.

3. Обзор технологии AVM Технология AVM (от англ. advanced verification methodology — передовая методология верификации) была создана в компании Mentor Graphics и распространяется под лицензией Apache 2.0. На настоящий момент она никак не стандартизирована и вся информация по ней находится в «книге рецептов» [5] и пользовательской инструкции по эксплуатации.

3.1. Основные принципы AVM С помощью технологии AVM реализуется возможность разработки сложных тестовых систем на SystemVerilog или SystemC. Основным средством AVM являются библиотеки классов, разработанные на этих языках. При разработке тестовых систем используются следующие базовые принципы: объектноориентированный подход, моделирование на уровне транзакций (TLM, Transaction-Level Modeling) и генерация случайных стимулов на основе ограничений (constraint-random generation). TLM — это подход к моделированию пересылки данных в цифровых системах, при котором организация связи между модулями системы отделена от их реализации. Под транзакцией понимается единичная пересылка управляющей информации или данных между двумя модулями. Например, в проектах, использующих шины передачи данных, чтение и запись в шину могут быть описаны транзакциями; в системах с коммутацией пакетов транзакцией является посылка или прием пакета. Использование объектно-ориентированного подхода и моделирования на уровне транзакций позволяет технологии AVM добиться высоких показателей повторного использования тестов. Использование механизмов наследования и перегрузки методов позволяет переопределять поведение компонента тестовой системы. За счет этого сокращается время, затрачиваемое на разработку и отладку тестов. 135

3.2. Архитектура тестовой системы AVM Тестовые системы, создаваемые с использованием технологии AVM, должны быть разбиты на несколько слоев (см. Рис. 1). Самый нижний уровень — это RTL-модель тестируемого устройства (DUT, Design Under Test). Над ним находится прослойка транзакторов (transactors) — компонентов тестовой системы, осуществляющих преобразование потока входных транзакций во входные сигналы тестируемой модели и наоборот преобразование выходных сигналов тестируемой модели в поток выходных транзакций. Примерами транзакторов являются: - драйвер (driver) — конвертирует поток транзакций во входные сигналы тестируемой модели; - ответчик (responder) — отвечает на запросы со стороны тестируемой модели относительно подачи дополнительных данных; - монитор (monitor) — осуществляет наблюдение за выходами тестируемой модели, не оказывая на нее влияния. Следующим слоем является так называемый слой операций (operational layer). Компоненты этого уровня образуют тестовое окружение необходимое тестируемой модели. К ним относятся: - генератор стимулов (stimulus generator) — создает поток входных транзакций (стимулов) на тестируемую модель. Для генерации стимулов используется подход на основе разрешения ограничений с использованием рандомизации (CRV, Constraint-Random Verification). Связь генератора с тестируемой моделью осуществляется через драйвер; - главный модуль (master) — элемент окружения тестируемой модели, инициирующий взаимодействие с ней. Главный модуль посылает последовательности транзакций (случайные или направленные на достижение какой-либо ситуации) и может использовать обратную связь для определения своих следующих действий. Связь главного модуля с тестируемой моделью осуществляется через драйвер; - подчиненный модуль (slave) — как и главный модуль моделирует окружение тестируемой модели, но, в отличие от него, является пассивным компонентом, отвечающим на запросы тестируемой модели. Связь подчиненного модуля с тестируемой моделью осуществляется через ответчик. Далее следует слой анализа (analysis layer), компоненты которого проверяют корректность поведения тестируемой модели, оценивают полноту тестирования и выполняют некоторые другие функции. Основными компонентами этого уровня являются: - компонент проверки (scoreboard) — проверяет корректность поведения тестируемой модели в ответ на входные транзакции; 136

- сборщик покрытия (coverage collector) — оценивает полноту тестирования путем подсчета числа событий заданных типов, возникающих в процессе тестирования. На самом верху находится слой управления, включающий в себя один единственный компонент — контроллер теста (test controller), который осуществляет координацию работы других компонентов тестовой системы. Рис. 1 иллюстрирует многослойную структуру тестовой системы. Каждый прямоугольник соответствует определенному слою. В левой части указано его название, в правой — основные компоненты тестовой системы, образующие данный слой. Стрелки показывают взаимодействие между слоями. Слой

Слой управления

Компоненты тестовой системы

Контроллер теста

Слой анализа

Компоненты проверки Сборщики покрытия

Слой операций

Генераторы стимулов Главные модули Подчиненные модули

Слой транзакторов

Слой реализации

не стандартизирована, но является главным претендентом на звание стандарта.

4.1. Основные принципы OVM Базовые принципы технологии OVM во многом схожи с AVM. Основным средством OVM является библиотека классов на языке SystemVerilog (в дальнейшем планируется поддержка SystemC), позволяющая создавать модульные тестовые системы, допускающие многократное использование. Одним из достоинств технологии является нацеленность на тестовое покрытие (CDV, Coverage-Driven Verification), что позволяет четко задавать цели тестирования и лучше управлять процессом разработки тестов.

4.2. Архитектура тестовой системы OVM В рамках технологии OVM тестовая система собирается из специальных блоков, называемых OVC (Open Verification Component). Каждый блок инкапсулирует тестовое окружение для отдельного модуля аппаратуры и состоит из полного набора компонентов, обеспечивающих генерацию стимулов, проверку правильности поведения и оценку полноты тестирования. Если тестируемая модель аппаратного обеспечения получается путем интеграции нескольких модулей, тестовая система для нее строится путем объединения соответствующих OVC-блоков и построения над ними специального синхронизирующего контроллера (virtual sequencer).

Драйверы Ответчики Мониторы

Тестируемая модель

Рис. 1. Слои тестовой системы AVM

4. Обзор технологии OVM Технология OVM (от англ. open verification methodology — открытая методология верификации) является совместной разработкой компаний Mentor Graphics и Cadence Design Systems. OVM представляет собой первый открытый промышленный метод разработки тестов на основе языка SystemVerilog [6]. Предшественниками OVM являются подходы AVM (от Mentor Graphics) и URM (от Cadence Design Systems). Технология OVM пока 137

Рис. 2. Блок тестовой системы 138

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

Структура OVC-блоков практически полностью соответствует архитектуре тестовой системы AVM. Пример блока тестовой системы приведен на Рис. 2.

5. Обзор технологии UniTESK

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

Технология UniTESK (от англ. unified specification and testing tool kit — унифицированный инструментарий для спецификации и тестирования) [7] разработана в Институте системного программирования РАН. В отличие от рассмотренных ранее технологий AVM и OVM, созданных в коммерческих организациях, UniTESK является академической разработкой, которая, тем не менее, основана на реальном опыте тестирования программного и аппаратного обеспечения.

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

5.1. Основные принципы UniTESK При разработке тестовых систем по технологии UniTESK используются следующие базовые принципы: - определенность набора компонентов с ясным разделением функций и четкими интерфейсами; - использование формальных спецификаций в форме пред- и постусловий интерфейсных операций и инвариантов типов данных для автоматической генерации тестовых оракулов (компонентов проверки); - применение конечно-автоматных моделей для построения последовательностей тестовых воздействий (стимулов). В качестве основного средства тестирования моделей аппаратного обеспечения используется инструмент CTESK, использующий для разработки тестовой системы язык SeC (Specification extension of C) — расширение языка программирования C.

5.2. Архитектура тестовой системы UniTESK Тестовая система UniTESK состоит из следующих основных компонентов (см. Рис. 3): - обходчик является библиотечным компонентом тестовой системы. В его основе лежит алгоритм обхода графа состояний конечного автомата, моделирующего целевую систему на некотором уровне абстракции; - итератор тестовых воздействий работает под управлением обходчика и предназначен для перебора в каждом достижимом состоянии конечного автомата допустимых тестовых воздействий. Он автоматически генерируется из тестового сценария, который представляет собой описание конечно-автоматной модели тестируемой системы; - тестовый оракул оценивает правильность поведения тестируемой системы в ответ на единичное тестовое воздействие. Он автоматически 139

Рис. 3. Архитектура тестовой системы UniTESK Помимо основных компонентов в тестовой системе выделяются части, отвечающие за интеграцию с конкретным HDL-языком. Например, для языка Verilog такими компонентами являются VPI1-модуль (включая VPI-медиатор) и Verilog-окружение. 1

VPI (Verilog Procedural Interface) — стандартный интерфейс, предназначенный для вызова из Verilog-модулей функций, написанных на языке программирования C и других языках программирования. 140

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

повторного использования тестов, в технологии UniTESK они менее развиты по сравнению с AVM и OVM. Во многом это связано с тем, что инструмент CTESK, используемый для тестирования моделей аппаратного обеспечения, основан на языке программирования C. Реализация основных принципов UniTESK для языков SystemVerilog и SystemC позволила бы улучшить показатели повторного использования тестов. Сопоставим архитектуру тестовой системы AVM (она такая же, как у OVCблока) и тестовой системы UniTESK (см. Рис. 4). Слой транзакторов в тестовой системе AVM приблизительно соответствует слою медиаторов в тестовой системе UniTESK. Соответствие в вышележащих слоях установить сложнее. Генератору стимулов AVM соответствует итератор тестовых воздействий UniTESK (в паре с обходчиком), компонентам проверки — тестовый оракул. Наиболее близким компонентом UniTESK, соответствующим контроллеру тестов AVM, является обходчик. Заметим, что для некоторых компонентов AVM нет явных соответствий в технологии UniTESK, например, там нет таких сущностей, как главные и подчиненные модули.

7. Заключение

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

Мы считаем, что в области разработки тестов для моделей аппаратного обеспечения в скором времени должны появиться стандарты. Главным претендентом на звание стандарта является технология OVM, которая продвигается такими крупными компаниями, как Mentors Graphics и Cadence Design Systems. Эта технология основана на хорошо зарекомендовавших себя подходах AVM и URM, поэтому ее начинают активно использовать в индустрии. Мы выступаем за унификацию технологии UniTESK (и других методов автоматизации разработки тестов для моделей аппаратного обеспечения) c подходом OVM. Лучше использовать один подход, который будет понятен разным группам разработчиков. Под унификацией здесь понимается следующее. Основные принципы, на которых основана UniTESK, прежде всего, использование формальных спецификаций в форме пред- и постусловий для описания поведения системы и применение конечно-автоматных моделей для генерации тестовых последовательностей, хорошо зарекомендовали себя на практике. Ничто не мешает реализовать эти принципы в терминах технологии OVM, на основе библиотеки базовых классов. Это позволит создавать тесты по технологии UniTESK, но которые при этом приобретают новое качество — их можно отчуждать, повторно использовать при построении более крупных тестовых систем и т.д.

142

Литература [1] IEEE Standard VHDL Language Reference Manual. IEEE Std 1076-1987. [2] IEEE Standard Hardware Description Language Based on the Verilog Hardware Description Language. IEEE Std 1364-1995. [3] IEEE Standard SystemC Language Reference Manual. IEEE Std 1666-2005. [4] IEEE Standard for SystemVerilog – Unified Hardware Design, Specification, and Verification Language. IEEE Std 1800-2005. [5] Adam Rose, Tom Fitzpatrick, Dave Rich, Harry Foster. Advanced Verification Methodology Cookbook. Mentor Graphics Corporation, 2008. (http://www.mentor.com/go/cookbook) [6] OVM Whitepaper. Mentor Graphics Corporation, Cadence, 2007. (http://www.ovmworld.org) [7] В.П. Иванников, А.С. Камкин, В.В. Кулямин, А.К. Петренко. Применение технологии UniTESK для функционального тестирования моделей аппаратного обеспечения. Препринт ИСП РАН, 2005.(http://citforum.ru/SE/testing/unitesk_hard/)

143

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

Генерация тестовых данных для системного функционального тестирования микропроцессоров с учетом кэширования и трансляции адресов

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

Е. В. Корныхин [email protected] Аннотация. В статье рассматривается задача генерации тестовых данных при генерации тестовых программ для системного функционального тестирования микропроцессоров (core-level verification), по абстрактной форме тестовой программы (тестовому шаблону). Для решения этой задачи в работе предложен алгоритм, сводящий ее к задаче разрешения ограничений. При этом учитываются такие особенности микропроцессора, как кэширование и трансляция адресов.

1. Введение Вычислительные системы играют все большую роль в процессах, от которых зависит здоровье и жизнь людей. Поэтому необходимо, чтобы вычислительные системы работали корректно. Базовым компонентом многих вычислительных систем являются микропроцессоры, выполняющие управляющие функции. Тестирование микропроцессоров является важной задачей, которой и посвящена данная работа. В данной работе микропроцессор рассматривается как единая система, входными данными для которой являются машинные программы, загруженные в память (далее такие программы будут называться тестовыми программами). Эти программы исполняются, процесс исполнения протоколируется и затем анализируется. Для функционального тестирования (которому посвящена данная статья) важно лишь, правильно ли исполнена загруженная программа. Кроме того, такое тестирование можно проводить еще до выпуска микропроцессора с использованием симуляции его модели на языке Verilog или VHDL. В статье [13] была предложена технологическая цепочка построения тестовых программ на основе модели микропроцессора. Цель генерации тестовых программ задается с помощью критерия тестового покрытия, выделяющего 145

4. завершающим этапом генерации тестовой программы является генерация начального состояния микропроцессора (регистров, кэшпамяти, TLB и др. – это и есть тестовые данные), на котором реализуются заданные в тестовом шаблоне зависимости и тестовые ситуации. В работе [13] последний этап был описан достаточно схематично. Автоматизации именно этого этапа (генерации тестовых данных) посвящена данная работа. Практика показывает, что при использовании штатных средств и алгоритмов удается строить тестовые данные для шаблонов небольшого размера (до трех инструкций), однако для тестирования современных процессоров следовало бы использовать тестовые шаблоны большего размера. Например, при тестировании конвейера приходится использовать тестовые программы, размер которых сопоставим с размером конвейера, а это несколько десятков инструкций. REGISTER ax : 32; REGISTER bx : 32; CONST offset : 16; ADD ax, bx, bx @ overflow

LUI ax, 0x50 ORI ax, ax, 0x67 SW bx, ax, 0x204 ADD ax, bx, bx

LW ax, bx, offset @ noexc(l1Miss,l2Hit)

LW ax, bx, 0x204

XOR bx, ax, bx @ noexc

XOR bx, ax, bx

Рис.1. Пример тестового шаблона и соответствующей ему тестовой программы 146

Входом генератора тестовых данных является тестовый шаблон (см. Рис 1) и модель тестовых ситуаций. По ним генератор тестовых данных строит начальное состояние микропроцессора (т.е. начальные значения регистров, ячеек кэш-памяти, буфера трансляции адресов и пр.) и ячеек ОЗУ. Генератор тестовых данных использует разрешение ограничений над целыми числами, для которого разработаны эффективные алгоритмы [12]. Причем обычно разрешение таких ограничений удается провести в разумные временные рамки. С использованием такого генератора тестовых данных удается полностью провести технологическую цепочку построения тестовых программ для микропроцессоров. Однако в известных работах [8, 9] описывается генерация ограничений для шаблонов, использующих лишь регистры, а для инструкций работы с памятью приводятся алгоритмы, не учитывающие такие технологии, как кэширование и трансляция адресов (получение физических адресов по виртуальным). Для шаблонов из арифметических и логических инструкций микропроцессора задача генерации тестовых данных заключается лишь в генерации начальных значений регистров (состояние остальных подсистем микропроцессора не меняется). Поэтому для таких шаблонов достаточно записать изменение значений в регистрах каждой инструкцией шаблона в виде ограничений и разрешить эти ограничения (на целые числа). Однако наивное применение подобных идей для инструкций работы с памятью приводит к очень сложным ограничениям 1, которые не удается разрешить за приемлемое время.

2. Обзор работ по системному функциональному тестированию микропроцессоров В настоящее время в практике тестирования микропроцессоров распространены следующие подходы к построению тестовых программ:

1

Даже без учета трансляции адресов для кодирования состояния микропроцессора можно использовать формулу длиной порядка размера памяти ( mem0 = var 0 ∧ mem1 = var1 ∧ ... ); каждое изменение производится по неизвестному индексу, поэтому при записи нового состояния микропроцессора приходится перебирать все приводит к формуле возможные варианты ( mem[i ] := x ) (i = 0 ∧ mem0 = x ∧ mem1 = var1 ∧ ...) ∨ (i = 1 ∧ mem0 = var 0 ∧ mem1 = x ∧ ...) ∨ ... ), а если таких изменений несколько, то приходится рассматривать все возможные варианты значений индексов. Получающаяся формула имеет размер порядка | L | ⋅2n , где | L | – размер памяти, а n – количество изменений памяти. В данной работе предложен метод кодирования изменений, приводящий к формуле размера порядка | L | + n . 147

•

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

•

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

•

случайная генерация тестовых программ применяется так же часто в силу простоты автоматизации. Такие тестовые программы позволяют быстро обнаружить простые ошибки, однако опять же не гарантируют полноты тестирования. Разрабатываются и более хитрые варианты случайной генерации [3].

•

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

В решении задачи генерации тестовых данных можно выделить следующие подходы: • комбинаторные техники; • с использованием решения задачи ATPG; • с использованием разрешения ограничений. Комбинаторные техники применимы в случае простых тестовых шаблонов. Ограничениями на переменные в таких тестовых шаблонах являются указания домена. Все значения в домене равноправны и могут появиться в тестовой программе. Однако данная техника требует доведения всех ограничений в тестовом шаблоне до простой формы (ограничение домена переменной), что удается сделать не всегда. В работе исследователей из Fujitsu Lab. [4] предлагается описывать тестовые программы в виде выражений (Test Specification Expressions, TSE) и описывать инструкции микропроцессора на языке ISDL. Специальный генератор строит тестовые программы, 148

удовлетворяющие TSE. Kohno и Matsumoto [5] рассматривают задачу верификации конвейерных микропроцессоров, сводя ее к генерации тестовых программ. В процессе своей работы генератор строит тестовый шаблон, к которому применяются также комбинаторные техники. Доменами переменных являются множество регистров и множество констант, допустимых в качестве значений параметров инструкций. Исследователи из Politecnico di Milano [7] предложили генеровать тестовые данные с использованием техник решения задачи ATPG (Automatic Test Pattern Generation). ATPG – задача поиска значений входных сигналов («векторов») схемы с целью поиска ее некорректного поведения. ATPG чаще применяется для модульного тестирования, если известна RTL-модель микропроцессора. Задача ATPG известна давно и для ее решения существуют (в том числе коммерческие) инструменты. Для применения ATPG при генерации тестовых программ необходимо, чтобы RTL-модель микропроцессора была готова к моменту генерации тестовых данных. Кроме того, использование такой методики именно для функционального тестирования ограничено, поскольку тесты на функционирование микропроцессора приходится строить с учетом модели спроектированного микропроцессора, которая сама же при этом будет и тестироваться. Наиболее впечатляющих результатов достигают инструменты, использующие для генерации тестовых данных разрешение ограничений. Ограничение с логической точки зрения то же, что и предикат, а задача разрешения ограничений – то же, что и задача выполнимости системы предикатов, но для решения этой задачи применяются специальные алгоритмы [12]. В работе [9] исследователей из Китайского Национального Университета технологий безопасности описывается инструмент MAATG. Тестовый шаблон для него может содержать лишь ограничения равенства или неравенства значений и указание области значений переменной. Для задания архитектуры микропроцессора используется описание на языке EXPRESSION. Другой инструмент – Genesys-Pro [8] – позиционируется компанией IBM как разработка, впитавшая лучшее за последние 20 лет. Тестовые шаблоны позволяют задавать тестовые программы переменной длины засчет повторов блоков инструкций и переборов внутри блока. Для любой инструкции в тестовом шаблоне может быть указана эвристика для выбора значений параметров [1]. Среди возможных эвристик есть и эвристики на события в кэш-памяти и при трансляции адресов. Однако в известных работах не раскрывается содержание таких эвристик, что не дает возможности понять эффективность генерации программ, нацеленных на тестирование памяти. Система команд микропроцессора должна быть описана в виде ограничений (constraint net) на операнды, код операции, что не является естественным описанием поведения инструкции, особенно если в рамках нее выполняется несколько последовательных вычислений на основе параметров инструкции. Для генерации параметров очередной инструкции Genesys-Pro использует уже построенную тестовую программу и состояние микропроцессора, которое 149

известно полностью. Genesys-Pro использует собственный, довольно нетривиальный, решатель ограничений, настроенный под генерацию тестовых программ. Этот подход обеспечил масштабируемость на большие тестовые шаблоны, но привел к необходимости использования механизма возврата (backtracking), когда выбрать параметры для очередной инструкции невозможно. В данной работе при решении задачи генерации тестовых данных также используется разрешение ограничений. В отличие от MAATG тестовые шаблоны могут содержать не просто ограничения равенства или неравенства, а более сложные ограничения, например, кэш-промах. А по сравнению с Genesys-Pro в данной статье делается попытка транслировать тестовый шаблон в ограничения целиком 2. При этом отпадает необходимость в механизме возврата 3. Особенностью тестовых шаблонов, получаемых в рамках [13], является фиксация для каждой инструкции регистров-параметров. Для таких шаблонов Genesys-Pro будет работать крайне неэффективно, поскольку теряется возможность с помощью выбора параметров «подогнать» исполнение очередной инструкции под заданные в тестовом шаблоне для нее события. На тестовых шаблонах из [13] Genesys-Pro будет работать следующим образом: выберет некоторое начальное состояние микропроцессора, начнет исполнять тестовый шаблон (поскольку начальное состояние ему известно), но как только дойдет до инструкции, которая будет исполнена не так, как требуется в шаблоне, Genesys-Pro сделает возврат в самое начало, а именно ему придется выбрать другое начальное состояние микропроцессора и весь процесс запустить заново. Такой процесс генерации тестовых данных слишком неэффективен для тестовых данных большого объема и тестовых шаблонах с множеством тестовых ситуаций. Для задания схемы трансляции адресов в Genesys-Pro предлагается использовать подход DeepTrans [10]. Однако по имеющимся работам невозможно сделать вывод о том, как такая схема трансляции адресов отображается в ограничения 4. Кроме 2

Известно, что задача разрешения ограничений (т.е. задача выполнимости) NP-полна. Это означает, что для больших тестовых шаблонов предлагаемый в данной статье метод может быть не столь эффективным. Однако действительно длинные тестовые шаблоны в практике тестирования микропроцессоров применяются редко. 3 Из-за этого качественно меняется разрешаемая система ограничений. Genesys-Pro сводит общую задачу к множеству задач, на порядок меньшей сложности. Кроме того, в данной статье предлагается более технологичный метод построения тестовых данных: описание архитектуры микропроцессора может быть получено из стандарта архитектуры микропроцессора и представляет собой понятное для человека императивное задание. 4 Авторы статьи используют при описании способа трансляции адреса элементы массива Memory с неизвестными индексами. Известно, что попытки построения ограничений, описывающих работу с элементами массива при 150

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

3. Описание тестовых шаблонов Тестовый шаблон задает свойства будущей тестовой программы. Как и тестовая программа, в тестовом шаблоне указывается последовательность инструкций тестовой программы. Каждый элемент такой последовательности содержит указание кода операции, аргументов и тестовой ситуации – связи значений операндов и состояния микропроцессора (ячейки кэш-памяти, регистры, другие подсистемы) перед началом выполнения инструкции. В качестве параметров команды в тестовом шаблоне могут выступать переменные величины – регистры, непосредственные значения, адреса. Отдельно могут быть зафиксированы в тестовой программе зависимости (предикаты) между переменными величинами. Подробнее см. [13]. Для возможности автоматического построения тестовых данных каждую тестовую ситуацию предлагается описать на простом императивном языке с единственным типом – целым числом заданной битовой длины [2, 14]. Каждое описание тестовой ситуации представляет собой последовательность операторов присваивания и операторов утверждения (assert), выражая соотношения между аргументами инструкций данной тестовой ситуации и состоянием микропроцессора. Пример описания тестового шаблона : REGISTER ax : 32; REGISTER bx : 32; CONST offset : 16; ADD ax, bx, bx @ overflow LW ax, bx, offset @ noexception( l1Miss, l2Hit ) XOR bx, ax, bx @ noexc В этом тестовом шаблоне три инструкции – ADD, LW и XOR. Шаблон начинается с объявления переменных с указанием их битовых длин. Модификатор (REGISTER или CONST) указывает семантику использования переменной. Тестовая ситуация указывается после знака «@»: тестовая ситуация первой команды – «overflow», второй команды – «noexception( l1Miss, l2Hit )» и третьей – «noexc». Тестовая ситуация для второй команды содержит параметры – они более детально описывают тестовую ситуацию. неизвестных индексах, приводит к очень сложным ограничениям, разрешимость которых за приемлемое время можно поставить под сомнение. 151

Каждой из трех задействованных тестовых ситуаций должно быть предоставлено описание. Описание первой тестовой ситуации – overflow – может быть таким (в описании используется операция битовой конкатенации «||» и отношение неравенства «#»): VAR RESULT x : 32; VAR READONLY y : 32; VAR READONLY z : 32; temp 1: (tc+1-t)/(t-1), = для t=1: c.

∑ij(yij) ≤ ∑ij(f(cij)) ≤ ∑ij(f(i-1)) ≤ ∑i(btf(i-1)) = = для t>1: bt∑i((ti-t)/(t-1)) = O(btn), = для t=1: b∑i(i-1) = O(bn2).

сравнения. Поэтому в любом случае объём вычислений по порядку в n раз превосходит длину обхода: для t>1: O(nbtn), для t=1: O(bn3). В этом подразделе мы убедимся, что при подходящей реализации алгоритма другие вычисления не изменяют этот порядок. Прежде всего, отметим, что лес деревьев, требуемый для прохода в неполное состояние, может использоваться много раз без его перестройки до тех пор, пока какое-то неполное состояние не станет полным. Поэтому мы будем перестраивать этот лес только в этом случае. Определим основные структуры данных. Будем считать, что все кнопки перенумерованы от 1 до b, и все пройденные состояния также пронумерованы. По номеру состояния i можно определить: I(i) – идентификатор состояния, получаемый при опросе состояния; B(i) – номер текущей кнопки, в полных состояниях B(i)=b+1, вначале B(i)=1; C(i) – счётчик текущей кнопки, вначале C(i)=0; T(i) – список различных номеров состояний, из которых в G выходит переход, заканчивающийся в i, вначале список T(i) пуст; P(i) – номер кнопки в лесе деревьев для достижения неполных состояний, начальное значение P(i)=0.

Эта оценка достигается (по порядку) на LTS, изображённой на Рис.4. Здесь имеется только одно действие и одна кнопка, разрешающая его. Если недетерминизм реализации устроен так, что в процессе движения по LTS каждый переход, выделенный пунктиром, предваряется t-1 переходами в начальное состояние (выделены жирной стрелкой), нижняя оценка равна O(tn). Заметим, что на этом примере указанная оценка достигается при любом алгоритме обхода, а не только описанном выше.

Отдельно хранится номер текущего состояния ic. Кроме этого, мы будем поддерживать счётчик N пройденных состояний (вначале N=0), счётчик полных состояний C (вначале C=0) и матрицу M размером N×N, строками и столбцами которой являются номера состояний, а M(i,j) cодержит кнопку, связанную с каким-нибудь переходом I(i)⎯ o→ I(j), или 0, если такой кнопки нет.

=

Теперь оценим суммарно работу блока «Переход в неполное состояние» во время обхода. Перенумеруем все состояния в том порядке, в котором они становились полными. Рассмотрим момент времени, непосредственно предшествующий получению в i-ом состоянии j-ой тройки (кнопка, наблюдение, постсостояние). Обозначим через cij число полных состояний в этот момент времени. Если непосредственно перед получением j-ой тройки мы выполняли блок «Переход в неполное состояние», переходя в состояние i, то обозначим через yij число тестовых воздействий в этом блоке; в противном случае положим yij=0. В силу доказанного yij≤f(cij). Поскольку cij≤i-1, а функция f монотонно возрастает, f(cij)≤f(i-1). Число троек, которые мы получаем в данном состоянии, не превосходит bt. Общая оценка числа тестовых воздействий в блоке равна:

Рис. 4. Пример реализации

4.4. Оценка объёма вычислений Мы будем считать, что при опросе состояния мы получаем его уникальный идентификатор, но не предполагаем каких-либо знаний об устройстве этого идентификатора, то есть мы можем только сравнивать два идентификатора на равенство. Каждый раз, когда после тестового воздействия мы делаем опрос постсостояния, мы должны определить, является ли это постсостояние новым или старым, и, если старым, то каким именно. Это требует O(n) операций 179

Блок «Текущее состояние неполное?» проверяет, что B(ic)≤b. Такое сравнение – элементарная операция, а число сравнений равно числу переходов, которое имеет точную верхнюю оценку O(btn). В блоке «Воздействие+наблюдение» в текущем состоянии с номером ic нажимается кнопка P и получается наблюдение o и постсостояние. Прежде всего, нам нужно определить номер постсостояния i`, что делается поиском по массиву состояний; если это новое состояние, то ему присваивается очередной номер N+1, создаётся его описание и расширяется матрица M, добавлением N+1-ых нулевых строки и столбца. Далее N:=N+1. Увеличиваем счётчик C(ic):=C(ic)+1. Если наблюдается отказ и i`=ic, или C(ic)=t, выбираем следующую кнопку B(ic):=B(ic)+1, C(ic):=0. Если M(ic,i`)=0, то состояние ic добавляется в список T(i`), а кнопка P заносится в матрицу M(ic,i`):=P. Меняется текущее состояние ic:=i`. 180

Все описанные операции можно считать элементарными, кроме определения номера постсостояния, которое требует порядка O(n) операций. Данный блок алгоритма работает не более btn раз, и суммарная оценка O(btn2). Если состояние ic становится полным B(ic)=b+1, то C:=C+1. Теперь нужно перестроить лес деревьев. Для этого используется рабочий список L номеров листовых состояний леса деревьев. Сначала за один просмотр всех пройденных состояний обнуляем номера кнопок P(i):=0 и помещаем номера неполных состояний в список L. Это даёт O(n) операций. Далее для головного элемента i списка L просматриваем список номеров состояний T(i) и для каждого состояния j из этого списка проверяем, принадлежит ли состояние j лесу деревьев, или ещё нет. Если не принадлежит (P(j)=0 & B(j)=b+1), то состояние j помещается в конец списка L, а P(j):=M(j,i). Построение заканчивается, когда список L становится пуст. Число проверяемых переходов по порядку не превышает O(btn). Поэтому лес деревьев строится за O(n)+O(btn)=O(btn) операций. Мы строим лес деревьев каждый раз, когда неполное состояние становится полным (и остаётся таким до конца), то есть не более n раз, что даёт суммарную оценку сложности построения всех лесов деревьев O(btn2). Суммарная оценка сложности работы блока «Воздействие+наблюдение» O(btn2)+O(btn2)=O(btn2). Блок «В G есть неполное состояние?» выполняет проверку C≠N. Суммарно это даёт не более O(btn) операций. В блоке «Переход в неполное состояние» для выполнения одного перехода нажимается кнопка P(ic) и опрашивается постсостояние. Здесь опять нам нужно определить номер постсостояния i`, что делается поиском по массиву состояний не более, чем за O(n) элементарных операций. Меняем текущее состояние ic:=i` и проверяем полноту нового текущего состояния. Если оно неполно, то есть B(ic)0), действия повторяются. Учитывая число тестовых воздействий в этом блоке O(btn) для t>1 и O(n3) для t=1, суммарно имеем оценку объёма вычислений: O(nbtn) для t>1, O(bn3) для t=1. Поскольку для t>1 имеем n≤tn-1, оценка объёма вычислений алгоритма:

O(btn)+O(btn2)+O(btn)+O(nbtn)=O(nbtn) для t>1, O(btn)+O(btn2)+O(btn)+O(bn3)=O(bn3) для t=1. 4.5. Сильно-Δ-связные реализации Описанный выше алгоритм обхода применим к любой конечной сильносвязной реализации с ограниченным недетерминизмом. При t=1 мы имеем детерминированный случай с полиномиальной оценкой длины обхода O(bn2) и объёма вычислений O(bn3). Однако при t>1 обе оценки экспоненциальны, что вряд ли приемлемо на практике. Эти оценки можно 181

улучшить, если ограничиться некоторыми подклассами тестируемых реализаций. Одним из таких подклассов является класс, так называемых, сильно-Δ-связных LTS. Сильно-Δ-связность была введена в [4] для решения задачи обхода графов переходов недетерминированных автоматов. Тестовое воздействие понималось как посылка стимула в реализацию, а наблюдение как получение реакции от реализации. Автомат не содержал непомеченных переходов (аналог τ-переходов в LTS). Мы переформулируем основные определения и утверждения этой работы в терминах LTS и R -семантики. Для состояния s и кнопки P Δ-переходом (s,P) будем называть множество всех переходов s⎯ z→ s`, где z∈P. Δ-маршрутом будем называть множество маршрутов D, начинающихся в одном состоянии и «ветвящихся» в каждом проходимом Δ-переходе. Формально: для любого префикса любого маршрута из D, заканчивающегося в состоянии s, существует такая кнопка P, что множество переходов, которыми этот префикс продолжается в D, совпадает с Δ-переходом (s,P). Начальное состояние a маршрутов Δ-маршрута будем называть началом Δ-маршрута. Если B – множество концов маршрутов Δ-маршрута, начинающегося в состоянии в состоянии a, такой Δ-маршрут называется [a,B]-Δ-маршрутом. Если B состоит из одной вершины b, то это [a,b]-Δ-маршрут. Длиной Δмаршрута будем называть максимальную длину его маршрутов. Маршрут будем называть обходом по кнопкам, если он содержит крайней мере один переход из каждого непустого Δ-перехода. Δ-обходом будем называть Δмаршрут, все маршруты которого являются обходами по кнопкам. Алгоритмом Δ-обхода называется такой алгоритм, который независимо от того или иного недетерминированного поведения LTS выполняет обход по кнопкам; суммарно по всем вариантам недетерминированного поведения LTS обходы по кнопкам, проходимые алгоритмом, образуют Δ-обход. Δ-путём называется Δ-маршрут, все маршруты которого являются путями. Состояние b Δ-достижимо из состояния a, если существует [a,b]-Δ-путь. LTS называется сильно-Δ-связной, если любое её состояние Δ-достижимо из любого другого состояния. Заметим, что Δ-достижимость мы также рассматриваем с учётом рестартов. Нестабильное состояние не может быть Δ-достижимым. Поэтому из сильно-Δсвязности следует отсутствие τ-переходов в реализации. Основное утверждение работы [4] переформулируется следующим образом: Существует алгоритм Δ-обхода сильно-Δ-связных LTS с точной верхней оценкой длины обхода O(nm) и объёма вычислений O(n2m), где n – число состояний, а m – число Δ-переходов. Для реализации с ограниченным 182

недетерминизмом m≤bn, и оценки имеют вид O(bn2) и O(bn3), соответственно. Для ограниченно недетерминированных сильно-Δ-связных реализаций можно модифицировать алгоритм Δ-обхода из [4] так, чтобы он стал алгоритмом обхода, то есть проходил по каждому переходу, а не по хотя бы одному переходу из каждого Δ-перехода. Этот алгоритм базировался на локальной аппроксимации Δ-расстояния состояния a до множества состояний B, где Δрасстояние определялось как минимальная длина [a,B]-Δ-маршрута по пройденной LTS. В качестве такого множества B выбиралось множество состояний, в которых мы нажимали ещё не все кнопки, поскольку целью был обход по кнопкам: в каждом состоянии нужно было хотя бы один раз нажать каждую кнопку. Модификация сводится к тому, что в качестве множества B выбирается множество неполных состояний. Поскольку теперь мы должны нажимать в каждом состоянии каждую кнопку хотя бы t раз, оценки увеличиваются в t раз: O(btn2) для числа тестовых воздействий и O(btn3) для объёма вычислений.

5. Алгоритм тестирования 5.1. Безопасно-достижимая LTS Обозначим: I – реализационная LTS, S – спецификационная LTS. В процессе тестирования мы будем строить безопасно-достижимую LTS, порождаемую не всеми маршрутами реализации, начинающимися в начальном состоянии, как для обхода, а только теми из них, трассы которых безопасны в спецификации. При тестировании мы будем совершать обход именно этой LTS. Если тестирование опирается на сильно-Δ-связность LTS, то это свойство предъявляется не ко всей реализации, а к её безопаснодостижимой LTS. Пройденную при тестировании часть LTS, по-прежнему, будем обозначать G. По-прежнему с каждым пройденным состоянием i и с каждой кнопки P свяжем счётчик c(P,i) числа нажатий кнопки P в состоянии i (3.1). Кроме того для каждого состояния i будем хранить множество S(i), элементами которого являются множества состояний спецификации. Множество S принадлежит S(i), если после наблюдения некоторой трассы σ мы оказались в реализационном состоянии i, а в спецификации трасса σ безопасна и заканчивается во множестве состояний S=(S after σ). Будем говорить, что кнопка P допустима в состоянии i, если она безопасна хотя бы в одном множестве состояний S∈S(i). Только допустимые кнопки мы можем нажимать, когда находимся в состоянии i. Определение полного состояния меняется, поскольку теперь требуется, чтобы не каждая, а каждая допустимая в состоянии кнопка была в нём полна. 183

Теперь реализация I и полностью построенная LTS G имеют одно и то же множество Safe(S)∩I R -трасс, безопасных в спецификации. Более того, они имеют одно и то же множество безопасно-тестируемых трасс, то есть трасс вида σ⋅〈o〉, где σ∈Safe(S)∩I, а наблюдение o разрешается некоторой кнопкой P safe S after σ. Поэтому I saco S ⇔ G saco S. Также LTS I и G имеют одно и то же множество состояний, достижимых в реализации по безопасно-тестируемым трассам.

5.2. Начало работы алгоритма В начале тестирования в G у нас есть только одно состояние i∈{I after ε}, соответствующее множеству состояний спецификации после пустой трассы ε. Полагаем S(i)={S after ε}. В состоянии i допустимы только те кнопки, которые допустимы в спецификации после пустой трассы, для каждой такой кнопки P полагаем c(P,i):=0. Если мы не предполагаем стабильности начального состояния (в частности, сильно-Δ-связности реализации), нам нужно в процессе тестирования получить все состояния реализации из множества I after ε. Для этого необходимо и достаточно, чтобы рестарт был определён хотя бы в одном состоянии, достижимом по безопасной трассе спецификации. Если начальное состояние реализации нестабильно, и рестарт не определён в безопаснодостижимых состояниях, то условие сильно-связности не гарантирует полноты тестирования (в отличие от обхода). Пример приведён на Рис.5. Здесь реализация не конформна спецификации, так как в ней с самого начала может наблюдаться действие y, что запрещено спецификацией (может быть только отказ {y}). Если в начале тестирования мы оказываемся в состоянии реализации 1, то при отсутствии рестарта в состояние 0 мы можем попасть только после нажатия кнопки {x}. А согласно спецификации после любой трассы, содержащей x, кнопка {y} опасна, и мы не будем её нажимать. Следовательно, мы не обнаружим наличие действия y в состоянии 0, то есть не обнаружим ошибку.

Рис. 5. Пример спецификации и неконформной реализации

184

5.3. Общая схема алгоритма На Рис.6 изображена общая схема алгоритма. В отличие от схемы обхода на Рис.3 здесь добавляются три блока, обведённые широкой серой линией. Кроме того, в блоке «Воздействие+наблюдение» мы нажимаем не любую кнопку, которая не полна в текущем состоянии, а только допустимую. Этим гарантируется, что при тестировании проходятся только трассы, безопасные в спецификации, поскольку в блоке «Переход в неполное состояние» нажимаются только те кнопки, которые уже раньше нажимались в блоке «Воздействие+наблюдение», то есть тоже допустимые.

2) o=P – отказ (им помечен виртуальный переход). Если P safe S, то вычисляется множество S`, состоящее из всех состояний s`∈S, в которых имеется отказ P. Если S`=∅, то это означает, что o∉obs(S,P), и процедура фиксирует ошибку. Если P safe S, то ничего не делается. 3) o=τ – внутреннее действие. Вычисляется S`=S, ошибка не фиксируется. Блок «Верификация наблюдения» работает после того, как в блоке «Воздействие+наблюдение» мы добавили новый (возможно, виртуальный) переход i⎯ o→ i`, где наблюдение o отлично от рестарта и отказа по рестарту. (Если мы наблюдаем отказ по рестарту в другом состоянии i`≠i, то, как описано выше, добавляется переход i⎯ τ→ i`.) Для каждого множества состояний S∈S(i) вызывается процедура Post(i⎯ o→ i`,S). Если проверка завершена успешно, выполняется блок «Распространение». В случае наблюдения рестарта постсостояние – это начально-достижимое состояние, поэтому множество S after ε добавляется к S(i`) при условии, что его там не было, и помечается в S(i`) флагом «добавленное». В блоке «Распространение» вызываем процедуру Post(i⎯ o→ i`,S) для

Рис. 6. Общая схема алгоритма Определим процедуру Post(i⎯ o→ i`,S), которая совмещает функции верификации (оракул) и вычисление множества спецификационных постсостояний. Здесь i⎯ o→ i` – это переход LTS G, а S∈S(i). Если фиксируется ошибка (неконформность), то тестирование заканчивается с вердиктом fail. Иначе вычисленное множество спецификационных постсостояний S` добавляется во множество S(i`) при условии, что S`≠∅ и S`∉S(i`), и помечается во множестве S(i`) специальным флагом «добавленное». Возможны три случая: 1) o – внешнее действие. Если существует кнопка P safe S такая, что o∈P, то вычисляется множество S`, состоящее из всех состояний s`, которые достижимы в спецификации по τ-переходам из концов переходов вида s⎯ z→ s`, где s∈S. Если S`=∅, то это означает, что o∉obs(S,P), и процедура фиксирует ошибку. Если такая кнопка P не существует, то ничего не делается. 185

каждого уже имеющегося перехода i⎯ o→ i`, где наблюдение o отлично от рестарта и отказа по рестарту, и добавленного множества состояний S∈S(i), после чего снимаем с множества S в S(i), флаг «добавленное». Эти действия выполняются до тех пор, пока есть добавленные множества состояний. Поскольку число состояний реализации конечно, а также конечно число состояний спецификации и, следовательно, число множеств состояний спецификации, блок «Распространение» закончится за конечное время. Важно отметить, что в этих двух блоках происходит не только верификация наблюдения, полученного после реальной трассы, пройденной при тестировании, но также после возможных наблюдений после потенциальных трасс. Более точно: верифицируются наблюдения, про которые установлено, что они возможны в реализации после трасс, про которые известно, что они безопасны в спецификации и имеются в реализации. Это даёт существенную экономию числа тестовых воздействий, необходимых для проверки конформности: мы выполняем множество проверок без реального тестирования, основываясь на полученном знании о поведении реализации. Докажем, что тест, работающий по описанному алгоритму, является полным, то есть значимым и исперпывающим. Сначала покажем, что для каждого состояния i LTS G каждое множество S∈S(i) является концом некоторой трассы, безопасной в спецификации: & i∈(I after σ). Будем вести ∃σ∈Safe(S)∩I S=(S after σ) 186

доказательство индукцией по последовательности добавлений множества S∉S(i) для любого S и любого i: S(i):=S(i)∪S. Такое добавление делается: 1) в начале работы алгоритма, 2) в блоке «Верификация наблюдения» для рестарта, 3) в процедуре Post. В случаях 1 и 2 утверждение верно для пустой трассы σ=ε. Процедура Post(i⎯ o→ i`,S) добавляет в S(i`)

множество постсостояний

S`

для перехода

i⎯ o→ i`

таким

образом, что, если ∃σ∈Safe(S)∩I S=(S after σ) & i∈(I after σ), то для

o≠τ

имеем

o safe (S after σ)

i`∈(I after σ⋅〈o〉), а для Утверждение доказано.

o=τ

&

имеем

S`=(S after σ⋅〈o〉)

S`=S

&

&

i`∈(I after σ).

Значимость эквивалентна тому, что каждая ошибка, обнаруживаемая тестом, действительно говорит о неконформности реализации. С учётом доказанного утверждения вердикт fail выносится в процедуре Post только тогда, когда обнаруживается, что после некоторой трассы σ∈Safe(S)∩I некоторая кнопка P safe S after σ разрешает наблюдение o∈obs(I after σ,P), отсутствующее в спецификации o∉obs(S after σ,P), то есть когда реализация неконформна. Исчерпываемость означает, что, если тест заканчивается с вердиктом pass, то реализация конформна. Нам достаточно показать, что для каждой трассы σ∈Safe(S)∩I после завершения теста каждое состояние i∈(I after σ) имеется в LTS G и (S after σ)∈S(i). Будем вести доказательство индукцией по трассам. Для пустой трассы ε утверждение верно, поскольку в начале тестирования или после одного из рестартов мы добавляем S after ε во множество S(i) для каждого состояния i∈(I after ε). Рассмотрим непустую трассу σ⋅〈o〉∈Safe(S)∩I, где наблюдение o отлично от рестарта или отказа по рестарту и разрешается некоторой кнопкой P safe S after σ. Пусть утверждение верно для трассы σ, и докажем его для трассы σ⋅〈o〉. Пусть состояние i`∈(I after σ⋅〈o〉). Тогда в реализации есть состояние i∈(I after σ) и переход i⎯ o→ i` (если o отказ, то это виртуальная петля). По предположению шага индукции, состояние i имеется в G и (S after σ)∈S(i). Поскольку в конце тестирования с вердиктом pass все состояния полны, мы должны были в состоянии i нажимать кнопку P и после некоторого нажатия получить переход i⎯ o→ i`. Следовательно, процедура Post должна была выполняться с параметрами (i⎯ o→ i`,S). А тогда требовалось доказать.

(S after σ⋅〈o〉)∈S(i`), что и 187

5.4. Оценка числа тестовых воздействий В отличие от обхода, при тестировании нажимаются только те кнопки, которые допустимы в текущем состоянии i. Допустимость кнопки в состоянии i зависит от трассы. Может случиться так, что кнопка P недопустима в состоянии i настолько долгое время, что все допустимые кнопки уже нажимались нужное число раз, то есть состояние i стало полным. Однако потом, после получения (реальной или потенциальной) трассы σ такой, что P safe S after σ и i∈(I after σ), кнопка P становится допустимой в состоянии i, то есть оно становится снова неполным. Теперь мы не можем считать, что состояние, ставшее полным, остаётся таким до конца тестирования. Поэтому при оценке суммарной работы блока «Переход в неполное состояние» нельзя считать монотонно неубывающим число полных состояний, от которого зависит оценка числа тестовых воздействий при однократной работы блока. Мы дадим оценку на основе числа вызовов блока. После прохода в неполное состояние мы нажимаем кнопку, которую ещё не нажимали нужное число раз в этом состоянии. Поэтому блок вызывается не более btn раз, и каждый раз выполняется не более f(n-1) тестовых воздействий. Это даёт оценку O(bntn) для t>1, и O(bn2)для t=1. Для детерминированного случая (t=1) оценка не изменилась, а для t>1 возросла в n раз. Мы высказываем гипотезу о том, что эта оценка завышена, а точная оценка остаётся той же O(btn). Эта гипотеза верна для b=1. Достаточно рассмотреть состояние in, которое последним из всех состояний становится полным. В состоянии, находящемся на расстоянии r от состояния in, мы должны были быть не более tr раз. Обозначим через ar число таких состояний. Суммарно во всех состояниях мы должны были быть не более ∑r(artr) ≤ t+t2+t3+…+tn = O(tn) раз, что совпадает с числом тестовых воздействий. Также эту гипотезу мы можем доказать для случая, когда рестарт определён в каждом (достижимом по безопасным трассам спецификации) состоянии реализации. Переход в неполное состояние выполняется как рестарт и далее переход в неполное состояние из начального состояния (если начальное состояние нестабильно, то может потребоваться несколько рестартов подряд, но это не увеличивает, а скорее уменьшает оценку). Выберем дерево, ориентированное от начального состояния и содержащее все пройденные состояния. Мы будем двигаться по дереву, нажимая соответствующие кнопки. Каждый раз, когда окажется, что мы не проходим нужный переход дерева изза недетерминизма, мы будем снова делать рестарт и начинать с начала. Обозначим через ar число состояний, находящих на расстоянии r от начального состояния по дереву. Чтобы гарантированно попасть в такое состояние, нам нужно по порядку не более tr тестовых воздействий. 188

Суммарно для прохода по одному разу в каждое состояние потребуется число = тестовых воздействий по порядку не более ∑r(artr) ≤ t+t2+…+tn-1 O(tn-1). Поскольку в каждое состояние мы должны переходить не более bt раз, общая оценка O(btn).

5.5. Оценка объёма вычислений Отличия от обхода следующие: 1) большее число тестовых воздействий, 2) большее число раз строится лес деревьев, 3) работа дополнительных блоков алгоритма. 1) Число тестовых воздействий умножается на n для оценки числа операций, требуемых для поиска номера состояния по его идентификатору. Суммарная оценка: для t>1: O(bn2tn) или O(bntn), если есть рестарты, и O(bn3)для t=1. 2) Лес деревьев теперь может строиться больше, чем n раз, но не более bn раз, так как каждое состояние переходит из неполного состояния в полное, при завершении нажатий некоторой кнопки. Суммарная оценка увеличивается в b раз: O(b2tn2). 3) Основные вычисления в дополнительных блоках происходят в процедуре Post(i⎯ o→ i`,S), однократная работа которой требует константного числа операций. Можно привести пример спецификации с k состояниями и реализации с n состояниями такой, что в LTS G появятся все возможные пары (i,S), то есть n2k пар. Для каждой такой пары проверяется не более bt переходов. Суммарная оценка O(btn2k). Нужно отметить, что все проверки, которые выполняет процедура Post, необходимы для верификации конформности: это проверки всех наблюдений, возможных в реализации после всех безопасных трасс спецификации. Общий объём вычислений алгоритма: O(bn2tn)+O(b2tn2)+O(btn2k), или первое слагаемое заменяется на O(bntn), если есть рестарты, или O(bn3)для t=1.

5.6. Сильно-Δ-связные реализации Числов тестовых воздействий определяется, главным образом, проходами в неполные состояния. Алгоритм, основанный на локальной аппроксимации Δрасстояний, предполагает, что каждое состояние только один раз становится полным. Но можно вычислять точные Δ-расстояния по LTS G. Каждый проход в неполное состояние будет, по-прежнему, требовать по порядку не более O(n) тестовых воздействий. Число таких проходов не более btn, поэтому суммарная оценка числа тестовых воздействий O(btn2). Для трёх случаев, описанных в предыдущем подразделе, имеем следующие оценки объёма вычислений. 189

1) Число тестовых воздействий умножается на n для оценки числа операций, требуемых для поиска номера состояния по его идентификатору. Суммарная оценка: O(btn3). 2) При вычислении Δ-расстояний нам достаточно для каждого состояния отметить Δ-переход, по которому достигается минимальное Δ-расстояние, то есть отметить кнопку. Такое вычисление аналогично построению леса деревьев и требует число операций по порядку не более числа переходов, то есть не более O(btn). Мы должны перевычислять Δ-расстояния каждый раз, когда неполное состояние становится полным. Число состояний n. Поскольку состояние становится полным, когда выполняются все нужные переходы по некоторой кнопке, это состояние становится полным не более b раз. Суммарная оценка O(b2tn2). 3) Вычисления в процедуре Post, как и в общем случае, занимают порядка O(btn2k) операций. Итоговая оценка объёма вычислений O(btn3)+O(b2tn2)+O(btn2k). Литература [1] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Использование конечных автоматов для тестирования программ. «Программирование». 2000. No. 2. [2] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай. «Программирование». 2003. No. 5. [3] Кулямин В.В., Петренко А.К., Косачев А.С., Бурдонов И.Б. Подход UniTesK к разработке тестов. «Программирование», 2003, No. 6. [4] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Неизбыточные алгоритмы обхода ориентированных графов. Недетерминированный случай. «Программирование». 2004. No. 1. [5] Бурдонов И.Б. Обход неизвестного ориентированного графа конечным роботом. «Программирование», 2004, No. 4. [6] Бурдонов И.Б. Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом. «Программирование», 2004, No. 6. [7] Бурдонов И.Б. Исследование одно/двунаправленных распределённых сетей конечным роботом. Труды Всероссийской научной конференции "Научный сервис в сети ИНТЕРНЕТ". 2004. [8] Бурдонов И.Б., Косачев А.С. Тестирование компонентов распределенной системы. Труды Всероссийской научной конференции «Научный сервис в сети ИНТЕРНЕТ», Изд-во МГУ, 2005. [9] Бурдонов И.Б., Косачев А.С. Верификация композиции распределенной системы. Труды Всероссийской научной конференции «Научный сервис в сети ИНТЕРНЕТ», Изд-во МГУ, 2005. [10] Bourdonov I., Kossatchev A., Kuliamin V. Formal Conformance Testing of Systems with Refused Inputs and Forbidden Actions. Proc. Of MBT 2006, Vienna, Austria, March 2006. [11] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Формализация тестового эксперимента. «Программирование», 2007, No. 5.

190

[12] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Безопасность, верификация и теория конформности. Материалы Второй международной научной конференции по проблемам безопасности и противодействия терроризму, Москва, МНЦМО, 2007. [13] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушением. «Наука», 2008. [14] Бурдонов И.Б. Теория конформности для функционального тестирования программных систем на основе формальных моделей. Диссертация на соискание учёной степени д.ф.-м.н., Москва, 2008. [15] http://www.ispras.ru/~RedVerst/RedVerst/Publications/TR-01-2007.pdf [16] Василевский М.П. О распознавании неисправностей автомата. Кибернетика, т. 9, № 4, стр. 93–108, 1973. [17] Aho A.V., Dahbura A.T., Lee D., Uyar M.Ü. An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Chinese Postman Tours. IEEE Transactions on Communications, 39(11):1604–1615, 1991. [18] Blass A., Gurevich Y., Nachmanson L., Veanes M. Play to Test Microsoft Research. Technical Report MSR-TR-2005-04, January 2005. 5th International Workshop on Formal Approaches to Testing of Software (FATES 2005). Edinburgh, July 2005. [19] Edmonds J. Johnson E.L. Matching. Euler Tours, and the Chinese Postman. Math. Programming 5, 88-124 (1973). [20] Fujiwara S. Bochmann G.v. Testing Nondeterministic Finite State Machine with Fault Coverage. IFIP Transactions, Proceedings of IFIP TC6 Fourth International Workshop on Protocol Test Systems, 1991, Ed. By Jan Kroon, Rudolf J. Hei-jink, and Ed Brinksma, 1992, North-Holland, pp. 267-280. [21] van Glabbeek R.J. The linear time – branching time spectrum. In J.C.M. Baeten and J.W. Klop, editors, CONCUR’90, Lecture Notes in Computer Science 458, SpringerVerlag, 1990, pp. 278–297. [22] van Glabbeek R.J. The linear time - branching time spectrum II; the semantics of sequential processes with silent moves. Proceedings CONCUR ’93, Hildesheim, Germany, August 1993 (E. Best, ed.), LNCS 715, Springer-Verlag, 1993, pp. 66-81. [23] Goodenough J.B. Gerhart S.L. Toward a theory of test data selection. IEEE Trans. Software Eng., vol. SE-1, no. 2, pp. 156- 173, June 1975. [24] Grochtmann M., Grimm K. Classification trees for partition testing. Software Testing, Verification and Reliability, 3:63-82, 1993. [25] Heerink L., Tretmans J. Refusal Testing for Classes of Transition Systems with Inputs and Outputs. In T.Mizuno, N.Shiratori, T.Higashino, A.Togashi, eds. Formal Description Techniques and Protocol Specification, Testing and Verification. Chapman & Hill, 1997. [26] Heerink L. Ins and Outs in Refusal Testing. PhD thesis, University of Twente, Enschede, The Netherlands, 1998. [27] Lee D., Yannakakis M. Testing Finite State Machines: State Identification and Verification. IEEE Trans. on Computers, Vol. 43, No. 3, March 1994, pp. 306-320. [28] Lee D., Yannakakis M. Principles and Methods of Testing Finite State Machines – A Survey. Proceedings of the IEEE 84, No. 8, 1090–1123, 1996. [29] Legeard B., Peureux F., Utting M. Automated boundary testing from Z and B. In Proc. of the Int. Conf. on Formal Methods Europe, FME'02, volume 2391 of LNCS, Copenhaguen, Denmark, pages 21--40, July 2002. Springer. [30] Lestiennes G., Gaudel M.-C. Test de systemes reactifs non receptifs. Journal Europeen des Systemes Automatises, Modelisation des Systemes Reactifs, pp. 255–270. Hermes, 2005.

191

[31] Milner R. A Calculus of Communicating Processes. LNCS, vol. 92, Springer-Verlag, 1980. [32] Milner R. Modal characterization of observable machine behaviour. In G. Astesiano & C. Bohm, editors: Proceedings CAAP 81, LNCS 112, Springer, pp. 25-34. [33] Milner R. Communication and Concurrency. Prentice-Hall, 1989. [34] Petrenko A., Yevtushenko N., Bochmann G.v. Testing deterministic implementations from nondeterministic FSM specifications. Selected proceedings of the IFIP TC6 9-th international workshop on Testing of communicating systems, September 1996. [35] Petrenko A., Yevtushenko N., Huo J.L. Testing Transition Systems with Input and Output Testers. Proc. IFIP TC6/WG6.1 15th Int. Conf. Testing of Communicating Systems, TestCom’2003, pp. 129-145. Sophia Antipolis, France, May 26-29, 2003. [36] Zhu, Hall, May. Software unit test coverage and adequacy. ACM Computing Surveys, v. 29, n. 4, 1997.

192

Тестирование с преобразованием семантик И.Б. Бурдонов, А.С. Косачев {igor,kos}@ispras.ru Аннотация. В статье представлен подход к формальному описанию тестирования в случае, когда тестовые семантики спецификации и реализации различаются. Для этого используется медиатор, осуществляющий преобразование спецификационных тестовых воздействий в реализационные и обратное преобразование реализационных наблюдений в спецификационные. Формально переопределяются условия тестирования и конформность. Также рассматривается тестирование с заданным преобразованием реализационных состояний в спецификационные. Определяются условия и способ построения теста, обнаруживающего все ошибки в реализации за конечное время.

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

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

2. Теория конформности 2.1. Семантика взаимодействия и безопасное тестирование Данная работа опирается на теорию тестирования конформности, изложенную в [3,4,5]. Напомним основные положения этой теории. Тестирование – это проверка в процессе эксперимента соответствия (конформности) реализации требованиям, заданным в виде спецификации. Семантика тестового взаимодействия определяется в терминах действий и кнопок. Действие – это внешнее действие тестируемой системы (реализации), которое может наблюдаться при тестировании. Множество внешних действий называется алфавитом действий и обозначается L. Кнопка – это подмножество P⊆L; нажатие кнопки P моделирует тестовое воздействие на реализацию, сводящееся к разрешению выполнять любое действие из P. При нажатии кнопки P наблюдается либо действие a∈P, выполняемое реализацией, либо – для некоторых кнопок – отсутствие таких действий, называемое отказом P. Семантика взаимодействия задаётся алфавитом L и двумя наборами кнопок: с наблюдением соответствующих отказов – семейство R⊆P (L) и без наблюдения отказов – семейство Q⊆P (L). Предполагается, что R∩Q=∅ и ∪R∪∪Q=L. Такая семантика называется R/Q-семантикой. Кроме внешних действий реализация может совершать внутренние (ненаблюдаемые) действия, обозначаемые τ. Эти действия всегда разрешены. Предполагается, что любая конечная последовательность любых действий совершается за конечное время, а бесконечная – за бесконечное время. 194

Бесконечная последовательность τ-действий («зацикливание») называется дивергенцией и обозначается Δ. Кроме этого вводится специальное, также не регулируемое кнопками, действие, которое называется разрушением и обозначается γ. Оно моделирует любое запрещённое при тестировании поведение реализации. Дивергенция сама по себе не опасна, но при попытке выхода из неё, когда нажимается любая кнопка, неизвестно, нужно ли ждать наблюдения или бесконечно долго будут выполняться только внутренние действия. Поэтому нельзя ни продолжить тестирование, ни закончить его. Тестирование, при котором не возникает разрушения и попыток выхода из дивергенции, называется безопасным.

Если нажатие кнопки P после R-трассы σ не вызывает попытку выхода из дивергенции (после трассы нет дивергенции) и не вызывает разрушение (после действия, разрешаемого кнопкой), то кнопка P называется безопасной в LTS после σ. При безопасном тестировании нажимаются только безопасные кнопки. Формально, кнопка P безопасна: в состоянии s: P safe s, если состояние s не дивергентно и в каждом состоянии s`, достижимом из s по τ-переходам, нет γ-переходов, а все переходы s`⎯ z→ s``, где z∈P неразрушающие;

2.2. LTS-модель и трассы наблюдений

во множестве состояний S: P safe S  ∀s∈S P safe s;

В качестве модели реализации и спецификации используется система помеченных переходов (LTS – Labelled Transition System) – ориентированный граф с выделенной начальной вершиной, дуги которого помечены некоторыми символами. Формально, LTS – это совокупность S=LTS(VS,L,ES,s0), где VS – непустое множество состояний (вершин графа), L – алфавит внешних действий, ES⊆VS×(L∪{τ,γ})×VS – множество переходов (помеченных дуг графа), s0∈VS – начальное состояние (начальная вершина графа). Переход из состояния s в состояние s` по действию z обозначается s⎯ z→ s`. Обозначим

после трассы σ: P safe S after σ  P safe (S after σ),

s⎯ z→  ∃s` s⎯ z→ s` и s⎯ z  s` s⎯ z→ s`. Маршрутом LTS называется последовательность смежных переходов: начало каждого перехода, кроме первого, совпадает с концом предыдущего перехода. Выполнение LTS в машине тестирования сводится к выполнению того или иного перехода, определённого в текущем состоянии и разрешаемого нажатой кнопкой (τ- и γ-переходы всегда разрешены). Состояние стабильно, если из него не выходят τ- и γ-переходы, и дивергентно, если в нём начинается бесконечная цепочка τ-переходов (в частности, τ-цикл). Отказ P∈R порождается стабильным состоянием, из которого нет переходов по действиям из P. Переход s⎯ z→ s` разрушающий, если из s` по цепочке (возможно пустой) τ-переходов достижимо начало γ-перехода. Добавим в каждом стабильном состоянии LTS S виртуальные петли, помеченные порождаемыми отказами, и Δ-переходы из дивергентных состояний. В полученной LTS рассмотрим маршруты, начинающиеся в начальном состоянии и не продолжающиеся после Δ- и γ-переходов. Rтрассой LTS S назовём последовательность пометок на переходах такого маршрута с пропуском символов τ. Множество R-трасс LTS S обозначим R(S). 195

2.3. Гипотеза о безопасности и безопасная конформность

где S after σ – множество состояний LTS S после трассы σ, то есть состояний, достижимых из начального состояния по трассе σ. Безопасность кнопок влечёт безопасность действий и отказов после трассы. Отказ R safe (S after σ), если после трассы σ безопасна кнопка R. Действие z safe (S after σ), если оно разрешается (z∈P) некоторой кнопкой P safe (S after σ). R-трасса безопасна, если 1) LTS не разрушается с самого начала, то есть в ней нет трассы 〈γ〉, 2) каждый символ трассы безопасен после непосредственно предшествующего ему префикса трассы. Множества безопасных трасс LTS S обозначим Safe(S). Требование безопасности тестирования выделяет класс безопасных реализаций, которые могут быть безопасно протестированы для проверки их конформности заданной спецификации. Этот класс определяется гипотезой о безопасности: реализация I безопасна для спецификации S, если 1) в реализации нет разрушения с самого начала, если этого нет в спецификации, 2) после общей безопасной трассы реализации и спецификации любая кнопка, безопасная в спецификации, безопасна после этой трассы в реализации: I safe for S  (〈γ〉∉F(S) ⇒ 〈γ〉∉F(I)) &

∀σ∈Safe(S)∩I ∀P∈R (P safe S after σ ⇒ P safe I after σ).

Гипотеза о безопасности не проверяема при тестировании и является его предусловием. Отношение конформности формально определяется так: реализация I конформна спецификации S, если она безопасна и выполнено проверяемое условие: любое наблюдение, возможное в реализации в ответ на нажатие безопасной (в спецификации) кнопки, разрешается спецификацией: I saco S  I safe for S & ∀σ∈Safe(S)∩I ∀P∈R (P safe S after σ ⇒ obs(I after σ,P)⊆obs(S after σ,P)), 196

где obs(M,P)  {u|∃m∈M u∈P & m⎯ u→ ∨ u=P & ∀z∈P m⎯ z } – множество наблюдений, которые возможны в состояниях из множества M при нажатии кнопки P. В [3,5] показано, что достаточно ограничиться семантиками, в которых все отказы наблюдаемы: Q=∅. Любая R/Q-семантика эквивалентна R∪Q/∅семантике: для любой спецификации в R/Q-семантике существует (и может быть построена при некоторых, практически приемлемых, ограничениях) спецификация в R∪Q/∅-семантике, определяющая тот же класс конформных реализаций и не меньший класс реализаций, поддающихся тестированию. Поэтому мы будем рассматривать только R-семантики, то есть Q=∅.

2.4. Генерация тестов Тест – это инструкция, состоящая из терминальных и нетерминальных пунктов. В каждом пункте указывается кнопка, которую нужно нажимать, и для каждого наблюдения, возможного после нажатия этой кнопки, – пункт инструкции, который должен выполняться следующим, или вердикт (pass или fail), если тестирование нужно закончить. В [3,4,5] такая инструкция соответствует формальному определению управляемого LTS-теста, который однозначно определяет тестирование (без лишнего недетерминизма). Реализация проходит тест, если её тестирование всегда заканчивается с вердиктом pass. Реализация проходит набор тестов, если она проходит каждый тест из набора. Набор тестов значимый, если каждая конформная реализация его проходит; исчерпывающий, если каждая неконформная реализация его не проходит; полный, если он значимый и исчерпывающий. Задача заключается в генерации полного набора тестов по спецификации. Полный набор тестов всегда существует, в частности, им является набор всех примитивных тестов. Такой тест строится по одной выделенной безопасной R-трассе спецификации. Для этого в трассу вставляются кнопки, которые нужно нажимать: перед каждым отказом R вставляется кнопка R, а перед каждым действием z – какая-нибудь безопасная (после префикса трассы) кнопка P, разрешающая действие z. Безопасность трассы гарантирует безопасность кнопки R и наличие такой безопасной кнопки P. Выбор кнопки P может быть неоднозначным: по одной безопасной трассе спецификации можно сгенерировать, вообще говоря, несколько разных примитивных тестов. Если наблюдение, полученное после нажатия кнопки, продолжает трассу, тест продолжается. Последнее в трассе наблюдение и любое наблюдение, «ведущее в сторону», всегда заканчивают тестирование. Вердикт pass выносится, если полученная R-трасса есть в спецификации, а вердикт fail – если нет. Такие вердикты соответствуют строгим тестам, которые, во-первых, значимые (не ловят ложных ошибок) и, во-вторых, не пропускают обнаруженных ошибок. Любой строгий тест сводится к 197

некоторому множеству примитивных тестов, которые обнаруживают те же самые ошибки.

3. Преобразование кнопок и наблюдений 3.1. Медиатор семантик В теории конформности предполагается, что реализация и спецификация заданы в одной R-семантике. Однако на практике обычно требуется некоторое преобразование спецификационных тестовых воздействий в реализационные тестовые воздействия и обратное преобразование реализационных наблюдений в спецификационные наблюдения. Программа, осуществляющая эти преобразования, называется медиатором. По сути, это означает, что реализация может быть задана в другой тестовой семантике – R`-семантике, и медиатор осуществляет преобразование семантик. В простейшем случае различие семантик только в разных способах представления одних и тех же действий в реализации и спецификации. Достаточно взаимно-однозначного преобразования алфавитов реализации и спецификации. В общем случае такого преобразования недостаточно, поскольку спецификация, как правило, определяется на более высоком уровне абстракции. Рассмотрим несколько примеров. 1. Передача сообщений. В спецификации может быть определена операция (кнопка) send(m) передачи сообщения m, а в реализации – send(m,i) с указанием дополнительного параметра i – номера одного из нескольких выходных портов. На уровне спецификации тест принимает любое сообщение, и отказ означает отсутствие сообщений. На уровне реализации тест может принимать сообщение только из одного порта, и для наблюдения спецификационного отказа нужно выполнить прием по каждому порту и убедиться, что ни по одному из них сообщений нет. В этом примере одной спецификационной кнопке send(m) соответствует множествен реализационных кнопок send(m,i), каждую из которых нужно нажать в том же самом состоянии реализации для того, чтобы при полном тестировании осуществить требуемое спецификационное тестовое воздействие для всех возможных ситуаций. Поскольку отказ не меняет состояния, последовательность отказов по всем портам гарантированно означает спецификационный отказ для того же самого состояния реализации. Однако, если из некоторого порта сообщение принимается, то состояние реализации меняется и прием из другого порта можно будет сделать только тогда, когда реализация снова окажется в том же состоянии, а тест объявит прием сообщений. Таким образом медиаторное преобразование, во-первых, адаптивно, то есть реализационные тестовые воздействия зависят от полученных реализационных наблюдений (сообщение или отказ), и, вовторых, зависит от состояния реализации, в котором оно начинает выполняться. 198

2. Пул элементов с операциями alloc и dealloc. В спецификации пула может быть определена операция dealloc без параметров, понимаемая как освобождение любого ранее занятого элемента пула, в то время как в реализации эта операция требует в качестве параметра указать конкретный освобождаемый элемент dealloc(i). Будем предполагать, что реализация удовлетворяет следующей реализационной гипотезе: все состояния пула, соответствующие одному и тому же множеству занятых элементов, эквивалентны. Здесь аналогично предыдущему примеру одной спецификационной кнопке dealloc соответствует множество (по числу занятых элементов) реализационных кнопок dealloc(i), каждую из которых нужно нажать хотя бы в одном состоянии реализации, соответствующем данному множеству занятых атомов. Здесь есть два отличия от предыдущего примера. 1) Медиаторное преобразование не адаптивно, точнее, от наблюдений (выполнение dealloc(i) или отказ) зависит только соответствующее спецификационное наблюдение, возвращаемое в тест, но не последующие реализационные тестовые воздействия: для каждого нажатия кнопки dealloc выполняется только одно нажатие одной кнопки dealloc(i). 2) Преобразование зависит от множества занятых элементов, вычисляемого по предыстории взаимодействия. По реализационной гипотезе, зависимость от реализационного состояния можно не учитывать, поскольку состояния с одним множеством занятых элементов эквивалентны. 3. Стационарное тестирование. Спецификация описывает конечный автомат, каждый переход которого помечен парой (стимул x∈X, реакция y∈Y); спецификационная кнопка P(x)={(x,y)|y∈Y} означает посылку стимула x и прием любой реакции. Реализация представляет собой LTS, каждый внешний переход которой помечен либо стимулом x∈X, либо реакцией y`∈Y`; реализационные кнопки: P`(x)={x}, означающая посылку стимула x, и P`=Y`, означающая прием любой реализационной реакции. Медиатор посылает стимул x и либо возвращает отказ, если наблюдается отказ, либо принимает реакции до тех пор, пока они поступают от реализации, а затем для полученной (быть может, пустой) последовательности y`1,…,y`n реализационных реакций выдает спецификационную реакцию y=f(y`1,…,y`n). Функция f как раз и определяет медиаторное преобразование. Тестирование через такой медиатор иногда называют стационарным тестированием, поскольку стимулы подаются только в стационарных состояниях реализации, то есть в состояниях, в которых нет реакций [2,7]. Здесь спецификационной кнопке соответствует последовательность реализационных тестовых воздействий, в процессе выполнения которой состояние реализации меняется, но, в отличие от первого примера, нас интересует состояние только в конце последовательности, соответствующее полному выполнению спецификационного тестового 199

воздействия. Преобразование адаптивно, но не зависит от реализационных состояний. В общем случае медиатор может оказаться довольно сложной программой, осуществляющей медиативные функции между реализацией в R`-семантике и тестом, генерируемым по спецификации в R-семантике. Медиатор компонуется с тестом; результат такой композиции рассматривается как тест в R`-семантике, который взаимодействует напрямую с реализацией. Тестирование через медиатор похоже на тестирование в контексте (асинхронное тестирование) [4,5,8,10,13]. Там тоже тест взаимодействует с реализацией не напрямую, а через промежуточную среду взаимодействия. Отличие в том, что при асинхронном тестировании спецификация задаётся в той же семантике, что и реализация. Проблема заключается в том, что тесты, генерируемые по исходной спецификации, при асинхронном тестировании могут обнаруживать ложные ошибки (не обнаруживаемые при синхронном тестировании, когда тест и реализация взаимодействуют напрямую). Для решения этой проблемы спецификация монотонно преобразуется (с сохранением класса конформных и не сужением класса безопасных реализаций) и компонуется с известной средой передачи. По этой композиции и генерируются тесты. В отличие от этого при тестировании через медиатор тест генерируется по исходной спецификации, семантика которой отлична от семантики реализации, и компонуется с медиатором, в результате чего получается тест в семантике реализации. Тестирование через медиатор также похоже на тестирование по факторспецификации [1]. Идея факторизации заключается в том, что на исходной LTS-спецификации, заданной в реализационной семантике, вводятся отношения эквивалентности состояний и переходов, которые индуцируют фактор-LTS: фактор-состояние – это класс эквивалентности состояний, а фактор-переход – это множество эквивалентных переходов, имеющих эквивалентные начальные состояния и эквивалентные конечные состояния. Действие, которым помечен фактор-переход – это класс эквивалентности переходов. Для фактор-спецификации определяется фактор-семантика, которая может быть любой, но должна быть согласована с реализационной семантикой и эквивалентностью переходов. В исходной спецификации для данного состояния фактор-кнопка определяет множество переходов, начинающихся в этом состоянии и отображаемых в фактор-действия, принадлежащие этой фактор-кнопке. Требуется, чтобы это множество переходов совпадало с множество переходов из этого состояния, разрешаемых некоторым множеством реализационных кнопок. Нажатие фактор-кнопки транслируется в нажатие одной из этих реализационных кнопок. Это согласование является частным случаем соотношения спецификационных и реализационных кнопок при тестировании через медиатор, как в первых двух примерах, приведенных выше. Существенное различие в цели тестирования. Факторизация преследует цель сократить время тестирования, основываясь на следующей реализационной гипотезе: если реализация ведет себя правильно 200

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

3.2. Устройство теста и медиатора При взаимодействии теста непосредственно с реализацией нажимаются реализационные кнопки и получаются реализационные наблюдения. При тестировании через медиатор с реализацией аналогичным образом взаимодействует медиатор, а интерфейс медиатора и теста будет уже другой. Работа теста, генерируемого по спецификации в R-семантике, – это последовательность пар «тестовое воздействие (кнопка P∈R), получение наблюдения a∈P или a=P». В медиаторе этой паре соответствует тройка «получение кнопки P∈R, взаимодействие с реализацией в R`-семантике, выдача наблюдения a». Взаимодействие медиатора с реализацией аналогично взаимодействию теста и реализации в одной R`-семантике. Но есть два отличия. 1) Вместо вынесения вердикта выдается спецификационное наблюдение. 2) Такое взаимодействие начинается после приема той или иной спецификационной кнопки. В медиаторе выделяются состояния трех типов. В состоянии 1-го типа принимаются спецификационные кнопки, причем медиатор должен быть готов принять любую такую кнопку. После приема кнопки медиатор осуществляет взаимодействие с реализацией в состояниях 2-го типа, которое за конечное число шагов должно заканчиваться переходом в состояние 3-го типа. Там выдается спецификационное наблюдение с переходом в состояние 1-го типа. Мы будем записывать σ`/M(P)=a/λ, если после прохождения в процессе тестирования реализационной трассы σ`, тест обращается к медиатору с кнопкой P, реализация взаимодействует с медиатором, проходя трассу λ, после чего медиатор возвращает тесту наблюдение a. Медиатор формально можно задать в виде отображения M:R×N`*→P (N`*×N), где N=L∪R множество наблюдений в R-семантике, с тем ограничением, что после нажатия кнопки может наблюдаться только разрешаемое ею действие или отказ: ∀P∈R ∀σ`∈N`* ∀(λ,a)∈M(P,σ`) a∈P∪{P}. Кроме этого медиатор (как и реализационный тест) должен быть готов получить любое 201

наблюдение от реализации, которое может быть после нажатия реализационной кнопки. Это означает, что замыкание по взятию префикса множества трасс λ, генерируемое отображением M(P,σ`), ветвится в каждой точке по всем наблюдениям, соответствующим некоторой реализационной кнопке. В общем случае медиаторное преобразование может зависеть от реализационного состояния или функции от него. Если такой зависимости нет, достаточно иметь одно состояние 1-го типа. Зависимость от состояния выражается в наличии нескольких состояний 1-го типа. При этом одному состоянию 1-го типа может соответствовать, вообще говоря, множество эквивалентных состояний. Если медиатор зависит от реализационного состояния, то, прежде всего, должна быть возможность опросить это состояние. Тестирование с такой возможностью называется тестированием с открытым состоянием [2,6,11]. Предполагается, что опрос состояния достоверен, то есть в каждом состоянии возвращает именно это состояние. Это можно понимать как добавление кнопки опроса состояния P0` (множества возможных состояний реализации) к R`. Алфавит реализации расширяется её состояниями. В каждом состоянии i реализации добавляется переход-петля по опросу состояния i⎯ i→ i. Тогда зависимость медиаторного преобразования от состояния сводится к адаптивности, то есть зависимости от наблюдений. При тестировании с открытым состоянием при некоторых дополнительных ограничениях на реализацию появляется возможность полного тестирования за конечное время. Для этого нужно, чтобы тест также мог опросить состояние реализации, используя для этой цели обращение к медиатору с опросом состояния, которому мы поставим в соответствие спецификационную кнопку «опрос реализационного состояния», также обозначаемую как P0`. В некоторых случаях (пример с пулом) вместо реализационного состояния медиатор сообщает тесту некоторое обобщенное состояние как функцию от реализационного состояния, но вычисляемую по предыстории взаимодействия (множество занятых элементов). Тестирование также может быть полным, если выполнена реализационная гипотеза об эквивалентности реализационных состояний, соответствующих одному обобщенному. Если эта гипотеза справедлива, опрос состояния реализации не требуется.

3.3. Гипотеза о безопасности и конформность Медиаторное отображение M генерирует отображение трасс * * T:N →P (N` ), дающее то множество реализационных трасс, которые могут быть получены при прохождении данной спецификационной трассы. Оно определяется следующими правилами: 1) T(ε)={ε}, 202

2) ∀σ∈N* ∀a∈N T(σ⋅〈a〉)={σ`⋅λ|σ`∈T(σ) & ∃P∈R(λ,a)∈M(P,σ`)}. На основе отображения трасс переопределим гипотезу о безопасности и конформность для тестирования через медиатор.

При генерации трасс учитывается опрос состояния T:K*→P (K`*), где K=N×VS, K`=N`×VI: 1) T(ε)={ε},

I safe for S  (〈γ〉∉F(S) ⇒ 〈γ〉∉F(I)) & ∀σ∈Safe(S)

2) ∀σ∈K* ∀a∈N T(σ⋅〈a〉)={σ`⋅λ|σ`∈T(σ) & ∃P∈R (λ,a)∈M(P,σ`)},

∀σ`∈T(σ)∩I ∀P∈R ∀(λ,a)∈M(P,σ`) (P safe S after σ ⇒ σ`⋅λ∈Safe(I)).

3) ∀σ∈K* ∀s∈VS T(σ⋅〈s〉)={σ`⋅〈i〉|σ`∈T(σ) & s=M0(i)}.

I saco S  I safe for S & ∀σ∈Safe(S) ∀σ`∈T(σ)∩I ∀P∈R ∀(λ,a)∈M(P,σ`) (P safe S after σ ⇒ a∈obs(S after σ,P)).

Опрос состояния безопасен в состоянии, которое не дивергентно и из которого не достижимы по τ-переходам состояния с γ-переходами. Соответственно, гипотеза о безопасности определяется так: I safe for S  (〈γ〉∉F(S) ⇒ 〈γ〉∉F(I)) & ∀σ∈Safe(S)

4. Преобразование состояний Кроме кнопок и действий, медиатор может преобразовывать также и состояния: из реализационного в спецификационное. Это означает, что на множестве состояний реализации предполагается заданным отношение эквивалентности, и состояние спецификации соответствует классу эквивалентных состояний реализации. В отличие от факторизации это соответствие является не предусловием тестирования (реализационной гипотезой), а частью проверяемого условия. Правда, эта проверка выполняется косвенным образом: если состояние реализации на самом деле не соответствует состоянию спецификации, в которое оно преобразуется медиатором, то это проявится после нажатия в этом состоянии реализации некоторой спецификационной кнопки как спецификационное наблюдение, отсутствующее в спецификации. Преобразование состояния осуществляется медиатором в ответ на дополнительную спецификационную кнопку «опрос спецификационного состояния» P0, добавляемую к семейству R. Алфавит спецификации расширяется её состояниями. В каждом состоянии s спецификации добавляется переход-петля по опросу состояния s⎯ s→ s. Медиаторное отображение, гипотеза о безопасности и конформность в измененной семантике определяются как обычно. Опишем, как это выглядит в терминах исходной семантики с учетом того, что трассы теперь содержат состояния, как особые наблюдения, а в спецификации и реализации добавлены переходыпетли по состояниям. Обращение к медиатору для опроса спецификационного состояния будем записывать как M0()=s. Медиатор задает отображение M0:VI→VS, где VI и VS множества состояний реализации I и спецификации S, соответственно1.

∀σ`∈T(σ)∩I ∀P∈R ∀(λ,a)∈M(P,σ`) (P safe S after σ ⇒ σ`⋅λ∈Safe(I)) & (P0 safe S after σ ⇒ P0` safe I after σ`). Если после безопасной трассы спецификации опрос состояния P0 безопасен, то состояние, возвращаемое медиатором, должно быть одним из состояний спецификации после этой трассы. Соответственно, конформность модифицируется так: I saco S  I safe for S & ∀σ∈Safe(S) ∀σ`∈T(σ)∩I ∀P∈R ∀(λ,a)∈M(P,σ`) (P safe S after σ ⇒ a∈obs(S after σ,P)) & ∀i∈(I after σ`) (P0 safe S after σ ⇒ M0(i)∈(S after σ)). Такая конформность похожа на слабую симуляцию [9,12], которая определяется как соответствие r⊆der(I)×der(S) достижимых состояний реализации и спецификации2, удовлетворяющее требованию: (i0,s0)∈r & ∀(i,s)∈r ∀σ∈L* ∀i` (i= σ⇒ i` ⇒ ∃s` s= σ⇒ s` & (i`,s`)∈r), где i= σ⇒ i` означает, что состояние i` достижимо из состояния i по трассе σ: существует маршрут, начинающийся в i, заканчивающийся в i` и имеющий трассу σ. Наша конформность имеет три существенных отличия от слабой симуляции. 1) Отказы: в нашем случае рассматриваются трассы с отказами, то есть не в алфавите L*, а в расширенном алфавите N*. Это предъявляет более жесткие требования к реализации. 2) Безопасность: в нашем случае рассматриваются не любые трассы, а только те, которые безопасны в спецификации, и не любые достижимые состояния, а только те, которые достижимы по безопасным трассам спецификации. Это позволяет не учитывать состояния и трассы реализации, которые опасны в спецификации. 3) Медиатор: трассы в

1

В случае обобщенного состояния вместо VI используется множество обобщенных состояний.

2

203

der(I) {i|∃μ i∈(I after μ)}. 204

реализации и спецификации не обязательно совпадают, хотя и связаны медиаторным отображением. Это позволяет рассматривать реализацию и спецификацию в разных семантиках (в том числе, в разных алфавитах) при наличии соответствующего медиатора. Кроме того, в нашем случае соответствие состояний – это всегда отображение VI→VS, то есть одному реализационному состоянию соответствует только одно спецификационное состояние. До сих пор мы предполагали, что в тесте опрос спецификационного состояния M0()=s необязателен: спецификационная трасса может как включать, так и не включать начальное состояние и состояние после того или иного наблюдения. Возможен вариант тестирования с жестким требованием опроса спецификационного состояния в начале тестирования и после каждого наблюдения. Если в безопасную трассу с необязательными состояниями добавить состояния в недостающих местах, то полученная трасса, очевидно, тоже безопасна. Отсюда легко показывается, что при переходе к тестированию с обязательным опросом состояния класс конформных реализаций сохраняется, а класс безопасных реализаций не сужается. Однако класс безопасных реализаций может расшириться, что показывается примером на Рис. 1.

S

0

x

1

y

2

I

a

x

b

y

c

γ

R=R`={{x},{y}}, S – спецификация, I – реализация, ∀P∈R ∀σ`∈N`* M(P,σ`)={(〈a〉,a)|a∈P∪{P}}, ∀i∈VI M0(i)=0.

Ограниченность сильно-связна3 и ограниченно недетерминирована. недетерминизма означает, что существует такое число t (степень недетерминизма), что в любом состоянии i реализации после t нажатий любой кнопки P будут получены все возможные пары (наблюдение a∈P∪{P}, постсостояние i`). При t=1 реализация детерминирована. При тестировании через медиатор алгоритм полного тестирования, описанный в [6], практически не меняется, кроме того, что тестовые воздействия и наблюдения выполняются через обращение к медиатору. Более существенные отличия касаются степени недетерминизма t. Во-первых, спецификационной кнопке P соответствует адаптивная последовательность реализационных кнопок P`i1,…,P`in , зависящая в i

общем случае как от реализационных наблюдений, так и от реализационных состояний. Поэтому, если t` – это степень недетерминизма каждой реализационной кнопки P`ij, то степень недетерминизма t спецификационной кнопки P вычисляется как максимум из tni. Число t, вообще говоря, зависит от кнопки P, причем эта зависимость известна лишь медиатору. Для того, чтобы использовать общую степень недетерминизма для всех спецификационных кнопок, пришлось бы брать максимум из t по всем кнопкам P. Понятно, что при таком тестировании мы будем делать много лишних нажатий спецификационных кнопок. Вместо этого медиатор мог бы вычислять степень недетерминизма t отдельно для каждой спецификационной кнопки и каждого реализационного состояния, в котором она нажимается. Более того, для разных последовательностей P`i1,…,P`in i

Рис. 1. Опасная реализация становится безопасной при переходе к обязательному опросу спецификационного состояния.

5. Полное тестирование с открытым состоянием ограниченно недетерминированных систем Когда семантики реализации и спецификации совпадают, полное тестирование с открытым состоянием удается закончить за конечное время, если выполнены следующие ограничения [6]. 1) Ограничения на семантику: число кнопок конечно и задан алгоритм разрешения кнопки относительно всех действий (в частности, все кнопки конечны). 2) Ограничения на спецификацию: LTS-спецификация конечна (конечно число достижимых состояний и переходов). 3) Ограничения на реализацию: реализация конечна,

число t могло бы быть разным, то есть зависящим от длины последовательности ni. Вместо того, чтобы передавать тесту вычисленное значение числа t, медиатору достаточно просто сообщить, нужно или не нужно еще раз нажимать эту спецификационную кнопку в этом реализационном состоянии. Во-вторых, степень недетерминизма зависит от семантики тестового взаимодействия. В примере с передачей сообщений через выходные порты реализация детерминирована в реализационной семантике, где каждому порту соответствует отдельная кнопка, если в каждом своем состоянии i она выдает не более одного сообщения в каждый порт j, а постсостояние однозначно определяется парой (i,j). Однако, если реализация выдает сообщения по нескольким портам, она недетерминирована в спецификационной семантике, где кнопка соответствует всем портам в 3

205

Из каждого состояния, достижимого из начального состояния, достижимо начальное состояние. 206

совокупности. Чтобы получить все возможные наблюдения, мы должны нажимать спецификационную кнопку приема сообщений n раз, если реализация выдает сообщения по n>0 портам, или 1 раз, если n=0. Медиаторное отображение теперь имеет вид M:R×N`*→P (N`*×N×Bool). Тест через медиатор опрашивает реализационное состояние σ`/M(P0`)=(i,false)/〈i〉, после чего с нужной кнопкой P обращается к медиатору σ`⋅〈i〉/M(P)=(a,Press)/λ и во втором выходном параметре узнает, нужно (Press=true) или не нужно (Press=false) еще раз нажимать кнопку P в том же реализационном состоянии i. Алгоритм тестирования в [6] строил LTS, состояниями которой являются достигнутые состояния реализации. С реализационным состоянием i связывалось семейство S(i) множеств вида S after σ, где σ∈Safe(S) и i∈(I after σ). При тестировании через медиатор i∈(I after σ`), где σ`∈T(σ)∩I. Эта связь используется в блоке «Распространение», который осуществляет верификацию не только наблюдений, полученные после реальных спецификационных трасс, пройденных при тестировании, но и возможных наблюдений после потенциальных трасс. Если после спецификационной трассы σ1 мы попадаем в реализационное состояние i, в котором мы уже были после трассы σ2, то есть (S after σ2)∈S(i), то все наблюдения уже полученные в состоянии i после σ2, могут быть в реализации и после трассы σ1. Такие наблюдения достаточно верифицировать аналитически. Это даёт существенную экономию числа тестовых воздействий, необходимых для проверки конформности: мы выполняем множество проверок без реального тестирования, основываясь на полученном знании о поведении реализации. Если медиатор осуществляет преобразование состояний M0:VI→VS, то с каждым реализационным состоянием i связано ровно одно спецификационное состояние M0(i). Поэтому блок «Распространение» больше не нужен. Это не означает, что вместо всех аналитических проверок нам теперь нужно выполнять столько же шагов реального тестирования. Различие в том, что конформность с преобразованием состояний предъявляет к реализации более жесткие требования: правильным должно быть не только наблюдение, но и постсостояние. Без преобразования состояний правильность постсостояний могла проверяться лишь косвенно: если постсостояние неправильное, то рано или поздно это скажется на неправильных наблюдениях в нем. Теперь мы делаем эту проверку напрямую.

[2] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Асинхронные автоматы: классификация и тестирование. Труды ИСП РАН, т. 4, 2003. [3] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Формализация тестового эксперимента. «Программирование», 2007, No. 5. [4] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушением. «Наука», 2008. [5] Бурдонов И.Б. Теория конформности для функционального тестирования программных систем на основе формальных моделей. Диссертация на соискание учёной степени д.ф.-м.н., Москва, 2008. [6] http://www.ispras.ru/~RedVerst/RedVerst/Publications/TR-01-2007.pdf [7] Бурдонов И.Б., Косачев А.С. Полное тестирование с открытым состоянием ограниченно недетерминированных систем. Настоящий сборник. [8] Г.В.Ключников, А.С.Косачев, Н.В.Пакулин, А.К.Петренко, В.З.Шнитман. Применение формальных методов для тестирования реализации IPv6. Труды Института системного программирования РАН, N 4, 2003. стр.121-140. [9] van der Bijl M., Rensink A., Tretmans J. Compositional testing with ioco. Formal Approaches to Software Testing: Third International Workshop, FATES 2003, Montreal, Quebec, Canada, October 6th, 2003. Editors: Alexandre Petrenko, Andreas Ulrich ISBN: 3-540-20894-1. LNCS volume 2931, Springer, pp. 86-100. [10] van Glabbeek R.J. The linear time - branching time spectrum II; the semantics of sequential processes with silent moves. Proceedings CONCUR ’93, Hildesheim, Germany, August 1993 (E. Best, ed.), LNCS 715, Springer-Verlag, 1993, pp. 66-81. [11] Jard C., Jéron T., Tanguy L., Viho C. Remote testing can be as powerful as local testing. In Formal methods for protocol engineering and distributed systems, FORTE XII/ PSTV XIX’ 99, Beijing, China, J. Wu, S. Chanson, Q. Gao (eds.), pp. 25-40, October 1999. [12] Lee D., Yannakakis M. Principles and Methods of Testing Finite State Machines – A Survey. Proceedings of the IEEE 84, No. 8, 1090–1123, 1996. [13] Milner R. Lectures on a calculus for communicating systems. Seminar on Concurrency, LNCS 197, Springer-Verlag, pp. 197-220. [14] Revised Working Draft on “Framework: Formal Methods in Conformance Testing”. JTC1/SC21/WG1/Project 54/1 // ISO Interim Meeting / ITU-T on, Paris, 1995.

Литература [1] Бурдонов И.Б., Косачев А.С., Кулямин В.В. Использование конечных автоматов для тестирования программ. «Программирование». 2000. No. 2.

207

208