Como posso contar o número de vezes que uma sequência de bytes ocorre em um arquivo?

16

Quero contar quantas vezes uma determinada sequência de bytes acontece dentro de um arquivo que eu tenho. Por exemplo, quero descobrir quantas vezes o número \0xdeadbeefocorre dentro de um arquivo executável. No momento, estou fazendo isso usando o grep:

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

(Os bytes são escritos em ordem inversa porque minha CPU é little-endian)

No entanto, tenho dois problemas com minha abordagem:

  • Essas \Xnnseqüências de escape funcionam apenas na casca do peixe.
  • grep está contando o número de linhas que contêm meu número mágico. Se o padrão ocorrer duas vezes na mesma linha, contará apenas uma vez.

Existe uma maneira de corrigir esses problemas? Como posso executar esse liner único no shell Bash e contar com precisão o número de vezes que o padrão ocorre dentro do arquivo?

hugomg
fonte
alguma ajuda: unix.stackexchange.com/q/231213/117549 - especificamente,grep -o
Jeff Schaller
11
grep é a ferramenta errada a ser usada. Considere bgrep ou bgrep2.
fpmurphy
3
Se a sequência a ser pesquisada for 11221122, como deve ser retornado em uma entrada 112211221122? 1 ou 2?
Stéphane Chazelas
Eu ficaria bem em relatar 2 ou 3 correspondências nesse caso. O que for mais simples de implementar.
hugomg

Respostas:

15

Esta é a solução de uma linha solicitada (para shells recentes que têm "substituição de processo"):

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

Se nenhuma "substituição de processo" <(…)estiver disponível, use grep como um filtro:

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

Abaixo está a descrição detalhada de cada parte da solução.

Valores de bytes de números hexadecimais:

Seu primeiro problema é fácil de resolver:

Essas seqüências de escape \ Xnn funcionam apenas na casca do peixe.

Altere o superior Xpara o inferior xe use printf (para a maioria das conchas):

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

Ou use:

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

Para aqueles shells que optam por não implementar a representação '\ x'.

Obviamente, traduzir hex para octal funcionará em (quase) qualquer shell:

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

Onde "$ sh" é qualquer shell (razoável). Mas é bastante difícil mantê-lo corretamente citado.

Arquivos binários.

A solução mais robusta é transformar o arquivo e a sequência de bytes (ambos) em alguma codificação que não apresenta problemas com valores de caracteres ímpares como (nova linha) 0x0Aou (byte nulo) 0x00. Ambos são bastante difíceis de gerenciar corretamente com ferramentas projetadas e adaptadas para processar "arquivos de texto".

Uma transformação como base64 pode parecer válida, mas apresenta o problema de que cada byte de entrada pode ter até três representações de saída, dependendo do primeiro, segundo ou terceiro byte da posição mod 24 (bits).

$ echo "abc" | base64
YWJjCg==

$ echo "-abc" | base64
LWFiYwo=

$ echo "--abc" | base64
LS1hYmMK

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

Transformação hexadecimal.

É por isso que a transformação mais robusta deve ser aquela que começa no limite de cada byte, como a simples representação HEX.
Podemos obter um arquivo com a representação hexadecimal do arquivo com qualquer uma destas ferramentas:

$ 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

A sequência de bytes a ser pesquisada já está em hexadecimal neste caso.
:

$ var="ef be ad de"

Mas também pode ser transformado. Um exemplo de uma viagem de ida e volta hex-bin-hex segue:

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

A cadeia de pesquisa pode ser definida a partir da representação binária. Qualquer uma das três opções apresentadas acima od, hexdump ou xxd são equivalentes. Apenas certifique-se de incluir os espaços para garantir que a correspondência esteja nos limites de bytes (nenhum deslocamento de mordidela é permitido):

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

Se o arquivo binário estiver assim:

$ 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

Em seguida, uma simples pesquisa grep fornecerá a lista de sequências correspondentes:

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

Uma linha?

Tudo pode ser realizado em uma linha:

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

