Как подсчитать, сколько раз последовательность байтов встречается в файле?

16

Я хочу посчитать, сколько раз определенная последовательность байтов происходит внутри файла, который у меня есть. Например, я хочу узнать, сколько раз число \0xdeadbeefвстречается в исполняемом файле. Прямо сейчас я делаю это, используя grep:

#/usr/bin/fish
grep -c \Xef\Xbe\Xad\Xde my_executable_file

(Байты записаны в обратном порядке, потому что мой процессор имеет младший порядок)

Однако у меня есть две проблемы с моим подходом:

  • Эти \Xnnэкранирующие последовательности работают только в оболочке рыбы.
  • grep фактически считает количество строк, содержащих мое магическое число. Если шаблон встречается дважды в одной строке, он будет учитываться только один раз.

Есть ли способ исправить эти проблемы? Как я могу заставить этот лайнер работать в оболочке Bash и точно подсчитать, сколько раз паттерн встречается внутри файла?

hugomg
источник
некоторая помощь: unix.stackexchange.com/q/231213/117549 - в частности,grep -o
Джефф Шаллер
1
grep - неправильный инструмент для использования. Рассмотрим bgrep или bgrep2.
fpmurphy
3
Если последовательность для поиска есть 11221122, что должно быть возвращено на входе, как 112211221122? 1 или 2?
Стефан Шазелас
Я был бы в порядке с сообщением 2 или 3 матчей в этом случае. Что будет проще реализовать.
hugomg

Ответы:

15

Это запрошенное однострочное решение (для последних оболочек, которые имеют «подстановку процессов»):

grep -o "ef be ad de" <(hexdump -v -e '/1 "%02x "' infile.bin) | wc -l

Если «подстановка процесса» <(…)недоступна, просто используйте grep в качестве фильтра:

hexdump -v -e '/1 "%02x "' infile.bin  | grep -o "ef be ad de" | wc -l

Ниже приведено подробное описание каждой части решения.

Значения байтов из шестнадцатеричных чисел:

Ваша первая проблема легко решается:

Эти escape-последовательности \ Xnn работают только в оболочке рыбы.

Измените верхний Xна нижний xи используйте printf (для большинства оболочек):

$ printf -- '\xef\xbe\xad\xde'

Или используйте:

$ /usr/bin/printf -- '\xef\xbe\xad\xde'

Для тех оболочек, которые решили не реализовывать представление '\ x'.

Конечно, перевод hex в восьмеричное будет работать (почти) в любой оболочке:

$ "$sh" -c 'printf '\''%b'\'' "$(printf '\''\\0%o'\'' $((0xef)) $((0xbe)) $((0xad)) $((0xde)) )"'

Где "$ sh" - это любая (разумная) оболочка. Но довольно сложно правильно его процитировать.

Бинарные файлы.

Наиболее надежное решение - преобразовать файл и последовательность байтов (обе) в некоторую кодировку, которая не имеет проблем со значениями нечетного символа, такими как (новая строка) 0x0Aили (нулевой байт) 0x00. И то, и другое довольно сложно правильно использовать с помощью инструментов, разработанных и адаптированных для обработки «текстовых файлов».

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

$ echo "abc" | base64
YWJjCg==

$ echo "-abc" | base64
LWFiYwo=

$ echo "--abc" | base64
LS1hYmMK

$ echo "---abc" | base64        # Note that YWJj repeats.
LS0tYWJjCg==

Шестнадцатеричное преобразование

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

$ od -vAn -tx1 infile.bin | tr -d '\n'   > infile.hex
$ hexdump -v -e '/1 "%02x "' infile.bin  > infile.hex
$ xxd -c1 -p infile.bin | tr '\n' ' '    > infile.hex

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

$ var="ef be ad de"

Но это также может быть преобразовано. Ниже приведен пример кругового обхода hex-bin-hex:

$ echo "ef be ad de" | xxd -p -r | od -vAn -tx1
ef be ad de

Строка поиска может быть установлена ​​из двоичного представления. Любые из трех представленных выше вариантов od, hexdump или xxd эквивалентны. Просто убедитесь, что включены пробелы, чтобы убедиться, что совпадение находится на границах байтов (не допускается сдвиг клочка):

$ a="$(printf "\xef\xbe\xad\xde" | hexdump -v -e '/1 "%02x "')"
$ echo "$a"
ef be ad de

Если бинарный файл выглядит так:

