по исходному коду MSIL — построил AST дерево,
нужны алгоритмы статического анализа исходного кода, т.е алгоритмы обхода по этому AST дереву для определения уязвимости приложения
у кого какие мысли?

а какие тут могут быть мысли. наливай да пей.

мсил превратить в дерево очень просто.
все комманды являются стейтментами. регистры переменными (для простоты можно считать их определенными в начале метода).

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

или вопрос был в том чем читать мсил?

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

M>нужны алгоритмы статического анализа исходного кода, т.е алгоритмы обхода по этому AST дереву для определения уязвимости приложения
M>у кого какие мысли?

У меня никаких мыслей что Вы здесь имеете ввиду под "уязвимостями".

Здравствуйте, Пельмешко, Вы писали:

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

M>>нужны алгоритмы статического анализа исходного кода, т.е алгоритмы обхода по этому AST дереву для определения уязвимости приложения
M>>у кого какие мысли?

П>У меня никаких мыслей что Вы здесь имеете ввиду под "уязвимостями".

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

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

M>у кого какие мысли?

Если F#/OCaml не пугает, то можно посмотреть на AbsIL

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

П>>У меня никаких мыслей что Вы здесь имеете ввиду под "уязвимостями".
M>определение наиболее потенциально опасных конструкций языка, должны быть специальные алгоритмы
Опять же — с какой стороны опасных-то?
Конкретней, пожалуйста. Опасность в чем состоит?

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

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

П>>>У меня никаких мыслей что Вы здесь имеете ввиду под "уязвимостями".
M>>определение наиболее потенциально опасных конструкций языка, должны быть специальные алгоритмы
LVV>Опять же — с какой стороны опасных-то?
LVV>Конкретней, пожалуйста. Опасность в чем состоит?

определение где возможны sql инъекции, переполнения буфера,xss атаки итд

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

M>определение где возможны sql инъекции, переполнения буфера,xss атаки итд

Вы про .Net?

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

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

M>>определение где возможны sql инъекции, переполнения буфера,xss атаки итд

A>Вы про .Net?

знаем-знаем))
помимо этого другие уязвимости есть

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

C>а какие тут могут быть мысли. наливай да пей.

C>мсил превратить в дерево очень просто.
C>все комманды являются стейтментами. регистры переменными (для простоты можно считать их определенными в начале метода).

C>структура классов/методов в мсиле лежит прямо. без всякого запутывания.

C>или вопрос был в том чем читать мсил?

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

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

M>дерево построил, нужны алгоритмы статического анализа для этого дерева

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

Пока не будет списка уязвимостей, не будет и алгоритмов.

Здравствуйте, malafish, Вы писали:
M>определение где возможны sql инъекции, переполнения буфера,xss атаки итд
Поскольку переполнения буфера и xss атаки в MSIL невозможны, то остаётся ловить SQL-иньекции.
Для этого нужно найти все те места, где текст команды передается в SqlCommand.
Потом нужно отследить, откуда берутся эти тексты команд. И если в них участвует что-то из пользовательского ввода, то нужно ругаться.

Чтобы не ставить смайлики:

malafish, в общем виде не решаемо.

Для sql-инъекций:
Если надо грязно проверить:
а) берётся ndepend и пишется CQL-й запрос (не опечатка, именно CQL)
б) пишется своё правило для FxCop
в) смотрим через analyze рефлектора.

Самая дубовая проверка: если строка, которая передаётся в свойство CommandText берётся не напрямую из ресурсов — возможна инъекция.

Дальше сложнее — проверяем как строка передаётся по стеку возможных вызовов (если вам удастся его построить, что очень маловероятно) и ищем места, где меняется значение переменной. Это для примитивных сценариев. На практике вам придётся отслеживать всякие wrapper'ы, если используете ORM-ы — убеждаться, что они не пропускают грязные переменные.

Полный анализ на предмет уязвимостей — такой же миф, как осуществимость full code coverage. Одного виртуального метода/интерфейса/делегата в ветке AST достаточно для того, чтобы пометить ветку как подозрительную ибо верификация невозможна. И это вы проверяете immutable объект — строку.

Если вы так боитесь инъекций, то или не давайте прав+используйте хранимые процедуры (возможно, генерящие ad hoc sql) или изолируйте код, которому вы доверяете и не допускайте других способов залезть в базу. Защита путём анализа кода является np-полной задачей — вам мощностей не хватит даже для 30 последовательных переходов (если вы анализируете _каждый возхможный_ путь выполнения, а не характерные ака образующие пути). С интересом посмотрю на анализ 64-х последовательных if/else (а самые примитивные ндка/регексп-билдеры куда сложнее код могут нагенерить).

