Елы-палы, если такая уж академическая задача - воспользуйся случаем, напиши свой дизасмик. Я щас изучаю один, но он под ia64, там все выровнено по 16. Оказалось не так сложно как думал поначалу.
Правда, в твоей задаче будет некоторая пробуксовка в начале анализа - ведь код может быть порезанный, придется тестить первые байты не менее 15 раз :)

А если внутри кода данные? Много данных?
Полноценный дизасм vs хорошее вероятностное распознавание...

Можно отдать код на съедение Ida, а затем смотреть процент fault - страниц

S_T_A_S_
попробовать искать в них опкоды, котрорые однозначно там не должны быть

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

Quantum
Я имел в виду опкоды push, retn, mov, int

Так такого добра будет полно даже в файле картинок...

Valery
Дизассемблер, при необходимости, я уже использую, но проблема в том, что даже в ассемблерном представлении я не знаю, как определить критерии корректности кода, чтобы реализовывать это в автоматическом режиме.

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

А если искать еще и некорректные последовательности?
Вроде (это плохие примеры) jmp а потом ret? Или mov reg,xx и xor reg,reg.

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

cucumber
[offtopic]
Профессия говорите? А я считал, что это диагноз для особо продвинутых пользователей, которым пишешь "Будьте любезны не выключать компьютер до завершения записи CD-R" а он возьмёт и на reset невзначай нажмёт, а потом матерится на кривость рук у программера.
[/offtopic]

Black_mirror
S_T_A_S_

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

В дальнейшем может что еще в голову придет:)

Orb
Все вышеперечисленные идеи можно заложить в нейросеть или просто в линейный алгоритм классификации с fuzzy logic. Даже если результаты не оправдают метод, с академической точки зрения можно будет сразу ставить высший балл ;-)

Второе (алгоритм классиф.) можно организовать следующим образом:

1. Определяем фильтры: F1,F2,...,Fn
F1 может быть наличие/отсутствие валидных инструкций;
F2 пусть будет нарушение стека (вроде большего кол-ва push, чем pop и/или add/sub esp,N и т.д.)
F3 может быть некоторый коэффициент энтропии.
...
Fn
2. Фильтры можно реализовать по принципу float Fn(void* data), где data является указателем на входные данные (файл), а возвращаемое значение определяет fuzzy-оценку Fn {принадлежность к интервалу} [0,1]. Вместо float можно использовать целочисленную оценку, т.е. чем выше балл, тем по мнению фильтра данный файл больше похож на исполнимый.
3. Общая оценка вычисляется по формуле R = F1 and F2 and ... and Fn. AND (и/или OR) в данном случае являются fuzzy-операторами. Например:

0,3 AND 0,7 = 0,3;
0,1 OR 0,9 = 0,9;

В данном случае использован принцип MIN/MAX, хотя существуют и более эффективные методы. Вместо знака равенства следует понимать равенство по определению (не нашёл этот символ).

4. Если конечный результат R > 0,5 следует понимать, что файл скорее всего исполнимый.

Точность данного метода теоретически можно довести до абсолютной.

2Quantum не лень тебе было такую пургу набирать?
для такой задачи fuzzy logic и нейросети скажут такую же информативную оценку как средняя температура по больнице

cucumber

А ты не квакай, а что-то сам умное предложи.

переборная задача у которой два параметра:
p1. количество команд процессора
p2. размер программы
аб чем тут можно говорить ?
как вообще такой вопрос можно поднимать?
никто не писал переборов?

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

Действительно сложно что-то предложить. Я, например, так и не понял, чего же Orb хочет на самом деле.

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

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

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

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

Orb

Расскажи всё-таки, что же тебе на самом деле нужно.

Если ты пишешь валидатор com-файлов, то это нереально. Ели бы таковые существовали, то, может, и винда бы не глючила. ;)

Если ты пишешь распознаватель типов файлов по содержимому, и тебя интересует оценка типа "на что этот файл больше похож", то, мне кажется, что ты подходишь к этому не стой стороны. Для подобных вероятностных определений, больше подходят всё-таки статистические методы. Какие-нибудь марковские цепи высоких порядков, или ещё что-нибудь в этом роде, типа контекстных деревьев. Я в этих вещах разбираюсь слабо, но, по-моему, это может помочь. Идея в том, чтобы собрать большую статистику вероятностей появления последовательных цепочек символов в различных типах файлов, а потом, посчитав её же для конкретного файла сравнивать, к какому типу он ближе. От распознавания по сигнатурам это отличается тем, что оцениваются вероятности всех сигнатур сразу, а от статистических выборок по одному-двум символам, как в той статье, на которую ты давал линк, тем, что одним-двумя символами анализ не ограничивается.
В принципе, этот подход гарантированно сработает, вопрос в том, сколько тебе придётся собирать статистики, и сколько это потребует ресурсов. ;) Хотя, в наше время персоналок с гигабайтом оперативки, последнее уже не такая и проблема. ;)
Опять же, никто не мешает добавить к нему некоторое количество эвристик, в основном это имеет смысл для обработки не учитываемых этими методами данных, например, позиции в файле, или внутренних взаимосвязей в данных (типа кроссрефов).

cucumber
Сразу видно, что с fuzzy дело не имели.

bsl_zcs
Универсального решения действительно нет. Поэтому AI - самое то. Меня сильно удивляет ваша позиция в данном вопросе.

2 All
Между прочим, знакомый доцент (не я) совсем недавно получил премию за формулировку/воплощение вышеописанного метода. Более детально я его описывать не могу, по понятным причинам, но думаю, что того, что я написал достаточно для данного конкретного случая. Вся хитрость в наиболее точном определении формулы для R. Точность в подобных случаян именуется fitness и существуют мат. методы оптимизации фитнеса, но в данном случае ими вполне можно пренебречь (не докторскую пишем :-).

Чтоб не быть голословным:
Одна из реализаций данного метода