Здрасте.

Вернулся к задаче защиты(OP). Поработав неделю, возник тупик. Тоесть нужен свежий взгляд.

Задача сложная, не из прикладного прог-я. Даже я мозг хорошо на ней поломал, решения не видно, тёмный лес

Кратко что есть визор. Это надстройка над кодом, по факту трассировка инструкций путём выделения линейных блоков и их исполнение напрямую в буферах, после чего визор получает управление, раскодирует новый блок и цикл замыкается.

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

В моём случае работа визора сводится к выделению потоков данных(DFG), а точнее это связывание событий по времени(src-dst для указателей в виде маркеров в памяти), без промежуточных деталей(DFG). Те исполнение кода приводит к динамик выделению dfg и урезанию её, что сводится лишь к причинно-следственным связям(PFG), через пересылки данных маркируется указатель.

Задача следующая.

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

Все логические цепочки вроде как приводят к невозможности решения(главное в нём - профайл - определение FG должно быть быстрее прямого исполнения).

У меня походу полная засада с данной задачей. Тем более что её даже нельзя чётко сформулировать.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет:
определение FG должно быть быстрее прямого исполнения

При этом решение этой задачи исключительно программное?

-----
EnJoy!

| Сообщение посчитали полезным:

Jupiter

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

В железо этот механизм можно будет заложить когда будут решены все нюансы/задачи. Это и должно исполнять железо, но пока это софт.

-----
vx

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

difexacaw пишет:
Это и должно исполнять железо, но пока это софт

Без вентилей/плисок, только на уровне софта ставить задачу по производительности в формулировке "определение FG должно быть быстрее прямого исполнения " нецелесообразно, имхо.
Если уж ты планируешь это всё на железе, то под это и надо затачивать сразу.

-----
EnJoy!

| Сообщение посчитали полезным:

Jupiter

Я поясню любые нюансы не понятные. Когда код пройден первый раз(визором) то он определён, формирована cfg/dfg/pfg. Железо тут совсем непричём, оно к теме относиться как лучший способ имплементации. А алгоритмы не зависимо от импл одинаковы, так что следует пока забыть про железки.

Добавлено спустя 12 минут
Jupiter

Я наверно плохо описал, тема слишком обширна.

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

Тут совсем иное. Каждая часть кода при каждой визор итерации копируется и исполняется, для этого нужны аппаратные перезагрузки контекста. Что есть тормоза. Что бы их исключить можно не трогать вообще какой то известный код, а изменить все его точки выхода и отдать управление напрямую. Изоляция точек выхода изолирует код, те он вернёт управление после отработки. Для этого не нужны никакие сложности типо отображений и прочих механизмов, которым памяти нужно слишком много.

-----
vx

| Сообщение посчитали полезным:

difexacaw

В дополнение к ответу shellstorm:

Если допускать, что блоки кода могут повторяться хотя бы на уровне структуры, то глобально я бы использовал графы и подобие радужных таблиц для уже известного кода, но это потребует множественных проходов, что уже заведомо медленнее прямого исполнения. По сути это очень быстрый сканер с простым (!) разборщиком, который при нескольких проходах условно идентифицирует блоки и либо заносит их в граф/lookup таблицу, либо использует их предварительно сохранённый обработчик из кэша.

-----
EnJoy!

| Сообщение посчитали полезным:

не знаю как вам, но мне первый пост напоминает - --> Link <--

Есть две книги по теме -
Embedded Computing: A VLIW Approach to Architecture, Compilers and Tools и VLIW Microprocessor Hardware Design (2007) в том числе описание Transmeta Crusoe может быть интересным, но difexacaw хочет, чтобы инструкция была в чистом виде или как минимум блоком, при этом игнорирует другие формы типа JIT. Сомневаюсь, что хоть что-то выйдет, ибо это как держаться за два разных полюса .. Уровень кода и уровень интерпретатора должен быть одинаковый по условию, при этом есть ещё и другое условие, что будет прибавление или как минимум равномерное распределение таймингов на наборе инструкций, это невозможно. Запускай два потока визора и один конвейер , на распараллеливании задачи может выйграешь)

-----
RE In Progress [!] Coding Hazard [!] Stay Clear of this Cube

| Сообщение посчитали полезным:

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

Да, его сложно найти, так как слишком уж много нюансов, но это не означает что задача не решаема.

Jupiter

> я бы использовал графы

Сформировать dfg для приложения невозможно, тому есть три препятствия: связывание(формат графа) занимает память, равною или большую размеру апп; формирование dfg невозможно для сервисных вызовов без описания их прототипов, а эта хардкодом являлось бы и гиблая затея; но так как сервисы нарушают вероятный dfg, то попытка его строить бессмысленна - можно найти только концы его цепи(in-out/data), таким образом граф данных в реальном случае не может быть построен, он сводится к графу событий(PFG), те наследованию некоторой инфы(в моём случае - это указатели).

