Типосостояний анализ - Typestate analysis

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

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

Типовой анализ был введен Робом Стромом в 1983 году.[2]на языке сетевой реализации (NIL), разработанном в Лаборатория Ватсона IBM Это было формализовано Стромом и Йемини в статье 1986 года.[3]в котором описано, как использовать typestate для отслеживания степени инициализации переменных, гарантируя, что операции никогда не будут применяться к неправильно инициализированным данным, и далее обобщены в Гермес язык программирования.

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

Подход

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

Стром и Йемини (1986) требовали, чтобы набор состояний типов для данного типа был частично заказанный таким образом, что состояние более низкого типа может быть получено из состояния более высокого, отбрасывая некоторую информацию. Например, int переменная в C обычно имеет тип состояния "неинициализированный" < "инициализирован", и ФАЙЛ* указатель может иметь тип состояния "нераспределенный" < "выделенный, но неинициализированный" < "инициализирован, но файл не открыт" < "файл открыт". Кроме того, Стром и Йемини требуют, чтобы у каждых двух типов состояний была точная нижняя граница, т.е. чтобы частичный порядок был четным встречная полурешетка; и что в каждом заказе есть наименьший элемент, всегда называемый «⊥».

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

int п;                // здесь n имеет typeestate "неинициализированный"если (...) {    п = 5;            // здесь n имеет typeestate "initialized"} еще {    /*ничего не делать*/    // здесь n имеет typeestate "неинициализированный"}                     // здесь n имеет typestate "uninitialized" = maximum_lower_bound ("initialized", "unitialized")

Каждая основная операция[примечание 1] должен быть оснащен Тип состояния перехода, т.е. для каждого параметра требуемое и гарантированное состояние типов до и после операции соответственно. Например, операция fwrite (..., fd) требует fd иметь состояние "файл открыт". Точнее, операция может иметь несколько результаты, каждый из которых требует своего собственного перехода типа-состояние. Например, код C ФАЙЛ * fd = fopen ("foo", "r") наборы fdтипсостояния "файл открыт" и "нераспределенный"если открытие было успешным и неудачным, соответственно.

За каждые два типа усадеб т1 <· т2, уникальный операция принуждения типа должен быть предоставлен, который, применительно к объекту typeestate т2, уменьшает его типсостояние до т1, возможно, высвободив некоторые ресурсы. Например, fclose (fd) принуждает fdтипсостояние из "файл открыт" к "инициализирован, но файл не открыт".

Выполнение программы называется типсостояние-правильный если

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

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

Вызовы

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

Еще одна проблема: для некоторых программ метод получения наибольшей нижней границы при сходящихся путях выполнения и добавления соответствующих операций с понижающим принуждением оказывается неадекватным. возврат 1 в следующей программе,[заметка 3] все компоненты Икс, у, и z из согласовывать инициализируются, но подход Строма и Йемини не учитывает этого, поскольку каждая инициализация компонента структуры в теле цикла должна быть понижена при повторном входе в цикл, чтобы соответствовать типу самой первой записи цикла, а именно. ⊥. Связанная проблема состоит в том, что этот пример потребует перегрузки переходов типа-состояния; Например, parse_int_attr ("x", & Coord-> x) меняет тип состояния "компонент не инициализирован" к "компонент x инициализирован", но также "компонент y инициализирован" к "x и y компоненты инициализированы".

int parse_coord(структура{int Икс;int у;int z;} *согласовывать) {    int видимый = 0;     / * запоминаем, какие атрибуты были проанализированы * /    пока (1)        если      (parse_int_attr("Икс",&согласовывать->Икс)) видимый |= 1;        еще если (parse_int_attr("у",&согласовывать->у)) видимый |= 2;        еще если (parse_int_attr("z",&согласовывать->z)) видимый |= 4;        еще перемена;    если (видимый != 7)    / * отсутствует какой-то атрибут, ошибка * /        возвращаться 0;    ...               / * присутствуют все атрибуты, выполняем некоторые вычисления и успешно * /    возвращаться 1;}

Типосословный вывод

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

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

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

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

Примечания

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

Рекомендации

  1. ^ Хорхе Луис Гевара Д'яз (2010). «Типично-ориентированный дизайн - подход с использованием цветной сети Петри» (PDF).
  2. ^ Стром, Роберт Э. (1983). «Механизмы обеспечения безопасности на этапе компиляции». Материалы 10-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования - POPL '83. С. 276–284. Дои:10.1145/567067.567093. ISBN  0897910907.
  3. ^ Стром, Роберт Э .; Йемини, Шаула (1986). «Typestate: концепция языка программирования для повышения надежности программного обеспечения» (PDF). IEEE Transactions по разработке программного обеспечения. IEEE. 12: 157–171. Дои:10.1109 / tse.1986.6312929.
  4. ^ ДеЛайн, Роберт; Фендрих, Мануэль (2004). «Типовые состояния для объектов». ECOOP 2004: Материалы 18-й Европейской конференции по объектно-ориентированному программированию. Конспект лекций по информатике. Springer. 3086: 465–490. Дои:10.1007/978-3-540-24851-4_21. ISBN  978-3-540-22159-3.
  5. ^ Бирхофф, Кевин; Олдрич, Джонатан (2007). "Модульная проверка объектов с псевдонимами". OOPSLA '07: Материалы 22-й конференции ACM SIGPLAN по объектно-ориентированному программированию: системы, языки и приложения. 42 (10): 301–320. Дои:10.1145/1297027.1297050. ISBN  9781595937865.
  6. ^ Гвидо де Касо, Виктор Браберман, Диего Гарбервецки и Себастьян Учитель. 2013. Абстракции программ на основе возможностей для проверки поведения. ACM Trans. Софтв. Англ. Методол. 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, Нью-Йорк, NY, США, 501-510
  14. ^ Иван Бесчастных, Юрий Брун, Сигурд Шнайдер, Майкл Слоан и Майкл Д. Эрнст. 2011. Использование существующих инструментов для автоматического вывода моделей с инвариантными ограничениями. В материалах 19-го симпозиума ACM SIGSOFT и 13-й Европейской конференции по основам программной инженерии (ESEC / FSE '11). ACM, Нью-Йорк, Нью-Йорк, США, 267-277
  15. ^ Pradel, M .; Гросс, T.R., «Автоматическое создание спецификаций использования объектов из больших трассировок методов», Автоматизированная разработка программного обеспечения, 2009. ASE '09. 24-я Международная конференция IEEE / ACM, том, №, стр. 371 382, ​​16-20 ноября 2009 г.
  16. ^ Олдрич, Джонатан. "Язык программирования Plaid". Получено 22 июля 2012.
  17. ^ Кобленц, Майкл. "Обсидиановый язык программирования". Получено 16 февраля 2018.
  18. ^ Бодден, Эрик. "Клара". Получено 23 июля 2012.
  19. ^ Си, Хунвэй. «Введение в программирование в ATS». Получено 20 апреля 2018.