bsl_zcs
Зря ты. Он, в принципе, прав. Притом, в обеих репликах в этом топике. Сейчас увидел третью, в ней уже нет. ;)

Здорово. Рад тебя видеть. С возвращением.
Теперь к делу. Я не согласен с тобой. Когда я готовил доклад о применении NN в предсказании вторичной и выше структуры белков мы с Fixer'ом много обговаривали те области, где можно и где не можно применять NN. Так вот, если ты не в силах четко сформулировать условие и даже статистический анализ тебе не дает явной корреляции или разбиения на признаки, единственное, что остается - это NN и что-нибудь из AI, например, тот же fuzzy logic, предложенный Квантом.

2volodya
проблема выполнимости КНФ
достаточно четко сформулированное условие?
и что из этого? легче дышать стало?
проблема выполнимости КНФ - фундаментальная проблема ИИ.
Quantum ее решил? Поздравляю. (Бурные продолжительные аплодисменты)

cucumber
Если вы имеете в виду конъюнктивную нормальную форму, то боюсь, что она не применима в данном случае, да и проблема совсем не в вычислении fuzzy-функции, а в её оптимальной формулировке, вместе с так называемыми фильтрами (см. выше). Короче, чем больше фильтров (F1, F2, ..., Fn), тем сильнее потенциал классификатора, но и тенденция к ошибке может серьёзно возрасти. Поэтому нужен баланс.

Quantum
Все вышеперечисленные идеи можно заложить в нейросеть или просто в линейный алгоритм классификации с fuzzy

При вычислении комплексного значения оценки "исполняемости" я использовал результирующее значение каждого этапа проверки (фильтра) и вычислял обычное среднее (f1+f2+...fn)/n, Для использования нечетких вычислений я предпосылок не нашел, т.к. результатом работы каждого фильтра является всего лишь "коэФфициент" удовлетворения фильтрующему условию, а не классическое нечеткое число. Хотя, конечно, возможно, что применение нечетких чисел могло более точно отразить результаты. Я, к сожалению, не смог посмотреть приведенную ссылку (сервер недоступен).
Что касается сети, то вариант я обдумывал давно, но так как имею не особо большой опыт в их проектировании, то возникли следующие вопросы:
- Какую организацию выбрать (тип, количество слоев)
- Что все же подвавть на вход (каким образом формировать входные вектора)
- и вообще, насколько адекватно применение сети для такой задачи (не получится ли, что такие же результаты можно будет тостигнуть путем применения тех же вероятностных фильтров)

bsl_zcs
Еще раз о задаче: Практическая сторона подразумевает создание программы, которая при наличии входного файла смогда бы ответить на вопрос "с какой вероятностью этот файл является корректно исполняемым". При этом подразумевается, что анализ не учитывает неправильную семантику программы, к только "правильную исполняемую структуру". Кроме того, все файлы - реальные, и поэтому большую часть можно определить по формату (EXE например), и, соответственно выяснить и точку входа и режим работы. Проблема появляется с теми файлами, которые не имеют какой либо форматирующей информации, например COM файлы.
Использование тех же марковских цепей насколько я понимаю, продразумевает определение как промежуточных состояний при анализе (+их вычисление из исходного файла), так и вычисление вероятностей перехода в них, а это само по ебе является давольно нетривиальной задачей и будет подразумевать создание еще одной, и не самой простой, программы для автоматического создания такой матрицы переходов (хотя может я все слишком усложняю).

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

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