Por exemplo, procurar 11221122no mesmo arquivo precisará destas duas etapas:

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

Para "ver" as correspondências:

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

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

… 0a 313132323131323231313232313132323131323231313232313132323131313232 313132320a


Carregando

Há uma preocupação de que o grep armazene em buffer todo o arquivo e, se o arquivo for grande, criará uma carga pesada para o computador. Para isso, podemos usar uma solução sed sem buffer:

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

O primeiro sed é sem buffer ( -u) e é usado apenas para injetar duas novas linhas no fluxo por sequência correspondente. O segundo sedimprimirá apenas as linhas (curtas) correspondentes. O wc -l contará as linhas correspondentes.

Isso armazenará apenas algumas linhas curtas. A (s) string (s) correspondente (s) no segundo sed. Isso deve ser bastante baixo em recursos utilizados.

Ou, um pouco mais complexo de entender, mas a mesma ideia em um sed:

a='ef be ad de'
hexdump -v -e '/1 "%02x "' infile.bin  |
    sed -u '/\n/P;//!s/'"$a"'/\n&\n/;D' |
        wc -l
sorontar
fonte
2
Observe que, se você colocar todo o texto em uma linha, isso significa grepque o carregamento será inteiro na memória (aqui o dobro do tamanho do arquivo original + 1 por causa da codificação hexadecimal); portanto, no final, ele acaba sendo mais sobrecarga do que a pythonabordagem ou perlaquele com -0777. Você também precisa de uma grepimplementação que suporte linhas de comprimento arbitrário (aquelas que -ogeralmente suportam ). Boa resposta caso contrário.
Stéphane Chazelas
11
Suas versões hexadecimais correspondem aos valores de nibble-shifted? E fb e a dd e? além dos bytes desejados. od -An -tx1 | tr -d '\n'ou hexdump -v -e '/1 " %02x"'com uma sequência de pesquisa que também contenha espaços, evite isso, mas não vejo essa correção xxd.
David_thompson_085
@ dave_thompson_085 Resposta editada. Acredito que a resposta só corresponda aos limites de bytes agora, obrigado novamente.
sorontar
@ StéphaneChazelas Você poderia revisar a opção proposta de usar um sed sem buffer. Obrigado.
sorontar
sed -u(quando disponível) é para o buffer. Isso significa que ele lerá um byte de cada vez na entrada e enviará sua saída imediatamente sem buffer. Em qualquer caso, ele ainda precisará carregar toda a linha no espaço do padrão, portanto não ajudará aqui.
Stéphane Chazelas
7

Com GNU grep's -P(perl-regexp) flag

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

LC_ALL=Cé evitar problemas em códigos de idioma de vários bytes que grep, de outra forma, tentariam interpretar sequências de bytes como caracteres.

-atrata arquivos binários equivalentes a arquivos de texto (em vez do comportamento normal, onde grepapenas imprime se há pelo menos uma correspondência ou não)

iruvar
fonte
Esta solução está sempre me dando 0 correspondências em vez do número correto.
Hugomg
@ hugomg, pode ser que você precise reverter os bytes passados ​​para grep que ele corresponda?
Iruvar
Eu não acho que é a ordem. As outras duas respostas para esta pergunta funcionam corretamente.
hugomg
2
@ hugomg, é o local. Veja editar.
Stéphane Chazelas
2
Sugerirei incluir a -aopção, caso contrário, o grep responderá com Binary file file.bin matchesqualquer arquivo que o grep detectar como binário.
sorontar
6
PERLIO=:raw perl -nE '$c++ while m/\xef\xbe\xad\xde/g; END{say $c}' file

Que trata o (s) arquivo (s) de entrada como binário (sem conversão para alimentações de linha ou codificações, consulte perlrun ), circula o (s) arquivo (s) de entrada não imprimindo incrementando um contador para todas as correspondências do hexadecimal fornecido (ou qualquer outra forma, consulte perlre ) .

