«Лекарство от болезни»: Автоматное программирование

в 5:28, , рубрики: Блог компании Университет ИТМО, Программирование, Университет ИТМО

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

«Лекарство от болезни»: Автоматное программирование - 1Robson# / Flickr / CC

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

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

Откуда растут ноги

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

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

Автоматное программирование вступает в игру

Автоматное программирование — это парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого-либо формального автомата. Этот термин в 1991 году предложил заведующий кафедрой Технологии программирования Университета ИТМО Анатолий Шалыто.

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

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

В качестве примера использования автоматного подхода при построении алгоритма приведем решение задачи прямого обхода (0–9) двоичного дерева.

«Лекарство от болезни»: Автоматное программирование - 2

Пример двоичного дерева

Будем считать, что каждая вершина содержит свой номер и указатели на дочерние вершины. На языке C++ эта структура может быть представлена следующим образом:

struct Node { 
int id; // Номер узла 
Node* left; // Левый дочерний узел 
Node* right; // Правый дочерний узел 
};

Также введем в систему функцию put (int x), которая выводит номер вершины в выходную последовательность, и класс, реализующий стек со следующим интерфейсом:

template class Stack { 
void push(const T& x); // Поместить значение x в стек 
void pop(); // Удалить из стека верхний элемент 
const T& top() const; // Верхний элемент стека 
}; 

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

«Лекарство от болезни»: Автоматное программирование - 3

Схема связей автомата, реализующего обход дерева

«Лекарство от болезни»: Автоматное программирование - 4

Диаграмма переходов автомата, реализующего обход дерева

Отметим, что теория конечных автоматов была успешно применена компанией Corezoid для построения одноименной облачной платформы для ИТ-решений. Анатолий Шалыто говорит о необходимости внедрения этого метода в современную разработку: «Программисты — они ведь очень умные, и применяют автоматы, как и другие математические абстракции, когда считают нужным. А я говорю: всегда его [автоматное программирование] надо применять для описания программ со сложным поведением, в которых имеет место зависимость их поведения от предыстории».

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

Автор: Университет ИТМО

Источник

Поделиться

* - обязательные к заполнению поля