Анализ состояния типа

Проверяет операции компьютерной программы

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

Typestates способны представлять поведенческие уточнения типов, такие как «метод A должен быть вызван до вызова метода B , а метод C не может быть вызван между ними». Typestates хорошо подходят для представления ресурсов, которые используют семантику открытия/закрытия, обеспечивая семантически допустимые последовательности, такие как «открыть, затем закрыть», в отличие от недопустимых последовательностей, таких как оставление файла в открытом состоянии. Такие ресурсы включают элементы файловой системы, транзакции, соединения и протоколы. Например, разработчики могут захотеть указать, что файлы или сокеты должны быть открыты перед тем, как они будут прочитаны или записаны, и что они больше не могут быть прочитаны или записаны, если они были закрыты. Название «typestate» происходит от того факта, что этот вид анализа часто моделирует каждый тип объекта как конечный автомат . В этом автомате каждое состояние имеет четко определенный набор разрешенных методов/сообщений, а вызовы методов могут вызывать переходы состояний. Сети Петри также были предложены в качестве возможной поведенческой модели для использования с типами уточнения . ^[1]

Анализ состояния типа был введен Робом Стромом в 1983 году ^[2] в Network Implementation Language (NIL), разработанном в Watson Lab IBM . Он был формализован Стромом и Йемини в статье 1986 года ^[3] , в которой описывалось, как использовать состояние типа для отслеживания степени инициализации переменных, гарантируя, что операции никогда не будут применяться к неправильно инициализированным данным, и далее обобщен в языке программирования Hermes .

В последние годы различные исследования разработали способы применения концепции состояния типа к объектно-ориентированным языкам. ^{[4] [5]}

Подход

Нелинейная решетка состояний типов, возникающая при инициализации переменной типа struct{int x;int y;int z;}.
Наименьший элемент ⊥ совпадает с состоянием ∅ ни одного инициализированного компонента структуры.

Strom и Yemini (1986) потребовали, чтобы набор состояний типов для данного типа был частично упорядочен, так что более низкое состояние типа можно было получить из более высокого, отбросив некоторую информацию. Например, переменная intв C обычно имеет состояния типов " uninitialized " < " initialized ", а FILE*указатель может иметь состояния типов " unallocated " < " allocated, but uninitialized " < " initialized, but file not opening " < " file opening ". Более того, Strom и Yemini требуют, чтобы каждые два состояния типов имели наибольшую нижнюю границу, т. е. чтобы частичный порядок был даже meet-semilattice ; и чтобы каждый порядок имел наименьший элемент, всегда называемый "⊥".

Их анализ основан на упрощении, что каждой переменной v назначается только одно состояние типа для каждой точки в тексте программы; если точка p достигается двумя различными путями выполнения и v наследует различные состояния типа через каждый путь, то состояние типа v в точке p принимается за наибольшую нижнюю границу унаследованных состояний типа. Например, в следующем фрагменте кода на языке C переменная nнаследует состояние типа " initialized " и " uninitialized " из частей thenи (пустой) elseсоответственно, поэтому она имеет состояние типа " uninitialized " после всего условного оператора.

int n ; // здесь n имеет состояние типа "неинициализировано" if (...) { n = 5 ; // здесь n имеет состояние типа "неинициализировано" } else { /*ничего не делаем*/ // здесь n имеет состояние типа "неинициализировано" } // здесь n имеет состояние типа "неинициализировано" = greatest_lower_bound("initialized","uninitialized")             

Каждая базовая операция ^{[примечание 1]} должна быть снабжена переходом typestate , т. е. для каждого параметра требуемым и гарантированным typestate до и после операции соответственно. Например, операция fwrite(...,fd)требует fdиметь typestate " file opening ". Точнее, операция может иметь несколько результатов , каждому из которых нужен свой переход typestate. Например, код C FILE *fd=fopen("foo","r")устанавливает fdtypestate в " file opening " и " unallocated ", если открытие успешно и не удалось, соответственно.

