Цель работы - разработка комплекса инструментальных средств для автоматизации анализа и упрощения понимания поведения кода программных систем. Предложены методы трансляции, абстракции, отладки и построения тестов для языка Кобол. Разработана экспериментальная система, реализующая предложенные методы. Ключевые слова: трансляция, Кобол, моделирование, абстракция, генерация тестов, отладка. Мета роботи - розробка комплексу інструментальних засобів для автоматизації аналізу та спрощення розуміння поведінки коду програмних систем. Запропоновано методи трансляції, абстракції, відлагодження та побудови тестів для мови Кобол. Розроблено експериментальну систему, яка реалізує запропоновані методи. Ключові слова: трансляція, Кобол, моделювання, абстракція, генерація тестів, відлагодження. The purpose of this work is to develop a software tool for analysis automation and simplifying of understanding of software systems behavior. Methods for translation, abstraction, debugging and test generation for COBOL are proposed. We developed a software system, which implements the methods.
Формальная модель
Для применения формальных методов преобразований и проверки достижимости мы используем
модель атрибутной транзиционной системы, в которой переходы представлены тройками вида (t,α ,β ) , где t
– имя перехода, α – его предусловие, а β – постусловие [
Построение UCM основано на использовании знаний о зависимостях исходной программы (PDG), при этом выполняются: автоматическое преобразование процедур в соответствующие карты UCM диаграмм; преобразование «goto» операторов в пути между картами; трансляция структур данных, заданных в Procedure Division, Data Division, Copy-books; удаление данных, которые отсутствуют в условиях и сигналах; удаление заведомо недостижимого кода; разворачивание REDEFINE операторов; преобразование CICS операторов в сигналы; преобразование SQL выражений в сигналы.
Для анализа и моделирования программ строится граф потока управления (CFG) с сохранением структуры исходного кода. Он представляется древовидной структурой данных, которая для удобства записывается в формате JSON, который включает в себя объекты следующих типов: «start» – начальная точка потока управления; «return» – оператор возврата; «decision» – разветвление потока управления, имеет вложенный массив объектов, каждый из которых соответствует ветке (branch) потока управления; «branch» – условие ветки потока управления; «assignment» – выражение с присваиванием; «call» – вызов программы или процедуры; «readevent» – оператор чтения (из файла, терминала, т. д.); «writeevent» – оператор записи (в файл, терминал, т. д.); «goto» – оператор безусловного перехода к произвольной точке программы; «attribute» – определение переменной в программе. Также строится соответствие строкам исходного кода.
Выражения преобразуются в абстрактное синтаксическое дерево (AST), которое представляется как массив объектов. Первый объект всегда строка, определяющая оператор или терминальный символ. Остальные объекты могут быть как строками для задания терминалов, так и массивами объектов для вложенных AST.
Ниже представлены приоритеты операторов в убывающем порядке: "[ ]" – обращение к элементу массива; " " – вызов функции (скобки); "-", "!" – унарный минус и отрицание; "*", "/" – арифметические операции; "+", "-" – арифметические операции; "<", ">", "<=", ">=", "==", "!=" – операции сравнения; "&&" – конъюнкция (логическое И); "||" – дизъюнкция (логическое ИЛИ); "," – запятая, разделяющая параметры в вызове функции; ":=" – присваивание.
Бинарные операторы имеют правостороннюю ассоциативность, кроме бинарного минуса и деления – они левосторонние.
AST не зависит от языка исходного кода и может содержать любые неспецифицированные операторы, как например, конкатенация строк. Так как в большинстве случаев такие операторы не влияют на логику программы, то можно от них абстрагироваться, заменив недетерминированными присваиваниями, тем самым
Рис.1. Синтаксис описания данных в языке Кобол Номера уровней (level-number) от 01 до 50 задают иерархию. Переменная является структурой и содержит все переменные, объявленные ниже с более высоким уровнем до конца секции или до переменной с тем же или более низким уровнем. Есть специальные уровни:
− уровень 66 используется для задания альтернативного имени data-name-1 области памяти, содержащей заданную переменную data-name-2 или все переменные от data-name-2 до data-name-3; − уровень 77 обозначает независимую переменную без возможности дальнейшего разбиения; − уровень 88 не определяет переменных, а используется для сравнения переменной, определенной перед 88 уровнем, с заданным значением или множеством значений. Тип любой переменной может быть числовым, буквенным или буквенно-цифровым. Последние два будем называть строковыми.
Для построения формул исчисления предикатов первого порядка необходимо преобразовать данные исходного языка в переменные перечислимых типов, целочисленные или булевские переменные. Разные уровни иерархии (поля структур) приводятся к простым переменным путем переименования. Строковые переменные преобразуются в переменные перечислимых типов по следующему алгоритму: 1. По всему исходному коду собираются пары переменных, связанных операторами, требующими строго соответствия типов (присваивание, сравнение), а также встречающиеся значения всех переменных.
2. Из собранных пар, по транзитивности строятся группы переменных, обязанных иметь один и тот же тип, а собранные значения этих переменных формируют элементы этого типа. Такое преобразование сохраняет свойства достижимости исходного кода в абстрактной модели, если отсутствуют операции над строками.
Трансляция данных для 77-го уровня тривиальна. 88-й уровень преобразовывается двумя способами: 1. Если значения в разных именах 88-го уровня для одной переменной не пересекаются, то все вхождения этих значений в модели заменяются на соответствующие имена, которые и составляют перечислимый тип. параметром перечислимого типа, построенного как в предыдущем пункте. Это позволяет иметь истинное значение переменной одновременно для нескольких имен 88-го уровня.
Дополнительные сложности возникают при несоблюдении типов, т. е. записи строковых значений в числовые переменные и наоборот, что вполне допускается в языке Кобол. Однако семантика операций над переменными, имеющими значения несоответствующего типа, не определена. Для обработки таких ситуаций мы генерируем сразу 3 переменных: целочисленная, перечислимого типа и переменная-флаг, сохраняющая информацию о том, какая из двух предыдущих модифицировалась последней. А при каждом чтении оригинальной переменной (т. е. одной из сгенерированных с учетом типа) также проверяется флаг, и в случае несоответствия выполняется обработка ошибки (сообщение пользователю или соответствующая трасса).
Некоторые системы трансляции языка Кобол выполняют преобразования области данных Коболпрограммы в один массив памяти, а доступ к каждой переменной заменяют на ряд доступов к соответствующим элементам этого массива (побайтно). Такой подход может быть эффективным для одноразовой автоматической трансляции, но к сожалению, не пригоден для случая, когда требуется дальнейшая модификация результирующего кода и совсем неприемлем для извлечения логики.
Далее мы предлагаем рассмотреть методы преобразований и абстракций на сквозном примере, исходный текст кода которого показан на рис. 2. Граф зависимости для этой программы показан на рис. 3.
На рис. 4, а и 4, б изображен UCM, который автоматически построен из программы. Заметим, что строки 11 и 28 удалены ввиду того, что атрибут Q не используется в условиях и сигналах. 01. IDENTIFICATION DIVISION. 02. PROGRAM-ID. Example initial. 03. DATA DIVISION. 04. WORKING-STORAGE SECTION. 05. 01 BUTTON-RECORD. 06. 05 S PIC 9(16). 07. 05 KEYV PIC X(16). 08. 01 RESULT PIC X(16). 09. 01 X PIC 9(7) VALUE 'UNKNOWN'. 10. 01 Z PIC X(16). 11. 01 Q PIC 9(16). 12. 01 U PIC 9(16). 13. 01 FORM-RECORD. 14. 05 LOGIN PIC X(16). 15. 05 PASS PIC X(16). 16. PROCEDURE DIVISION. 17. EXEC CICS 18. READ FILE ('F') 19. INTO (BUTTON-RECORD) 20. END-EXEC. 21. IF EIBCALEN > ZERO 22. MOVE S TO U 23. ELSE 24. MOVE 'ABORT' TO RESULT 25. EXIT 26. END-IF.
27. IF S > 0 THEN 28. MOVE 1 TO Q 29. IF KEYV = 'M' THEN 30. MOVE 'MODERATOR' TO Z 31. ELSE 32. MOVE 'USER' TO Z 33. END-IF 34. IF U = 0 THEN 35. MOVE Z TO X 36. END-IF 37. ELSE 38. PERFORM 0000-AUTH 39. IF RESULT = 'OK' THEN 40. MOVE 'ADMIN' TO X 41. ELSE 42. MOVE 'INTRUDER' TO X 43. END-IF 44. END-IF. 45. EXEC CICS 46. SEND TEXT FROM (X) 47. END-EXEC. 48. STOP RUN. 49. 0000-AUTH. 50. EXEC CICS READ 51. FILE ('FORM') 52. INTO (FORM-RECORD) 53. END-EXEC. 54. IF LOGIN NOT EQUAL 'admin' THEN 55. MOVE 'FAILED' TO RESULT 56. ELSE 57. IF PASS NOT EQUAL 'admin' THEN 58. MOVE 'FAILED' TO RESULT 59. END-IF 60. END-IF.
Рис. 2. Исходный код на языке Кобол Рис. 3. Граф зависимостей в программе Статический срез
Исходная модель может быть очень большой. Извлечение логики может потребовать сильных огрублений. Но можно рассматривать поведение «по частям», например, организовав разбиение по принципу входных и выходных сигналов, исследуя их по отдельности. Так, задав множество интересующих сигналов, можно статически идентифицировать место их вхождения в коде и использовать технику слоев. Например, для выходных сигналов использовать обратные срезы, а для входных – прямые. Таким образом, можно восстановить логику зависимости выходных сигналов от входных. При этом размер кода будет существенно уменьшен. Так же можно прибегнуть к технике частичных вычислений. В результате построения обратного статического среза для строки 46 будет удалена строка 24. Абстракция процесса вычислений
Часто код описывает довольно громоздкий анализ некоторых входных параметров, в результате которого вычисляется некое результирующее значение. Во многих случаях можно выделить процесс вычисления и исследовать его отдельно, а в общей схеме поведения, в целях уменьшения размера описания логики поведения, заменить его недетерминированным присваиванием, таким образом, абстрагироваться от загромождающих деталей. Интуитивно, достаточным условием корректности такой абстракции будет нарушение связности DEF-USE графа при удалении ребра, соединяющего процесс вычисления с результатом. На рис. 5 показан результат применения такого типа абстракции для строки 46.
Рис. 5. Абстракция вычисления значения атрибута RESULT На этом этапе удалены строки 49–60, строка 38 заменена строкой 38а, в которой используется оператор NONDET, обозначающий недетерминированный выбор. Анализ достижимости
Как известно, статические методы преувеличивают фактические информационные связи [
Недостижимым код может оказаться не только вследствие ошибки, но и после выполнения частичных вычислений, когда удаляются участки кода, не удовлетворяющие некоторому заданному условию. При этом некоторый код, подлежащий удалению, может остаться из-за того, что некоторые зависимости или условия не удалось разрешить статически.
Отметим полезную функциональность разработанной системы – оперативное выделение всех DEFUSE ветвей для заданного атрибута в заданной точке, причем с информацией об их достижимости. На базе этой функции реализован режим объяснения причин недостижимости. В этом режиме будут построены (и выделены на UCM специальной подсветкой) участки путей от последнего присваивания атрибуту, значение которого не удовлетворяет формуле предусловия недостижимого перехода, к самому переходу.
Следует иметь ввиду, что даже при условии конечности множества состояний модели, анализ
достижимости может оказаться весьма трудоемким процессом ввиду так называемого эффекта
комбинаторного взрыва [
27. IF S > 0 THEN 27a. CONTINUE 37. ELSE 38a. 39. 40. 41. ELSE 42. MOVE 'INTRUDER' TO X 43. END-IF 44. END-IF.
MOVE NONDET{OK,FAILED} TO RESULT IF RESULT = 'OK' THEN
MOVE 'ADMIN' TO X 45. EXEC CICS 46. SEND TEXT FROM (X) 47. END-EXEC.
48. STOP RUN.
Рис. 7. Результирующий код после повторного статического среза
UCM сценарий, получившийся в результате описанных преобразований и абстракций описывает логику поведения модели, ведущего к интересующей точке (в нашем примере, к 46-й строке кода). Аналогично, можно исследовать влияние некоторой точки на последующее поведение, используя прямые срезы и абстракции. Генерация тестов
При выполнении миграции на другую платформу возникает проблема проверки адекватности новой
реализации. Одним из методов, широко применяемых на практике для этих целей, является тестирование. В
условиях отсутствия спецификаций на исходную реализацию, актуальной становится задача порождения
тестовых наборов. Некоторые подходы предлагают осуществлять запуск старой программы и фиксировать
реакцию на различные входы вручную, однако такой подход не эффективен для больших систем. Мы
предлагаем автоматическую генерацию тестовых сценариев на основе анализа кода. Так, построив
формальную модель UCM, применяем существующие методы анализа достижимости, которые в процессе
обхода поведения модели способны [
Разработанный программный комплекс был успешно применен в ряде промышленных проектов. Далее представлена сводная таблица статистики.
Отметим, что операционное время, затраченное созданным программным комплексом на получение указанных результатов, исчисляется секундами. Такая производительность позволяет использовать инструментарий интерактивно в режиме реального времени, что очень востребовано при анализе поведения больших объемов программного кода. Таблица. Статистика применения
Проект (домен) № 1 (лизинг) № 2 (страхование) № 3 (финансы)