Jak mogę policzyć, ile razy sekwencja bajtów występuje w pliku?

16

Chcę policzyć, ile razy pewna sekwencja bajtów dzieje się w pliku, który mam. Na przykład chcę dowiedzieć się, ile razy liczba \0xdeadbeefwystępuje w pliku wykonywalnym. Teraz robię to za pomocą grep:

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

(Bajty są zapisywane w odwrotnej kolejności, ponieważ mój procesor to little-endian)

Mam jednak dwa problemy z moim podejściem:

  • Te \Xnnsekwencje ucieczki działają tylko w skorupkach ryb.
  • grep faktycznie liczy liczbę linii, które zawierają moją magiczną liczbę. Jeśli wzorzec występuje dwa razy w tej samej linii, będzie liczony tylko raz.

Czy istnieje sposób na rozwiązanie tych problemów? Jak mogę uruchomić ten jeden liner w powłoce Bash i dokładnie zliczyć liczbę wystąpień wzoru w pliku?

hugomg
źródło
pomoc: unix.stackexchange.com/q/231213/117549 - konkretniegrep -o
Jeff Schaller
1
grep jest niewłaściwym narzędziem do użycia. Rozważ bgrep lub bgrep2.
fpmurphy
3
Jeśli sekwencją do wyszukania jest 11221122, co należy zwrócić na danych wejściowych, takich jak 112211221122? 1 lub 2?
Stéphane Chazelas,
W takim przypadku zgodziłbym się na zgłoszenie 2 lub 3 meczów. Cokolwiek byłoby łatwiejsze do wdrożenia.
hugomg

Odpowiedzi:

15

Jest to wymagane rozwiązanie jednowierszowe (dla najnowszych powłok, które mają „podstawianie procesów”):

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

Jeśli nie <(…)jest dostępne „podstawienie procesu” , użyj grep jako filtru:

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

Poniżej znajduje się szczegółowy opis każdej części rozwiązania.

Wartości bajtów z liczb szesnastkowych:

Twój pierwszy problem jest łatwy do rozwiązania:

Te sekwencje specjalne \ Xnn działają tylko w skorupkach ryb.

Zmień górną Xna dolną xi użyj printf (dla większości powłok):

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

Albo użyj:

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

Dla tych powłok, które zdecydują się nie implementować reprezentacji „\ x”.

Oczywiście, przełożenie hex na ósemkowe będzie działać na (prawie) dowolnej powłoce:

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

Gdzie „$ sh” jest dowolną (rozsądną) powłoką. Ale trudno jest poprawnie go podać.

Pliki binarne.

Najbardziej niezawodnym rozwiązaniem jest transformacja pliku i sekwencji bajtów (oba) na kodowanie, które nie ma problemów z nieparzystymi wartościami znaków, takimi jak (nowa linia) 0x0Alub (bajt zerowy) 0x00. Oba są dość trudne do prawidłowego zarządzania za pomocą narzędzi zaprojektowanych i przystosowanych do przetwarzania „plików tekstowych”.

Transformacja taka jak base64 może wydawać się poprawna, ale przedstawia problem polegający na tym, że każdy bajt wejściowy może mieć maksymalnie trzy reprezentacje wyjściowe, w zależności od tego, czy jest to pierwszy, drugi czy trzeci bajt pozycji mod 24 (bitów).

$ echo "abc" | base64
YWJjCg==

$ echo "-abc" | base64
LWFiYwo=

$ echo "--abc" | base64
LS1hYmMK

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

Przekształcenie heksadecymalne.

Właśnie dlatego najbardziej niezawodną transformacją powinna być taka, która rozpoczyna się na każdej granicy bajtów, podobnie jak prosta reprezentacja HEX.
Możemy uzyskać plik z reprezentacją szesnastkową pliku za pomocą dowolnego z tych narzędzi:

$ 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

W tym przypadku sekwencja bajtów do przeszukiwania jest już szesnastkowa.
:

$ var="ef be ad de"

Ale można go również przekształcić. Oto przykład szesnastkowego pojemnika szesnastkowego w obie strony:

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

Wyszukiwany ciąg może być ustawiony z reprezentacji binarnej. Każda z trzech opcji przedstawionych powyżej od, hexdump lub xxd są równoważne. Pamiętaj tylko, aby uwzględnić spacje, aby upewnić się, że dopasowanie znajduje się na granicach bajtów (niedozwolone jest przesunięcie końcówki):

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

Jeśli plik binarny wygląda następująco:

$ 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

