Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, мыщъх, Вы писали:

М>>...
cjhhb за зажержку. обмозговывал ваш пост. дотнет за разумное время не осилю. сейчас и так по приказу партии курю пиона, рубина и sql. думаю -- а что если это как-то аусорсить тому, что уже это знает? вам -- реклама языка (все-таки мы уже в интел, а это контора большая) плюс деньги (разумные) за выполнения заказа.

VD>Задача весьма странная. Интересно откуда у нее растут ноги? Что ломает эти скрипты?
есть пассивные сенсоры, работающие на сетевом уровне, ассемблирующие TCP и передающие данные на мой уровень. вот только на моем уровне обнаруживается, что сборка реально кривая и целые фрагменты физически отсутствуют. одна из причин -- потеря пакетов на сенсоре. по статистике 10%. остальные причины -- хз. но в итоге у меня ~15% скриптов выходят "битыми" и мне нужно что-то с этим делать, т.к. разработчики сенсора фикс обещают только в светлом коммунистическом будущем, а кушать хочется здесь и сейчас.

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

var heapSprayToAddress = 0x05050505;
var shellcode = unescape("%u9090%u9090 ... %u6a51%uff00raySlide;
    }
    spraySlide = spraySlide.substring(0,spraySlideSize/2);
    return spraySlide;

как видно, тут мы потеряли кавычку, закрывающую круглую скобку и какую-то конструкцию, открывающую фигурную скобку, в которую мы "врезаемся".

данный скрипит писали хакеры-идиоты, и потому он автоматически реконструировался еще в ранних релизах. переменная raySlide очевидно _sp_raySlide, что распознается по словрю. но даже если бы она была не spraySlide, а foo, то по конструкции 0x5050505/unescape/substring легко распознать что это такое.

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

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

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

М>>а что вы еще можете порекомендовать?
VD>Давай лучше на ты.
давай. только я могу забыть и снова перейти на "вы" по привычке



М>>сейчас я все это могу распарсить на регулярках, т.е. понять, что 'olla-la-shit-happens' это одно, а f.read это уже другое. именно f.read, а не happensf.read, т.к. дальше идет f.close.

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

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

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

М>>что из готовых инструментов вы посоветуете? у меня токенизация делается по списку ключевых слов. в первом проходе это будет read, close, return.

VD>PEG позволяет избавиться от стадии лексического разбора, что позволит тебе выявлять и битые последовательности.
VD>Скажем не закрытую строку или сросшиеся литералы.
пока у меня такой алгоритм. после того как мы нашли unescape поиском по подстроке (без парсинга), на начинаем анализировать аргументы:

"var shellcode = unescape("%u9090%u9090 ... %u6a51%uff00raySlide;
}
"
в данном случае мы видим, что есть неожиданный перенос строки, следовательно уже косяк. затем мы выделяем из строки (от открывающихся кавычек до переноса) подстроку "raySlide", которая есть фрагмент переменной. от начала переменной и дальше идет осмысленный код, который парсится без ошибок. таким образом, за не именем лучших предположений мы относим raySlide; к границе строки, устанавливая внутренний флаг, что строка повреждена и потому все данные, опирающиеся на нее, достоверны только с некоторым приближением.

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

скорее у меня ближе к нормальному парсингу с той лишь оговоркой, что первичная токенизация делается путем словарного поиска, а так же поиска по шаблонам вида x = foo ( a1, a2, a3 ) [; | EOL | .bar ].

полученные токены служат опорными точками. много их извлекается из комментов и строк (на js куча кода в строках), и уже потом решается что делать с пространством между ними.

VD>Стадии у тебя должны быть такими:
VD>1. Парсинг в алгебраические типы данных. Причем формат АлгТД должен быть таким чтобы учитывать возможность хранения битых последовательностей. Их можно по ходу дела наращивать.
пока с типами данных у меня трудности. достаточно очевидно, что "родных" типов js для решения задачи не хватает. в частности, a = foo()/b = bar(a). тут 'a' может быть (физически) и Array, и String, но у меня указывается, что 'a' это тот тип, который возвращается foo и который хочет bar (при условии, что они связаны примерно как open и read).

М>>у нас половина людей под никсами, вторая половина под маками. код им понимать необязательно, но он у них должен по крайней мере работать. я не в курсе как у вас с кросс-платформенностью. под линухом заведется?
VD>Во-первых, немерл, а стало быть и Nemerle.Peg прекрасно живут под Моно, а значит под Линуксом и Маком.
про моно я слышал, но был не в курсе работает ли под ним Nemerle.Peg, ну раз вы говорите, что работает... (от коллег слышал, что под моно вообще мало что дотнетовского работает, но сам никогда не юзал ни дотнет, ни моно)

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

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

