Methodology of software expertise based on improved windowed entropy calculation algorithm

S.V. Karbovskiy

Abstract


The article discusses an algorithm for calculating the sliding entropy of a binary file with an intersection between adjacent blocks. The relevance of the study is due to the widespread use of entropy analysis in software expertise. The currently used algorithm for calculating entropy with intersection between adjacent blocks has quadratic complexity in the worst case. As a result, the entropy calculation algorithm used in the analysis tools divides the input file into disjoint blocks, which reduces the accuracy of entropy analysis. The paper analyzes the changes in the information entropy of a message when one character changes in it. It is determined that calculations of entropy changes, regardless of the ratio of the frequency of occurrence of deleted and added characters in the message, can be carried out in constant time. As a result of the analysis of the revealed dependencies, a more productive algorithm for calculating the sliding entropy of binary files with intersecting blocks has been developed. It is shown that the developed algorithm makes it possible to calculate entropy with an arbitrary amount of displacement between adjacent blocks of the file. An experimental evaluation of the accuracy and performance of the algorithm was carried out. It is revealed that the performance gain when using the developed algorithm increases with a decrease in the offset between adjacent blocks. The study is intended for specialists in the field of system analysis of software, as well as in the field of reverse engineering of software.


Full Text:

PDF (Russian)

References


Cortesi A. Visualizing entropy in binary files // Aldo Cortesi. 2012. URL: https://corte.si/posts/visualisation/entropy/ (visited: 16.11.2022).

Nesterovich S.A., Kuptsova Yu.I. On some possibilities of hidden malicious code detection //Proceedings of the Russian New University. Serie: Complex Systems: models, analysis and control. – 2021. – № 3. – С. 156-161. – DOI 10.25586/RNU.V9187.21.03.P.156.

Benvenuto F. et al. Firmware Extraction from Real IoT Devices through Power Analysis of AES //ITASEC. – 2021. – C. 461-474.

Hui T.X., Mohamad K.M., Rahman N.H.A. myEntropy: a file type identification tool using entropy scoring //International Journal of Electronic Security and Digital Forensics. – 2022. – T.14. – № 1. – C. 76-95.

Kopyltsov A.V. Wavelet-analysis of the file structural entropy //Proceedings of Russian State Pedagogical University. – 2011. – № 138. – С. 7-15.

Sorokin I.V. Mathematical models and algorithms of packed malicious program recognition: diss. – Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, 2013.

Yuganson A.N. Method for determining packed and encrypted data inside of embedded software //Scientific and Technical Bulletin of Information Technologies, Mechanics and Optics. – 2020. – Т. 20. – №. 5. – С. 708-713.

Lyda R., Hamrock J. Using entropy analysis to find encrypted and packed malware //IEEE Security & Privacy. – 2007. – T. 5. – № 2. – C. 40-45.

Ugarte-Pedrero X. et al. Countering entropy measure attacks on packed software detection //2012 IEEE Consumer Communications and Networking Conference (CCNC). – IEEE, 2012. – С. 164-168.

Choi M.J. et al. All-in-one framework for detection, unpacking and verification for malware analysis //Security and Communication Networks. – 2019. – T. 2019. – DOI: 10.1155/2019/5278137.

BinGraph // Github. URL: https://github.com/geekscrapy/binGraph (visited: 16.11.2022).

Bintropy // Github. URL: https://github.com/packing-box/binropy (visited: 16.11.2022).

Binwalk // Github. URL: https://github.com/ReFirmLabs/binwalk (visited: 16.11.2022).

Detect-It-Easy // Github. URL: https://github.com/horsicq/Detect-It-Easy (visited: 16.11.2022).

EntroPy // Github. URL: https://github.com/gcmartinelli/entroPy (visited: 16.11.2022).

Ghidra // Github. URL: https://github.com/NSA/ghidra (visited: 16.11.2022).

Mittal G., Korus P., Memon N. FiFTy: large-scale file fragment type identification using convolutional neural networks //IEEE Transactions on Information Forensics and Security. – 2020. – Т. 16.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162