Orb
Да, что-то с нашим сервером :( Если что, могу намылить этот документ (53Кб)

Orb
я уже перестал понимать о чем речь идет. Ты хочешь прокупоросить файл, а потом выдать мессагу "Вы можете попытаться запустить это. Кто не спрятался - я не виноват"?
Великая цель, нечего сказать.

конкретное предложение: берем два архива sfx и обыкновенный среднего размера. Разница между ними небольшая, но принципиальная. Все линейные алгоритмы пролетают сразу. В идеальном случае fuzzy функция Quantuma даст вероятности 51 и 49% (вместе как раз 100 :) Очень замечательно :(. Пример вроде не сильно искусственный, вполне обыденный, но нерешабельный.
Отсюда мораль: без исследования дерева эту задачу можно решать путем подбрасывания монетки и ни о каких 100% и не мечтай и думать забудь.
Так что перебор forever.

cucumber

И что именно ты собрался перебирать, если не секрет?

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

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

Кроме того, он же пишет, что файлы реальные, поэтому, всяких замороченных файлов, специально чтобы он обломился (типа тех, что перечислил я, или указал ты), ему никто подсовывать не будет. В свете его последних высказываний, мне представляется вариант применения типа “взять каталог Windows и найти в нём все исполнимые файлы”.


Quantum

Насчёт твоего предложения использовать нечёткую логику в этой задаче – она здесь практически неприменима. Получаемый Orb-ом "коэффициент" удовлетворения фильтрующему условию вполне можно трактовать как нечёткую логическую величину, дело в другом – используемые им фильтры разрозненны и не связаны между собой. Выражение, которое ты обозначил как R, но сути является математической моделью обсчитываемой системы, в данном случае выполненной на нечёткой логике. Оно должно отражать все взаимосвязи всех учитываемых факторов. При полном отсутствии этих взаимосвязей, оно вырождается вплоть до перечисления всех полученных коэффициентов через какой-нибудь AND – то есть, до банального накопления вероятности. А оно, в свою очередь, в той или иной форме у Orb-а и так присутствует, поскольку на выходе он получает всё-таки одну вероятность.

Как ты очень верно заметил, при любом моделировании, вся хитрость заключается в наиболее точном определении матмодели. Правда, математических методов “оптимизации её фитнеса”, как я понимаю, ровно два: исправление матмодели и дополнение матмодели. ;)
Я имею ввиду, что для получения сколько-нибудь практически ценных результатов, причём, не на макетах, а на реальных объёмах информации, модель должна быть построена аналитически, то бишь, вручную. Пользуясь априорными сведениями о характере моделируемой системы, можно создать куда более оптимальную модель, чем посредством перебора или ещё какой полуэмпирики.

Поэтому, тот документ, на который ты давал ссылку, мне представляется намного обогнавшим своё время. :) То есть, при нынешнем уровне развития техники, практических результатов от описанных методов добиться сложно. ;)
Впрочем, fuzzy logic, там касается только введение на одну колонку. В остальном, там описывается автоматизированное построение матмоделей посредством генетических алгоритмов. Притом, генетика там простенькая, без каких-либо наворотов. А в качестве основной инновации там преподносится хитрый способ сериализации дерева разбора выражения, с целью сделать его пригодным для рекомбинации. Причём, я бы порекомендовал вместо этого банально использовать обратную польскую нотацию. ;) Кстати, если ты общаешься с авторами этого труда, можешь им об этом намекнуть. :)

Да, ещё маленькая личная просьба: не стоит ко мне обращаться на “вы”. В конце концов, я ещё не старик. (с) Чиж, кажется...


volodya

Привет тебе тоже. И всем остальным на форуме привет.

если ты не в силах четко сформулировать условие и даже статистический анализ тебе не дает явной корреляции или разбиения на признаки, единственное, что остается - это NN и что-нибудь из AI

А на что следует натаскивать нейросеть, когда ты не в силах четко сформулировать условие? Типа: “Угадала? А хрен его знает.” ;)

Ладно, это я глумлюсь. ;) Другой вопрос, в том, действительно ли для этой задачи условия неформализуемы, и так ли здесь бесполезен статистический анализ.

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

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

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


Orb