Następnie proste wyszukiwanie grep wyświetli listę pasujących sekwencji:

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

Jedna linia?

Wszystko to można wykonać w jednym wierszu:

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

Na przykład wyszukiwanie 11221122w tym samym pliku wymaga dwóch następujących kroków:

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

Aby „zobaczyć” dopasowania:

$ 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


Buforowanie

Istnieje obawa, że ​​grep zbuforuje cały plik, a jeśli plik jest duży, spowoduje duże obciążenie komputera. W tym celu możemy użyć niebuforowanego rozwiązania 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

Pierwszy sed jest niebuforowany (-u ) i służy tylko do wstrzykiwania dwóch nowych wierszy do strumienia na pasujący ciąg. Drugi sedwydrukuje tylko (krótkie) pasujące linie. Wc -l policzy pasujące linie.

Spowoduje to buforowanie tylko niektórych krótkich linii. Pasujące łańcuchy w drugim sed. Powinno to być dość niskie w wykorzystywanych zasobach.

Lub nieco bardziej skomplikowany do zrozumienia, ale ten sam pomysł w jednym 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
źródło
2
Zauważ, że jeśli umieścisz cały tekst w jednym wierszu, oznacza to, że w grepkońcu załadujesz go do pamięci (tutaj dwukrotnie większy niż oryginalny plik + 1 ze względu na kodowanie szesnastkowe), więc ostatecznie będzie więcej nad głową niż pythonpodejście lub ten perlz -0777. Potrzebujesz także grepimplementacji, która obsługuje wiersze o dowolnej długości (te, które obsługują, -ozazwyczaj tak robią). W przeciwnym razie dobra odpowiedź.
Stéphane Chazelas,
1
Twoje wersje szesnastkowe pasują do wartości przesuniętych przez skubanie? E fb ea dd e? oprócz żądanych bajtów. od -An -tx1 | tr -d '\n'lub hexdump -v -e '/1 " %02x"'z ciągiem wyszukiwania uniknąć również zawierające przestrzenie, ale nie widzę taką poprawkę xxd.
dave_thompson_085
@ dave_thompson_085 Odpowiedź edytowana. Wierzę, że odpowiedź będzie teraz pasować tylko do granic bajtów, jeszcze raz dziękuję.
sorontar
@ StéphaneChazelas Czy mógłbyś przejrzeć proponowaną opcję użycia niebuforowanego sed. Dzięki.
sorontar,
sed -u(jeśli jest dostępny) służy do rozpakowywania. Oznacza to, że będzie czytał jeden bajt na raz na wejściu i od razu wysyła swoje wyjście bez buforowania. W anycase nadal będzie musiał załadować całą linię do obszaru wzorów, więc tutaj nie pomoże.
Stéphane Chazelas,
7

Z GNU grep„s -Pflag (Perl-regexp)

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

LC_ALL=Cpolega na unikaniu problemów w ustawieniach wielobajtowych, w których w grepinnym przypadku próbowano by interpretować sekwencje bajtów jako znaki.

-atraktuje pliki binarne równoważne plikom tekstowym (zamiast normalnego zachowania, gdzie grepwypisuje tylko, czy jest co najmniej jedno dopasowanie, czy nie)

iruvar
źródło
To rozwiązanie zawsze daje mi 0 dopasowań zamiast prawidłowej liczby.
hugomg
@hugomg, czy może być konieczne odwrócenie przekazanych bajtów grep , aby dopasować?
iruvar
Nie sądzę, że to jest kolejność. Pozostałe dwie odpowiedzi na to pytanie działają poprawnie.
hugomg
2
@hugomg, to lokalizacja. Zobacz edycję.
Stéphane Chazelas,
2
Proponuję zawrzeć -aopcję, w przeciwnym razie grep odpowie Binary file file.bin matchesna każdy plik, który grep rozpozna jako binarny.
sorontar
6
PERLIO=:raw perl -nE '$c++ while m/\xef\xbe\xad\xde/g; END{say $c}' file

Który traktuje pliki wejściowe jako pliki binarne (brak tłumaczenia dla źródeł i kodowania, patrz Perlrun ), a następnie zapętla pliki wejściowe, nie drukując, zwiększając licznika dla wszystkich dopasowań danego heksadecymalnego (lub dowolnej postaci, patrz perlre ) .