mak

> чтобы инструкция была в чистом виде или как минимум блоком

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

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

> чтобы инструкция была в чистом виде

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Нужно пойти дальше и организовать пакеты инструкций на прямое исполнение. При этом должен сохранятся pfg, но так как по одной и той же процедуре происходит множество вызовов, то очевидно что нет смысла крутить это непрерывно выполняя блоки, нужно найти способ отпустить управление в процедуру(конечно же вложенность подразумевается).

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

| Сообщение посчитали полезным:

shellstorm

Задача весьма сложная, она не решаема на досуге", видимо в анализ нужно глубоко погрузится. Иначе найти решение невозможно походу.

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

Необходимо алгоритмическое решение, самодостаточное, не включающее в себя сомнительные компоненты, которые существуют лишь на бумаге"

Добавлено спустя 24 минуты
shellstorm

> нужно писать свой оптимизатор и систему кешерования

Я как то пропустил это, точнее не обратил внимание. Давно был реализован синхронный кэш, очень быстрый. Это дало прирост по профайлу лишь гдето 10%, что очень мало, но памяти оно требует слишком много. Изначально кэш инструкций был использован для свёртки vmp, оно не эффективно в качестве оптимизации.

-----
vx

| Сообщение посчитали полезным:

хлам, опять выдуманное слово визор какоето, купи нормальный камень и открой для себя аппаратную виртуализацию, а не лепи горбатого из костылей

| Сообщение посчитали полезным:

SegFault

У меня хорошая машинка, камень поддерживает все эти технологии гпв. Но дело не в этом.

Гипервизор это мод(режим), его нельзя интегрировать в приложение. Визоры для этих целей и предназначены.

Они работают в текущем моде. Это отлично работает в юм, на счёт км - я не уверен, это не рассматривалось.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Задача весьма сложная, она не решаема на досуге

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

difexacaw пишет: Матчасть по леммам, свёрткам, нейросетевая/символическое_исполнение и прочее совершенно в данном случае бесполезно

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

| Сообщение посчитали полезным:

shellstorm

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

> ты всю работу делаешь в одном потоке

Распараллеливание невозможно, это не вычисления, а исполнение кода.

Добавлено спустя 5 минут
Даже если теоретически создать два треда, и распределять между ними блоки на выполнение - ничего не выйдет, по простой причинно следственной связи - второй тред будет синхронно ждать выполнение блока в первом треде и наоборот. Получится перекрёстная работа потоков, когда один исполняет, а второй ждёт ничего не делая. Тайминг на синхронизацию будет большим, такая схема бессмысленна.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Даже если теоретически создать два треда, и распределять между ними блоки на выполнение

Я разве писал об исполнении? В потоке крутить оптимизатор и постобработку исполнения блоков, с построением связей между блоками. исполнения блоков гипотетически можно распараллеливать, но на практике это закончится разрывом пятой точки. Другая проблема, это управление исполнением, сам "мотор" ради "мотора" не имеет практического смысла, даже велосипеду нужен руль и правила опять же лучше исполнять в другом потоке.
Например в python добавление декоратора numba в некоторых случаях может ускорить выполнение в 20 раз, несмотря на то, что функция сначала загоняется в дизасм, по ней проходит транслятор, настраивается контекст и только после это всё исполняется.

| Сообщение посчитали полезным:

shellstorm

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

> Например в python добавление декоратора numba в некоторых случаях может ускорить выполнение в 20 раз

Это немного иное - оптимизация на уровне компилера/интерпретатора/вм. Тут вся суть в том, как ускорить повторные прямые выполнения блоков. Чем тяжелее по времени какая то высокоуровневая обработка, тем проще её оптимизировать. На уровне прямого исполнения оптимизация становится проблемой, тоесть не эффективной или трудно решаемой.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Не нужны нам пока потоки, хоть бы с одним разобраться

В таком случае остаются только константные блоки.
Допустим есть такая функция:



Очевидно, что эта функция и связанные с ней блоки (std::vector) константны, соответственно можно выполнять напрямую. Нужно выделить признаки которые указывают на константность и проанализировать связанные блоки, в некоторых случаях это существенная часть кодовой базы, iostream это в некоторых случаях мегабайт кода, существенная часть которого const. Других вариантов для одного потока не вижу, остальное будет давать огромное проседания по скорости из за сложного анализа.

| Сообщение посчитали полезным:

shellstorm

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

Добавлено спустя 43 минуты
shellstorm

