Evaluating obfuscation method by Kolmogorov complexity

🗣 Overview

This paper quantifies the diffuculty of program analysis based on the information theory. The basic idea is to consider that a program ultimately obscated if instructions appear at random; that is (1) all instructions has an equal frequency of appearance, and (2) there is no pattern observed in the instruction sequence. We quantified (1) based on the entropy and (2) based on the Kolmogorov complexity. We evaluated the feasibility of our proposal through a case study.

(Abstract from Computer Software, Vol.30, No. 3)

📚 Publications

• 二村 阿美，門田 暁人，玉田 春昭，神崎 雄一郎，中村 匡秀，松本 健一，“命令のランダム性に基づくプログラム難読化の評価”，コンピュータソフトウェア, Vol. 30, No. 3, pp. 18-24, September 2013.
• 二村 阿美，門田 暁人，玉田 春昭，神崎 雄一郎，中村 匡秀，松本 健一，“命令の乱雑さに基づくプログラム理解性の評価”，ソフトウェア工学の基礎XIX，日本ソフトウェア科学会 FOSE2012 (FOSE2012), pp.151–160, December 2012 (Reviewed).

🔎 Related Research Topics

• Artificiality evaluation of obfuscations
• De-obfuscate IRM (identifier renaming method)
• Unreadability evaluation of obfuscated programs

🤝 Collaborators

• A. Monden@Software mesurement and analytics laboratory, Okayama University
• M. Nakamura@Kobe University
• Y. Kanzaki@Kumamoto National College of Technology