Теория и практика защиты программ


         

Общее описание модели


Описание метода Нельсона приведем в соответствии с работой [ТЛН]. Для описания введем сначала следующие обозначения.

Совокупность действий, включающая ввод Ei, выполнение программы П, которое заканчивается получением результата F'(Ei) называется прогоном программы П. Необходимо также отметить, что значения входных переменных, образующие Ei, не должны все одновременно подаваться на вход программ П. Таким образом, вероятность P

того, что прогон программы приведет к обнаружению дефекта, равна вероятности того, что набор данных Ei, используемый в данном прогоне, принадлежит множеству Ee. Если обозначить через ne число различных наборов значений входных данных, содержащихся в Ee, то P=ne/N

- есть вероятность того, что прогон программы на наборе входных данных Ei, случайно выбранном из E среди равновероятных, закончится обнаружением дефекта. При этом R=1-P - есть вероятность того, что прогон программы П на наборе входных данных Ei, случайно выбранном из E среди априорно равновероятных, приведет к получению приемлемого результата.

Однако в процесс функционирования программы выбор входных данных из E обычно осуществляется не с одинаковыми априорными вероятностями, а диктуется определенными условиями работы. Эти условия характеризуются некоторым распределением вероятностей pi, того, что будет выбран набор входных данных Ei. Распределение P может быть определено через pi с помощью величины yi, которая принимает значение 0, если прогон программы на наборе Ei заканчивается вычислением приемлемого значения функции, и значением 1, если этот прогон заканчивается обнаружением дефекта. Поэтому

 - есть вероятность того, что прогон программы на наборе входных данных Ei, выбранных случайно с распределением вероятностей pi, закончится обнаружением дефекта. При этом R=1-P есть вероятность того, что прогон программы П на наборе входных данных Ei, выбранных случайно с распределением вероятностей pi, приведет к получению приемлемого результата.

Так как R - вероятность того, что единичный прогон программы не закончится отказом на наборе входных данных, выбранных в соответствии с распределением рi, то вероятность успешного выполнения п прогонов этой программы при независимом для каждого прогона выборе входных данных в соответствии с распределением Р



Содержание  Назад  Вперед