gałązka
źródło
2
Zauważ, że nie możesz tego użyć, jeśli szukana sekwencja zawiera bajt 0xa. W takim przypadku możesz użyć innego separatora rekordów (z -0ooo).
Stéphane Chazelas,
1
@ StéphaneChazelas możesz użyć interesującej cię sekwencji, ponieważ $/z nieco innym kompromisem (użycie pamięci proporcjonalne do maksymalnej odległości między takimi sekwencjami):perl -nE 'BEGIN { $/ = "\xef\xbe\xad\xde" } chomp; $c++ unless eof && length; END { say $c }'
hobbs
@ StéphaneChazelas Proszę przeczytać moją odpowiedź, aby znaleźć rozwiązanie dla dowolnych wartości bajtów.
sorontar
1
@ hobbs, w każdym razie, nawet tutaj, użycie pamięci będzie proporcjonalne do maksymalnej odległości między dwoma bajtami 0xa, która dla plików nietekstowych może być dowolnie duża.
Stéphane Chazelas,
5

Dzięki GNU awkmożesz:

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

Jeśli którykolwiek z bajtów jest operatorem ERE, trzeba by go jednak uciec (za pomocą \\). Podobnie jak 0x2eto ., które należy wprowadzić jako \\.lub \\\x2e. Poza tym powinien działać z dowolnymi wartościami bajtów, w tym 0 i 0xa.

Pamiętaj, że nie jest to tak proste, jak tylko NR-1dlatego, że istnieje kilka specjalnych przypadków:

  • gdy wejście jest puste, NR wynosi 0, NR-1 daje -1.
  • gdy dane wejściowe kończą się w separatorze rekordów, pusty rekord nie jest tworzony. Testujemy na to za pomocą RT=="".

Zauważ też, że w najgorszym przypadku (jeśli plik nie zawiera wyszukiwanego terminu), plik zostanie w całości załadowany do pamięci).

Stéphane Chazelas
źródło
5

Najbardziej proste tłumaczenie, jakie widzę, to:

$ 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

Gdzie użyłem $'\xef'jako bash ANSI powołujący (pierwotnie ksh93funkcję, teraz obsługiwane przez zsh, bash, mksh, FreeBSD sh) wersja Fisha \Xefi wykorzystywane grep -o ... | wc -ldo liczenia wystąpień. grep -owypisuje każde dopasowanie w osobnej linii. -aFlag sprawia grep zachowywać w plikach binarnych w ten sam sposób to robi na plikach tekstowych. -Fjest dla stałych ciągów, więc nie musisz uciekać operatorom wyrażeń regularnych.

Podobnie jak w twoim fishprzypadku, nie możesz użyć tego podejścia, jeśli szukana sekwencja zawiera bajty 0 lub 0xa (nowa linia w ASCII).

Jeff Schaller
źródło
Użycie printf '%b' $(printf '\\%o ' $((0xef)) $((0xbe)) $((0xad)) $((0xde))) > hugohex'byłoby najbardziej przenośną metodą „czystej powłoki”. Oczywiście: printf "efbeadde" | xxd -p -r > hugohexwydaje się najbardziej praktyczną metodą.
sorontar
4

Możesz użyć bytes.countmetody Pythona, aby uzyskać całkowitą liczbę nie nakładających się podciągów w bajtowaniu.

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

Ten jednowierszowy ładuje cały plik do pamięci, więc nie jest najbardziej wydajny, ale działa i jest bardziej czytelny niż Perl; D

Nick T.
źródło
„bardziej czytelny niż Perl” to tylko jeden krok w górę od TECO - którym IINM jest: 239I$ 190I$ 173I$ 222I$ HXA ERfile$Y 0UC <:S^EQA$; %C$> QC=(gd & r)
dave_thompson_085
Możesz mmap()plik w Pythonie ; to zmniejszy zatwierdzenie pamięci.
Toby Speight
1
tr "$(printf \\0xef)\n" \\n\\0 < infile |
grep -c "^$(printf "\0xbe\0xad\0xde")"
mikeserv
źródło
1

Myślę, że możesz użyć Perla, spróbuj:

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

Polecenie Zamień spodaje liczbę wykonanych zamian, -0777 oznacza, że ​​nie traktuj nowej linii jako znaku specjalnego, e- wykonaj komendę, sayaby wydrukować, co będzie dalej, wypisz znak nowej linii, nnie do końca zrozumiałem, ale nie działa bez - z dokumenty:

powoduje, że Perl zakłada następującą pętlę wokół twojego programu, co powoduje iterację argumentów nazw plików, takich jak sed -n lub awk: LINE: while (<>) {... # twój program idzie tutaj}

Aleksiej Martianow
źródło