$ cat infile.bin | xxd
00000000: 5468 6973 2069 7320 efbe adde 2061 2074  This is .... a t
00000010: 6573 7420 0aef bead de0a 6f66 2069 6e70  est ......of inp
00000020: 7574 200a dead beef 0a66 726f 6d20 6120  ut ......from a 
00000030: 6269 0a6e 6172 7920 6669 6c65 2e0a 3131  bi.nary file..11
00000040: 3232 3131 3232 3131 3232 3131 3232 3131  2211221122112211
00000050: 3232 3131 3232 3131 3232 3131 3232 3131  2211221122112211
00000060: 3232 0a

Затем простой поиск grep выдаст список совпадающих последовательностей:

$ grep -o "$a" infile.hex | wc -l
2

Одна линия?

Все это может быть выполнено в одну строку:

$ grep -o "ef be ad de" <(xxd -c 1 -p infile.bin | tr '\n' ' ') | wc -l

Например, для поиска 11221122в одном и том же файле понадобятся следующие два шага:

$ a="$(printf '11221122' | hexdump -v -e '/1 "%02x "')"
$ grep -o "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ') | wc -l
4

Чтобы «увидеть» совпадения:

$ grep -o "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ')
3131323231313232
3131323231313232
3131323231313232
3131323231313232

$ grep "$a" <(xxd -c1 -p infile.bin | tr '\n' ' ')

0a 3131323231313232313132323131323231313232313132323131323231313232 313132320a


Буферизация

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

a='ef be ad de'
hexdump -v -e '/1 "%02x "' infile.bin  | 
    sed -ue 's/\('"$a"'\)/\n\1\n/g' | 
        sed -n '/^'"$a"'$/p' |
            wc -l

Первый sed unbuffered ( -u) и используется только для вставки двух новых строк в поток для каждой соответствующей строки. Вторая sedнапечатает только (короткие) совпадающие строки. Wc -l будет считать соответствующие строки.

Это буферизует только некоторые короткие строки. Соответствующая строка (и) во втором седе. Это должно быть довольно мало используемых ресурсов.

Или, несколько сложнее понять, но та же идея в одном седе:

a='ef be ad de'
hexdump -v -e '/1 "%02x "' infile.bin  |
    sed -u '/\n/P;//!s/'"$a"'/\n&\n/;D' |
        wc -l
sorontar
источник
2
Обратите внимание, что если вы поместите весь текст в одну строку, это означает, что в grepитоге он будет загружен целиком в память (здесь в два раза больше исходного файла + 1 из-за шестнадцатеричной кодировки), так что в итоге он будет более накладные расходы, чем pythonподход или perlтот, с -0777. Вам также нужна grepреализация, которая поддерживает строки произвольной длины (те, которые поддерживают, -oкак правило, делают). Хороший ответ иначе.
Стефан Шазелас
1
Ваши шестнадцатеричные версии соответствуют сдвинутым по куску значениям? E fb ea dd e? в дополнение к желаемым байтов. od -An -tx1 | tr -d '\n'или hexdump -v -e '/1 " %02x"'с помощью строки поиска, также содержащей пробелы, избегайте этого, но я не вижу такого исправления для xxd.
dave_thompson_085
@ dave_thompson_085 Ответ отредактирован. Я считаю, что ответ будет соответствовать только границам байтов сейчас, еще раз спасибо.
Соронтар
@ StéphaneChazelas Не могли бы вы рассмотреть предложенный вариант использования небуферизованного sed. Благодарю.
Соронтар
sed -u(где доступно) для снятия буфера. Это означает, что он будет считывать по одному байту за раз на входе и сразу выводить свой вывод без буферизации. В любом случае, ему все равно потребуется загрузить всю строку в пространстве шаблона, поэтому здесь это не поможет.
Стефан Шазелас
7

В GNU grep«s -P(Perl-регулярных выражений) флаг

LC_ALL=C grep -oaP '\xef\xbe\xad\xde' file | wc -l

LC_ALL=Cсостоит в том, чтобы избежать проблем в многобайтовых локалях, где grepиначе пытались бы интерпретировать последовательности байтов как символы.

-aрассматривает двоичные файлы как текстовые файлы (вместо обычного поведения, при котором grepвыводится только то, есть ли хотя бы одно совпадение или нет)

Iruvar
источник
Это решение всегда дает мне 0 совпадений вместо правильного числа.
hugomg
@hugomg, может быть, вам нужно обратить байты, чтобы передать grep их в соответствие?
iruvar
Я не думаю, что это заказ. Два других ответа на этот вопрос работают правильно.
hugomg
2
@hugomg, это локаль. Смотрите редактировать.
Стефан Шазелас
2
Я предлагаю включить эту -aопцию, иначе grep ответит Binary file file.bin matchesза любой файл, который grep обнаружил как двоичный файл.
Соронтар
6
PERLIO=:raw perl -nE '$c++ while m/\xef\xbe\xad\xde/g; END{say $c}' file

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