Для каждых двух typestates t ₁ <· t ₂ необходимо предоставить уникальную операцию приведения typestate , которая при применении к объекту typestate t ₂ снижает его typestate до t ₁ , возможно, освобождая некоторые ресурсы. Например, fclose(fd)приводит fdtypestate из " file opening " в " initialized, but file not opening ".

Выполнение программы называется typestate-correct, если

• перед каждой базовой операцией все параметры имеют именно то состояние типа, которое требуется для перехода состояния типа операции, и
• при завершении программы все переменные находятся в состоянии типа ⊥. ^{[примечание 2]}

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

Вызовы

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

Еще одна проблема заключается в том, что для некоторых программ метод взятия наибольшей нижней границы при сходящихся путях выполнения и добавления соответствующих операций понижающего приведения оказывается неадекватным. Например, перед return 1в следующей программе ^{[примечание 3]} все компоненты x, yи инициализируются, но подход Строма и Йемини не распознает этого, поскольку каждая инициализация компонента структуры в теле цикла должна быть подвергнута понижающему приведению при повторном входе в цикл, чтобы соответствовать состоянию типа самого первого входа в цикл, а именно ⊥. Связанная с этим проблема заключается в том, что этот пример потребует перегрузки переходов состояний типов; например, zизменяет состояние типа " no component initialized " на " x component initialized ", а также " y component initialized " на " x and y component initialized ".coordparse_int_attr("x",&coord->x)

int parse_coord ( struct { int x ; int y ; int z ; } * coord ) { int seen = 0 ; /* запоминаем, какие атрибуты были проанализированы */                 while ( 1 ) if ( parse_int_attr ( "x" , & coord -> x )) виден |= 1 ; else if ( parse_int_attr ( "y" , & coord -> y )) виден |= 2 ; else if ( parse_int_attr ( "z" , & coord -> z )) виден |= 4 ; else break ;                        если ( seen != 7 ) /* отсутствует какой-то атрибут, неудача */ return 0 ; ... /* все атрибуты присутствуют, выполняем некоторые вычисления и добиваемся успеха */ return 1 ; }          

вывод состояния типа

Существует несколько подходов, направленных на выведение состояний типов из программ (или даже других артефактов, таких как контракты). Многие из них могут выводить состояния типов во время компиляции ^{[6] [7] [8] [9]} , а другие извлекают модели динамически. ^{[10] [11] [12] [13] [14] [15]}

Языки, поддерживающие typestate

Typestate — это экспериментальная концепция, которая пока не перешла в основные языки программирования. Однако многие академические проекты активно исследуют, как сделать ее более полезной в качестве повседневной техники программирования. Два примера — языки Plaid и Obsidian, которые разрабатываются группой Джонатана Олдрича в Университете Карнеги-Меллона . ^{[16] [17]} Другие примеры включают в себя фреймворк для исследования языка Clara ^[18] , более ранние версии языка Rust и >>ключевое слово в ATS . ^[19]

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

• Государственный образец
• Проектирование по контракту
• Система линейного типа
• Система эффектов
• Проверка во время выполнения

Примечания

1. сюда входят языковые конструкции, например, +=в C, и стандартные библиотечные процедуры, напримерfopen()
2. Это направлено на то, чтобы гарантировать, что, например, все файлы закрыты, а вся malloced-память очищена free. В большинстве языков программирования время жизни переменной может закончиться до завершения программы; тогда понятие typestate-correctness должно быть соответствующим образом уточнено.
3. предполагая, что int parse_int_attr(const char *name,int *val)инициализация происходит *valвсякий раз, когда она успешна

Ссылки

