Разорвать граф.

Тема в разделе "WASM.A&O", создана пользователем Clerk, 11 сен 2010.

  1. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    wsd
    улыбнуло. нет ничего объяснимее математики.
    доказательства осуществимости выполняются при наличии результатов поиска этих доказательств.
    в то самое время, пока вы будете искать доказательство, кто-то уже реализует план действий.
    но это не означает, что искать доказательства не надо. искать доказательства надо для того, чтобы что-то понять, и иметь это доказательство для выполнения задачи осуществимость.
    Clerk
    ...
    2. Размер инструкций. Зададим размер наибольшей ветви равным 2 байта (максимально получается две ветви). Тогда:
    а) Инструкции с данными -- опкод_инструкции + данные -- 1 + 1 байт;
    б) Инструкции без данных -- 1 байт;
    Прямой перебор 2х байтовых инструкций, прямой перебор однобайтовых инструкций.
    ...
     
  2. wsd

    wsd New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2007
    Сообщения:
    2.824
    Clerk
    о каком размере кода вообще речь?
    хотябы для начала прототип с избытком мусора сделать, а потом усовершенствовать
    итеративная разработка так сказать)
     
  3. wsd

    wsd New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2007
    Сообщения:
    2.824
    t00x
    у Вас базовые элементарные знания матана имеются?
    если есть 20 ячеек под команды и есть 30 разных команд какое кол-во вариантов?
    30^20? не?
    сколько его генератор будет брутить варианты?
    а если кода килобайт будет?
     
  4. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    wsd
    не вдаваясь в подробности, здесь предпочтительнее "теория вероятностей" переходящая в "сложность операций".
    ТЗ у Вас отсутствует, цифры с лампочки, суть метода Вы не уловили. Ключевое слово -- "Размер инструкции".
     
  5. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    TermoSINteZ
    t00x
    Спасибо за ответ. Подумаю над этим.
     
  6. kaspersky

    kaspersky New Member

    Публикаций:
    0
    Регистрация:
    18 май 2004
    Сообщения:
    3.006
    Clerk
    > Такой вопрос. Допустим имеется код начиная с адреса Ip. Это будет первая ветвь.
    видел такое несколько раз в малвари. причем непохоже что делали руками. выглядит очень интересно. там тысячи команд и все они перекрываются. ида сходит с ума. но лог трассировки все показывает. правда в этом логе глубокие циклы, так что лог приходится обрабатывать скриптами.

    конкретного примера под рукой нету. но это вроде бы широко известный прием обфускации. там получается примерно так:
    l_1:
    add eax, XXXX
    xor eax, YYYY
    JNZ L_1 + 1

    после прыжка видим:
    L_2:
    sub al, 40
    jnz L_2 + 1

    после прыжка видим
    l3:
    inc eax
    jnz l3

    и дальше продолжается код который шел за JNZ L_1 + 1. и этот код как нетутрдно догаться, использует значение eax.

    причем там можно еще и ветвление за пределами блока устроить.... да много что можно сделать... вопрос - кого оно обломает?
     
  7. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    kaspersky
    Парсер создающий граф обламает, тоесть любой дизассемблер. Для этого достаточно только одной инструкции в ветви. Но интересна задача в целом.
     
  8. wsd

    wsd New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2007
    Сообщения:
    2.824
    Крис так, это другая история.
    Клерку надо скрестить функционал, а не заобфусцировать значения eax.
    вообше задача интересная. возможно ли вообще три пути с насыщенным функционалом сделать Ip, Ip+1, Ip+2 ?
     
  9. asd

    asd New Member

    Публикаций:
    0
    Регистрация:
    12 мар 2005
    Сообщения:
    952
    Адрес:
    Russia
    Чтоб не обломился, надо всего лишь помечать начала инструкций, по которым проходим, тогда при повторном попадании на один и тот же диапазон адресов парсером, станет ясно, что к чему.
    Имхо сложность разработки парсера, который на этом не обломится намного меньше сложности создания такого кода. Хотя задача, конечно, достаточно интересна.
     
  10. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    asd
    В этом случае построение графа завершается, так как g = f(p), а для p код описан уже. В этом случае придётся вводить виртуальные адреса. Это нигде не реализовано.
    wsd
    Возможно, хотя маловероятно. По большей части там будет мусор, так как размер инструкции ограничен(число возможных опкодов). Вручную данная задача видимо не решается, так как очень сложна.
     
  11. kaspersky

    kaspersky New Member

    Публикаций:
    0
    Регистрация:
    18 май 2004
    Сообщения:
    3.006
    Clerk
    wsd
    > Но интересна задача в целом.
    ну давайте чисто математически сначала решим задачу двух перекрывающихся команд, таких чтобы ep+1 и ep давал осмысленный код. нам известный опокоды всех инструкций и потому если записать опкод как x1...xn, то из всех x1...xn достаточно выбрать x2...xn-k. задача решается табличным способом очень просто. и мы получаем кучу разных cmd1-cmd2 из которых можно выбирать нужные пары при генерации кода. (попутно: x1...xn может быть и не одной командой, а несколькими)

    если на размер кода нет жестких ограничений, то кодогенератор для двух-трех путей я бы написал без труда (кодогенатор это когда берем произвольный входной код А и автоматом превращаем его в "трехпутевой" код Б), причем если использовать предложенную табличную методику, выбирая случайную пару команд из числа возможных, то обратное пеобразрвание провести будет труднее.

    но даже по скромным прикидкам данная метода даст разбухание кода в несколько раз даже при двухпутевом коде. пока у меня получается что ..xn и y1... (где y1 - начало следующей команды) должны реально улетают в мусор, ибо произвольные команды не спариваются и их приходится дополнять мусором. ну что-то jz xxx, который не исполняется, таким образом мы можем брать любой y1.
     
  12. kaspersky

    kaspersky New Member

    Публикаций:
    0
    Регистрация:
    18 май 2004
    Сообщения:
    3.006
    Clerk
    > Возможно, хотя маловероятно. По большей части там будет мусор, так как размер
    > инструкции ограничен(число возможных опкодов). Вручную данная задача видимо
    > не решается, так как очень сложна.
    например, можно в уже существующий поток инструкций вклинвать команды типа XOR EAX, imm32, тогда у нас есть три байта. последний байт уйдет на jmps и байт следующей инструкции используется как целевой адрес. но это уже совсем тривальный подход.
     
  13. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    (эскузи, не вникал в подробности предыдущих постов, посему допускаю повторения)

    итак, как бы я это делал, если бы я это делал.

    (п-код == промежуточный код. нужен код попроще, покрупнозернистее и без особого изобилия команд и вывертов)

    подготавливаем отдельные таблицы:
    1) машкод -> назначение + регистры (напр. mov eax, ebx)
    2) назначение + регистры -> варианты реализации в машкоде/п-коде с указанием границ команд/п-кодин.
    3) список возможных вариантов и генераторов нопов.
    4) п-кодина -> варианты реализаций в назначениях/п-кодах. опять же с указанием границ отдельных назн/п-к

    1. для начала отдельные ветки компилируем в п-код.
    2. берем очередную п-кодину.
    3. переводим по таблицам 4 и 2 в очередные машкода. пишем в буфер (с разделением по комадам)
    4. сдвигаемся в нужный адрес, меняем ветку.
    5. берем очередную п-к из очередной ветки.
    6. читаем начало машкода (хвост предыдущего).
    7. по таблице 1 находим какие назначения это могут быть.
    8. то таблице 4 пробуем подобрать машкодину к нужной п-к.
    9. если не получается - по таблице 3 пробуем подобрать ноп.
    10. если и тут ничего, пробуем двигаясь назад менять команды, если проскакивал выбор.
    11. если опять ничего - месаж("ваша мутка неслабо перемучена. в будующуем мы може ее и разрулим. если вы пришлете нам ваш глючный сэмпл - мы можем попробовать предложить вам следующую версию со скидкой 5%")
    12. если все получилось и команда вставилась - гото 5.

    гдето так, если я не ошибся.

    (хотя, я бы не брался. слишком много мороки уже на составлении таблиц, тк х86 машкод состоит больше из исключений. а без них не выйдет в любом случае)
     
  14. 100gold

    100gold New Member

    Публикаций:
    0
    Регистрация:
    26 фев 2010
    Сообщения:
    165
    1. Придумать\взять готовую виртуальную машину с наиболее простым+удобным+небольшим набором команд.
    2. Транслировать исходный код в ассемблер для этой виртуальной машины.
    3. Создать таблицу соответствия х86 ассемблера и пар команд для VM. Т.е. если обозначить множество команд VM как S, то будет матрица перехода [S,S,Delta], где первые две размерности определяют команды из первой и второй нити соотв, а дельта это смещение второй нити относительно первой(т.е. "1" в самом начале). Совершенно необязательно, чтобы в ячейке матрицы была ровно одна команда х86 ассемблера.
    4. Теперь пользуясь полученной матрицей создать х86 код будет достаточно просто.
    ...
    Очевидно, самый сложный пункт здесь это 3. Генерить матрицу можно:
    1. Вручную
    2. Полным перебором
    3. Использовать генетические алгоритмы, это немного сократит перебор
    Вероятно часть ячеек заполнить не удастся, тогда можно модифицировать код на ассемблере для VM чтобы обойти проблемные места.
     
  15. IceCrashLdr

    IceCrashLdr New Member

    Публикаций:
    0
    Регистрация:
    29 июн 2010
    Сообщения:
    193
    Думаю стоит попробовать решать задачу в лоб, изначально не вдаваясь в детали инструкций.
    У вас должны быть две ветви(возможно больше) машинных инструкций.
    Можно сделать "bindiff" на массивы байт. В итоге должен получится граф. Схожие байт будут ребрами, создавая ребра, не байт которые не попали в граф, надо будет выравнивать. Вот как выравнивать...
    Но скорее всего это добавит много мусора.
    Хотя и анализ "bindiff" должен быть давольно таки мощным что бы находить такую разницу, как построения синусоиды и косинусоиды(с одной стороны графики имеет обсолютно разные точки, с другой стороны нужен только сдвиг).
     
  16. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Проблема в том, что предыдущий байт это функция от следующего, а следующий от предыдущего, причём это определяет формат инструкций и их набор. Таблиц явно не достаточно. Темболее регистры и операции явно не задаются.
     
  17. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Clerk
    Если использовать полезные команды длиной не более 3х байт и сильно разбавлять мусором, то шаблон
    NN 11 11 11 NN 22 22 22 NN 11 11 11 .... можно продолжать бесконечно долго.
    NN - однобайтовая команда для которой следующие 4 байта воспринимаются как операнд.
    11 - полезные команда первой ветви.
    22 - полезные команды второй ветви.
    Хотя это совсем уж частное решение.
     
  18. s_d_f

    s_d_f New Member

    Публикаций:
    0
    Регистрация:
    15 май 2008
    Сообщения:
    342
    Очень сложная задача. Возможно следует начать с чего-нибудь простого.

    Например если взять два блока.

    Код (Text):
    1. block1:
    2.    mov eax,[ecx]
    3.    add eax,[ecx+4]
    4.    retn
    5. block2:
    6.    mov ebx,ecx
    7.    mov eax,[ecx+40h]
    8.    retn
    Совмещаем два блока, простым чередованием.
    Код (Text):
    1. block1:
    2.     mov eax,[ecx]
    3.     jmp secinst1
    4. block2:
    5.     mov ebx,ecx
    6.     jmp secinst2
    7. secinst1:
    8.     add eax,[ecx+4]
    9.     jmp endblocks
    10. secinst2:
    11.     mov eax,[ecx+40h]
    12. endblocks:
    13.     retn
    И дальше уже думать как проводить анализ на возможность, оптимизации и совмещения отдельных инструкций.
     
  19. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.615
    Адрес:
    Russia
    Clerk
    начни с байтов мнемокодов команд - например в первой ветке у тебя
    mov ax,ofs16
    первый байт это код инструкции два остальных смещение - соответственно для второй ветки (упрощенно) пусть будет два нопа
    следовательно тебе потребуется ячейка с адресом в два нопа
     
  20. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Если использовать только двухбайтовые команды, то трёхпутевой код можно строить таким шаблоном:
    11 11 NN NN 22 22 NN NN 33 33 NN NN 11 11 ...
    А в 64х битном режиме можно удвоить каждый байт шаблона, при этом заменяя каждый NN на код команды mov r64,i64(два байта, так как нужно использовать префикс REX) , и тогда полезные команды могут быть до 4х байт длиной. Может таким же путём получится построить и 4х путевой код, правда 2 байта на команду в 64х битном режиме может оказаться маловато.