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

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

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

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

Организация тестирования

Тестирование осуществляется на заданном заранее множестве входных данных X и множестве предполагаемых результатов Y – (X,Y), которые задают график желаемой функции. Кроме того, зафиксирована процедура Оракул (oracle), которая определяет, соответствуют ли выходные данные – Yв (вычисленные по входным данным – X) желаемым результатам – Y, т.е. принадлежит ли каждая вычисленная точка (x,yв) графику желаемой функции (X,Y).
Оракул дает заключение о факте появления неправильной пары (x,yв) и ничего не говорит о том, каким образом она была вычислена или каков правильный алгоритм – он только сравнивает вычисленные и желаемые результаты. Оракулом может быть даже Заказчик или программист, производящий соответствующие вычисления в уме, поскольку Оракулу нужен какой-либо альтернативный способ получения функции (X,Y) для вычисления эталонных значений Y.
Пример сравнения словесного описания пункта спецификации с результатом выполнения фрагмента кода
Пункт спецификации: «Метод Power должен принимать входные параметры: x – целое число, возводимое в степень, и n – неотрицательный порядок степени. Метод должен возвращать вычисленное значение xn».
Выполняем метод со следующими параметрами: Power(2,2)
Проверка результата выполнения возможна, когда результат вычисления заранее известен – 4. Если результат выполнения 22 = 4, то он соответствует спецификации.
В процессе тестирования Оракул последовательно получает элементы множества (X,Y) и соответствующие им результаты вычислений (X,Yв) для идентификации фактов несовпадений (test incident).
При выявлении (x,yв)(X,Y) запускается процедура исправления ошибки, которая заключается во внимательном анализе (просмотре) протокола промежуточных вычислений, приведших к (x,yв), с помощью следующих методов:

for (int i=1;n>=i;i++)
<
z = z*x;
Console.WriteLine(«i = <0>z = <1>«,
i, z);
>
return z;
>
Пример 2.3. Исходный текст метода Power со вставкой оператора протоколирования
double Power(double x, int n)
<
double z=1;
int i;
for (i=1;n>=i;i++)
<
z = z*x;
printf(«i = %d z = %f\n»,i,z);
>
return z;
>
Пример 2.3.1. Исходный текст метода Power со вставкой оператора протоколирования

Пример пошагового выполнения программы
При пошаговом выполнении программы код выполняется строчка за строчкой. В среде Microsoft Visual Studio.NET возможны следующие команды пошагового выполнения:

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

Пример выполнения программы с заказанными контрольными точками и анализом трасс и дампов

Например: наусловно изображен управляющий граф некоторой программы. Трасса, проходящая через вершины 0-1-3-4-5 зафиксирована в. Строки таблицы отображают вершины управляющего графа программы, или breakpoints, в которых фиксировались текущие значения заказанных пользователем переменных.

Источник

Реферат по теме выпускной работы

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

Цели и задачи, которые должны решаться.

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

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

Актуальность темы работы

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

Задачи тестирования основаны на следующих постулатах тестирования ПО:

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

Текущие результаты исследований.

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

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

Рисунок 1 – Управляющий граф программы

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

Рисунок 2 – Конечный расширенный автомат (анимация: 7 кадров, 6 Кб, 7 циклов)

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

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

(1)

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

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

(2)
где m– число шагов в пути, m=n*3, здесь n– число переходов в пути;
f_i– расстояние до условия для i-го шага.
d_i– вес i-го с шага, d_i=(m-i) 2

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

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

Источник

Управляющий граф

Управляющий граф (Control flow graph, Flow graph) — основная модель программы, представляющая в виде орграфа поток управления (систему управляющих связей) в программе; в ней сохраняется только членение программы на операторы (команды, лучи), а также информация о тождественности операторов и возможных передачах управления между операторами.

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

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

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

Источник

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

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

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

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

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

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

Алгоритм А

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

А₂. В графе программы ищется структурированная конструкция. Если такой нет, то выполняется переход к шагу А₄.

А₃. В дереве образуется вершина структурированной конструкции. Эта конструкция сворачивается в вершину, тип которой указывается. Выполняется переход к шагу А₂.

А₄. Если в графе осталась только одна вершина, то работа алгоритма заканчивается.

А₅. В графе выделяется неструктурируемая конструкция и в структурном дереве образуется вершина соответствующего типа. Конструкция в графе сворачивается, после чего выполняется переход к шагу А₂.

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

Источник

Граф потока управления

Граф потока управления (англ. control flow graph, CFG ) — в теории компиляции — множество всех возможных путей исполнения программы, представленное в виде графa.

Содержание

Обзор

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

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

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

Терминология

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

entry block — входной блок, стартовый блок узел, с которого начинается любой путь exit block — выходной блок узел, на котором завершаются все пути back edge — обратная дуга дуга, указывающая на предка, то есть узел, который бы был пройден раньше в процессе обхода графа в глубину critical edge — критическая дуга an edge which is neither the only edge leaving its source block, nor the only edge entering its destination block. These edges must be split (a new block must be created in the middle of the edge) in order to insert computations on the edge without affecting any other edges. abnormal edge — аномальная дуга дуга с неизвестным назначением. Могут появляться, например, после преобразования конструкций обработки исключений. Эти дуги препятствуют оптимизациям. impossible edge — невозможная дуга (иногда называется ложная дуга) дуга, добавленная в граф исключительно для того, чтобы сохранить свойство графа о постдоминировании выходным узлом любого другого узла. Эта дуга не может быть пройдена. dominator — доминатор узел M доминирует над узлом N, если любой путь, достигающий N обязан предварительно пройти блок M. Входной узел доминирует над всеми остальными узлами графа. postdominator — постдоминатор узел M постдоминирует над узлом N, если любой путь от N к выходному блоку обязан пройти через узел M. Выходной узел постдоминирует все узлы графа. en:Lengauer-Tarjan’s algorithm. postdominator tree — дерево постдоминаторов Аналог дерева доминаторов. Его корнем является выходной блок. loop header — заголовок цикла Иногда называется точкой входа цикла — доминатор, который является назначением обратных дуг, образующих цикл. Доминирует над всеми узлами тела цикла. loop pre-header — предзаголовок цикла Предположим, что блок M — доминатор с несколькими входными дугами, некоторые из которых являются обратными (таким образом, M — заголовок цикла). Для некоторых фаз оптимизации выгодно, чтобы блок M был разделен на два блока, M_pre и M_loop. Содержимое M и обратные дуги переносится в M_loop, остальные дуги переносятся на M_pre, и создается новая дуга от M_pre к M_loop (таким образом, M_pre стал непосредственным доминатором M_loop). Сразу после преобразования M_pre будет пустым, но оптимизации вроде выноса инвариантов (en:loop-invariant code motion) могут пополнить его. M_pre называется предзаголовком цикла, а M_loop стал заголовком цикла.

Примеры

Для фрагмента кода:

Источник