1. Хорхе Луис Гевара Диас (2010). «Проектирование, ориентированное на состояние типа — подход с использованием цветных сетей Петри» (PDF) .
2. Strom, Robert E. (1983). "Механизмы обеспечения безопасности во время компиляции". Труды 10-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования - POPL '83 . стр. 276–284. doi :10.1145/567067.567093. ISBN 0897910907. S2CID  6630704.
3. Strom, Robert E.; Yemini, Shaula (1986). «Typestate: концепция языка программирования для повышения надежности программного обеспечения» (PDF) . IEEE Transactions on Software Engineering . 12. IEEE: 157–171. doi :10.1109/tse.1986.6312929. S2CID  15575346.
4. ДеЛайн, Роберт; Фендрих, Мануэль (2004). «Состояния типов для объектов». ECOOP 2004 – Объектно-ориентированное программирование . Конспект лекций по информатике. Том 3086. Springer. С. 465–490. doi :10.1007/978-3-540-24851-4_21. ISBN 978-3-540-22159-3.
5. Бирхофф, Кевин; Олдрич, Джонатан (2007). «Проверка состояния типов с псевдонимами объектов Modular typestate». Труды 22-й ежегодной конференции ACM SIGPLAN по системам объектно-ориентированного программирования, языкам и приложениям . Том 42. С. 301–320. doi :10.1145/1297027.1297050. ISBN 9781595937865. S2CID  9793770.
6. Гвидо де Касо, Виктор Браберман, Диего Гарберветски и Себастьян Учитель. 2013. Абстракции программ на основе возможностей для проверки поведения. ACM Trans. Softw. Eng. Methodol. 22, 3, статья 25 (июль 2013 г.), 46 страниц.
7. Р. Алур, П. Черни, П. Мадхусудан и В. Нам. Синтез спецификаций интерфейсов для классов Java, 32-й симпозиум ACM по принципам языков программирования, 2005 г.
8. Джаннакопулу, Д. и Пасареану, К. С. , «Генерация интерфейса и композиционная проверка в JavaPathfinder», FASE 2009.
9. Томас А. Хензингер, Ранджит Джхала и Рупак Маджумдар. Разрешительные интерфейсы. Труды 13-го ежегодного симпозиума по основам программной инженерии (FSE), ACM Press, 2005, стр. 31-40.
10. Валентин Даллмайер, Кристиан Линдиг, Анджей Васильковски и Андреас Целлер. 2006. Поведение объектов майнинга с помощью ADABU. В трудах международного семинара 2006 года по анализу динамических систем (WODA '06). ACM, Нью-Йорк, США, 17-24
11. Карло Гецци, Андреа Моччи и Маттиа Монга. 2009. Синтез интенциональных моделей поведения путем преобразования графа. В трудах 31-й Международной конференции по программной инженерии (ICSE '09). IEEE Computer Society, Вашингтон, округ Колумбия, США, 430-440
12. Марк Габель и Чжэндун Су. 2008. Символический анализ временных спецификаций. В трудах 30-й международной конференции по программной инженерии (ICSE '08). ACM, Нью-Йорк, США, 51-60.
13. Давиде Лоренцоли, Леонардо Мариани и Мауро Пецце. 2008. Автоматическая генерация моделей поведения программного обеспечения. В трудах 30-й международной конференции по программной инженерии (ICSE '08). ACM, Нью-Йорк, США, 501-510
14. Иван Бесчастных, Юрий Брун, Сигурд Шнайдер, Майкл Слоан и Майкл Д. Эрнст. 2011. Использование существующего инструментария для автоматического вывода инвариантно-ограниченных моделей. В трудах 19-го симпозиума ACM SIGSOFT и 13-й Европейской конференции по основам программной инженерии (ESEC/FSE '11). ACM, Нью-Йорк, США, 267-277
15. Прадель, М.; Гросс, ТР, «Автоматическая генерация спецификаций использования объектов из больших трасс методов», 2009. ASE '09. 24-я Международная конференция IEEE/ACM по автоматизированной разработке программного обеспечения, т., №, стр. 371,382, 16–20 ноября 2009 г.
16. Олдрич, Джонатан. "Язык программирования Plaid" . Получено 22 июля 2012 г.
17. Кобленц, Майкл. "Язык программирования Obsidian" . Получено 16 февраля 2018 г.
18. Бодден, Эрик. "Клара" . Получено 23 июля 2012 г.
19. Си, Хунвэй. "Введение в программирование в ATS" . Получено 20 апреля 2018 г.