Надеюсь, у вас не было планов продавать очередной CD-ejector?

За что люди были бы по гроб благодарны — плагин для рефлектора — рисование графов по выбранным элементам depedency matrix. API есть, плагин, что строит матрицы есть. NDepend в платной версии подобное умеет, вот если бы не цена в 300$...

Удачи.

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

S>С интересом посмотрю на анализ 64-х последовательных if/else (а самые примитивные ндка/регексп-билдеры куда сложнее код могут нагенерить).

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

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

C>>или вопрос был в том чем читать мсил?

M>дерево построил, нужны алгоритмы статического анализа для этого дерева

1) Точно дерево правильно построил? Что алгоритм делает, если после dup идёт br?

2) http://en.wikipedia.org/wiki/Abstract_interpretation

http://en.wikipedia.org/wiki/Model_checking

Q>Дык анализировать то надо от уязвимой функции снизу вверх, а не от начала программы в надежде что нибудь найти Так и ненужные ветки отсекутся.

if (flag1)
{
  Action1();
}
else
{
  Action2();
}
//...
if (flag32)
{
  Action63();
}
else
{
  Action64();
}

MethodToAnalyze();

MethodToAnalyze() — проверяемый метод, который зависит от 64 полей, Action1..64 — инстанс методы, меняющие эти поля.

Сколько у вас возможных комбинаций для анализа?

Если вы не делаете верификации в рантайме на момент конкретного вызова — а там она даром не сдалась — вычисление всех возможных путей выполнения np-полная задача.

Щастья вам.

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

S>MethodToAnalyze() — проверяемый метод, который зависит от 64 полей, Action1..64 — инстанс методы, меняющие эти поля.

S>Сколько у вас возможных комбинаций для анализа?

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

S>Если вы не делаете верификации в рантайме на момент конкретного вызова — а там она даром не сдалась — вычисление всех возможных путей выполнения np-полная задача.

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

Дорогой вы мой, если бы всё было так просто — подобных инструментов было бы как грязи. Пока же только FxCop aka CodeAnalysis, StyleCop, ndepend да плагины к профайлерам. На анализ уязвимостей никто почему-то не замахивался. Не хотите занять нишу?

Быстрые проверки по стеку aka снизу вверх — например, значение строки не должно изменяться по всему стеку — неосуществимы если один из методов в стеке дёргает другой метод, принимающий строку как ref.
Для mutable объектов проверки по стеку бесполезны.
Например:

void A(Mutable m)
{
  if (m != null)
  {
    B(m);
    C(m);
  }
}
void B(Mutable m)
{
  m.Property = null;
}
void C(Mutable m)
{
  string s = m.Property.ToString();
}

В C будет NullReferenceException. Проверка стека снизу вверх — из C в A — никаких ошибок не найдёт. Вам нужен обход всех возможных путей выполнения.

void A(Mutable m, bool f1, bool f2)
{
  if (m != null)
  {
    if (f1)
    {
      B(m);
    }
    if (f2)
    {
      C(m);
    }
  }
}
void B(Mutable m)
{
  m.Property = null;
}
void C(Mutable m)
{
  string s = m.Property.ToString();
}

Теперь NullReferenceException будет только в одном случае из 4. А может и не быть вообще, если f1 всегда != f2;

Что должен сказать ваш Analyzer?

Анализ по образующим может не выявлять существующих уязвимостей, или, наоборот, предупреждать о несуществующих проблемах. Полный анализ невозможен — слишком большое пространство состояний. Это если анализировать только стек. Если у вас появляется хранимое состояние, то область анализа разрастается ещё круче — мы вынуждены учитывать все методы, что меняют каждое из полей и возможные пути их вызова.

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

Мы ещё не дошли до циклов, ленивых итераторов и прочих прелестей.

Проблема в том, что для построения полного графа вызовов нам надо иметь код всей системы, гарантию, что нет DLR/рантайм-генерации кода/позднего связывания и убедиться что у нас нет динамического workflow — делегатов, интерфейсов, виртуальных методов.

Баловство это в общем.

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

S>Дорогой вы мой, если бы всё было так просто — подобных инструментов было бы как грязи. Пока же только FxCop aka CodeAnalysis, StyleCop, ndepend да плагины к профайлерам. На анализ уязвимостей никто почему-то не замахивался. Не хотите занять нишу?

Для .NET не богато, а вообще — вагон и маленькая тележка: Coverity, Klocwork, продукты Semantic Designs, и т.п. Даже для Си (!!!).

S>Быстрые проверки по стеку aka снизу вверх — например, значение строки не должно изменяться по всему стеку — неосуществимы если один из методов в стеке дёргает другой метод, принимающий строку как ref.
S>Для mutable объектов проверки по стеку бесполезны.

