Поиск строк в пакете

Question

Предположим, мы собираем пакеты с API C libpcap. Эффективно ли анализировать некоторые строки полезной нагрузки со строковым поиском strstr() в линейной скорости (например, Mbps/Gbps)? Например strstr (полезная нагрузка, «User-Agent»);

Было бы более эффективным сделать это с помощью библиотеки соответствия шаблонов регулярных выражений, таких как libpcre?

Если мы хотим сделать это только для аргументов заголовка HTTP, существует ли какой-либо C API? Мне непонятно, может ли libcurl это сделать ... заблаговременно.

Answer 1

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

Если вы ищете несколько строк, вам лучше использовать быстрый алгоритм сопоставления строк, такой как Aho-Corasick, или создать машину состояний, которая соответствует строкам, которые вы хотите в нужном вам контексте, то есть синтаксический анализатор , Для анализа основной регулярной грамматики, такой как HTTP в C, ragel state machine compiler является моим инструментом выбора.

Answer 2

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

Answer 3

http://www.arstdesign.com/articles/fastsearch.html имеет некоторые показатели, показывающие, что strstr прилично исполнен. Для коротких совпадений строк я сомневаюсь, что библиотека регулярных выражений может превзойти хорошую оптимизированную сборку.