Принципы написания самопроверяющихся программ

[Serg79]

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

Может кто знает соответствующие статитьи в данном направлении, дайте ссылки. Буду очень благодарен.

[Dimka]

offtop: Если не секрет, в какой области деятельности такие задачи возникают?

[Serg79]

Программные методы обеспечения безопасности и локализация отказов микропроцессорных систем автоматики.

[Sla]

вопросы диагностики (самодиагностики) достаточно сложны.
Главное. Выбрать то чему доверяешь.
Пример.
Микроконтроллер.
  Проверить работоспособность памяти внешней. (методы проверки памяти - контрольная сумма, бегущая 1 или 0 и т.д.)
  проверить работоспособность внеших устройств (подача стандртных сигналов, получение ответов)
  Контроль стека внутри подпрограмм. (на любителя)
  контроль контрольной суммы ПЗУ (внешней, затем внутренней)

ЗЫ это так на вскидку.
а не на вскидку все намного сложнее
например, наличие watchdog, или контролирущих устройств адресной шины
принятие решения, например, два из трех

[Serg79]

Главное. Выбрать то чему доверяешь.

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

Проверить работоспособность памяти внешней. (методы проверки памяти - контрольная сумма, бегущая 1 или 0 и т.д.)

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

Контроль стека внутри подпрограмм. (на любителя)

Я незнаю как реализовать данный метод, ведь формированием стека занимается сам процессор. А как контролировать его в программе затрудняюсь сказать.

контроль контрольной суммы ПЗУ (внешней, затем внутренней)

Да, ето единственный разумный вариант, для МК.

например, наличие watchdog, или контролирущих устройств адресной шины

Контора котораю проводит атестацию кода, сказала что watchdog они вообще серьезно не расматриваю. Причина мне пока не известна.

Да, построение безопасного ПО задача действительно не тривиальная как кажется на первый взгляд.

[Alf]

Подскажите, с чего следует начинать при написании программы которая должна контролировать правильность своей работы,

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

целостность своего кода

Вполне подойдет контроль с помощью CRC или более серьезных сигнатур.

и памяти.

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

Да и вообще должна зафиксировать любой факт воздействия на код и на данные.

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

А так же должна контролировать правильность работы АЛУ.

Почему именно АЛУ? В системе используется не однокристалльный процессор, АЛУ реализовано отдельным модулем, который может отказать?

Может кто знает соответствующие статитьи в данном направлении, дайте ссылки. Буду очень благодарен.

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

[Serg79]

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

Alf не подскажешь, где можно взять данную доку. Мои поиски с помошью поисковиков не пренесли результатов.

[Dimka]

Мне кажется, что для проверки чего-то одного (например, внешнего устройства или памяти) нужно полагать, что выполняющая проверку программа не повреждена. Для проверки частей программ нужно полагать, что исправна аппаратная часть.

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

Наверно, задачу нужно поставить как-нибудь иначе...

[Alf]

Alf не подскажешь, где можно взять данную доку. Мои поиски с помошью поисковиков не пренесли результатов.

Я думаю, имеет смысл поискать на военных заводах и институтах, туда подобная техника поступала в больших количествах. Сами машины наверняка растащены, а вот документацию могли сохранить. Еще посмотри аналоги. VAX-11 выпускались в СССР (под маркой СМ-1700) и в Болгарии (ИЗОТ-1055, ИЗОТ-1080). Может, посчастливится что-то найти.

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

[Serg79]

Мне кажется, что для проверки чего-то одного (например, внешнего устройства или памяти) нужно полагать, что выполняющая проверку программа не повреждена. Для проверки частей программ нужно полагать, что исправна аппаратная часть.

Вот случай который был на самом деле.
Пренесли код на проверку, в котором был такой участок:
switch( mode )
{
   case NORM_MODE:
      shine = NORM_MODE_SHINE;
      break;

   case NIGHT_MODE:
      shine = NIGHT_MODE_SHINE;
      break;

   case WAR_MODE:
      shine = WAR_MODE_SHINE;
      break;

   default:
      return;
}