Это слишком примитивно. Я говорю про Abstract interpretation, она позволяет, не заморачиваясь на termination problem, протянуть расцвеченный dataflow-граф через весь код. Даже рефлексию во многих случаях сжуёт и не поморщится.

И, да, это не так уж и просто. Это до хрена тяжелой и сложной rocket science. Я этим как бы немножко занимаюсь, и оно даже как бы немножко работает.

Кстати, даже решение termination problem для многих важных на практике задач имеется уже давно, а это куда как сложнее:

http://research.microsoft.com/en-us/um/cambridge/projects/terminator/

S>В C будет NullReferenceException. Проверка стека снизу вверх — из C в A — никаких ошибок не найдёт. Вам нужен обход всех возможных путей выполнения.

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

Вообще странно, что вас смущает отсутствие реализаций, индустрия от передового фронта науки всегда лет на 15-20 отставала.

S>Теперь NullReferenceException будет только в одном случае из 4. А может и не быть вообще, если f1 всегда != f2;

Опять же — простая раскраска графа эту возможность выявит (но не докажет), а на практике этого вполне достаточно. Простое изменение в коде эту возможность исключит.

S>Анализ по образующим может не выявлять существующих уязвимостей, или, наоборот, предупреждать о несуществующих проблемах.

А вот последнее как раз не колышет. Обычно у таких анализаторов соотношение правильных срабатываний к мусору где-то 1 к 10, и ничего, проблемы решаются — и это главное. Теоретическая чистота и красота никому никуда не впилась, людям надо решать реальные проблемы. Если ради одной настоящей дыры придётся просмотреть всего лишь 9 безвредных вариантов — то это прекрасно окупается.

S> Полный анализ невозможен — слишком большое пространство состояний.

У вас довольно таки странное представление о том, как делается анализ. Почитайте, пожалуйста, про abstract interpretation — сложность с увеличением числа вариантов не растёт. И обычно применяется ещё и ряд других техник, таких, как например в языке Why.

S> Это если анализировать только стек.

Не надо вообще анализировать стек.

S> Если у вас появляется хранимое состояние, то область анализа разрастается ещё круче — мы вынуждены учитывать все методы, что меняют каждое из полей и возможные пути их вызова.

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

S>Ещё веселее когда мы дёргаем виртуальный метод или метод интерфейса или делегат — любой анализ идёт лесом, можно только пометить путь исполнения, как опасный для всех уязвимостей.

Ничего подобного. Даже рефлексия не представляет проблемы.

S> Очень интересно, как будут выглядеть ваши рекомендации для устранения NullReferenceException в подобных вариантах.

Грубо говоря, это ужесточение системы типов (введение nullable и ни фига не nullable объектов), с глобальным выводом типов по всему коду. Этого более чем достаточно. Только вот, мы тут немного не про NullReferenceException говорим, а про отслеживание попадания данных, не отфильтрованных через кошерную (и юзером отмеченную) процедуру, в аргументы одного из помеченных как опасные методов. А это вообще задача тривиальная. Отследить, что прочитанное из потока попадает невозбранно в один из вызовов ADO.NET можно за время, линейное от размера кода.

S>Мы ещё не дошли до циклов, ленивых итераторов и прочих прелестей.

Обратно же, читайте про abstract interpretation!!!

S>Проблема в том, что для построения полного графа вызовов нам надо иметь код всей системы, гарантию, что нет DLR/рантайм-генерации кода/позднего связывания и убедиться что у нас нет динамического workflow — делегатов, интерфейсов, виртуальных методов.

Виртуальные вызовы в 99.999% случаев сводятся к статическим при таком анализе.

S>Баловство это в общем.

Рынок этого балоства — сотни миллионов долларов. См. на вышеперечисленные компании, и на их вклад в устранение проблем в open source.

Аноним, сорри, обычное недопонимание.
Тема началась если помните с вопроса "я построил ast, как мне теперь найти уязвимости?".

Свою точку зрения изложил выше:
>Полный анализ на предмет уязвимостей — такой же миф, как осуществимость full code coverage

Дальше товарищ предложил анализ снизу вверх как решение всех проблем. Я в ответ привёл быдлопример, на котором подобная проверка ни разу не сработает. Тут появляетесь вы и говорите, что нифига, dataflow-анализ прекрасно здесь сработает.

Дальше меня заклинило, и я воспринял ваш пост как очередное изобретение серебрянной пули Собсно весь ответ и был посвящён неосуществимости серебрянной пули (о чём вы конечно не писали)

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

Принято?