Исследования по теме выполнялись в рамках 6 проектов.

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

Разработаны потоковый и статический анализы ошибок для программ на языке Java. Реализованы проектирование и программирование новых компонент в потоковом анализаторе для Java. На базе гиперграфового представления анализируемой программы разработаны алгоритмы потокового анализа Jawa-программ при наличии исключительных ситуаций.

Подготовлена пользовательская версия статического анализатора ошибок для языка Java; написано руководство к пользованию.

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

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

Разработана статическая модель программы для автоматического построения тестов. Ее реализация базируется на результатах потокового анализатора OSA. Разработан прототип системы, в качестве пакетно-диалоговой среды использовался модифицированный вариант отладчика XD (в системе программирования XDS для Модулы-2). Реализован цепочечный метод автоматического построения тестов.

Конвертор с языка Эль-76 на язык Си++ функционирует на рабочих SPARC-станциях с операционной системой SunOS (Solaris 2.x) и вычислительных системах на их базе.

Конвертор состоит из:

• описания входного языка, оформленного в виде набора файлов в формате HTML;
• собственно программы конвертирования текстов программ с языка Эль-76 на язык Си++;
• библиотеки поддержки исполнения.

Конвертор порождает выходные программы на языке Си++. Одной из основных особенностей языка Эль-76 являются динамические типы данных. Язык позволяет переменным программы пользователя менять свой тип во время исполнения программы. В библиотеке поддержки исполнения описан специальный класс языка Си++. Кроме значения, объект данного класса имеет тег, формат данных, количество битов, занимаемых значением, некоторые другие атрибуты и множество методов. Все действия с объектами динамических типов интерпретируются библиотекой поддержки исполнения. Разрешены также объекты статических типов.

Библиотека поддержки исполнения разрешает объектам динамических типов иметь значение либо в представлении SPARC-станции, либо в представлении Эльбрус-2. В связи с тем, что в языке Си++ отсутствуют вложенные процедуры, Конвертор выносит вложенные процедуры на верхний уровень. При этом различаются 3 случая:

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

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

Оптимизирующие преобразования Конвертора связаны, в первую очередь, со статизацией типов объектов.

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

В НИГ переносимых систем программирования проводилась работа по исследованию применимости объектно-ориентированного подхода к построению компиляторов для реализации компилятора с языка Java в объектный код целевой платформы.

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

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

Реализована конкретизация абстрактного интерфейса перенацеливаемой кодогенерации: компонента генерации объектного кода для Java.

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

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

Shelekhov V.I., Kuksenko S.V. Data Flow Analysis of Java Programs in the Presence of Exceptions // Proc. of the 3^rd Intern. Andrei Ershov Memorial Conf. " Perspectives of System Informatics ", Novosibirsk, 1999. – Berlin a.o.: Springer, 2000. – P. 385–391. – (Lect. Notes Comput. Sci.; 1755).

Shelekhov V.I., Kuksenko S.V. On the Practical Static Checker of Semantic Run-time Errors // Proc. of the 6th Asia Pacific Software Engineering Conf. APSEC'99, Takamatsu, Japan, 1999. – IEEE Computer Society Press, 1999.

Katkov S.I., Ruban E.Y. Parallel Programming System Based on Super Language// Lect. Notes Comput. Sci. – 1999. – Vol. 1662. – P. 481–482.

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

Кроме указанных выше задач, система HyperCode использовалась также:

• как составная часть Rescueware – промышленной системы сопровождения и переноса программного обеспечения, написанного на языке Кобол;
• как составная часть среды смешанных вычислений для языка Модула-2;
• как инструмент отладки кодогенерирующей части компилятора языка Модула-2 фирмы XDS, сопоставляющий фрагментам исходной программы полученные по ним фрагменты на ассемблере и накопленную отладочную информацию;
• как инструмент для изучения и исследования результатов анализа отношений равенства программных термов и анализа синонимов в языках Модула-2 и Оберон-2.

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

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

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

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

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

Интерфейс, предоставляемый совокупностью порожденных документов, максимально приближен к операционной обстановке RescueWare, что повышает эффективность навигации и восприятия информации. На следующем рисунке представлен HTML-аналог системы HyperCode:

Исследовались возможности использования расширяемого языка разметки XML в задачах визуализации свойств программных комплексов и системах перепроектировки. Интерес к XML определяется следующими обстоятельствами. Это открытый формат структурирования информации, поддерживаемый мировыми лидерами компьютерной индустрии (IBM, Sun Microsystems, Microsoft, Netscape, W3C и др.). Стандартом XML определяются унифицированные средства проверки корректности формата обрабатываемых данных и предоставляется программный интерфейс, позволяющий манипулировать этими данными. XML и связанные с ним технологии приобретают все большее значение для распределенной обработки информации через Интернет.

Emelianov P.G. Analysis of equality relationships: proofs and examples // Joint Bulletin of NCC&IIS. Ser.: Comput. Sci. – 1999. – N 11. – P. 15–38.

Продолжались исследования широко известной комбинаторной задачи, известной в англоязычной литературе как "Snake-in-the-Box Problem". Задача заключается в отыскании длины и в эффективном конструировании максимального цикла без хорд в n-мерном единичном кубе. На данный момент известны лишь первые 5 точных значений длин. Совместно с Dr. A. Lukito (Delft University of Technology, The Netherlands) подготовлена и принята к публикации статья, посвященная исследованию верхней оценки мощности бинарных цепных кодов (snake-in-the-box problem). Отметим, что эта задача, являясь чрезвычайно сложной с вычислительной точки зрения, в то же время очень важна на практике, при конструировании прецизионных устройств. Проводились численные эксперименты, реализующие различные эвристики и нацеленные на получение рекордных "змей" в кубах малой размерности. Были получены результаты, близкие к наилучшим известным в настояшее время.

Emelianov P.G., Lukito A. On the maximal length of a snake in hypercubes of small dimension // Discrete Mathematics. – 2000. – Vol. 211 (1-3). – P. 181–191.

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

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

Основное окно интерфейса

Система была использована, в частности, для восстановления работоспособности библиотечной системы ИСИ СО РАН.

Система See2k предназначена для проведения более глубокого анализа в рамках проекта, включающего одну или несколько взаимосвязанных программ, написанных на языке программирования С/С++. В процессе анализа проекта производятся его полное препроцессирование, синтаксический анализ и частичный семантический анализ. Система предлагает автоматическое распространение информации о переменной, подозрительной на содержание даты, по всему приложению. Так, например, если пользователь отметил, что некоторый класс требует исправлений, то автоматически будут отмечены и все наследуемые классы, вхождения описания объектов этих классов, их вхождения и т.д. Поддерживаются следующие диалекты языка С: ANSI C/C++, Microsoft Visual C++, Borland C++, GNU C/C++. Пользовательский интерфейс системы сходен с интерфейсом системы Scan2K.

Система подготовки расписания занятий.

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

Система внедрена и сопровождается в Новосибирском госуниверситете, в Новосибирской государственной академии экономики и управления и в Сибирском университете потребительской кооперации.