А вот его ассемблерный вариант:
    switch( mode )
    175a:   89 81          ldd   r24, Y+1   ; 0x01
    175c:   99 27          eor   r25, r25
    175e:   9c 83          std   Y+4, r25   ; 0x04
    1760:   8b 83          std   Y+3, r24   ; 0x03
    1762:   8b 81          ldd   r24, Y+3   ; 0x03
    1764:   9c 81          ldd   r25, Y+4   ; 0x04
    1766:   82 30          cpi   r24, 0x02   ; 2
    1768:   91 05          cpc   r25, r1
    176a:   a1 f0          breq   .+40        ; 0x1794 <sign_on+0x50>
    176c:   8b 81          ldd   r24, Y+3   ; 0x03
    176e:   9c 81          ldd   r25, Y+4   ; 0x04
    1770:   83 30          cpi   r24, 0x03   ; 3
    1772:   91 05          cpc   r25, r1
    1774:   34 f4          brge   .+12        ; 0x1782 <sign_on+0x3e>
    1776:   8b 81          ldd   r24, Y+3   ; 0x03
    1778:   9c 81          ldd   r25, Y+4   ; 0x04
    177a:   81 30          cpi   r24, 0x01   ; 1
    177c:   91 05          cpc   r25, r1
    177e:   39 f0          breq   .+14        ; 0x178e <sign_on+0x4a>
    1780:   25 c0          rjmp   .+74        ; 0x17cc <sign_on+0x88>
    1782:   8b 81          ldd   r24, Y+3   ; 0x03
    1784:   9c 81          ldd   r25, Y+4   ; 0x04
    1786:   83 30          cpi   r24, 0x03   ; 3
    1788:   91 05          cpc   r25, r1
    178a:   39 f0          breq   .+14        ; 0x179a <sign_on+0x56>
    178c:   1f c0          rjmp   .+62        ; 0x17cc <sign_on+0x88>
   {
      case NORM_MODE:
         shine = NORM_MODE_SHINE;
    178e:   9f ef          ldi   r25, 0xFF   ; 255
    1790:   9a 83          std   Y+2, r25   ; 0x02
         break;
    1792:   05 c0          rjmp   .+10        ; 0x179e <sign_on+0x5a>

      case NIGHT_MODE:
         shine = NIGHT_MODE_SHINE;
    1794:   80 e8          ldi   r24, 0x80   ; 128
    1796:   8a 83          std   Y+2, r24   ; 0x02
         break;
    1798:   02 c0          rjmp   .+4         ; 0x179e <sign_on+0x5a>

      case WAR_MODE:
         shine = WAR_MODE_SHINE;
    179a:   95 e0          ldi   r25, 0x05   ; 5
    179c:   9a 83          std   Y+2, r25   ; 0x02
         break;

      default:
         return;
   }

и было сказанно, как поведет себя ваша программа если заменить оператор в стороке в тот момент когда mode = NORM_MODE
    177a:   81 30          cpi   r24, 0x01   ; 1   // сравнение с NORM_MODE
на оператор:
    add   r24, r25  // сложение двух регистров
Ответ был таким: х.. знает как она себя поведет.

Целенапраленно изменяются разные машинные команды а вот ПО должно отследить такие вольности. Короче, новые рынки сбыта открываються с большим трудом.

[Sla]

имелась некоторая аппаратная поддержка

но кто-то должен контролировать и саму аппаратную поддержку.


Watchdog - не такая сложная штука, но защитит систему от зависания
тем более в МК, в последнне время встраивают во внутрь.
Отказываться от него не вижу смысла.
Мой товарищ, защищал диплом по разработке watchdog-подобной системы, она потом была принята в производство. и очень себя оправдала.

кроме того, обязательный жесткий контроль параметров приходящий из вне (на валидность) перед принятием решения.

кроме того тесты, действительно можно гонять, в свободное от вычисления, измерения и т.п. время

Контроль стека? Пришлось как-то такое делать. Стек (не всякий) имеет как верхнюю так и нижнюю границу. поэтому в каждой процедуре приходилось контролировать. Не помню уже причину

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

