Нахождение полутени проблемы удовлетворения ограничений

12

Следующий вопрос неоднократно возникал при тестировании безопасности системы или модели.

Мотивация: недостатки безопасности программного обеспечения часто возникают не из-за ошибок из-за допустимых входных данных, а из-за неправильных входных данных, которые достаточно близки к допустимым входным данным, чтобы пройти многие из простых проверок достоверности. Классическим примером, конечно, является переполнение буфера, когда ввод является разумным, за исключением того, что он слишком велик. Компиляторы и другие инструменты могут помочь решить эти проблемы, изменив компоновку стека и кучи и используя другие методы запутывания. Альтернативой является удаление проблем из самого исходного кода. Один из методов, называемый фаззингом, бомбардирует программу с входами, близкими к ожидаемым, но в некоторых местах необоснованными (большие значения для целочисленных или строковых полей). Я хотел бы понять фаззинг (в качестве одного примера) с более формальной точки зрения.

Предположим, что пространство действительных входов описывается ограничениями Φ . Пусть M - множество решений таких ограничений, а именно M={mM | mΦ} , где M - пространство возможных входов.

Я ищу работу, описывающую следующие понятия:

  • MMMmM mΦ MM

  • Способы ослабления ограничений to , так что, во-первых, и , в некотором смысле, являются синтаксической полутенью .ΦΦΦΦΦ¬ΦΦ

«Пенумбра» - это слово, которое я выбрал, чтобы описать концепцию. Это вполне можно назвать чем-то другим.

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

Кто-нибудь может пролить свет?

Дэйв Кларк
источник
Проблема сама по себе действительно интересна, однако большую часть времени интересует не создание полутени (я не знаю более «официального» названия), а скорее запутывание техник, которые избегают атак на программные атаки (таких как атаки через модификацию). вход). Эти методы скрывают ядро ​​поведения программы, наводняя ее чем-то другим. Например, вы можете создать программу, чередуя исходную программу с программой, которая жестко закодирует решение сложной проблемы NP на конкретном экземпляре.
Сильвен Пейроннет
Это действительно так. Я намекаю на подход, известный как фаззинг.
Дэйв Кларк
Кстати, CSP = проблема удовлетворения ограничений.
MS Dousti 7.10.10

Ответы:

6

Большая часть внимания, уделяемого вариантам оптимизации проблемы удовлетворения ограничений (CSP), была сосредоточена на удовлетворении некоторого числа ограничений (MAX-CSP) или в булевом случае при выборе решения, которое назначает как можно большему числу переменных значение 1 ( MAX-ONES, есть также MIN-ONES).

Вместо этого вы спрашиваете о варианте, который может называться MAXIMUM PARTIAL CSP. Это было изучено, по крайней мере, еще в конце 1960-х годов, но я не знаю, что у него есть устоявшееся имя. Это естественная проблема, и было бы неплохо увидеть больше работы по ее исследованию. Спасибо за предоставление еще одного потенциального приложения для этой проблемы!

  • Эмблер, А. П. и Барроу, Х. Г. и Браун, С. М. и Бурстолл, Р. М. и Попплстоун, Р. Дж., Универсальная система для сборки с компьютерным управлением , Искусственный интеллект 6 129–156, 1975. doi: 10.1016 / 0004-3702 (75) 90006- 5

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

Один из способов выразить проблему оптимизации заключается в следующем.

МАКСИМАЛЬНАЯ ЧАСТИЧНАЯ CSP:
Вход: экземпляр CSP
Выход: prop Критерий: максимизироватьf
|f|

В случае с переменными очевидно, что опора мощности будет решением. Могут существовать большие реквизиты, с количеством элементов до , которые не содержатся ни в одном решении.nnn1

В предложенной вами терминологии набор подпорок с максимальной мощностью образует полутень, возможно, даже с некоторой дополнительной свободой (таким образом, количество элементов не менее ).kdkd

Вторая часть вашего вопроса также кажется очень интересной, но я не знаю ни о какой работе, связанной с этим.


Сноска: термин опора взят из моего тезиса; оно предназначено для передачи идеи о том, что такие частичные назначения являются правильными, а также что они поддерживают набор решений. Это в отличие от nogood , который является общепринятым термином для описания частичного присвоения, которое не может быть распространено на решение. Слово «nogood» было введено Ричардом Столменом и Джеральдом Суссманом в 1976 году, когда RMS все еще был исследователем ИИ, а не активистом свободы программного обеспечения.

  • Столлман, Ричард М. и Суссман, Джеральд Джей, Прямое рассуждение и обратное отслеживание в зависимости от системы автоматизированного анализа цепей , Лаборатория искусственного интеллекта MIT № 380, 1976. ( PDF )
Андраш Саламон
источник