thrig
источник
2
Обратите внимание, что вы не можете использовать это, если последовательность для поиска содержит байт 0xa. В этом случае вы можете использовать другой разделитель записей (с -0ooo).
Стефан Шазелас
1
@ StéphaneChazelas вы можете использовать интересующую вас последовательность как $/, с немного другим компромиссом (использование памяти пропорционально максимальному расстоянию между такими последовательностями):perl -nE 'BEGIN { $/ = "\xef\xbe\xad\xde" } chomp; $c++ unless eof && length; END { say $c }'
hobbs
@ StéphaneChazelas Пожалуйста, прочитайте мой ответ для решения для любых значений байтов.
Соронтар
1
@hobbs, в любом случае, даже здесь, использование памяти будет пропорционально максимальному расстоянию между двумя байтами 0xa, которое для нетекстовых файлов может быть сколь угодно большим.
Стефан Шазелас
5

С GNU awkвы можете сделать:

LC_ALL=C awk -v 'RS=\xef\xbe\xad\xde' 'END{print NR - (NR && RT == "")}'

Если какой-либо из байтов является оператором ERE, он должен быть экранирован (с помощью \\). Как и 0x2eчто .должно быть введено как \\.или \\\x2e. Кроме этого, он должен работать с произвольными значениями байтов, включая 0 и 0xa.

Обратите внимание, что это не так просто, NR-1потому что есть пара особых случаев:

  • когда вход пуст, NR равен 0, NR-1 даст -1.
  • когда ввод заканчивается в разделителе записей, пустая запись после этого не создается. Мы проверяем это сRT=="" .

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

Стефан Шазелас
источник
5

Самый простой перевод, который я вижу:

$ echo $'\xef\xbe\xad\xde' > hugohex
$ echo $'\xef\xbe\xad\xde\xef\xbe\xad\xde' >> hugohex
$ grep -F -a -o -e $'\xef\xbe\xad\xde' hugohex|wc -l
3

Где я использовал в $'\xef'качестве Баша ANSI-цитирование (первоначально ksh93функции, теперь поддерживается zsh, bash, mksh, FreeBSD sh) версия рыбы \Xef, и используется grep -o ... | wc -lдля подсчета экземпляров. grep -oвыводит каждое совпадение на отдельной строке. -aФлаг делает Grep себя на бинарные файлы так же , как это делает на текстовые файлы. -Fпредназначен для фиксированных строк, поэтому вам не нужно экранировать операторы регулярных выражений.

Как и в вашем fishслучае, вы не можете использовать этот подход, хотя, если последовательность поиска включает байты 0 или 0xa (перевод строки в ASCII).

Джефф Шаллер
источник
Использование printf '%b' $(printf '\\%o ' $((0xef)) $((0xbe)) $((0xad)) $((0xde))) > hugohex'будет наиболее переносимым методом «чистой оболочки». Конечно, printf "efbeadde" | xxd -p -r > hugohexкажется наиболее практичным методом.
Соронтар
4

Вы можете использовать bytes.countметод Python, чтобы получить общее количество неперекрывающихся подстрок в строке байтов.

python -c "print(open('./myexecutable', 'rb').read().count(b'\xef\xbe\xad\xde'))"

Этот однострочный загружает весь файл в память, поэтому не самый эффективный, но работает и более разборчив, чем Perl; D

Ник Т
источник
«более разборчиво, чем Perl» - это всего лишь один шаг по сравнению с TECO, а именно IINM: 239I$ 190I$ 173I$ 222I$ HXA ERfile$Y 0UC <:S^EQA$; %C$> QC=(gd & r)
dave_thompson_085
Вы можете mmap()файл в Python ; это уменьшило бы фиксацию памяти.
Тоби Спейт
1
tr "$(printf \\0xef)\n" \\n\\0 < infile |
grep -c "^$(printf "\0xbe\0xad\0xde")"
mikeserv
источник
1

Я думаю, что вы можете использовать Perl, попробуйте:

perl -0777ne 'CORE::say STDOUT s/\xef\xbe\xad\xde//g' file_name  

Команда Replace sдает число выполненных замен, -0777 означает, что новая строка не рассматривается как специальный символ, e- выполните команду, sayчтобы напечатать то, что идет дальше, затем напечатать символ новой строки,n я не полностью понял, но не работает без документы:

заставляет Perl предполагать следующий цикл вокруг вашей программы, который заставляет его перебирать аргументы имени файла, вроде sed -n или awk: LINE: while (<>) {... # ваша программа идет сюда}

Алексей Мартианов
источник