Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 13

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

Иными словами, нужно гарантировать, что произойти могут только предусмотренные события. Это не позволит нечистому на руку пользователю украсть деньги у других или их "напечатать". В конце раздела приводится очень простой пример (плохого) протокола расчета электронными деньгами, моделируемого конечными автоматами, и показывается, как конструкции на основе автоматов можно использовать для проверки протоколов (или, как в нашем случае, для поиска в протоколе изъянов).

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

Кроме того, клиент имеет возможность отменить свой файл, т.е. попросить банк вернуть деньги на свой счет, причем они уже не могут быть израсхо- ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ 54 дованы. Взаимодействие трех участников ограничено, таким образом, следуюшими пятью событиями. 1. Клиент может совершить опяату (рау) товара, т.е. переслать денежный файл в магазин. 2. Клиент может выполнить отмену (сапсем денег. Они отправляются в банк вместе с сообшением о том, что их сумму следует добавить к банковскому счету клиента. 3. Магазин может произвести доставку 1зй~р) товара клиенту. 4. Магазин может совершить выкуп (греет) денег.

Они отправляются в банк вместе с требованием передать их сумму магазину. 5. Банк может выполнить перевод (ггап~ег) денег, создав новый, надлежашим образом зашифрованный, файл и переслав его магазину. 2.1.2. Протокол Во избежание недоразумений участники должны вести себя осторожно. В нашем случае мы резонно полагаем, что клиенту доверять нельзя. Клиент, в частности, может попытаться скопировать денежный файл и после этого уплатить им несколько раз или уплатить н отменить его одновременно, получая, таким образом, товар бесплатно. Банк должен вести себя ответственно, иначе он не банк. В частности, он должен проверять, не посылают ли на выкуп два разных магазина один и тот же денежный файл, и не допускать, чтобы одни и те же деньги и отменялись, и выкупались.

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

Оказывается, важно не то, кому именно позволено вызывать эти события, а то, какие последовательности событий могут произойти. На рис. 2.1 участники представлены автоматами. На диаграмме показаны лишь те события, которые влияют на того или иного участника. Например, действие оллшла влияет лишь на клиента и магазин. Банк не знает о том, что клиент отправил деньги в магазин; он узнает об этом, когда магазин выполняет действие выкуп. Рассмотрим вначале автомат (а), изображаюший банк. Его начальное состояние— зто состояние 1. Оно соответствует ситуации, когда банк выпустил денежный файл, о котором идет речь, но еще не получил требования на его вылул или отмену.

Если клиент 2.1. НЕФОРМАЛЬНОЕ ЗНАКОМСТВО С КОНЕЧНЫМИ АВТОМАТАМИ бб посылает в банк запрос на отмену, то банк восстанавливает деньги на счету клиента и переходит в состояние 2. Оно представляет ситуацию, в которой деньги возвращены клиенту. Поскольку банк в ответе за свои действия, то, попав в состояние 2, он уже не покидает его.

Этим он не позволит клиенту вернуть на свой счет с помощью оттнены или израсходовать те же самые деньги. 1 ставка отмена отмен Начало б) клиент Начало в) банк Рис. 2!. Конечные аетолеаты, лредетаоляющие клиента, магазин и банк С другой стороны, находясь в состоянии 1, банк может получить от магазина требование вылуаа денег. В этом случае он переходит в состояние 3 и тут же отправляет магазину сообщение о аереваде, в котором содержится новый денежный файл, принадлежащий уже магазину. Отослав это сообщение, банк переходит в состояние 4. В этом со- стоянии он не принимает запросов на ашнену или выкуп денег, равно как не совершает никаких других действий с этим конкретным денежным файлом. Рассмотрим теперь автомат на рис.

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

ГЛАВА 2. КОНЕЧНЫЕ АВТОМАТЫ друга. Тогда доставка может быть выполнена до, во время или после выкупа электронных денег. Придерживаясь такой политики, магазин рискует попасть в ситуацию, когда товар уже доставлен, а деньги, как выясняется, поддельные. Магазин начинает в состоянии а. Когда покупатель заказывает товар, выполняя оплату, магазин переходит в состояние Е В этом состоянии магазин начинает одновременно два процесса: доставку товара и выкуп денег. Если первым заканчивается процесс доставки, то магазин переходит в состояние с, в котором он еще должен осуществить выкуп денег и получить перевод эквивалентного денежного файла из банка.

Магазин также может сначала отправить в банк запрос на выкуп денег и перейти в состояние д. В состоянии д магазин либо доставит товар и перейдет в состояние е, либо получит из банка денежный перевод и перейдет в состояние Г'. Следует ожидать, что в состоянии / магазин в конце концов доставит товар и перейдет в состояние я. В последнем случае сделка завершена, и ничего больше не происходит. В состоянии е магазин ожидает перевода денег из банка. К сожалению, может получиться, что магазину не повезет: товар он доста- вит, а денежного перевода так никогда и не получит.

Рассмотрим, наконец, звтомат на 2.1, б, изображающий клиента. У этого автомата есть только одно состояние, отражающее тот факт, что клиент может делать все, что угодно. Он может выполнять оплату или отмену сколько угодно раз и в любом порядке. При этом после каждого действия он остается в своем единственном состоянии. 2.1.3. Возможность игнорирования автоматом некоторых действий Тройка автоматов на рис. 2.! отображает поведение участников независимо друг от друга, однако некоторые переходы в автоматах пропущены. Так, сообщение об отчеие де- нег не затрагивает магазин, и если клиент отменяет деньги, то магазин должен оставаться в том же состоянии, в котором находился. Однако согласно формальному определению конечного автомата, которое мы рассмотрим в разделе 2.2, если на вход автомата подается Х, то он должен совершить переход по дуге с меткой Х из текущего состояния в некоторое новое. Следовательно, к каждому состоянию автомата для магазина нужно добавить еще одну дугу с меткой отчеиа, ведущую в то же состояние.

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

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

Поскольку это состояние не имеет выходящей дуги с меткой оплата, то автомат, изображмоший магазин, умрет прежде, чем получит перевод из банка. Итак, к некоторым со- 2,Ь НЕФОРМАЛЬНОЕ ЗНАКОМСТВО С КОНЕЧНЫМИ АВТОМАТАМИ отмена оплата, отмена оплата, отмена оплата, отмена оплата, отмена оплата, отмена оплата, отмена оплата, доставка доставка, выкуп, перевод, оплата, отмена ыкчп, осгавка оплата, доставка Начало б)клиент Начало в) банк Рис 22 Полные множества переходов для трех автоматов 1.