Программа нарезки - Program slicing

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

Техника нарезки быстро развивалась с момента первоначального определения Марком Вейзером . Сначала нарезка была только статической, т. Е. Применялась к исходному коду без какой-либо другой информации, кроме исходного кода. Богдан Корел и Януш Ласки представили динамическое нарезание , которое работает на конкретном выполнении программы (для данной трассировки выполнения). Существуют и другие формы нарезки, например нарезка пути.

Статическая нарезка

Основываясь на исходном определении Вайзера, неформально статический программный фрагмент S состоит из всех операторов в программе P, которые могут влиять на значение переменной v в операторе x. Срез определяется для критерия среза C = (x, v), где x - это инструкция в программе P, а v - переменная в x. Статический срез включает все операторы, которые могут влиять на значение переменной v в операторе x для любого возможного ввода. Статические срезы вычисляются путем отслеживания зависимостей между операторами. Более конкретно, чтобы вычислить статический срез для (x, v), мы сначала находим все операторы, которые могут напрямую влиять на значение v, прежде чем встретится оператор x. Рекурсивно, для каждого оператора y, который может повлиять на значение v в операторе x, мы вычисляем срезы для всех переменных z в y, которые влияют на значение v. Объединение всех этих срезов является статическим срезом для (x, v) .

пример

Например, рассмотрим приведенную ниже программу C. Давайте вычислим срез для (запись (сумма), сумма). На значение суммы напрямую влияют утверждения «sum = sum + i + w», если N> 1, и «int sum = 0», если N <= 1. Итак, slice (write (sum), sum) - это объединение трех срезов и оператора int sum = 0, который не имеет зависимостей:

срез (сумма = сумма + я + ш, сумма)
срез (сумма = сумма + я + ш, я)
срез (сумма = сумма + я + ш, ш)
{int sum = 0}.

Довольно легко увидеть, что slice (sum = sum + i + w, sum) состоит из «sum = sum + i + w» и «int sum = 0», потому что это единственные два предшествующих утверждения, которые могут повлиять на значение суммы в «сумма = сумма + я + ш». Аналогично, slice (sum = sum + i + w, i) содержит только «for (i = 1; i <N; ++ i) {», а slice (sum = sum + i + w, w) содержит только оператор «int w = 7».

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

int i;
int sum = 0;
int product = 1;
int w = 7;
for(i = 1; i < N; ++i) {
  sum = sum + i + w;
  product = product * i;
}
write(sum);
write(product);

Статический исполняемый фрагмент для критериев ( write(sum), сумма) - это новая программа, показанная ниже.

int i;
int sum = 0;
int w = 7;
for(i = 1; i < N; ++i) {
  sum = sum + i + w;

}
write(sum);

Фактически, большинство техник статической нарезки, включая собственную технику Вайзера, также удаляют write(sum)оператор. Поскольку в заявлении write(sum)значение sumне зависит от самого утверждения. Часто срез для конкретного оператора x будет включать более одной переменной. Если V - это набор переменных в операторе x, то срез для (x, V) - это объединение всех срезов с критериями (x, v), где v - переменная в множестве V.

Упрощенный подход к статической нарезке вперед

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

Динамическая нарезка

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

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

Смотрите также

Сопровождение программного обеспечения
Анализ зависимости
Достижение определения
Зависимость от данных
Frama-C Инструмент , который реализует алгоритмы нарезки на программы C .
Частичное устранение мертвого кода

Ноты

Ссылки

Марк Вайзер . «Программа нарезки». Труды 5-й Международной конференции по разработке программного обеспечения, страницы 439–449, IEEE Computer Society Press, март 1981 г.
Марк Вайзер . «Программа нарезки». IEEE Transactions on Software Engineering, Volume 10, Issue 4, pages 352–357, IEEE Computer Society Press, июль 1984 г.
Сьюзан Хорвиц , Томас Репс и Дэвид Бинкли, Межпроцедурные срезы с использованием графов зависимостей, ACM Transactions on Programming Languages and Systems, Volume 12, Issue 1, pages 26-60, January 1990.
Фрэнк Тип. «Обзор методов нарезки программ». Журнал языков программирования, том 3, выпуск 3, страницы 121–189, сентябрь 1995 г.
Дэвид Бинкли и Кейт Брайан Галлахер. «Программа нарезки». Достижения в области компьютеров, том 43, страницы 1–50, Academic Press , 1996.
Андреа де Люсия. «Нарезка программ: методы и приложения», Международный семинар по анализу исходного кода и манипуляциям, страницы 142–149, 2001, IEEE Computer Society Press.
Марк Харман и Роберт Хиеронс. «Обзор программной нарезки», Software Focus, Volume 2, Issue 3, страницы 85–92, январь 2001 г.
Дэвид Бинкли и Марк Харман. «Обзор эмпирических результатов нарезки программ», Advances in Computers, Том 62, страницы 105-178, Academic Press , 2004.
Йенс Кринке. «Program Slicing», В Справочнике по разработке программного обеспечения и инженерии знаний, Том 3: Последние достижения. World Scientific Publishing , 2005 г.
Сильва, Жозеп. «Словарь методов, основанных на нарезке программ», ACM Computing Surveys, том 44, выпуск 3, Association for Computing Machinery , июнь 2012 г.
Alomari HW et al. «srcSlice: очень эффективный и масштабируемый прямой статический срез». Wiley Journal of Software: Evolution and Process ( JSEP ), DOI: 10.1002 / smr.1651, Vol. 26, No. 11, pp. 931-961, 2014.

Languages

In other projects