Если и усложняешь, то не слишком. Как я понимаю, эффективно реализовать нормальное контекстное дерево на самом деле достаточно сложно. :( Поэтому, если тебе это может пригодиться только как ещё один фильтр для com-файлов, лучше действительно не заморачиваться на его реализацию в полном объёме.

С другой стороны, если собрать достаточное количество статистики, этот метод мог бы решить задачу полностью самостоятельно. В собранной статистике осели бы и хедеры exe-файлов, и таблицы импортов, и типовые занесения параметров в регистры с последующим вызовом int 21h, и стандартные прологи и эпилоги функций у различных компиляторов, и команды с префиксами смены сегмента или размера операнда, и многое другое.

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

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

перед тем как решать задачу нужно определить ее сложность и постараться свести к решенным, а орба заклинило на линейном алгоритме.
в простейшем случае это задача выполнимости КНФ. (это параметр 2).
У Орба она осложняеся небулевостью задачи. Т. е. нужно строить опупеннейшую грамматику (это параметр 1 ). т.е. программно реализовывать функции процессора (сколько там миллионов транзисторов?) :((((((((
Чтоб вам стало совсем грустно можно вспомнить Тьюринга с его недетерминированными машинами.
А рассуждаю я об этом, потому что коробит от таких распознавателей, у которых точность всегда почему-то 100%

bsl_zcs
Теперь совсем другое дело! Спасибо, что уделил время анализу моих умозаключений.

Насчёт твоего предложения использовать нечёткую логику в этой задаче – она здесь практически неприменима. [...]
Вполне возможно, что стат. анализ и/или NN покажут лучшие результаты, чем мой классификатор. Это можно достоверно установить только перепробовав все 3 или более методов, но суть не в этом. В общем, я и не утверждал, что предложенный мною метод лучше - это был просто ещё один неординарный вариант решения задачи. А вот эффективность данного метода, IMHO, всё равно может оказаться довольно высокой (я всё ещё верю в 100% точность :-), хотя достичь подобных результатов, возможно, проще другими методами (вроде предложенного тобой статистического с сигнатурами).

Впрочем, fuzzy logic, там касается только введение на одну колонку.
Отнюдь, просто авторы используют упрщённую модель нечёткой логики (вроде упомянутого раннее MIN/MAX), но весь метод тесно связан с fuzzy, особенно четверичная логика для подсчёта фитнеса.

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

Причём, я бы порекомендовал вместо этого банально использовать обратную польскую нотацию. ;)
Изначально использовались выражения infix (со скобками), но авторы решили усложнить мне задачу и перешли на operator-precedence а я так и не понял зачем :-)

Кстати, если ты общаешься с авторами этого труда, можешь им об этом намекнуть. :)
Я им намекал уже неоднократно и напрямую заявлял, а они упёрлись и хоть ты тресни ;-)

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

Это не по-дзенски :)

volodya
Понимаю.

Идет девушка, видит: парень в противогазе косит траву.
- Ты чего в противогазе-то? Сними - будет легче косить.
- Я коммунист! Я не могу без трудностей!

cucumber
Я понимаю, что решение этой задачи не самое простое и уж тем более не 100% точное, но все равно, надо искать пути приближения к идеалу.

bsl_zcs
Спасибо за столь развернутый ответ! Действительно, сигнатуры наиболее часто встречающихся конструкций могут помочь повысить точность распознавания. Этот вопрос я оставлю на будущую проработку... Сейчас же занимаюсь добавлением фильтра, позволяющего выявить правильность обработчиков параметров, переданных при вызове прерываний. Для этого пытаюсь отследить значения регистров в точке вызова. Одновременно с этим (все равно тот же анализ команд) пытаюсь отследить валидность стека. Мне кажется это должно дополнительно помочь выявлять исполняемые куски кода.
Теоретически такой дополнительный анализ может позволить справляться с теми же sfx-архивами, предложенными cucumber. Файл разбивается на части, смотрится статистика по каждой из них... Если для нескольких частей статистика не равномерна, + в одной из этих частей точка входа, то уже можно проведя анализ таких частей с помощью той же проверки параметров прерываний/вылидности стека/правильности инчтрукций и переходов (рассматривая дерево исполнения начиная от точки входа), можно делать вывод о принадлежности файла к sfx.

Quantum
Спасибо за ссылку на статью. Наконец то нашел, посмотрел...