Из общих соображений получается такое. Блок должен быть отображён на dfg или быстрый pfg при первом проходе(исполнении). Так как блок(процедура) не линейна, те содержит условные конструкции, то и её описание(cfg/dfg/etc) будет содержать условную конструкцию, которую так же нужно обработать на cpu, а учитывая более высокий уровень обработки, тайминг будет куда ниже, чем обработка аналогичного условия напрямую. Таким образом видимо невозможно как то скипнуть целиком нелинейный блок(тк FG нелинеен, зависит от аргументов).

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Получается как минимум можно выделить линейные подблоки

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

| Сообщение посчитали полезным:

shellstorm

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

Я поразмыслил над задачей, вроде бы как решение найдено.

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

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

Реализация это уже классическая задача по работе с кодом. В данном случае видны два пути:

A. Мод всех ветвлений.
B. Перенос кода в буфера. Этот вариант откланяется из за дублирования памяти.

Остаётся решить простую алго задачу - корреляцию блоков при патче(когда размер ветвления больше размера блока).

-----
vx

| Сообщение посчитали полезным:

difexacaw
А если там short jxx то как патчить?

| Сообщение посчитали полезным:

SegFault

А есчо однобайтный рет может быть, в чём проблема ?

Переносим пролог в индексируемый буфер, пишем call для дальнейшего определения адреса возврата. Для блоков, патч которых невозможен, это например малого размера - переносим их целиком в буфер, либо выполняем под визором штатным путём(мне больше первый вариант нравится, памяти займёт больше, но не нужно копировать каждый раз). Можно использовать метод callmap, это когда происходит вызов из произвольного адреса в линейный массив call-ов, на основе адреса возврата вычисляется индекс. Для данной задачи вариантов решения овер дофига, какие из них выбрать - хз, нужно продумать всё, но всё равно лучший способ покажут только тесты на профайл.

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

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Возможен иной тип выполнения под визором - не использовать копирование, а патчить ветвления в самом коде. В таком случае профайл существенно возрастает

Как будет решаться обработка ошибок? Копирование делается не просто так, а для изоляции памяти и обработки ошибок (memory isolation, доков полно). Допустим нужен мне тул для фаззинга, взял твой вариант и во время работы что-то пошло не так, что делать, падать?

| Сообщение посчитали полезным:

shellstorm

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

-----
vx

| Сообщение посчитали полезным:

Прошло некоторое время, я в сети небыл, но думал что зайду и почитаю ответы, таки почитал

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Прошло некоторое время, я в сети небыл, но думал что зайду и почитаю ответы, таки почитал

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

| Сообщение посчитали полезным: difexacaw

shellstorm

Набросок сложно сделать, задача не решена, части её не понятны. Изначально я сказал что задача сложная, это не из типа задач, взял и закодил". Нюансов столь много, что нужна куча времени, пока это всё соберётся в единое целое, тогда можно говорить про конкретные алгоритмы.

Не получается даже сделать примерную оценку на профайл/ресурсы. Любое усложнение приводит к необходимости использования битовых отображений на AS. Для этого нужна куча памяти. К примеру не понятно как быть с читаемым-исполняемым кодом, запись которого невозможна. Тут два варианта - либо собирать код в буферах, либо его выполнять визором. Во втором случае копирование, повторные проходы и те тормоза; в первом случае засада с чтением - нужны таблицы для отображения исходных адресов на буфера с собираемым кодом, нельзя просто всё адресное пространство копировать, получается есчо одна сложная довольно задача, как вариант использовать механизмы трансляции. Это динамическое выделение буферов по ходу использования памяти, для этого используются синхронные буфера, адреса вычисляются(транслируются), это тоже не фонтан", но чтение кода(R-df) операция весьма редкая.

-----
vx

| Сообщение посчитали полезным:

Появилась новая идея

Учитывая множество проблемных нюансов, это например перемещения кода и как минимум необходимость хранения таблиц отображений ветвлений на исходные адреса, можно использовать более простой и видимо лучший способ.

- каждое ветвление изменяется не на ветвление в визор, а на 1B-RET. Тогда перед выполнением блока визор загрузит адрес возврата в себя. В таком случае адрес следующего блока не хранится в коде(в отличие от call_visor). Что бы получить адрес ветвления(RET), те размер блока нужно использовать тяжёлые во всех смыслах глобальные таблицы трансляции. Вместо этого сохраняем трассу и при последующих проходах линкуем трассу в граф(односвязанный список). В этом виде переход к следующему блоку происходит через выбор следующей ссылки из списка(графа).

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

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

-----
vx

| Сообщение посчитали полезным:

судя по описанию ты изобретаешь своеобразный GC. сборка ссылок на блоки и разрешение коллизий с поиском это именно часть GC, часть с RET это исполнитель, который относится к трасировке\исполнителю, совсем другой компонент. AVL вполне подходит под задачу, только и здесь есть разные варианты которые быстрее-медленнее.

| Сообщение посчитали полезным: