arrowdodger 8 июл 2011 в 16:45

Виртуальная машина KLEE для символьного выполнения кода

6 мин

4.3K

Информационная безопасность*

Перевод

+37

Комментарии 7

Laplace 8 июл 2011 в 16:56

Интересно, но непонятно. Можете подробнее про KLEE рассказать? В чём суть?

arrowdodger 8 июл 2011 в 16:59

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

Почитайте их сайт, раздел публикации.

Laplace 8 июл 2011 в 17:40

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

arrowdodger 8 июл 2011 в 17:48

Да, в общем случае это долго, есть программы, где KLEE неприменима, но есть и куча хитрых аспектов и ньюансов. Например, иногда можно доказать, что такой-то путь ни на что не влияет, или что два пути равносильны по ограничениям и их можно объединить в один.
Ну и все зависит от самой программы — на ее входе может быть строка с бесконечной длиной, а в коде проверяется только 3 символ этой строки. В таком случае KLEE не будет работать бесконечно, а сразу закончит, т.к. здесь только 2 разных пути.