VD>Кстати, грамматика JavaScript (не знаю уж насколько полноценная) уже есть. Можно взять ее за основу и доработать напильником, так чтобы парсер брал и битый код.
я бы с удовольствием это аутсорсил, попросив у руководства денежек для финансирования этой затеи. есть желающие? и сколько это примерно может стоить? т.к. это не кодинг, а главным образом ресерч, то догадываюсь, что и стоить будет соответственно, но хоть примерно?

М>> а потому сначала выделяю ключевые слова ("ключевые" в смысле словарные), а уже отталкиваясь от них бью текст на токены, но это разбивка предположительная, и там приходится искать лучшее соответствие. я стрю семантическое дерево (если я правильно его называю),
VD>Не правильно. Это называется синтаксическим деревом, или сокращенно AST (Abstract Syntax Tree).
неее... что такое AST я знаю. но у меня все-таки семантическое дерево, т.е. дерево описывающее _смысл_ функций, в частности, указывается, что такое open и чем оно отличается от close.

тут в соседней ветке про абби пишут о дереве понятий в естественных языках. так вот, хоть это и смешно, но у меня что-то похожее получается для языка программирования. даже если названия функций ничего не говорят, из самой последовательности вызовов и схемы передачи аргументов и возвращенных значений можно много чего "вытянуть". ну например: a = new b(c); a.foo = xxx; a.bar = yyy; a.baz = ooo; ooo = a; тут как бы сразу понятно из какой это оперы. с точки зрения семантики это интерцепт (не важно хакерский или легальный), с точки зрения AST...

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

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

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

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

Здравствуйте, мыщъх, Вы писали:

М>cjhhb за зажержку. обмозговывал ваш пост. дотнет за разумное время не осилю. сейчас и так по приказу партии курю пиона, рубина и sql. думаю -- а что если это как-то аусорсить тому, что уже это знает? вам -- реклама языка (все-таки мы уже в интел, а это контора большая) плюс деньги (разумные) за выполнения заказа.

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

Потом еще вопрос денег интересен. Если деньги будут серьезными, то много кто возьмется.

М>есть пассивные сенсоры,

Это что?

М>работающие на сетевом уровне, ассемблирующие TCP и передающие данные на мой уровень. вот только на моем уровне обнаруживается, что сборка реально кривая и целые фрагменты физически отсутствуют. одна из причин -- потеря пакетов на сенсоре. по статистике 10%. остальные причины -- хз. но в итоге у меня ~15% скриптов выходят "битыми" и мне нужно что-то с этим делать, т.к. разработчики сенсора фикс обещают только в светлом коммунистическом будущем, а кушать хочется здесь и сейчас.

Круто. Это значит из-за сбоя в железки вы какой-то догадыватель пишите?
А как потом такие скрипты используются? Не уж то выполняются?

М>так что задача далеко не теоретическая. пример реально битого скрипта привожу ниже.

М>

М>var heapSprayToAddress = 0x05050505;
М>var shellcode = unescape("%u9090%u9090 ... %u6a51%uff00raySlide;
М>    }
М>    spraySlide = spraySlide.substring(0,spraySlideSize/2);
М>    return spraySlide;
М>

М>как видно, тут мы потеряли кавычку, закрывающую круглую скобку и какую-то конструкцию, открывающую фигурную скобку, в которую мы "врезаемся".

Если мы из него "угадаем":

var heapSprayToAddress = 0x05050505;
var shellcode = unescape("%u9090%u9090 ... %u6a51%uff00raySlide");
    spraySlide = spraySlide.substring(0,spraySlideSize/2);
    return spraySlide;

этого будет достаточно?

М>однако, для js скриптов готовых решений нет (во всяком случае на паблике).

Да я вообще впервые вижу подобную задачу.

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

Как, как? Сначала пробуем прогнать обычны правила. Если они все обломались, то переходим в режим восстановления после обнаружения ошибки. Этот режим будет пытаться применить эдакие эвристические правила которые будут пытаться выявить несуразности по шаблонам. Если и это не удастся, то начинаем с места где не удалось спарсить код выполнять пропуск символов до тех пор пока код снова не начнет парситься. Полученные пропущенный диапазон анализируем отдельно и с пристрастием.

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

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

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

Что-то это больно походит на гадание на кофейно гуще.

М>"var shellcode = unescape("%u9090%u9090 ... %u6a51%uff00raySlide;
М> }
М>"
М>в данном случае мы видим, что есть неожиданный перенос строки, следовательно уже косяк.