[Alf]

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

Например, в VAX-11 диагностика выглядела примерно следующим образом. Сначала запускался специальный консольно-диагностический процессор (КДП), задача которого - диагностика системы и диалог с оператором. Он производил простейшую самодиагностику (контрольная сумма ПЗУ, тест ОЗУ), после чего начинал диагностику остальных процессоров. Сначала тестировался центральный процессор (ЦП) - ему поочередно подсовывались микропрограммы различных тестов, он их выполнял и складывал результаты в регистры, доступные для чтения КДП. КДП сравнивал результаты тестов с эталонными и выносил вердикт о работоспособности ЦП.

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

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

Разумеется, при таком подходе делается 2 предположения:
1) КДП исправен.
2) Неисправность не возникла во время тестирования. Если мы протестировали микросхему, считаем ее исправной и используем для тестирования других узлов, а она в это время дала дуба, диагностика окажется недостоверной.

[Sla]

В теории это звучит приблизительно так

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

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

цитата отсюда h**p://www.stcraduga.ru/publication/3_st.htm

[Serg79]

С колегами договарились до того, что для начала следует проводить, при старте МК, проверку правельности выполнения всех "asm" команд и работоспособность его регистров.

[Alf]

На мини-ЭВМ подобная проверка выполнялась порядка часа. Вряд ли реально выполнять ее в полном объеме при каждом старте контроллера. Не думаю, что быстродействие контроллера выше на несколько порядков.

[Serg79]

На мини-ЭВМ подобная проверка выполнялась порядка часа. Вряд ли реально выполнять ее в полном объеме при каждом старте контроллера. Не думаю, что быстродействие контроллера выше на несколько порядков.

Нет, я не думаю что будет такое время выполнения. AVR семейства Mega содержит 133 команды и кварц на 14 МГц ну максимум 0.1сек ведь нужно установить сам факт правильности работы команды.

Вот пример проверки команд:
/* cli sei brid brie */
"sei \n\t"                 \
"brie i_1 \n\t"            \
"jmp stop \n\t"            \
"i_1: brid stop \n\t"      \
"cli \n\t"                 \
"brid i_2 \n\t"            \
"jmp stop \n\t"            \
"i_2: brie stop \n\t"      \

"jmp next \n\t"            \
"stop: nop \n\t"           \
"jmp stop \n\t"            \
"next: nop \n\t"
и так на основе проверенных проверять остальные.

Но если время будет действительно большим, надо будет придумывать уже что то другое.

[Alf]

Чтобы проверить, например, команду сложения, недостаточно выполнить ее только один раз. Ведь может оказаться битым разряд АЛУ. Так что нельзя, сложив 1+1 и получив в итоге 2, сделать вывод, что команда сложения исправна. Может оказаться, что в результате сложения, например, 5-й бит всегда равен 0, и наш единственный тест эту ошибку не выявит. Поэтому каждую команду следует тестировать много раз, с разными комбинациями данных. А это требует затрат времени. Например, при полном тесте байтового сложения мы имеем 64К комбинаций. Если же процессор умеет работать с 16-битными словами, то полный тест - безнадежная затея, нужно ограничивать число комбинаций операндов. Отсюда и берутся такие большие временные затраты на серьезные тесты.

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

[Serg79]

Да, задача действительно не простая.

Alf как думаешь, вот такая последовательность:

; регистры 8-разрядные
mov r0,0x00
add r0,0xFF
... и ...
mov r0,0xFF
add r0,0x00

Может выявить битый бит в АЛУ?

[Alf]

Такая - точно не выявит, потому что результат в обоих случаях 0xFF.

Даже если в ответ на любое сложение АЛУ выдает 0xFF, данный тест этого не выявит. Кроме того, в АЛУ может залипнуть в единицу любой бит, пара бит и так далее. Два сложения, которые оба дают все единицы, этот дефект не обнаружат.

Минимальный тест должен хотя бы проверить, что каждый бит способен установиться как в 0, так и в 1.

[Serg79]

Ну тут смысол был в то, что сначало из регистра в АЛУ загружается 0х00, а вовтором случае 0хFF.

А если добавить, к выше приведенному такое:

mov r0, 0x00
add r0, 0x00

то можно выявить покрайней мере грубое залипание НУЛЯ или ЕДЕНИЦЫ в АЛУ?

[Alf]

Грубое залипание выявишь. Но не выявишь, например, межбитовое замыкание. У тебя ведь во всех трех тестах результат - либо все нули, либо все единицы. Если, скажем, замыкают между собой биты 0 и 1, эти тесты не обнаружат дефект.

[Sla]

Точно договорились
Команд 133, а способов адресации?
С таким подходом к самодиагностике невозможно создать работающую систему. (имхо)
оно конечно можно
доверям mov
проверяем внутренние регистры
устанавливаем флаги
проверяем флаги
проверяем АЛУ
как проверить команды условного перехода? - проверять счетчик команд
идет сплошное зацикливание с доверием-недоверием. Имхо - в корне неверный подход.
Неужели до сих пор стоит актуальность проверки БИС программным способом?
Проще построить мажоритарную систему, чем тратить время на разработку софта самодиагностирования.

[Dimka]

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

Вот именно это мне и показалось странным, когда впервые прочитал тему. В каких задачах нужна такая паранойя? Может дешевле поставить 2-3 параллельных вычислительных узла и принимать решение голосованием...

[Alf]

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

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

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

[Serg79]

Может дешевле поставить 2-3 параллельных вычислительных узла и принимать решение голосованием...

Сдесь и всамом деле применяется два МК которые в паралель работают и после определенных команд сверяют свою работу и принимают решение о состоянии системы.

Но что бы они стали работать надо сначало провести тестирование внутренних узлов МК, сначало надо хотябы убедиться что правельно устанавливаются, сбрасываются флаги МК и выполняются команды условных переходов.
А также протестировать каректность работы АЛУ.

В идеале такие тесты надо проводить постоянно вовремя работы программы.

[Serg79]

Да Alf прав, если вводить дополнительные узлы проводяшие тестирование МК то как проводить уже их тестирование?

[Sla]

Если есть доступ к исходным кодам программ
строится некий "диагностический процессор" с выходом на шину адреса и шину данных
программа анализируется, "сворачивается" по определенным правилам, диагностическому процессору задаются временные метки. и тд
2 девайса не могут принимать решения. Подерутся. Два из трех, куда ни шло.

[Dimka]

Но что бы они стали работать надо сначало провести тестирование внутренних узлов МК, сначало надо хотябы убедиться что правельно устанавливаются, сбрасываются флаги МК и выполняются команды условных переходов.
А также протестировать каректность работы АЛУ.

Я не о том.

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

Собственно, голосование и есть тест прямо в процессе работы. Если нет единогласия - что-то сломалось. Одинаково одновременно сломаться врядли что-то может (по внутренним причинам).

Чем плохо (опуская вопрос стоимости)?

[Sla]

если проводить тестирование узлов МК, то надо проводить тест АЦП, ЦАП, регистров прерываний,ОЗУ, ПЗУ, таймеров
но не выполнение команд.
Если стоит задача по обеспечению безопасности работоспособности МК, то надо и выбирать соответствующие МК-производителей, с отлаженным ядром и пр.

[Sla]

Пренесли код на проверку, в котором был такой участок:

Код:

switch( mode )
{
   case NORM_MODE:
      shine = NORM_MODE_SHINE;
      break;

   case NIGHT_MODE:
      shine = NIGHT_MODE_SHINE;
      break;

   case WAR_MODE:
      shine = WAR_MODE_SHINE;
      break;

   default:
      return;
}

код изначально ущербен
Что все таки произойдет по default?
а вопрос о замене оператора неверен по своей сути.
177a:   81 30          cpi   r24, 0x01   

add   r24, r25  // сложение двух регистров
двоичное представление какое?
сколько единиц, нулей будет изменено?