agitar
fonte
2
Observe que você não pode usá-lo se a sequência a procurar contiver o byte 0xa. Nesse caso, você pode usar um separador de registros diferente (com -0ooo).
Stéphane Chazelas
11
@ StéphaneChazelas você pode usar a sequência de interesse em si $/, pois , com uma troca ligeiramente diferente (uso de memória proporcional à distância máxima entre essas seqüências):perl -nE 'BEGIN { $/ = "\xef\xbe\xad\xde" } chomp; $c++ unless eof && length; END { say $c }'
hobbs
@ StéphaneChazelas Leia minha resposta para obter uma solução para quaisquer valores de bytes.
sorontar
11
@hobbs, em qualquer caso, mesmo aqui, o uso da memória será proporcional à distância máxima entre dois bytes de 0xa que, para arquivos não-texto, pode ser arbitrariamente grande.
Stéphane Chazelas
5

Com o GNU awk, você pode fazer:

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

Se algum dos bytes for um operador ERE, eles terão que ser escapados (com \\). Como o 0x2eque é .teria que ser inserido como \\.ou \\\x2e. Fora isso, ele deve funcionar com valores de bytes arbitrários, incluindo 0 e 0xa.

Observe que não é tão simples quanto apenas NR-1porque existem alguns casos especiais:

  • quando a entrada está vazia, NR é 0, NR-1 daria -1.
  • quando a entrada termina no separador de registros, um registro vazio não é criado depois disso. Testamos isso com RT=="".

Observe também que, na pior das hipóteses (se o arquivo não contiver o termo de pesquisa), o arquivo acabará sendo carregado inteiro na memória).

Stéphane Chazelas
fonte
5

A tradução mais direta que vejo é:

$ 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

Onde eu usei $'\xef'como a festa ANSI-citando (originalmente um ksh93recurso, agora apoiado por zsh, bash, mksh, FreeBSD sh) versão de peixes de \Xef, e usados grep -o ... | wc -lpara contar os casos. grep -oproduz cada partida em uma linha separada. A -asinalização faz com que o grep se comporte nos arquivos binários da mesma forma que nos arquivos de texto. -Fé para cadeias fixas, para que você não precise escapar dos operadores de expressões regulares.

Como no seu fishcaso, você não pode usar essa abordagem se a sequência a procurar incluir os bytes 0 ou 0xa (nova linha em ASCII).

Jeff Schaller
fonte
Usar printf '%b' $(printf '\\%o ' $((0xef)) $((0xbe)) $((0xad)) $((0xde))) > hugohex'seria o método "shell puro" mais portátil. Claro: printf "efbeadde" | xxd -p -r > hugohexparece ser o método mais prático.
sorontar
4

Você pode usar o bytes.countmétodo Python para obter o número total de substrings não sobrepostos em uma bytestring.

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

Esse liner carregará o arquivo inteiro na memória, portanto não é o mais eficiente, mas funciona e é mais legível que o Perl; D

Nick T
fonte
'mais legível que o Perl' está a apenas um passo do TECO - que é o IINM: 239I$ 190I$ 173I$ 222I$ HXA ERfile$Y 0UC <:S^EQA$; %C$> QC=(gd & r)
dave_thompson_085
Você pode mmap()um arquivo em Python ; isso reduziria a confirmação da memória.
Toby Speight
1
tr "$(printf \\0xef)\n" \\n\\0 < infile |
grep -c "^$(printf "\0xbe\0xad\0xde")"
mikeserv
fonte
1

Eu acho que você pode usar Perl, tente:

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

O comando Replace sfornece o número de substituições feitas, -0777 significa não tratar a nova linha como caractere especial, e- execute o comando, saypara imprimir o que vem a seguir e, em seguida, imprima o novo caractere de linha,n eu não tinha entendido completamente, mas não funciona sem / - from docs:

faz com que o Perl assuma o seguinte loop em torno do seu programa, o que faz com que ele itere sobre os argumentos do nome do arquivo, como sed -n ou awk: LINE: while (<>) {... # seu programa está aqui}

Alexei Martianov
fonte