А разве жабасктипт не допускает перенос строк внутри строк?

М>затем мы выделяем из строки (от открывающихся кавычек до переноса) подстроку "raySlide", которая есть фрагмент переменной.

На каком основании? Может быть программист хотел написать что=то вроде "raySlide=" + spraySlide

М> от начала переменной и дальше идет осмысленный код, который парсится без ошибок. таким образом, за не именем лучших предположений мы относим raySlide; к границе строки, устанавливая внутренний флаг, что строка повреждена и потому все данные, опирающиеся на нее, достоверны только с некоторым приближением.


VD>>Стадии у тебя должны быть такими:
VD>>1. Парсинг в алгебраические типы данных. Причем формат АлгТД должен быть таким чтобы учитывать возможность хранения битых последовательностей. Их можно по ходу дела наращивать.
М>пока с типами данных у меня трудности. достаточно очевидно, что "родных" типов js для решения задачи не хватает. в частности, a = foo()/b = bar(a). тут 'a' может быть (физически) и Array, и String, но у меня указывается, что 'a' это тот тип, который возвращается foo и который хочет bar (при условии, что они связаны примерно как open и read).

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

Короче надо не за один проход все проблемы решать, а за два, а луче на три. На первом просто разбираешь синтаксис (выявляя битые части), а на втором делаешь анализ. На третьем собираешь из битого АСТ гипотетический целый.

М>про моно я слышал, но был не в курсе работает ли под ним Nemerle.Peg, ну раз вы говорите, что работает... (от коллег слышал, что под моно вообще мало что дотнетовского работает, но сам никогда не юзал ни дотнет, ни моно)

На самом деле не так мало. А пег — это всего лишь парсер. Он только доступ к строке по индексу и использует.

VD>>Во-вторых, ты же говоришь о прототипе. А его по фигу на чем писать.
М>на чем писать -- по фиг, но если он будет запускаться только на моей машине... вот тут коллега написал скрипт на руби, который работает только на никсах, хотя юзает rails и потому должен (в теории) запускаться и на винде. но у меня запустить его не получилось. и я написал свой. на питоне. у меня одна часть лучше, у коллеги другая часть лучше. у меня выдает больше данных, у коллеги -- данные более "чистые". и мы щас мержим каждый сам свою версию, портируя с питона на рубин и с рубина на питон...

Ну, или у вас прототип. Или вы все же пишите уже что-то рабочее. Прототип нужен только для пробы идей. Далее уже по прототипам вы напишите рабочую версию.

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

А не проще ли позвать коллег к себе, показать им прототип и рассказать суть концепций?

VD>>Кстати, грамматика JavaScript (не знаю уж насколько полноценная) уже есть. Можно взять ее за основу и доработать напильником, так чтобы парсер брал и битый код.
М>я бы с удовольствием это аутсорсил, попросив у руководства денежек для финансирования этой затеи. есть желающие?

Создай тему здесь. А вось кто-то и найдется. Поработать за деньги на немерле может оказаться многим интересно. Только задание какое-то неопределенное, что может отпугнуть.

М>и сколько это примерно может стоить?

Черт его знает. Ты задачу только в общих чертах описал. Все зависит от деталей.

М>>> а потому сначала выделяю ключевые слова ("ключевые" в смысле словарные), а уже отталкиваясь от них бью текст на токены, но это разбивка предположительная, и там приходится искать лучшее соответствие. я стрю семантическое дерево (если я правильно его называю),
VD>>Не правильно. Это называется синтаксическим деревом, или сокращенно AST (Abstract Syntax Tree).
М>неее... что такое AST я знаю. но у меня все-таки семантическое дерево, т.е. дерево описывающее _смысл_ функций, в частности, указывается, что такое open и чем оно отличается от close.

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

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

В ЯП семантика однозначая, так что с этим никаких проблем нет. А вот для естественных языков понятность — это высший пилотаж, точнее ИИ.

М>даже если названия функций ничего не говорят, из самой последовательности вызовов и схемы передачи аргументов и возвращенных значений можно много чего "вытянуть". ну например: a = new b(c); a.foo = xxx; a.bar = yyy; a.baz = ooo; ooo = a; тут как бы сразу понятно из какой это оперы. с точки зрения семантики это интерцепт (не важно хакерский или легальный), с точки зрения AST...

Ну, вот когда код разобран, то такой паттерн распознать будет не сложно. Но не надо сваливать стадию парсинга и распознавания паттерна в одну стадию.

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

Антивирусы пишите?

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

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

Интересный скрипт. У меня тут антивирус старательно блокирует эту ветку дискуссии и на сайте и в почте.